Voir la source de Surjection

[[Image:Surjection-fr1.svg|cadre|[[Diagramme sagittal]] d'une surjection : tous les points de Y sont atteints.]]

En [[mathématiques]], une '''surjection''' ou '''application surjective''' est une [[Application (mathématiques)|application]] pour laquelle tout élément de l'[[ensemble d'arrivée]] a au moins un [[antécédent (mathématiques)|antécédent]], c'est-à-dire est [[Image (mathématiques)|image]] d'au moins un élément de l'[[Correspondance et relation|ensemble de départ]]. Il est équivalent de dire que l'[[Image d'une application|ensemble image]] est égal à l'ensemble d'arrivée.

Il est possible d'appliquer l'adjectif « surjectif » à une fonction (voire à une [[Correspondance et relation|correspondance]]) dont le [[domaine de définition]] n'est pas tout l'ensemble de départ, mais en général le terme « surjection » est réservé aux applications (qui sont définies sur tout leur ensemble de départ), auxquelles nous nous limiterons dans cet article (pour plus de détails, voir le [[Application (mathématiques)#Fonction et application|paragraphe « Fonction et application » de l'article « Application »]]).

Pour désigner les ensembles de départ et d'arrivée d'une surjection, il est usuel de dire « de ''A sur B'' » au lieu de « de ''A dans B'' » comme pour une application en général.

Dans le cas d'une [[fonction réelle d'une variable réelle]], sa '''surjectivité''' est équivalente au fait que son [[graphe d'une fonction|graphe]] intersecte toute droite parallèle à l'axe des abscisses.

Une application qui est à la fois surjective et [[Injection (mathématiques)|injective]] est une [[bijection]].

== Définition formelle ==
Une application {{mvar|f}} de {{mvar|X}} dans {{mvar|Y}} est dite surjective si [[pour tout]] élément {{mvar|y}} de {{mvar|Y}}, [[Quantificateur existentiel|il existe au moins un]] élément {{mvar|x}} de {{mvar|X}} tel que {{math|1=''y'' = ''f''(''x'')}}, ce qui s'écrit formellement :
: <math>\forall y \in Y,\quad\exist x \in X,\quad y = f(x)</math>.

== Exemples ==

=== Exemple concret ===

On considère le cas d'une station de vacances où un groupe de touristes doit être logé dans un hôtel. Chaque façon de répartir ces touristes dans les chambres de l'hôtel peut être représentée par une application de l'ensemble ''X'' des touristes vers l'ensemble ''Y'' des chambres (à chaque touriste est associée une chambre).
* L'hôtelier souhaite que l'application soit '''surjective''', c'est-à-dire que ''chaque chambre soit occupée''. Cela n'est possible que s'il y a au moins autant de touristes que de chambres (dans ce cas, plusieurs touristes peuvent occuper la même chambre).
* Les touristes souhaitent que l'application soit '''injective''', c'est-à-dire que ''chacun d'entre eux ait une chambre individuelle''. Cela n'est possible que si le nombre de touristes ne dépasse pas le nombre de chambres.
* Ces souhaits ne sont compatibles que si le nombre de touristes est égal au nombre de chambres. Dans ce cas, il sera possible de répartir les touristes de telle sorte qu'il y en ait un seul par chambre, et que toutes les chambres soient occupées : l'application sera alors à la fois injective et surjective ; on dira qu'elle est '''bijective'''.
[[Image:Surjection Injection Bijection-fr.svg]]

=== Exemples et contre-exemples dans les fonctions réelles ===
La fonction définie par
:<math>\begin{matrix}f: & \R & \rightarrow& \R\\ & x & \mapsto &x^2\\\end{matrix}</math>
n'est pas surjective car certains réels ne possèdent pas d'antécédent. Par exemple, il n'y a pas de réel ''x'' tel que ''f''(''x'')&nbsp;= −4. Mais si on change la définition de ''f'' en donnant comme ensemble d'arrivée ℝ<sup>+</sup>,
:<math>\begin{matrix}f: & \R & \rightarrow& \R_+\\ & x & \mapsto &x^2\\\end{matrix}</math>
alors elle le devient car chaque réel positif possède au moins un antécédent : 0 possède exactement un antécédent, 0, et tous les réels ''y'' strictement positifs en possèdent deux, la [[racine carrée]] de ''y'' et son [[Opposé (mathématiques)|opposé]].

La fonction définie par
:<math>\begin{matrix}f: & \R & \rightarrow &\R\\ & x & \mapsto& 2x+1\\\end{matrix}</math>
est surjective puisque, pour tout réel arbitraire ''y'', il existe des solutions à l'équation ''y''&nbsp;= 2''x''&nbsp;+&nbsp;1 d'inconnue ''x'' ; une solution est ''x''&nbsp;= (''y''&nbsp;−&nbsp;1) / 2.

La fonction définie par
:<math>\begin{matrix}g: & \R & \rightarrow &\R\\ & x & \mapsto &\cos(x)\\\end{matrix}</math>
n'est pas surjective car les réels strictement plus grands que 1 ou strictement plus petits que –1 n'ont pas d'antécédent. Mais la fonction définie par
:<math>\begin{matrix}h: & \R & \rightarrow& [-1,1]\\ & x & \mapsto &\cos(x)\\\end{matrix}</math>
qui possède la même expression que ''g'', mais avec un ensemble d'arrivée qui a été restreint à l'ensemble des réels compris entre –1 et 1, est surjective. En effet, pour tout réel arbitraire ''y'' de l'intervalle [–1, 1], il existe des solutions à l'équation ''y''&nbsp;= cos(''x'') d'inconnue ''x'' : ce sont les réels ''x'' = ±[[Arc cosinus|arccos]](''y'') + 2''k''[[Pi|{{math|π}}]] pour tout [[entier relatif]] ''k''.

Sur ces quelques exemples, on voit qu'il est toujours possible de transformer une application non surjective en une surjection à condition de [[#Réduction de l'ensemble d'arrivée|restreindre son ensemble d'arrivée]].

== Propriétés ==
=== Réduction de l'ensemble d'arrivée ===
Si ''f'' est une application de ''X'' dans ''Y'' et Im(''f'') = ''f''(''X'') son [[ensemble image]] (c'est-à-dire l'ensemble des images par ''f'' des éléments de ''X''), alors l'application
:<math>\begin{matrix}s: & X & \rightarrow& f(X)\\ & x & \mapsto &f(x)\\\end{matrix}</math>
est une surjection.

En d'autres termes, si ''f'' est corestreinte à Im(''f''), c'est-à-dire si on remplace son ensemble d'arrivée par son ensemble image, elle devient '''surjective'''.

=== Décomposition canonique ===
{{Loupe|contenu=Paragraphe détaillé : [[Application (mathématiques)#Décomposition canonique|Décomposition canonique]] dans l'article [[application (mathématiques)|Application]].}}

Toute application ''f'' peut être décomposée comme ''f = i''∘''s'' où ''s'' est une surjection et ''i'' une injection. Cette décomposition est unique à un [[isomorphisme]] près. Une décomposition est fournie dans le paragraphe détaillé. Une autre (équivalente) est de choisir pour ''s'' la surjection définie ci-dessus, et pour ''i'' l'[[injection canonique]] de l'image de ''f'' dans son ensemble d'arrivée.

=== Images directes et réciproques ===
Pour toute application ''f'' :&nbsp;''X'' → ''Y'', les quatre propriétés suivantes sont équivalentes<ref name=Wikiversité>{{Note autre projet|Wikiversité|Application (mathématiques)/Exercices/Injection, surjection, bijection|les exercices corrigés du chapitre « Injection, surjection, bijection »|début=Voir par exemple}}</ref> :
# ''f'' est surjective ;
# tout [[sous-ensemble]] ''B'' de ''Y'' est l'[[image directe]] de son [[image réciproque]], {{c.-à-d.}} ''f''(''f''<sup> −1</sup>(''B'')) {{=}} ''B'' ;
# ''f''(''f''<sup> −1</sup>(''Y'')) {{=}} ''Y'' ;
#pour toute partie ''A'' de ''X'', le [[Complémentaire (théorie des ensembles)|complémentaire]] de l'image directe de ''A'' est inclus dans l'image directe du complémentaire de ''A'', {{c.-à-d.}} ''Y''\''f''(''A'') ⊂ ''f''(''X''\''A'').

=== Surjectivité et composée ===
[[Image:Surjective composition-fr.svg|cadre|Composée surjective : il est nécessaire que ''g'' soit surjective.]]
Soit ''f'' une application de ''X'' dans ''Y''.
* Pour toute application ''g'' de ''Y'' dans ''Z''<ref name=Wikiversité/> :
** si ''g''∘''f'' est surjective alors ''g'' est surjective ;
** si ''f'' et ''g'' sont surjectives alors ''g''∘''f'' est surjective ;
** si ''g ''est injective et si ''g''∘''f'' est surjective alors ''f ''est surjective.
* ''f'' est surjective si et seulement si, pour tout ''Z'' et pour toutes applications ''g'' et ''h'' de ''Y'' dans ''Z'', ''g''∘''f''&nbsp;= ''h''∘''f'' entraîne ''g''&nbsp;= ''h''<ref name=Wikiversité/>. En d'autres termes, les surjections sont précisément les [[épimorphisme]]s dans la [[catégorie des ensembles]].

=== Section et axiome du choix ===
{{ancre|Réciproque partielle et axiome du choix}}
Soit ''f'' une application de ''X'' dans ''Y''. Si ''f'' est {{Citation|[[inversible]] à droite}}, c'est-à-dire<ref>{{Ouvrage|titre=Cours de mathématiques|volume=1|titre volume=Notions fondamentales d'algèbre et d'analyse|auteur=[[Lucien Chambadal]]|auteur2=Jean-Louis Ovaert|éditeur=[[Gauthier-Villars]]|année=1966|page=27}}.</ref> s'il existe une application ''g'' de ''Y'' dans ''X'' telle que la [[fonction composée]] ''f''∘''g'' soit égale à l'[[application identité]] sur ''Y'', alors ''f'' est surjective (d'après une propriété vue [[#Surjectivité et composée|plus haut]]).

Une telle application ''g'' est appelée une ''[[Section (théorie des catégories)|section]]'', ou ''inverse à droite''<ref>{{Bourbaki-Ensembles}}, {{Google Livres|VDGifaOQogcC|page autre=SL252-PA19|{{p.|II-19}}}}.</ref> de ''f''. Elle est nécessairement [[injection (mathématiques)|injective]].

Réciproquement, si ''f'' est surjective alors elle admet une section. Cette propriété s'appuie sur le fait que l'on peut toujours « remonter les flèches » de ''Y'' vers ''X'' . Elle est toujours vraie si ''Y'' est fini. L'affirmation<ref>{{Harvsp|Bourbaki|p=II-18}}, la démontre en utilisant [[Axiome du choix#Une forme plus forte de l'axiome du choix : le epsilon de Hilbert|une forme plus forte que l'axiome du choix]].</ref> qu'elle est vraie pour tout ensemble ''Y'' est [[Axiome du choix#Autres formulations|équivalente à l'axiome du choix]]<ref>{{Ouvrage|auteur1=[[Saunders  Mac Lane]], [[Garrett Birkhoff]]|prénom1=|nom1=|prénom2=Jean|nom2=Weil|nom3=|titre=Algèbre et solutions développées des exercices : structures fondamentales, les grands théorèmes, théorie de Galois|passage=11|éditeur=J. Gabay|date=1996|isbn=2-87647-138-8|isbn2=978-2-87647-138-2|oclc=490130463|lire en ligne=|consulté le=}}</ref>.

{| width="100%" align="center" border="0" cellpadding="4" cellspacing="4" 
|- valign="top"
| width="50%" |
[[Image:Surjection-fr2.svg|cadre|centré|Construction d'une fonction ''g''.]]
| width="50%" |
[[Image:Surjection-fr3.svg|cadre|centré|''f''∘''g'' = Identité dans ''Y''.]]
|}

=== Cardinaux ===
* S'il existe une surjection de ''X'' dans ''Y'', alors (d'après ce qui précède, donc en admettant l'axiome du choix) il existe une injection de ''Y'' dans ''X'', autrement dit l'ensemble ''X'' a au moins autant d'éléments que l'ensemble ''Y'', au sens des [[Nombre cardinal|cardinaux]].
* [[Théorème de Cantor]] (sans axiome du choix) : pour tout ensemble ''X'', il n'existe aucune surjection de ''X'' dans l'[[Ensemble des parties d'un ensemble|ensemble de ses parties]].

== Dénombrement des surjections dans le cas fini ==
Le nombre de surjections d'un ensemble à {{Mvar|n}} éléments sur un ensemble à {{Mvar|p}} éléments est égal à  :
:<math>\sigma(n,p) =p! S(n,p)=\sum_{i=0}^p(-1)^{p-i}\binom pii^n </math>
où <math>S(n,p)</math> est le [[Nombre de Stirling#Nombre de Stirling de seconde espèce|nombre de Stirling de seconde espèce]].

Ceci peut se démontrer par la [[Formule d'inversion de Pascal#Applications classiques|formule d'inversion de Pascal]], ou le [[Principe d'inclusion-exclusion#Nombre de surjections d'un ensemble fini dans un autre|principe d'inclusion-exclusion]].

On peut définir ces nombres par récurrence avec l'initialisation : <math>\sigma(n,1)=1,\sigma(n,n)=n!</math>

et la [[Suite définie par récurrence|relation de récurrence]] : <math>\sigma(n,p)=p(\sigma(n-1,p)+\sigma(n-1,p-1))</math> pour <math>2\leqslant p\leqslant n-1</math><ref name=":0">{{Article|auteur1=Jean de Biasi|titre=Quelques triangles analogues à celui de Pascal|périodique=Bulletin de l'APMEP|numéro=332|pages=27-32|date=février 1982|lire en ligne=https://bibnum.publimath.fr/AAA/AAA82010.pdf}}</ref>.

{| class="wikitable"
|+ Tableau de valeurs ({{OEIS|A019538}})
!''n''&nbsp;\&nbsp;''p''
! width="9%" |1
! width="9%" |2
! width="9%" |3
! width="9%" |4
! width="9%" |5
|-
!1
|1
|-
!2
|1
|2
|-
!3
|1
|6
|6
|-
!4
|1
|14
|36
|24
|-
!5
|1
|30
|150
|240
|120
|}
On peut remarquer directement que <math>\sigma(p+1,p)=\binom{p+1}2p!=\frac{p(p+1)!}{2}</math> : {{OEIS|A001286}},

ainsi que <math>\sigma(p+2,p)=p(3p+1)\frac{(p+2)!}{4!}</math> : {{OEIS|A037960}}.

Plus généralement <math>\sigma(p+k,p)=\sigma_k(p)\frac{(p+k)!}{(2k)!}</math> où <math>\sigma_k</math> est un [[polynôme]] de degré <math> k</math><ref name=":0" />.

== Notes et références ==
{{Références}}

== Voir aussi ==
* [[Principe des tiroirs]]

{{Portail|mathématiques}}

[[Catégorie:Théorie des ensembles]]
[[Catégorie:Propriété de fonction|Surjectivite]]