Abzählbarkeit von Folgen < naiv < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | b) Untersuchen Sie, ob die Menge aller Abbildungen $f: [mm] \mathbb{N} \rightarrow \mathbb{N}$ [/mm] mit [mm] $f(n)\leq [/mm] f(n+1)$ für alle $n [mm] \in \mathbb{N}$ [/mm] abzählbar oder überabzählbar ist. Wie verhält es sich für die Menge aller Abbildungen $f: [mm] \mathbb{N} \rightarrow \mathbb{N}$ [/mm] mit $f(n) [mm] \geq [/mm] f(n+1)$ für alle $n [mm] \in \mathbb{N}$? [/mm] |
Den ersten Teil konnte ich als überabzählbar beweisen, indem ich über Widerspruch gezeigt habe, dass es keine surjektive Abbildung von [mm] $\mathbb{N}$ [/mm] auf die definierte Menge gibt.
Beim zweiten Teil komme ich einfach nicht auf die richtige Idee dazu. Zuerst dachte ich, man könnte alle diese Folgen abzählen, war mir dann später aber nicht mehr sicher, ob das geht, da ich keine passende surjektive Abbildung finde. Der Widerspruchsbeweis von Teil 1 lässt sich auch nicht auf die zweite Menge zurechtschneiden. Ich hoffe, mir kann jemand mal einen kurzen Denkanstoß geben, mir würde es auch schon reichen, bloß zu wissen, ob man die Folgen im 2. Teil abzählen kann oder nicht.
LG Feuervogel
|
|
| |
|
> b) Untersuchen Sie, ob die Menge aller Abbildungen [mm]f: \mathbb{N} \rightarrow \mathbb{N}[/mm]
> mit [mm]f(n)\leq f(n+1)[/mm] für alle [mm]n \in \mathbb{N}[/mm] abzählbar
> oder überabzählbar ist. Wie verhält es sich für die
> Menge aller Abbildungen [mm]f: \mathbb{N} \rightarrow \mathbb{N}[/mm]
> mit [mm]f(n) \geq f(n+1)[/mm] für alle [mm]n \in \mathbb{N}[/mm]?
> Den
> ersten Teil konnte ich als überabzählbar beweisen, indem
> ich über Widerspruch gezeigt habe, dass es keine
> surjektive Abbildung von [mm]\mathbb{N}[/mm] auf die definierte
> Menge gibt.
> Beim zweiten Teil komme ich einfach nicht auf die richtige
> Idee dazu. Zuerst dachte ich, man könnte alle diese Folgen
> abzählen, war mir dann später aber nicht mehr sicher, ob
> das geht, da ich keine passende surjektive Abbildung finde.
> Der Widerspruchsbeweis von Teil 1 lässt sich auch nicht
> auf die zweite Menge zurechtschneiden. Ich hoffe, mir kann
> jemand mal einen kurzen Denkanstoß geben, mir würde es
> auch schon reichen, bloß zu wissen, ob man die Folgen im
> 2. Teil abzählen kann oder nicht.
>
Die Menge dürfte abzählbar sein.
Für f(1) gibt es abzählbar viele Möglichkeiten, danach müssen die Funktionswerte schrittweise immer kleiner werden. Daraus sollte sich ein Beweis für die Abzählbarkeit basteln lassen.
> LG Feuervogel
|
|
|
| |
|
Wenn es darauf hinauskommt, dass es für jeden Funktionswert abzählbar viele Möglichkeiten gibt, dürfte man doch auf ähnliche (nicht gleich, vielleicht liegt hier irgendwo ein Denkfehler) Weise beweisen können, dass es abzählbar viele reelle Zahlen zwischen 0 und 1 gibt?? Die erste Ziffer lässt man bei 0 und die Nachkommastellen sind nur eine Folge natürlicher Zahlen von 0-9. Daher begann ich nach einer Weile an meiner Vermutung zu zweifeln, dass man diese Folgen abzählen kann.
|
|
|
| |
|
> Wenn es darauf hinauskommt, dass es für jeden
> Funktionswert abzählbar viele Möglichkeiten gibt, dürfte
> man doch auf ähnliche (nicht gleich, vielleicht liegt hier
> irgendwo ein Denkfehler) Weise beweisen können, dass es
> abzählbar viele Reelle Zahlen zwischen 0 und 1 gibt?? Die
> erste Zffer lässt man bei 0 und die Nachkommastellen sind
> nur eine Folge natürlicher Zahlen von 0-9. Daher bagann
> ich nach einer Weile an meiner Vermutung zu zweifeln, dass
> man diese Folgen abzählen kann.
Nein. Der Punkt ist, dass die betrachteten Funktionen f(n) monoton fallend sind. Ein Beweisansatz wäre:
Ist X die Menge aller betrachteten f, so setzt man zu [mm] k\in\bN
[/mm]
[mm] X_k=\{f\in X: f(1)=k\}
[/mm]
X ist dann die (abzählbare) Vereinigung der [mm] X_k. [/mm] Da eine abzählbare Vereinigung abzählbarer Mengen wieder abzählbar ist, genügt es dann zu zeigen, dass jedes [mm] X_k [/mm] abzählbar ist .....
|
|
|
| |
|
OK. Ich zweifel zwar immer noch, dass das so einfach geht, aber warten wir mal den Beweis ab. Hättest Du vielleicht noch einen kleinen Tipp? Wie zeige ich, dass diese Mengen abzählbar sind? Den Beweis würde ich sonst induktiv führen.
|
|
|
| |
|
> OK. Ich zweifel zwar immer noch, dass das so einfach geht,
> aber warten wir mal den Beweis ab. Hättest Du vielleicht
> noch einen kleinen Tipp? Wie zeige ich, dass diese Mengen
> abzählbar sind? Den Beweis würde ich sonst induktiv
> führen.
Ganz so einfach ist es auch nicht (jedenfalls habe ich keine so einfache Idee).
Zum beweis, dass [mm] X_k [/mm] abzählbar ist, betrachtet man zu [mm] f\in X_k [/mm] und j=1,...,k jeweils die größte Zahl [mm] n_j, [/mm] für die [mm] f(n_j)\ge [/mm] j gilt. Ist [mm] f(n)\ge [/mm] j für unendlich viele j, so setze [mm] n_j=\infty.
[/mm]
Jedes [mm] f\in X_k [/mm] ist durch diese [mm] n_1,...,n_k [/mm] eindeutig bestimmt (aufgrund der Monotonie).
Da [mm] (n_1,...,n_k)\in (N\cup\{\infty\})^k, [/mm] gibt es dafür nur abzählbar viele Möglichkeiten.
|
|
|
| |
|
Ich habe folgende Idee: Ich zeige zuerst, dass [mm] $X_{1}$ [/mm] abzählbar ist (einfacher Induktionsanfang). Danach, dass sich alle f [mm] \in X_{k+1} [/mm] über
[mm] $f_{i,j}:\mathbb{N}^{2} \rightarrow X_{k+1}, f_{i,j}(n) [/mm] = [mm] \begin{cases}
k+1, & \forall n \leq i \\
g_{j}(n), & \forall n>i
\end{cases}$
[/mm]
identifizieren lassen [mm] ($f_{i,j}$ [/mm] ist surjektiv). Hier benutze ich also die nach Induktionsvoraussetzung geltende Abzählbarkeit der [mm] $g_{j} \in X_{k}$. [/mm] Ferner zeige ich, dass es eine surjektive Abbildung [mm] $h:\mathbb{N} \rightarrow \mathbb{N}^{2}$ [/mm] gibt. Durch Verketten folgt f [mm] \circ [/mm] h ist surjektiv. Und es ist $f [mm] \circ [/mm] h: [mm] \mathbb{N} \rightarrow X_{k+1}$. [/mm] Damit gilt [mm] $k\Rightarrow [/mm] k+1$.
Ginge das so?
|
|
|
| |
|
> Ich habe folgende Idee: Ich zeige zuerst, dass [mm]X_{1}[/mm]
> abzählbar ist (einfacher Induktionsanfang). Danach, dass
> sich alle f [mm]\in X_{k+1}[/mm] über
>
> [mm]$f_{i,j}:\mathbb{N}^{2} \rightarrow X_{k+1}, f_{i,j}(n)[/mm] =
> [mm]\begin{cases}
k+1, & \forall n \leq i \\
g_{j}(n), & \forall n>i
\end{cases}$[/mm]
>
> identifizieren lassen ([mm]f_{i,j}[/mm] ist surjektiv). Hier benutze
> ich also die nach Induktionsvoraussetzung geltende
> Abzählbarkeit der [mm]g_{j} \in X_{k}[/mm]. Ferner zeige ich, dass
> es eine surjektive Abbildung [mm]h:\mathbb{N} \rightarrow \mathbb{N}^{2}[/mm]
> gibt. Durch Verketten folgt f [mm]\circ[/mm] h ist surjektiv. Und es
> ist [mm]f \circ h: \mathbb{N} \rightarrow X_{k+1}[/mm]. Damit gilt
> [mm]k\Rightarrow k+1[/mm].
>
> Ginge das so?
Ich denke ja. Lediglich das f mit f(n)=k+1 für alle n erwischt du mit deiner Konstruktion nicht, aber das noch einzuauen (z.B. mit [mm] i=\infty) [/mm] ist kein wirkliches Problem.
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:41 Fr 28.10.2011 | | Autor: | m.athe |
Hallo zusammen!
Ich sitze auch gerade an der Aufgabe. Ich habe auch versucht zu zeigen, dass es keine surjektive Abbildung von [mm] \IN [/mm] in die Menge gibt, allerdings weiß ich nicht wie ich bei diesem Widerspruchsbeweis auf einen Widerspruch komme. Kann mir da jemand helfen?
Vielen Dank im Voraus
m.athe
|
|
|
| |
|
> Hallo zusammen!
> Ich sitze auch gerade an der Aufgabe. Ich habe auch
> versucht zu zeigen, dass es keine surjektive Abbildung von
> [mm]\IN[/mm] in die Menge gibt, allerdings weiß ich nicht wie ich
> bei diesem Widerspruchsbeweis auf einen Widerspruch komme.
> Kann mir da jemand helfen?
> Vielen Dank im Voraus
> m.athe
Man kann das ganze sicherlich ähnlich wie die Überabzählbarkeit der reellen Zahlen mit einem "Diagonalargument" beweisen.
Alternativ lässt sich eine injektive Abbildung von einem reellen Intervall in die betrachtete Menge M konstruieren, womit die Überabzählbarkeit auch bewiesen ist. Idee dazu:
Zu [mm] x\in[0,1;1) [/mm] und [mm] n\in [/mm] N sei [mm] f_x(n)\in [/mm] N die Summe der ersten n Nachkommastellen von x.
Beispiel: zu x = 0,142857.... ist [mm] f_x(4)=1+4+2+8=15
[/mm]
Dann ist die Abbildung [mm] [0,1;1)\to [/mm] M, [mm] x\mapsto f_x [/mm] injektiv
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:52 Sa 29.10.2011 | | Autor: | Feuervogel |
> Zu [mm]x\in[0,1;1)[/mm] und [mm]n\in[/mm] N sei [mm]f_x(n)\in[/mm] N die Summe der
> ersten n Nachkommastellen von x.
> Beispiel: zu x = 0,142857.... ist [mm]f_x(4)=1+4+2+8=15[/mm]
> Dann ist die Abbildung [mm][0,1;1)\to[/mm] M, [mm]x\mapsto f_x[/mm] injektiv
Die Abbildung ist nicht wohldefiniert. Zumindest nicht für rationale Zahlen wie 0,8 oder 0,79999999999999... ;)
|
|
|
| |
|
Ich habe einfach angenommen, dass M abzählbar wäre. Dabei habe ich mir gedanklich eine uendliche Matrix mit Folgen als Zeilen und Folgegliedern als Spalten vorgestellt. Ich habe dann eine monoton wachsende Folge konstruiert, die deswegen selbst in einer Zeile der Matrix auftaucht, aber sich selbst widerspricht. Wie man eine solche Folge nun genau konstruiert, darauf musst Du jetzt von selbst kommen.
Gruß, Feuervogel
|
|
|
|
