Menge aller endliche 01-Folgen abzählbar?

Erste Frage Aufrufe: 1349     Aktiv: 21.02.2021 um 11:15
0
Hi, ich soll beweisen, dass die Menge aller endlichen 01-Folgen abzählbar ist bzw. dass die Menge aller unendlichen 01-Folgen, die nicht ab einem Index konstant ( 0 oder 1) sind, überabzählbar sind.

Nun, soweit ich es verstanden habe ist eine Menge dann abzählbar, wenn ihre Mächtigkeit kleinergleich der Mächtigkeit von N ist bzw. wenn eine Bijektion zwischen N und der gegeben Menge liegt.

Ich fange gerade erst an mich mit mathemtaischen Beweisen zu befassen, und mir fehlt glaube ich ein wenig ein Startpunkt. Denn: bijektiv ist die Menge der endlichen 01-Folgen glaube ich nicht, da man eine 01-Folge ja theoretisch auch als Treppenfunktion darstellen könnte, und diese in bezug auf N nicht injektiv ist, und daher auch nicht bijektiv. Und intuitiv hätte ich schon gesagt dass deren Mächtigkeiten gleich groß sind, da beide Mengen abzählbar viele Elemente besitzen, aber dann wäre ja auch die Menge aller unendlichen 01-Folgen abzählbar, was aber laut Angabe nicht so ist? 

Würde mich über jeden Tipp freuen.

Lg Lola
Diese Frage melden
gefragt

Punkte: 20

 
Kommentar schreiben
1 Antwort
1
Wie genau du die Aufgabe lösen sollst, hängt davon ab, wie viel ihr schon in Bezug auf Kardinalitäten gelernt habt. Weißt du z.B. schon, dass abzählbare Vereinigungen abzählbarer Mengen wieder abzählbar sind? Dann ist der erste Teil einfach: Sei \(F_n\) die Menge der Folgen der Länge \(n\), dann ist \(|F_n|=2^n\) endlich und folglich die Menge aller endlichen Folgen \(\bigcup_{n\in\mathbb N}F_n\) eine abzählbare Vereinigung endlicher - also insbesondere abzählbarer - Mengen und damit abzählbar. Wenn du dieses Resultat noch nicht kennst, kannst du entweder versuchen, die Menge durchzunummerieren, oder eine Injektion in \(\mathbb Q\) angeben (vorausgesetzt, du weißt, dass \(\mathbb Q\) abzählbar ist).

Für die Überabzählbarkeit von \(\{0,1\}^\mathbb N\) kannst du eine Bijektion zu \(\mathcal P(\mathbb N)\) angeben und zeigen, dass für jede Menge \(X\) es keine Bijektion \(X\to\mathcal P(X)\) geben kann, oder eine Bijektion zu \([0,1]\) angeben, wenn du schon weißt, dass \(\mathbb R\) überabzählbar ist.
Diese Antwort melden
geantwortet

Punkte: 11.27K

 
Danke für die schnelle Antwort!
Nur für mein Verständnis nochmal: Man kann die Menge der endlichen Folgen auch als Folgen einer Länge n definieren (wie kann man sich das aber vorstellen?), und somit ist, da Länge endlich, auch die folgen endlich und abzählbar, dh. damit ist dann auch die vereinigungsmenge der abzählbaren Mengen, dh. die menge aller endlichen Folgen abzählbar? Und diesen Beweis kann man so schriftlich umsetzen und mathematisch gültig?   ─   pfeiferl99 21.02.2021 um 10:44
Jede endliche Folge hat eine bestimmte Länge \(n\). Wenn du dann über alle natürlichen Zahlen \(n\) vereinigst, ist jede endliche Folge enthalten. Das heißt nicht, dass man die Menge der endlichen Folgen als Folgen einer festen Länge \(n\) definieren kann. Sozusagen ist \(\{0,1\}^{<\mathbb N}=\bigcup_{n\in\mathbb N}\{0,1\}^n\), wobei auf der linken Seite die endlichen Folgen stehen und auf der rechten Seite die Vereinigung über alle \(n\in\mathbb N\) von Folgen der Länge \(n\).
Ab dann stimmt das, was du sagst. Jedes Element der Vereinigung ist endlich, es werden abzählbar viele Mengen vereinigt, also ist die Vereinigung selbst abzählbar. Vorausgesetzt, dieses Resultat wurde in deiner Vorlesung bewiesen, ist das ein vollständiger und korrekter Beweis.   ─   stal 21.02.2021 um 10:55
und beim zweiten Beweis hänge ich prinzipiell ein bisschen... Könntest du das vielleicht noch ein bisschen mehr erläutern? Wäre super hilfreich!
lg   ─   pfeiferl99 21.02.2021 um 10:57
Ahh okay, jetzt macht das erste Sinn!   ─   pfeiferl99 21.02.2021 um 10:59
Sei \((a_n)_{n\in\mathbb N}\) eine Folge. Setze \(\Phi((a_n)_n)=\{k\in\mathbb N\ |\ a_k=1\}\). Zeige, dass \(\Phi\) eine Bijektion \(\{0,1\}^{\mathbb N}\to\mathcal P(\mathbb N)\) ist.   ─   stal 21.02.2021 um 11:15

Kommentar schreiben