Um einzusehen, dass die Potenzmenge von [latex]\Sigma^*[/latex]
nicht abzählbar ist, reicht es ja zu sehen, dass die Potenzmenge
der natürlichen Zahlen nicht abzählbar ist (die natürlichen Zahlen
lassen sich ja als {a}* in [latex]\Sigma^*[/latex] einbetten).
Angenommen, man hätte eine Bijektion [latex]F:\mathbb{N}\to\mathcal{P}(\mathbb{N})[/latex].
Dann setze [latex]T:=\{n\in\mathbb{N}\mid n\notin F(n)\}[/latex].
Dann gibt es offenbar kein m mit F(m)=T, denn:
- Im Fall [latex]m\in F(m)[/latex] würde [latex]m\notin T[/latex] folgen, also [latex]T\ne F(m)[/latex].
- Im Fall [latex]m\notin F(m)[/latex] wäre [latex]m\in T[/latex], also auch [latex]T\ne F(m)[/latex].
Also ist F nicht surjektiv.
Intuitiv gesprochen: Für die Teilmengen der natürlichen Zahlen
haben wir so viele Wahlmöglichkeiten, dass wir für jede solche
Funktion eine Teilmenge finden können, die sich von allen getroffenen
Teilmengen fernhält, d.h. die Potenzmenge enthält viel mehr Elemente
als die natürlichen Zahlen selbst.
Edit: Eine Daumenregel für Abzählbarkeit ist übrigens folgende:
Eine Menge ist immer dann abzählbar, wenn man für jedes
Element eine endliche Darstellung finden kann, d.h. wenn endlich
viel Information genügt, um es zu beschreiben. Das ist z.B. bei den
endlichen Teilmengen von [latex]\Sigma^*[/latex] der Fall, bei
allen Teilmengen von [latex]\Sigma^*[/latex] dagegen nicht.
