Quantità
Se vogliamo confrontare due insiemi finiti, possiamo determinare quale sia il più grande semplicemente contandone gli elementi.
Cosa possiamo dire se vogliamo invece confrontare due insiemi infiniti?
Ad esempio, è più grande l’insieme \(\mathbb{N}\) oppure l’insieme \(\mathbb{Q}\)? E che dire di \(\mathbb{Z}\) e \(\mathbb{R}\)? L’insieme di tutti i programmi che si possono scrivere in Java è più o meno grande dell’insieme \(\mathbb{N}\)?
Certamente non possiamo pensare di “contarne” gli elementi, visto che sono insiemi infiniti...
Abbiamo bisogno di una tecnica diversa
per stabilire quanti elementi contiene un insieme!
In questa immagine ci sono più punti rossi o più punti blu?
Sono disegnati in maniera disordinata 6 punti rossi a sinistra e 7 punti blu a destraQuasi tutti rispondono (correttamente) che ci sono più punti blu che rossi, perchè ci sono \(7\) punti blu e solo \(6\) punti rossi.
Sembra che, nel caso finito, per determinare se un insieme contenga più elementi di un altro bisogni contare il numero di elementi e confrontare i due numeri così ottenuti...
In questa immagine ci sono più punti rossi o più punti blu?
Sono disegnati in maniera disordinata moltissimi punti rossi a sinistra e moltissimi punti blu a destra
Quasi nessuno riesce a rispondere in poco tempo: è molto difficile contare rapidamente il numero di punti ed è molto difficile non “perdere il conto” e fare errori. Proviamo a disporre gli stessi punti in un modo diverso...
In questa immagine ci sono più punti rossi o più punti blu?
I puntini rossi sono disposti in maniera ordinata riga per riga, sotto ogni riga di puntini rossi sono disposti in corrispondenza i puntini blu
Ora è facile rispondere: ci sono più punti rossi!
La diversa disposizione ci permette di “accoppiare” gli elementi dei due insiemi (ovvero di stabilire una corrispondenza univoca) e di notare che ci sono 3 punti rossi in più.
Questo piccolo esempio mostra chiaramente che per confrontare la grandezza (in termini di quantità di elementi) di due insiemi la cosa più naturale da fare è quella di tentare di stabilire una corrispondenza biunivoca tra i due insiemi: i due insiemi hanno lo stesso numero di elementi se e solo se esiste una biezione tra di essi.
Questo metodo, non richiedendo più di “contare” il numero di elementi,
si può applicare senza alcun problema agli insiemi infiniti,
e ci porta al concetto fondamentale di cardinalità.
Cardinalità
Definizione Due insiemi \(X\) e \(Y\) hanno la stessa cardinalità se esiste una biezione \(f \colon X \to Y\).
Scriveremo \[X \approx Y ,\] oppure \[\mathopen | X \mathclose | = \mathopen | Y \mathclose |\] per indicare che \(X\) e \(Y\) hanno la stessa cardinalità.
Esercizio La relazione \(\approx\) è una relazione di equivalenza.
Definizione Un insieme è finito se e solo se è in biezione con \(\left \{ 0 , \dots , n - 1 \right \}\) per qualche \(n \in \mathbb{N}\) (dove poniamo \(\left \{ 0 , \dots , n - 1 \right \} = \emptyset\) quando \(n = 0\)).
Se \(X\) è finito ed in biezione con \(\left \langle 0, \dots, n-1 \right \rangle\) scriveremo \[\mathopen | X \mathclose | = n .\]
Un insieme che non è finito si dice infinito.
Osservazione Se \(\mathopen | X \mathclose |=n\) e \(\mathopen | Y \mathclose |=m\), allora \(\mathopen | X \times Y \mathclose |=n\cdot m\).
Se inoltre \(X\cap Y=\emptyset\), allora \(\mathopen | X\cup Y \mathclose | =n+m\).
Definizione \(X\) si inietta in \(Y\) se esiste una iniezione \(f \colon X \to Y\). In questo caso scriveremo \[X \precsim Y\] oppure \[\mathopen | X \mathclose | \leq \mathopen | Y \mathclose | .\] Scriveremo \(X \prec Y\) (oppure \(\mathopen | X \mathclose | < \mathopen | Y \mathclose |\)) quando \(X \precsim Y\) ma \(Y \not\precsim X\).
Esercizio \(\precsim\) è un preordine sugli insiemi (ossia è una relazione riflessiva e transitiva).
Osservazione Se \(X \approx Y\), allora \(X \precsim Y\) e \(Y \precsim X\). Infatti, \(X \approx Y\) se esiste una biezione \(f \colon X \to Y\): ma allora \(f\) stessa mostra anche che \(X \precsim Y\), mentre \(f^{-1} \colon Y \to X\), che è a sua volta una biezione, dimostra che \(Y \precsim X\).
Sia \(X \neq \emptyset\). Allora \(X \precsim Y\) se e solo se c’è una suriezione \(g \colon Y \to X\).
Quindi per dimostrare che \(\mathopen | X \mathclose | \leq \mathopen | Y \mathclose |\) possiamo mostrare che esiste una iniezione da \(X\) in \(Y\) oppure, equivalentemente, che esiste una suriezione da \(Y\) su \(X\).
[Dimostrazione.] Sia \(f \colon X \to Y\) iniettiva e fissiamo un arbitrario \(x_{0} \in X\). Allora possiamo definire una suriezione \(g \colon Y \to X\) ponendo \[g ( y ) = \begin{cases} f^{-1} ( y ) & \text{se } y \in f[X] = \mathopen \{f(x) \boldsymbol\mid x \in X \mathclose\} \\ x_{0} & \text{altrimenti}. \end{cases}\]
Viceversa, se \(g \colon Y \to X\) è una suriezione, allora per ogni \(x \in X\) si ha \(g^{-1}(x) \neq \emptyset\). Quindi possiamo definire una funzione \(f \colon X \to Y\) che scelga per ogni \(x \in X\) un punto in \(g^{-1}(x)\): tale funzione è necessariamente iniettiva.
Abbiamo osservato che se \(X \approx Y\), allora \(X \precsim Y\) e \(Y \precsim X\).
Dimostreremo ora che vale anche il viceversa: se \(X \precsim Y\) e \(Y \precsim X\), allora \(X \approx Y\), ovvero \(\approx\) è la relazione d’equivalenza indotta dal preordine \(\precsim\).
Questo fatto non è per nulla ovvio:
Esempio
Siano \(X = [0;1]\) e \(Y = (0;1)\). Allora si ha che \((0;1) \precsim {[0;1]}\) perchè \((0;1) \subseteq [0;1]\). Inoltre, la funzione
\(f \colon [0;1] \to (0;1)\), \(x \mapsto \frac{x+1}{3}\)
è chiaramente iniettiva e dimostra che \([0;1] \precsim (0;1)\).
Tuttavia, non è così immediato vedere come si possa definire una biezione tra \([0;1]\) e \((0;1)\).
(Dove mandiamo gli estremi \(0\) e \(1\) di \(X\)?)
Il teorema di Cantor-Schröder-Bernstein
La relazione d’equivalenza associata a \(\precsim\) è proprio \(\approx\).
Se \(X \precsim Y\) e \(Y \precsim X\) allora \(X \approx Y\).
In altre parole \(\mathopen | X \mathclose | \leq \mathopen | Y \mathclose | \leq \mathopen | X \mathclose |\) se e solo se \(\mathopen | X \mathclose | = \mathopen | Y \mathclose |\).
Idea della dimostrazione Siano \(f \colon X \to Y\) e \(g \colon Y \to X\) iniezioni. Definiamo
| \[X_{0}\] | \[=\] | \[X\] |
|---|---|---|
| \[Y_{0}\] | \[=\] | \[Y\] |
| \[X_{n+1}\] | \[=\] | \[g[Y_{n}]\] |
| \[Y_{n+1}\] | \[=\] | \[f[X_{n}]\] |
Siano \(X_{\infty} = \bigcap_{n \in \mathbb{N}} X_{n}\) e \(Y_{\infty} = \bigcap_{n \in \mathbb{N}} Y_{n}\). Definiamo
\(A = X_{\infty} \cup \bigcup\nolimits_{i \in \mathbb{N}} (X_{2i} \setminus X_{2i+1})\) e \(B = \bigcup\nolimits_{i \in \mathbb{N}} (Y_{2i} \setminus Y_{2i+1})\).
(continua)
Idea della dimostrazione. Si verifica che (la restrizione ad \(A\) di) \(f\) è una biezione tra \(A\) e \(Y\setminus B\), mentre (la restrizione a \(B\) di) \(g\) è una biezione tra \(B\) e \(X \setminus A\). Allora la funzione
\(h \colon X \to Y\), \(x \mapsto \begin{cases} f(x) & \text{se } x \in A \\ g^{-1}(x) & \text{se } x \in X \setminus A \end{cases}\)
è una biezione.
Negli approfondimenti (parte finale delle slide) si trova una dimostrazione completa e dettagliata del teorema di Cantor-Schröder-Bernstein.
Se \(X\subseteq Y\) e \(Y\precsim X\) allora \(X\approx Y\).
Se \(X\subseteq Y\) allora l’iniezione \(f \colon X \to Y\) definita da \(f(x) = x\) per ogni \(x \in X\) mostra che \(X\precsim Y\). Dall’ipotesi \(Y \precsim X\) e dal teorema di Cantor-Schröder-Bernstein segue che \(X\approx Y\).
\(X\) è infinito se e solo se \(\mathbb{N} \precsim X\). In particolare \(\mathbb{N}\) è il più piccolo insieme infinito: se \(X\) è infinito \(\mathopen | \mathbb{N} \mathclose | \leq \mathopen | \mathopen | X \mathclose | \mathclose |\).
Dimostrazione. Se \(\mathbb{N} \precsim X\), \(X\) è chiaramente infinito poichè non esiste una suriezione di \(\{0,\dots,n-1\}\) con \(\mathbb{N}\), e quindi a maggior ragione con \(X\), per ogni \(n\in\mathbb{N}\).
(continua)
Dimostrazione. Viceversa, assumiamo che \(X\) sia infinito. Siccome in particolare \(X \neq \emptyset\) (altrimenti \(X\) sarebbe finito), esiste qualche \(a_{0} \in X\). Ma poichè \(X\) è infinito, anche \(X \setminus \{ a_{0} \} \neq \emptyset\) (altrimenti \(X=\{a_{0}\}\) sarebbe finito), per cui esiste \(a_{1} \in X \setminus \{ a_{0} \}\). Poichè \(X\) è infinito, anche \(X \setminus \{ a_{0}, a_{1} \} \neq \emptyset\) (altrimenti \(X=\{a_{0},a_{1}\}\) sarebbe finito), per cui esiste \(a_{2} \in X \setminus \{ a_{0}, a_{1} \}\). Più in generale, se abbiamo già definito \(a_{0}, \dotsc, a_{n}\in X\), possiamo ancora usare il fatto che \(X\) sia infinito per osservare che \(X \setminus \{ a_{0}, \dotsc, a_{n} \} \neq \emptyset\) (altrimenti \(X = \{ a_{0}, \dotsc, a_{n} \}\) sarebbe finito), per cui esiste \(a_{n+1} \in X \setminus \{ a_{0}, \dotsc, a_{n} \} \neq \emptyset\). Proseguendo in questo modo, costruiamo una successione infinita \(a_{0}, a_{1}, \dotsc\) di elementi di \(X\) a due a due distinti. Otteniamo quindi la funzione iniettiva
\(f \colon \mathbb{N} \to X\), \(n \mapsto a_{n}\).
Due insiemi finiti sono in biezione se e solo se hanno lo stesso numero di elementi. In particolare, non esiste alcuna iniezione (quindi nemmeno una biezione) tra un insieme finito e un suo sottoinsieme proprio.
Questo segue dal
Principio dei cassetti Se \(m,n \in \mathbb{N}\) con \(m > n\), in qualunque modo si dispongano \(m\) oggetti in \(n\) cassetti, ci sarà almeno un cassetto che contiene più di un oggetto.
Una riformulazione più “matematica” è la seguente:
Sia \(X\) un insieme finito con \(m\) elementi e \(Y\) un insieme finito con \(n\) elementi. Se \(m > n\), allora per ogni \(f \colon X \to Y\) esistono \(x,x' \in X\) distinti tali che \(f(x) = f(x')\).
Nel nostro caso: se \(X\) è un qualunque insieme finito con \(m\) elementi e \(Y\) un suo sottoinsieme proprio, allora il numero \(n\) di elementi di \(Y\) è strettamente minore di \(m\): quindi non ci può essere nessuna iniezione (e tantomeno una biezione) \(f \colon X \to Y\).
Al contrario, la funzione \(f\) definita da \(f(n) = n+1\) è una biezione tra \(\mathbb{N}\) ed il suo sottoinsieme proprio \(\{ n \in \mathbb{N} \mid n > 0 \}\) (più in generale: \(\mathbb{N}\) è in biezione con ogni suo sottoinsieme infinito). Questa è una caratteristica degli insiemi infiniti:
Proposizione Un insieme \(X\) è infinito se e solo se esiste \(Y \subset X\) tale che \(Y \approx X\).
Se \(X\) ha \(n\) elementi e \(Y \subset X\), non si può avere \(Y \approx X\) perchè \(Y\) ha al più \(n-1\) elementi. Se \(X\) è infinito, allora esiste una iniezione \(j \colon \mathbb{N} \to X\). Sia \(Y = X \setminus \{ j(0) \}\). Allora \(Y \subset X\) e si ottiene una biezione \(f \colon X \to Y\) ponendo \[f(x) = \begin{cases} x & \text{se } x \notin \mathrm{rng}(j) \\ j(n+1) & \text{se } x = j(n). \end{cases}\]
Un insieme si dice numerabile se è in biezione con \(\mathbb{N}\), ossia se la sua cardinalità è la più piccola tra quelle infinite.
Osservazione In particolare se \(f \colon \mathbb{N} \to X\) è suriettiva, allora \(X\) è finito oppure numerabile.
(Infatti, dall’esistenza di \(f\) segue che \(X \precsim \mathbb{N}\). Se \(X\) è infinito, si ha anche \(\mathbb{N} \precsim X\), per cui \(X \approx \mathbb{N}\) per il teorema di Cantor-Schröder-Bernstein.)
Per dimostrare che un insieme \(X\) è numerabile è sufficiente enumerare \(X\), ovvero elencare i suoi elementi in una successione infinita \[x_{0}, x_{1}, x_{2}, \dotsc, x_{n}, \dotsc\] in cui ogni elemento di \(X\) compaia una e una sola volta. Infatti, una tale lista definisce in realtà la biezione
\(f \colon \mathbb{N} \to X\), \(n \mapsto x_{n}\).
Esempio
La funzione \(f \colon \mathbb{Z} \to \mathbb{N}\) definita da \[f(z) = \begin{cases} 2z & \text{se } z \geq 0 \\ -2z-1 & \text{se } z < 0 \end{cases}\] è una biezione. Quindi \(\mathbb{Z}\) è numerabile.
Alternativamente, si può enumerare \(\mathbb{Z}\) in questo modo: \[0, -1, 1, -2, 2, -3, 3, \dotsc, -n, n, \dotsc\]
Esercizio Verificare che la biezione indotta da tale enumerazione è la funzione inversa della biezione \(f\) definita nell’esempio.
\(\mathbb{N} \times \mathbb{N} \approx \mathbb{N}\)
Dimostriamo ora che: \(\mathbb{N} \times \mathbb{N} \approx \mathbb{N}\).
Dimostrazione 1
L’enumerazione diagonale o triangolare è ottenuta enumerando \(\mathbb{N}^2\) secondo l’ordinamento \[( x , y ) \lhd_{T} ( x' , y' ) \mathbin{ \Leftrightarrow} x + y < x' + y' \vee [ x + y = x' + y' \wedge x < x' ] ,\]
Dimostrazione 2
L’enumerazione quadrata è ottenuta enumerando \(\mathbb{N}^2\) secondo l’ordinamento \[\begin{gathered}
( x , y ) \lhd_{Q} ( x' , y' ) \mathbin{ \Leftrightarrow } \bigl ( \max ( x , y ) < \max ( x' , y' )
\\
\vee [ \max ( x , y ) = \max ( x' , y' ) \wedge ( x < x' \vee [ x = x' \wedge y < y' ] )] \bigr ) ,\end{gathered}\]
Abbiamo già dimostrato che la funzione
\(f \colon \mathbb{N} \times \mathbb{N} \to \mathbb{N}\), \(( n , m ) \mapsto 2^n \cdot ( 2 m + 1 ) - 1\)
è una biezione.
Osservazione Più in generale si dimostra che, a differenza di ciò che succede per gli insiemi finiti, per ogni insieme \(X\) infinito si ha \(\mathopen | X\times X \mathclose |= \mathopen | X \mathclose |\). La dimostrazione di questo risultato però non è per nulla banale.
Corollario \(\mathopen | \mathbb{N}^n \mathclose | = \mathopen | \mathbb{N} \mathclose |\) per ogni \(n \geq 1\). Analogamente, \(\mathopen | X^n \mathclose | = \mathopen | X \mathclose |\) per ogni \(X\) infinito.
Vediamo come si costruisce una biezione tra \(\mathbb{N}^3\) e \(\mathbb{N}\). Sia \(h_{2} \colon \mathbb{N}^2 \to \mathbb{N}\) una qualunque biezione. Definiamo \(h_{3} \colon \mathbb{N}^3 \to \mathbb{N}\) ponendo \[h_{3}(n,m,k) = h_{2}(h_{2}(n,m),k)\] Si verifica facilmente che la funzione \(h_{3}\) è una biezione. Infatti, \(h_{3}\) si può scrivere come \(h_{2}\circ (h_{2}\times \mathrm{Id})\), dove \(\mathrm{Id}\) è la funzione identità su \(\mathbb{N}\).
Più in generale, per ogni \(n > 2\) la funzione
\(h_{n} \colon \mathbb{N}^n \to \mathbb{N}\), \((x_{1}, \dotsc , x_{n}) \mapsto h_{2}(h_{2}(\dotsc h_{2}(h_{2}(x_{1}, x_{2}),x_{3}), \dotsc ),x_{n})\)
è una biezione.
Si può verificare che \(h_{n+1}=h_{2}\circ(h_{n}\times \mathrm{Id})\) per ogni \(n\in\mathbb{N}\).
\(\mathbb{Q}\) è numerabile, ovvero \(\mathopen | \mathbb{Q} \mathclose | = \mathopen | \mathbb{N} \mathclose |\)
\(\mathopen | \mathbb{N} \mathclose | \leq \mathopen | \mathbb{Q} \mathclose |\) dato che \(\mathbb{N}\subseteq \mathbb{Q}\).
La funzione
\(g \colon \mathbb{Z} \times \mathbb{N} \to \mathbb{Q}\), \((n,m)\mapsto \frac{n}{m+1}\)
è una suriezione perchè ogni numero razionale \(q\) si può sempre rappresentare come rapporto tra due numeri interi \(n/(m+1)\) con denominatore \((m+1)\) strettamente positivo. Perciò \(\mathopen | \mathbb{Q} \mathclose | \leq \mathopen | \mathbb{Z} \times \mathbb{N} \mathclose |\).
Attenzione! \(g\) non è iniettiva, ad esempio \(g(-2,2)=-\frac{2}{3}=g(-4,5)\).
Fatto cruciale Poichè il prodotto di due biezioni è ancora una biezione, se \(\mathopen | X \mathclose | = \mathopen | Y \mathclose |\) e \(\mathopen | Z \mathclose | = \mathopen | W \mathclose |\) allora \(\mathopen | X \times Z \mathclose | = \mathopen | Y \times W \mathclose |\).
Quindi \(\mathopen | \mathbb{N} \mathclose | \leq \mathopen | \mathbb{Q} \mathclose | \leq \mathopen | \mathbb{Z}\times\mathbb{N} \mathclose | = \mathopen | \mathbb{N}\times\mathbb{N} \mathclose | = \mathopen | \mathbb{N} \mathclose |\), da cui \(\mathopen | \mathbb{N} \mathclose | = \mathopen | \mathbb{Q} \mathclose |\).
\(\mathbb{N}^{< \mathbb{N}}\) è numerabile
Ricordiamo che \(\mathbb{N}^{< \mathbb{N}}\) è l’insieme di tutte le sequenze finite di numeri naturali, ovvero \(\mathbb{N}^{< \mathbb{N}} = \bigcup_{n \in \mathbb{N}} \mathbb{N}^n\) (con la convenzione che \(\mathbb{N}^0 = \{ \varepsilon \}\), dove \(\varepsilon\) è l’unica sequenza vuota).
Proposizione \(\mathopen | \mathbb{N}^{< \mathbb{N}} \mathclose | = \mathopen | \mathbb{N} \mathclose |\).
Per il teorema di Cantor-Schröder-Bernstein, per ottenere una biezione tra \(\mathbb{N}^{< \mathbb{N}}\) ed \(\mathbb{N}\) è sufficiente dimostrare che \(\mathbb{N} \precsim \mathbb{N}^{< \mathbb{N}}\) e \(\mathbb{N}^{< \mathbb{N}}\precsim \mathbb{N}\).
La funzione
\(g \colon \mathbb{N} \to \mathbb{N}^{< \mathbb{N}}\), \(n \mapsto \langle n \rangle\)
è chiaramente iniettiva, quindi \(\mathbb{N} \precsim \mathbb{N}^{< \mathbb{N}}\).
Per definire una funzione iniettiva \(f \colon \mathbb{N}^{< \mathbb{N}} \to \mathbb{N}\) procediamo nel modo seguente:
Sia \(\langle \boldsymbol{p}_{n} \rangle_{n \in \mathbb{N}}\) l’enumerazione di tutti i numeri primi, cioè \(\boldsymbol{p}_{0} = 2\), \(\boldsymbol{p}_{1} = 3\), \(\boldsymbol{p}_{2} = 5\), …
Data una sequenza non vuota \(s = \langle m_{0} , m_{1} , \dots , m_{k} \rangle \in \mathbb{N}^{<\mathbb{N}}\) costruiamo il numero non nullo
\(f ( s ) = \boldsymbol{p}_{0}^{m_{0} + 1} \cdot \boldsymbol{p}_{1}^{m_{1} + 1 } \cdots \boldsymbol{p}_{k}^{m_{k} + 1}\)
e poniamo \(f(\varepsilon) = 0\). Per la fattorizzazione unica, la funzione \(f \colon \mathbb{N}^{< \mathbb{N}} \to \mathbb{N}\) è iniettiva.
Osservazione Se avessimo posto semplicemente \(f ( s ) = \boldsymbol{p}_{0}^{m_{0} } \cdot \boldsymbol{p}_{1}^{m_{1} } \cdots \boldsymbol{p}_{k}^{m_{k} }\) la funzione non sarebbe stata iniettiva perchè ad esempio \[f(\langle 0\rangle) = 2^0 = 1 = 2^0 \cdot 3^0 = f(\langle 0,0\rangle) .\]
Sequenze finite Più in generale, dato un insieme non vuoto \(X\) indichiamo con \(X^{< \mathbb{N}}\) l’insieme delle sequenze finite \(s = \langle x_{0}, \dotsc, x_{n} \rangle\) di elementi di \(X\). Più precisamente \(X^{<\mathbb{N} } = \bigcup_{n \in \mathbb{N}} X^n\), con la solita convenzione \(X^0 = \{ \varepsilon \}\), dove \(\varepsilon = \langle \rangle\) è la sequenza vuota. Abbiamo visto che se \(X\) è infinito allora \(X^{< \mathbb{N}}\) è infinito, poichè il suo sottoinsieme \(X^1 = \{ \langle x \rangle \mid x \in X \}\) è in biezione con \(X\), e quindi è esso stesso infinito.
L’insieme \(X^{< \mathbb{N}}\) è infinito (indipendentemente dal fatto che \(X\) sia finito o infinito).
Infatti, dato qualunque \(a \in X\) si può considerare l’iniezione
\(f \colon \mathbb{N} \to X^{< \mathbb{N}}\), \(n \mapsto \langle \underbrace{a,a, \dotsc, a}_{n \text{ volte}} \rangle\).
Dimostrare che se \(X\) è finito allora per ogni \(n \in \mathbb{N}\) l’insieme \(X^n\) è finito. Quanti elementi ha \(X^n\)?
Cardinalità dell’insieme delle parti \(\mathscr{P}(X)\) Sia \(X\) un insieme non vuoto. Ricordiamo che \(2^X\) è l’insieme di tutte le funzioni da \(X\) in \(\{ 0,1 \}\), e che è in biezione con l’insieme delle parti \(\mathscr{P}(X)\) di \(X\). In particolare, ne segue che se \(X\) è finito e ha \(n\) elementi allora \(\mathscr{P}(X)\) ha \(2^n\) elementi, da cui \[\mathopen | X \mathclose | < \mathopen | \mathscr{P}(X) \mathclose |.\] Dimostreremo ora che questa proprietà continua a valere anche quando \(X\) è infinito.
Il teorema di Cantor Chiaramente \(X \precsim \mathscr{P}(X)\) poichè \(X \to \mathscr{P}(X)\), \(x \mapsto \left \{ x \right \}\) è iniettiva.
Non esiste alcuna suriezione da \(X\) su \(\mathscr{P} ( X )\). Quindi \(\mathscr{P} ( X ) \not \precsim X\).
Supponiamo per assurdo che esista una suriezione \(g \colon X \to \mathscr{P} ( X )\) e sia \[Y = \mathopen \{ x \in X \boldsymbol\mid x \notin g ( x ) \mathclose\} .\] Fissiamo un \(\bar{x} \in X\) tale che \(g ( \bar{x} ) = Y\). Allora
\(\bar{x} \in Y\) se e solo se \(\bar{x} \notin\) \(g ( \bar{x} )\) \(= Y\) ,
contraddizione.
Quindi per ogni insieme \(X\) non vuoto si ha \(\mathopen | X \mathclose | < \mathopen | \mathscr{P}(X) \mathclose |\).
Alcune osservazioni
In particolare \(\mathscr{P} ( \mathbb{N} )\) non è in biezione con \(\mathbb{N}\), ovvero \(\mathopen | \mathbb{N} \mathclose | < \mathopen | \mathscr{P}(\mathbb{N}) \mathclose |\), e lo stesso vale quando \(\mathbb{N}\) viene sostituito da \(\mathbb{Z}\), \(\mathbb{Q}\), e così via.
Inoltre, vale il fatto seguente:
Ogni iniezione (suriezione, biezione) \(f \colon X \to Y\) induce in maniera canonica la funzione iniettiva (suriettiva, biettiva)
\(\mathscr{P} ( X ) \to \mathscr{P} ( Y )\), \(A \mapsto f [ A ] = \left \{ f ( x ) \boldsymbol\mid x \in A \right\}\)
Di conseguenza \[\mathopen | \mathscr{P}(\mathbb{N}) \mathclose | = \mathopen | \mathscr{P}(\mathbb{Z}) \mathclose | = \mathopen | \mathscr{P}(\mathbb{Q}) \mathclose |.\]
\(\mathopen | \mathbb{N} \mathclose | < \mathopen | \mathbb{R} \mathclose |\)
Teorema \(\mathopen | \mathbb{R} \mathclose | = \mathopen | \mathscr{P}(\mathbb{N}) \mathclose |\). In particolare, \(\mathopen | \mathbb{N} \mathclose | = \mathopen | \mathbb{Q} \mathclose | < \mathopen | \mathbb{R} \mathclose |\).
Poichè \[\mathopen | 2^\mathbb{N} \mathclose | = \mathopen | \mathscr{P}(\mathbb{N}) \mathclose | = \mathopen | \mathscr{P}(\mathbb{Q}) \mathclose | ,\] è sufficiente dimostrare che \(2^\mathbb{N} \precsim \mathbb{R}\) e \(\mathbb{R} \precsim \mathscr{P}(\mathbb{Q})\).
Data \(f \in 2^\mathbb{N}\), sia \(x_{f}\) il numero reale con espansione decimale \[0, n_{0} n_{1} n_{2} \dotsc\] dove \(n_{i} = f(i)+1\). Chiaramente \(x_{f} \in (0;1)\) e se \(f,f' \in 2^\mathbb{N}\) sono distinte allora \(x_{f} \neq x_{f'}\). Quindi la funzione
\(2^\mathbb{N} \to (0;1)\), \(f \mapsto x_{f}\)
dimostra che \(2^\mathbb{N} \precsim (0;1) \subseteq \mathbb{R}\).
Per dimostrare che \(\mathbb{R} \precsim \mathscr{P}(\mathbb{Q})\), utilizziamo il seguente
Fatto I razionali sono densi in \(\mathbb{R}\), ovvero se \(x,y \in \mathbb{R}\) sono tali che \(x < y\) allora esiste \(q \in \mathbb{Q}\) tale che \[x < q < y.\]
Consideriamo la funzione
\(\mathbb{R} \to \mathscr{P}(\mathbb{Q})\), \(r \mapsto A_{r} = \{ q \in \mathbb{Q} \mid q < r \}\).
Per la densità dei razionali in \(\mathbb{R}\), tale funzione è iniettiva: se \(r < r'\) allora preso \(q \in \mathbb{Q}\) tale che \(r < q < r'\) si ha che \(q \in A_{r'} \setminus A_{r}\). Quindi \(\mathbb{R} \precsim \mathscr{P}(\mathbb{Q})\).
Questo conclude la dimostrazione del teorema, ovvero del fatto che \[\mathbb{R} \approx \mathscr{P}(\mathbb{N}) .\]
Alcune osservazioni
Si ricordi che nella prima parte abbiamo in realtà dimostrato che \(2^\mathbb{N} \precsim (0;1)\). Poichè ora abbiamo anche che \(\mathbb{R} \approx \mathscr{P}(\mathbb{N}) \approx 2^\mathbb{N}\), questo vuol dire che \(\mathbb{R} \precsim (0;1)\). Ma poichè \((0;1) \subseteq \mathbb{R}\), si ha che \[\mathbb{R} \approx (0;1),\] ovvero che l’intera retta reale \(\mathbb{R}\) e l’intervallo aperto \((0;1)\) hanno lo stesso numero di punti.
Questo fatto può essere anche dimostrato geometricamente utilizzando la proiezione stereografica.
Corollario Per ogni \(a,b \in \mathbb{R}\) con \(a < b\) si ha che \[\mathbb{R} \approx [a;b] \approx [a;b) \approx (a;b] \approx (a;b).\]
Alcune osservazioni
Poichè \(\mathbb{R}\) è un insieme infinito, si ha che \[\mathbb{R}^2 = \mathbb{R} \times \mathbb{R} \approx \mathbb{R} ,\] ovvero che la retta reale e il piano cartesiano hanno lo stesso numero di punti.
C’è anche una semplice suriezione di \([0;1]\) su \([0;1]\times[0;1]\) che permette di ottenere in modo esplicito lo stesso risultato: per esempio la funzione che assegna (modulo la opportuna attenzione ai numeri che ammettono due espansioni decimali) al numero \(x = 0,x_{0}x_{1}x_{2}x_{3}\dotsc\) la coppia \((y,z)\) dove
\(y = 0,x_{0}x_{2}x_{4}x_{6}\dotsc x_{2i}\dotsc\) e \(z = 0,x_{1}x_{3}x_{5}x_{7}x_{9}\dotsc x_{2i+1}\dotsc\)
Utilizzando il fatto che l’iniezione \(\mathbb{R} \to \mathbb{R}^2\), \(x \mapsto (x,0)\) testimonia \(\mathbb{R} \precsim \mathbb{R}^2\), si ottiene quindi \[\mathbb{R} \precsim \mathbb{R} \times \mathbb{R} \approx [0;1] \times [0;1] \precsim [0;1] \subseteq \mathbb{R}.\]
Esercizio Dimostrare che per ogni \(n \geq 1\) si ha \(\mathbb{R}^n \approx \mathbb{R}\). Spiegare perchè da questo segue anche \([a;b] \approx [a;b]^n\) e \((a;b) \approx (a;b)^n\) per ogni \(a,b \in \mathbb{R}\) tali che \(a < b\).
Esercizio Dimostrare che se \(Y\) è un insieme infinito e \(X\) è tale che \(\mathopen | X \mathclose | \leq \mathopen | Y \mathclose |\), allora \[\mathopen | X \cup Y \mathclose | = \mathopen | X \times Y \mathclose | = \mathopen | Y \mathclose |.\]
Suggerimento. Utilizzare il fatto che, essendo \(Y\) infinito, si ha \(\mathopen | Y \times Y \mathclose | = \mathopen | Y \mathclose |\).
Esercizio Dimostrare che date due circonferenze \(C_{1} , C_{2}\) si ha \(\mathopen | C_{1} \mathclose | = \mathopen | C_{2} \mathclose |\) e che \(\mathopen | C_{1} \mathclose | = \mathopen | \mathbb{R} \mathclose |\).
Esercizio Sia \(\mathbb{N}^\mathbb{N}\) l’insieme di tutte le funzioni \(f \colon \mathbb{N} \to \mathbb{N}\).
Dimostrare che la funzione
\(F \colon \mathbb{N}^\mathbb{N} \to \mathscr{P}(\mathbb{N} \times \mathbb{N})\), \(f \mapsto \{ (n,m) \in \mathbb{N} \times \mathbb{N} \mid m = f(n) \}\)
è iniettiva.
Utilizzando quanto visto a lezione, dimostrare che \[\mathopen | \mathbb{N}^\mathbb{N} \mathclose | = \mathopen | \mathbb{R} \mathclose |.\]
Esercizio Dimostrare che gli insiemi
\(\{ f \in \mathbb{N}^\mathbb{N} \mid f \text{ è iniettiva} \}\)
e \[\{ f \in \mathbb{N}^\mathbb{N} \mid f \text{ è suriettiva} \}\] sono in biezione con \(\mathbb{N}^\mathbb{N}\).
Concludere che anche l’insieme \[\{ f \in \mathbb{N}^\mathbb{N} \mid f \text{ è biettiva} \}\] ha la stessa cardinalità di \(\mathbb{N}^\mathbb{N}\).
Esercizio Dimostrare che l’insieme di tutte le rette nel piano cartesiano è in biezione con \(\mathbb{R}\).
Esercizio Dimostrare che l’insieme delle sequenze binarie finite (ovvero l’insieme di tutte le sequenze finite di \(0\) e \(1\)) è un insieme numerabile.
Esercizio Più in generale, dimostrare che se \(X\) è finito o numerabile, allora \(X^{<\mathbb{N} }\) è numerabile.
Sia \(X\) un insieme non vuoto. Una sequenza \(s = \langle s_{0}, \dotsc , s_{n} \rangle \in X^{< \mathbb{N}}\) contiene ripetizioni se in \(s\) c’è almeno un elemento ripetuto due volte, ovvero se esistono \(0 \leq i<j \leq n\) tali che \(s_{i} = s_{j}\). Se ciò non accade diciamo che \(s\) è senza ripetizioni.
Esercizio Dimostrare che per ogni insieme \(X\) infinito, l’insieme \[\{ s \in X^{< \mathbb{N}} \mid s \text{ è senza ripetizioni} \}\] è un insieme infinito. Dimostrare anche che se \(X\) è numerabile, allora anche l’insieme delle sequenze senza ripetizioni lo è.
Esercizio Dimostrare che se invece \(X\) è finito, allora l’insieme delle sequenze \(s \in X^{< \mathbb{N}}\) senza ripetizioni è un insieme finito. (Facoltativo: quanti elementi ha?)
Esercizio Dimostrare che per ogni insieme \(X\) non vuoto, l’insieme \[\{ s \in X^{< \mathbb{N}} \mid s \text{ contiene ripetizioni} \}\] è un insieme infinito, e che se \(X\) è numerabile allora anche l’insieme delle sequenze contenenti ripetizioni lo è.
Esercizio Dimostrare che l’insieme di tutti i programmi che si possono scrivere in un dato linguaggio di programmazione è numerabile.
Il teorema di Cantor-Schröder-Bernstein
Se \(X \precsim Y\) e \(Y \precsim X\) allora \(X \approx Y\). In particolare, \(\mathopen | X \mathclose | \leq \mathopen | Y \mathclose | \leq \mathopen | X \mathclose |\) se e solo se \(\mathopen | X \mathclose | = \mathopen | Y \mathclose |\).
Dimostrazione. Siano \(f \colon X \to Y\) e \(g \colon Y \to X\) iniezioni. Definiamo \[\begin{aligned} X_{0} & = X & Y_{0} &= Y \\ X_{n+1} & = g[Y_{n} ] & Y_{n+1} & = f[X_{n}]\end{aligned}\] Per definizione di \(Y_{n+1}\), ciascuna funzione \(f \restriction X_{i} \colon X_{i} \to Y\) è iniettiva e ha range \(Y_{i+1}\), ovvero è una biezione tra \(X_{i}\) e \(Y_{i+1}\). Da questo segue che per ogni \(i \in \mathbb{N}\) la funzione \(f \restriction (X_{2i} \setminus X_{2i+1}) \colon X_{2i} \setminus X_{2i+1} \to Y\) è una funzione iniettiva il cui range è esattamente \(Y_{2i+1} \setminus Y_{2i+2}\), quindi è una biezione tra \(X_{2i} \setminus X_{2i+1}\) e \(Y_{2i+1} \setminus Y_{2i+2}\).
(continua)
Dimostrazione. Similmente, si dimostra che per ogni \(i \in \mathbb{N}\) la funzione \(g \restriction (Y_{2i} \setminus Y_{2i+1}) \colon Y_{2i} \setminus Y_{2i+1} \to X_{2i+1} \setminus X_{2i+2}\) è una biezione, per cui \(g^{-1} \restriction (X_{2i+1} \setminus X_{2i+2})\) è una biezione tra \(X_{2i+1} \setminus X_{2i+2}\) e \(Y_{2i} \setminus Y_{2i+1}\).
Siano \(X_{\infty} = \bigcap_{n \in \mathbb{N}} X_{n}\) e \(Y_{\infty} = \bigcap_{n \in \mathbb{N}} Y_{n}\). Mostriamo ora che la funzione \(f \restriction A_{\infty} \colon A_{\infty} \to Y\) ha range \(B_{\infty}\), ovvero è una biezione tra \(A_{\infty}\) e \(B_{\infty}\). Se \(x \in A_{\infty}\), allora \(x \in X_{n}\) per ogni \(n \in \mathbb{N}\), quindi per definizione di \(Y_{n+1}\) si ha \(f(x) \in Y_{n+1}\) per ogni \(n \in \mathbb{N}\), quindi \(f(x) \in \bigcap_{n \in \mathbb{N}} Y_{n} = Y_{\infty}\) (il fatto che \(f(x) \in Y_{0}\) è banale perchè \(Y_{0} = Y\)). Questo mostra che \(\mathrm{rng}(f \restriction X_{\infty}) \subseteq Y_{\infty}\). Viceversa, dato \(y \in Y_{\infty}\) allora \(y \in Y_{n +1}\) per ogni \(n \in \mathbb{N}\). In particolare, poichè \(y \in Y_{1} = f[X_{0}] = \mathrm{rng}(f)\) esiste un unico (visto che \(f\) è iniettiva) \(x \in X\) tale che \(f(x) = y\). Inoltre, poichè \(f^{-1}(Y_{n+1}) = X_{n}\), da \(f(x) = y \in Y_{n+1}\) segue \(x \in X_{n}\), perciò \(x \in \bigcap_{n \in \mathbb{N}} X_{n} = X_{\infty}\). Dato che \(f(x) = y\) e \(x \in X_{\infty}\), questo dimostra he \(y \in \mathrm{rng}(f \restriction X_{\infty})\). Dunque anche \(Y_{\infty} \subseteq \mathrm{rng}(f \restriction X_{\infty})\), e per il principio di doppia inclusione \(f \restriction X_{\infty} = Y_{\infty}\).
(continua)
Dimostrazione.
Dunque abbiamo dimostrato che
per ogni \(i \in \mathbb{N}\), la funzione \(f \restriction (X_{2i} \setminus X_{2i+1}) \colon X_{2i} \setminus X_{2i+1} \to Y\) è una biezione tra \(X_{2i} \setminus X_{2i+1}\) e \(Y_{2i+1} \setminus Y_{2i+2}\);
per ogni \(i \in \mathbb{N}\), la funzione \(g^{-1} \restriction (X_{2i+1} \setminus X_{2i+2})\) è una biezione tra \(X_{2i+1} \setminus X_{2i+2}\) e \(Y_{2i} \setminus Y_{2i+1}\);
la funzione \(f \restriction A_{\infty} \colon A_{\infty} \to Y\) è una biezione tra \(A_{\infty}\) e \(B_{\infty}\).
Quindi la funzione \[h \colon X \to Y, \qquad x \mapsto \begin{cases} f(x) & \text{se } x \in X_{\infty} \\ f(x) & \text{se } x \in X_{2i} \setminus X_{2i+1} \text{ per qualche } i \in \mathbb{N} \\ g^{-1}(x) & \text{se } x \in X_{2i+1} \setminus X_{2i+2} \text{ per qualche } i \in \mathbb{N} \end{cases}\] è una biezione tra \(X\) e \(Y\).