funzioni funzioni iniettive iniettive – – surgettive surgettive

Esercitazione N Esercitazione N .2 .2

31 ottobre

31 ottobre 2006 2006

Funzioni Funzioni

„„

funzioni funzioni iniettive iniettive – – surgettive surgettive

„„

funzioni funzioni bigettive bigettive tra tra insiemi insiemi infiniti infiniti

Cenni di calcolo combinatorio Cenni di calcolo combinatorio

„ „ permutazioni permutazioni – – disposizioni disposizioni - - combinazioni combinazioni

Invertibilit

Invertibilit à à delle funzioni delle funzioni

„ „ inversa inversa destra destra – – inversa inversa sinistra sinistra

ESERCIZIO

1.

Ancora sulle funzioni iniettive , surgettive

1) Sia f: Z→ ZxZ la funzione definita da f(n)=(n

,n).

a)Determinare la controimmagine f

((1,1)).

b)Stabilire se f è iniettiva, surgettiva.

2) Provare che la funzione f:ZxZ→N definita da f(a,b)=|ab|

è surgettiva.

3) Provare che la funzione definita da f: Z → N

⎩ ⎨ ⎧

≤

−

= >

0 n se

n 1

- ) 2n

( n

n se

f 2

0 è bigettiva.

1a) f

((1,1)) = {n ∈ Z | f(n)= (1,1) } = {n ∈ Z | (n

,n) = (1,1) }

= {n ∈ Z | n

= 1 e n= 1) } = {1}

Due coppie (a,b), (c,d) sono uguali se e solo se hanno gli elementi ordinatamente uguali, ossia a=c, c=d

ne

1b) f: Z→ ZxZ la funzione definita da f(n)=(n

,n)

Iniettività : f(x) = f(y) ⇒ x=y

Per def. f(x)=(x

,x), f(y)=(y

,y).

Da (x

,x)=(y

,y) ne segue che ⎩ ⎨ ⎧

=

= y x

y x

quindi ⎩ ⎨ ⎧

=

= +

y x

0 y)

y)(x -

(x

⇒ x=y Ok: f iniettiva

Surgettività: Im(f) = ZxZ

no, ad esempio (-1,1) ∉ Imf

perché non esiste n∈Z t.c. f(n) = (-1,1) ( f(n) =(n

,n)=(-1,1)

⇒ n

=-1 :assurdo in Z).

2) f: ZxZ→ N tale che f(a,b) = |ab| è surgettiva se ∀ n ∈N ∃ (a,b) ∈ ZxZ t.c. f(a,b) = n.

Quindi il quesito è :

∀ n ∈N ∃ (a,b) ∈ ZxZ t.c. |ab| = n ?

sì, basta scegliere ad esempio a=n, b=1 e si è trovato un elemento (n,1) ∈ ZxZ (n ∈Z, perché n ∈N) che va bene !

In pratica si risolve l’equazione |ab| = n dove n è

supposto essere termine noto ed a, b sono le incognite.

Per la surgettività basta trovare una soluzione soltanto, se esiste ! ( Quindi una sola coppia (a, b) ).

3) f: Z N t.c. ⎩ ⎨ ⎧

≤

−

= >

0 n se 2

0 n 1

- ) 2n

( n

n se

f iniettiva

Dalla figura intuitivamente f risulta iniettiva e surgettiva.

0 1 2 3 4

-1 -2

-3

0 1 2 3 4

Z

N

Per provare correttamente l’ iniettività occorre distinguere 3 casi.

I

Se m>0, n≤ 0 in Z (quindi m, n distinti)

⇒ f(m)=2m-1, f(n)=-2n

⇒ f(m) ≠ f(n), perché f(m) è dispari, mentre f(n) è pari.

ok!

II

m ≤ 0, n ≤ 0 , m ≠ n ⇒ f(m) ≠ f(n)

In generale è meglio usare l’implicazione logica equi- valente che fa uso dell ″=″ anziché ″≠″ per poter

applicare le note proprietà dell’uguaglianza rispetto alle operazioni.

Mostriamo quindi che:

f(m) = f(n), m ≤ 0, n ≤ 0 ⇒ m=n

Se f(m) = f(n) con m ≤ 0, n ≤ 0 ⇒ -2m = -2n

⇒ m = n ok!

III

Mostriamo che : m>0, n>0, f(m)=f(n) ⇒ m=n Se f(m) = f(n) con m>0, n>0 ⇒ 2m-1 = 2n-1

⇒ m=n

Conclusione: f è iniettiva.

Proviamo ora la surgettività di f: Z N t.c

⎩ ⎨

⎧

≤

−

= >

0 n se 2

0 n 1

- ) 2n

( n

n se f

Proviamo cioè che vale la proprietà:

∀ b ∈ N ∃ a ∈ Z t.c. f(a)=b

Dobbiamo distinguere i pari dai dispari:

♦ se b ∈ N e b è dispari, b è del tipo b = 2a-1 con a∈N

, ma 2a-1 è proprio f(a) quando a>0 (per def. di f),quindi abbiamo trovato a∈Z t.c. b=f(a) ok!

♦ se b ∈ N e b è pari, dobbiamo trovare a∈ Z t.c. f(a)=b, ossia t. c. –2a = b, con a≤0. Supposto quindi b dato, e a incognita, si ha che

∀ b∈ N, b pari ∃ a= ⁻ ₂ ^b , a∈ Z, t.c. f(a)=b. ok!

O

: La funzione f che abbiamo studiato è

bigettiva e stabilisce quindi una corrispondenza biunivoca tra i

due insiemi infiniti N e Z. Si dice che Z è numerabile, o che ha

la stessa cardinalità di N, nel senso che riusciamo a “contare

fino all’infinito” gli elementi di Z (uno, due, tre, …. ), essendo

Z in corrispondenza biunivoca con N.

ESERCIZIO

2.

Contiamo le funzioni…

Siano A ={1,2,3}, B={1,2,3,4}. Si considerino gli insiemi seguenti

a)

X = {funzioni f: A →B}

b)

Y = {funzioni iniettive f: A →B}

c)

Z = {funzioni iniettive f: A →B tali che f(1)=1}

d)

W = {funzioni surgettive f: A →B}

Dire quanti elementi hanno gli insiemi X, Y, Z,W.

a) f: {1,2,3}→ {1,2,3,4} è una funzione quando ad ogni elemento del dominio fa corrispondere uno ed un solo elemento del codominio.

Ad esempio:

1 → 3 2 → 2 3 → 3

In generale le funzioni da A in B sono |B|

dove con |A| indichiamo la cardinalità dell’insieme A.

f è individuata da una terna ordinata (•,∗,♦) di elementi del codominio (che possono

anche essere ripetuti). Quante sono queste terne? Per ogni elemento abbiamo 4 scelte.

In totale 4⋅4⋅4 = 4

= 64. Quindi |X|=64.

f

b) f: {1,2,3}→ {1,2,3,4} funzione iniettiva: funzione che manda elementi distinti in elementi distinti.

Ad esempio:

f: {1,2,3}→ {1,2,3,4} t.c. 1 →3, 2 →4, 3 →1

f è individuata da una terna ordinata (•,∗,♦) di elementi distinti del codominio.

Quante sono queste possibili terne (f(1),f(2),f(3)) ? Ci sono 4 scelte per il I

elemento f(1) che, una volta

fissato, consente 3 scelte per il II

, e così … 2 scelte per il III

( per l’iniettività! ).

In totale le terne sono : 4 ⋅ 3 ⋅ 2 = 24. Quindi |Y|=24.

Q

E’ una domanda “equivalente” chiedere:

quante sono le possibili assegnazioni di medaglie (oro, argento, bronzo) in una gara a cui partecipano 4

concorrenti ?

Sì, perché…

Le funzioni iniettive f: A →B con A={1,2,3,…k}, |B|=n, (k ≤ n) si chiamano disposizioni (semplici) di n oggetti di classe k , con k ≤ n

( nel nostro esempio:k=3, n=4) e il loro numero è D

= n ⋅ (n-1) ⋅ (n-2) ⋅ ⋅ ⋅ (n-(k-1))

D

= 4 ⋅ 3 ⋅ 2 ( 3 fattori decrescenti consecutivi) . (Cfr. lo schema riassuntivo alle pagine successive).

c) funzioni iniettive f: {1,2,3}→ {1,2,3,4} tali che f(1)=1.

1 → 1

2 → ♣ abbiamo per ♣ 3 scelte ( va escluso 1 )

3 → ♠ abbiamo per ♠ 2 scelte (va escluso 1 e ♣ )

Sono in pratica tante quante le funzioni iniettive di

{2,3}→ {2,3,4}, cioè 3⋅2=6. Quindi |Z|=6.

Se f fosse surgettiva sarebbe Im(f) = B, ma B ha 4 elementi e Imf ha al massimo 3 elementi : assurdo!

⇒ non ci sono f surg.

R

Denominazione Definizione Numero Disposizione con

ripetizione

Funzione : A →B

A={1,2,3,…k}, |B|=n n^k

Disposizione (semplice) Funzione iniettiva: A →B

A={1,2,3,…k}, |B|=n, (k ≤ n) n(n-1)(n-2)…(n-(k-1)) Permutazione

Funzione bigettiva: A →A o funzione bigettiva f :{1,2,3,…,n}→A, n=|A|

n!

Combinazione di classe k di n elementi , k≤n

Sottoinsieme di {1,2,3,…n} di k

elementi

⎟⎟

⎠

⎜⎜ ⎞

⎝

⎛

k

n

d)

ESERCIZIO

3.

… ancora un po’ di calcolo combinatorio

a) Quanti sono i possibili anagrammi della parola “Esami”

( senza tener conto del significato ! ) ?

b) Quanti sono i possibili terni al gioco del lotto ?

c) Quante sono le possibili colonne di 13 al totocalcio ?

a) Sono tutti i possibili modi di “disporre”,tenendo conto dell’ordine, i caratteri “e, s, a, m, i”, o meglio tutti gli elementi dell’insieme {e,s,a,m,i}.

Sono tanti quante le funzioni bigettive

f: A={e,s,a,m,i} → A={e,s,a,m,i}, o equivalentemente g: A={1,2,3,4,5} → A={e,s,a,m,i}, e si chiamano permutazioni di A.

Le permutazioni si possono riguardare come un caso particolare delle disposizioni (semplici), quando n=k.

Il numero delle permutazioni di un insieme di n elementi è:

n(n-1)(n-2) ⋅ ⋅ ⋅ 1 = n! ( n fattoriale ).

Nel nostro caso sono 5! = 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 120.

Notiamo che nel caso finito per f:A→ A si ha :

f bigettiva ⇔ f iniettiva ⇔ f surgettiva

b) Contiamo le possibili terne scelte nell’insieme L={1,2,3,4,…..,90}.

Poiché non conta l’ordine,ma solo gli elementi stessi ( non ripetuti), sono tutti i possibili sottoinsiemi di 3 elementi di L.

Si chiamano “ combinazioni” di classe k degli n elementi ( qui k=3, n= 90 ).

Il numero delle combinazioni di n elementi di classe k ( k≤ n) è C

= ⎟⎟⎠ ⎞

⎜⎜ ⎝

⎛ k n =

k!

1)) (k (n 2) 1)(n

n(n− − ⋅⋅⋅ − −

(al numeratore:k fattori decrescenti).

N.B. E’ la formula ⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛ k

n = (n k)! k!

n!

− semplificata.

Nel nostro caso C

= ⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛ 3

90 = 3 ! 88 89 90 ⋅ ⋅

= 3 2 1 88 89 90

⋅

⋅

⋅

⋅ =117.480.

Curiosità : la probabilità di fare terno, giocando 1 sola volta è pari a

480 117

1

. ∼ 0.000008512 ossia ∼ 0.0008512 %

c) Si tratta di contare tutte le funzioni f: {1,2,3,….,13}→ {1,x,2}.

Il loro numero è quindi 3

.

ESERCIZIO

4.

Funzioni composte

Sono date la funzione f:ZxZ →Z definita da f((x,y)) =x-y e la funzione g:Z →Z xZ definita da g(n) = (n+1,3n).

Stabilire il dominio e il codominio delle funzioni f ○ g, g ○ f e darne la rispettiva definizione.

La funzione f ○ g è definita poiché il codominio di g coincide con il dominio di f.

Z ⎯ ⎯→

ZxZ ⎯ ⎯→

Z

n ⎯ ⎯→

( n + 1 , 3 n )

( x , y ) ⎯ ⎯→

x − y

n g(n) = (n+1,3n) f((n+1,3n)= n+1-3n=1-2n

Z ⎯ ⎯ →

⎯

Z t.c. f ○ g (n) = 1-2n.

Analogamente si trova ZxZ ⎯ ⎯ →

⎯

ZxZ t.c. g○f (x,y)=(x-y+1,3x-3y).

Sta in “codominio di g” = “dominio di f”

dominio codominio

ESERCIZIO

5.

Inversi destri – inversi sinistri

Sia f: ù→ù la funzione definita da f(n) =n+1.

a) Stabilire se ha inversa sinistra e in caso affermativo determinarne una.

b) Stabilire se ha inversa destra.

c) Stabilire se è invertibile.

a) Data f: ù →ù si dice inversa sinistra di f una funzione g: ù →ù t.c. g ○ f = Id

.

Vale la seguente proprietà : f ha inversa sinistra ⇔ f è iniettiva

La funzione f: ù →ù definita da f(n) =n+1 è iniettiva se: f(x) = f(y) ⇒ x= y.

Ma f(x) = x+1, f(y) =y+1, e da x+1=y+1 discende x=y,

quindi f è iniettiva ed ha inversa sinistra.

Troviamola ( o troviamone una ! ).

ù ù ù 0 → 1 → 0

1  → 2 → 1 2  → 3 → 2 . → . → .

Problema

g non è stata “automaticamente” definita in 0.

Come definiamo g(0) = ?

Come g(0) va bene un qualsiasi numero naturale, poiché g(0) non interviene nel fare la composizione.

Quindi scriviamo la definizione di una delle infinite g inverse sinistre di f.

Ad esempio: g: ù ^→ ù t.c. g(n)= _⎩ ^{⎨ ⎧} ₀ ^{n − 1} _se ^se _n ⁿ ₌ ^{≥ 1} ₀

Oppure anche g(n)= |n-1| va bene, oppure … g

f

Imponiamo la

condizione g ○ f = Id

b) Data f: ù →ù si dice inversa destra di f una funzione g: ù →ù t.c. f ○ g = Id

.

Vale la seguente proprietà :

f ha inversa destra ⇔ f è surgettiva.

f è surgettiva se

∀ y∈ù (codominio) ∃ x∈ù (dominio) t.c. f(x) = y.

Ma dallo schema fatto vediamo che 0 ∉ Im(f) , in

altre parole, scelto y=0 (nel condominio di f ) non esiste x ∈ ù (dominio) t.c. f(x) = 0.

Quindi f non è surgettiva e di conseguenza non ha inversa destra.

c) f è invertibile se ∃ g: ù →ù tale che f○g=Id

e g○f=Id

Per b) f non è invertibile perchè non ha inversa destra.

O equivalentemente, usando la proprietà (cfr. teoria)

"f invertibile ⇔ f è bigettiva"

si ricava che f non è invertibile, perché non è bigettiva.