De stelling van Cantor-Schröder-Bernstein

Naïeve verzamelingenleer: Grootte van een verzameling

De stelling van Cantor-Schröder-Bernstein

Voor twee verzamelingen \(X\) en \(Y\) zeggen we dat de cardinaliteit van \(X\) kleiner dan of gelijk is aan de cardinaliteit van \(Y\), of dat de machtigheid van \(X\) kleiner dan of gelijk aan de machtigheid van \(Y\) is, of dat \(Y\) minstens zo groot is als \(X\), of dat \(X\) niet groter is dan \(Y\), als er een injectieve functie van \(X\) naar \(Y\) bestaat. We schrijven: \(X\preccurlyeq Y\).

We zeggen dat de cardinaliteit van \(X\) kleiner dan de cardinaliteit van \(Y\) is, of dat de machtigheid van \(X\) kleiner dan de machtigheid van \(Y\) is, of dat \(Y\) groter dan \(X\) is, of dat \(X\) kleiner dan \(Y\) is, als er een injectieve functie van \(X\) naar \(Y\) bestaat, maar geen bijectie van \(X\) naar \(Y\). Met andere woorden, \(X\preccurlyeq Y\), maar \(X\ncong Y\). We schrijven: \(X\prec Y\).

Met bovenstaande definities kunnen we ook zeggen dat een verzameling \(X\) aftelbaar is als \(X\preccurlyeq \mathbb{N}\) en overaftelbaar als \(\mathbb{N}\prec X\).

Stelling van Cantor \(X\prec{\Large\wp}(\mathbb{X})\) voor elke verzameling \(X\).

De functie \(f:\; X\rightarrow {\Large\wp}(\mathbb{X}),\quad f(x)=\{x\}\) is een injectieve functie, want als \(x\neq y\), dan \(\{x\}\neq\{x\}\) en dus \(f(x)\neq f(y)\).

Stel nu dat er een bijectie \(g\; X\rightarrow {\Large\wp}(\mathbb{X})\) bestaat. Definieer \(D=\bigl\{x\in X\mid x\notin g(z)\bigl\}\). Omdat \(g\) surjectief is bestaat er een \(d\in X\) met \(g(d)=D\). Maar dan geldt: \[\begin{aligned}d\in g(d)& \text{ dan en slechts dan als }d\in D&(\text{omdat }g(d)=D)\\ &\text{ dan en slechts dan als }d\notin g(d)&(\text{wegens de definitie van}D)\end{aligned}\] Dit is een tegenspraak, zodat een bijectie \(g\) niet kan bestaan.

De volgende stelling van Cantor-Schröder-Bernstein geeft een handige manier om gelijkmachtigheid van verzamelingen aan te tonen, omdat je niet meer een bijectieve functie hoeft op te sporen tussen twee verzameling, maar het volstaat om twee injectieve functies te vinden van de ene verzameling naar de andere en vice versa.

Stelling van Cantor-Schröder-BernsteinStel \(X\) en \(Y\) zijn twee verzamelingen. Als er een injectieve functie van \(X\) naar \(Y\) bestaat en er bestaat een injectieve functie van \(Y\) naar \(X\), dan bestaat er een bijectieve functie van \(X\) naar \(Y\) en zijn de twee verzamelingen dus gelijkmachtig. In formuletaal:

Voor twee verzamelingen \(X\) en\(Y\) geldt: \(\text{Als }X\preccurlyeq Y\text{ en }Y\preccurlyeq X\text{ dan } X\cong Y\).

Stel \(X\preccurlyeq Y\) en \(Y\preccurlyeq X\). Dan zij er twee injectieve functies \(f:\;X\rightarrow Y\) en \(g\;Y\rightarrow X\). Merk op dat \(Y\cong \mathrm{im}(g)\) Om te bewijzen dat \(Y\cong X\) , is het dus voldoende te bewjzen dat \(\mathrm{im}(g)\cong X\). Nu is \(\mathrm{im}(g)\subset X\) en is de samenstelling \(g\circ f\) een injectieve functie van \(X\) naar \(\mathrm{im}(g)\). Het is dus voldoende het volgende lemma te bewijzen:

Lemma Als \(U\subset X\) en \(U\preccurlyeq X\), dan \(U\cong X\).

Het bewijs van dit lemma is tamelijk technisch en laten we achterwege.

Gevolg De open en gesloten intervallen \((0,1)\) en \([0,1]\) in \(\mathbb{R}\) zijn gelijkmachtig. In formule vorm: \((0,1)\cong [0,1]\).

De functie \(\mathrm{id}:\;(0,1)\rightarrow [0,1]\) is injectief. Definieer de functie \(\mathrm{id}:\;[0,1]\rightarrow (0,1)\) door \(f(x)=\tfrac{1}{3}(x+1)\). De functie \(f\) is ook injectief. Volgens de stelling van Cantor-Schröder-Bernstein zijn de twee intervallen dan gelijkmachtig.

\(\mathbb{R}\times \mathbb{R} \cong \mathbb{R}\).

We weten al dat \(\mathbb{R}\cong (0,1)\). Het volstaat dus om aan te tonen dat \((0,1)\times (0,1) \cong (0,1)\). Elk element \((x,y)\in (0,1)\times (0,1)\) kan in decimale ontwikkeling geschreven worden als \[(x,y)=(0.\xi_1\xi_2\xi_3\cdots, 0.\eta_1\eta_2\eta_23\cdots)\] met in elke decimale ontwikkeling een oneindig aantal cijfers ongelijk aan \(0\) (schrijf bijvoorbeeld \(1/2=0.4999\cdots\)). De functie \[f:\; (0,1)\times (0,1)\rightarrow (0,1),\quad f(x,y)=0.\xi_1\eta_1\xi_2\eta_2\xi_3\eta_3\cdots\] is injectief. Omgekeerd is de functie \[g:\;(0,1)\rightarrow (0,1)\times (0,1),\quad g(x)=(x,\tfrac{1}{2})\] ook injectief. Dus volgens de stelling van Cantor-Schröder-Bernstein: \((0,1)\times (0,1) \cong (0,1)\).