Matematica Discreta
Lezione del giorno 6 dicembre 2010
Il prossimo risultato dimostra che, nel caso di dominio e codominio finiti e con la stessa cardinalità, i concetti di funzione iniettiva e surgettiva in pratica coincidono.
Teorema. Siano A,B insiemi di cardinalità finita, e supponiamo anche che essi abbiano uguale cardinalitàA= n=B. Allora, data una funzione f: A B, si ha:
f è iniettiva f è surgettiva.
Dimostrazione:
Dimostriamo la prima implicazione , in cui l’ipotesi è che f sia iniettiva e la tesi è che f sia surgettiva.
Elenchiamo esplicitamente gli n elementi distinti di A:
A={a1, a2, a3, …….., an}
Poiché per ipotesi f è iniettiva, i corrispondenti:
f(a1), f(a2), f(a3),……, f(an)
sono elementi tutti diversi nel codominio B, quindi tali corrispondenti sono esattamente in numero di n. Ma l’insieme B contiene esattamente n elementi, e dunque tali corrispondenti esauriscono tutti gli n elementi di B. Questo vuol dire che ogni elemento di B è corrispondente di qualche elemento di A, cioè f è surgettiva (tesi).
Dimostriamo la seconda implicazione , in cui l’ipotesi è che f sia surgettiva e la tesi è che f sia iniettiva.
Ragioniamo per assurdo: supponiamo vera l’ipotesi e falsa la tesi, cioé supponiamo f surgettiva ma f non iniettiva.
Elenchiamo esplicitamente gli n elementi distinti di A:
A={a1, a2, a3, …….., an}
Poiché per assurdo f non è iniettiva, i corrispondenti:
f(a1), f(a2), f(a3),……, f(an)
non sono tutti distinti, quindi sono in numero minore di n. Ma l’insieme B contiene esattamente n elementi, dunque tali corrispondenti non esauriscono tutti gli n elementi di B. Questo vuol dire che esiste qualche elemento di B che non è corrispondente di nessun elemento di A, cioè f non é surgettiva (contraddizione).
Funzione identica
Dato un insieme A, si definisce la cosiddetta funzione identica di A: essa è la funzione che ha dominio e codominio coincidenti entrambi con A, ed associa ogni elemento di A con sé stesso.
Tale funzione si indica con il simbolo:
iA: A A
ed è quindi definita ponendo iA(x)=x per ogni xA. Ovviamente la funzione identica è biunivoca.
Funzione inversa di una funzione biunivoca.
Sia data una funzione biunivoca f: A B. Comunque preso un elemento bB, essendo f surgettiva esiste almeno un elemento aA tale che si abbia f(a)=b. Ma questo elemento aA tale che si abbia f(a)=b è anche unico, perché f è iniettiva.
Se allora associamo all’elemento bB questo unico elemento aA che soddisfa la proprietà f(a)=b, otteniamo una nuova funzione da B ad A, detta funzione inversa di f .
Tale funzione inversa è indicata con il simbolo f -1: B A.
Se la funzione f è rappresentata graficamente, la f-1 è rappresentata graficamente semplicemente invertendo il verso delle frecce.
Esempio:
funzione biunivoca f
A f B
funzione inversa f -1
B f-1 A
Formalmente, per costruire la funzione inversa di una funzione biunivoca, si deve seguire il procedimento usato per dimostrarne la surgettività; in tale procedimento, dato un elemento generico del codominio, si cerca un elemento del dominio la cui immagine è l’elemento dato: tale elemento del dominio è per costruzione proprio l’immagine dell’elemento di partenza mediante la funzione inversa.
Esempio: se Z è l’insieme dei numeri interi relativi e se f: Z Z è la funzione definita da f(x)=x-5, è facile verificare che f è iniettiva. Dimostriamo che f è surgettiva: preso un generico elemento bZ (quindi b è un numero intero relativo), cerchiamo l’esistenza di un elemento aZ tale che:
f(a)=a-5=b
Si ottiene la soluzione a=b+5Z. Ciò dimostra che f è surgettiva (quindi biunivoca), ma permette anche di costruire la funzione inversa f –1: Q Q, definita appunto da f –1(x)=x+5.
Osservazione: è ovvio che se A è un insieme, la funzione inversa della funzione identica iA: A A è la stessa funzione iA, quindi iA-1 = iA .
Composizione di funzioni
Siano A,B,C, 3 insiemi e siano f: A B, g: B C delle funzioni (notare che siamo in una situazione particolare: il codominio B di f coincide con il dominio B di g). Se prendiamo un elemento generico xA, la f associa a tale elemento x un unico elemento y=f(x)B; a sua volta la g associa a tale elemento y un unico elemento z=g(y)C. In tal modo, associando ad xA l’unico elemento zC si ottiene una nuova funzione con dominio A e codominio C, detta composizione di f e g (o anche funzione composta di f e g), e indicata con il simbolo gf: A C. In pratica l’azione di gf è ottenuta applicando f e poi g:
(gf)(x)=z=g(y)=g(f(x))
(notare che la funzione f, che agisce per prima, è scritta per seconda nel simbolo gf).
a b c
2 5 7
2 5 7
a b c
Esempi:
1) Siano A={1,2,3,4}, B={a,b,c}, C={5,6,8} e siano f: A B, g: B C le funzioni descritte graficamente da:
f g
Allora la composizione gf: A C è descritta graficamente da:
gf
2) Se N è l’insieme dei numeri naturali, Q l’insieme dei numeri razionali, R l’insieme dei numeri reali, date le 2 funzioni f: A B, g: B C definite dalle formule:
f(x)=x/3, g(x)= x21
la composizione gf: A C è definita da:
(gf)(x)=g(f(x))=g(x/3)= (x/3)21= (x2 9)/9
Teorema. La composizione di 2 funzioni iniettive è una funzione iniettiva. La composizione di 2 funzioni surgettive è una funzione surgettiva. La composizione di 2 funzioni biunivoche è una funzione biunivoca.
Dimostrazione:
Siano f: A B, g: B C due funzioni.
Supponiamo dapprima che f, g siano iniettive e dimostriamo che gf è iniettiva: se a,bA, ab, si ha f(a)f(b) (per l’iniettività di f), e allora g(f(a))g(f(b)) ((per l’iniettività di g) dunque si conclude che (gf)(a) (gf)(b), ossia gf è iniettiva.
Supponiamo ora che f, g siano surgettive e dimostriamo che gf è surgettiva: dato cC, cerchiamo una elemento aA tale che (gf)(a)=c; ma, per la surgettività di g, esiste bB tale che g(b)=c;
inoltre, per la surgettività di f, esiste aA tale che f(a)=b, da cui in totale (gf)(a)=c.
La terza affermazione segue ovviamente dalle prime due.
Calcoliamo la composizione di funzioni in alcuni casi particolari.
Siano A,B insiemi, sia f: A B una funzione e consideriamo la funzione identica di B:
iB : B B
Possiamo allora considerare la composizione iBf : A B.
1 2 3 4
a b c
5 6 8
1 2 3 4
5 6 8
Per ogni elemento xA si ha (iBf)(x)= iB(f(x))=f(x), e si conclude che le funzioni iBf ed f sono uguali (perché agiscono allo stesso modo su un generico elemento x):
iBf = f
Analogamente siano A,B insiemi, sia f: A B una funzione e consideriamo la funzione identica di A:
iA : A A
Possiamo allora considerare la composizione fiA : A B.
Per ogni elemento xA si ha (fiA)(x)= f(iA(x))=f(x), e di nuovo si conclude che le funzioni fiA ed f sono uguali:
fiA = f
Se A,B sono insiemi e se f: A B una funzione biunivoca, possiamo considerare la funzione inversa f-1: B A, e le due composizioni:
f-1f : A A ff-1 : B B
Per ogni elemento xA si ha (f-1f)(x)= f-1(f(x))=x, e si conclude che la funzione f-1f coincide con la funzione identica di A:
f-1f = iA
Con ragionamento analogo di ha che la funzione ff-1 coincide con la funzione identica di B:
ff-1 = iB .