TI: Cantorsche Tupelfunktion (Update 4)

Update 4: Rechenfehler bei Umkehrfunktion, statt \(1218\) ist \(1185\) richtig. Danke Marion.

Update 3: Tippfehler, statt \(q(500)\) muss das nun \(q(39)\) heißen. Danke Christian.

Update 2: meine Güte, wo war ich mit meinen Gedanken? Nach mehreren Hinweisen von Martin und David z. B. scheint die Tupelfunktion nicht ganz richtig definiert gewesen zu sein. Ich weiß ehrlich gesagt auch nicht mehr, wo ich sie her hatte. Nundenn, ist nun wieder aktuell, so definiert wie in der Wikipedia und im Skript und müsste korrekt sein.

Die Cantorsche Tupelfunktion ist eigentlich ein sehr nettes Werkzeug und relativ einfach zu verstehen. Daher wird dieser Beitrag wahrscheinlich eher kurz ausfallen. Martin hat mich auf die Idee gebracht und da mir die Definition der Funktion nicht mehr so geläufig war: warum also nicht? 😉

Die Paarungsfunktion \(\pi : \mathbb{N}^2 \rightarrow \mathbb{N}\) macht folgendes: es weist einem Tupel (z.B. (2,6)) einen eindeutigen Wert zu. Aus diesem Wert kann man das Tupel wieder zurückgewinnen. Sie ist somit umkehrbar, d.h. bijektiv und total. Eig. eine ziemlich coole Sache (ja, ich habe eine durchaus fragwürdige Definition von „cool“). Wozu brauche ist das überhaupt? Z.B. für folgendes:

Mächtigkeit von Mengen

Nehmen wir einfach mal zwei Mengen \(M_1\) und \(M_2\). Zwei Mengen sind gleichmächtig (d.h. es sie beinhalten die gleiche Anzahl an Elementen) wenn es eine bijektive Abbildung \(f : M_1 \rightarrow M_2\) gibt. Die Bijektivität der Abbildung ordnet jedem Wert aus der Definitionsmenge \(M_1\) genau einen Wert aus der Wertemenge \(M_2\) zu. Nicht mehr und nicht weniger. Gibt es diese Abbildung, so gilt jede unendliche Menge als abzählbar wenn die Mächtigkeit von M der Mächtigkeit von \(\mathbb{N}\) entspricht (\(\left|M\right| =\left|\mathbb{N}\right|\)).  Tut sie das nicht (\(\left|M\right| \neq\left|\mathbb{N}\right|\)), ist sie überabzählbar.

Z.B. sind die Mengen

\(M_1 = \{a,z,d\}\) und \(M_2 = \{5,1,9\}\) gleichmächtig (\(\left|M_1\right| = \left|M_2\right|\)).

Wir nummerieren die Elemente einer Menge durch die Elemente der anderen Menge. Wie, ist egal. Hauptsache es gibt eine Nummerierung. Ein schönes Beispiel ist die Nummerierung der ganzen Zahlen \(\mathbb{Z}\) (…,-2,-1,0,1,…) durch die natürlichen Zahlen \(\mathbb{N} (0,1,2,3,…)\) aus dem Buch von Dirk. W. Hoffmann. Intuitiv scheint die Menge der ganzen Zahlen größer, es sind schließlich auch negative Zahlen dabei. Ist sie aber nicht. Eine Nummerierung könnte z.B. wie folgt aussehen: \( f:\mathbb{Z} \rightarrow \mathbb{N}\) mit:

\(f(x) = \begin{cases} -2x, & \mbox{ falls } x<0\\ 2x+1, & \mbox{ falls } x\geq 0\end{cases}\)

\(f(-5) = 10\) und \(f(5) = 11\). Da es eine bijektive Abbildung ist, können wir daraus auch eine Umkehrfunktion \( f^{-1}:\mathbb{N} \rightarrow \mathbb{Z}\) basteln mit:

\(f^{-1}(x) = \begin{cases} -x/2, & \mbox{ wenn x gerade }\\ (x-1)/2, & \mbox{ wenn x ungerade}\end{cases}\)

\(f^{-1}(10) = -5\) und \(f^{-1}(11) = 5\).

Damit haben wir eine eindeutige Nummerierung und Umkehrabbildung gefunden.

Die Tupelfunktion

Aber wir sind nicht nur in der Lage einem Tupel (z.B. (2,3)) eine eindeutige Nummer zu vergeben. Wir können die Zahl sogar einem Tripel (z.B. (5,3,9)) und einem Quadrupel (z.B. (7,4,9,1) und … ach, Ihr wisst worauf ich hinaus will. Hierbei hilft uns die Cantorsche Paarungsfunktion. Sie ist definiert als:

\(\pi_\mathbb{N}(x,y) = \sum_{i=0}^{x+y} i+y={{1}\over{2}}(x+y)(x+y+1)+y\)

Um auch Tripel zu erfassen, ist die Funktion definiert als:

\(\pi_\mathbb{N}^3(x,y,z)=\pi_\mathbb{N}(\pi_\mathbb{N}(x,y),z)\)

Wir können den Gedanken weiterspinnen und landen so bei der allgemeinen Definition:

\(\pi^1_\mathbb{N}(x_1) := x_1\) \(\pi^{n+1}_\mathbb{N}(x_1,…,x_n,x_{n+1}) := \pi_\mathbb{N}(\pi^{n}_\mathbb{N}(x_1,…,x_n),x_{n+1})\)

Beispiel gefällig? Sicher doch!

Beispiel: \(\pi^{4}_\mathbb{N}(5,3,9,1)\)

Wir lösen zunächst auf und rechnen dann aus. Die exemplarische Nebenrechnungen für das erste Tupel ist unter dem Rechenweg damit es nicht zu unübersichtlich wird:

\(\begin{array} {lcl}\pi^{4}_\mathbb{N}(5,3,9,1)&=&\pi_\mathbb{N}(\pi^{3}_\mathbb{N}(5,3,9),1)\\{}&=&\pi_\mathbb{N}(\pi_\mathbb{N}(\pi_\mathbb{N}(5,3),9),1)\\{}&{}&\mbox{(nun }\pi_\mathbb{N}(5,3)\mbox{ ausrechnen: siehe Nebenrechnung)}\\{}&=&\pi_\mathbb{N}(\pi_\mathbb{N}(39,9),1)\\{}&{}&\mbox{(jetzt }\pi_\mathbb{N}(39,9) \mbox{ ausrechnen)}\\{}&=&\pi_\mathbb{N}(1185,1)\\{}&{}&\mbox{(als letztes noch }\pi_\mathbb{N}(1185,1)\mbox{)}\\{}&=&703892\end{array}\)

(Korrektur! Danke Marion)

* Nebenrechnung 1:

\(\begin{array} {lcl}\pi_\mathbb{N}(5,3) &=&{{1}\over{2}}(5+3)(5+3+1)+3\\&=&{{1}\over{2}}(25+15+5+15+9+3)+3\\&=&{{1}\over{2}}(72)+3\\&=&39\end{array}\)

Tada! Ist doch eig. ganz einfach. Es sei denn man macht es wie ich und verrechnet sich dauernd bis man die Formel in Wolfram alpha eingibt 😉

Update: Umkehrfunktion

Da wir in der theoretischen Informatik Teil B auch die Umkehrfunktion brauchen, schreibe ich diese der Vollständigkeit halber mal auf. Martin hat ja einen schönen Link gepostet. Nehmen wir an wir suchen also die Tupel zu \(z = 39\), d.h. \(\pi(39)\). Das sind zunächst die 4 Formeln, die wir dazu brauchen (frech geklaut aus der Wikipedia):

\(q(z) =\lfloor{\frac{\sqrt{8\cdot z+1}-1}{2}} \rfloor\) \(f(w) =\frac{w\cdot(w+1)}{2}\) \(\pi_2(z) = z – f(q(z))\) \(\pi_1(z) = q(z) – \pi_2(z)\)

Setzen wir unser \(z = 39\) einfach mal ein und rechnen das aus:

\(q(39) = \lfloor {\frac{\sqrt{8\cdot 39+1}-1}{2}} \rfloor = 8\)

\(f(8) = \frac{8\cdot (8+1)}{2} = 36\) \(\pi_2(39) = 39 – 36 = 3\) \(\pi_1(39) = 8 – 3 = 5\)

Und damit \(\pi(39) = <5,3>\). That’s it (Danke Martin!).