Gleichmächtigkeit NxN und N < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:23 So 29.11.2009 | | Autor: | valoo |
| Aufgabe | | Zeigen Sie: [mm] |\IN|=|\IN [/mm] x [mm] \IN| [/mm] |
Mir ist klar, dass man das mit Diagonalisierung machen kann. Auch gibt es ja die Cantor'sche Paarungsfunktion (wobei ich mich frage, ob die für [mm] \IN [/mm] mit oder ohne 0 gilt?).
Aber gibt es nicht eine andere Alternative? Zwei Mengen sind ja gleichmächtig, wenn es Surjektionen oder Injektionen in beide Richtungen gibt.
Eine Injektion kann man einfach von [mm] \IN [/mm] nach [mm] \IN [/mm] x [mm] \IN [/mm] konstruieren, aber eine Injektion in die andere Richtung zu konstruieren, ist nicht so leicht. Bei der Surjektion ist es umgekehrt.
Gibt es eine formale Möglichkeit, die Gleichmächtigkeit zu beweisen, ohne spezifische Abbildungen konstruieren zu müssen?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:53 So 29.11.2009 | | Autor: | pelzig |
Eine Injetkion von [mm] $\IN\times\IN\to\IN$: (m,n)\mapsto 2^m3^n. [/mm] Letztlich muss man die Existenz einer Bijektion zeigen, das ist nunmal die Definition von Gleichmächtigkeit. Der Satz von Cantor-Bernstein ist da schonmal ne Hilfe, wenn auch hochgradig nicht-konstruktiv... wie so ziemlich alles was mit wirklich großen Mengen zu tun hat.
Gruß, Robert
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:55 So 29.11.2009 | | Autor: | valoo |
Ich denke, ich mache das mit den zwei Injektionen.
Nur ich bin mir nicht sicher, wie ich die Injektivität beweisen soll.
Bei
[mm] f:\IN\to \IN [/mm] x [mm] \IN
[/mm]
[mm] n\mapsto(n,n)
[/mm]
ist das ja noch einfach (n,n)=(m,m) => n=m
Aber bei der anderen:
[mm] g:\IN [/mm] x [mm] \IN \to\IN
[/mm]
[mm] (m,n)\mapsto2^{m}*3^{n}
[/mm]
Finde ich das garnicht so leicht.
Z. z.: [mm] 2^{m}*3^{n}=2^{p}*3^{q} [/mm] =>(m,n)=(p,q)
Ich bin da mit Fallunterscheidung herangegangen:
Sei n=q:
Dann: [mm] 2^{m}=2^{p} [/mm] => m=p => (m,n)=(p,q)
Sein [mm] n\not=q [/mm] (O. B. d. A. n<q)
Dann: [mm] 2^{m}*3^{n}=2^{p}*3^{n+x} [/mm] mit [mm] x\in\IN, x\not=0
[/mm]
=> [mm] 2^{m}=2^{p}*3^{x}
[/mm]
=> Es existiert [mm] y\in\IN [/mm] mit [mm] 2^{y}=3^{x} [/mm] sodass [mm] 2^{m}=2^{p+y} [/mm] => m=p+y
w.w.: (2*a)*(2*b)=4*a*b gerade für alle [mm] a,b\in\IN
[/mm]
außerdem (2*a+1)*(2*b+1)=4*a*b+2*a+2*b+1 ungerade für alle [mm] a,b\in\IN
[/mm]
Also: Es existieren keine [mm] x,y\in\IN [/mm] mit [mm] 2^{y}=3^{x}
[/mm]
=> g ist injektiv
Ist so die Injektivität von g wirklich bewiesen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:02 So 29.11.2009 | | Autor: | Merle23 |
Hi,
benutze einfach die Eindeutigkeit der Primfaktorzerlegung.
LG, Alex
|
|
|
|
