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.

Un esempio di funzione suriettiva: non esiste alcun elemento di Y che non sia puntato da un elemento di X

Definizione

Una funzione ${\displaystyle f\colon X\rightarrow Y}$ è detta suriettiva se ${\displaystyle \forall y\in Y,\exists x\in X|f(x)=y}$.

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

Esempi

• Per ogni insieme ${\displaystyle X}$, la funzione identità ${\displaystyle \mathrm {id} _{X}}$ su ${\displaystyle X}$ è suriettiva.
• La funzione ${\displaystyle f:\mathbb {R} \rightarrow \mathbb {R} }$ definita da ${\displaystyle f(x)=2x+1}$ è suriettiva, perché per ogni numero reale ${\displaystyle y}$ si ha ${\displaystyle f(x)=y}$ dove ${\displaystyle x}$ è ${\displaystyle {\frac {y-1}{2}}}$.
• La funzione logaritmo naturale ${\displaystyle \ln \colon \mathbb {R} ^{+}\rightarrow \mathbb {R} }$ è suriettiva.
• Sia la parabola ${\displaystyle f(x)=x^{2}}$ definita in maniera seguente: ${\displaystyle f\colon \mathbb {R} \longrightarrow \mathbb {R} }$; 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 questa restrizione: ${\displaystyle f\colon \mathbb {R} \longrightarrow \mathbb {R} ^{+}\cup \{0\}}$, ovvero considerare un codominio diverso.

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 ${\displaystyle x}$ di equazione ${\displaystyle y=h}$ con ${\displaystyle h}$ scelto nel codominio della funzione, allora questa retta orizzontale intersecherà il grafico della funzione almeno una volta.

Proprietà

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

Numero di funzioni suriettive

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

${\displaystyle S_{a,1}=1,}$

${\displaystyle 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 ${\displaystyle S_{ab}}$, basta contare quante sono tutte le ${\displaystyle f\colon A\to B}$ (cioè ${\displaystyle b^{a}}$) e sottrarre quelle non suriettive. Le funzioni non suriettive hanno come immagine un sottoinsieme più piccolo di ${\displaystyle B}$, di cardinalità ${\displaystyle 1\leqslant k\leqslant b-1}$. Per ogni ${\displaystyle k}$ si sottrarrà dunque ${\displaystyle S_{ak}}$ tante volte quanti sono i possibili modi di scegliere i ${\displaystyle k}$ elementi su ${\displaystyle b}$ disponibili e cioè ${\displaystyle {\binom {b}{k}}}$.

La formula che utilizza i numeri di Stirling di seconda specie è la seguente ${\displaystyle S_{a,b}=b!\left\{{\begin{matrix}a\\b\end{matrix}}\right\}}$ ^[1]

Per esempio ${\displaystyle S_{5,3}=3!\left\{{\begin{matrix}5\\3\end{matrix}}\right\}=3!25=150~~~~S_{5,2}=2!\left\{{\begin{matrix}5\\2\end{matrix}}\right\}=2!15=30~~~~S_{5,1}=1!\left\{{\begin{matrix}5\\1\end{matrix}}\right\}=1!1=1}$

Anche mediante l'altra formula ${\displaystyle S_{5,3}=3^{5}-({\binom {3}{1}}1+{\binom {3}{2}}30)=243-93=150}$

Note

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

Voci correlate

• Funzione iniettiva
• Funzione biiettiva

Altri progetti

Altri progetti

• Wikimedia Commons

• 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, Funzione suriettiva, su MathWorld, Wolfram Research.

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