Matematica Discreta Lezione del giorno 28 ottobre 2009

(1)

Matematica Discreta

Lezione del giorno 28 ottobre 2009

Useremo (come già visto in alcuni esempi precedenti) i seguenti simboli per indicare gli insiemi numerici più comuni: N è l’insieme dei numeri interi >0, detti numeri naturali; Z è l’insieme dei numeri interi relativi (cioè positivi, negativi e lo zero); Q è l’insieme dei numeri razionali relativi (ossia delle frazioni aventi come numeratore e denominatore 2 numeri interi relativi, e con il denominatore non nullo); R è l’insieme dei numeri reali relativi (positivi negativi o nulli).

Un asterisco sul simbolo indicherà che dall’insieme è escluso lo 0 (per es. Q* è l’insieme dei numeri razionali relativi non nulli); un segno + sul simbolo indicherà che dell’insieme sono considerati solo i positivi (per es. Q⁺ è l’insieme dei numeri razionali positivi)

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 di cardinalità differente, non esiste nessuna funzione biunivoca f: A  B.

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)

(2)

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, essendo f surgettiva esiste almeno un elemento aA tale che si abbia f(a)=b. Ma questo elemento aA tale che si abbia f(a)=b è anche unico, perché f è iniettiva.

Se allora associamo all’elemento bB questo unico elemento aA 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 Q è l’insieme dei numeri razionali relativi e se f: Q  Q è la funzione definita da f(x)=(3x+5)/9, è facile verificare che f è iniettiva. Dimostriamo che f è surgettiva: preso un generico elemento bQ (quindi b è un numero razionale relativo), cerchiamo l’esistenza di un elemento aA tale che f(a)=(3a+5)/9=b; si ottiene (nell’incognita a) la soluzione a=(9b-5)/3Q. 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)=(9x-5)/3.

a b c

2 5 7

a b c

(3)

Teorema. Sia f: A  B una funzione biunivoca. Allora la funzione inversa f^–1: B  A è anch’essa biunivoca.

Dimostrazione:

Dimostriamo che f^–1 è iniettiva: se per assurdo esistessero b,cB, bc tali che f^–1(b)= f^–1(c), denotato con a tale elemento f^–1(b)=f^–1(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^–1(b)=f^–1(c) 

f  c

Dimostriamo che f^–1 è surgettiva: dato un elemento generico yA, dobbiamo trovare un elemento xB tale che si abbia f^–1(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^-1 x  

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 xA. Ovviamente la funzione identica è biunivoca.

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 xA, 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 xA l’unico elemento zC si ottiene una nuova funzione con dominio A e codominio C, detta composizione di f e g (o funzione composta di f e g), e indicata con il simbolo gf: A  C. In pratica l’azione di gf è ottenuta applicando f e poi g:

(gf)(x)=z=g(y)=g(f(x))

(notare che la funzione f, che agisce per prima, è scritta per seconda nel simbolo gf).

(4)

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 gf: A  C è descritta graficamente da:

gf

2) Se N è l’insieme dei numeri naturali, Q⁺ l’insieme dei numeri razionali positivi, R⁺ l’insieme dei numeri reali positivi, date le 2 funzioni f: A  B, g: B  C definite dalle formule:

f(x)=x/3, g(x)= x²1

la composizione gf: A  C è definita da:

(gf)(x)=g(f(x))=g(x/3)= ^(x/3⁾²¹= ^(x² ⁹⁾^/⁹

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 gf è iniettiva: se a,bA, ab, 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 (gf)(a) (gf)(b), ossia gf è iniettiva.

Supponiamo ora che f, g siano surgettive e dimostriamo che gf è surgettiva: dato cC, cerchiamo una elemento aA tale che (gf)(a)=c; ma, per la surgettività di g, esiste bB tale che g(b)=c;

inoltre, per la surgettività di f, esiste aA tale che f(a)=b, da cui in totale (gf)(a)=c.

La terza affermazione segue ovviamente dalle prime due.

Calcoliamo la composizione di funzioni in alcuni casi particolari.

1 2 3 4

a b c

5 6 8

1 2 3 4

5 6 8

(5)

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 iBf : A  B.

Per ogni elemento xA si ha (iBf)(x)= iB(f(x))=f(x), e si conclude che le funzioni iBf ed f sono uguali: iBf = 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 fiA : A  B.

Per ogni elemento xA si ha (fiA)(x)= f(iA(x))=f(x), e si conclude che le funzioni fiA ed f sono uguali: fiA = 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^-1f : A  A ff^-1 : B  B

Per ogni elemento xA si ha (f^-1f)(x)= f^-1(f(x))=x, e si conclude che la funzione f^-1f coincide con la funzione identica di A:

f^-1f = iA

Con ragionamento analogo di ha che la funzione ff^-1 coincide con la funzione identica di B:

ff^-1 = iB .