In matematica discreta una funzione non è una formula, ma una regola che associa a ogni elemento di un insieme esattamente un elemento di un altro. Questa visione più generale permette di ragionare su codifiche, tabelle, identificativi e funzioni hash con lo stesso linguaggio. Le tre proprietà di iniettività, suriettività e biiettività rispondono a domande molto pratiche: si perde informazione? si coprono tutti i valori? si può tornare indietro?
Definizione
Una funzione f: A → B associa a ogni elemento a di A uno e un solo elemento f(a) di B.
- A è il dominio.
- B è il codominio.
- L'immagine è l'insieme dei valori effettivamente raggiunti: f(A) = {f(a) | a ∈ A}, che è un sottoinsieme di B.
Formalmente, f è una relazione tra A e B in cui ogni elemento di A compare come primo elemento in esattamente una coppia. Due condizioni: nessun elemento del dominio resta senza valore, e nessuno ne ha due.
Esempio: la funzione che associa a ogni utente il suo reparto è una funzione (ogni utente ha un solo reparto); quella che associa a ogni reparto un suo dipendente non lo è, perché un reparto ha molti dipendenti e ce ne possono essere di vuoti.
Iniettiva
f è iniettiva se elementi diversi hanno immagini diverse: se a ≠ a′ allora f(a) ≠ f(a′). Equivalentemente: se f(a) = f(a′) allora a = a′.
Una funzione iniettiva non perde informazione: dal valore si risale all'elemento di partenza. Esempi:
- f(n) = 2n sugli interi è iniettiva.
- f(n) = n² sugli interi non lo è: f(3) = f(−3) = 9.
- Il codice fiscale, come funzione dalle persone alle stringhe, è pensato per essere iniettivo; le omocodie, gestite con la sostituzione di alcuni caratteri, sono proprio i casi in cui la regola di base non lo sarebbe.
Una chiave primaria in un database è, per definizione, un attributo che rende iniettiva la funzione dalle righe ai valori della chiave.
Suriettiva
f è suriettiva se ogni elemento del codominio è raggiunto: per ogni b ∈ B esiste almeno un a con f(a) = b. In altre parole l'immagine coincide con il codominio.
- f(n) = n mod 7, dagli interi a {0, 1, …, 6}, è suriettiva.
- f(n) = 2n dagli interi agli interi non lo è: i dispari non vengono mai raggiunti.
La suriettività dipende dal codominio scelto. f(n) = 2n è suriettiva se la si considera come funzione dagli interi ai numeri pari.
Biiettiva
f è biiettiva se è sia iniettiva sia suriettiva: ogni elemento del codominio è raggiunto da esattamente un elemento del dominio. Le biiezioni sono le funzioni che si possono invertire: esiste f⁻¹: B → A con f⁻¹(f(a)) = a e f(f⁻¹(b)) = b.
Esempi informatici di biiezioni:
- la conversione tra un numero e la sua rappresentazione esadecimale;
- la codifica Base64 tra sequenze di byte e stringhe Base64 valide;
- un cifrario a blocchi con chiave fissata, che deve essere biiettivo sui blocchi, altrimenti non si potrebbe decifrare.
Il legame con le cardinalità
Per insiemi finiti, le tre proprietà impongono vincoli sulle dimensioni:
| Se f: A → B è… | allora |
|---|---|
| iniettiva | |A| ≤ |B| |
| suriettiva | |A| ≥ |B| |
| biiettiva | |A| = |B| |
La prima riga, letta al contrario, è il principio dei cassetti: se |A| > |B|, nessuna funzione da A a B può essere iniettiva. È il motivo per cui una funzione hash, che porta input di lunghezza arbitraria in un'uscita di lunghezza fissa, ha necessariamente delle collisioni. Una buona funzione hash crittografica non le evita: le rende soltanto difficilissime da trovare.
Un'altra conseguenza utile: se |A| = |B| ed entrambi sono finiti, iniettiva e suriettiva si equivalgono. Basta verificarne una per avere la biiezione. Questo non vale per gli insiemi infiniti, come mostra f(n) = 2n.
Composizione
Date f: A → B e g: B → C, la composizione g ∘ f: A → C è definita da (g ∘ f)(a) = g(f(a)). Le proprietà si conservano:
- composizione di iniettive è iniettiva;
- composizione di suriettive è suriettiva;
- composizione di biiezioni è una biiezione, e (g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹.
L'ordine inverso della formula ha un senso pratico: per annullare «prima comprimi, poi cifra» si deve prima decifrare e poi decomprimere.
Un controllo in Python
Per funzioni su domini finiti, rappresentate come dizionari, le proprietà si verificano in una riga:
def iniettiva(f):
return len(set(f.values())) == len(f)
def suriettiva(f, codominio):
return set(f.values()) == set(codominio)
In sintesi
- Una funzione associa a ogni elemento del dominio esattamente un elemento del codominio.
- Iniettiva: niente collisioni, nessuna perdita di informazione; suriettiva: tutto il codominio è coperto.
- Biiettiva significa invertibile, come le codifiche e i cifrari.
- Se il dominio è più grande del codominio non può esserci iniettività: da qui le collisioni degli hash.
- L'inversa di una composizione si ottiene invertendo i passi in ordine opposto.
