Lezione 2 (29 febbraio 2000 h. 11-13)

   
Insiemi infiniti: l'assioma della scelta

Uno degli strumenti più potenti di cui si ha spesso bisogno quando si deve trattare con insiemi infiniti, è il seguente:

Assioma 2.1 (della scelta)   Sia I un insieme e per ogni $i\in I$ sia dato un insieme $A_i\ne\varnothing$. Allora esiste una funzione, detta funzione di scelta,

$$\varphi:I \longrightarrow\bigcup_{i\in I} A_i$$

tale che

$$\forall i \in I \quad \varphi(i)\in A_i$$

Osservazione 2.2   Questo assioma dice essenzialmente che quando si ha un insieme di insiemi non vuotiè possibile scegliere, in un colpo solo, un elemento da ciascuno di essi. Si osservi che questo assioma è non costruttivo per antonomasia: ci dice che una funzione di scelta esiste, ma non dà alcun modo per trovarla.

Esercizio 2.1      Si provi che una funzione $f:X\to Y$ è surgettiva se e solo se esiste $g:Y\to X$ tale che $f\circ g={\rm id}_Y$. Una tale g si chiama una inversa destra di f.
Soluzione

Esercizio 2.2      Si provi che una funzione $f:X\to Y$ è iniettiva se e solo se esiste $g:Y\to X$ tale che $g\circ f={\rm id}_X$. Una tale g si chiama una inversa sinistra di f.
Soluzione

Teorema 2.3   Se X è un insieme infinito, allora contiene un sottinsieme Y con $\left\vert Y\right\vert = \left\vert\mathbb N\right\vert$.

Dimostrazione.  Sia $\varphi:2^X-\{\varnothing\} \to X$ una funzione di scelta e, dato un elemento $x_0\in X$ consideriamo la funzione $\psi : \mathbb N\to 2^X$ definita ricorsivamente da:

$$\begin{eqnarray*}\psi(0) & = & \{x_0\} \\ \psi(n+1) & = & \psi(n) \cup \{ \varphi(X-\psi(n)) \} \end{eqnarray*}$$

e quindi definiamo la funzione $f:\mathbb N\to Y$ ponendo f(0)=x₀ e per ogni n>0, $f(n)=\varphi(X-\psi(n-1))$. Osserviamo che, dalla definizione di $\psi$segue che per ogni $n\in\mathbb N$ si ha $f(n)\in \psi(n)$ e $\psi(n)\subseteq \psi(n+1)$, da cui segue che se $n \le m$ allora $\psi(n)\subseteq\psi(m)$ e quindi $f(n)\in\psi(m)$. Ma allora se n < m, $f(n)\in \psi(m-1)$, mentre $f(m)=\varphi(X-\psi(m-1))\in X-\psi(m-1)$ e quindi $f(n)\ne f(m)$, pertanto fè iniettiva. L'insieme $f(\mathbb N)$ è allora l'insieme cercato.     $\square$

Osservazione 2.4   In qualche senso il teorema precedente mostra come la cardinalità dei numeri naturali sia, in un senso ancora da specificare la ``più piccola'' tra le cardinalità infinite.

Proposizione 2.5   Ogni insieme infinito è equipotente ad un suo sottinsieme proprio.

Dimostrazione. Sia X un insieme infinito e sia $Y\subseteq X$ un sottinsieme equipotente a $\mathbb N$. Abbiamo già visto che $\mathbb N$ è equipotente ad un suo sottinsieme proprio, quindi se $\left\vert Y\right\vert = \left\vert\mathbb N\right\vert$, Y è equipotente ad un suo sottinsieme proprio, in parrtcolare esiste una bigezione $f:Y\to Y'$ essendo $Y'\subsetneq Y$. Ma allora la funzione $g:X \to X$ definita da

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

dà una bigezione tra X ed il sottinsieme $(X-Y)\cup Y'\subsetneq X$.     $\square$

La proposizione precedente ed il corollario 1.12, provano la seguente caratterizzazione degli insiemi infiniti.

Teorema 2.6   Un insieme è infinito se e solo se è equipotente ad un suo sottinsieme proprio.

   
Insiemi numerabili

Definizione 2.7   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 2.8   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) && \hbox{\rm {se }} x\in X \\ 2 g(x)+1 && \hbox{\rm {se }} x\in Y \end{array}$$

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

Proposizione 2.9   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) && \hbox{\rm {se }} x\in Y \\ f(x)+n && \hbox{\rm {se }} x\in X \end{array}$$

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

Proposizione 2.10   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 3.4.     $\square$

Proposizione 2.11   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 1.11 Y-X è finito o numerabile.

Sia $Z\subseteq X$ un sottinsieme numerabile, per le due proposizioni 2.9, 2.8, 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) && \hbox{\rm {se }} x\in Z \\ x && \hbox{\rm {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 2.12   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}) \quad \hbox{\rm {se }} M_{n-1}\le k < M_n$$

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

Proposizione 2.13   $\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 2.14   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 2.3    Si eseguano nel dettaglio tutte le verifiche necessarie a concludere le dimostrazioni delle proposizioni di questa sezione.
Soluzione

Esercizio 2.4      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 2.5      Si provi che se $\{X_m \mid m\in\mathbb N\}$ è una famiglia numerabile di insiemi numerabili, allora la loro unione è numerabile.
Soluzione

Esercizio 2.6    Si provi che $\mathbb Q$ è numerabile.
Soluzione