Matematica Discreta
Lezione del giorno 18 ottobre 2011 Funzioni surgettive
Dati gli insiemi A,B una funzione f: A B è detta surgettiva quando ogni elemento b del codominio B é l’associato di almeno un elemento a del dominio A.
Quindi f sarà non surgettiva quando esiste qualche elemento del codominio B che non è l’associato 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
Esempio di rappresentazione grafica di una funzione non surgettiva (l’elemento 5 di B f non è l’associato 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, fissato un generico elemento bB, si cerca almeno un elemento aA tale che si abbia f(a)=b: se un tale elemento aA esiste sempre (comunque sia preso bB) allora f é surgettiva; se invece per alcuni valori di bB un tale elemento aA non esiste, allora la f non è surgetttiva. Si tratta in pratica di risolvere un’equazione in cui b è termine noto, ed a è l’incognita di cui si cercano soluzioni nel dominio A: se almeno una soluzione per a esiste nel dominio A (per ogni valore di b in B) allora la funzione è surgettiva . Esempio: se A é l’insieme dei numeri interi >8, la funzione f: A N definita da f(x)=x-8 é surgettiva. Infatti, fissato un generico elemento bN (quindi b è un intero positivo), la ricerca di un valore aA tale che si abbia f(a)=b porta all’equazione a-8=b, che ha (nell’incognita a) la soluzione a=b+8 (soluzione il cui valore appartiene al dominio A, perché, essendo b un intero positivo, certamente a=b+8 è un intero >8).
1 2 3 6
2 5 7
1 2 3 6
2 5 7
Invece la funzione f: A N definita da f(x)=x-5 non é surgettiva. Infatti, fissato un generico elemento bN (quindi b è un intero positivo), la ricerca di un valore aA tale che si abbia f(a)=b porta all’equazione a-5=b, che ha nell’incognita a la soluzione a=b+5 (soluzione che però, per alcuni valori di b, può non appartenere al dominio A: per esempio per b=2 si ha a=7A).
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 associati diversi nel codominio B, e ogni elemento del codominio B é associato di almeno un elemento del dominio A).
Cardinalità di un insieme
Diremo che un insieme A è un insieme finito se A contiene un numero finito di elementi; in caso contrario diremo che A è un insieme infinito.
Se A è un insieme finito, si definisce 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, ci limiteremo a dire che la sua cardinalità è infinita (in seguito approfondiremo l’argomento distinguendo vari “tipi” di infinito).
Teorema. Se A,B sono insiemi finiti, se A=n,B=m, e se esiste una funzione iniettiva f: A B allora nm.
Dimostrazione:
Elenchiamo esplicitamente gli n elementi distinti di A:
A={a1, a2, a3, …….., an}
(dove a1 indica l’elemento al primo posto nell’elenco, a2 quello al secondo posto,….., an quello al posto n, ultimo nell’elenco).
Poiché per ipotesi f è iniettiva, i loro associati:
f(a1), f(a2), f(a3),……, f(an)
sono elementi tutti diversi nel codominio B, quindi tali associati sono esattamente in numero di n.
Poiché per ipotesi B contiene esattamente m elementi, si conclude che nm (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 è possibile costruire nessuna funzione iniettiva f: A B.
Teorema. Se A,B sono insiemi finiti, seA=n,B=m, e se esiste una funzione surgettiva f:A B, allora nm.
Dimostrazione:
Elenchiamo esplicitamente gli m elementi distinti di B:
B={b1, b2, b3, …….., bm}
Poiché per ipotesi f è surgettiva, troviamo almeno un elemento a1A tale che f(a1)=b1 (se ne esiste più di uno, ne scegliamo a piacere uno fra i tanti che hanno come associato b1); per lo stesso motivo troviamo almeno un elemento a2A tale che f(a2)=b2 e così procediamo fino a trovare almeno un elemento amA tale che f(am)=bm.
Gli elementi trovati a1, a2, …. ,am 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 associato in B): si deduce che il numero degli elementi a1, a2, …. ,am è esattamente m.
Poiché per ipotesi l’insieme A contiene esattamente n elementi, si conclude che nm (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 nessuna funzione surgettiva f: A B.
Teorema. Se A,B sono insiemi finiti, se A=n, B=m e se esiste una funzione biunivoca f: A B, allora n=m.
Dimostrazione:
Essendo f iniettiva, per un teorema già dimostrato si ha nm; essendo f surgettiva, per un altro teorema già dimostrato si ha nm. 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 è possibile costruire nessuna funzione biunivoca f: A B.
