Bijektive Abbildungen auf \IN < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Zeige: Es existiert eine bijektive Abbildung von [mm] \IN [/mm] auf [mm] \IN\times\IN. [/mm] |
Hallo liebes Forum,
Die o.g. Aufgabe bringt mich mittlerweile zum verzweifeln. Ich suche eine bijektive Abbildung
[mm] \phi: \IN\times\IN \rightarrow \IN
[/mm]
deren Umkehrfunktion zugleich o.g. Aussage beweisen soll (denn offenbar ist dann [mm] \phi^{-1} [/mm] eine Bijektion von [mm] \IN [/mm] auf [mm] \IN\times\IN).
[/mm]
Meine Idee ist, zunächst eine injektive Funktion
[mm] \psi:\IN\times\IN \rightarrow \IN
[/mm]
zu definieren, die jedem Tupel (m, n) genau einen Funktionswert aus [mm] \IN [/mm] zuordnet. Ich definiere dann für jedes (m,n) [mm] \in \IN\times\IN:
[/mm]
[mm] (m,n)\phi [/mm] = [mm] |\IN \cap \{ 1, 2, \ldots, (m,n)\psi \}|
[/mm]
Diese Abbildung wäre dann offensichtlich injektiv und surjektiv auf [mm] \IN [/mm] (was im Detail noch zu zeigen wäre).
Mein Problem ist, daß mir keine Funktion [mm] \psi [/mm] wie oben einfällt. Mein erster Gedanke war, [mm] (m,n)\phi [/mm] = [mm] m^n [/mm] zu definieren, aber das klappt nicht (bspw. wäre [mm] \psi(4,2) [/mm] = 16 = [mm] \psi(2,4) [/mm] ).
Findet jemand eine Funktion [mm] \psi [/mm] für mich, oder kann mir jemand einen Tipp geben?
Im voraus bereits vielen lieben Dank für eine Hilfe!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:25 Mi 11.04.2007 | | Autor: | comix |
Ich habe Deine Funktion [mm] \Phi [/mm] und [mm] \Psi [/mm] noch nicht verstanden. Mein Tipp:
Notiere die Elemente von [mm] \IN [/mm] x [mm] \IN [/mm] in einer nach (z.B.) rechts und unten offenen Tabelle und zähle sie mit dem Diagonalisierungsverfahren ab:
(1,1) (1,2) (1,3) (1,4) ...
(2,1) (2,2) (2,3) (2,4) ...
(3,1) (3,2) (3,3) ...
(4,1) (4,2) ...
(5,1) ...
...
Nun erhält jedes Feld eine forlaufende Nummer:
1 2 4 7 11 ...
3 5 8 ...
6 9 ...
10 ...
...
Intuitiv ist die Sache damit eigentlich klar. Für einen Beweis hilft Dir vielleicht:
Sei <i,j> der Wert in der i-ten Zeile und j-ten Spalte. Dann gilt:
<1,j> = 1 + [mm] \summe_{k=1}^{j-1} [/mm] k
<2,j> = <1,j+1> + 1
Vielleicht hilft Dir das weiter?
|
|
|
| |
|
Hallo,
- Ja, das hilft mir weiter!
Das Diagonalisierungsverfahren erinnert mich an einen Beweis, in dem gezeigt wurde, daß [mm] \IQ [/mm] abzählbar ist.
Supi, danke!! 
|
|
|
|
