Funktion, eine mathematische Rechenvorschrift, die einer Zahl (oder mehreren Zahlen) eine andere Zahl zuordnet.

Eine Funktion nimmt also eine oder mehrere Zahlen und errechnet daraus als Resultat die zugeordnete Zahl. Man definiert Funktionen, indem man die Formel zur Berechnung ihres Resultats angibt, also etwa so:

                                    f(x) = x²

Diese Funktion ordnet einer Zahl deren Quadratzahl zu: f(2) = 2² = 4, oder f(3) = 3² = 9. Das x in der Definition steht für irgendeine beliebige Zahl. Ein Beispiel für eine Funktion mit zwei Zahlen ist

                                    s(x,y) = x+y

Diese liefert die Summe zweier beliebiger Zahlen x und y, also s(1,2) = 3 oder s(3,3) = 6. Eine Funktion kann eine Rekursion sein, d.h. in ihrer Definition auf sich selbst verweisen. Das tut etwa die sogenannte Fakultät-Funktion:

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

Diese Funktion benötigt also schon zwei Zeilen für ihre Definition. Und um diese Funktion für einen Zahlenwert zu berechnen, muss man zuerst die Funktionswerte für alle niedrigeren Zahlenwerte ausrechnen. Einsetzen von Zahlen ergibt:

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
.

Wie man sieht, liefert die Fakultät-Funktion bereits für niedrige Zahlen schnell anwachsende Werte. Es gibt aber noch interessantere Funktionen. Eine berühmte rekursive Funktion etwa ist die Mandelbrot-Funktion, die unter Fraktal beschrieben ist.

Über alle Grenzen

Eine noch seltsamere rekursive Funktion ist die Ackermann-Funktion. Sie wurde 1926 von Wilhelm Ackermann gefunden und 1955 von der ungarischen Mathematikerin Rózsa Péter umformuliert und vereinfacht. Es ist eine Funktion mit über alle Grenzen wachsenden Werten. Sie ist in der Rózsa-Péter-Variante folgendermaßen definiert:

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

Diese Definition sieht sehr unschuldig aus, da die einzigen von ihr verwendeten Rechenoperationen das Addieren und Subtrahieren von 1 sind. Sie hat es aber in sich. Zwar ist die Ackermann-Funktion für alle Zahlenwerte mit endlich vielen Rechenschritten berechenbar. Es ist aber unmöglich, aus den eingesetzten Zahlenwerten die Anzahl der Rechenschritte vorherzusagen. Denn es genügt hier nicht, wie in der Fakultät-Funktion die Funktionswerte für niedrigere Zahlenwerte zu kennen. Sehen wir uns zum Beispiel die einzelnen Rechenschritte für die Berechnung von a(1,1) und a(2,2) an:

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

Das sind eine Menge Rechenschritte schon für die kleinen Zahlenwerte von 2 und 2, die den bescheidenen Funktionswert 7 ergeben. Immerhin beträgt a(3,2) schon 29. a(4,2) ist eine 19727-stellige Zahl, viel größer als die Zahl der Atome im sichtbaren Universum (s. www.kosara.net/thoughts/ackermann.html). Und a(5,2), obwohl immer noch eine endliche Zahl, hat bisher noch niemand explizit ausgerechnet. Es gibt Anlass zur Vermutung, dass es auch niemand jemals tun wird.

Bijektionen

Ein Sonderfall einer Funktion ist die Bijektion. Eine Bijektion ordnet einer Zahl genau eine eindeutige andere Zahl zu. Im Gegensatz zu einer Funktion kann es bei der Bijektion nicht passieren, dass zwei verschiedenen Zahlen die gleiche Zahl zugeordnet wird. Beispielsweise ist

                                    f(x) = x²

keine Bijektion, denn hier ist der Zahl 2 und auch der Zahl -2 die gleiche Zahl zugeordnet, nämlich 4. Hingegen ist die Funktion f(x) = 2x eine Bijektion.

Die Bijektion dient zur Definition unendlicher Mengen. Der Mathematiker Dedekind definierte eine Menge als unendlich genau dann, wenn es eine Bijektion auf eine ihrer echten Teilmengen gibt. Die Menge der Natürlichen Zahlen ist nach dieser Definition unendlich, da es mit der Funktion f(x) = 2x eine Bijektion auf eine ihrer Teilmengen gibt, nämlich auf die Menge der geraden Zahlen. Dedekind nutzte diese Definition, um zu beweisen, dass die Menge seiner ►Gedanken unendlich ist.


 

© Johann Christian Lotter   ■  Infinity  ■  Links  ■  Forum