Diagonalisierung < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Sei [mm] $\IN^{\IN}=\{s | s \mbox{ ist eine unendliche Folge in } \IN\}.$ [/mm] Zeigen Sie, dass [mm] $|\IN|<|\IN^{\IN}|$ [/mm] ist. |
Hallo,
die Lösung für diese Aufgabe scheint genau der Beweis des "Satz von Cantor" aus dem folgenden Wikipedia-Eintrag zu sein:
![[]](/images/popup.gif) Satz von Cantor
Leider habe ich einige Schwierigkeiten, den Beweis nachzuvollziehen.
Bei meiner Aufgabe stelle ich mir das so vor; ich habe zwei Mengen, mit z.B.:
[mm] $\IN=\{1,2,3\}$
[/mm]
[mm] $\IN^{\IN}=\{1,2,3,4,5,6,7,8,9\}$
[/mm]
Ich sehe, dass Injektivität herrscht, jedoch herrscht keine Surjektivität und keine Bijektivität.
Um über einen Widerspruch zu zeigen, dass es keine Surjektivität gibt, nehme ich an, dass es doch eine surjektive Abbildung [mm] $f:\IN \to \mathcal P(\IN)$ [/mm] gibt.
Definiere nun [mm] $M:=\{x \in \IN | x \not\in f(x) \} \in \mathcal P(\IN).$ [/mm] Wegen der Annahme, dass [mm] $\!f\$ [/mm] surjektiv ist, gibt es ein $n [mm] \in \IN$ [/mm] mit $f(n)=M.$ Dann gilt aber: $n [mm] \in [/mm] f(n) [mm] \gdw [/mm] n [mm] \in [/mm] M [mm] \gdw [/mm] n [mm] \not\in [/mm] f(n).$
(Erste Äquivalenz wegen $f(n)=M,$ zweite Äquivalenz nach Definition von M)
Mein Problem:
[mm] $M:=\{x \in \IN | x \not\in f(x) \} \in \mathcal P(\IN)$ [/mm] leuchtet mir überhaupt nicht ein. M enthält alle natürlichen Zahlen, für die gilt, dass sie nicht in f(x) enthalten sind, M ist aber in [mm] $\mathcal [/mm] P$ enthalten. Dabei dachte ich f(x) meint [mm] $\mathcal [/mm] P.$ Was ist hier wirklich gemeint?
Es wäre sehr nett, wenn jemand bei Gelegenheit hier ein paar hilfreiche Worte niederschreiben könnte.
Vielen Dank!
Gruß
el_grecco
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:57 Fr 13.05.2011 | | Autor: | Blech |
Hi,
> $ [mm] \IN=\{1,2,3\} [/mm] $
definitiv nicht. =)
Anstatt des abstrakten Beweises mach's so:
[mm] $\IN=\{1,2,3,4,5,\ldots\}$
[/mm]
und [mm] $\IN^\IN$ [/mm] ist die Menge aller unendlichen Folgen, d.h. aller Tupel [mm] $(a_1,a_2,\ldots)$.
[/mm]
Wären sie gleichmächtig, gäbe es also eine bijektive Abbildung, könnte man die beiden folgendermaßen in einer Tabelle anordnen (da [mm] $\IN$ [/mm] abzählbar ist):
[mm]\begin{tabular}{|c|c|c|}
\hline
\mathbb{N} &\mathbb{N}^\IN & \text{Bsp.}\\
\hline
\hline
1 & (a_{1,1}, a_{1,2}, a_{1,3}, a_{1,4},\ldots) & (1, 2, 3, 4, \ldots)\\
2 & (a_{2,1}, a_{2,2}, a_{2,3}, a_{2,4},\ldots)& (35, 5, 6, 25345,\ldots)\\
3 & (a_{3,1}, a_{3,2}, a_{3,3}, a_{3,4},\ldots)& (3246, 231, 3, 1,\ldots)\\
\vdots & \vdots & \vdots\\
\hline
\end{tabular}
[/mm]
Da die Abbildung bijektiv ist, muß jedes Element in [mm] $\IN^\IN$ [/mm] irgendwo in dieser Liste auftauchen.
Was ist also mit dem Element [mm] $(a_{1,1}+1, a_{2,2}+1,\ldots, a_{i,i}+1,\ldots)$?
[/mm]
(mit den Bspen also $(2, 6, 4, [mm] \ldots)$ [/mm] )
|
|
|
| |
|
| Aufgabe | | Sei $ [mm] \IN^{\IN}=\{s | s \mbox{ ist eine unendliche Folge in } \IN\}. [/mm] $ Zeigen Sie, dass $ [mm] |\IN|<|\IN^{\IN}| [/mm] $ ist. |
Hi Blech,
lange ist's her, aber diese Aufgabe bereitet mir kurz vor der Klausur doch noch Schwierigkeiten...
> Anstatt des abstrakten Beweises mach's so:
>
> [mm]\IN=\{1,2,3,4,5,\ldots\}[/mm]
> und [mm]\IN^\IN[/mm] ist die Menge aller unendlichen Folgen, d.h.
> aller Tupel [mm](a_1,a_2,\ldots)[/mm].
> Wären sie gleichmächtig, gäbe es also eine bijektive
> Abbildung, könnte man die beiden folgendermaßen in einer
> Tabelle anordnen (da [mm]\IN[/mm] abzählbar ist):
>
> [mm]\begin{tabular}{|c|c|c|}
\hline
\mathbb{N} &\mathbb{N}^\IN & \text{Bsp.}\\
\hline
\hline
1 & (a_{1,1}, a_{1,2}, a_{1,3}, a_{1,4},\ldots) & (1, 2, 3, 4, \ldots)\\
2 & (a_{2,1}, a_{2,2}, a_{2,3}, a_{2,4},\ldots)& (35, 5, 6, 25345,\ldots)\\
3 & (a_{3,1}, a_{3,2}, a_{3,3}, a_{3,4},\ldots)& (3246, 231, 3, 1,\ldots)\\
\vdots & \vdots & \vdots\\
\hline
\end{tabular}
[/mm]
>
> Da die Abbildung bijektiv ist, muß jedes Element in
> [mm]\IN^\IN[/mm] irgendwo in dieser Liste auftauchen.
>
>
> Was ist also mit dem Element [mm](a_{1,1}+1, a_{2,2}+1,\ldots, a_{i,i}+1,\ldots)[/mm]?
>
> (mit den Bspen also [mm](2, 6, 4, \ldots)[/mm] )
Ich sehe, dass Du hier die Diagonale meinst, ich sehe aber leider nicht, wie das zum gewünschten Widerspruch führt...?
Vielen Dank!
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:22 So 04.09.2011 | | Autor: | Helbig |
Die konstruierte Folge [mm](a_{1,1}+1, a_{2,2}+1, a_{3,3}+1, \;\ldots)[/mm] müßte laut Annahme in einer der Tabellenzeilen stehen. Tut sie das?
|
|
|
| |
|
| Aufgabe | | Sei $ [mm] \IN^{\IN}=\{s | s \mbox{ ist eine unendliche Folge in } \IN\}. [/mm] $ Zeigen Sie, dass $ [mm] |\IN|<|\IN^{\IN}| [/mm] $ ist. |
Hallo Helbig,
> Die konstruierte Folge [mm](a_{1,1}+1, a_{2,2}+1, a_{3,3}+1, \;\ldots)[/mm]
> müßte laut Annahme in einer der Tabellenzeilen stehen.
> Tut sie das?
Deiner Frage nach zu urteilen nicht. 
Aber woher weiß ich, ob diese konstruierte Folge nicht irgendwo in der Fortsetzung der Tabelle auftaucht?
Vielen Dank!
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:43 Mo 05.09.2011 | | Autor: | Blech |
Hi,
dann müßte sie ja bei einem gewissen Index n auftauchen. Aber nach Konstruktion kann das nicht sein, denn wie sieht der n-te Eintrag aus?
ciao
Stefan
|
|
|
| |
|
| Aufgabe | | Sei $ [mm] \IN^{\IN}=\{s | s \mbox{ ist eine unendliche Folge in } \IN\}. [/mm] $ Zeigen Sie, dass $ [mm] |\IN|<|\IN^{\IN}| [/mm] $ ist. |
Hi Stefan,
> dann müßte sie ja bei einem gewissen Index n auftauchen.
> Aber nach Konstruktion kann das nicht sein, denn wie sieht
> der n-te Eintrag aus?
[mm] $(a_{n,1},a_{n,2},a_{n,3},...,a_{n,i})$
[/mm]
Sorry, aber der Groschen will bei mir einfach noch nicht fallen... ![[verwirrt]](/images/smileys/verwirrt.gif "[verwirrt]")
> ciao
> Stefan
Vielen Dank für Deine Hilfe!
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:14 Mo 05.09.2011 | | Autor: | Blech |
> $ [mm] (a_{n,1},a_{n,2},a_{n,3},...,a_{n,i}) [/mm] $
Das ist eine endliche Folge, wir haben aber unendliche.
[mm] $(a_{n,1},a_{n,2},\ldots, a_{n,n-1},a_{n,n},a_{n,n+1},\ldots)$
[/mm]
wie war jetzt die Konstruktionsvorschrift?
[mm] $a_{n,1}=a_{1,1}+1$
[/mm]
[mm] $a_{n,2}=a_{2,2}+1$
[/mm]
[mm] $~\qquad\vdots$
[/mm]
ciao
Stefan
|
|
|
| |
|
| Aufgabe | | Sei $ [mm] \IN^{\IN}=\{s | s \mbox{ ist eine unendliche Folge in } \IN\}. [/mm] $ Zeigen Sie, dass $ [mm] |\IN|<|\IN^{\IN}| [/mm] $ ist. |
Hallo Stefan,
> [mm](a_{n,1},a_{n,2},\ldots, a_{n,n-1},a_{n,n},a_{n,n+1},\ldots)[/mm]
>
> wie war jetzt die Konstruktionsvorschrift?
>
> [mm]a_{n,1}=a_{1,1}+1[/mm]
> [mm]a_{n,2}=a_{2,2}+1[/mm]
> [mm]~\qquad\vdots[/mm]
ich habe alle Antworten sauber auf Papier mitgeschrieben, aber ich sehe leider noch immer nicht, worauf die Informationen hinauslaufen?
> ciao
> Stefan
Danke für Deine Geduld!
Gruß
el_Grecco
|
|
|
| |
|
Hallo el grecco,
es wurde alles schon versucht zu erklären, deswegen Zusammenfassung:
Angenommen die Abbildung [mm] J:\IN\to{\IN}^{\IN} [/mm] ist bijektiv (eine Abzählung von [mm] \IN^{\IN}). [/mm] Dann bildet J die natürlichen Zahlen auf Folgen ab. Es wird also [mm] i\in\IN [/mm] auf die Folge [mm] (a_{i, n}) [/mm] abgebildet, hier ist n die Laufvariable der Folge.
Betrachtet wird nun die Folge [mm] (a_n) [/mm] natürlicher Zahlen mit [mm] a_i=a_{i,i}+1 [/mm] für alle [mm] i\in\IN. [/mm] Da nach Annahme J eine Abzählung aller natürlichen Folgen ist, müsste es ein Urbild von [mm] (a_n) [/mm] unter der Abbildung J in [mm] \IN [/mm] geben. Sagen wir [mm] J^{-1}(a_n)=m. [/mm] Dann gilt aber nach Konstruktion von [mm] (a_n), [/mm] dass [mm] a_{m}=a_{m,m}+1\neq a_{m,m}. [/mm] Das ist aber ein Widerspruch, denn es folgt [mm] J(m)\neq (a_n).
[/mm]
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:14 Mo 05.09.2011 | | Autor: | el_grecco |
Hallo kamaleonti,
vielen Dank für Deine Ausführung, jetzt habe ich es endlich verstanden!
Gruß
el_grecco
|
|
|
|
