Appunti del Corso: Capitolo 4 - Funzioni e Cardinalità
Definizione di Funzione (o Applicazione)
Una funzione (o applicazione) $f$ da un insieme $A$ (chiamato dominio) a un insieme $B$ (chiamato codominio), indicata con $f: A \to B$, è un tipo particolare di relazione binaria tra $A$ e $B$. Nello specifico, una relazione $f \subseteq A \times B$ è una funzione se soddisfa due condizioni fondamentali:
- Ovunque definita: Per ogni elemento $x \in A$, esiste almeno un elemento $y \in B$ tale che $(x,y) \in f$. (Ogni elemento del dominio deve essere "collegato" a qualcosa nel codominio).
- Funzionale (o Unicità dell'immagine): Per ogni elemento $x \in A$, esiste al massimo un elemento $y \in B$ tale che $(x,y) \in f$. (Ogni elemento del dominio è collegato a *un solo* elemento nel codominio).
Combinando queste due condizioni, diciamo che una relazione $f \subseteq A \times B$ è una funzione se e solo se:
$\forall x \in A, \exists ! y \in B : (x,y) \in f$.
L'unico elemento $y$ associato a $x$ si indica con $f(x)$ e si chiama immagine di $x$ tramite $f$. Scriviamo $y = f(x)$.
Visualizzazione:
Immagina due insiemi di punti, A e B. Una funzione traccia una freccia da ogni punto di A verso esattamente un punto di B.
- Non possono partire due frecce dallo stesso punto in A.
- Nessun punto in A può rimanere senza una freccia in uscita.
- È possibile che più frecce da A arrivino allo stesso punto in B.
- È possibile che alcuni punti in B non siano raggiunti da alcuna freccia.
Proprietà delle Funzioni: Iniettività, Suriettività, Biiettività
Le funzioni possono essere classificate in base a come "mappano" gli elementi del dominio a quelli del codominio.
1. Funzione Suriettiva (o surgettiva)
Una funzione $f: A \to B$ è **suriettiva** (o "su") se ogni elemento del codominio $B$ è immagine di almeno un elemento del dominio $A$. In altre parole, l'immagine della funzione, $f(A) = \{f(x) \mid x \in A\}$, coincide con l'intero codominio $B$.
Formalmente: $f \text{ è suriettiva } \iff \forall y \in B, \exists x \in A : f(x) = y$.
Intuizione: Tutti gli elementi del codominio vengono "raggiunti" da almeno una freccia.
Se $A=\{1,2,3\}$, $B=\{a,b\}$ e $f(1)=a, f(2)=b, f(3)=a$. Questa funzione è suriettiva perché sia $a$ che $b$ sono immagini di qualche elemento di $A$.
Se una funzione $f: A \to B$ è suriettiva, si può dedurre che la cardinalità di $A$ è maggiore o uguale alla cardinalità di $B$ (nel caso di insiemi finiti, $|A| \ge |B|$).
2. Funzione Iniettiva
Una funzione $f: A \to B$ è iniettiva (o "uno-a-uno") se elementi distinti del dominio vengono mappati in elementi distinti del codominio. Cioè, non ci sono due elementi diversi in $A$ che vengono mandati nello stesso elemento in $B$.
Formalmente: $f \text{ è iniettiva } \iff \forall x_1, x_2 \in A, (f(x_1) = f(x_2) \Rightarrow x_1 = x_2)$.
O, equivalentemente (usando la contronominale): $f \text{ è iniettiva } \iff \forall x_1, x_2 \in A, (x_1 \neq x_2 \Rightarrow f(x_1) \neq f(x_2))$.
Intuizione: Non ci sono due frecce che partono da punti diversi in A e arrivano allo stesso punto in B.
Se $A=\{1,2\}$, $B=\{a,b,c\}$ e $f(1)=a, f(2)=c$. Questa funzione è iniettiva. Non è suriettiva perché $b$ non è immagine di nessuno.
Se una funzione $f: A \to B$ è iniettiva, si può dedurre che la cardinalità di $A$ è minore o uguale alla cardinalità di $B$ (nel caso di insiemi finiti, $|A| \le |B|$).
3. Funzione Biiettiva (o Biunivoca)
Una funzione $f: A \to B$ è biiettiva (o biunivoca, o una corrispondenza uno-a-uno) se è sia iniettiva che suriettiva.
Formalmente: $f \text{ è biiettiva } \iff (\forall y \in B, \exists ! x \in A : f(x) = y)$. (Per ogni elemento del codominio, esiste uno ed un solo elemento del dominio che viene mappato in esso).
Intuizione: Ogni elemento di A è accoppiato con un unico elemento di B, e ogni elemento di B è accoppiato con un unico elemento di A. C'è una corrispondenza perfetta.
Se $A=\{1,2,3\}$, $B=\{a,b,c\}$ e $f(1)=a, f(2)=b, f(3)=c$. Questa funzione è biiettiva.
Se esiste una funzione biiettiva $f: A \to B$, allora i due insiemi $A$ e $B$ hanno la stessa cardinalità (stesso "numero" di elementi), e si dicono equipotenti. Scriviamo $|A|=|B|$.
Una funzione biiettiva ammette una funzione inversa $f^{-1}: B \to A$, che è anch'essa biiettiva.
Cardinalità degli Insiemi
La cardinalità di un insieme $A$, denotata con $|A|$, è una misura del "numero di elementi" dell'insieme.
- Per gli insiemi finiti, la cardinalità è semplicemente il numero dei suoi elementi (un numero naturale).
- Due insiemi $A$ e $B$ (finiti o infiniti) si dicono equipotenti (o che hanno la stessa cardinalità) se esiste una funzione biiettiva $f: A \to B$.
Insiemi Numerabili
Un insieme $A$ è detto numerabile (o enumerabile) se è equipotente all'insieme dei numeri naturali $\mathbb{N} = \{0, 1, 2, \dots\}$. In altre parole, se i suoi elementi possono essere messi in una lista infinita (corrispondenza uno-a-uno con i naturali).
La cardinalità degli insiemi numerabili si indica con $\aleph_0$ ("aleph-zero").
L'insieme dei numeri pari $P = \{0, 2, 4, \dots\}$ è numerabile. La funzione $f: \mathbb{N} \to P$ definita da $f(n) = 2n$ è una biiezione. Quindi $|P| = |\mathbb{N}| = \aleph_0$.
Analogamente, l'insieme dei numeri dispari $D$ è numerabile.
Proprietà: L'unione di due insiemi numerabili è numerabile. Il prodotto cartesiano di due insiemi numerabili è numerabile. ($\aleph_0 + \aleph_0 = \aleph_0$; $\aleph_0 \cdot \aleph_0 = \aleph_0$).
Teorema di Cantor
Il Teorema di Cantor afferma che 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 ha implicazioni profonde: significa che non esiste un "insieme di tutti gli insiemi" e che esistono infiniti di grandezza diversa. Ad esempio, $|\mathbb{N}| < |\mathcal{P}(\mathbb{N})|$.
Si dimostra anche che $|\mathcal{P}(\mathbb{N})| = |\mathbb{R}|$, dove $\mathbb{R}$ è l'insieme dei numeri reali. La cardinalità di $\mathbb{R}$ è detta cardinalità del continuo (indicata con $c$ o $\aleph_1$ sotto l'ipotesi del continuo).
La dimostrazione del Teorema di Cantor si fa per assurdo: si suppone che esista una funzione suriettiva $f: A \to \mathcal{P}(A)$ e si costruisce un particolare sottoinsieme di $A$ (chiamato insieme diagonale di Cantor) che non può essere immagine di alcun elemento di $A$ tramite $f$, portando a una contraddizione.
L'insieme diagonale $X$ è definito come $X = \{x \in A \mid x \notin f(x)\}$. Se esistesse $y \in A$ tale che $f(y) = X$, allora si avrebbe:
$y \in X \iff y \notin f(y) \iff y \notin X$, che è una contraddizione.