Wie zeigt man die Überabzählbarkeit der Menge der {0,1}-Folgen?

Question

Aufgabe:

{0,1} ^ℕ :={x : ℕ → {0,1}}

Davon soll man die Überabzählbarkeit beweisen.

Problem/Ansatz:

Im Internet gibt es ja eigentlich viel zu dem Thema. Allerdings verwirrt mich die Schreibweise der Aufgabe ein wenig. Manchmal wurde ein Beweis in den Bereich der Natürlichen, dann wieder mit den Reellen Zahlen geführt. Dann wurde bei verschiedenen Beweisen mit Surjektivität gerechnet, dann wieder andere mit Bijektivität. -> Ich weiß nicht weiter. Könnt ihr es richtig stellen? :)

Answer 1

Mache das gleich, wie ihr die Überabzählbarkeit der reellen Zahlen gezeigt habt.

Am einfachsten wohl so: https://de.wikipedia.org/wiki/Cantors_zweites_Diagonalargument

Comments

Also könnte ich es theoretisch so abschreiben??

---

Ja. Die Folgen haben unendlich viele Elemente.

Angenommen, du hast eine Abzählung, kannst du sie hinschreiben.

Nun kannst du eine Folge finden, die sicher noch nicht aufgezählt wurde. Das machst du, indem du eine Folge in der Diagonalen definierst, in der du an jeder Stelle die Ziffer änderst, d.h. bei {0,1}^ℕ einfach 1 und 0 vertauschst.

Answer 2

Das ist die Binärdarstellung der Zahlen im Intervall \(\left[0,1\right]\). Dieses Intervall ist ebenso überabzählbar wie die Menge der reellen Zahlen selbst. Man könnte bei Bedarf eine Bijektion basteln oder es einfach bei dem Hinweis belassen.

Comments

Also ist ℕ gar nicht ausschlaggebend, sondern das Intervall?

---

Also der Ansatz vielleicht so?

{0,1}^ℕ := x:ℕ → {0,1} | {0,1}^ℕ | = |P(ℕ)| = 2^|ℕ|

Beweis durch Widerspruch

Satz: {0,1}^ℕ  ist abzählbar