Bijektion zw. Mengen < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:32 Mo 20.10.2014 | | Autor: | baxbear |
| Aufgabe | | Zeigen Sie, dass N und [mm] Z^2:=ZxZ [/mm] gleichmächtig sind. |
Hallo,
ich habe nun 6h Stunden lang in der Gruppe alleine und mit Hilfe dieses Forums:
http://www.onlinemathe.de/forum/Beweis-der-Abzaehlbarkeit-einer-unendlichen-Menge
diese Aufgabe zu lösen. Ich habe bijektive Funktionen zwischen Z und N und [mm] Z^2 [/mm] und [mm] N^2 [/mm] gefunden. Nur für [mm] N^2 [/mm] auf N, Q auf N und [mm] Z^2 [/mm] auf N kann ich keine finden. Ich habe mir das Zeugs ähnlich dem Verfahren von Cantor aufgemalt, weiß aber nicht wie ich weiter vorgehen soll... (grafische Lösungen sind nicht erwünscht).
Ich weiß nicht mehr weiter. Kann mir bitte irgendwer erklären wie ich bei einer solchen Aufgabe eine Lösung finden kann. Also eine Art Kochanleitung. Es kann doch nicht sein, dass ich die richtige Funktion raten muss.
|
|
| |
|
Es genügt, eine Injektion [mm] $\IN^2\longrightarrow\IN [/mm] $ anzugeben. Tipp: eine Primzahlpozenz ist durch Basis und Exponent eindeutig bestimmt.
Liebe Grüße,
UniversellesObjekt
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:45 Mo 20.10.2014 | | Autor: | baxbear |
Hmm k,
also dann hätte ich z.B. [mm] f(x,y)=3^x*5^y [/mm] als injektion - was mache ich dann mit Paaren aus [mm] Z^2?
[/mm]
Fallunterscheidung:
[mm] x,y\in\mathbb{Z}
[/mm]
f(x,y)=
1 x,y >= 0; [mm] 3^{2x}*5^{2y}
[/mm]
2 x >= 0, y < 0; [mm] 3^{2x}*5^{-2y-1}
[/mm]
3 x < 0, y >= 0; [mm] 3^{-2x-1}*5^{2y}
[/mm]
4 x < 0, y < 0; [mm] 3^{-2x-1}*5^{-2y-1}
[/mm]
und wie zeige ich über die Injektivität das die Mengen gleichmächtig sind?
|
|
|
| |
|
Hallo,
Du meintest doch, du hättest schon eine Bijektion [mm] $\IZ^2\longrightarrow\IN^2$. [/mm] Die Komposition [mm] $\IZ^2\longrightarrow\IN^2\longrightarrow\IN [/mm] $ wird dann das Geforderte leisten.
Liebe Grüße,
UniversellesObjekt
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:50 Mo 20.10.2014 | | Autor: | baxbear |
warum meinst du eigentlich das es reicht eine injektive Abbildung zu finden? Ich verstehe nicht richtig wie das gemeint ist?
|
|
|
| |
|
Hallo,
Wenn du eine Injektion [mm] $g\colon\IN^2\longrightarrow\IN [/mm] $ hast, ist diese bijektiv auf ihr Bild. Das Bild ist aber eine unendliche Teilmenge $ M $ von [mm] $\IN$ [/mm] und auf diese können wir rekursiv eine Bijektion [mm] $f\colon\IN\longrightarrow [/mm] M $ definieren durch $ f [mm] (0)=\min [/mm] M $, $ f [mm] (n+1)=\min\{m\in M| m\not=f (0), f (1),..., f (n)\} [/mm] $.
Dann ist [mm] $\IN^2\xrightarrow [/mm] {\ \ g\ \ } [mm] M\xrightarrow{\ \ f^{-1}\ \ }\IN [/mm] $ eine Bijektion.
Liebe Grüße,
UniversellesObjekt
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:30 Mo 20.10.2014 | | Autor: | baxbear |
Wow, genial - vielen Dank - bin gerade neidisch, dass ich da nicht drauf gekommen bin^^ aber auf jeden Fall vielen Dank!
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:54 Mo 20.10.2014 | | Autor: | Ladon |
Hallo baxbear,
sicherlich kennst du die Abzählung der rationalen Zahlen [mm] \IQ [/mm] nach Cantor. In ähnlicher Weise kannst du dir gewiss eine Abzählung von [mm] \IZ\times\IZ [/mm] überlegen, wobei die nicht-teilerfremden Elemente nicht gestrichen werden dürfen. Hast du eine Abzählung gefunden gibt dir das eine bijektive Abbildung [mm] \IN\to\IZ\times\IZ.
[/mm]
Der Gedanke kam mir, als ich mich an die ![[]](/images/popup.gif) Definition der rationalen Zahlen erinnerte.
MfG
Ladon
PS: Nur als Bemerkung am Rande:
Eine sehr elegante Abzählung der rationalen Zahlen haben übrigens Calcin und Wilf vorgelegt (vgl. Buch der Beweise, S. 123), was uns allerdings nicht weiterbringt.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 15:04 Mo 20.10.2014 | | Autor: | baxbear |
naja ich kann ja die Paare wie folgt darstellen:
(-2, 2)(-1, 2)( 0, 2)( 1, 2)( 2, 2)
(-2, 1)(-1, 1)( 0, 1)( 1, 1)( 2, 1)
(-2, 0)(-1, 0)( 0, 0)( 1, 0)( 2, 0)
(-2,-1)(-1,-1)( 0,-1)( 1,-1)( 2,-1)
(-2,-2)(-1,-2)( 0,-2)( 1,-2)( 2,-2)
dann könnte man z.B. die Tupel nach ihrem Betrag ordnen:
(0,0)
(1,0)(0,1)(-1,0)(0,-1)
(1,1)(2,0)(0,2)(-2,0)(0,-2)(-1,-1),(-1,1),(1,-1)
allerdings bin ich dann auch nicht weiter gekommen - wie mache ich daraus eine Formel/Funktion?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:23 Mo 20.10.2014 | | Autor: | Ladon |
Warum brauchst du eine konkrete Formel? Du kannst doch analog zu Cantors Diagonalargument eine Abzählung durchführen (siehe z.B. hier). Damit ist dann klar, dass [mm] \IZ\times\IZ [/mm] abzählbar ist und damit Gleichmächtig zu [mm] \IN. [/mm]
Zur Formel: Vielleicht hilft dir die Formel für eine Abzählung von [mm] \IN\times\IN [/mm] weiter:
[mm] f:\IN\times\IN\to\IN [/mm] mit [mm] (x,y)\mapsto x+\frac{(x+y-2)\cdot(x+y-1)}{2} [/mm] ist Bijektion. Und jetzt bilde mal die rekursive Abbildungsvorschrift der inversen Abb.:
[mm] f^{-1}(1)=(1,1) [/mm] und [mm] $f^{-1}(n)=(x,y) \Rightarrow f^{-1}(n+1)=\begin{cases}
(1,x+1) \mbox{ für }y=1 \\
(x+1,y-1) \mbox{ sonst }
\end{cases}$
[/mm]
MfG
Ladon
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:20 Mi 22.10.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:26 Mo 20.10.2014 | | Autor: | Marcel |
Hallo,
> Zeigen Sie, dass N und [mm]Z^2:=ZxZ[/mm] gleichmächtig sind.
> Hallo,
>
> ich habe nun 6h Stunden lang in der Gruppe alleine und mit
> Hilfe dieses Forums:
>
> http://www.onlinemathe.de/forum/Beweis-der-Abzaehlbarkeit-einer-unendlichen-Menge
> diese Aufgabe zu lösen. Ich habe bijektive Funktionen
> zwischen Z und N und [mm]Z^2[/mm] und [mm]N^2[/mm] gefunden. Nur für [mm]N^2[/mm] auf
> N, Q auf N und [mm]Z^2[/mm] auf N kann ich keine finden. Ich habe
> mir das Zeugs ähnlich dem Verfahren von Cantor aufgemalt,
> weiß aber nicht wie ich weiter vorgehen soll... (grafische
> Lösungen sind nicht erwünscht).
es reicht vollkommen, wenn Du Dir den [mm] $\IR^2$ [/mm] skizzierst und darin das [mm] $\IZ \times \IZ$-Gitter.
[/mm]
Jetzt folgende Idee:
Wir konstruieren eine Abbildung $f [mm] \colon \IN \to \IZ^2$ [/mm] wie folgt:
[mm] $f(1)=(0,0)\,,$
[/mm]
[mm] $f(2)=(1,0)\,,$
[/mm]
[mm] $f(3)=(1,1)\,,$
[/mm]
[mm] $f(4)=(0,1)\,,$
[/mm]
[mm] $f(5)=(-1,1)\,,$
[/mm]
[mm] $f(6)=(-1,0)\,,$
[/mm]
[mm] $f(7)=(-1,-1)\,,$
[/mm]
[mm] $f(8)=(0,-1)\,,$
[/mm]
[mm] $f(9)=(1,-1)\,.$
[/mm]
Das heißt, wir nehmen die Mengen
[mm] $M_0:=\{(a,b) \in \IZ^2\mid \|(a,b)\|_\infty=0\}\,,$
[/mm]
[mm] $M_1:=\{(a,b) \in \IZ^2 \mid \|(a,b)\|_\infty=1\}\,,$
[/mm]
[mm] $M_2:=\{(a,b) \in \IZ^2 \mid \|(a,b)\|_\infty=2\}\,,$
[/mm]
[mm] $M_3:=\{(a,b) \in \IZ^2 \mid \|(a,b)\|_\infty=3\}\,,$
[/mm]
.
.
.
und "nummerieren" deren Elemente durch - die Art der Nummerierung
verläuft hier so, dass wir "das rechteste Element der x-Achse" einer solchen Menge
hernehmen, und dann die Punkte [mm] $(a,b)\,$ [/mm] der zugehörigen Quadrats durchlaufen,
und zwar entgegen dem Uhrzeigersinn. (Quasi eine Art *Quadratische
Spirale 'mit Sprüngen' *.)
Wenn Du oben guckst:
[mm] $M_0$ [/mm] und [mm] $M_1$ [/mm] haben wir erfasst, wenn Du das Prinzip verstanden hast,
dann wirst Du sehen, dass es dann mit
$f(10)=(2,0) [mm] \in M_2$
[/mm]
weitergehen würde.
Ob man das jetzt in eine Formel verpacken kann, das ist eine andere
Frage. Aber man kann sicher durchaus einen Algorithmus hinschreiben,
der den "Weggang" beschreibt. Z.B.
"Start bei (0,1)."
Danach steht dann irgendwo im Code:
"Aktuelle Stelle sei [mm] $(x,y)\,.$ [/mm] Erhöhe [mm] $x\,$-Komponente [/mm] um [mm] $1\,,$ [/mm] falls $x< 1$ ist. Ist [mm] $x=1\,,$ [/mm] dann schaue auf die [mm] $y\,$-Komponente...."
[/mm]
Auch mit solchen "Rekursionsvorschriften" kann man die Bijektivität nachweisen.
Die Surjektivität wäre oben einfach, weil man für $(x,y) [mm] \in \IZ^2$ [/mm] ja sofort [mm] $\|(x,y)\|_\infty=\max\{|x|,\;|y|\}$
[/mm]
angeben kann und damit $(x,y) [mm] \in M_{\max\{|x|,|y|\}}$ [/mm] gilt.
Aber generell ist das vorgehen: Man fängt irgendwo in [mm] $\IZ \times \IZ$ [/mm] an, meistens
wohl in $(0,1),$ und überlegt sich dann, wie man *weiterlaufen kann, um alle
Punkte aus [mm] $\IZ \times \IZ$ [/mm] zu markieren* (das ist die Surjektivität), und
natürlich darf ein Punkt höchstens einmal markiert werden (das ist die Injektivität).
Ein weiteres Bsp., wo sowas schön angedeutet wurde:
Siehe
hier (klick!)
den Beitrag No. 4 von 1/4.
Gruß,
Marcel
|
|
|
|
