Bigettività
Inviato: 30 mar 2012, 14:57
Siano$ f,g $ due funzioni di $ N $ in sè, con la proprietà che $ f(g(f(n)))=n $ per ogni numero naturale $ n $. Provare che $ f $ e $ g $ sono bigettive.
Cominciamo col dimostrare che $ f(n) $ è iniettiva. La tesi è vera sempre se lo è in qualunque intervallo da $ 0 $ a $ N $ arbitrario (in pratica, non è possibile trovare un intervallo tale che contiene valori distinti di $ n $ a cui corrispondono eguali valori di $ f(n) $). In questo intervallo vi sono esattamente $ N $ valori distinti di $ n $, a cui corrispondono $ a \leq N $ valori distinti di $ f(n) $, a cui corrispondono $ b \leq a \leq N $ valori distinti di $ g(f(n)) $, a cui corrispondono $ c \leq b \leq a \leq N $ valori distinti di $ f(g(f(n)))=n $. Ma deve valere l'uguaglianza, perciò $ c=N $, e in sintesi a ogni valore di $ n $ corrisponde un solo valore di $ f(n) $
Ora dimostriamo l'iniettività di $ g $.
$ f(g(f(n)))=n $
applico a entrambi i membri la funzione composta f(g(n))
$ f(g(f(g(f(n)))))=f(g(n)) $
ma $ f(g(f(n)))=n $ per ogni $ n $. Quindi:
$ g(f(n))=f(g(n) $ (c'è UN SOLO $ g(f(n)) $ che può essere sostituito nell'argomento della seconda $ f $ in modo che la relazione sia vera, e questo equivale a $ f(g(n)) $)
sostituiamo $ f(n) $ a $ n $ e abbiamo
$ g(f(f(n))=n $
al che possiamo tornare ad applicare il ragionamento di prima e concludere che $ g(n) $ è iniettiva.
Concludiamo mostrando che entrambe le funzioni sono suriettive. $ f(g(f(n)))=n $ ci dice che possiamo dare qualsiasi valore naturale a n, cosicché al variare di un valore $ k $ (che si calcola come $ g(f(n)) $), $ f(k) $ genera tutti i numeri naturali. Stesso discorso per $ g(f(f(n))=n $ e $ g $. Concludiamo che ogni valore del codominio è immagine di un qualche valore nel dominio, ed entrambe le funzioni sono suriettive.
