{"id":580,"date":"2012-10-25T17:12:27","date_gmt":"2012-10-25T15:12:27","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=580"},"modified":"2025-11-25T23:11:57","modified_gmt":"2025-11-25T22:11:57","slug":"ti-cantorsche-tupelfunktion","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=580","title":{"rendered":"TI: Cantorsche Tupelfunktion (Update 4)"},"content":{"rendered":"

Update 4<\/strong>: Rechenfehler bei Umkehrfunktion, statt \\(1218\\) ist \\(1185\\) richtig. Danke Marion.<\/p>\n

Update 3<\/strong>: Tippfehler, statt \\(q(500)\\) muss das nun \\(q(39)\\) hei\u00dfen. Danke Christian.<\/p>\n

Update 2<\/strong>: meine G\u00fcte, 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\u00df 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\u00fcsste korrekt sein.<\/p>\n

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\u00e4ufig war: warum also nicht? \ud83d\ude09<\/p>\n

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\u00fcckgewinnen. Sie ist somit umkehrbar, d.h. bijektiv und total. Eig. eine ziemlich coole Sache (ja, ich habe eine durchaus fragw\u00fcrdige Definition von „cool“). Wozu brauche ist das \u00fcberhaupt? Z.B. f\u00fcr folgendes:<\/p>\n

M\u00e4chtigkeit von Mengen<\/h2>\n

Nehmen wir einfach mal zwei Mengen \\(M_1\\) und \\(M_2\\). Zwei Mengen sind gleichm\u00e4chtig (d.h. es sie beinhalten die gleiche Anzahl an Elementen) wenn es eine bijektive<\/a> Abbildung \\(f : M_1 \\rightarrow M_2\\) gibt. Die Bijektivit\u00e4t 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\u00e4hlbar<\/em> wenn die M\u00e4chtigkeit von M der M\u00e4chtigkeit von \\(\\mathbb{N}\\) entspricht (\\(\\left|M\\right| =\\left|\\mathbb{N}\\right|\\)). \u00a0Tut sie das nicht (\\(\\left|M\\right| \\neq\\left|\\mathbb{N}\\right|\\)), ist sie \u00fcberabz\u00e4hlbar<\/em>.<\/p>\n

Z.B. sind die Mengen<\/p>\n

\\(M_1 = \\{a,z,d\\}\\) und \\(M_2 = \\{5,1,9\\}\\) gleichm\u00e4chtig (\\(\\left|M_1\\right| = \\left|M_2\\right|\\)).<\/p>\n

Wir nummerieren die Elemente einer Menge durch die Elemente der anderen Menge. Wie, ist egal. Hauptsache es gibt eine Nummerierung. Ein sch\u00f6nes Beispiel ist die Nummerierung der ganzen Zahlen \\(\\mathbb{Z}\\) (…,-2,-1,0,1,…) durch die nat\u00fcrlichen Zahlen \\(\\mathbb{N} (0,1,2,3,…)\\) aus dem Buch von Dirk. W. Hoffmann. Intuitiv scheint die Menge der ganzen Zahlen gr\u00f6\u00dfer, es sind schlie\u00dflich auch negative Zahlen dabei. Ist sie aber nicht. Eine Nummerierung k\u00f6nnte z.B. wie folgt aussehen: \\( f:\\mathbb{Z} \\rightarrow \\mathbb{N}\\) mit:<\/p>\n\\(f(x) = \\begin{cases} -2x, & \\mbox{ falls } x<0\\\\ 2x+1, & \\mbox{ falls } x\\geq 0\\end{cases}\\)\n

\\(f(-5) = 10\\) und \\(f(5) = 11\\). Da es eine bijektive Abbildung ist, k\u00f6nnen wir daraus auch eine Umkehrfunktion\u00a0\\( f^{-1}:\\mathbb{N} \\rightarrow \\mathbb{Z}\\) basteln mit:<\/p>\n\\(f^{-1}(x) = \\begin{cases} -x\/2, & \\mbox{ wenn x gerade }\\\\ (x-1)\/2, & \\mbox{ wenn x ungerade}\\end{cases}\\)\n

\\(f^{-1}(10) = -5\\) und\u00a0\\(f^{-1}(11) = 5\\).<\/p>\n

Damit haben wir eine eindeutige Nummerierung und Umkehrabbildung gefunden.<\/p>\n

Die Tupelfunktion<\/h2>\n

Aber wir sind nicht nur in der Lage einem Tupel (z.B. (2,3)) eine eindeutige Nummer zu vergeben. Wir k\u00f6nnen 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:<\/p>\n\\(\\pi_\\mathbb{N}(x,y) = \\sum_{i=0}^{x+y} i+y={{1}\\over{2}}(x+y)(x+y+1)+y\\)\n

Um auch Tripel zu erfassen, ist die Funktion definiert als:<\/p>\n\\(\\pi_\\mathbb{N}^3(x,y,z)=\\pi_\\mathbb{N}(\\pi_\\mathbb{N}(x,y),z)\\)\n

Wir k\u00f6nnen den Gedanken weiterspinnen und landen so bei der allgemeinen Definition:<\/p>\n\\(\\pi^1_\\mathbb{N}(x_1) := x_1\\)\n\\(\\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})\\)\n

Beispiel gef\u00e4llig? Sicher doch!<\/p>\n

Beispiel<\/strong>: \\(\\pi^{4}_\\mathbb{N}(5,3,9,1)\\)<\/p>\n

Wir l\u00f6sen zun\u00e4chst auf und rechnen dann aus. Die exemplarische Nebenrechnungen f\u00fcr das erste Tupel ist unter dem Rechenweg damit es nicht zu un\u00fcbersichtlich wird:<\/p>\n\\(\\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}\\)\n

(Korrektur! Danke Marion)<\/p>\n

* Nebenrechnung 1:<\/p>\n\\(\\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}\\)\n

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 \ud83d\ude09<\/p>\n

Update: Umkehrfunktion<\/h2>\n

Da wir in der theoretischen Informatik Teil B auch die Umkehrfunktion brauchen, schreibe ich diese der Vollst\u00e4ndigkeit halber mal auf. Martin hat ja einen sch\u00f6nen Link gepostet<\/a>. Nehmen wir an wir suchen also die Tupel zu \\(z = 39\\), d.h. \\(\\pi(39)\\). Das sind zun\u00e4chst die 4 Formeln, die wir dazu brauchen (frech geklaut aus der Wikipedia):<\/p>\n

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

Setzen wir unser \\(z = 39\\) einfach mal ein und rechnen das aus:<\/p>\n

\\(q(39) = \\lfloor {\\frac{\\sqrt{8\\cdot 39+1}-1}{2}} \\rfloor = 8\\)<\/p>\n\\(f(8) = \\frac{8\\cdot (8+1)}{2} = 36\\)\n\\(\\pi_2(39) = 39 – 36 = 3\\)\n\\(\\pi_1(39) = 8 – 3 = 5\\)\n

Und damit \\(\\pi(39) = <5,3>\\). That’s it (Danke Martin!).<\/p>\n","protected":false},"excerpt":{"rendered":"

Update 4: Rechenfehler bei Umkehrfunktion, statt ist richtig. Danke Marion. Update 3: Tippfehler, statt muss das nun hei\u00dfen. Danke Christian. Update 2: meine G\u00fcte, 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\u00df ehrlich gesagt auch nicht … <\/p>\n

\u201eTI: Cantorsche Tupelfunktion (Update 4)\u201c <\/span>weiterlesen<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,4],"tags":[],"class_list":["post-580","post","type-post","status-publish","format-standard","hentry","category-fernuni","category-theoretische-informatik"],"_links":{"self":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/580","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=580"}],"version-history":[{"count":54,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/580\/revisions"}],"predecessor-version":[{"id":3540,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/580\/revisions\/3540"}],"wp:attachment":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=580"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=580"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=580"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}