Esercitazione N Esercitazione N .2 .2
31 ottobre
31 ottobre 2006 2006
Rosalba
Rosalba BaratteroBarattero
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
ESERCIZIOC1.
Ancora sulle funzioni iniettive , surgettive
1) Sia f: Z→ ZxZ la funzione definita da f(n)=(n2,n).
a)Determinare la controimmagine f−1((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,1)) = {n ∈ Z | f(n)= (1,1) } = {n ∈ Z | (n2,n) = (1,1) }
= {n ∈ Z | n2 = 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)=(n2,n)
Iniettività : f(x) = f(y) ⇒ x=y
Per def. f(x)=(x2,x), f(y)=(y2,y).
Da (x2,x)=(y2,y) ne segue che ⎩⎨⎧
=
= y x
y x2 2
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) =(n2,n)=(-1,1)
⇒ n2 =-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
Dallafigura intuitivamente f risulta iniettiva e surgettiva.
Per provare correttamente l’ iniettività occorre distinguere 3 casi.
0 1 2 3 4
-1 -2 -3
0 1 2 3 4
Z
N
I CASO
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 CASO
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 CASO
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= −2b , a∈ Z, t.c. f(a)=b. ok!
OSSERVAZIONE : 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
ESERCIZIOC2.
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||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 = 43 = 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.
QUESITO
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 è Dn,k = n ⋅ (n-1) ⋅ (n-2) ⋅ ⋅ ⋅ (n-(k-1))
D4,3 = 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.
RIEPILOGO
Denominazione Definizione Numero Disposizione con
ripetizione
Funzione : A →B
A={1,2,3,…k}, |B|=n nk
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) ESERCIZIOC3.
… 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) è Cn,k = ⎟⎟⎠⎞
⎜⎜⎝
⎛ 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 C90,3 = ⎟⎟⎠
⎜⎜ ⎞
⎝
⎛ 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 117480
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 313 .
ESERCIZIOC4.
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 ⎯⎯→g ZxZ⎯⎯→f Z
n⎯⎯→g (n +1,3n)
(x,y)⎯⎯→f x− y
n g(n) = (n+1,3n) f((n+1,3n)= n+1-3n=1-2n
Z ⎯⎯ →f⎯og Z t.c. f ○ g (n) = 1-2n.
Analogamente si trova ZxZ⎯⎯ →g⎯of ZxZt.c. g○f (x,y)=(x-y+1,3x-3y).
Sta in “codominio di g” = “dominio di f”
dominio codominio
ESERCIZIOC5.
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)= ⎩⎨⎧0n −1 sese nn=≥10
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.