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.2. 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}$}\setbox0\hbox{$f$} {{f} \vrule wi... ...\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