Beweise, dass M = {f | f: IN ––> {0,1}} überabzählbar ist.

Question

Ich weiß leider nicht wie ich dies beweisen soll, gerade beim beweisen stell ich mich immer etwas schwierig an. Ich bin sehr dankbar über jeden Tip.

Die Aufgabe:

Sei \( M = \{ f | f : N \rightarrow \{ 0 , I \} \} \)

N sind die natürlichen Zahlen, ich hab das Zeichen leider nicht gefunden. ;)

Beweisen Sie, dass M überabzählbar ist.

Answer 1

Du kannst hier das Zweite Cantor'sche Diagonalargument nutzen:

Nimm das Gegenteil an, d.h.: sei die Menge abzählbar unendlich. Dann existiert einen Bijektion φ: ℕ→Μ und man kann eine Tabelle erstellen:

n φ(n)(1) φ(n)(2) φ(n)(3) ... 1 2 3 ...

a11	a12	a13	...
a21	a22	a23	...
a31	a32	a33	...
...	...	...	...

Was bedeutet das jetzt?
Die Menge besteht aus allen Funktionen f, die jeder natürlichen Zahl einen Wert der Menge {0, 1} zuordnen, das heißt, ein mögliches f sieht so aus:

f(1) = 0, f(2)=0, f(3)=1, f(4)=0, f(5)=1, f(6)=1, ...

in beliebiger Kombination folgen also 0en und 1en aufeinander. Aus der Annahme, es gebe nur abzählbar endlich viele solcher Funktionen folgt, dass es eine Bijektion zu den natürlichen Zahlen gibt: das heißt, man kann diese Funktionen durchnummerieren, wie ist erstmal egal.

In der Tabelle steht nun in der ersten Zeile die erste Funktion, in der zweiten die Zweite usw. Und in den Spalten steht dann jeweils der Wert der ersten Funktion für die 1, für die 2 und so weiter.

Stünde etwa die Beispielfunktion in der ersten Zeile, dann wäre

a₁₁ = 0, a₁₂ = 0, a₁₃ = 1, ...

Da es sich um eine Bijektion handelt, muss jede mögliche Funktion vorkommen - und zwar genau einmal.

Nun kann man aber mit dem Cantorschen Diagonalargument eine Funktion konstruieren, die in der Tabelle nicht vorkommt und zwar folgendermaßen:

Wähle eine neue Funktion und zwar folgendermaßen:

g(1) = ¬a₁₁
g(2) = ¬a₂₂
g(3) = ¬a₃₃
...
g(k) = ¬a_kk

Wobei die Funktion ¬: {0, 1}→ {0, 1} folgendermaßen definiert sei:

¬0 = 1
¬1 = 0

Diese Funktion g hat nun die folgenden Eigenschaften:

1.) Sie ist auf ganz ℕ definiert.

2) Sie nimmt Werte in der Menge {0, 1} an.

Diese beiden Eigenschaften zeigen schonmal, dass sie eigentlich in der Tabelle vorkommen muss.

Aber die dritte Eigenschaft ist:

3.) Sie kommt nicht in der Tabelle vor.

Wie zeigt man die dritte Eigenschaft?
Ganz einfach: damit sie in der Tabelle vorkommt, muss eine Zeile existieren, mit der sie komplett identisch ist.

Aber: von jeder Zeile unterscheidet sie sich mindestens in der k-ten Spalte, denn da ist sie ja gerade als Gegenteil definiert worden. Mit anderen Worten (wenn man die Funktion der n-ten Zeile f_n nennt:)

g(1) ≠ f₁(1)
g(2) ≠ f₂(2)
g(3) ≠ f₃(3)
...

Also ist die Menge nicht abzählbar.