4.8. Gleichmächtige Mengen

Definition:  Zwei Mengen M und N heißen gleichmächtig (in Zeichen ${\displaystyle M\sim N}$), falls es eine bijektive Funktion

gibt

Bemerkung:  

Beweis:  

1. ►  Ist ${\displaystyle M\sim \varnothing }$, so gibt es eine bijektive Funktion von ${\displaystyle M\to \varnothing }$. Falls ${\displaystyle M\ne \varnothing }$, gibt es aber überhaupt keine Funktion von ${\displaystyle M\to \varnothing }$. Ist ${\displaystyle M=\varnothing }$, so ergibt sich die Behauptung aus 2.

2. ►  ${\displaystyle {\mathrm{X}}_M}$ ist eine umkehrbare Funktion von ${\displaystyle M\to M}$ ([4.7.11]).

3. ►  Ist ${\displaystyle f:M\to N}$ bijektiv, so ist ${\displaystyle f^{-1}:N\to M}$ ebenfalls bijektiv ([4.7.12]).

4. ►  Sind ${\displaystyle g:M\to N}$ und ${\displaystyle f:N\to L}$ bijektiv, so ist auch ${\displaystyle f\circ g:M\to L}$ bijektiv ([4.7.13]).

Definition:  

Bemerkung:  

Beweis:  

1. ►  Offensichtlich ist ${\displaystyle \{(\mathrm{0,}{a}_0),\dots ,(n,a_n)\}}$ eine bijektive Funktion von ${\displaystyle \{\mathrm{0,}\dots ,n\}\to \{a_0,\dots ,a_n\}}$.

2. ►  Sei ${\displaystyle f:\mathbb{N}\to M}$ eine Abzählung von M. Insbesondere ist damit ${\displaystyle M\ne \varnothing }$. Wäre nun M endlich, so gäbe es für ein ${\displaystyle n\in \mathbb{N}}$ eine Bijektion ${\displaystyle g:\{\mathrm{0,}\dots ,n\}\to M}$. ${\displaystyle h=f^{-1}\circ g}$ ist dann aber eine umkehrbare Funktion von ${\displaystyle \{\mathrm{0,}\dots ,n\}\to \mathbb{N}}$. Dabei kann h gar nicht bijektiv sein, denn es gibt natürliche Zahlen ohne h-Urbild, z.B. die Zahl ${\displaystyle \max \{h(0),\dots ,h(n)\}+1}$ - Widerspruch!

3. ►  Ergibt sich sofort aus 2.

4. ►  Der sehr elegante Beweis geht auf Cantor zurück. Wir müssen zeigen: keine Funktion ${\displaystyle f:M\to P(M)}$ ist umkehrbar. Angenommen, es gibt eine solche Funktion f. Wir betrachten dann die Menge

A kann aber kein Urbild besitzen, denn die Gleichung ${\displaystyle f(y)=A}$ für ein ${\displaystyle y\in M}$ erzeugt den Widerspruch

f ist also nicht bijektiv - Widerspruch!

Bemerkung:  

Beweis:  

1. ►  ${\displaystyle {\mathrm{X}}_{\mathbb{N}}}$ ist eine Bijektion von ${\displaystyle \mathbb{N}\to \mathbb{N}}$.

2. ►  Die Aufgabe besteht darin, die Elemente von ${\displaystyle \mathbb{Z}}$, d.h. die Zahlen .....,−2,−1,0,1,2,..... mit natürlichen Zahlen durchzunummerieren. Dies scheint schwierig zu sein, da ${\displaystyle \mathbb{Z}}$ keinen "Anfang" hat; die folgende Umsortierung aber räumt dieses Hindernis aus dem Weg: 0,−1,1,−2,2,...... Mit Hilfe der Gaußfunktion

i

Die Gauß- oder floor-Funktion ${\displaystyle [\mathrm{X}]:ℝ\to ℝ}$ haben wir in [4.2.15] eingeführt: ${\displaystyle [x]=\max \{n\in \mathbb{Z}|n\le x\}}$.

können wir diese Nummerierung durch eine Funktion erzeugen:

${\displaystyle f:\mathbb{N}\to \mathbb{Z}}$ gegeben durch

ist bijektiv und ${\displaystyle g:\mathbb{Z}\to \mathbb{N}}$ mit

ist die Umkehrfunktion.

Zum Beweis reicht es nach [4.7.2] zu zeigen, dass sich f und g in ihrer Wirkung gegenseitig aufheben:

• Für ${\displaystyle n\in {\mathbb{Z}}^{\ge 0}}$ ist ${\displaystyle f\circ g(n)={(-1)}^{2n}[\frac{2n+1}{2}]=[n+\frac{1}{2}]=n}$.
• Für ${\displaystyle n\in {\mathbb{Z}}^{<0}}$ ist ${\displaystyle f\circ g(n)={(-1)}^{-2n-1}[\frac{-2n}{2}]=-[-n]=n}$.
• Ist ${\displaystyle n\in \mathbb{N}}$ gerade, etwa ${\displaystyle n=2k}$, so ist ${\displaystyle g\circ f(n)=g({(-1)}^{2k}[\frac{2k+1}{2}])=g([k+\frac{1}{2}])=g(k)=2k=n}$.
• Ist ${\displaystyle n\in \mathbb{N}}$ ungerade, etwa ${\displaystyle n=2k-1}$, so ist ${\displaystyle g\circ f(n)=g({(-1)}^{2k-1}[\frac{2k}{2}])=g(-k)=2k-1=n}$.

Bemerkung:  

Beweis:  

1. ►  Falls ${\displaystyle A=\varnothing }$, ist nichts zu zeigen. Sei also ${\displaystyle A\ne \varnothing }$. Wir bilden A nun bijektiv auf einen fortlaufenden Abschnitt ${\displaystyle \{\mathrm{1,}\dots ,k\}}$ ab, wobei wir zunächst die Länge k dieses Abschnitts benötigen. Dazu "zählen" wir die Elemente von A mit Hilfe ihrer Indikatorfunktion

i

Die Indikatorfunktion (auch charakteristische Funktion) einer Menge A, ${\displaystyle {\mathrm{\chi }}_A:A\to ℝ}$ haben wir in [4.2.15] eingeführt: ${\displaystyle {\mathrm{\chi }}_A(x)=\{\begin{array}{l}\mathrm{1,}\text{falls}x\in A\hfill \\ \mathrm{0,}\text{falls}x\notin A\hfill \end{array}}$

${\displaystyle {\mathrm{\chi }}_A}$ und setzen

Da ${\displaystyle A\ne \varnothing }$, ist ${\displaystyle k\ge 1}$. Für ${\displaystyle A=\{\mathrm{2,3}\}\subset \{\mathrm{0,1,2,3}\}}$ z.B. ist

Auf ähnliche Weise definieren wir nun die Funktion ${\displaystyle g:A\to \{\mathrm{1,}\dots ,k\}}$ durch

Da ${\displaystyle A\ne \varnothing }$, besitzt A ein kleinstes Element ${\displaystyle \min A}$, wobei offensichtlich ${\displaystyle g(\min A)=1}$ ist. Ferner hat man

d.h. ${\displaystyle g(i+1)}$ entsteht aus ${\displaystyle g(i)}$ durch Addition von 1 oder 0, also ist insbesondere ${\displaystyle g(i)\le g(i+1)}$. Außerdem ist ${\displaystyle g(i)\le i\le k}$, also sind alle Werte von g natürliche Zahlen zwischen 1 und k, liegen daher im angegebenen Bildbereich.

Wir zeigen jetzt die Bijektivität von g:

• Verschiedene Elemente aus A haben verschiedene Bilder (also besitzt jedes Bild auch höchstens ein Urbild):
  Sind i und j zwei verschiedene Elemente aus A, etwa ${\displaystyle i<j}$, so ist
   
  ${\displaystyle g(i)\le g(j-1)<g(j-1)+1=g(j-1)+{\mathrm{\chi }}_A(j)=g(j)}$.
   
• Jedes ${\displaystyle j\in \{\mathrm{1,}\dots ,k\}}$ hat mindestens ein Urbild:
  Sei anderenfalls j das kleinste Element von ${\displaystyle \{\mathrm{1,}\dots ,k\}}$ ohne Urbild. Da 1 ein Urbild hat, nämlich ${\displaystyle \min A}$, ist ${\displaystyle j>1}$ und ${\displaystyle j-1\in \{\mathrm{1,}\dots ,k-1\}}$ hat ein Urbild in A, etwa ${\displaystyle j-1=g(r)}$. Wäre ${\displaystyle A\subset \{\mathrm{0,}\dots ,r\}}$, so wäre
   
  ${\displaystyle k={\mathrm{\chi }}_A(0)+\dots +{\mathrm{\chi }}_A(n)={\mathrm{\chi }}_A(0)+\dots +{\mathrm{\chi }}_A(r)=g(r)=j-1\le k-1}$.
   
  Daher ist die Restmenge ${\displaystyle A\text{}\{\mathrm{0,}\dots ,r\}\ne \varnothing }$ und für ihr kleinstes Element ${\displaystyle s>r}$ hat man:
   
  ${\displaystyle g(s)={\mathrm{\chi }}_A(0)+\dots +{\mathrm{\chi }}_A(r)+\underset{=1}{\underbrace{{\mathrm{\chi }}_A(r+1)+\dots +{\mathrm{\chi }}_A(s)}}=g(r)+1=j-1+1=j}$.
   
  j hat also ein Urbild, nämlich s - Widerspruch!

Mit g ist auch die Funktion h gegeben durch ${\displaystyle h(n)≔g^{-1}(n+1)}$ eine Bijektion, und zwar von ${\displaystyle \{\mathrm{0,}\dots ,k-1\}\to A}$. ${\displaystyle A}$ ist somit endlich.

2. ►  Sei A eine nicht-endliche Teilmenge von ${\displaystyle \mathbb{N}}$. Zunächst bilden wir A bijektiv auf ${\displaystyle {\mathbb{N}}^{\ast }}$ ab und bemühen dazu noch einmal die Indikatorfunktion ${\displaystyle {\mathrm{\chi }}_A}$. Für ${\displaystyle g:A\to {\mathbb{N}}^{\ast }}$ gegeben durch

Die Umkehrbarkeit von g garantiert nun, dass auch ${\displaystyle h:\mathbb{N}\to A}$ gegeben durch

bijektiv ist. A ist damit abzählbar.

Bemerkung:  

Beweis:  

1. ►  Für ${\displaystyle A=\varnothing }$ ist nichts zu zeigen. Ist A nicht-leer, so ist auch M nicht-leer. Gemäß Voraussetzung gibt es ein ${\displaystyle n\in \mathbb{N}}$ und eine Bijektion ${\displaystyle f:\{\mathrm{0,}\dots ,n\}\to M}$. Nach [4.8.16] ist ${\displaystyle f^{-1}(A)}$ eine endliche Teilmenge von ${\displaystyle \{\mathrm{0,}\dots ,n\}}$, es gibt daher für ein geeignetes ${\displaystyle k\in \mathbb{N}}$ eine Bijektion ${\displaystyle h:\{\mathrm{0,}\dots ,k\}\to f^{-1}(A)}$. Dann ist aber ${\displaystyle f\circ h}$ eine umkehrbare Funktion von ${\displaystyle \{\mathrm{0,}\dots ,k\}\to A}$, ${\displaystyle A}$ also endlich.

2. ►  Wir betrachten o.E. nur den Fall ${\displaystyle A\ne \varnothing }$. Sei ${\displaystyle f:\mathbb{N}\to M}$ eine Abzählung von M. Nach [4.8.17] ist ${\displaystyle f^{-1}(A)}$ eine (nicht-leere) endliche oder eine abzählbare Teilmenge von ${\displaystyle \mathbb{N}}$.

Im ersten Fall gibt es eine Bijektion ${\displaystyle h:\{\mathrm{0,}\dots ,n\}\to f^{-1}(A)}$. Die bijektive Funktion ${\displaystyle f\circ h}$ belegt dann die Endlichkeit von A.
Im zweiten Fall existiert eine Bijektion ${\displaystyle h:\mathbb{N}\to f^{-1}(A)}$. ${\displaystyle f\circ h}$ belegt hier, dass A abzählbar ist.

Bemerkung:  Für jedes ${\displaystyle i\in \mathbb{N}}$ sei ${\displaystyle A_i}$ eine endliche, nicht-leere Menge. Sind die Mengen ${\displaystyle A_i}$ paarweise disjunkt, so ist die Menge

abzählbar.

Beweis:  Zunächst gibt es nach Voraussetzung zu jedem ${\displaystyle i\in \mathbb{N}}$ ein ${\displaystyle n_i\in \mathbb{N}}$ und eine Bijektion

Setzen wir für ein ${\displaystyle x\in A}$, also ${\displaystyle x\in A_i}$ für genau ein i

${\displaystyle f(x)≔n_0+\dots +n_{i-1}+i+g_i^{-1}(x)}$,

i

Für ${\displaystyle i=0}$ existiert der Ausdruck ${\displaystyle n_0+\dots +n_{i-1}}$ nicht. Wir setzen in diesem Fall: ${\displaystyle n_0+\dots +n_{-1}=0}$ und ${\displaystyle n_0-\dots -n_{-1}=0}$.

so ist die dadurch gegebene Funktion ${\displaystyle f:A\to \mathbb{N}}$ umkehrbar. Die Umkehrfunktion ist die Funktion ${\displaystyle g:\mathbb{N}\to A}$, gegeben durch

Zum Beweis zeigen wir wieder, dass sich f und g in ihrer Wirkung gegenseitig aufheben:

• Für ein ${\displaystyle n\in \mathbb{N}}$ hat man:
   
  ${\displaystyle \begin{array}{ll}f(g(n))\hfill & =n_0+\dots +n_{i^{\ast }-1}+i^{\ast }+g_{i^{\ast }}^{-1}(g_{i^{\ast }}(n-n_0-\dots -n_{i^{\ast }-1}-i^{\ast }))\hfill \\ \hfill & =n_0+\dots +n_{i^{\ast }-1}+i^{\ast }+n-n_0-\dots -n_{i^{\ast }-1}-i^{\ast }\hfill \\ \hfill & =n.\hfill \end{array}}$
   
• Sei nun ${\displaystyle x\in A}$, etwa ${\displaystyle x\in A_i}$. Da ${\displaystyle 0\le g_i^{-1}(x)\le n_i}$ hat man zunächst
   
  ${\displaystyle n_0+\dots +n_{i-1}+i\le n_0+\dots +n_{i-1}+i+g_i^{-1}(x)<n_0+\dots +n_i+i+1}$,
   
  womit gezeigt ist, dass das zu ${\displaystyle n_0+\dots +n_{i-1}+i+g_i^{-1}(x)}$ gehörige ${\displaystyle i^{\ast }}$ identisch mit i ist. Damit gilt jetzt:
   
  ${\displaystyle \begin{array}{ll}g(f(x))\hfill & =g(n_0+\dots +n_{i-1}+i+g_i^{-1}(x))\hfill \\ \hfill & =g_i(n_0+\dots +n_{i-1}+i+g_i^{-1}(x)-n_0-\dots -n_{i-1}-i)\hfill \\ \hfill & =g_i(g_i^{-1}(x))\hfill \\ \hfill & =x.\hfill \end{array}}$

Bemerkung:  

Beweis:  Wir zerlegen ${\displaystyle \mathbb{Q}}$ in abzählbar viele endliche Mengen. Bei der Darstellung von Brüchen darf man o.E. annehmen, dass alle Nenner positiv sind und nur maximal gekürzte Bruchdarstellungen vorkommen, also:

Wenn wir für den Augenblick den Bruch ${\displaystyle \frac{n}{m}}$ als Zahlenpaar ${\displaystyle (n,m)\in \mathbb{Z}\times {\mathbb{N}}^{\ast }}$ schreiben, haben wir die Möglichkeit, ihn als Gitterpunkt der Zeichenebene zu sehen.

So sind etwa die auf den roten Diagonalen liegenden Brüche durch die Paare (−4,1), (−3,2), (−2,3), (−1,4), (0,5), (1,4), (2,3), (3,2) und (4,1) gegeben. Addiert man nun bei diesen Paaren die Beträge der Koordinaten, also z.B. ${\displaystyle \left|-4\right|+\left|1\right|}$, so erhält man in allen Fällen den Wert 5! (Die genannten neun Paare sind übrigens die einzigen, die auf diese Weise den Wert 5 liefern.)

Für eine Bruchzahl ${\displaystyle x=\frac{n}{m}}$ setzen wir jetzt

Die Mengen ${\displaystyle A_i≔\{x\in \mathbb{Q}|b(x)=i\},i\in {\mathbb{N}}^{\ast }}$, sind daher endlich, nicht-leer und paarweise disjunkt. Ihre Vereinigung ist ${\displaystyle \mathbb{Q}}$. Nach dem Satz über abzählbare Vereinigungen ist ${\displaystyle \mathbb{Q}}$ somit abzählbar.

Die Zerlegungsmengen ${\displaystyle A_i}$ enthalten offensichtlich genau diejenigen teilerfremden Brüche, die auf dem i-ten Diagonalenpaar liegen. Diese Art der Aufteilung heißt Cantorsches Diagonalverfahren.

Bemerkung:  

Beweis:  Es reicht zu zeigen, dass ${\displaystyle ℝ}$ eine überabzählbare Teilmenge enthält. Wir betrachten dazu die Menge

also die Menge aller Dezimalzahlen zwischen 0 und 1, deren Nachkommastellen nur mit 0 oder 1 besetzt sind.

Die Elemente von R stehen in einem direkten Verhältnis zu den Teilmengen von ${\displaystyle {\mathbb{N}}^{\ast }}$, denn bezeichnet man für eine solche Teilmenge ${\displaystyle A\subset {\mathbb{N}}^{\ast }}$ mit ${\displaystyle x_A}$ diejenige Zahl ${\displaystyle \mathrm{0,}{x}_1{x}_2\dots \in R}$ bei der ${\displaystyle x_i=1}$ ist, genau dann wenn ${\displaystyle i\in A}$ (also z.B. ${\displaystyle x_{\left\{\mathrm{2,3,4}\right\}}=\mathrm{0,01101}}$ oder ${\displaystyle x_{\varnothing }=0}$ oder auch ${\displaystyle x_{{\mathbb{N}}^{\ast }}=\mathrm{0,1111...}=\mathrm{0,}\overline{1}}$), so ist die Funktion ${\displaystyle f:P({\mathbb{N}}^{\ast })\to R}$ gegeben durch

bijektiv. Jede Zahl ${\displaystyle \mathrm{0,}{x}_1{x}_2\dots \in R}$ besitzt nämlich genau ein Urbild, und zwar die Menge derjenigen ${\displaystyle i\in {\mathbb{N}}^{\ast }}$ mit ${\displaystyle x_i=1}$.

R ist damit nicht abzählbar, denn anderenfalls wäre auch die zu R gleichmächtige Menge ${\displaystyle P({\mathbb{N}}^{\ast })}$ abzählbar. Dies aber ist nach [4.8.13] nicht wahr.