ℝ und die Potenzmenge der natürlichen Zahlen

 Wir zeigen || =|()|. Die Grundidee ist, dass wir einer Teilmenge A von  ihre Indikatorfunktion indA :   { 0, 1 } zuordnen. Allgemein definieren wir:

Definition (Indikatorfunktion oder charakteristische Funktion)

Sei M eine Menge, und sei A ⊆ M. Dann ist die Indikatorfunktion von A in M  indA, M : M  { 0, 1 } definiert durch

indA,M(x)=1,falls xA,0,falls xA.

 Es gilt nun:

Satz

Sei M eine Menge. Dann gilt |(M)| = |M{ 0, 1 }|.

Beweis

Wir definieren f : (M)  M{ 0, 1 } bijektiv durch

f (A)  =  indA, M  für A ⊆ M.

 Hinsichtlich |()| = || fassen wir nun indA, für A ⊆  einfach als reelle Zahl im Einheitsintervall in Binärdarstellung auf. Da endliche Mengen dadurch in eine trivial endende Darstellung einer reellen Zahl übergehen, ist aber etwas Vorsicht geboten. Wir brauchen eine Vorüberlegung.

Definition (*())

Wir setzen

*()  =  { A ⊆  | A ist unendlich }.

 Als Übung kann der Leser versuchen, folgenden Satz zu zeigen:

Satz

Es gilt |*()| = |()|.

Beweis

|*()| ≤ |()| ist klar wegen *() ⊆ (). Wir zeigen

|()| ≤ |*()|.

Hierzu definieren wir f : ( *() wie folgt. Sei

U = { 2n + 1 | n  ∈   }

die Menge aller ungeraden natürlichen Zahlen. Wir setzen für A ⊆ :

f (A)  =  { 2n | n  ∈  A }  ∪  U.

Dann ist f : ( *() injektiv, also gilt |()| ≤ |*()|.

 Der Beweis, den der Leser gefunden hat, ist vielleicht: () ist überabzählbar (durch Diagonalisierung, vgl. auch Kapitel 10), E = { A ⊆  | A ist endlich } ist abzählbar, und die Subtraktion einer abzählbaren Menge ändert die Mächtigkeit nicht.

 Damit können wir nun leicht den fundamentalen Zusammenhang zwischen den Mächtigkeiten der natürlichen und der reellen Zahlen zeigen:

Satz

Es gilt || = |()|.

Beweis

Sei I = ] 0, 1 ] = { x  ∈   | 0 < x ≤ 1 }. Es gilt |I| = || und |()| = |*()|. Es genügt also zu zeigen, dass |I| = |*()|. Hierzu definieren wir f : I  *() wie folgt. Sei x  ∈  I und sei, in kanonischer Binärdarstellung,

x  =  0, a0 a1 a2 … 

mit an  ∈  { 0, 1 }. Wir definieren f (x) ⊆  durch:

f (x)  =  { n | an = 1 }.

Da die kanonische Darstellung von x nicht trivial endet, ist f (x) unendlich für alle x  ∈  I. Das so definierte f : I  *() ist bijektiv.

 Die beiden wichtigsten Strukturen der Mathematik  und  sind also von unterschiedlicher Mächtigkeit, und die Mächtigkeit der zweiten ist gerade die Mächtigkeit der Potenzmenge der ersten. Ein bemerkenswerter Zusammenhang! In der Mengenlehre wird oftmals sogar eine Teilmenge von  direkt als reelle Zahl bezeichnet.

 Eine etwas andere Strategie, um || = |()| zu zeigen, ist diese: Der unproblematische Teil ist der Nachweis von || = |[ 0, 1 ]| ≤ |()|, was man durch kanonische binäre Darstellung von x  ∈ [ 0, 1 ] leicht zeigt. Für die Umkehrung |()| ≤ || ist die Mehrdeutigkeit der Binärdarstellung hinderlich. Dieses Problem kann man nun umgehen, indem man zu b-adischen Entwicklungen mit b > 2 übergeht. Der einfachste Fall b = 3 führt zur sogenannten Cantormenge, die wir in Kapitel 12 des zweiten Abschnitts ausführlich untersuchen werden.

Übung

Die Cantormenge C ⊆  ist definiert als die Menge aller reellen Zahlen x mit 0 ≤ x ≤ 1, für die es eine (nicht notwendig kanonische) Ternär-Darstellung (= 3-adische Darstellung)

x  =  0, a0 a1 a2 … 

gibt mit der Eigenschaft: für alle n ist an ≠ 1. Anders ausgedrückt: x lässt sich schreiben als

x  =  a0/3 + a1/32 + a2/33 + …

mit an  ∈  { 0, 2 }. Zeigen Sie:

|C| = |{ 0, 1 }| = |()| (und damit |()| = ||).