Matematica Discreta I Lezione del giorno 17 ottobre 2007 Teorema.

Matematica Discreta I

Lezione del giorno 17 ottobre 2007

Teorema. Siano A,B insiemi di cardinalità finita. Supponiamo che essi abbiano uguale cardinalitàA= n=B, e sia data una funzione f: A  B.

Allora si ha la seguente doppia implicazione: 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={a

, a

, a

, …….., a

}

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. 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={a

, a

, a

, …….., a

}

Poiché per assurdo f non è iniettiva, i corrispondenti:

f(a

), f(a

), f(a

),……, f(a

)

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 inversa di una funzione biunivoca.

Sia data una funzione biunivoca f: A  B. Comunque preso un elemento bB, la surgettività di f assicura che esiste almeno un elemento aA tale che si abbia f(a)=b. Ma l’iniettività di f assicura anche che è unico tale elemento aA che abbia la proprietà f(a)=b.

Se allora associamo ad ogni elemento bB questo unico elemento aA tale che si abbia f(a)=b, otteniamo una nuova funzione da B ad A, detta funzione inversa di f .

Tale funzione inversa è indicata con il simbolo f

: B  A.

Se la funzione f è rappresentata graficamente, la f

è rappresentata graficamente semplicemente invertendo il verso delle frecce.

Esempio:

funzione biunivoca f

A f B a

b c

2

5

7

funzione inversa f

B f

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 A è l’insieme dei numeri razionali positivi, negativi o nulli e se f: A  A è la funzione definita da f(x)=(x+7)/9, è facile verificare che f è iniettiva. Dimostriamo che f è surgettiva: preso un generico elemento yA, cerchiamo l’esistenza di un elemento xA tale che f(x)=(x+7)/9=y; si ottiene la soluzione x=9y-7A. Ciò dimostra che f è surgettiva (quindi biunivoca), ma permette anche di costruire la funzione inversa f

: A  A, definita appunto da f

(y)=9y-7.

Teorema. Sia f: A  B una funzione biunivoca. Allora la funzione inversa f

: B  A è anch’essa biunivoca.

Dimostrazione:

Dimostriamo che f

è iniettiva: se per assurdo esistessero b,cB, bc tali che f

(b)= f

(c), denotato con a tale elemento f

(b)=f

(c), si avrebbe, per definizione di funzione inversa f(a)=b, f(a)=c, e l’elemento aA avrebbe 2 immagini diverse mediante f, contraddicendo l’ipotesi che f è una funzione. Graficamente si avrebbe:

f  b a=f

(b)=f

(c) 

f  c

Dimostriamo che f

è surgettiva: dato un elemento generico yA, dobbiamo trovare un elemento xB tale che si abbia f

(x)=y: ma a tale scopo basta scegliere tale x coincidente con l’immagine f(y) dell’elemento y mediante f. Graficamente:

y f x  

y f

x  

2 5 7

a

b

c