ASD 03a - Le Funzioni in Matematica

Intuitivamente una funzione è un strumento matematico che ci permette di associare elementi di un insieme ad elementi di un altro insieme. Tramite una funzione siamo quindi in grado di catturare come elementi di diversi insiemi sono relazionati tra loro. È proprio questa abilità di catturare relazioni tra oggetti matematici diversi che rende la funzione uno degli strumenti matematici più importanti di sempre.

Fissati due insiemi \(A\) e \(B\), per indicare che \(f\) è una funzione che associa elementi di \(A\) ad elementi di \(B\) possono essere utilizzate diverse notazioni. Tra queste troviamo anche le seguenti due:

  • \(f:A \to B\)

  • \(A \overset{f}{\longrightarrow} B\)

In ogni caso, qualsiasi notazione utilizziamo, essa deve mettere in risalto tre simboli: il simbolo di funzione \(f\), detto anche funtore, l'insieme di partenza \(A\), detto anche dominio, e l'insieme di destinazione \(B\), detto anche codominio.

Per indicare invece le particolari associazioni che la funzione \(f\) ci permette di effettuare possiamo procedere utilizzando una notazione grafica, come la seguente

Notiamo però che questa notazione grafica, per quanto intuitiva possa essere, non è molto scalabile quando abbiamo a che fare con insiemi molto grandi (per non parlare di insiemi infiniti). Necessitiamo quindi una descrizione più analitica e sintetica. A tale fine, fissati \(A = \{a_1, a_2, a_3\}\) e \(B=\{b_1, b_2, b_3, b_4\}\), possiamo utilizzare la seguente:

\[\begin{split} f(a_1) &= b_1 \\ f(a_2) &= b_2 \\ f(a_3) &= b_4 \\ \end{split}\]

Dove la sitnassi \(f(a_1) = b_1\) ci indica esattamente il fatto che l'elemento \(a_1\) è stato associato, tramite \(f\), all'elemento \(b_1\).

Ricapitolando quindi, una funzione \(f:A \to B\) ci permette di esprimere una qualche relazione che ci permette di associare elementi di un insieme ad elementi di un altro insieme. Notiamo però che non tutte le associazioni di elementi da un insieme ad un altro sono delle funzioni. Andiamo quindi a renndere più chiaro che cosa intendiamo effettivamente per funzione nel contesto matematico.

Troviamo la seguente definizione.

Def: Dati due insiemi \(A, B\), si dice funzione da \(A\) e \(B\) ogni \(f \subseteq A \times B\) tale che

\[\forall a \in A: \exists! b \in B: (a, b) \in f\]

Questa definizione ci dice due cose:

  1. Come rappresentiamo formalmente una funzione, ovvero che una funzione è un sottoinsieme del prodotto cartesiano dei due insiemi.

  2. Il vincolo logico che una associazione, per poter essere chiamata funzione, deve rispettare. Il vincolo è scritto nel linguaggio della logica del primo ordine, e ci dice che ogni elemento del dominio \(a \in A\) deve essere mappato tramite \(f\) ad uno e uno solo elemento del codominio \(b \in B\).

Notiamo che dati due insiemi \(A, B\), una associazione \(f \subseteq A \times B\) può fallire nell'essere considerata una funzione per due ragioni diverse:

  1. Il primo motivo è che \(f\) potrebbe lasciare stare qualche elemento del dominio, come mostra il seguente esempio.

    In questo caso l'associazione definita da \(f\) non è una funzione in quanto \(f\) non associa ad \(a_1\) nessun elemento del codominio \(B\).

  2. Il secondo motivo è che \(f\) potrebbe associare allo stesso elemento del dominio due o più elementi del codominio, come mostra il seguente esempio.

Per chiarire le idee, e anche per ripassare come si calcola il prodotto cartesiano tra due insiemi, andiamo a vedere come rappresentiamo formalmente la funzione che avevamo mostrato precedentemente.

Ricordiamo brevemente gli elementi del dominio \(A = \{a_1, a_2, a_3\}\) e gli elementi del codominio \(B = \{b_1, b_2, b_3, b_4\}\). Possiamo quindi calcolare il prodotto cartesiano \(A \times B\) tra questi due insiemi, ricordando che tale prodotto è ottenuto prendendo tutte le possibili coppie \((a, b)\) dove il primo elemento della coppia è preso dal primo insieme \(a \in A\) e il secondo elemeneto dal secondo insieme \(b \in B\). In questo caso troviamo

\[\begin{split} A \times B = \{ &(a_1, b_1), (a_1, b_2), (a_1, b_3), (a_1, b_4), \\ & (a_2, b_1), (a_2, b_2), (a_2, b_3), (a_2, b_4), \\ & (a_3, b_1), (a_3, b_2), (a_3, b_3), (a_3, b_4) \} \\ \end{split}\]

La nostra funzione \(f \subseteq A \times B\) è quindi data da

\[f = \{(a_1, b_1), (a_2, b_2), (a_3, b_4)\} \subseteq A \times B\]

Notiamo che tale \(f\) rispetta il vincolo logico che avevamo imposto. Per controllare tale vincolo infatti basta vedere che per ogni elemento del dominio \(a \in A\) abbiamo una e una sola coppia in \(f\) il cui primo elemento è \(a\).

Continuando con qualche esempio, sia \(P\) l'insieme delle persone, \(U\) l'insieme degli uomini e \(D\) l'insieme delle donne. Allora possiamo definire le seguenti due funzioni:

  • La funzione \(\mu: P \to P\), che associa una persona alla propria madre. Formalmente,

    \[\mu := \{(a, b) \in P \times P \,\,|\,\, b \text{ è la madre di } a\}\]

  • La funzione \(\pi: P \to P\), che associa una persona al proprio padre. Formalmente,

    \[\pi := \{(a, b) \in P \times P \,\,|\,\, b \text{ è il padre di } a\}\]

Da un punto di vista notazionale per parlare di una funzione viene utilizzata la seguente terminologia/notazione.

  • Per indicare che \((a, b) \in f\) scriviamo

    \[f(a) := b \in B\]

    dove \(b\) è l'unico elemento di \(B\) associato ad \(a\) tramite \(f\).

  • Per ogni sottoinsieme del dominio, \(A' \subseteq A\), chiamiamo immagine di \(A'\) tramite \(f\) il seguente sottoinsieme di \(B\)

    \[f(A') := \{b \in B \,\,|\,\, \exists a' \in A': f(a') = b\}\]

    In altre parole l'immagine di \(A'\) è l'insieme di tutti i valori del codominio \(B\) ottenuti applicando \(f\) agli elementi di \(A'\).

  • Per ogni \(B' \subseteq B\), chiamiamo controimmagine di \(B'\) tramite \(f\) il seguente sottoinsieme di \(A\)

    \[f^{-1}(B') := \{a \in A \,\,|\,\, \exists b' \in B': f(a) = b'\}\]

    La controimmagine di \(B'\) è quindi l'insieme di tutti i valori del dominio che sono associati a qualche elemento di \(B'\) tramite \(f\).

Come è prassi in matematica, una volta che si definisce un oggetto matematico, il prossimo passo è sempre quello di analizzare le possibili proprietà che questo oggetto può possedere. Una funzione in particolare può avere le seguenti proprietà

Una funzione \(f: A \to B\) è detta iniettiva se e solo se

\[\forall a', a^{''} \in A: \,\, f(a') = f(a^{''}) \implies a' = a^{''}\]

ovvero "elementi distinti in \(A\) vengono mappati in elementi distinti in \(B\)". Equivalentemente,

\[\forall a', a^{''} \in A: a' \neq a^{''} \implies f(a') \neq f(a^{''})\]

Notiamo che non tutte le funzioni sono iniettive.

Una funzione \(f: A \to B\) è detta suriettiva se e solo se

\[\forall b \in B: \exists a \in A: f(a) = b\]

ovvero "ogni elemento di B è immagine di un qualche elemento di A".

Nuovamente, non tutte le funzioni sono suriettive.

Una funzione \(f: A \to B\) è detta biettiva se e solo è sia iniettiva che suriettiva. In formula,

\[\forall b \in B: \exists! a \in a: \,\, f(a) = b\]

Date due funzioni \(f:A \to B\) e \(g:B \to C\), si definisce la composizione (o prodotto) di \(g\) per \(f\) la funzione \(g \circ f: A \to C\) data da

\[\forall a \in A: (g \circ f)(a) := g(f(a))\]

Graficamente otteniamo

Notiamo che in generale la composizione di funzioni gode della proprietà associativa, ovvero, date tre funzioni \(f:A \to B\), \(g:B \to C\), \(h:C \to D\), abbiamo

\[h \circ (g \circ f) = (h \circ g) \circ f\]

In generale però la composizione non gode della proprietà commutativa, ovvero scambiando l'ordine delle funzioni otteniamo risultati diversi. In particolare, se

\[\begin{split} f:\mathbb{R} \to \mathbb{R}, &\,\,\, f(x) := x + 1 \\ g:\mathbb{R} \to \mathbb{R}, &\,\,\, g(x) := x^2 \\ \end{split}\]

allora otteniamo

\[\begin{split} (g \circ f)(x) &= g(f(x)) &= g(x + 1) &= (x + 1)^2 \\ (f \circ g)(x) &= f(g(x)) &= f(x^2) &= x^2 + 1 \\ \end{split}\]

E dato che le funzioni ottenute sono diverse, abbiamo che in questo caso, e quindi in generale

\[g \circ f \neq f \circ g\]

Andiamo adesso a dimostrare che date due funzioni iniettive \(f:A \to B\) e \(g: B \to C\), abbiamo che anche la loro composizione \(g \circ f\) è iniettiva.

Dim: Siano \(a_1, a_2 \in A\). Noi vogliamo dimostrare che \((g \circ f)\) mappa elementi diversi del dominio in elementi diversi del codominio, o equivalentemente che se due elementi del dominio sono stati mappati nello stesso elemento del codominio, allora questi due elementi sono in realtà uguali. In formula,

\[(g \circ f)(a_1) = (g \circ f(a_2) \overset{?}{\implies} a_1 = a_2\]

Procediamo quindi assumendo che \((g \circ f)(a_1) = (g \circ f(a_2)\).

Ora, utilizzando la definizione di funzione composta otteniamo

\[g(f(a_1)) = g(f(a_2))\]

Dall'iniettività di \(g\) otteniamo

\[g(f(a_1)) = g(f(a_2)) \implies f(a_1) = f(a_2)\]

Dall'iniettività di \(f\) invece otteniamo

\[f(a_1) = f(a_2) \implies a_1 = a_2\]

Ma allora, mettendo tutto insieme abbiamo che

\[(g \circ f)(a_1) = (g \circ f)(a_2) \implies a_1 = a_2\]

\[\tag*{$\blacksquare$}\]

Una funzione \(f:A \to B\) si dice invertibile se esiste un'altra funzione \(\tilde{f}:B \to A\) tale che

\[\tilde{f} \circ f = id_A, \,\,\, f \circ \tilde{f} = id_B\]

dove fissato un insieme \(X\) la funzione \(id_X: X \to X\) mappa ogni elemento a se stesso, ovvero

\[\forall x \in X: id_X(x) := x\]

Notiamo che se tale \(\tilde{f}\) esiste, allora è unica. Infatti, se \(\tilde{f}\) e \(\hat{f}\) sono funzioni da \(B\) ad \(A\) per cui

\[\begin{split} \hat{f} \circ f = id_A \,\,,\,\, f \circ \hat{f} = id_B \\ \tilde{f} \circ f = id_A \,\,,\,\, f \circ \tilde{f} = id_B \\ \end{split}\]

allora,

\[\begin{split} \hat{f} = \hat{f} \circ id_B &= \hat{f} \circ (f \circ \tilde{f}) \\ &= (\hat{f} \circ f) \circ \tilde{f} \\ &= id_A \circ \tilde{f} \\ &= \tilde{f} \\ \end{split}\]

\[\tag*{$\checkmark$}\]

Ma quindi, dato che se esiste l'inversa di \(f\) è unica, essa sarà denotata univocamente con il simbolo \(f^{-1}\).

Vale la seguente proposizione.

Proposizione: Per ogni funzione \(f:A \to B\) abbiamo che

\[f \text{ è invertibile } \iff f \text{ è biiettiva }\]

Dim: \((\implies)\) Per iniziare assumiamo che \(f\) sia invertibile e dimostriamo che \(f\) è anche biiettiva. Sia quindi \(f^{-1}\) l'inversa di \(f\). Per dimostrare che \(f\) è biettiva dimostreremo che è sia iniettiva che suriettiva:

  • \(f\) è iniettiva. Infatti, fissati due \(a_1, a_2 \in A\) abbiamo che

    \[\begin{split} f(a_1) = f(a_2) &\implies f^{-1}(f(a_1)) = f^{-1}(f(a_2)) \\ &\implies id_A(a_1) = id_A(a_2) \\ &\implies a_1 = a_2 \end{split}\]

  • \(f\) è suriettiva. Infatti, fissato \(b \in B\), abbiamo che prendendo \(a := f^{-1}(b) \in A\) otteniamo

    \[f(a) = f(f^{-1}(b)) = id_B(b) = b\]

Dato che \(f\) è sia iniettiva che suriettiva, concludiamo che \(f\) è anche biettiva, e quindi questo lato è concluso.

\[\tag*{$\checkmark$}\]

\((\impliedby)\) Continuando la dimostrazione, andiamo adesso a dimostrare l'inverso, ovvero che se \(f\) è biettiva allora \(f\) è anche invertibile. A tale fine definiamo \(f^{-1}:B \to A\) nel seguente modo

\[\forall b \in B: f^{-1}(b) := a \iff f(a) = b\]

andiamo quindi a far vedere che \(f^{-1}\) è la funzione inversa di \(f\). Per fare questo dobbiamo far vedere che le seguenti relazioni valgono

\[\begin{split} f^{-1} \circ f = id_A \\ f \circ f^{-1} = id_B \\ \end{split}\]

Notiamo che questo è vero per definizione, in quanto

\[\begin{split} f^{-1} \circ f (a) = f^{-1}(f(a)) = a \\ f^{} \circ f^{-1} (a) = f(f^{-1}(b)) = b \\ \end{split}\]

\[\tag*{$\blacksquare$}\]

Tra tutte le possibili funzioni ce ne sono alcune fondamentali per lo studio degli algoritmi. Tra queste troviamo:

  • Funzioni polinomiali

  • Funzioni esponenziali

  • Funzioni logaritmiche

Queste funzioni saranno l'oggetto di studio dei prossimi video.

In questa lezione abbiamo trattato la funzione sotto il punto di vista matematico. Detto questo, il concetto di funzione appare anche in altri contesti, tra cui quello informatico.

La maggior parte del linguaggi di programmazione infatti permette di definire delle funzioni (o procedure), che costituiscono dei blocchi di codice che possono essere eventualmente parametrizzati rispetto a delle variabili.

Notiamo quindi come la stessa parola "funzione" assume, in contesti diversi, significati diversi.

Consideriamo ad esempio la funzione che abbiamo scritto nella prima lezione (ASD - 01 - Problemi, Algoritmi e Modelli di Calcolo) per controllare se un dato intero \(n\) è primo oppure no. 

def check_primeness(n):
    result = True
    for j in range(2, n):
        if n % j == 0:
            result = False
    return result

Volendo tradurre questa funzione informatica in una funzione matematica otteniamo la funzione \(f: \mathbb{N} \to \{\text{True}, \text{False}\}\) definita come segue

\[\forall n \in \mathbb{N} \,\,\, f(n) := \begin{cases} \text{True} \,&,\,\, n \text{ è primo} \\ \text{False} \,&,\,\, n \text{ non è primo} \\ \end{cases}\]

Osserviamo ora la differenza tra queste due definizioni:

  • La funzione matematica è un esempio di conoscenza dichiarativa, nel senso che ci dice qual è il valore di \(f(n)\) per ogni \(n\), ma non ci permette di calcolarlo. \(f(n)\) dice: se \(n\) è primo, allora valgo \(\text{True}\), altrimenti valgo $\text{False}.

  • La funzione informatica invece rappresenta un altro tipo di conoscenza, che possiamo chiamare conoscenza procedurale. Essa non solo ci dice il valore che assume per ogni input \(n\), ma ci permette anche di calcolarlo. In alre parole, la funzione informatica check_primeness è una implementazione della funzione matematica \(f(n)\), nel senso che ci da da una ricetta per calcolare \(f(n)\) a partire da un dato valore di \(n\).

Come mostra il precedente esempio, può succedere che una funzione matematica sia calcolata tramite una funzione informatica. In generale però questi due concetti sono diversi, in quanto una funzione informatica può modificare lo stato della macchina in cui è eseguita. In questi casi quindi perdiamo il mapping completo tra funzione informatica funzione matematica.

Osservazione: Gli effetti secondari che una funzione ha sullo stato del processo in cui è eseguita vengono chiamati side-effects. C'è un intero ramo della programmazione, che prende il nome di programmazione funzionale, il cui obiettivo è quello di ridurre al minimo possibile questi side-effects. La loro motivazione è che la presenza di questi side-effects rende il software estremamente complicato da analizzare e da debuggare, e quindi meno side-effects si ha e meglio è.