Capitolo 4: Funzioni e Cardinalità

Dopo aver esplorato insiemi e relazioni, in questo capitolo introduciamo un concetto fondamentale che permea tutta la matematica e l'informatica: la funzione (o applicazione). Le funzioni descrivono una corrispondenza specifica tra elementi di due insiemi. Studieremo poi come le funzioni ci aiutano a confrontare le "dimensioni" degli insiemi, introducendo il concetto di cardinalità, specialmente per gli insiemi infiniti.

4.1 Cos'è una Funzione (o Applicazione)?

Una **funzione** $f$ da un insieme $A$ a un insieme $B$, che scriviamo come $f: A \to B$, è una regola speciale che associa ad ogni elemento dell'insieme $A$ uno ed un solo elemento dell'insieme $B$.

L'insieme $A$ è chiamato il dominio della funzione (l'insieme di "partenza").
L'insieme $B$ è chiamato il codominio della funzione (l'insieme di "arrivo" potenziale).

Se $x$ è un elemento del dominio $A$ (scritto $x \in A$), l'unico elemento $y$ nel codominio $B$ (scritto $y \in B$) che la funzione $f$ associa a $x$ è chiamato immagine di $x$ tramite $f$, e si scrive $y = f(x)$.

Formalmente, una funzione è un tipo particolare di relazione binaria $f \subseteq A \times B$ tale che:

Per ogni $x \in A$, esiste un $y \in B$ tale che $(x,y) \in f$. (Ogni elemento del dominio ha un'immagine; la funzione è definita per tutto il dominio).
Se $(x,y_1) \in f$ e $(x,y_2) \in f$, allora $y_1 = y_2$. (L'immagine di ogni elemento del dominio è unica).

Queste due condizioni insieme significano: $\forall x \in A, \exists ! y \in B : (x,y) \in f$ (per ogni $x$ in $A$, esiste uno ed un solo $y$ in $B$ tale che $x$ è in relazione con $y$ tramite $f$).

Metafora: Pensa a una macchinetta distributrice ($f$). Tu inserisci un codice (l'elemento $x$ del dominio $A$, l'insieme dei codici validi). La macchinetta ti dà un prodotto (l'elemento $y=f(x)$ del codominio $B$, l'insieme dei prodotti disponibili).

Ogni codice valido ($x \in A$) deve erogare un prodotto (la funzione è definita per ogni $x$).
Ogni codice valido ($x \in A$) deve erogare esattamente un tipo di prodotto ($f(x)$ è unico). Non può darti due prodotti diversi per lo stesso codice.
È possibile che codici diversi diano lo stesso prodotto (es. due codici per la stessa bevanda).
È possibile che alcuni prodotti nel distributore (elementi di $B$) non vengano mai scelti da nessun codice.

4.2 Immagine della Funzione e Insieme Immagine

Data una funzione $f: A \to B$:

L'immagine di un elemento $x \in A$ è $f(x) \in B$.
L'insieme immagine (o semplicemente **immagine**) di $f$, indicato con $Im(f)$ o $f(A)$, è il sottoinsieme del codominio $B$ costituito da tutti gli elementi che sono immagine di almeno un elemento di $A$.
$Im(f) = \{y \in B \mid \exists x \in A \text{ tale che } y = f(x)\}$.
Nota che $Im(f) \subseteq B$.

Sia $A = \{1, 2, 3, 4\}$, $B = \{a, b, c, d, e\}$. Sia $f: A \to B$ definita da $f(1)=a, f(2)=b, f(3)=a, f(4)=d$.
Il dominio è $A$. Il codominio è $B$.
L'immagine di $1$ è $a$. L'immagine di $2$ è $b$.
L'insieme immagine è $Im(f) = \{a, b, d\}$. Nota che $c$ ed $e$ sono nel codominio ma non nell'immagine.

4.3 Tipi di Funzioni: Iniettiva, Suriettiva, Biiettiva

Le funzioni possono essere classificate in base a come mettono in corrispondenza gli elementi del dominio con quelli del codominio.

4.3.1 Funzione Iniettiva (o "Uno-a-Uno")

Una funzione $f: A \to B$ è **iniettiva** se ad elementi distinti del dominio $A$ corrispondono sempre elementi distinti del codominio $B$. In altre parole, non succede mai che due elementi diversi di $A$ abbiano la stessa immagine in $B$.

Formalmente, $f$ è iniettiva se:
$\forall x_1, x_2 \in A, (f(x_1) = f(x_2) \Rightarrow x_1 = x_2)$.
Equivalentemente (usando la contronominale, spesso più facile da verificare):
$\forall x_1, x_2 \in A, (x_1 \neq x_2 \Rightarrow f(x_1) \neq f(x_2))$.

Esempio: Sia $f: \mathbb{N} \to \mathbb{N}$ definita da $f(n) = n+1$. Questa funzione è iniettiva. Se $f(n_1) = f(n_2)$, allora $n_1+1 = n_2+1$, che implica $n_1=n_2$.
Controesempio: Sia $g: \mathbb{Z} \to \mathbb{Z}$ definita da $g(x) = x^2$. Questa non è iniettiva, perché ad esempio $g(2)=4$ e $g(-2)=4$, ma $2 \neq -2$.

Se $f: A \to B$ è iniettiva e $A, B$ sono finiti, allora $|A| \le |B|$.

4.3.2 Funzione Suriettiva (o "Su")

Una funzione $f: A \to B$ è suriettiva (o "su $B$") se ogni elemento del codominio $B$ è immagine di almeno un elemento del dominio $A$. In pratica, l'insieme immagine $Im(f)$ coincide con l'intero codominio $B$. Nessun elemento del codominio viene "lasciato fuori".

Formalmente, $f$ è suriettiva se:
$\forall y \in B, \exists x \in A \text{ tale che } f(x) = y$.

Esempio: Sia $A = \{-2, -1, 0, 1, 2\}$ e $B = \{0, 1, 4\}$. Sia $f: A \to B$ definita da $f(x) = x^2$. $f(-2)=4, f(-1)=1, f(0)=0, f(1)=1, f(2)=4$. L'insieme immagine è $Im(f) = \{0, 1, 4\}$, che è uguale al codominio $B$. Quindi $f$ è suriettiva.
Controesempio: Sia $g: \mathbb{N} \to \mathbb{N}$ definita da $g(n) = n+1$. Questa non è suriettiva, perché ad esempio $0 \in \mathbb{N}$ (codominio), ma non esiste alcun $n \in \mathbb{N}$ (dominio) tale che $n+1=0$.

Se $f: A \to B$ è suriettiva e $A, B$ sono finiti, allora $|A| \ge |B|$.

4.3.3 Funzione Biiettiva (o Biunivoca)

Una funzione $f: A \to B$ è biiettiva (o biunivoca, o una corrispondenza uno-a-uno e su) se è sia iniettiva sia suriettiva.

In una funzione biiettiva, ogni elemento del dominio è accoppiato con un unico elemento del codominio, e ogni elemento del codominio è accoppiato con un unico elemento del dominio. C'è una corrispondenza perfetta, "elemento per elemento", tra i due insiemi.

Formalmente, $f$ è biiettiva se:
$\forall y \in B, \exists ! x \in A \text{ tale che } f(x) = y$ (per ogni $y$ nel codominio, esiste uno ed un solo $x$ nel dominio tale che $f(x)=y$).

Esempio: Sia $A = \{1, 2, 3\}$ e $B = \{\text{rosso, verde, blu}\}$. Sia $f: A \to B$ definita da $f(1)=\text{rosso}, f(2)=\text{verde}, f(3)=\text{blu}$. Questa funzione è iniettiva (elementi diversi di A vanno in colori diversi) e suriettiva (tutti i colori in B sono usati). Quindi è biiettiva.

Se esiste una funzione biiettiva $f: A \to B$, allora gli insiemi $A$ e $B$ si dicono **equipotenti** (o che hanno la stessa cardinalità). Questo è un concetto cruciale per confrontare le "dimensioni" degli insiemi, specialmente quelli infiniti.

Una funzione biiettiva $f: A \to B$ ammette sempre una **funzione inversa** $f^{-1}: B \to A$, che è anch'essa biiettiva.

4.4 Cardinalità degli Insiemi: Quanti Elementi?

La **cardinalità** di un insieme $A$, indicata con $|A|$, è una misura del "numero di elementi" che esso contiene.

Per gli **insiemi finiti**, la cardinalità è semplicemente il conteggio dei suoi elementi (un numero naturale: 0, 1, 2, ...). Ad esempio, se $A=\{a,b,c\}$, allora $|A|=3$.
Per gli insiemi infiniti, il concetto di "numero di elementi" diventa più sottile. Diciamo che due insiemi $A$ e $B$ (finiti o infiniti) hanno la stessa cardinalità (o sono equipotenti) se è possibile stabilire una corrispondenza biunivoca (una funzione biiettiva) tra di essi. Scriviamo $|A|=|B|$.

4.4.1 Insiemi Numerabili (o Contabili)

Un insieme $A$ si dice numerabile (o enumerabile, o contabile) se ha la stessa cardinalità dell'insieme dei numeri naturali $\mathbb{N} = \{0, 1, 2, 3, \dots\}$. In pratica, significa che possiamo "mettere in fila" tutti gli elementi di $A$ e associarli uno per uno ai numeri naturali, senza tralasciarne alcuno e senza ripetizioni.

La cardinalità degli insiemi numerabili è indicata con il simbolo $\aleph_0$ (si legge "aleph-zero").

Esempi di insiemi numerabili:

$\mathbb{N}$ stesso (la funzione identità $f(n)=n$ è una biiezione da $\mathbb{N}$ a $\mathbb{N}$).
L'insieme dei numeri interi $\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}$. Anche se sembra "più grande" di $\mathbb{N}$, si può trovare una biiezione.
L'insieme dei numeri pari $P = \{0, 2, 4, \dots\}$. La funzione $f(n)=2n$ da $\mathbb{N}$ a $P$ è biiettiva.
L'insieme dei numeri razionali $\mathbb{Q}$ (le frazioni). Questo è un risultato meno intuitivo ma dimostrabile.

Un insieme è **al più numerabile** se è finito o numerabile.

4.4.2 Insiemi Non Numerabili (Più che Numerabili)

Esistono insiemi infiniti che sono "più grandi" degli insiemi numerabili, cioè per i quali non è possibile stabilire una biiezione con $\mathbb{N}$. Questi insiemi sono detti **non numerabili** (o più che numerabili).

Esempio: L'insieme dei numeri reali $\mathbb{R}$ è non numerabile. La sua cardinalità è detta **cardinalità del continuo**, indicata con $c$ o $\mathfrak{c}$.

4.4.3 Teorema di Cantor e Gerarchia degli Infiniti

Un risultato fondamentale dovuto a Georg Cantor è il Teorema di Cantor, che afferma:
Per qualsiasi insieme $A$ (finito o infinito), la cardinalità di $A$ è strettamente minore della cardinalità del suo insieme delle parti $\mathcal{P}(A)$.

Formalmente: $|A| < |\mathcal{P}(A)|$.

Questo teorema è sorprendente perché implica che, dato un qualsiasi insieme infinito, possiamo sempre costruirne uno "ancora più infinito" prendendo il suo insieme delle parti. Questo crea una gerarchia infinita di "grandezze" di infinito.

Ad esempio, $|\mathbb{N}| < |\mathcal{P}(\mathbb{N})|$. Si può dimostrare che l'insieme delle parti dei numeri naturali, $\mathcal{P}(\mathbb{N})$, ha la stessa cardinalità dell'insieme dei numeri reali $\mathbb{R}$. Quindi, $\aleph_0 < c$.

La dimostrazione del Teorema di Cantor utilizza un elegante argomento per assurdo, noto come **argomento diagonale di Cantor**. Si suppone per assurdo che esista una funzione suriettiva (e quindi potenzialmente biiettiva se $A$ fosse equipotente a $\mathcal{P}(A)$) $f: A \to \mathcal{P}(A)$. Poi si costruisce un particolare sottoinsieme $X_D \subseteq A$ (l'"insieme diagonale") definito come:
$X_D = \{a \in A \mid a \notin f(a)\}$.
Questo $X_D$ è un sottoinsieme di $A$, quindi $X_D \in \mathcal{P}(A)$. Se $f$ fosse suriettiva, dovrebbe esistere un elemento $d \in A$ tale che $f(d) = X_D$. A questo punto ci si chiede: $d \in X_D$?

Se $d \in X_D$, allora per definizione di $X_D$, $d \notin f(d)$. Ma $f(d)=X_D$, quindi $d \notin X_D$. Contraddizione!
Se $d \notin X_D$, allora per definizione di $X_D$, $d \in f(d)$. Ma $f(d)=X_D$, quindi $d \in X_D$. Contraddizione!

Poiché in entrambi i casi si giunge a una contraddizione, l'ipotesi iniziale che $f$ sia suriettiva deve essere falsa. Quindi non può esistere una funzione biiettiva tra $A$ e $\mathcal{P}(A)$, e si conclude che $|A| < |\mathcal{P}(A)|$.

4.5 Esercizi del Capitolo 4

Esercizio 4.1: Identificare Tipi di Funzioni

Per ciascuna delle seguenti funzioni, determina se è iniettiva, suriettiva, biiettiva. Giustifica la tua risposta.

$f: \mathbb{Z} \to \mathbb{Z}$, definita da $f(x) = 2x$.
$g: \mathbb{R} \to \mathbb{R}$, definita da $g(x) = x^3$.
$h: \mathbb{N} \to \mathbb{N}$, definita da $h(x) = x+2$.
$k: \mathbb{R} \to \mathbb{R}^{\ge 0}$ (dove $\mathbb{R}^{\ge 0} = \{y \in \mathbb{R} \mid y \ge 0\}$), definita da $k(x) = x^2$.

Risposte Brevi:

Iniettiva, non suriettiva.
Iniettiva, suriettiva (quindi biiettiva).
Iniettiva, non suriettiva.
Non iniettiva, suriettiva.

Svolgimenti Dettagliati:

a) $f: \mathbb{Z} \to \mathbb{Z}$, $f(x) = 2x$.

Iniettiva: Sì. Se $f(x_1) = f(x_2)$, allora $2x_1 = 2x_2$, che implica $x_1=x_2$.
Suriettiva: No. L'immagine $Im(f)$ contiene solo numeri interi pari. Ad esempio, $1 \in \mathbb{Z}$ (codominio), ma non esiste $x \in \mathbb{Z}$ (dominio) tale che $2x=1$.
Biiettiva: No, perché non è suriettiva.

b) $g: \mathbb{R} \to \mathbb{R}$, $g(x) = x^3$.

Iniettiva: Sì. Se $g(x_1) = g(x_2)$, allora $x_1^3 = x_2^3$. Facendo la radice cubica (che è ben definita e unica per i reali), si ottiene $x_1=x_2$.
Suriettiva: Sì. Per ogni $y \in \mathbb{R}$ (codominio), possiamo trovare $x = \sqrt[3]{y} \in \mathbb{R}$ (dominio) tale che $g(x) = (\sqrt[3]{y})^3 = y$.
Biiettiva: Sì, perché è sia iniettiva che suriettiva.

c) $h: \mathbb{N} \to \mathbb{N}$, $h(x) = x+2$. (Assumiamo $\mathbb{N}=\{0,1,2,\dots\}$)

Iniettiva: Sì. Se $h(x_1) = h(x_2)$, allora $x_1+2 = x_2+2$, che implica $x_1=x_2$.
Suriettiva: No. Ad esempio, $0 \in \mathbb{N}$ (codominio) e $1 \in \mathbb{N}$ (codominio) non sono immagini di alcun $x \in \mathbb{N}$ (dominio), perché $x+2=0$ implicherebbe $x=-2 \notin \mathbb{N}$, e $x+2=1$ implicherebbe $x=-1 \notin \mathbb{N}$. L'immagine è $Im(h) = \{2,3,4,\dots\}$.
Biiettiva: No.

d) $k: \mathbb{R} \to \mathbb{R}^{\ge 0}$, $k(x) = x^2$. (dove $\mathbb{R}^{\ge 0} = \{y \in \mathbb{R} \mid y \ge 0\}$)

Iniettiva: No. Ad esempio, $k(2)=4$ e $k(-2)=4$, ma $2 \neq -2$.
Suriettiva: Sì. Per ogni $y \in \mathbb{R}^{\ge 0}$ (codominio, quindi $y \ge 0$), possiamo trovare $x = \sqrt{y} \in \mathbb{R}$ (dominio) tale che $k(x) = (\sqrt{y})^2 = y$. (Anche $x = -\sqrt{y}$ funziona).
Biiettiva: No.

Esercizio 4.2: Cardinalità e Numerabilità

Indica se i seguenti insiemi sono finiti, numerabili o non numerabili (più che numerabili). Giustifica brevemente.

L'insieme delle lettere dell'alfabeto italiano.
L'insieme dei numeri interi dispari.
L'insieme $\mathcal{P}(\mathbb{N})$ (l'insieme delle parti dei numeri naturali).
L'insieme dei punti su un segmento di retta di lunghezza 1 cm.
L'insieme $A \times B$ dove $A$ è finito e $B$ è numerabile.

Esercizio 4.3: Dimostrazione di Equipotenza

Dimostra che l'insieme dei numeri naturali pari $P = \{0, 2, 4, 6, \dots\}$ è equipotente all'insieme dei numeri naturali $\mathbb{N} = \{0, 1, 2, 3, \dots\}$.