Lezione 4

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 w... ...\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

Scommettiamo che due di voi hanno lo stesso compleanno?

Storiella. Il professore di Matematica Discreta entra nell'aula e davanti ai suoi 60 studenti esclama: --Scommettiamo che due di voi hanno lo stesso compleanno?-- e aggiunge --se io perdo pago la cena a tutti, se vinco voi pagete una cena a me.--

Gli studenti accettano entusiasti la scommessa: --Male che vada ci rimettiamo 50 centesimi ciascuno, ma in ogni caso-- pensano --è praticamente impossibile che il prof. vinca, siamo troppo pochi.--

Una rapida verifica e quindi la delusione: il professore, come ogni anno, si è guadagnato una cena.

Perché il prof. ha vinto? È soltanto una fortuna sfacciata, che gli consente di vincere ogni anno, o è qualcos'altro?

Formalizziamo la situazione. Associare ad ogni studente il proprio giorno di nascita è una funzione da un insieme $X$ con 60 elementi (l'insieme degli studenti) in un insieme $Y$ con 365 elementi (l'insieme dei possibili giorni di nascita, escludendo il caso degli anni bisestili). Il professore perde se tale funzione è iniettiva, vince altrimenti. Si tratta allora di contare il numero di funzioni iniettive, e dividerlo per il numero di funzioni, questo darà la probabilità di perdere la scommessa da parte del professore.

Esercizio 4.5   Siano $X$ e $Y$ insiemi finiti di cardinalità rispettivamente $k$ e $n$, con $k \le n$. Si provi che l'insieme delle applicazioni iniettive $X\to Y$ ha cardinalità pari a $n!/(n-k)!$.
Soluzione

Questo, assieme al risultato dell'esercizio 4.4 (punto 2), ci dice che se $\left\vert X\right\vert= k$ e $\left\vert Y\right\vert= n$ la probabilità che una funzione $f:X\to Y$ sia iniettiva è pari a

$$\frac{n!}{(n-k)!n^k}$$

Questa formula applicata al caso $n=365$ e $k=60$ produce: $0.005877$, ossia quel furbacchione del professore aveva una probabilità di perdere la scommessa inferiore al $0.6\%$. Ciò spiega perché si fa una cena gratis ogni anno (vedi figura 1).

Figura 1: Grafico della probabilità di successo o di insuccesso, nella scommessa del compleanno, in funzione del numero di persone. Già con 60 persone si ha la ragionevole certezza di vincere la scommessa: la probabilità di perdere è inferiore a 6/1000, con 100 persone le probabilità di perdere scende a circa 3/10000000

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

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