Menge der binären Folgen überazählbar unendlich

Question

Hi,

ich komme leider bei dem Beweis, dass die Menge der binären Folgen {a I a: ℕ → {0,1}} überabzählbar unendlich sein soll einfach nicht weiter. Ich weiß, dass es bei den reellen Zahlen mit Cantors Diagonalargument geht, aber bei dieser Aufgabe stehe ich komplett auf dem Schlauch.

Vielen Dank schon einmal im Voraus.

Answer 1

Nimm mal an es gäbe eine Abzählung \( ( a_i)_{i\in\mathbb{N}} \) dieser Folgen

Jetzt konstruiere dir die Folge b mit

$$ b(i) := 1 - a_i(i),~i\in\mathbb{N} $$

Ist das b einem der \(a_i\) gleich? Was folgerst du?

Comments

Tut mir leid ich verstehe es gerade einfach nicht.

Wieso konstruiert man eine Folge b(i) := 1-a_i(i), i∈ ℕ ?

---

Du machst hier nichts anders als beim Beweis der Überabzählbarkeit der reellen Zahlen. Nimm dir zum Beispiel einfach mal 3 Folgen aus der angenommenen Abzählung

$$ a_1 = (1,0,1,1,...)$$

$$ a_2 = (0,1,1,0,...)$$

$$ a_3 = (1,0,0,1,...)$$

Jetzt konstruieren wir die ersten 3 Folgenglieder von b

$$b(1) = 1 - a_1(1) = 1 - 1 = 0$$

Das erste Glied von \( a_1\) ist ja 1.

Und weiter

$$b(2)=1-a_2(2) = 1 - 1 = 0$$

$$b(3)=1-a_3(3) = 1 - 0 = 1$$

usw. Dein b unterscheidet sich dann von allen Folgen in deiner Abzählung, ist aber selbst eine Folge mit Werten 0/1. Also ist deine Abzählung unvollständig und der Raum der Folgen damit überabzählbar.

---

Ah jetzt habe ich es verstanden,