Gleiche Mächtigkeit N & NxNxN < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Man konstruiere bijektive Punktabbildungen zwischen den Mengen [mm] \IN [/mm] und [mm] $\IN\times \IN$ [/mm] sowie [mm] \IN [/mm] und [mm] $\IN \times \IN \times \IN$. [/mm] Hinweis: Man betrachte die Paare [mm] (n,m)\in\IN\times\IN [/mm] bzw. Tripel [mm] (n,m,p)\in\IN\times\IN\times\IN [/mm] als Koordinaten von Punkten eines Gitters mit Maschenweite 1 in der Ebene bzw. im Raum und nummeriere diese auf geeignete Weise durch. |
Hallo!
Ich habe zwei Fragen zu der Aufgabe und meinen Lösungsideen. Bei der Abbildung zwischen [mm] \IN [/mm] und [mm] \IN\times\IN [/mm] kann man ja so nummerieren:
(1,1) (1,2) (1,3) (1,4) (1,5) ...
1 3 6 10 15
(2,1) (2,2) (2,3) (2,4) ...
2 5 9 14
(3,1) (3,2) (3,3) ...
4 8 13
(4,1) (4,2) ...
7 12
(5,1) ...
11
Dass praktisch [mm] 1\to(1,1), 2\to(2,1), 3\to(1,2), 4\to(3,1), 5\to(2,2), 6\to [/mm] (1,3), usw., d.h. immer von links unten nach rechts oben diagonal durchzählen, begonnen bei (1,1) und dann immer eine Zeile nach unten.
Würde es reichen, diese Idee so zu der Aufgabe zu schreiben?
Ich habe versucht, eine Art explizite Abbildung aus meiner Idee zu machen, aber ich verzweifle da gerade etwas. Basis meiner Zuordnung ist die Tatsache, dass die Paare aus der ersten Zeile den natürlichen Zahlen [mm] $\sum_{k=1}^{n}k [/mm] = [mm] \frac{n*(n+1)}{2}$ [/mm] zugeordnet werden:
[mm] $f:\IN\times\IN:(k,n)\mapsto \frac{n*(n+1)}{2} [/mm] + (k -1)$
Hier muss aber $k [mm] \in \{1,...n+1\}$ [/mm] sein. Gibt es eine bessere Möglichkeit, weil ich würde gern dann mit [mm] \IN\times\IN\times\IN [/mm] etwas ähnliches probieren.
Grüße,
Stefan
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:18 Di 20.10.2009 | | Autor: | felixf |
Hallo Stefan!
> Man konstruiere bijektive Punktabbildungen zwischen den
> Mengen [mm]\IN[/mm] und [mm]\IN\times \IN[/mm] sowie [mm]\IN[/mm] und [mm]\IN \times \IN \times \IN[/mm].
> Hinweis: Man betrachte die Paare [mm](n,m)\in\IN\times\IN[/mm] bzw.
> Tripel [mm](n,m,p)\in\IN\times\IN\times\IN[/mm] als Koordinaten von
> Punkten eines Gitters mit Maschenweite 1 in der Ebene bzw.
> im Raum und nummeriere diese auf geeignete Weise durch.
>
> Ich habe zwei Fragen zu der Aufgabe und meinen
> Lösungsideen. Bei der Abbildung zwischen [mm]\IN[/mm] und
> [mm]\IN\times\IN[/mm] kann man ja so nummerieren:
>
> (1,1) (1,2) (1,3) (1,4) (1,5) ...
> 1 3 6 10 15
> (2,1) (2,2) (2,3) (2,4) ...
> 2 5 9 14
> (3,1) (3,2) (3,3) ...
> 4 8 13
> (4,1) (4,2) ...
> 7 12
> (5,1) ...
> 11
>
> Dass praktisch [mm]1\to(1,1), 2\to(2,1), 3\to(1,2), 4\to(3,1), 5\to(2,2), 6\to[/mm]
> (1,3), usw., d.h. immer von links unten nach rechts oben
> diagonal durchzählen, begonnen bei (1,1) und dann immer
> eine Zeile nach unten.
>
> Würde es reichen, diese Idee so zu der Aufgabe zu
> schreiben?
>
> Ich habe versucht, eine Art explizite Abbildung aus meiner
> Idee zu machen, aber ich verzweifle da gerade etwas. Basis
> meiner Zuordnung ist die Tatsache, dass die Paare aus der
> ersten Zeile den natürlichen Zahlen [mm]\sum_{k=1}^{n}k = \frac{n*(n+1)}{2}[/mm]
> zugeordnet werden:
>
> [mm]f:\IN\times\IN:(k,n)\mapsto \frac{n*(n+1)}{2} + (k -1)[/mm]
>
> Hier muss aber [mm]k \in \{1,...n+1\}[/mm] sein.
Das funktioniert allerdings nicht.
> Gibt es eine
> bessere Möglichkeit, weil ich würde gern dann mit
> [mm]\IN\times\IN\times\IN[/mm] etwas ähnliches probieren.
Bei [mm] $\IN \times \IN \times \IN$ [/mm] nimmst du eine Bijektion [mm] $\varphi [/mm] : [mm] \IN \times \IN \to \IN$ [/mm] und betrachtest [mm] $\psi [/mm] : [mm] \varphi \circ (\varphi \times id_\IN)$.
[/mm]
Nun zu [mm] $\IN \times \IN$. [/mm] Die Eintraege in der linken Spalte sind ja $1 + [mm] \frac{k (k + 1)}{2}$.
[/mm]
Wenn du jetzt einen beliebigen Eintrag gegeben hast, sagen wir $(k, n)$, dann haengt der Wert von er Diagonalen ab auf der sich $(k, n)$ befindet. Der Eintrag auf der Diagonalen am weitesten links ist $(k + n - 1, 1)$, womit dieser den Wert $1 + [mm] \frac{(k + n - 1) (k + n)}{2}$ [/mm] hat. Jetzt muss man noch dazuaddieren wieweit man zur ersten Spalte gehen muss, naemlich $n - 1$ Schritte. Also erhaelst du $1 + [mm] \frac{(k + n - 1) (k + n)}{2} [/mm] + (n - 1) = n + [mm] \frac{(k + n - 1) (k + n)}{2}$. [/mm] Eventuell kann man das jetzt noch ausmultiplizieren und vereinfachen, eventuell auch nicht.
LG Felix
|
|
|
| |
|
Hallo Felix,
danke für deine Erleuchtung  Das habe ich verstanden.
Du hast allerdings bei k = 0 angefangen, obwohl es ja bei mir erst bei k = 1 beginnt, die Formel verändert sich dann zu: (k,n) hat die Nummer
[mm] $\frac{(k+n-1)*(k+n-2)}{2}+n$
[/mm]
(Es geht nicht wirklich zu vereinfachen). Muss ich nun noch nachweisen, dass diese Abbildung bijektiv ist, oder ist das aufgrund der Konstruktion klar? (Es steht ja in der Aufgabenstellung "Man konstruiere...". Abgesehen davon, hätte ich ziemliche Probleme damit, das zu beweisen, habe ich gemerkt. Es handelt sich ja jetzt um die Abbildung
[mm] $f:\IN\times\IN\to\IN:(k,n)\mapsto\left(\frac{(k+n-1)*(k+n-2)}{2}+n\right)$.
[/mm]
Surjektiv: Jeder Wert von [mm] \IN [/mm] wird erreicht: Ich müsste ja [mm] z\in\IN [/mm] wählen und nun geeignete k,n finden sodass [mm] $\left(\frac{(k+n-1)*(k+n-2)}{2}+n\right) [/mm] = z$ gilt. Aber das geht ja dann nur mit ein wenig Zahlentheorie, oder?
> Bei [mm]\IN \times \IN \times \IN[/mm] nimmst du eine Bijektion
> [mm]\varphi : \IN \times \IN \to \IN[/mm] und betrachtest [mm]\psi : \varphi \circ (\varphi \times id_\IN)[/mm].
Das verstehe ich ehrlich gesagt (noch) nicht. Was ist [mm] $\varphi \times id_{\N}$ [/mm] ? Was ist verstehe, ist, dass wir die Bijektion von oben benutzen wollen, damit wir weniger Arbeit haben.
Mein Knoten im Gehirn: [mm] \varphi [/mm] (also oben f) akzeptiert doch als "Eingabewert" nur [mm] \IN\times\IN. [/mm] Bei dir sieht es aber so aus, als könnte [mm] \varphi [/mm] nun plötzlich für eines dieser [mm] \IN [/mm] wieder [mm] \IN\times\IN [/mm] nehme ... (?)
Danke für Eure Hilfe,
Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:37 Di 20.10.2009 | | Autor: | felixf |
Hallo Stefan!
> danke für deine Erleuchtung Das habe ich verstanden.
> Du hast allerdings bei k = 0 angefangen, obwohl es ja bei
> mir erst bei k = 1 beginnt, die Formel verändert sich dann
> zu: (k,n) hat die Nummer
>
> [mm]\frac{(k+n-1)*(k+n-2)}{2}+n[/mm]
Ja, da hab ich mich vertan. So stimmt es jetzt aber wohl.
> (Es geht nicht wirklich zu vereinfachen). Muss ich nun noch
> nachweisen, dass diese Abbildung bijektiv ist, oder ist das
> aufgrund der Konstruktion klar? (Es steht ja in der
> Aufgabenstellung "Man konstruiere...". Abgesehen davon,
> hätte ich ziemliche Probleme damit, das zu beweisen, habe
> ich gemerkt. Es handelt sich ja jetzt um die Abbildung
>
> [mm]f:\IN\times\IN\to\IN:(k,n)\mapsto\left(\frac{(k+n-1)*(k+n-2)}{2}+n\right)[/mm].
>
> Surjektiv: Jeder Wert von [mm]\IN[/mm] wird erreicht: Ich müsste ja
> [mm]z\in\IN[/mm] wählen und nun geeignete k,n finden sodass
> [mm]\left(\frac{(k+n-1)*(k+n-2)}{2}+n\right) = z[/mm] gilt. Aber das
> geht ja dann nur mit ein wenig Zahlentheorie, oder?
Es geht: finde doch erstmal die Nummer der Diagonalen und den Abstand bzgl. der linken Spalte raus: waehle $k'$ maximal mit $1 + [mm] \frac{(k' - 1) k'}{2} \le [/mm] z$. Dann gilt fuer $n' = z - [mm] \frac{(k' - 1) k'}{2}$, [/mm] dass $n' [mm] \ge [/mm] 1$ ist. Man kann dann schnell $n' [mm] \le [/mm] k'$ zeigen. Jetzt musst du aus $(k', n')$ noch $(k, n)$ bekommen.
> > Bei [mm]\IN \times \IN \times \IN[/mm] nimmst du eine Bijektion
> > [mm]\varphi : \IN \times \IN \to \IN[/mm] und betrachtest [mm]\psi : \varphi \circ (\varphi \times id_\IN)[/mm].
>
> Das verstehe ich ehrlich gesagt (noch) nicht. Was ist
> [mm]\varphi \times id_{\N}[/mm] ?
Das ist die Abbildung [mm] $(\IN \times \IN) \times \IN \to \IN \times \IN$, [/mm] $((a, b), c) [mm] \mapsto (\varphi(a, [/mm] b), [mm] id_\IN(c))$.
[/mm]
> Was ist verstehe, ist, dass wir
> die Bijektion von oben benutzen wollen, damit wir weniger
> Arbeit haben.
> Mein Knoten im Gehirn: [mm]\varphi[/mm] (also oben f) akzeptiert
> doch als "Eingabewert" nur [mm]\IN\times\IN.[/mm] Bei dir sieht es
> aber so aus, als könnte [mm]\varphi[/mm] nun plötzlich für eines
> dieser [mm]\IN[/mm] wieder [mm]\IN\times\IN[/mm] nehme ... (?)
Ist das mit dem oben jetzt klarer?
LG Felix
|
|
|
| |
|
Hallo Felix,
zunächst danke für deine Antwort
> Es geht: finde doch erstmal die Nummer der Diagonalen und
> den Abstand bzgl. der linken Spalte raus: waehle [mm]k'[/mm] maximal
> mit [mm]1 + \frac{(k' - 1) k'}{2} \le z[/mm]. Dann gilt fuer [mm]n' = z - \frac{(k' - 1) k'}{2}[/mm],
> dass [mm]n' \ge 1[/mm] ist. Man kann dann schnell [mm]n' \le k'[/mm] zeigen.
Es ist für mich zwar logisch, dass $n' [mm] \le [/mm] k'$ sein muss, aber irgendwie kann ich es mit den gegebenen Ungleichungen nicht zeigen:
$n' = z - [mm] \frac{(k' - 1) k'}{2} [/mm] $
Ich nehme an, dass ich irgendwie benutzen muss, was der höchste Wert von z ist, also einfach mal den nachfolgenden nehmen und - 1 rechnen?
Dann wäre im schlimmsten Fall $z = [mm] \frac{k'*(k'+1)}{2}$, [/mm] d.h. es ist [mm] $z\le \frac{k'*(k'+1)}{2}$. [/mm] Nun muss ich das wahrscheinlich oben einsetzen:
$n' = z - [mm] \frac{(k' - 1) k'}{2} \le \frac{k'*(k'+1)}{2} [/mm] - [mm] \frac{(k' - 1) k'}{2} [/mm] = k' $
Ist das so okay? Wozu brauche ich das eigentlich?
> Jetzt musst du aus [mm](k', n')[/mm] noch [mm](k, n)[/mm] bekommen.
Mmh... Wir haben doch jetzt schon genau ein Paar (k', n') definiert, das entsprechend der Abbildung z erzeugen müsste. Was meinst du mit (k,n) bekommen? Mir ist allerdings bewusst, dass ich bisher noch nicht wirklich verifiziert habe, dass (k',n') die gewünschte Eigenschaft hat.
Tut mir leid, komm' mir grad ziemlich doof vor... :-(
> > > Bei [mm]\IN \times \IN \times \IN[/mm] nimmst du eine Bijektion
> > > [mm]\varphi : \IN \times \IN \to \IN[/mm] und betrachtest [mm]\psi : \varphi \circ (\varphi \times id_\IN)[/mm].
> Das ist die Abbildung [mm](\IN \times \IN) \times \IN \to \IN \times \IN[/mm],
> [mm]((a, b), c) \mapsto (\varphi(a, b), id_\IN(c))[/mm].
Okay, jetzt hab ich's verstanden.
Bin ich mit der Definition dieser Abbildung schon fertig, wenn ich weiß, dass die Komposition von bijektiven Abbildungen wieder bijektiv ist und ich obige Abbildung als [mm] \varphi [/mm] nehme?
Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:32 Di 20.10.2009 | | Autor: | felixf |
Hallo Stefan!
> zunächst danke für deine Antwort
>
> > Es geht: finde doch erstmal die Nummer der Diagonalen und
> > den Abstand bzgl. der linken Spalte raus: waehle [mm]k'[/mm] maximal
> > mit [mm]1 + \frac{(k' - 1) k'}{2} \le z[/mm]. Dann gilt fuer [mm]n' = z - \frac{(k' - 1) k'}{2}[/mm],
> > dass [mm]n' \ge 1[/mm] ist. Man kann dann schnell [mm]n' \le k'[/mm] zeigen.
>
> Es ist für mich zwar logisch, dass [mm]n' \le k'[/mm] sein muss,
> aber irgendwie kann ich es mit den gegebenen Ungleichungen
> nicht zeigen:
>
> [mm]n' = z - \frac{(k' - 1) k'}{2}[/mm]
>
> Ich nehme an, dass ich irgendwie benutzen muss, was der
> höchste Wert von z ist, also einfach mal den nachfolgenden
> nehmen und - 1 rechnen?
>
> Dann wäre im schlimmsten Fall [mm]z = \frac{k'*(k'+1)}{2}[/mm],
> d.h. es ist [mm]z\le \frac{k'*(k'+1)}{2}[/mm]. Nun muss ich das
> wahrscheinlich oben einsetzen:
>
> [mm]n' = z - \frac{(k' - 1) k'}{2} \le \frac{k'*(k'+1)}{2} - \frac{(k' - 1) k'}{2} = k'[/mm]
>
> Ist das so okay?
Ja.
> Wozu brauche ich das eigentlich?
Nun: das zeigt dir, dass du aus $z$ eindeutig $(k', n')$ bekommen kannst: aus diesen wiederum kannst du $(k, n)$ rekonstruieren, die unter deiner Konstruktion auf $z$ abgebildet werden -- und damit hast du ein Urbild.
> > Jetzt musst du aus [mm](k', n')[/mm] noch [mm](k, n)[/mm] bekommen.
>
> Mmh... Wir haben doch jetzt schon genau ein Paar (k', n')
> definiert, das entsprechend der Abbildung z erzeugen
> müsste. Was meinst du mit (k,n) bekommen? Mir ist
> allerdings bewusst, dass ich bisher noch nicht wirklich
> verifiziert habe, dass (k',n') die gewünschte Eigenschaft
> hat.
Unser Paar $(k', n')$ gibt die Diagonale und den Abstand auf der Diagonalen vom linken Rand an -- und nicht einen Index $(k, n)$ mit Zeilen- und Spaltennummer. Es gilt $k - n + 1 = k'$ und $n = n' + 1$.
> > > > Bei [mm]\IN \times \IN \times \IN[/mm] nimmst du eine Bijektion
> > > > [mm]\varphi : \IN \times \IN \to \IN[/mm] und betrachtest [mm]\psi : \varphi \circ (\varphi \times id_\IN)[/mm].
>
> > Das ist die Abbildung [mm](\IN \times \IN) \times \IN \to \IN \times \IN[/mm],
> > [mm]((a, b), c) \mapsto (\varphi(a, b), id_\IN(c))[/mm].
>
> Okay, jetzt hab ich's verstanden.
Gut :)
> Bin ich mit der Definition dieser Abbildung schon fertig,
> wenn ich weiß, dass die Komposition von bijektiven
> Abbildungen wieder bijektiv ist und ich obige Abbildung als
> [mm]\varphi[/mm] nehme?
Ja.
LG Felix
|
|
|
| |
|
Hallo Felix!
Danke für deine Antwort, hat mir wieder einige Taschenlampen in den Tunnel geworfen!
Das mit dem Beweis von n' [mm] \le [/mm] k' ist also gewissermaßen nur eine Bestätigung der Anschauung, weil ja klar ist, dass der Abstand vom "Beginn" der Diagonalen bis zum Ende nicht größer als k' sein kann.
> Unser Paar [mm](k', n')[/mm] gibt die Diagonale und den Abstand auf
> der Diagonalen vom linken Rand an -- und nicht einen Index
> [mm](k, n)[/mm] mit Zeilen- und Spaltennummer. Es gilt [mm]k - n + 1 = k'[/mm]
> und [mm]n = n' + 1[/mm].
Müsste nicht eher $k + n - 1 = k'$ sein?
Dann wäre $n = n'+1$ und $k = k'-n+1 = k'-(n'+1)+1 = k'-n'$.
(?)
Um nochmal zu der Variante mit dem [mm] \IN\times\IN\times\IN [/mm] zurückzukommen...
Auch wenn es eigentlich klar ist, haben wir in der Vorlesung nie bewiesen, dass die Komposition von Bijektionen eine Bijektion ist.
Deswegen wäre für mich nun noch die Frage, wie ich die Punktmenge im Raum geeignet (anschaulich) abzähle.
Dazu habe ich versucht, mir deine Abbildung [mm] $\varphi\circ(\varphi\times id_{\IN})$ [/mm] anschaulich vorzustellen...
Das ist ja so ähnlich, wie als wenn ich einen Punkt (k,m,n) erstmal auf eine Ebene runterprojiziere, wieder mit dem Diagonalverfahren, und dann von dort aus auf eine Achse.
Aber mein Vorstellungsvermögen versagt, sich jetzt die Nummerierungen dazuzudenken, wo die genau sind.
Sollte ich überhaupt darüber nachdenken, nach der Aufgabenstellung ja schon, oder?
Grüße,
Stefan
|
|
|
| |
|
> Um nochmal zu der Variante mit dem [mm]\IN\times\IN\times\IN[/mm]
> zurückzukommen...
> Auch wenn es eigentlich klar ist, haben wir in der
> Vorlesung nie bewiesen, dass die Komposition von
> Bijektionen eine Bijektion ist.
Dann beweise es mal kurz für dein eigenes Seelenheil !
> Deswegen wäre für mich nun noch die Frage, wie ich die
> Punktmenge im Raum geeignet (anschaulich) abzähle.
> Dazu habe ich versucht, mir deine Abbildung
> [mm]\varphi\circ(\varphi\times id_{\IN})[/mm] anschaulich
> vorzustellen...
>
> Das ist ja so ähnlich, wie als wenn ich einen Punkt
> (k,m,n) erstmal auf eine Ebene runterprojiziere, wieder mit
> dem Diagonalverfahren, und dann von dort aus auf eine
> Achse.
> Aber mein Vorstellungsvermögen versagt, sich jetzt die
> Nummerierungen dazuzudenken, wo die genau sind.
>
> Sollte ich überhaupt darüber nachdenken, nach der
> Aufgabenstellung ja schon, oder?
Eine solche "anschauliche" Vorstellung von der
Bijektion von [mm] \IN^3 [/mm] auf [mm] \IN [/mm] wird eben eigentlich über-
flüssig, wenn man sich (und den Kommunikations-
partner, also z.B. den Vorlesungsassistenten) von
der Bijektivität der Abbildungen [mm] g:\IN^3\to\IN^2 [/mm] und
[mm] f:\IN^2\to\IN [/mm] überzeugen kann, welche dann zur Bijektion
[mm] B=f\circ{g}:\IN^3\to\IN [/mm] zusammengesetzt werden.
LG Al-Chw.
|
|
|
| |
|
Hallo Stefan,
ich komme auf eine etwas andere Formel als Felix,
nämlich:
[mm] f(k,n)=n+\frac{(n+k-1)*(n+k-2)}{2}
[/mm]
Dies stimmt mit deiner Nummerierung (aber auch
nicht mit deiner Formel) überein.
LG Al-Chw.
|
|
|
| |
|
Danke, Al-Chwarizmi, hab ich auch festgestellt
Grüße,
Stefan
|
|
|
|
