Lezione 6

Insiemi numerabili

Definizione 6.1   Un insieme $X$ si dice numerabile se $\left\vert X\right\vert = \left\vert\mathbb{N}\right\vert$. La cardinalità di $\mathbb{N}$ viene spesso indicata con $\aleph_0$ (si legge aleph con zero). Quindi per dire che $X$ è numerabile si scriverà anche $\left\vert X\right\vert=\aleph_0$.

Il simbolo $\aleph$ la prima lettera dell'alfabeto ebraico.

Diamo ora alcune proprietà degli insiemi numerabili.

Proposizione 6.2   Se $X$ e $Y$ sono insiemi numerabili disgiunti, allora $X\cup Y$ è numerabile.

Dimostrazione. Siano $f:X\to \mathbb{N}$ e $g : Y \to \mathbb{N}$ due bigezioni, allora si definisca $h:X\cup Y\to \mathbb{N}$ ponendo

$$h(x)=\Big\langle \begin{array}{lcl} 2 f(x) && \text{se } x\in X \\ 2 g(x)+1 && \text{se } x\in Y \end{array}$$

Si verifica facilmente che $h$ è una bigezione.     $\square$

Proposizione 6.3   Se $X$ e $Y$ sono disgiunti, $X$ numerabile e $Y$ è finito, allora $X\cup Y$ è numerabile.

Siano $f:X\to \mathbb{N}$ e $g : Y \to I_n$ due bigezioni, allora si definisca $h:X\cup Y\to \mathbb{N}$ ponendo

$$h(x)=\Big\langle \begin{array}{lcl} g(x) && \text{se } x\in Y \\ f(x)+n && \text{se } x\in X \end{array}$$

Si verifica facilmente che $h$ è una bigezione.     $\square$

Proposizione 6.4   Se $X$ è numerabile e $Y\subseteq X$ allora $Y$ è finito o numerabile.

Dimostrazione.  Se $Y$ non è finito, allora contiene un sottinsieme numerabile $Z$, ma allora la tesi segue dal lemma 6.12.     $\square$

Proposizione 6.5   Se $X$ è un insieme infinito ed $Y$ è un insieme finito o numerabile allora $\left\vert X\cup Y\right\vert=\left\vert X\right\vert$.

Dimostrazione. Possiamo supporre che $Y$ sia disgiunto da $X$, in quanto $X\cup Y = X\cup (Y-X)$ e per la proposizione precedente e la proposizione 4.4 $Y-X$ è finito o numerabile.

Sia $Z\subseteq X$ un sottinsieme numerabile, per le due proposizioni 6.3, 6.2, esiste una bigezione $f:Z \to Z\cup Y$. Si definisca allora $g : X \to X\cup Y$ ponendo

$$g(x)=\Big\langle \begin{array}{lcl} f(x) && \text{se } x\in Z \\ x && \text{se } x\in X-Z \end{array}$$

Proviamo che $g$ è iniettiva. Siano $x_1,x_2\in X$ diversi, chiaramente, dato che $f$ è iniettiva, se $x_1,x_2\in Z$ allora $f(x_1)\ne f(x_2)$ e quindi $g(x_1)\ne g(x_2)$. Se $x_1,x_2\in X-Z$, evidentemente $g(x_1)\ne g(x_2)$. Se $x_1\in Z$ e $x_2\in X-Z$ allora $g(x_1)=f(x_1)\in Z\cup Y$ e, dato che $Y$ è disgiunto da $X$, $(Z\cup Y)\cap (X-Z)=\varnothing$, e quindi $f(x_1)\notin X-Z$, mentre $g(x_2)=x_2\in X-Z$.

Proviamo che $g$ è surgettiva. Sia $w\in X\cup Y$, allora si hanno due casi: $w\in X-Z$ oppure $W\in Z \cup Y$. Nel primo caso, preso $x=w$, si ha che $g(x)=w$. Nel secondo caso, dato che $f$ è surgettiva, esiste $z\in Z$ tale che $f(z)=w$, e quindi $g(z)=w$.     $\square$

Proposizione 6.6   Se $\{X_n \mid n\in\mathbb{N}\}$ è una famiglia numerabile di insiemi finiti e a due a due disgiunti, allora $\bigcup_n X_n$ è numerabile.

Dimostrazione. Sia $m_n=\left\vert X_n\right\vert$ e per ogni $n$ sia $f_n:I_{m_n}\to X_n$ una bigezione. Si considerino i numeri $M_n = \sum_{i=0}^n m_i$, $M_{-1}=0$, e si definisca $f:\mathbb{N}\to \bigcup_n X_n$ ponendo

$$f(k) = f_n (k-M_{n-1})$$   se $$M_{n-1}\le k < M_n$$

Una semplice verifica mostra che $f$ è ben definita ed è una bigezione.     $\square$

Proposizione 6.7   $\mathbb{N}\times \mathbb{N}$ è numerabile, e quindi il prodotto di due insiemi numerabili è numerabile.

Dimostrazione.  Per ogni $m\in \mathbb{N}$ si consideri $X_m=\{(n_1,n_2)\in\mathbb{N}\times\mathbb{N}\mid n_1+n_2=m\}$. Chiaramente $\left\vert X_m\right\vert=m+1$ per ogni $m$, $X_m\cap X_k=\varnothing$ se $m\ne k$ e infine $\bigcup_mX_m=\mathbb{N}\times \mathbb{N}$ (si osservi che $(n_1,n_2)\in X_{n_1+n_2}$). Ma allora la tesi segue dalla proposizione precedente.

Per quanto riguarda la seconda parte dell'enunciato, si osservi che se $X$ e $Y$ sono numerabili, e $f:X\to \mathbb{N}$ e $g : Y \to \mathbb{N}$ sono bigezioni, allora l'applicazione prodotto $f\times g : X\times Y \to \mathbb{N}\times\mathbb{N}$ è bigettiva.     $\square$

Proposizione 6.8   Se $\{X_n \mid n\in\mathbb{N}\}$ è una famiglia numerabile di insiemi numerabili e a due a due disgiunti, allora $\bigcup_n X_n$ è numerabile.

Dimostrazione.  Per ogni $n\in \mathbb{N}$ sia $f_n:\mathbb{N}\to X_n$ una bigezione, definiamo $f:\mathbb{N}\times\mathbb{N}\to \bigcup_n X_n$ ponendo $f(n,m)=f_n(m)$. Si conclude verificando che $f$ è una bigezione.     $\square$

Esercizio 6.1   Si eseguano nel dettaglio tutte le verifiche necessarie a concludere le dimostrazioni delle proposizioni di questa sezione.
Soluzione

Esercizio 6.2   Si provi che se $\{X_m \mid m\in\mathbb{N}\}$ è una famiglia numerabile di insiemi finiti, allora la loro unione è finita o numerabile.
Soluzione

Esercizio 6.3   Si provi che se $\{X_m \mid m\in\mathbb{N}\}$ è una famiglia numerabile di insiemi numerabili, allora la loro unione è numerabile.
Soluzione

Esercizio 6.4   Si provi che $\mathbb{Q}$ è numerabile.
Soluzione

Confronto di cardinalità: il Teorema di Cantor-Bernstein

Definizione 6.9   Dati due insiemi, $X$ e $Y$ diremo che la cardinalità di $X$ è minore o uguale alla cardinalità di $Y$, e lo scriveremo $\left\vert X\right\vert \le \left\vert Y\right\vert$, se esiste una funzione iniettiva, $f:X\to Y$.

Diremo che la cardinalità di $X$ è strettamente minore di quella di $Y$, e lo denoteremo con $\left\vert X\right\vert < \left\vert Y\right\vert$, se $\left\vert X\right\vert \le \left\vert Y\right\vert$ e $\left\vert X\right\vert \ne \left\vert Y\right\vert$.

È immediato verificare che $\left\vert X\right\vert \le \left\vert Y\right\vert$ se e solo se $Y$ contiene un sottinsieme equipotente a $X$.

Esercizio 6.5   Si provi che nel caso di insiemi finiti, la nozione di ordinamento appena introdotta tra le cardinalità, coincide con l'usuale ordinamento dei numeri naturali.
Soluzione

Esercizio 6.6   Si provi che $\left\vert X\right\vert \le \left\vert Y\right\vert$ se e solo se esiste $f:Y \to X$ surgettiva.
Soluzione

Proposizione 6.10   Valgono le seguenti proprietà:

1. Per ogni $X$, $\left\vert X\right\vert \le \left\vert X\right\vert$
2. per ogni $X,Y,Z$, se $\left\vert X\right\vert \le \left\vert Y\right\vert$ e $\left\vert Y\right\vert \le \left\vert Z\right\vert$ allora $\left\vert X\right\vert \le \left\vert Z\right\vert$

Dimostrazione.  Basta osservare che l'identità è iniettiva e che composizione di funzioni inettive è una funzione iniettiva.     $\square$

Osservazione 6.11   La proposizione precedente mostra che la relazione di avere cardinalità minore o uguale gode delle proprietà riflessiva e transitiva. Vedremo tra poco che gode anche della proprietà antisimmetrica.

Lemma 6.12   Supponiamo che $X\subseteq Y \subseteq Z$ e che $\left\vert X\right\vert = \left\vert Z\right\vert$, allora $\left\vert Y\right\vert = \left\vert Z\right\vert$.

Dimostrazione. Sia $f : Z \to X$ una bigezione. Poniamo $A_0 = Z - Y$ e $A_{n+1}=f(A_n)$, e si ponga $A=\bigcup_n A_n$. Osserviamo che $f(A)\subseteq A\cap Y$, e che $f$ è una bigezione tra $A$ e la sua immagine. Definiamo allora $g:Z \to Y$ ponendo

$$g(z) = \Big \langle \begin{array}{lcl} f(z) &&\text{se } z\in A \\ z &&\text{se } z\in Z-A \end{array}$$

e proviamo che è una bigezione.

$g$ è iniettiva, siano infatti $z_1,z_2\in Z$, $z_1\ne z_2$. Si hanno tre casi:

1. $z_1,z_2 \in A$. In questo caso, dato che $f$ è iniettiva, $g(z_1)=f(z_1)\ne f(z_2)=g(z_2)$.
2. $z_1,z_2 \in Z-A$. In questo caso $g(z_1)=z_1\ne z_2=g(z_2)$.
3. $z_1\in A$ e $z_2 \in Z-A$. In tal caso $g(z_1)=f(z_1)\in A$, mentre $g(z_2)=z_2\in Z- A$ quindi $g(z_1) \ne g(z_2)$.

$g$ è surgettiva. Sia $y\in Y$, allora o $y\in Y-A$ e allora $g(y)=y$, oppure $y\in A$. In questo caso esiste $i\in\mathbb{N}$ tale che $y\in A_i$, inoltre dato che $y\in Y$ e $A_0 = Z - Y$, sicuramente $i>0$. Ma allora $A_i=f(A_{i-1})$, quindi esiste $z\in A_{i-1}$ tale che $f(z)=y$. Dato che $z\in A$ allora $g(z)=f(z)=y$.     $\square$

Teorema 6.13 (Cantor-Bernstein)   Siano $X$ e $Y$ due insiemi e supponiamo che $f:X\to Y$ e $g:Y\to X$ siano due funzioni iniettive. Allora esiste una funzione bigettiva $h:X\to Y$.

Dimostrazione.  Si osservi che $\left\vert X\right\vert = \left\vert f(X)\right\vert$ e che $\left\vert g(f(X))\right\vert=\left\vert f(X)\right\vert$ e quindi $\left\vert X\right\vert=\left\vert g(f(X))\right\vert$. D'altra parte, $g(f(x)) \subseteq g(Y) \subseteq X$, quindi per il lemma precedente $\left\vert X\right\vert=\left\vert g(Y)\right\vert$. Dato che $\left\vert g(Y)\right\vert=\left\vert Y\right\vert$ segue la tesi.     $\square$

La tricotomia dei cardinali

Enunciamo senza dimostrare un importante teorema, la cuidimostrazione richiede tecniche che esulano dalle finalità del corso, ma che è comunque importante conoscere:

Teorema 6.14 (tricotomia dei cardinali)   Per ogni coppia di insiemi $X$, $Y$ si ha che o $\left\vert X\right\vert \le \left\vert Y\right\vert$ oppure $\left\vert Y\right\vert\le \left\vert X\right\vert$.

Osservazione 6.15   Come era naturale aspettarsi, la relazione di avere cardinalità minore o uguale gode di tutte le proprietà di un ordinamento totale.

Il procedimento diagonale di Cantor

Le cardinalità finite e numerabile non esauriscono tutte le possibili cardinalità, il seguente teorema dimostra che esistonoo insiemi di cardinalità arbitrariamente elevata.

Teorema 6.16 (Cantor)   Per ogni $X$ si ha che $\left\vert X\right\vert < \left\vert 2^X\right\vert$.

Dimostrazione.  La funzione $f:X\to 2^X$ definita da $f(x)=\{x\}$ è iniettiva. Se $f:X\to 2^X$ è una qualsiasi funzione allora non è surgettiva, infatti l'insieme $\{x\in X\mid x\notin f(x)\}$ non appartiene all'immagine di $f$.     $\square$

Osservazione 6.17   La tecnica di dimostrazione usata in questo teorema è nota come procedimento diagonale. Il perché di tale nome appare chiaro se consideriamo la dimostrazione nel caso particolare di $\mathbb{N}$. Supponiamo di avere una numerazione di sottinsiemi di $\mathbb{N}$, rappresentiamo ogni sottinsieme di $\mathbb{N}$ con una successione di 0 e $1$ (mettiamo un $1$ in corrispondenza degli elementi che appartengono al sottinsieme e uno 0 altrimenti)

$$\begin{array}{cccccccccc} & & 0 & 1 & 2 & 3 & 4 & 5 & 6 & \dots \... ... \vdots & \ddots [10pt] A & = & 0 & 1 & 1 & 0 & 0 & 1 & 1 & \dots \end{array}$$

Costruiamo una nuova successione di 0 e $1$ ponendo all'$n$-esimo posto uno 0 se all'$n$-esimo posto di $f(n)$ c'è un $1$, e $1$ altrimenti. Chiaramente tale successione è diversa da ciascuna delle $f(n)$. La successione così costruita rappresenta proprio l'insieme $\{n\in\mathbb{N}\mid n\notin f(n)\}$.

Esempio 6.18   La stessa tecnica diagonale può essere usata per provare che l'insieme dei numeri reali è più che numerabile. Si supponga di avere un'applicazione $f:\mathbb{N}\to (0,1)$, e per ogni $n$ sia $\varepsilon _n$ la $n$-esima cifra dello sviluppo decimale infinito di $f(n)$. Si ponga

$$\delta_n = \Big\langle \begin{array}{lcl} 1 &&\text{se } \varepsi... ...xt{ \\lq e pari} \\ 2 &&\text{se } \varepsilon _n \text{ \\lq e dispari} \end{array}$$

Si costruisca quindi il numero reale $r$ che ha $\delta_n$ come $n$-esima cifra del suo sviluppo decimale.

$$\begin{array}{ccccccccccc} f(0) & = & 0. & \fbox 1 & 4 & 9 & 2 & ... ...ts & \ddots [10pt] r & = & 0. & 2 & 2 & 1 & 1 & 1 & 2 & 1 & \dots \end{array}$$

Chiaramente, questo numero sta nell'intervallo $(0,1)$ ma è diverso da tutti gli $f(n)$. in quanto differisce da $f(n)$ nella $n$-esima cifra decimale. Per concludere, si osserva che $\left\vert(0,1)\right\vert=\left\vert\mathbb{R}\right\vert$. Si può in realtà dimostrare che $\left\vert\mathbb{R}\right\vert =2^{\aleph_0}$.

Esercizio 6.7   Si provi che $\left\vert(0,1)\right\vert=\left\vert\mathbb{R}\right\vert$.
La funzione $f:(0,1)\to\mathbb{R}$ definita da $f(t)=\tan(\pi t-\pi/2)$ è una bigezione. $\qedsymbol$

SoluzioneARRAY(0x8eaf5f0)

Esercizio 6.8   Siano $Y\subseteq X$. Si provi che se $\left\vert X\right\vert > \left\vert Y\right\vert =\aleph_0$ allora $\left\vert X-Y\right\vert=\left\vert X\right\vert$.
Soluzione

Esercizio 6.9   Siano $F=\{A\in 2^\mathbb{N}\mid A$    è finito$\}$. Si provi che $\left\vert F\right\vert = \aleph_0$
Soluzione

Esercizio 6.10   Si identifichi ogni numero reale in $(0,1)$ con la successione di $1$ e 0 data del suo sviluppo binario, scegliendo quello infinito nei casi di ambiguità (i.e. $0.11 = 0.10111\dots$) e si usino i due esercizi precedenti per provare che $\left\vert\mathbb{R}\right\vert = \left\vert 2^\mathbb{N}\right\vert$.
Soluzione