Matematica Discreta Lezione del giorno 1 dicembre 2010 Cardinalità di un insieme

Matematica Discreta

Lezione del giorno 1 dicembre 2010 Cardinalità di un insieme

Se A è un insieme finito, ossia che contiene un numero finito di elementi, si chiama cardinalità di A (e si indica con il simbolo A) il numero degli elementi distinti di A.

Per esempio se A={1,a,2,3,b} si ha A=5. Ovviamente =0.

Per il momento, se A è un insieme infinito (ossia non finito), ci limiteremo a dire che la sua cardinalità è infinita (in seguito approfondiremo l’argomento).

Teorema. Se A,B sono insiemi finiti, se A=n, B=m, e se f: A  B è una funzione iniettiva, allora nm.

Dimostrazione:

Elenchiamo esplicitamente gli n elementi distinti di A:

A={a

, a

, a

, …….., a

}

(dove a

indica l’elemento al primo posto nell’elenco, a

quello al secondo posto,….., a

quello al posto n, ultimo nell’elenco).

Poiché per ipotesi f è iniettiva, i corrispondenti:

f(a

), f(a

), f(a

),……, f(a

)

sono elementi tutti diversi nel codominio B, quindi tali corrispondenti sono esattamente in numero di n. L’insieme B contiene dunque almeno n elementi, cioè nm (tesi).

Una conseguenza immediata del teorema precedente è la seguente: se A,B sono insiemi finiti e se la cardinalità n di A è maggiore della cardinalità m di B, allora non esiste nessuna funzione iniettiva f: A  B.

Teorema. Se A,B sono insiemi finiti, se A=n, B=m, e se f: A  B è una funzione surgettiva, allora nm.

Dimostrazione:

Elenchiamo esplicitamente gli m elementi distinti di B:

B={b

, b

, b

, …….., b

}

Poiché per ipotesi f è surgettiva, troviamo almeno un elemento a

A tale che f(a

)=b

; per lo stesso motivo troviamo almeno un elemento a

A tale che f(a

)=b

e così procediamo fino a trovare almeno un elemento a

A tale che f(a

)=b

.

Gli elementi trovati c

, c

, …. ,c

sono tutti diversi fra loro (se 2 fra essi coincidessero, la f non sarebbe più una funzione perché esisterebbe qualche elemento di A con più di un corrispondente in B): si deduce che il numero degli elementi c

, c

, …. ,c

è esattamente m.

L’insieme A contiene dunque almeno m elementi, cioé nm (tesi).

Una conseguenza immediata del teorema precedente è la seguente: se A,B sono insiemi finiti e se la cardinalità n di A è minore della cardinalità m di B, allora non è possibile costruire una funzione surgettiva f: A  B.

Funzioni biunivoche

Dati gli insiemi A,B una funzione f: A  B è detta biunivoca (o bigettiva) quando f è sia iniettiva

che surgettiva (quindi quando elementi diversi del dominio A hanno sempre corrispondenti diversi

nel codominio B, e ogni elemento del codominio B é corrispondente di almeno un elemento del dominio A).

Teorema. Se A,B sono insiemi finiti, se A=n, B=m e se f: A  B è una funzione biunivoca, allora n=m.

Dimostrazione:

Essendo f iniettiva, per un teorema già dimostrato si ha nm; essendo f surgettiva, per un altro teorema già dimostrato si ha nm. Si conclude allora che n=m.

Una conseguenza del teorema precedente è la seguente: se A,B sono insiemi finiti e se la

cardinalità n di A è diversa dalla cardinalità m di B, allora non esiste nessuna funzione

biunivoca f: A  B.