Menge aller Abbildungen < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:20 Di 08.05.2007 | | Autor: | Zerwas |
| Aufgabe | Sei M = [mm] [0,1]^\IN [/mm] die Menge der Abbildungen [mm] \IN \to [/mm] {0, 1}.
Beweisen Sie:
(1) M ist überabzählbar.
(2) Ist A abzählbar, so ist P(A) überabzählbar. |
Ich habe mir folgendes gedacht:
Es existieren eine überabzählbare Anzahl von Abbildungen, da ich eine abzählbare Anzahl Abbildungen konstruieren kann die jeweils alle [mm] n\in\IN [/mm] der 0 zuweist außer das Element mit dem es "zum abzählen" aus [mm] \IN [/mm] identifiziert wird. Dieses wird der 1 zugeordenet ... jetzt existieren aber noch überabzählbar viele Abbildungen die eines odere mehrer andere Elemente der 1 zuweisen.
Ist der Gedanke richtig und vollständig? Und wie schreibe ich das mathematisch korrekt auf?
Ich habe diese Frage auf keinem anderen Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:56 Di 08.05.2007 | | Autor: | felixf |
Hallo!
> Sei M = [mm][0,1]^\IN[/mm] die Menge der Abbildungen [mm]\IN \to[/mm] {0,
> 1}.
> Beweisen Sie:
> (1) M ist überabzählbar.
> (2) Ist A abzählbar, so ist P(A) überabzählbar.
> Ich habe mir folgendes gedacht:
>
> Es existieren eine überabzählbare Anzahl von Abbildungen,
> da ich eine abzählbare Anzahl Abbildungen konstruieren kann
> die jeweils alle [mm]n\in\IN[/mm] der 0 zuweist außer das Element
> mit dem es "zum abzählen" aus [mm]\IN[/mm] identifiziert wird.
> Dieses wird der 1 zugeordenet ... jetzt existieren aber
> noch überabzählbar viele Abbildungen die eines odere mehrer
> andere Elemente der 1 zuweisen.
>
> Ist der Gedanke richtig und vollständig? Und wie schreibe
> ich das mathematisch korrekt auf?
Wenn du so argumentierst, ist [mm] $\IQ$ [/mm] auch ueberabzaehlbar, da ja [mm] $\IN \subseteq \IQ$ [/mm] abzaehlbar ist und es zwischen zwei Elementen aus [mm] $\IN$ [/mm] unendlich viele weitere Elemente aus [mm] $\IQ$ [/mm] gibt.
Das ist aber nicht der Fall...
Du musst hier ein Diagonalargument verwenden wie bei dem Beweis, dass [mm] $\IR$ [/mm] nicht abzaehlbar ist (kennst du den?). Du nimmst also an, dass es eine Bijektion [mm] $\IN \to \{ 0, 1 \}^{\IN}$ [/mm] gibt, und konstruierst damit einen Widerspruch. (Wenn du eine Idee brauchst, google mal nach ``Cantorsches Diagonalargument''...)
Aufgabenteil (2) folgt uebrigens ziemlich direkt aus (1)...
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:47 Do 10.05.2007 | | Autor: | Zerwas |
Okay ... d.h. dass ich das dann so mache:
Beweis durch Widerspruch:
Angenommen M sei abzählbar => [mm] \exists f:\IN\to [/mm] M, f bijektiv.
Sei [mm] (a_i) [/mm] irgendeine Folge von Elementen aus M, [mm] i\in\IN
[/mm]
[mm] \begin{matrix}
& 1\mapsto & 2\mapsto & 3\mapsto & ... \\
a_1: & x_{11} & x_{12} & x_{13} & ... \\
a_2: & x_{21} & x_{22} & x_{23} & ... \\
a_1: & x_{31} & x_{32} & x_{33} & ... \\
a_4: & ... \\
\vdots
\end{matrix}
[/mm]
[mm] x_{ij}\in [/mm] {0,1}
Nun sei [mm] m\in [/mm] M derart gewählt, dass gilt:
[mm] \begin{matrix}
m:&1\mapsto& \begin{cases} 0, & \mbox{für } x_{11}=1 \\ 1, & \mbox{für } x_{11}=0 \end{cases}& => m\not= a_1\\
\ & 2\mapsto& \begin{cases} 0, & \mbox{für } x_{22}=1 \\ 1, & \mbox{für } x_{22}=0 \end{cases}& => m\not= a_2\\
\ & 3\mapsto& \begin{cases} 0, & \mbox{für } x_{33}=1 \\ 1, & \mbox{für } x_{33}=0 \end{cases}& => m\not= a_3\\
\ & 4\mapsto& ... & => m\not= a_4\\
\ & \vdots
\end{matrix}
[/mm]
=> [mm] m\not\in a_i [/mm] = Widerspruch zur Annahme [mm] \exists f:\IN\to [/mm] M, f bijektiv
=> M ist überabzählbar.
[mm] \Box
[/mm]
Ist das so dann Korrekt?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:39 Do 10.05.2007 | | Autor: | felixf |
Hallo!
> Okay ... d.h. dass ich das dann so mache:
>
> Beweis durch Widerspruch:
> Angenommen M sei abzählbar => [mm]\exists f:\IN\to[/mm] M, f
> bijektiv.
>
> Sei [mm](a_i)[/mm] irgendeine Folge von Elementen aus M, [mm]i\in\IN[/mm]
>
> [mm]\begin{matrix}
& 1\mapsto & 2\mapsto & 3\mapsto & ... \\
a_1: & x_{11} & x_{12} & x_{13} & ... \\
a_2: & x_{21} & x_{22} & x_{23} & ... \\
a_1: & x_{31} & x_{32} & x_{33} & ... \\
a_4: & ... \\
\vdots
\end{matrix}[/mm]
>
> [mm]x_{ij}\in[/mm] {0,1}
>
> Nun sei [mm]m\in[/mm] M derart gewählt, dass gilt:
> [mm]\begin{matrix}
m:&1\mapsto& \begin{cases} 0, & \mbox{für } x_{11}=1 \\ 1, & \mbox{für } x_{11}=0 \end{cases}& => m\not= a_1\\
\ & 2\mapsto& \begin{cases} 0, & \mbox{für } x_{22}=1 \\ 1, & \mbox{für } x_{22}=0 \end{cases}& => m\not= a_2\\
\ & 3\mapsto& \begin{cases} 0, & \mbox{für } x_{33}=1 \\ 1, & \mbox{für } x_{33}=0 \end{cases}& => m\not= a_3\\
\ & 4\mapsto& ... & => m\not= a_4\\
\ & \vdots
\end{matrix}[/mm]
>
> => [mm]m\not\in a_i[/mm] = Widerspruch zur Annahme [mm]\exists f:\IN\to[/mm]
> M, f bijektiv
>
> => M ist überabzählbar.
> [mm]\Box[/mm]
>
> Ist das so dann Korrekt?
Jap, das ist perfekt so.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:03 Di 08.05.2007 | | Autor: | Ankh |
Da die Frage schon beantwortet wurde, werfe ich nur diesen ![[]](/images/popup.gif) Link in die Runde.
|
|
|
|
