Lezione 4 (7 marzo 2001 h. 10.30-11.30)

   
Cardinalità degli insiemi finiti

Una prima immediata conseguenza del lemma dei cassetti è il seguente corollario:

Corollario 4.1   Se $n,m\in\mathbb N$ sono due naturali diversi X e Y sono insiemi finiti con $\left\vert X\right\vert=\left\vert I_ n\right\vert$ e $\left\vert Y\right\vert=\left\vert I_m\right\vert$, allora X e Y non sono equipotenti. In particolare, se $\left\vert X\right\vert=\left\vert I_ n\right\vert$ e $\left\vert X\right\vert = \left\vert I_m\right\vert$ allora n=m.

Questo corollario fa sì che si possa definire la cardinalità degli insiemi finiti.

Definizione 4.2   Sia X un insieme finito, si dice cardinalità di X l'unico numero naturale n tale che $\left\vert X\right\vert=\left\vert I_ n\right\vert$. Tale numero si denota allora con $\left\vert X\right\vert$.

È facile provare la seguente

Proposizione 4.3   Due insiemi finiti sono equipotenti se e solo se $\left\vert X\right\vert=\left\vert Y\right\vert$.

Dimostrazione.  Se $\left\vert X\right\vert=\left\vert Y\right\vert$, allora esiste $n\in\mathbb N$ tale che X è equipotente a I_n e Y è equipotente a I_n, ma allora X e Y sono tra loro equipotenti (proposizione 2.3. Viceversa se sono equipotenti il corollario precedente mostra che hanno la stessa cardinalità.     $\square$

   
Sottinsiemi di un insieme finito

Proposizione 4.4   Sia X un insieme finito e $Y\subseteq X$ allora anche Y è finito e $\left\vert Y\right\vert \le \left\vert X\right\vert$. Se Y è un sottoinsieme proprio di X allora $\left\vert Y\right\vert < \left\vert X\right\vert$.

Dimostrazione. Procediamo per induzione su $n=\left\vert X\right\vert$. Se n=0 allora $X=\varnothing$ e quindi anche $Y=\varnothing$, da cui si conclude. Supponiamo la tesi vera per n e sia dato X con $\left\vert X\right\vert = n+1$. Sia $f:I_{n+1}\to X$ una bigezione e poniamo x_n=f(n) e $X'=X-\{x_n\}$. Chiaramente $\setbox \restrictbox=\hbox{$\hbox{$f$ }_{I_n}$ } \setbox 0\hbox{$f$ } {{f}\,\vr... ...\dp\restrictbox\, \hbox{\vrule depth\dp0 height \ht0 width0pt}_{I_n}}:I_n\to X'$ è una bigezione, quindi $\left\vert X'\right\vert=n$. Si hanno due casi $x_n\not\in Y$ e $x_n\in Y$. Nel primo caso $Y\subseteq X'$, quindi, per ipotesi di induzione, $\left\vert Y\right\vert\le\left\vert X'\right\vert=n<n+1=\left\vert X\right\vert$. Nel secondo caso, detto $Y'=Y-\{x_n\}$ si ha che $Y'\subseteq X'$ e quindi $\left\vert Y'\right\vert\le\left\vert X'\right\vert$ e quindi $\left\vert Y\right\vert=\left\vert Y'\right\vert+1\le\left\vert X'\right\vert+1=\left\vert X\right\vert$. Si osservi che in quest'ultimo caso, se $Y\ne X$ allora anche $Y'\ne X'$ e quindi, per ipotesi di induzione si ha che $\left\vert Y'\right\vert<\left\vert X'\right\vert$ da cui $\left\vert Y\right\vert < \left\vert X\right\vert$.     $\square$

Come conseguenza si ha il seguente

Corollario 4.5   Un insieme finito non è equipotente ad alcun suo sottinsieme proprio.

Esempio 4.6   L'insieme $\mathbb N$ è infinito, si consideri ad esempio l'applicazione $\mathbb N\to\mathbb N$ definita da $n \mapsto\mathop{\rm succ}\nolimits(n)$, questa è una bigezione tra $\mathbb N$ ed il sottinsieme proprio $\mathbb N-\{0\}$.

Esercizio 4.1    Si determinino altri sottinsiemi propri di $\mathbb N$ equipotenti a $\mathbb N$
Soluzione

Esercizio 4.2      Siano X e Y insiemi finiti. Si provi che

1.

se $X\cap Y=\varnothing$ allora $\left\vert X\cup Y\right\vert=\left\vert X\right\vert+\left\vert Y\right\vert$.

2.

in generale $\left\vert X\cup Y\right\vert=\left\vert X\right\vert+\left\vert Y\right\vert-\left\vert X\cap Y\right\vert$

Soluzione

Esercizio 4.3      Siano $X_1,\dots, X_n$ insiemi finiti a due a due disgiunti si provi che $\bigcup_{i=1}^nX_i$ è finito e che

$$\left\vert\bigcup_{i=1}^n X_i\right\vert=\sum_{i+1}^n\left\vert X_i\right\vert.$$

Soluzione

Esercizio 4.4      Se X e Y sono insiemi finiti, si provi che

1.

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

2.

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

3.

$\left\vert 2^X\right\vert=2^{\left\vert X\right\vert}$.

Soluzione

Esercizio 4.5    Siano X e Y insiemi finiti entrambi di cardinalità n. Si provi che ogni funzione iniettiva $X\to Y$ è anche surgettiva.
Soluzione

Esercizio 4.6    Sia X un insieme finito di cardinalità n. Si determini il numero delle applicazioni biunivoche di X in sé.
Soluzione