Function: a mathematical rule that correlates a number (or group of numbers) with another number.

A function picks one or more numbers and determines the correlated number by a process of calculation. We define functions by stating the formula by which their results are calculated, as in the following.

                                    f(x) = x²

This function assigns any number its square; for example, f(2) = 2² = 4 or f(3) = 3² = 9. The variable x in this definition stands for any given number. An example of a function with two numbers is

                                    s(x,y) = x+y

This function gives us the sum of any two numbers x and y, such as s(1,2) = 3 or s(3,3) = 6. A function can be recursive; that is, its definition can refer to the function itself as a numerical input value. This is the case with the so-called faculty function:

                                    f(0) = 1
                                    f(x) = x ∙ f(x-1)

As you can see here, this function already requires two lines for its definition. In addition, in order to calculate the result of this function for any given numerical value we first need to calculate the corresponding results for all smaller numerical values. When we replace the variable x by actual numbers we obtain these results:

f(1) = 1 ∙ f(0) = 1
f(2) = 2
∙ f(1) = 2  ∙ 1 = 2
f(3) = 3
∙ f(2) = 3  ∙ 2 = 6
f(4) = 4
∙ f(3) = 4  ∙ 6 = 24
f(5) = 5
∙ f(4) = 5  ∙ 24 = 120
f(6) = 6
∙ f(5) = 6  ∙ 120 = 720
f(7) = 7
∙ f(6) = 7  ∙ 720 = 5040
.

As you can see here, the faculty function's output values quickly increase even at the level of small input values. However, there are even more interesting functions. One famous recursive function is the Mandelbrot function, which is described in the article on fractals.

Beyond All Limits

An even more peculiar recursive function is the Ackermann function, which was first discovered in 1926 by Wilhelm Ackermann and later reformulated and simplified in 1955 by the Hungarian mathematician Rózsa Péter. This is a function whose values increase beyond all limits. In Rózsa Péter's variation, it is defined as follows:

a(0,x) = x+1
a(y,0) = a(y-1,1)
a(x,y) = a(x-1,a(x,y-1))

Taken by itself, this definition looks entirely innocuous, involving as it does only the arithmetic operations of adding and subtracting the number 1. Nevertheless, it turns out to be full of surprises. Though the Ackermann function can be computed for any numerical input value in a finite number of steps, one cannot predict the number of steps a given computation will require on the basis of the input values used. This is because with the Ackermann function, unlike the faculty function, knowing the functional output values for smaller input numbers does not enable one to know the number of steps that will be required for a larger input number. To understand this, let us take a look at the individual computational steps involved in the calculation of a(1,1) and a(2,2):

a(1,1)
= a(0,a(1,0))
= a(0,a(0,1))
= a(0,1+1)
= 3

a(2,2)
= a(1,a(2,1))
= a(1,a(1,a(2,0)))
= a(1,a(1,a(1,1)))
= a(1,a(1,a(0,a(1,0))))
= a(1,a(1,a(0,a(0,1))))
= a(1,a(1,a(0,2)))
= a(1,a(1,3))
= a(1,a(0,a(1,2)))
= a(1,a(0,a(0,a(1,1))))
= a(1,a(0,a(0,a(0,a(1,0)))))
= a(1,a(0,a(0,a(0,a(0,1)))))
= a(1,a(0,a(0,a(0,2))))
= a(1,a(0,a(0,3)))
= a(1,a(0,4))
= a(1,5)
= a(0,a(1,4))
= a(0,a(0,a(1,3)))
= a(0,a(0,a(0,a(1,2))))
= a(0,a(0,a(0,a(0,a(1,1)))))
= a(0,a(0,a(0,a(0,a(0,a(0,1)))))
= a(0,a(0,a(0,a(0,a(0,a(1,0)))))
= a(0,a(0,a(0,a(0,a(0,2)))))
= a(0,a(0,a(0,a(0,3))))
= a(0,a(0,a(0,4)))
= a(0,a(0,5))
= a(0,6)
= 7

That is a lot of computational steps even at the level of such small numerical input values as 2 and 2, which yield the modest functional value 7. With a(3,2) we already obtain a functional value as large as 29. And a(4,2) yields a 19727-digit number - much larger than the number of atoms in the visible universe (see www.kosara.net/thoughts/ackermann.html). Finally, though a(5,2) is still a finite number, no one to date has tried to compute it, and there is reason to suspect that no one ever will.

Bijections

Then there are the functions known as bijections. A bijection assigns to each number of a given input set exactly one output number, and vice versa. Thus, in contrast to ordinary functions, with a bijection it is impossible for two different input numbers to be assigned the same output number. The function

                                    f(x) = x²

is therefore not a bijection, since it assigns both the number 2 and the number -2 the same output number, namely, 4. However, the function

                                    f(x) = 2x

is a bijection.

Bijections serve to define infinite sets. The mathematician Dedekind defined an infinite set as a set that is bijective with regard to one of its proper subsets. According to this definition, the set of natural numbers is infinite, since it has a bijection f(x) = 2x on one of its proper subsets (namely, the set of even numbers). Dedekind used this definition to prove that the set of his own ►thoughts is infinite.


 

© Johann Christian Lotter   ■  Infinity  ■  Links  ■  Forum