Una relazione \(f \subseteq A \times B\) si dice funzione da \(A\) in \(B\) se
per ogni \(a \in A\) c’è un \(b \in B\) tale che \((a , b ) \in f\) (ovvero \(dom(f) = A\)), e
se \(( a , b_{1} ) \in f\) e \(( a , b_{2} ) \in f\), allora \(b_{1} = b_{2}\).
In questo caso scriveremo \(f \colon A \to B\) e l’unico \(b \in B\) tale che \(( a , b ) \in f\) si indica con \(f ( a )\).
Se \(f \colon A \to B\) è una funzione
\(A = dom(f)\) si dice dominio della funzione \(f\);
\(B\) si dice codominio (da non confondersi con il range di \(f\)).
Immagine
Sia \(f \colon A \to B\) una funzione.
L’elemento \(f(a)\) si dice valore di \(f\) su \(a\), oppure immagine di \(a\) mediante \(f\).
L’insieme
| \[\mathrm{rng}\] | \[=\] | \[\left \{f(a) \boldsymbol\mid a \in A \right\}\] |
|---|---|---|
| \[\] | \[=\] | \[\left \{b \in B \boldsymbol\mid \exists a \in A (f(a) = b) \right\}\] |
Dato \(C \subseteq A\), l’insieme
| \[f[C]\] | \[=\] | \[\left \{f(a) \boldsymbol\mid a \in C \right\}\] |
|---|---|---|
| \[\] | \[=\] | \[\left \{b\in B \boldsymbol\mid \exists a \in C (f(a) = b) \right\}\] |
Preimmagine
Sia \(f \colon A \to B\) una funzione.
La preimmagine o controimmagine di un elemento \(b \in B\) è l’insieme \[f^{-1}[\{b\}] = \left \{a \in A \boldsymbol\mid f(a) = b \right\}.\] Con un leggero abuso di notazione, scriveremo spesso \(f^{-1}(b)\) invece di \(f^{-1}[\{b\}]\).
Più in generale, se \(D \subseteq B\) l’insieme \[\begin{aligned} f^{-1}[D] & = \left \{a \in A \boldsymbol\mid f(a) \in D \right\} \\ & = \bigcup_{b \in D}f^{-1}(b)\end{aligned}\] è la preimmagine o controimmagine di \(D\).
Come si definisce una funzione?
Una funzione \(f \colon A \to B\) può essere descritta in vari modi:
fornendo un elenco di tutte le coppie \((a,b) \in A \times B\) tali che \((a,b) \in f\), ovvero tali che \(b = f(a)\);
Esempio
Sia \(A = \{ a,b,c\}\) e \(B = \{ 0,1 \}\). Allora la lista \[\begin{aligned} f(a) & = 0 \\ f(b) & = 1 \\ f(c) & = 0\end{aligned}\] descrive in maniera univoca una funzione \(f \colon A \to B\).
fornendo una “regola” che permette di determinare i valori di \(f\) su ciascun \(a \in A\);
Esempio
Sia \(A = B = \mathbb{R}\). Allora la scrittura \[f(x) = x^2 + 3\] descrive in maniera univoca una funzione \(f \colon \mathbb{R} \to \mathbb{R}\), ovvero la funzione che manda un generico numero reale \(r \in \mathbb{R}\) nel numero reale \(r^2 + 3\).
un mix delle due.
Esempio
Sia \(A = B = \mathbb{R}\). Allora la scrittura \[f(x) = \begin{cases} \frac{1}{x} & \text{se } x \neq 0 \\ \pi & \text{se } x = 0 \end{cases}\] descrive in maniera univoca una funzione \(f \colon \mathbb{R} \to \mathbb{R}\) fornendo in alcuni casi il valore esplicito della funzione e in altri casi una “regola” per calcolarne il valore.
Spesso useremo la notazione
\(f \colon A \to B\), \(a \mapsto f(a)\)
per dire che \(f\) è una funzione da \(A\) in \(B\) che manda un generico elemento \(a \in A\) nel valore corrispondente \(f(a) \in B\).
Esempio La scrittura
\(f \colon \mathbb{N} \to \mathbb{N}\), \(n \mapsto 2n\)
indica che \(f\) è la funzione da \(\mathbb{N}\) in se stesso che manda ogni numero naturale nel suo doppio.
Data una funzione \(f \colon A \to B\) e un insieme \(C \subseteq A\), la funzione
\(f \restriction C \colon C \to B\) , \(c \mapsto f(c)\)
si dice restrizione di \(f\) a \(C\).
Si osservi che
\(dom(f \restriction C) = C\) e \(\mathrm{rng}(f \restriction C) = f[C]\).
Date due funzioni \(f \colon A \to B\) e \(g \colon B \to C\), la composizione di \(f\) e \(g\) è la funzione
\(g \circ f \colon A \to C\), \(a \mapsto g(f(a))\).
Ad esempio, siano
\(f \colon \mathbb{R} \to \mathbb{R}\), \(x \mapsto x^2\)
e
\(g \colon \mathbb{R} \to \mathbb{R}\), \(x \mapsto 2x+3\).
Allora \(g \circ f\) è anch’essa una funzione da \(\mathbb{R}\) in \(\mathbb{R}\). Per calcolarne i valori si procede come segue: \[(g \circ f) (2) = g(f(2)) = g(2^2) = g(4) = 2 \cdot 4 + 3 = 11.\] Più in generale, per ogni \(x \in \mathbb{R}\) \[(g \circ f)(x) = g(f(x)) = g(x^2) = 2x^2+3.\]
Le funzioni della forma \(f \colon A^n \to A\) vengono a volte dette operazioni \(n\)-arie su \(A\).
Esempio
La somma \(+\) tra numeri interi è una funzione \(+ \colon \mathbb{N}^2 \to \mathbb{N}\), ovvero un’operazione binaria su \(\mathbb{N}\). Lo stesso vale per il prodotto, o quando si considerano queste operazioni su altri insiemi numerici.
Se \(* \colon A \times A \to A\) è un’operazione binaria su \(A\) spesso scriveremo \(a * b\) invece di \(* (a,b)\) (ad esempio, \(a + b\) al posto di \(+ (a,b)\)).
Attenzione! La differenza non è un’operazione binaria su \(\mathbb{N}\), in quanto non è definita per tutti le coppie in \(\mathbb{N}^2\). è invece un’operazione binaria su \(\mathbb{Z}\), \(\mathbb{Q}\) o \(\mathbb{R}\).
Una funzione \(f \colon A \to B\) si dice
se da \(a_{1} \neq a_{2}\) segue che \(f ( a_{1} ) \neq f ( a_{2} )\), o, equivalentemente, se da \(f ( a_{1} ) = f ( a_{2} )\) segue che \(a_{1} = a_{2}\);
se ogni \(b \in B\) è della forma \(f ( a )\) per qualche \(a \in A\) (equivalentemente, \(\mathrm{rng}(f) = B\));
se è iniettiva e suriettiva.
Per brevità diremo che \(f\) è una
iniezione se è una funzione iniettiva;
suriezione se è una funzione suriettiva;
biezione se è una funzione biettiva.
Osservazioni
Se \(f \colon A \to A\) con \(A\) finito si ha che \(f\) è una biezione se e solo se \(f\) è una iniezione se e solo se \(f\) è una suriezione. Lo stesso vale per le funzioni \(f \colon A \to B\) in cui \(A\) e \(B\) sono insiemi finiti con lo stesso numero di elementi.
Se \(f \colon A \to B\) è iniettiva allora \(f \colon A \to \mathrm{rng}(f)\) (ovvero la stessa \(f\), ma vista come funzione da \(A\) nella sua immagine) è una biezione.
Date \(f \colon A \to B\) e \(g \colon B \to C\), si ha che se sia \(f\) che \(g\) sono iniettive anche \(g \circ f\) lo è, e se \(f\) e \(g\) sono entrambe suriezioni anche \(g \circ f\) lo è. In particolare, la composizione di due biezioni è una biezione.
Sia \(f \colon A \to B\) una funzione. Allora \(f\) è un’iniezione se e solo se \(f^{-1}(b)\) contiene al più un elemento per ogni \(b \in B\), ed è una suriezione se e solo se \(f^{-1}(b) \neq \emptyset\) per ogni \(b \in B\).
Poichè una funzione \(f \colon A \to B\) è, per definizione, una relazione \(f \subseteq A \times B\), possiamo formare la sua relazione inversa \(f^{-1} \subseteq B \times A\), dove \((b,a) \in f^{-1}\) se e solo se \((a,b) \in f\), ovvero se e solo se \(f(a) = b\). Tuttavia non è detto che \(f^{-1}\) sia anch’essa una funzione da \(B\) in \(A\):
se \(f\) non è iniettiva, allora ci sono \(a,a' \in A\) distinti tali che \(f(a) = f(a') = b\) per qualche \(b \in B\): quindi sia \((b,a)\) che \((b,a')\) appartengono a \(f^{-1}\), perciò \(f^{-1}\) non è una funzione (ci sarebbero almeno due valori di \(f^{-1}\) su \(b\));
se \(f\) non è suriettiva, allora esiste \(b \in B \setminus \mathrm{rng}(f)\): quindi non esiste alcun \(a \in A\) tale che \((b,a) \in f^{-1}\), ovvero \(f^{-1}\) non può essere una funzione con dominio \(B\).
Dunque una funzione \(f \colon A \to B\) si può invertire (ovvero è tale che la sua relazione inversa \(f^{-1}\) è ancora una funzione) solo se è iniettiva e anche in questo caso il dominio di \(f^{-1}\) è \(\mathrm{rng}(f)\) e non necessariamente tutto \(B\).
Definizione Se \(f \colon A \to B\) è una funzione iniettiva, allora la sua inversa è la funzione \[f^{-1} \colon \mathrm{rng}(f) \to A\] che manda ciascun \(b \in \mathrm{rng}(f)\) nell’unico elemento in \(f^{-1}(b)\).
Si osservi \(f^{-1}\) è sempre iniettiva (poichè \(f\) era una funzione) e suriettiva (poichè \(dom(f) = A\)), ovvero \(f^{-1}\) è una biezione tra \(\mathrm{rng}(f)\) e \(A\).
Osservazione Quando \(f\) è anche suriettiva (ovvero una biezione) si ha che \(\mathrm{rng}(f) = B\): quindi in questo caso \(dom(f^{-1}) = B\). Perciò l’inversa di una biezione \(f \colon A \to B\) è a sua volta una biezione \(f^{-1} \colon B \to A\).
Osservazione 1 Tecnicamente, quando \(f \colon A \to B\) è una funzione iniettiva e \(b \in \mathrm{rng}(f)\) la notazione \(f^{-1}(b)\) è lievemente ambigua. Può infatti indicare
la preimmagine dell’elemento \(b\) mediante \(f\), ovvero l’insieme \(\{ a \}=f^{-1}[\{b\}] \subseteq A\) con \(a \in A\) unico tale che \(f(a) = b\) (l’unicità di \(a\) deriva dal fatto che \(f\) è iniettiva): in accordo con la notazione introdotta in precedenza, infatti, la preimmagine \(f^{-1}[\{ b \}]\) di \(b\) si denota anche con \(f^{-1}(b)\);
l’immagine di \(b\) mediante la funzione inversa \(f^{-1}\), ovvero l’elemento \(a \in A\) tale che \(f^{-1}(b)=a\): per definizione, \(a\) è l’unico elemento tale che \(f(a) = b\).
Sarà il contesto a chiarire quale dei due significati dare a tale espressione.
Se \(f \colon X\to Y\) e \(g \colon Z\to W\) sono entrambe iniezioni (suriezioni, biezioni) allora lo è anche la funzione prodotto
\(f\times g \colon X\times Z\to Y\times W\), \((x,z) \mapsto (f(x),g(z))\) .
Sia \(h\) la funzione prodotto \(f \times g\), cosicchè \(h(x,z) = (f(x),g(z))\).
Fissiamo \((x,z) , (x',z') \in X \times Z\). Se \(h(x,z) = h(x',z')\), allora \((f(x),g(z)) = (f(x'),g(z'))\), da cui \(f(x) = f(x')\) e \(g(z) = g(z')\). Poichè \(f\) e \(g\) sono entrambe iniettive, si ha \(x = x'\) e \(z = z'\), perciò \((x,z) = (x',z')\).
Consideriamo un generico \((y,w) \in Y \times W\). Poichè \(f\) e \(g\) sono suriezioni, esistono \(x \in X\) e \(z \in Z\) tali che \(f(x) = y\) e \(g(z) = w\). Allora \(h (x,z) = (y,w)\).
Alcuni esempi ed esercizi
Esempio L’operazione di somma tra numeri naturali è una funzione binaria
\(f \colon \mathbb{N}^2 \to \mathbb{N}\), \((n,m) \mapsto n+m\).
è una funzione suriettiva perchè ogni \(n \in \mathbb{N}\) è immagine, ad esempio, della coppia \((n,0)\), ma non è iniettiva (quindi neanche biettiva) perchè, ad esempio, \((1,1) \neq (0,2)\) ma \(f(1,1) = 1+1 = 0+2 = f(0,2)\).
Esempio La funzione (unaria)
\(f \colon \mathbb{N} \to \mathbb{N}\), \(n \mapsto 2n\)
è iniettiva poichè se \(2n = 2m\) allora \(n = m\), ma non è suriettiva (quindi neanche biettiva) perchè i numeri dispari non sono immagine mediante \(f\) di alcun numero naturale.
Esempio La funzione
\(f \colon \mathbb{R} \to \mathbb{R}\), \(x \mapsto x^2\)
non è nè iniettiva (ad esempio, \(-1 \neq 1\) ma \(f(-1) = (-1)^2 = 1^2 = f(1)\)), nè suriettiva (i numeri reali negativi non sono immagine mediante \(f\) di alcun numero reale: \(x^2\) è sempre \(\geq 0\)).
Esempio Dati \(a, b \in \mathbb{R}\) con \(a \neq 0\), consideriamo la funzione
\(f \colon \mathbb{R} \to \mathbb{R}\), \(x \mapsto ax+b\).
è una iniezione poichè se \(ax+b = ay +b\) allora \(x = y\), ed è una suriezione poichè per ogni \(y \in \mathbb{R}\) si ha che \(y = f(x)\) con \(x = \frac{y-b}{a}\). Quindi \(f\) è una biezione.
Dimostrare che la funzione “moltiplicazione”
\(f \colon \mathbb{N}^2 \to \mathbb{N}\), \((n,m) \mapsto n \cdot m\)
è suriettiva ma non iniettiva.
La funzione è suriettiva perchè per ogni \(n \in \mathbb{N}\) si ha \(f(1,n) = 1 \cdot n = n\).
Non è iniettiva perchè, ad esempio, \(f(3,4) = 3 \cdot 4 = 12 = 2 \cdot 6 = f(2,6)\).
(Per mostrare che \(f\) non è iniettiva si può anche semplicemente osservare che \(f(n,0) = 0\) per ogni \(n \in \mathbb{N}\), oppure che \(f(n,m) = f(m,n)\) per ogni \(n,m \in \mathbb{N}\).)
Dimostrare che la funzione
\(f \colon \mathbb{N} \to \mathbb{N}\), \(n \mapsto 2^n\)
è iniettiva ma non suriettiva.
L’iniettività è ovvia: se \(n \neq m\) allora \(2^n \neq 2^m\) (se \(n < m\) allora \(2^m = 2^n \cdot 2^{m-n} \geq 2^n \cdot 2 > 2^n\)).
La funzione \(f\) non è suriettiva perchè, ad esempio, \(3 \notin \mathrm{rng}(f)\).
Siano \(\mathbb{P} = \mathopen \{n \in \mathbb{N} \boldsymbol\mid n \text{ è pari} \mathclose\}\) e \(\mathbb{D} = \mathopen \{n \in \mathbb{N} \boldsymbol\mid n \text{ è dispari} \mathclose\}\). Dimostrare che
\(f \colon \mathbb{P} \to \mathbb{D}\), \(n \mapsto n+1\)
è una biezione.
Iniettività: Ovvia, se \(f(n) = f(m)\) (ovvero \(n+1 = m+1\)) allora \(n = m\).
Suriettività: Se \(k \in \mathbb{D}\) allora \(k \neq 0\): segue che \(n = k-1 \in \mathbb{P}\) e \(f(n) = k\).
Essendo \(f\) sia iniettiva che suriettiva, è una biezione.
Siano \(\mathbb{P} = \mathopen \{ n \in \mathbb{N} \boldsymbol\mid n \text{ è pari} \mathclose\}\) e \(\mathbb{D} = \mathopen \{n \in \mathbb{N} \boldsymbol\mid n \text{ è dispari} \mathclose\}\). Dimostrare che la funzione
\(f \colon \mathbb{D} \to \mathbb{P}\), \(n \mapsto n+1\)
è iniettiva ma non suriettiva.
Il fatto che la funzione sia iniettiva è ovvio (vedi slide precedente).
La funzione non è invece suriettiva perchè \[\mathrm{rng}(f) = \left \{n+1 \boldsymbol\mid n \in \mathbb{D} \right\} = \mathbb{P} \setminus \{ 0 \},\] perciò \(0 \in \mathbb{P}\) ma \(0 \notin \mathrm{rng}(f)\).
Dimostrare che
\(f \colon \mathbb{N}^2 \to \mathbb{N}\), \((n,m) \mapsto 2^n(2m+1) - 1\)
è una biezione.
Fatto. Ogni \(k > 0\) si scrive in maniera unica come \(2^n (2m+1)\). Infatti, se \(n \in \mathbb{N}\) è massimo tale che \(2^n \mathrel{|} k\), allora \(k = 2^n \cdot l\) con \(l\) dispari, per cui \(l = 2m+1\) per qualche \(m \in \mathbb{N}\).
Iniettività. Siano \((n,m), (n',m') \in \mathbb{N}^2\) tali che \(f(n,m) = f(n',m')\), ovvero \(2^n(2m+1)-1 = 2^{n'} (2m'+1)-1\). Allora \(k = 2^n(2m+1)\) e \(k' = 2^{n'} (2m'+1)\) sono \(> 0\), e \(k = k'\) (per l’uguaglianza precedente). Per l’unicità della scrittura osservata nel Fatto precedente, necessariamente \(n = n'\) e \(m = m'\), ovvero \((n,m) = (n',m')\).
Suriettività. Per ogni \(j \in \mathbb{N}\), si ha che \(k = j+1 > 0\). Per il Fatto precedente, ci sono \(n,m \in \mathbb{N}\) tali che \(k = 2^n(2m+1)\). Segue che \[f(n,m) = 2^n (2m+1)-1 = k-1 = (j+1)-1 = j,\] perciò \(j \in \mathrm{rng}(f)\).
Sia \(\mathbb{N}^{< \mathbb{N}} \stackrel{\text{def}}{=}\bigcup_{n \in \mathbb{N}} \mathbb{N}^n\) l’insieme di tutte le tuple di numeri naturali (di lunghezza arbitraria). Dimostrare che la funzione
\(f \colon \mathbb{N}^{< \mathbb{N}} \to \mathbb{N}^{< \mathbb{N}}\), \(( k_{0}, k_{1}, \dotsc, k_{n-1} ) \mapsto ( k_{0}, k_{0}, k_{1}, k_{1}, \dotsc, k_{n-1}, k_{n-1} )\)
è iniettiva ma non suriettiva.
La funzione \(f\) manda ogni \(n\)-upla \((k_{0}, \dotsc, k_{n-1}) \in \mathbb{N}^n\) nell’unica \(2n\)-upla \((\ell_{0}, \dotsc, \ell_{2n-1}) \in \mathbb{N}^{2n}\) tale che per ogni \(0 \leq i < n\) si ha \(\ell_{2i+1} = \ell_{2i} = k_{i}\). Quindi se \(s = (k_{0}, \dotsc, k_{n-1})\) e \(s' = ( k'_{0}, \dotsc, k'_{m-1})\) sono tuple distinte si possono avere due casi:
\(n \neq m\): allora \(f(s) \neq f(s')\) poichè \(f(s) \in \mathbb{N}^{2n}\) e \(f(s') \in \mathbb{N}^{2m}\), e chiaramente \(2n \neq 2m\).
\(n = m\) (ovvero \(s\) e \(s'\) sono entrambe \(n\)-uple), ma \(k_{i} \neq k'_{i}\) per qualche \(0 \leq i < n\): allora \(f(s) \neq f(s')\) poichè posto \(f(s) = (\ell_{0}, \dotsc, \ell_{2n-1})\) e \(f(s') = (\ell'_{0}, \dotsc, \ell'_{2n-1})\) si ha \(\ell_{2i} \neq \ell'_{2i}\) e \(\ell_{2i+1} \neq \ell'_{2i+1}\).
Questo dimostra che \(f\) è iniettiva. Il fatto \(f\) non sia suriettiva segue dal fatto che ogni tupla in \(\mathrm{rng}(f)\) ha lunghezza pari, perciò si ha ad esempio \(( 0,3,1 ) \notin \mathrm{rng}(f)\).
Sia \(X\) un insieme non vuoto. Per ogni \(A \subseteq X\) la funzione caratteristica di \(A\) è la funzione \(\chi_{A} \colon X \to \{ 0,1 \}\) definita da \[\chi_{A}(x) = \begin{cases} 1 & \text{se } x \in A \\ 0 & \text{se } x \notin A. \end{cases}\] Sia \(2^X\) l’insieme di tutte le funzioni da \(X\) in \(\{ 0,1 \}\). In particolare, \(\chi_{A} \in 2^X\) per ogni \(A \in \mathscr{P}(X)\).
Dimostrare che la funzione \(F \colon \mathscr{P}(X) \to 2^X\) che manda ogni \(A \subseteq X\) nella sua funzione caratteristica \(F(A) = \chi_{A}\) è una biezione.
Iniettività: Dati \(A,B \in \mathscr{P}(X)\) distinti, o esiste \(x \in A \setminus B\) oppure esiste \(x \in B \setminus A\). Nel primo caso si avrà \(\chi_{A}(x) = 1\) e \(\chi_{B}(x) = 0\), nel secondo caso \(\chi_{A}(x) = 0\) e \(\chi_{B}(x) = 1\). In ogni caso \(\chi_{A}(x) \neq \chi_{B}(x)\), per cui \(\chi_{A} \neq \chi_{B}\), cioè \(F(A) \neq F(B)\). Suriettività: Data \(f \colon X \to \{ 0,1 \}\) sia \(A = \left \{x \in X \boldsymbol\mid f(x) = 1 \right\}\). Allora per definizione di funzione caratteristica si ha \(\chi_{A} = f\), ovvero \(F(A) = f\).
Abbiamo visto che dato un qualunque insieme non vuoto \(X\), c’è una biezione tra \(\mathscr{P}(X)\) e l’insieme \(2^X\) di tutte le funzioni da \(X\) in \(\{ 0,1 \}\).
Se \(X\) è finito e ha \(n \in \mathbb{N}\) elementi, allora ci sono esattamente \(2^n\) elementi in \(2^X\). Quindi
se \(X\) è un insieme non vuoto finito con \(n\) elementi, allora \(\mathscr{P}(X)\) ha \(2^n\) elementi.
In particolare, si ha che \(X\) ha meno elementi di \(\mathscr{P}(X)\): questo fatto verrà generalizzato ad insiemi \(X\) infiniti quando parleremo di cardinalità (Sezione 2.4).
Data una funzione \(f \colon X \to Y\), sia \(R_{f} \subseteq X \times X\) la relazione definita da
\(x_{1} \mathrel{R_{f}} x_{2}\) se e solo se \(f(x_{1}) = f(x_{2})\).
Che tipo di relazione è \(R_{f}\)? (Ordine? Equivalenza?)
è una relazione riflessiva, simmetrica e transitiva, quindi è una relazione di equivalenza.
Se ogni classe di equivalenza rispetto ad \(R_{f}\) contiene un unico elemento, che tipo di funzione è \(f\)? (Iniettiva? Suriettiva? Biettiva?)
Iniettiva (ma non necessariamente suriettiva).
Se \(X = Y = \mathbb{R}\) e \(f \colon \mathbb{R} \to \mathbb{R}\) è definita da \(f(x) = x^2\), come sono fatte le classi di equivalenza di \(R_{f}\)?
Sono del tipo \([r]_{R_{f}} = \{ r, -r \}\) per \(r \geq 0\) (si osservi che \(R_{f}\) è la relazione di equivalenza della slide 18 del file sulle relazioni).
Data una funzione \(f \colon X \to Y\), sia \(R_{f} \subseteq X \times X\) la relazione definita da
\(x_{1} \mathrel{R_{f}} x_{2}\) se e solo se \(f(x_{1}) = f(x_{2})\).
Fissiamo \(0 \neq n \in \mathbb{N}\). Sia \(X = \mathbb{Z}\), \(Y = \mathbb{N}\) e definiamo \(f \colon \mathbb{Z} \to \mathbb{N}\) ponendo
\(f(z) =\) il resto della divisione intera per \(n\) di \(z\).
Che relazione \(R_{f}\) otteniamo?
Si ha che \(f(z) = f(z')\) se e solo se \(z \equiv z' (\mathrm{mod} n)\). Quindi \(R_{f}\) è la relazione di congruenza modulo \(n\).
Sia \(X = \mathbb{N}\). Trovare un opportuno insieme \(Y\) e una funzione \(f \colon X \to Y\) tale che la relazione risultante \(R_{f}\) sia la relazione considerata nella slide 20 del file sulle relazioni.
Basta porre \(Y = \mathbb{N}\) e definire \(f \colon \mathbb{N} \to \mathbb{N}\) ponendo
\(f(n) =\) il numero di cifre di \(n\) (in notazione decimale).
Più in generale, si può dimostrare che ogni relazione d’equivalenza \(E\) su un insieme \(A\) è della forma \(R_{f}\) per un’opportuna scelta di \(f \colon X \to Y\).
Basta infatti prendere \(X = A\), \(Y = A/E\) e
\(f \colon X \to Y\), \(a \mapsto [a]_{E}\)
e ricordare che dati \(a,b \in A\) si ha che
\(a \mathrel{E} b\) se e solo se \([a]_{E} = [b]_{E}\).
Una stringa finita (su \(A\)) è una sequenza finita di simboli provenienti da un dato insieme non vuoto \(A\), che in questo caso viene detto alfabeto. L’insieme di tutte le stringhe finite su \(A\) si indica con \(A^*\).
Esempio
Sia \(A\) l’insieme di tutti i caratteri presenti su una normale tastiera di computer. Allora i seguenti sono esempi di stringhe su \(A\):
\(abcaaa\) \(102035\) \(a1BnWms()*8x\)
Altri esempi di stringhe su \(A\) sono ad esempio le password che inseriamo per accedere ad un account, il codice PIN della Sim di un cellulare, le parole italiane (scritte) e così via.
Attenzione! A differenza di ciò che accade con gli insiemi, in una stringa è essenziale tenere conto sia delle (eventuali) ripetizioni che dell’ordine con cui i vari elementi di \(A\) compaiono.
La stringa \[abcaaa\] sarà anche scritta con una notazione che spesso viene usata in matematica per rappresentare le sequenze, ovvero \[\langle a,b,c,a,a,a\rangle\]
In alcuni casi, questo cambio di notazione è necessario! Se ad esempio \(A = \mathbb{N}\) non è chiaro se la stringa \(703\) rappresenti:
una stringa con tre elementi, ovvero i numeri \(7\), \(0\) e \(3\);
una stringa con due elementi, ovvero i numeri \(70\) e \(3\);
una stringa con un unico elemento, ovvero il numero \(703\).
Questo accade perchè anche i numeri naturali sono a loro volta scritti come stringhe sull’alfabeto \(A' = \{ 0,1,2,3,4,5,6,7,8,9 \} \subseteq \mathbb{N}\).
Scrivendo invece \(\langle 70, 3 \rangle\) non vi è più alcuna ambiguità!
Notazione I termini stringa e sequenza saranno per noi sinonimi, ma graficamente adotteremo la convenzione che le stringhe vengono scritte nella forma \(abcade\) (quando questo non porta ad ambiguità!), mentre le corrispondenti sequenze vengono scritte nella forma \(\langle a,b,c,a,d,e\rangle\).
La lunghezza di una stringa \(s\), denotata con \(lh(s)\), è il numero di simboli che vi compaiono. Ad esempio, se \(A\) è l’alfabeto italiano formato da \(21\) lettere, la seguente stringa su \(A\) \[hdilcga\] ha lunghezza \(7\).
C’è un’unica stringa/sequenza di lunghezza \(0\), ovvero quella che non contiene alcun simbolo, detta stringa o sequenza vuota. Se usiamo la notazione per le sequenze la possiamo indicare con \(\langle \rangle\). La notazione per le stringhe non ci dà invece alcun modo per rappresentare la stringa vuota: perciò si è stabilito (specialmente in ambito informatico) di denotarla con \(\varepsilon\).
C’è una naturale biezione tra gli elementi di \(A\) e le stringhe su \(A\) di lunghezza \(1\), ovvero la funzione che associa a ciascun \(a \in A\) la sequenza \(\langle a \rangle\). Per questa ragione, l’insieme delle sequenze su \(A\) di lunghezza \(1\) viene identificato con \(A\) stesso.
Le stringhe su \(A\) di lunghezza \(2\) sono invece identificabili con le coppie ordinate di elementi di \(A\), ovvero con gli elementi dell’insieme \(A^2 = A \times A\).
Le stringhe su \(A\) di lunghezza \(3\) si possono identificare con le triple ordinate di elementi di \(A\), ovvero con gli elementi dell’insieme \(A^3 = A \times A \times A\).
Più in generale, le stringhe su \(A\) di lunghezza \(n\) si possono identificare con le \(n\)-uple di elementi di \(A\), ovvero con gli elementi dell’insieme \(A^n\).
Questo giustifica l’uso della notazione seguente.
Notazione L’insieme delle sequenze su \(A\) di lunghezza \(n\) si denota con \(A^n\). L’insieme di tutte le sequenze finite su \(A\) (di qualunque lunghezza) si denota con \(A^{< \mathbb{N}}\), ovvero \[A^{<\mathbb{N}} = \left \{\langle a_{0}, \dotsc, a_{n-1}\rangle \boldsymbol\mid n \in \mathbb{N} \wedge \forall i < k (a_{i} \in A) \right\}.\]
Dunque \[A^* = A^{< \mathbb{N}} = \bigcup_{n \in \mathbb{N} } A^n.\] Per quanto osservato prima, \(A^0 = \{ \langle \rangle \} = \{ \varepsilon \}\). Inoltre \(A^1\) viene identificato con \(A\) stesso.
Esempio
Sia \(A=\{ 0 , 1 \}\). Utilizzando sia la notazione per le sequenze che quella per le stringhe si ottiene:
| \[A^1\] | \[=\] | \[{\{\langle0\rangle,\langle1\rangle\}}\] |
|---|---|---|
| \[\] | \[=\] | \[{\{ 0,1 \}}\] |
| \[A^2\] | \[=\] | \[{\{\langle0,0\rangle,\langle0,1\rangle,\langle1,0\rangle,\langle1,1\rangle\}}\] |
|---|---|---|
| \[\] | \[=\] | \[{\{ 00,01,10,11\}}\] |
| \[A^3\] | \[=\] | \[{\{\langle0,0,0\rangle,\langle0,0,1\rangle,\langle0,1,0\rangle,\langle0,1,1\rangle,\langle1,0,0\rangle,\langle1,0,1\rangle,\langle1,1,0\rangle,\langle1,1,1\rangle\}}\] |
|---|---|---|
| \[\] | \[=\] | \[{\{000,001,010,011,100,101,110,111 \}}\] |
Esercizio
Quante sono le stringhe in \(\{0,1\}^4\)? Più in generale, dato un numero naturale \(n\in\mathbb{N}\) quante sono le stringhe in \(\{0,1\}^n\)?
Se \(A\) è un insieme finito con \(k\) elementi e \(n \in \mathbb{N}\), quante sono le stringhe in \(A^n\)? E se \(A\) è infinito?
Rappresentazione di stringhe come funzioni
Una sequenza finita \(s\) su \(A\) può anche essere rappresentata come una funzione dall’insieme \(\{ k \in \mathbb{N} \mid k < lh(s) \}\) in \(A\). Più precisamente, la sequenza \(s\) su \(A\) di lunghezza \(n\) \[\langle s_{0}, \dotsc, s_{n-1} \rangle\] si identifica con la funzione
\(s \colon \{ k \in \mathbb{N} \mid k < n \} \to A\), \(k \mapsto s_{k}\).
L’idea è che la funzione \(s \colon \{ k \in \mathbb{N} \mid k < n \} \to A\) enumera i simboli della stringa: \(s(0)\) è il primo elemento della stringa, \(s(1)\) è il secondo elemento della stringa, e così via.
Attenzione! I numeri naturali partono da \(0\) e non da \(1\). Quindi il “primo elemento” di \(\langle s_{0},s_{1}, \dotsc, s_{n-1}\rangle\) è \(s_{0}\) e NON \(s_{1}\), il “secondo elemento” è \(s_{1}\) NON \(s_{2}\) e così via.
Esempio
Sia \(A = \{ a,b \}\) e \(s \in A^4\) la stringa \(aaba\) (che si può scrivere anche \(\langle a,a,b,a \rangle\)). Allora \(s\) si può vedere come la funzione \(s \colon \{ 0,1,2,3 \} \to A\) definita da
\(s(0) = a\) \(s(1) = a\) \(s(2) = b\) \(s(3) = a\)
Invece la funzione
\(s \colon \left \{ k \in \mathbb{N} \boldsymbol\mid k < 10 \right\} \to \{ 0,1,2,3,4,5,6,7,8,9 \}\), \(k \mapsto 9-k\)
rappresenta la stringa \[9876543210\]
Esercizio
Trovare le funzioni che rappresentano le seguenti stringhe
sull’alfabeto \(A = \{ 0,1 \}\).
\(010\) \(00\) \(0010\) \(100010100\)
Trovare la funzione che rappresenta la sequenza \(\langle 0,1,2,3,4,5 \rangle\).
Qual’è la funzione che rappresenta la stringa vuota?
Scrivere come funzioni le seguenti stringhe sul normale alfabeto per la lingua italiana (\(21\) lettere).
Date due stringhe \(s,t \in A^*\), la concatenazione di \(s\) e \(t\), denotata con \[st,\] è la stringa su \(A\) di lunghezza \(lh(s) + lh(t)\) ottenuta facendo seguire i simboli elencati in \(s\) dai simboli elencati in \(t\).
Esempio
Se \(s\) è la stringa \(acbbca\) e \(t\) è la stringa \(bacac\), allora \(st\) è la stringa
\(acbbca\) \(bacac\).
Si noti che concatenando una qualunque stringa \(s \in A^*\) con la sequenza vuota si ottiene la sequenza \(s\) di partenza, ovvero \[s \varepsilon = \varepsilon s = s.\]
Utilizzando la notazione per le sequenze, se \(s = \langle 5,17,23 \rangle\) e \(t = \langle 0,73,162 \rangle\) si ha che \[st = \langle 5,17,23 \rangle\langle 0,73,162 \rangle = \langle 5,17,23, 0,73,162 \rangle.\]
Infine, utilizzando la rappresentazione come funzioni, se \[s \colon \{ k \in \mathbb{N} \mid k < lh(s) \} \to A\] e \[t \colon \{ k \in \mathbb{N} \mid k < lh(t) \} \to A\] allora \(st\) è la sequenza di lunghezza \(lh(s) + lh(t)\) definita ponendo per ogni \(k < lh(s)+lh(t)\) \[st(k) = \begin{cases} s(k) & \text{se }k < lh(s) \\ t(k - lh(s)) & \text{se } k \geq lh(s). \end{cases}\]
Qualche volta è necessario considerare anche stringhe infinite del tipo \[0011001010100001000001100001000\dotsc\] Usando la notazione per le sequenze, tali stringhe si possono rappresentare come \[\langle s_{0}, s_{1}, s_{2}, \dotsc, s_{n}, \dotsc \rangle\] oppure, in maniera più concisa, come \[\langle s_{n} \rangle_{n \in \mathbb{N}}.\]
Esempio
La sequenza \(\langle 2n \rangle_{n \in \mathbb{N}}\) è la stringa infinita di tutti i numeri pari (in ordine crescente), ovvero \[\langle 0, 2,4,6,8,10,12,14,16, \dotsc, 2n, \dotsc \rangle\]
Anche una stringa infinita \(s = \langle s_{n} \rangle_{n \in \mathbb{N}}\) su un alfabeto \(A\) si può identificare con la sua funzione “enumerante”
\(s \colon \mathbb{N} \to A\), \(k \mapsto s_{k}\).
Questa identificazione ci permette di dare una definizione rigorosa di che cosa è una stringa infinita su un alfabeto \(A\): ad esempio, una stringa infinita binaria è semplicemente una funzione \(f \colon \mathbb{N} \to \{ 0,1 \}\).
Definizione Dato un insieme \(A\), indichiamo con \(A^\mathbb{N}\) l’insieme delle funzioni da \(\mathbb{N}\) in \(A\), ovvero \[A^\mathbb{N} = \left \{f \boldsymbol\mid f \colon \mathbb{N} \to A \right\}.\]
Dunque \(A^\mathbb{N}\) può anche essere visto come l’insieme di tutte le stringhe infinite su \(A\).
Le sequenze infinite \(\langle a_{n} \rangle_{n \in \mathbb{N}}\) vengono anche chiamate successioni e denotate con \((a_{n})_{n \in \mathbb{N}}\).
Esempio
La stringa \[010101\dotsc\] che alterna \(0\) ed \(1\) senza mai ripeterne due consecutivamente è la funzione \(f \colon \mathbb{N}\to \{ 0,1 \}\) tale che
\(f(0)=0\) \(f(1)=1\) \(f(2)=0\) \(\dotsc\) \(f(2k) = 0\) \(f(2k+1) = 1\) \(\dotsc\)
che può essere definita esplicitamente come
\(f \colon \mathbb{N} \to \{ 0,1 \}\), \(n\mapsto [n]_{2}\) .
Esempio
La funzione
\(g \colon \mathbb{N} \to \mathbb{N}\), \(n \mapsto n^2\)
è la successione \[\langle 0, 1, 4, 9, 16, 25, \dotsc \rangle\] che può anche essere scritta come \[\langle n^2 \rangle_{n \in \mathbb{N}}.\]
Esercizio
Scrivere la stringa \[\langle 1,2,4,8,16,32,64,128,256,\dotsc \rangle\] sia come funzione \(f \colon \mathbb{N} \to \mathbb{N}\), sia con la notazione per le sequenze infinite \(\langle a_{n} \rangle_{n \in \mathbb{N}}\).
Qual’è la successione definita dalla seguente funzione?
\(f \colon \mathbb{N} \to \mathbb{N}\), \(n \mapsto \frac{1}{2}n(n+1)\)
Scriverne esplicitamente i primi \(10\) termini.