Lezione 3 (6 marzo 2000 h. 9-11)

   
Confronto di cardinalità: il Teorema di Cantor-Bernstein

Definizione 3.1   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 3.1    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 3.2    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 3.2   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 3.3   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 3.4   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₀ = Z - Y e A_n+1=f(A_n), e si ponga $B=\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(x) = \Big \langle \begin{array}{lcl} f(x) &&\hbox{\rm {se }} x\in A \\ x &&\hbox{\rm {se }} x\in X-A \end{array}$$

Proviamo che g è una bigezione. g è iniettiva     $\square$

Teorema 3.5 (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 3.6 (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 3.7   Come era naturale aspettarsi, la relazione di avere cardinalità minore o uguale gode di tutte le proprietà di un ordinamento totale.

che mostra come la relazione di avere cardinalità minore o uguale goda 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 3.8 (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 3.9   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 & \d... ... [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 3.10   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 &&\hbox{\rm {se... ...rm {se }} \varepsilon_n \hbox{\rm { \\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 &... ...] 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 3.3      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.
Soluzione

Esercizio 3.4    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 3.5    Siano $F=\{A\in 2^\mathbb N\mid A \hbox{\rm { \\lq e finito}}\}$. Si provi che $\left\vert F\right\vert = \aleph_0$
Soluzione

Esercizio 3.6      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

   
Operazioni tra cardinalità

Sebbene non abbiamo dato la definizione di cardinalità di un insieme, (abbiamo dato significato al simbolo $\left\vert X\right\vert$ solo nel caso finito), con una serie di esercizi, vediamo come si possano ugualmente definire delle operazioni tra cardinalità.

Esercizio 3.7    Supponiamo che $\left\vert X\right\vert = \left\vert X'\right\vert$ e che $\left\vert Y\right\vert =\left\vert Y'\right\vert$ allora

1.

$\left\vert X \times Y\right\vert=\left\vert X'\times Y'\right\vert$

2.

$\left\vert X^Y \right\vert=\left\vert{X'}^{Y'}\right\vert$

3.

$\left\vert(X\times\{0\})\cup(Y\times\{1\})\right\vert = \left\vert(X'\times\{0\})\cup(Y'\times\{1\})\right\vert$

Soluzione

L'esercizio precedente permette di dare la seguente

Definizione 3.11   Se X e Y sono insiemi, si definiscono

1.

$\left\vert X\right\vert + \left\vert Y\right\vert = \left\vert(X\times\{0\})\cup(Y\times\{1\})\right\vert$

2.

$\left\vert X\right\vert \left\vert Y\right\vert = \left\vert X\times Y\right\vert$

3.

$\left\vert X\right\vert^{\left\vert Y\right\vert}= \left\vert X^Y\right\vert$

Esercizio 3.8    Si provi che le operazioni appena definite, nel caso di insiemi finiti, coincidono con le usuali operazioni tra numeri naturali.
Soluzione

Esercizio 3.9    Si provi che $2^{\left\vert X\right\vert}=\left\vert 2^X\right\vert$.
Soluzione

Lasciamo come esercizio la dimostrazione del fatto che queste operazioni verificano tutte le propruietà delle usuali operazioni tra numeri naturali.

Esercizio 3.10    Si provino le seguenti:

1.

$\left\vert X\right\vert + \left\vert Y\right\vert = \left\vert Y\right\vert + \left\vert X\right\vert$

2.

$\left\vert X\right\vert \left\vert Y\right\vert = \left\vert Y\right\vert \left\vert X\right\vert$

3.

$(\left\vert X\right\vert + \left\vert Y\right\vert)+\left\vert Z\right\vert =\left\vert X\right\vert + (\left\vert Y\right\vert+\left\vert Z\right\vert)$

4.

$(\left\vert X\right\vert \left\vert Y\right\vert)\left\vert Z\right\vert =\left\vert X\right\vert (\left\vert Y\right\vert \left\vert Z\right\vert)$

5.

$\left\vert X\right\vert (\left\vert Y\right\vert + \left\vert Z\right\vert)= (\... ...\vert\left\vert Y\right\vert)+(\left\vert X\right\vert \left\vert Z\right\vert)$

6.

$\left\vert X\right\vert ^{\left\vert Y\right\vert +\left\vert Z\right\vert} = \... ...rt ^{\left\vert Y\right\vert} \left\vert X\right\vert^{\left\vert Z\right\vert}$

7.

$\big(\left\vert X\right\vert ^{\left\vert Y\right\vert}\big)^{\left\vert Z\righ... ...t} = \left\vert X\right\vert ^{\left\vert Y\right\vert \left\vert Z\right\vert}$

Soluzione