Matematica Discreta Lezione del giorno 9 ottobre 2008 Cardinalità di un insieme

Matematica Discreta

Lezione del giorno 9 ottobre 2008 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, e allora la cardinalità di B non è inferiore ad n, cioè nm (tesi).

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

A>B allora non è possibile costruire una funzione iniettiva f: A  B.

Funzioni surgettive

Dati gli insiemi A,B una funzione f: A  B è detta surgettiva quando ogni elemento y del codominio B é corrispondente di almeno un elemento x del dominio A.

Quindi f non sarà surgettiva quando esiste qualche elemento del codominio B che non è corrispondente di nessun elemento del dominio A.

Se f è rappresentata graficamente, la f è surgettiva quando ogni elemento di B è coperto da almeno una punta delle frecce che partono dagli elementi del dominio A.

Esempio:

Esempio di rappresentazione grafica di una funzione surgettiva

f

A B 1

2 3 6

2

5

7

Esempio di rappresentazione grafica di una funzione non surgettiva (l’elemento 5 di B f non è corrispondente di nessun elemento di A) A B

Se f è rappresentata con una matrice, la f è surgettiva quando ogni colonna contiene almeno un valore =1 (quindi non vi sono colonne con tutte le caselle contenenti valori =0).

Per verificare formalmente se una funzione f: A  B é surgettiva, si prende un generico elemento yB e si cerca almeno un elemento xA tale che si abbia f(x)=y: se un tale xA esiste sempre (comunque sia preso yB) allora f é surgettiva; se per alcuni valori di yB tale xA non esiste, allora la f non è surgetttiva.

Spesso, nelle funzioni matematiche, la f(x)=y diventa un’equazione di cui si devono cercare le soluzioni x nel dominio A: se almeno una di tali soluzioni esiste sempre in A (comunque sia preso yB) allora f é surgettiva.

Esempio: se A é l’insieme dei numeri interi >8, e se B é l’insieme dei numeri interi >0, la funzione f: A  B definita da f(x)=x-8 é surgettiva. Infatti, preso un generico intero yB, la ricerca di un valore intero xA tale che si abbia f(x)=y porta all’equazione x-8=y, che ha la soluzione x=y+8 (soluzione il cui valore é in A, per ogni yB, perché essendo y un intero positivo, certamente x=y+8 è un intero >8).

Invece, se A,B sono come sopra, la funzione f: A  B definita da f(x)=x-5 non é surgettiva. Infatti, preso un generico intero yB, la ricerca di un valore xA tale che si abbia f(x)=y porta all’equazione x-5=y, che ha la soluzione x=y+5 (soluzione il cui valore però non sempre é elemento di A: per esempio per y=2B si ha x=2+5=7A).

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 c

A tale che f(c

)=b

; per lo stesso motivo troviamo almeno un elemento c

A tale che f(c

)=b

e così procediamo fino a trovare almeno un elemento c

A tale che f(c

)=b

.

Gli elementi trovati c

, c

, …. ,c

sono tutti diversi fra loro (se 2 fra essi coincidessero, la f non sarebbe più una funzione) quindi il loro numero è esattamente m.

L’insieme A contiene dunque almeno questi m elementi, cioé la cardinalità di A è non inferiore ad m, ossia nm (tesi).

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

A<B allora non è possibile costruire una funzione surgettiva f: A  B.

1 2 3 6

2

5

7