Funzione suriettiva

In matematica, una funzione si dice suriettiva (o surgettiva, o una suriezione) quando ogni elemento del codominio è immagine di almeno un elemento del dominio. In tal caso si ha che l'immagine coincide con il codominio.

Definizione

Una funzione $f : X \to Y$ è detta suriettiva se per ogni $y \in Y$ esiste $x \in X$ tale che $f (x) = y$ .

La composta di due funzioni suriettive è a sua volta suriettiva; ma se $g \circ f$ è suriettiva, possiamo concludere solo che $g$ è suriettiva

Esempi

Per ogni insieme $X$ , la funzione identità ${i d}_{X}$ su $X$ è suriettiva.
La funzione $f : ℝ \to ℝ$ definita da $f (x) = 2 x + 1$ è suriettiva, perché per ogni numero reale $y$ si ha $f (x) = y$ dove $x$ è $\frac{y - 1}{2}$ .
La funzione logaritmo naturale $\ln : (0, + \infty) \to ℝ$ è suriettiva.
Sia la funzione $f (x) = x^{2}$ definita con il seguente dominio e codominio: $f : ℝ ⟶ ℝ$ ; questa funzione non è suriettiva in quanto l'insieme delle immagini è costituito da tutti i numeri reali non negativi. Per rendere suriettiva questa funzione è sufficiente effettuare la seguente restrizione del codominio: $f : ℝ ⟶ [0, + \infty)$ .

Graficamente la suriettività può essere vista in questo modo: se abbiamo una funzione reale di una variabile reale che è suriettiva allora tracciando sul piano cartesiano una qualsiasi retta parallela all'asse $x$ di equazione $y = h$ con $h$ scelto nel codominio della funzione, allora questa retta orizzontale intersecherà il grafico della funzione almeno una volta.

Proprietà

Una funzione $f : X \to Y$ è suriettiva se e solo se esiste una funzione $g : Y \to X$ tale che $f \circ g$ è la funzione identità su $Y$ (tale proposizione è equivalente all'assioma della scelta).
Se $f$ e $g$ sono entrambe suriettive, allora $f \circ g$ è suriettiva.
Se $f \circ g$ è suriettiva, allora $f$ è suriettiva (ma $g$ può non esserlo).
$f : X \to Y$ è suriettiva se e solo se, per ogni coppia di funzioni $g, h : Y \to Z$ , ogni volta che $g \circ f = h \circ f$ , allora $g = h$ . In altri termini, le funzioni suriettive sono esattamente gli epimorfismi nella categoria $I n s$ di tutti gli insiemi.
Se $f : X \to Y$ è suriettiva e $B$ è un sottoinsieme di $Y$ , allora $f (f^{- 1} (B)) = B$ . Ne consegue che $B$ può essere ricostruito dalla sua controimmagine $f^{- 1} (B)$ .
Per ogni funzione $h : X \to Z$ esistono una suriezione $f$ e una funzione iniettiva $g$ tale che $h$ può essere decomposta come $h = g \circ f$ . Tale decomposizione è unica a meno di un isomorfismo, e $f$ può essere vista come una funzione avente gli stessi valori di $h$ ma il cui codominio è ristretto all'insieme immagine $h (W)$ di $h$ , che è un sottoinsieme del codominio $Z$ di $h$ .
Aggregando insieme tutte le controimmagini di una prefissata immagine, ogni funzione suriettiva induce una funzione biunivoca definita sul quoziente del suo dominio. In particolare, ogni funzione suriettiva $f : A \to B$ può essere fattorizzata in una proiezione seguita da una biiezione nel seguente modo. Sia $A / \sim$ l'insieme delle classi di equivalenza di $A$ rispetto alla seguente relazione d'equivalenza: $x \sim y \Leftrightarrow f (x) = f (y)$ . Sia $P (\sim) : A \to A / \sim$ la proiezione che associa ogni $x \in A$ alla sua classe d'equivalenza $[x]_{\sim}$ , e sia $f_{P} : A / \sim \to B$ la funzione ben definita data da $f_{P} ([x]_{\sim}) = f (x)$ . Allora $f = f_{P} \circ P (\sim)$ .
Se $f : X \to Y$ è suriettiva e $X, Y$ sono insiemi finiti, allora $X$ ammette almeno lo stesso numero di elementi di $Y$ .
Se $X$ e $Y$ sono finiti con lo stesso numero di elementi, allora $f : X \to Y$ è suriettiva se e solo se $f$ è iniettiva.

Numero di funzioni suriettive

Il numero di funzioni suriettive da un insieme finito $A$ con $a$ elementi a un insieme finito $B$ con $b$ elementi è pari a 0 se $a < b$ (vedi proprietà 8). Nel caso meno banale in cui $a ⩾ b$ il numero di funzioni suriettive da $A$ a $B$ , indicato con $S_{a b}$ , sarà dato dalla seguente relazione di ricorrenza:

S_{a, 1} = 1,

S_{a, b} = b^{a} - \sum_{k = 1}^{b - 1} (\binom{b}{k}) S_{a, k} .

Per giustificare questa formula basti pensare al fatto che, per calcolare $S_{a, b},$ basta contare quante sono tutte le $f : A \to B$ (cioè $b^{a}$ ) e sottrarre quelle non suriettive. Le funzioni non suriettive hanno come immagine un sottoinsieme più piccolo di $B$ , di cardinalità $1 ⩽ k ⩽ b - 1$ . Per ogni $k$ si sottrarrà dunque $S_{a, k}$ tante volte quanti sono i possibili modi di scegliere i $k$ elementi su $b$ disponibili e cioè $(\binom{b}{k})$ .

La formula che utilizza i numeri di Stirling di seconda specie è la seguente

S_{a, b} = b! {\begin{matrix} a \\ b \end{matrix}} .

Per esempio:

S_{5, 3} = 3! {\begin{matrix} 5 \\ 3 \end{matrix}} = 3! 25 = 150;

S_{5, 2} = 2! {\begin{matrix} 5 \\ 2 \end{matrix}} = 2! 15 = 30;

S_{5, 1} = 1! {\begin{matrix} 5 \\ 1 \end{matrix}} = 1! 1 = 1.

Anche mediante l'altra formula

S_{5, 3} = 3^{5} - ((\binom{3}{1}) 1 + (\binom{3}{2}) 30) = 243 - 93 = 150.

Note

↑ Mauro Cerasoli, Franco Eugeni; Marco Protasi, Elementi di matematica discreta, Bologna, Zanichelli, 1988, p. 22, ISBN 978-88-08-03858-6.

Voci correlate

Altri progetti

Wikimedia Commons contiene immagini o altri file sulla funzione suriettiva

Collegamenti esterni

suriezione, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.

(EN) surjection, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.

(EN) Eric W. Weisstein, Surjection, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica

[1] Mauro Cerasoli, Franco Eugeni; Marco Protasi, Elementi di matematica discreta, Bologna, Zanichelli, 1988, p. 22, ISBN 978-88-08-03858-6.