Lezione 5

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 5.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 5.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 è fortemente non costruttivo: ci dice che una funzione di scelta esiste, ma non dà alcun modo per trovarla.

Osservazione 5.3   Una delle situazioni in cui più spesso si adopera l'assioma della scelta (e che anzi ne è una formulazione equivalente) è la seguente: sia $X$ un insieme, prendiamo come insieme di indici l'insieme $2^X-\{\varnothing \}$ e per ogni $i\in I$ (ossia per ogni $i\subseteq X$ diverso da $\varnothing$ poniamo $A_i=i$. L'assioma di scelta ci dice allora che esiste una funzione $\varphi :2^X-\{\varnothing \}\to X=\bigcup_{i\in 2^X-\{\varnothing \}}i$ tale che $\varphi (i)\in i$ per ogni $i\in2^X-\{\varnothing \}$.

Esercizio 5.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 5.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 5.4   Se $X$ è un insieme infinito, allora contiene un sottinsieme $Y$ equipotente a $\mathbb{N}$.

Dimostrazione.  Sia $\varphi :2^X-\{\varnothing \} \to X$ una funzione di scelta e denotiamo con $2^X_F$ l'insieme delle parti finite di $X$, ovvero $2^X_F=\{Z\subset X\mid Z$   è finito$\}$. Dato un elemento $x_0\in X$, (che esiste essendo $X$ infinito e quindi non vuoto) consideriamo la funzione $\psi : \mathbb{N}\to 2^X_F$ definita ricorsivamente da:

$$\psi(0) = \{x_0\}$$

$$\psi(n+1) = \psi(n) \cup \{ \varphi (X-\psi(n)) \}$$

e quindi definiamo la funzione $f:\mathbb{N}\to Y$ ponendo $f(0)=x_0$ 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 5.5   Nella dimostrazione del teorema precedente si definisce ricorsivamente una funzione $\psi : \mathbb{N}\to 2^X_F$. La funzione $h:\mathbb{N}\times 2^X_F\to2^X_F$ che si in questa definizione ricorsiva è la funzione data da $h(n,Z)=Z\cup\{\varphi (X-Z)\}$. Si osservi che dato che $X$ è infinito, se $Z$ è finito, allora $X-Z\ne\varnothing$ e quindi ha senso prendere $\varphi (X-Z)$ e il risultato dell'applicare $\psi$, $\psi(Z)$ è ancora un insieme finito. È esattamente in questo punto che si usa l'ipotesi di infinitezza dell'insieme $X$.

Osservazione 5.6   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 5.7   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$ (si provi questa affermazione). Ma allora la funzione $g:X \to X$ definita da

$$g(x)=\Big \langle \begin{array}{lcl} x &&\text{se }x\in X-Y \\ f(x) && \text{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 4.5, provano la seguente caratterizzazione degli insiemi infiniti.

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

Esercizio 5.3   Si provi quanto affermato nella dimostrazione della proposizione 5.7, ossia che se $Y$ è equipotente a $\mathbb{N}$ allora esiste una bigezione di $Y$ con un suo sottinsieme proprio.
Soluzione