Kardinalität N^N < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:17 Do 11.02.2010 | | Autor: | nooschi |
Hallo zusammen,
ich frage mich gerade, ob [mm] \IN^{\IN} [/mm] bzw. die Menge aller Funktionen die von [mm] \IN [/mm] nach [mm] \IN [/mm] gehen (:= [mm] ^{\IN}\IN), [/mm] dieselbe Kardinalität wie [mm] \IN [/mm] haben.
Ich versuche also eine Injektion [mm] ^{\IN}\IN\rightarrow\IN [/mm] zu basteln (weiss aber nicht obs überhaupt geht):
ich weiss, dass es eine Bijektion zwischen [mm] \IN^{2} [/mm] und [mm] \IN [/mm] gibt, also kann ich die Punkte in [mm] \IN^2 [/mm] sozusagen abzählen, d.h. ich kann jeder Funktion [mm] $f\in ^{\IN}\IN$ [/mm] eine unendliche Teilmenge von [mm] \IN [/mm] zuordnen. ich weiss aber nicht ob mich das weiterbringt.
Ich wäre um jede Antwort froh, auch nur schon über die Info, obs die Bijektion überhaupt gibt 
|
|
| |
|
| Status: |
(Antwort) fehlerhaft  | | Datum: | 20:22 Do 11.02.2010 | | Autor: | abakus |
> Hallo zusammen,
>
> ich frage mich gerade, ob [mm]\IN^{\IN}[/mm] bzw. die Menge aller
> Funktionen die von [mm]\IN[/mm] nach [mm]\IN[/mm] gehen (:= [mm]^{\IN}\IN),[/mm]
> dieselbe Kardinalität wie [mm]\IN[/mm] haben.
>
> Ich versuche also eine Injektion [mm]^{\IN}\IN\rightarrow\IN[/mm] zu
> basteln (weiss aber nicht obs überhaupt geht):
> ich weiss, dass es eine Bijektion zwischen [mm]\IN^{2}[/mm] und [mm]\IN[/mm]
> gibt, also kann ich die Punkte in [mm]\IN^2[/mm] sozusagen
> abzählen, d.h. ich kann jeder Funktion [mm]f\in ^{\IN}\IN[/mm] eine
> unendliche Teilmenge von [mm]\IN[/mm] zuordnen. ich weiss aber nicht
> ob mich das weiterbringt.
>
>
> Ich wäre um jede Antwort froh, auch nur schon über die
> Info, obs die Bijektion überhaupt gibt
Behauptung:
[mm] \IN [/mm] und [mm] \IN^{\IN} [/mm] sind gleich mächtig.
Beweis durch vollständige Induktion....
Gruß Abakus
|
|
|
| |
|
| Status: |
(Korrektur) fundamentaler Fehler  | | Datum: | 20:35 Do 11.02.2010 | | Autor: | SEcki |
> Behauptung:
> [mm]\IN[/mm] und [mm]\IN^{\IN}[/mm] sind gleich mächtig.
> Beweis durch vollständige Induktion....
Das geht so nicht - mit Induktion beweist man für endliche natürliche Zahlen, nicht für die natürlichen Zahlen als Ganzheit. Dafür bräuchtest du transfinite Induktion - und die geht schief, da es einfach falsch ist.
SEcki
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:36 Do 11.02.2010 | | Autor: | nooschi |
hmm.... aalso nochmals langsam für Dummies:
[mm] |\IN|=|\IN^1|
[/mm]
und nun will ich zeigen: [mm] |\IN|=|\IN^n|\rightarrow |\IN|=|\IN^{n+1}|
[/mm]
ok, das ist mir klar wie ich das beweisen muss, ist mir aber zu müsahm hier auszuführen.
Aber wenn ich das habe, dann weiss ich, dass [mm] $|\IN|=|\IN^n|\forall n\in\IN$
[/mm]
und jetzt kommt der Punkt den ich nicht verstehe: warum darf ich jetzt auch [mm] \IN [/mm] für n einsetzen?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:45 Do 11.02.2010 | | Autor: | felixf |
Moin!
> hmm.... aalso nochmals langsam für Dummies:
>
> [mm]|\IN|=|\IN^1|[/mm]
>
> und nun will ich zeigen: [mm]|\IN|=|\IN^n|\rightarrow |\IN|=|\IN^{n+1}|[/mm]
>
> ok, das ist mir klar wie ich das beweisen muss, ist mir
> aber zu müsahm hier auszuführen.
Gut.
(Wenn man mal eine Bijektion [mm] $\phi [/mm] : [mm] \IN \times \IN \to \IN$ [/mm] konstruiert hat, ist die Bijektion [mm] $\IN^n \to \IN$ [/mm] einfach: [mm] $(k_1, \dots, k_n) \mapsto \phi( \cdots \phi(\phi(k_1, k_2), k_3), \dots, k_n)$.)
[/mm]
> Aber wenn ich das habe, dann weiss ich, dass
> [mm]|\IN|=|\IN^n|\forall n\in\IN[/mm]
![[ok]](/images/smileys/ok.gif "[ok]")
> und jetzt kommt der Punkt den
> ich nicht verstehe: warum darf ich jetzt auch [mm]\IN[/mm] für n
> einsetzen?
Darfst du nicht. Also nicht wenn weiterhin [mm] $|\IN^\IN| [/mm] = [mm] |\IN|$ [/mm] gelten soll.
LG Felix
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:34 Do 11.02.2010 | | Autor: | SEcki |
> Ich wäre um jede Antwort froh, auch nur schon über die
> Info, obs die Bijektion überhaupt gibt
Die gibt es nicht. Zum Beweis, schau zB mal in Deiser, Einführung in die Mengenlehre, da ist's sehr ausführlich.
SEcki
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:40 Do 11.02.2010 | | Autor: | nooschi |
ah ok, dankeschön!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:42 Do 11.02.2010 | | Autor: | felixf |
Halo!
> Hallo zusammen,
>
> ich frage mich gerade, ob [mm]\IN^{\IN}[/mm] bzw. die Menge aller
> Funktionen die von [mm]\IN[/mm] nach [mm]\IN[/mm] gehen (:= [mm]^{\IN}\IN),[/mm]
> dieselbe Kardinalität wie [mm]\IN[/mm] haben.
>
> Ich wäre um jede Antwort froh, auch nur schon über die
> Info, obs die Bijektion überhaupt gibt
Schau dir mal [mm] $\{ 1, 2 \}^\IN$ [/mm] an. Dies ist offenbar eine Teilmenge von [mm] $\IN^\IN$. [/mm]
Also muss [mm] $|\{ 1, 2 \}^\IN| \le |\IN^\IN|$ [/mm] gelten.
Nun ist [mm] $\{ 1, 2 \}^\IN$ [/mm] aber die Potenzmenge von [mm] $\IN$, [/mm] womit sie strikt maechtiger as [mm] $\IN$ [/mm] ist. (Die Potenzmenge ist gleichmaechtig zu [mm] $\IR$.)
[/mm]
Es kann also sein, dass [mm] $\IN^\IN$ [/mm] sogar noch echt maechtiger ist als [mm] $\IR$.
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:59 Do 11.02.2010 | | Autor: | nooschi |
> Halo!
>
> > Hallo zusammen,
> >
> > ich frage mich gerade, ob [mm]\IN^{\IN}[/mm] bzw. die Menge aller
> > Funktionen die von [mm]\IN[/mm] nach [mm]\IN[/mm] gehen (:= [mm]^{\IN}\IN),[/mm]
> > dieselbe Kardinalität wie [mm]\IN[/mm] haben.
> >
> > Ich wäre um jede Antwort froh, auch nur schon über die
> > Info, obs die Bijektion überhaupt gibt
>
> Schau dir mal [mm]\{ 1, 2 \}^\IN[/mm] an. Dies ist offenbar eine
> Teilmenge von [mm]\IN^\IN[/mm].
>
> Also muss [mm]|\{ 1, 2 \}^\IN| \le |\IN^\IN|[/mm] gelten.
>
> Nun ist [mm]\{ 1, 2 \}^\IN[/mm] aber die Potenzmenge von [mm]\IN[/mm],
hmm, stimmt jetzt erinnere ich mich auch wieder, dass ich das irgendwo einmal gelesen habe.
> womit
> sie strikt maechtiger as [mm]\IN[/mm] ist. (Die Potenzmenge ist
> gleichmaechtig zu [mm]\IR[/mm].)
>
> Es kann also sein, dass [mm]\IN^\IN[/mm] sogar noch echt maechtiger
> ist als [mm]\IR[/mm].
>
> LG Felix
>
danke vielmals!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:32 Do 11.02.2010 | | Autor: | SEcki |
> Es kann also sein, dass [mm]\IN^\IN[/mm] sogar noch echt maechtiger
> ist als [mm]\IR[/mm].
In Wahrheit sind sie aber gleichmächtig. Der Vollständigkeit (!) halber. ;)
SEcki
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:30 Do 11.02.2010 | | Autor: | felixf |
Moin!
> > Es kann also sein, dass [mm]\IN^\IN[/mm] sogar noch echt maechtiger
> > ist als [mm]\IR[/mm].
>
> In Wahrheit sind sie aber gleichmächtig. Der
> Vollständigkeit (!) halber. ;)
Stimmt, das ist nicht offensichtlich aber man kann's beweisen.
LG Felix
|
|
|
|
