% !TEX TS-program = LuaLaTeX
%\documentclass[ColorTheme=Red]{dino-iPhone}

\tgotitle{Relations binaires}
\tgoshorttoc
\section*{Avertissement}
{\itshape
Ce chapitre de la \emph{Mathematica dinosaurorum} a un statut un peu particulier, dans la mesure où il regroupe des notions somme toute assez basiques et que je ne tiens pas à présenter en introduction à d'autres chapitres. Il s'agit donc d'un texte destiné à servir de référence, et pas nécessairement à être lu d'une traite. Les exemples y sont donc peu nombreux, de même que les théorèmes, car tout ceci figure ou figurera dans les chapitres qui font référence à celui-ci.

}

\section{Généralités}
\subsection{Produit cartésien}
Deux ensembles $E$ et $F$ étant donnés, on appelle produit cartésien de $E$ et $F$ l'ensemble noté~$E\times F$ des couples $(x,y)$ où $x\in E$ et $y\in F$ :
\[z\in E\times F \iff \exists\, x \in E, \exists\, y\in F,\;\text{tels que}\; z=(x,y).\]

Dans le cas où $E=F$, on peut noter $E^2$ au lieu de $E\times E$. Ce cas particulier est important : par exemple, l'ensemble des couples des coordonnées des points du plan rapporté à un repère donné est~$\mathbb{R}^2$. On comprend alors que l'ordre de chaque couple est important et qu'il faut distinguer $(x,y)$ et~$(y,x)$, dans le cas de l'exemple qui vient d'être donné, mais aussi d'une façon générale.

Cette notion se généralise à plus de deux ensembles : par exemple~$\R^3$ est l'ensemble~\mbox{$\R\times\R\times\R$} des triplets ordonnés de réels.

\subsection{Parties d'un ensemble}
On dit qu'un ensemble $X$ est une partie d'un ensemble $E$ si tout élément de $X$ est un élément de $E$. On dit aussi que~$X$ est un sous-ensemble de $E$ ou que $X$ est inclus dans $E$, ce que l'on note $X \subset E$ :
\[X\subset E \iff \forall x,\; (x\in X\implies x\in E).\]

L'ensemble vide $\emptyset$ et l'ensemble $E$ lui-même sont des parties de $E$, et l'on note~$\Pt{E}$ l'ensemble de toutes les parties de $E$.
\[X\in \Pt{E}\iff X\subset E.\]

\begin{alert}
La propriété ci-dessus exprime le fait qu'une inclusion dans $E$ se traduit par une appartenance à $\Pt{E}$. Si $A$ et $B$ sont des parties de $E$, ce sont des \emph{éléments} de $\Pt{E}$, de même que~$\emptyset$ et~$E$. En revanche $\{A\}$, qui est un ensemble admettant pour seul élément la partie $A$ de $E$, est une partie de~$\Pt{E}$ de même que $\{\emptyset\}$ et $\{\emptyset, A, B,E\}$. En tant que parties de $\Pt{E}$, ce sont aussi des éléments de $\Pt{\Pt{E}}$! On notera aussi que l'ensemble vide~$\emptyset$, qui ne contient aucun élément, ne doit pas être confondu avec $\{\emptyset\}$, qui est un ensemble qui contient l'ensemble vide pour seul élément : ces deux ensembles sont des parties de $\Pt{E}$, distinctes l'une de l'autre. Enfin, il apparaît que $\emptyset$ est à la fois un élément et une partie de $\Pt{E}$…
\end{alert}

\begin{example}[Exemples]
\begin{enumerate}
\item Si $E=\{a,b\}$, $\Pt{E}=\{\emptyset,\{a\},\{b\},E\}$.
\item Si $E=\emptyset$, $\Pt{E}=\{\emptyset\}$, $\Pt{\Pt{E}}=\{\emptyset,\{\emptyset\}\}$ et \[\Pt{\Pt{\Pt{E}}}=\{\emptyset,\{\emptyset\},\{\{\emptyset\}\},\{\emptyset,\{\emptyset\}\}\}.\]
\end{enumerate}
\end{example}

\subsubsection{Opérations dans l'ensemble des parties}
On définit l'union (notée $\cup$) et l'intersection (notée $\cap$) de deux parties de $E$ de la façon suivante :

\smallskip\par
\begin{itemize}
\item\textit{Union :} $x\in A\cup B \iff ((x\in A)\;\text{ou}\;(x\in B))$.
\item\textit{Intersection :} $x\in A\cap B \iff ((x\in A)\;\text{et}\;(x\in B))$.
\end{itemize}
\smallskip\par

À propos de l'union, on notera qu'en mathématique le mot \frquote{ou} a \emph{toujours} un sens inclusif, c'est-à-dire \frquote{l'un ou l'autre ou les deux}. L'union et l'intersection de deux parties de $E$ sont elles-mêmes des parties de $E$.

De même on définit le complémentaire d'une partie $A$ de $E$ comme étant la partie de $E$ constituée des éléments de $E$ qui n'appartiennent pas à~$A$. Ce complémentaire est noté $E\smallsetminus A$ ou~$\complement_{E} A$. Lorsque qu'il n'y a aucune ambiguïté concernant l'ensemble $E$, on peut même le noter~$\bar{A}$.
\smallskip\par
\begin{itemize}
\item\textit{Complémentaire :} $x\in \complement_E A \iff ((x\in E)\;\text{et}\;(x\notin A))$.
\end{itemize}

\smallskip
Enfin on définit également la \emph{différence ensembliste} de deux parties $A$ et $B$ de $E$, notée~$A\smallsetminus B$ comme étant l'ensemble des éléments de $A$ qui ne sont pas éléments de $B$.
\smallskip\par
\begin{itemize}
\item\textit{Différence ensembliste :} $x\in A\smallsetminus B \iff ((x\in A)\;\text{et}\;(x\notin B))$.
\end{itemize}

\subsubsection{Partition d'un ensemble}
Soit un ensemble $E$  et $\symcal{C}$ une ensemble de parties de $E$ (c'est-à-dire un sous-ensemble ou encore une partie de $\Pt{E}$), on dit que $\symcal{C}$ est une partition de $E$ si les deux conditions suivantes sont vérifiées :
\begin{enumerate}
\item Tout élément de $\symcal{C}$ est non vide.
\item Tout élément de $E$ appartient à  un élément de $\symcal{C}$ et un seul.\label{cond2}
\end{enumerate}

\begin{remark}On notera que la condition~\ref{cond2} ci-dessus peut s'expliciter en disant que les parties qui constituent $\symcal{C}$ sont deux à deux disjointes (c'est-à-dire d'intersection vide) et que leur réunion est égale à$E$.
\end{remark}

\subsection{Relation binaire entre deux ensembles}\label{relbin}
Une \emph{relation binaire} $\symcal{R}$ entre deux ensembles $E$ et $F$ est définie par la donnée d'une partie~$\symcal{G}$ du produit cartésien~$E\times F$ (on a donc $\symcal{G}\in\Pt{E\times F}$). Cette partie, qui est donc un ensemble de couples, est le \emph{graphe} de la relation : par définition, un couple~$(x,y)$ de~$E\times F$ est lié par la relation~$\symcal{R}$ si~$(x,y)\in \symcal{G}$. Donner une relation binaire revient donc à donner son graphe. Si la relation est notée $\symcal{R}$, on écrit $x\mathrel{\symcal{R}}y$ ou $\symcal{R}(x,y)$ pour exprimer que~$x$ et~$y$, dans cet ordre, sont liés par la relation $\symcal{R}$. On a donc pour une relation~$\symcal{R}$ dont le graphe est $\symcal{G}$:
\[\forall (x,y)\in E\times F, \; x\mathrel{\symcal{R}}y\iff(x,y)\in \symcal{G}.\]

\begin{example}[Exemples]
\begin{enumerate}
\item L'égalité est une relation binaire qui peut être définie sur tout ensemble $E$. Son graphe est ce que l'on nomme la \emph{diagonale} de $E$, c'est à dire l'ensemble des couples $(x,y)$ de~$E^2$ tels que~$x=y$.

%\item L'ordre strict dans l'ensemble des réels est une relation binaire notée~$<$ (on aurait également pu considérer un ordre large ou l'ordre inverse). Par définition, $x<y$ traduit le fait que $y-x$ est un réel strictement positif :
%\[\forall (x,y) \in \R^2, \; x<y \iff (y-x)\in \R^{*}_+.\]
%Le graphe de cette relation peut être représenté par l'ensemble des points du plan repéré dont l'ordonnée est strictement supérieure  à l'abscisse, c'est à dire les points situés strictement au dessus de la droite d'équation $y=x$ (première bissectrice du repère).
%\label{ord-strict}
%On notera que la \emph{règle des signes}, reposant sur la \emph{partition} de $\R$ en trois ensembles qui sont $\R^*_-$, le singleton $\{0\}$ et $\R^*_+$, préexiste à la définition d'un ordre dans $\R$.

\item Le relation $p$ définie entre $\R$ et $\R_+$ par 
\[\forall (x,y)\in \R\times \R_+,\; p(x,y)\iff y=x^2.\]
Le graphe de $p$ peut être représenté, dans le demi-plan repéré des points d'ordonnée positive, par la parabole d'équation~$y=x^2$. On notera que cette relation est en réalité une fonction et que la notation $y=p(x)$ aurait été plus habituelle; nous y reviendrons. 
\end{enumerate}
\end{example}

% Dans le cas d'une
%relation fonctionnelle (voir  \S~\ref{Rfonc} ci-dessous), pour laquelle un seul élément y de $F$ est en relation avec un élément $x$ donné dans $E$, on écrit en général $y=\symcal{R}(x)$. 
%

\section{Relations d'équivalence}
\subsection{Définition}
On dit qu'une relation $\symcal{R}$, définie sur $E$ (on se place donc dans le cas où $E=F$) est une relation d'équivalence si elle possède les trois propriétés suivantes :
\begin{enumerate}
\item Elle est \emph{réflexive}, c'est-à-dire que tout élément de $E$ est en relation avec lui même :
\[\forall x \in E,\; x\mathrel{\symcal{R}}x.\]
\item Elle est \emph{symétrique}:
\[\forall (x,y)\in E\times E,\; (x\mathrel{\symcal{R}}y \implies y\mathrel{\symcal{R}}x).\]
\item Elle est \emph{transitive} :
%\[
%\forall (x,y,z)\in E^3,\quad \left.\begin{aligned}
%x&\mathrel{\symcal{R}}y\\
%&\text{et}\\
%y&\mathrel{\symcal{R}}z
%\end{aligned}\right\}
%\implies x\mathrel{\symcal{R}}z
%\]
\[
\forall (x,y,z)\in E^3,\; \bigl((x\mathrel{\symcal{R}}y\;\text{ et }\;y\mathrel{\symcal{R}}z)\implies x\mathrel{\symcal{R}}z\bigr).
\]
\end{enumerate}

\begin{example}[Exemples]
\begin{enumerate}
\item L'égalité est une relation d'équivalence sur tout ensemble, c'est une conséquence directe de la définition.
\item Si l'on désigne par $\symfrak{D}$ l'ensemble des droites du plan, le parallélisme est une relation d'équivalence sur $\symfrak{D}$ : c'est immédiat également,  on peut noter au passage que la transitivité traduit le fait que \frquote{deux droites parallèles à une même troisième sont parallèles entre elles}.
\item Pour un ensemble $E$ donné, la relation dont le graphe est $E\times E$ est une relation d'équivalence. Tous les couples d'éléments de $E$ sont donc liés par cette relation.
\item La relation $\equiv$ définie dans l'ensemble $\Z$ des entiers par
\[\forall (m,n)\in\Z\times\Z,\; m\equiv n \iff (m-n) \text{ est un entier pair.}\]
est une relation d'équivalence.

Rappelons qu'un élément $p$ de $\Z$ est un entier pair s'il est divisible par~$2$, c'est-à-dire s'il existe $k$ appartenant à $\Z$ tel que~$p=2k$ et montrons que la relation~$\equiv$ remplit bien les conditions requises :
\begin{enumerate}
\item \emph{Réflexivité. — }Soit $m\in\Z$ un entier quelconque : $m-m=0=2\times0$. Donc~$m-m$ est pair. La relation $\equiv$ est réflexive.
\item \emph{Symétrie. — }Soit $m$ et $n$ deux entiers tels que $m\equiv n$. Alors il existe un entier~$k$ tel que~$m-n=2k$. Il suffit alors d'écrire $n-m=2\times(-k)$ pour constater que $n\equiv m$. La relation~$\equiv$ est symétrique.
\item\emph{Transitivité. — }Soit $(m,n,p)$ dans $\Z^3$ tels que $m\equiv n$ et $n\equiv p$. Il existe alors deux entiers~$k$ et~$k'$ tels que \mbox{$m-n=2k$} et $n-p=2k'$. Il suffit de remarquer que 
\[m-p=(m-n)+(n-p)=2(k+k'), \text{ où $(k+k')\in\Z$}\] 
pour établir que $m\equiv p$. La relation $\equiv$ est donc transitive.
\end{enumerate}
\end{enumerate}
\end{example}
%\subsection{Exemples}

\subsection{Classes d'équivalence}
Soit un ensemble $E$ et une relation d'équivalence $\symcal{R}$ sur$E$. On dit qu'une partie~$A$ de~$E$ est une classe d'équivalence modulo la relation~$\symcal{R}$ s'il existe un élément $x$ de~$E$ tel que~$A$ soit l'ensemble des éléments~$y$ de~$E$ pour lesquels la relation~$x\mathrel{\symcal{R}}y$ est vérifiée. On note alors~$A=\cl_{\symcal{R}} (x)$ ou~$A=\cl (x)$ s'il n'y a pas d'ambiguité.
\[y\in\cl_{\symcal{R}} (x)\iff x\mathrel{\symcal{R}}y.\]

\begin{thm}
Soit un ensemble $E$ et une relation d'équivalence $\symcal{R}$ sur $E$. L'ensemble des classes d'équivalence modulo $\symcal{R}$ constitue une partition de $E$.
\end{thm}

\begin{proof}
Tout d'abord la réflexivité de la relation $\symcal{R}$ entraîne que pour tout~$x$ appartenant à~$E$,~$x$ appartient à~$\cl(x)$. Par conséquent, tout $x\in E$ appartient à une classe et toute classe est non vide. Il nous reste à prouver que tout élément $x$ de $E$ appartient à une seule classe, c'est à dire que s'il existe un élément $y$ de $E$ tel que $x\in \cl(y)$, alors $\cl(x)=\cl(y)$.

Nous allons procéder par double inclusion.
\begin{itemize}
\item Soit donc $y\in E$ tel que $x\in\cl(y)$. On sait que $y\mathrel{\symcal{R}}x$, donc,
pour tout~$z\in \cl(x)$, on a à la fois $y\mathrel{\symcal{R}}x$ et $x\mathrel{\symcal{R}}z$ : par transitivité on obtient~$y\mathrel{\symcal{R}}z$, soit~$z\in\cl(y)$ :
\[\forall z\in E, (z\in\cl(x)\implies z\in\cl(y), \text{ donc }\cl (x)\subset\cl (y).\]
 \item Par symétrie de la relation d'équivalence $\symcal{R}$, on a aussi~$x\mathrel{\symcal{R}}y$. On peut alors refaire le même raisonnement que ci-dessus : 
 pour tout $z$ appartenant à $\cl(y)$ on a  à la fois~$x\mathrel{\symcal{R}}y$ et~$y\mathrel{\symcal{R}}z$, 
 donc par transitivité $x\mathrel{\symcal{R}}z$, soit~\mbox{$z\in\cl(x)$} :
\[\forall z\in E, (z\in\cl(y))\implies z\in\cl(x), \text{ donc }\cl (y)\subset\cl (x).\]
\item Finalement $\cl(x)=\cl(y)$.\qedhere
\end{itemize}
\end{proof}

\begin{remark}
Réciproquement, toute partition $\symcal{C}$ d'un ensemble $E$ est l'ensemble des classes d'une relation d'équivalence. Il suffit en effet de considérer la relation $\sim$ telle que pour tout~$(x,y)$ dans $E^2$, on ait \textit{$x\sim y$ si $x$  appartient au même élément de $\symcal{C}$ que~$y$}, laquelle répond à la question.
\end{remark}
%\end{document}
%\subsubsection{Notion de structure quotient}

\section{Relations d'ordre}
\subsection{Définition}
On dit qu'une relation $\preccurlyeq$, définie sur $E$ (on se place donc ici encore dans le cas où~$E=F$) est une relation d'ordre si elle possède les trois propriétés suivantes :
\begin{enumerate}
\item Elle est \emph{réflexive}, c'est-à-dire que tout élément de $E$ est en relation avec lui même :
\[\forall x \in E,\; x\preccurlyeq x.\]
\item Elle est \emph{antisymétrique}:
\[\forall (x,y)\in E\times E,\; \bigl((x\preccurlyeq y)\text{ et }(y\preccurlyeq x)\implies x=y\bigr).\]
\item Elle est \emph{transitive} :
%\[
%\forall (x,y,z)\in E^3,\quad \left.\begin{aligned}
%x&\mathrel{\symcal{R}}y\\
%&\text{et}\\
%y&\mathrel{\symcal{R}}z
%\end{aligned}\right\}
%\implies x\mathrel{\symcal{R}}z
%\]
\[
\forall (x,y,z)\in E^3,\; \bigl((x\preccurlyeq y\;\text{ et }\;y\preccurlyeq z)\implies x\preccurlyeq z\bigr).
\]
\end{enumerate}

\begin{remark}
La démonstration du résultat suivant est immédiate.

Une relation d'ordre $\preccurlyeq$ sur un ensemble $E$ étant donnée, la relation~$\succcurlyeq$, définie par 
\[\forall (x,y) \in E^2, x\succcurlyeq y \iff y\preccurlyeq x\,,\] 
est une relation d'ordre sur $\R$ nommée \emph{ordre inverse} de $\preccurlyeq$.
\end{remark}

%\begin{exemple}[Exemples]
%\begin{enumerate}
%\item La relation d'ordre strict sur l'ensemble $\R$ des réels, telle que nous l'avons rencontrée dans l'exemple~\ref{ord-strict} du paragraphe~\ref{relbin} n'est pas une relation d'ordre, car elle n'est pas réflexive. En revanche l'ordre large correspondant, défini par 
%\[\forall (x,y) \in \R^2, \; x\leq y \iff (y-x)\in \R_+\,,\]
%est bien une relation d'ordre. En effet :
%\begin{itemize}
%\item Pour tout $x$ réel, $x-x=0$ et $0\in \R_+$, ce qui assure que la relation~$\leq$ est \emph{réflexive}.
%\item Pour tout couple de réels $(x,y)$, si $x\leq y$ et $y\leq x$ alors $x=y$. En effet, en effet, $y\leq x$ signifie que $(x-y)\in \R_+$. Le réel $(y-x)$ se retrouve donc appartenir à la fois à $\R_+$ (car $x\leq y$) et à $\R_-$ (en tant qu'opposé de $(x-y)$) ; on en déduit que $y-x=0$ donc que $x=y$. La relation~$\leq$ est donc \emph{antisymétrique}.
%\item Soit $(x,y,z)\in\R^3$, on a $z-x=(z-y)+(y-x)$. On en déduit que si $x\leq y$ et $y\leq z$, $z-x$ est élément de $\R_+$ et tant que somme de deux éléments de $\R_+$, ce qui revient à dire que $x\leq z$. Le relation~$\leq$ est donc \emph{transitive}.
%\end{itemize}
%\end{enumerate}
%\end{exemple}

\subsection{Ordre dans les ensembles de nombres}
Les relations usuelles $<$ et $>$, définies sur les ensembles de nombres, \emph{ne sont pas} des relations d'ordre, il est facile de l'établir : ces relations \emph{ne sont pas} réflexives. Il est en revanche plus délicat de démontrer que les relations~$\leq$ et~$\geq$ sont des relations d'ordre, et même de tout simplement définir ces relations.
 On pourrait songer à définir l'ordre dans $\R$ en disant que~$x\leq y$ si $(y-x)\in \R_{+}$… Mais alors il resterait à définir $\R_{+}$ sans utiliser l'ordre, ce qui ne semble nullement évident. C'est pour cette raison que nous nous contenterons d'affirmer que la relation $\leq$, telle que chacun la connaît, est bien une relation d'ordre sur $\R$ (ainsi d'ailleurs que sur $\N$, $\Z$, $\symbb{D}$ et $\Q$).
 
% 
\subsection{Un peu de vocabulaire}
On se donne dans ce paragraphe un ensemble $\symcal{E}$ sur lequel est définie une relation d'ordre~$\preccurlyeq$.
\subsubsection{Ordre total}
 On dit que la relation $\preccurlyeq$ définit un ordre total sur $\symcal{E}$ si pour tout couple~$(x,y)$ d'éléments de~$\symcal{E}$, la proposition 
 \XSmartphoneCommand{$\bigl((x\preccurlyeq y)\text{ ou }(y\preccurlyeq x)\bigr)$}
 \SmartphoneCommand{%
 \[
 \bigl((x\preccurlyeq y)\text{ ou }(y\preccurlyeq x)\bigr)
 \]%
 }
  est vraie. 

\subsubsection{Majorants, minorants \& C\up{ie}}
Soit maintenant $\symcal{A}$ une partie de $\symcal{E}$.

\begin{itemize}
\item On dit qu'un élément $M$ de $\symcal{E}$ est un majorant de $\symcal{A}$, si $\forall x\in \symcal{A},\, x\preccurlyeq M$.
\item On dit qu'un élément $m$ de $\symcal{E}$ est un minorant de $\symcal{A}$, si $\forall x\in \symcal{A},\, m\preccurlyeq x$.
\item On dit que $\symcal{A}$ admet $A$ pour plus grand élément si $A\in \symcal{A}$ et si $A$ est un majorant de $\symcal{A}$.
\item On dit que $\symcal{A}$ admet $a$ pour plus petit élément si $a\in \symcal{A}$ et si $a$ est un minorant de~$\symcal{A}$.
\end{itemize}



\begin{remark}
Dans un ensemble muni d'une relation d'ordre, l'existence d'un majorant, d'un minorant, d'un plus petit ou d'un plus grand élément n'est nullement assurée. On a en revanche le résutat suivant.
\end{remark}

\begin{thm}
Soit un ensemble $\symcal{E}$ sur lequel est définie une relation d'ordre $\preccurlyeq$ et soit $\symcal{A}$ une partie de~$\symcal{E}$. Si~$\symcal{A}$ admet une plus grand élément (respectivement un plus petit élément) pour la relation $\preccurlyeq$, ce plus grand élément (respectivement ce plus petit élément) est unique.
\end{thm}
\begin{proof}
Nous proposons la démonstration dans le cas du plus petit élément, celle de l'autre cas est identique. Supposons que~$a$ et~$a'$ soient des plus petits éléments de $\symcal{A}$. D'après la définition d'un plus petit élément, on sait que pour tout~$x$ de~$\symcal{A}$, $a\preccurlyeq x$ et en particulier~\mbox{$a\preccurlyeq a'$}. Et de la même façon, on sait que pour tout $x$ de $\symcal{A}$, $a'\preccurlyeq x$ et en particulier~\mbox{$a'\preccurlyeq a$}. L'antisymétrie de la relation $\preccurlyeq$ nous assure alors que $a=a'$, d'où l'unicité du plus petit élément.
\end{proof}

Supposons maintenant que $\symcal{A}$ admette $A$ pour plus grand élément et soit $\symcal{M}$ l'ensemble de tous les majorants de $\symcal{A}$. Il va de soi que $\symcal{A}\cap\symcal{M}=\{A\}$. L'élément $A$ apparaît ainsi également comme le plus petit élément de $\symcal{M}$. De la même façon, si $\symcal{A}$ admet un plus petit élément, ce dernier est le plus grand des minorants de $\symcal{A}$.

\begin{alert}
Dans le cas où $\symcal{A}$ ne possède pas de plus grand élément, il n'est nullement assuré que~$\symcal{M}$ possède un plus petit élément, ni même d'ailleurs que $\symcal{M}$ soit non vide. Néanmoins il est possible que $\symcal{M}$ possède un plus petit élément, et ceci que $\symcal{A}$ possède ou non un plus grand élément. Ce plus petit élément de $\symcal{M}$ est alors par définition la \emph{borne supérieure} de~$\symcal{A}$ dans l'ensemble $\symcal{E}$ ordonné par $\preccurlyeq$. 
\end{alert}

 \section{Applications, fonctions}\label{Rfonc}
%%%Fonction caractéristique, cardinal de $\symcal{P}(E)$ ou $\symfrak{P}(E)$
\subsection{Définition}
On dit qu'une relation binaire $f$ entre deux ensembles $E$ et~$F$ est fonctionnelle ou qu'elle est une \emph{fonction} définie sur~$E$ et à valeurs dans $F$ ou encore une \emph{application} de~$E$ dans $F$ si tout élément $x$ de $E$ est en relation avec un élément~$y$ de~$F$ et un seul. Cet élément $y$ est appelé \emph{image} de~$x$ par~$f$ et noté $f(x)$ (autrement dit on écrit plus volontiers~$y=f(x)$ que~$x \mathrel{f}y$). L'ensemble $E$ est l'ensemble de départ de la fonction et l'ensemble $F$ son ensemble d'arrivée. 

Une application est donc déterminée par la donnée de son ensemble de départ, de son ensemble d'arrivée et d'un procédé décrivant une correspondance fonctionnelle entre ces deux ensembles. On note souvent :

\begin{align*}&f\::\;E\to F\;,\quad x\longmapsto f(x)\,.\\
\intertext{Par exemple :}
&f\::\;\left]-1,1\right[\to\R\;,\quad x \longmapsto \frac{1}{x^2-1}\;,\\
\intertext{ou}
&g\::\;\Z\to\{0,1\}\;,\quad p\longmapsto
\begin{cases} 0&\text{ si $p$ est pair,}\\
1&\text{ sinon.}
\end{cases}
\end{align*}

Il n'y a pas de distinction entre fonction et application, mais le contexte peut introduire certaines nuances. En effet, lorsque $E$ est une partie de l'ensemble $\R$ des nombres réels, $f(x)$ est souvent donné par une expression, sa valeur étant le résultat d'un calcul. On emploie alors plus volontiers le vocable \emph{fonction} et dans ce cas l'ensemble de départ peut ne pas être précisé et correspond alors à l'ensemble des valeurs de $x$ pour lesquelles le calcul de $f(x)$ est possible. On parle alors plutôt d'ensemble de définition que d'ensemble de départ. 

\begin{example}[Exemples]
\begin{enumerate}
\item Soit la fonction $f$ de la variable réelle $x$, telle que 
\[f(x)=\frac{x}{x^2-4}\;.
\]
Déterminons l'ensemble de définition $\symcal{D}_f$ de la fonction $f$. On a 
\begin{align*}
x\in \symcal{D}_f &\iff x^2-4\neq 0\\
&\iff x\neq -2 \text{ et } x\neq 2.
\end{align*}

Donc $\symcal{D}_f= \R\smallsetminus\{-2,2\}$.
\item Soit la fonction $g$ telle que $g(x)=\sqrt{1-x^2}$. Déterminons l'ensemble de définition de $g$. On a
\[
x\in \symcal{D}_g \iff 1-x^2\geq 0.
\]

Il nous faut donc résoudre l'inéquation $1-x^2\geq0$. Le polynôme $1-x^2$ admet les nombres~$-1$ et~$1$ pour racines et le coefficient de $x^2$ est négatif :~\mbox{$1-x^2$} est donc positif dans l'intervalle des racines (on  pourra consulter le volet consacré aux polynômes du second degré).

Donc $\symcal{D}_g= \left[-1,1\right]$.
\end{enumerate}
\end{example}

\subsection{Antécédents, surjections, injections \& bijections}
\subsubsection{Notion d'antécédent}
Soit une application $f$ de $E$ dans $F$ et soit~$b$ élément de~$F$. On dit qu'un élément~$a$ de~$E$ est un \emph{antécédent} de $b$ si $f(a)=b$, autrement dit si~$b$ est l'image de~$a$ par $f$.
Alors que la définition d'une fonction entraîne que l'image d'un quelconque élément de $E$ existe et est unique, dans le cas d'une recherche d'antécédent, rien de ce genre n'est assuré.

Considérons par exemple la fonction \emph{carré} définie par
\[f\::\;\R\to\R\;,\quad x\longmapsto f(x)=x^2 \]
et recherchons les antécédents par $f$ d'un élément~$y$ de~$\R$, c.-à-d. les solutions de l'équation d'inconnue~$x$ :~\mbox{$x^2=y$}.
\begin{itemize}
\item \textit{Si $y>0$} : $y$ admet deux antécédents qui sont $\sqrt{y}$ et $-\sqrt{y}$.
\item \textit{Si $y=0$} : le seul antécédent de $0$ est $0$.
\item \textit{Si $y<0$} : $y$ ne possède aucun antécédent.
\end{itemize}
\begin{remark}
Il faut remarquer ici que la connaissance précise des ensembles de départ et d'arrivée est indispensable à la recherche des antécédents. Considérons la fonction
\[g\::\;\R_+\to\R_+\;,\quad x\longmapsto g(x)=x^2. \]
Les expressions de $g(x)$ et de $f(x)$ sont parfaitement identiques, mais, contrairement à ce que nous venons d'étudier pour la fonction $f$,  dans le cas de la fonction $g$ tout élément~$y$ de l'ensemble d'arrivée possède un antécédent unique qui est $\sqrt{y}$.
\end{remark}
\subsubsection{Surjections, injections et bijections}
\begin{remark}[Surjections]
On dit qu'une application $f$ de $E$ dans $F$ est \emph{surjective} (ou encore que~$f$ est une \emph{surjection}) si tout élément de $F$ possède au moins un antécédent dans~$E$.
\end{remark}
\begin{remark}[Injections]
On dit qu'une application $f$ de $E$ dans $F$ est \emph{injective} (ou encore que $f$ est une \emph{injection}) ou encore si  deux éléments distincts quelconques de $E$, ont des images distinctes. De façon plus formelle,~\mbox{$f\::\;E\to F$} est injective si
\begin{gather}\forall(x,y)\in E\times E, \;\bigl(x\neq y\implies f(x)\neq f(y)\bigr).\label{condinj1}\\
\intertext{Ou, par contraposition, $f\::\;E\to F$ est injective si}
\forall(x,y)\in E\times E, \;\bigl(f(x)= f(y)\implies x=y\bigr).\label{condinj2}
\end{gather}

On peut dire également que $f$ est injective si et seulement si tout élément de $F$ possède au plus un antécédent dans~$E$.
\end{remark}

\begin{remark}[Bijections]
On dit qu'une application $f$ de $E$ dans $F$ est \emph{bijective} (ou encore que $f$ est une \emph{bijection}) si tout élément de $F$ possède un antécédent dans $E$ et un seul, autrement dit si $f$ est à la fois surjective et injective.

Si l'application $f\::\;E\to F$ est bijective, l'application qui à tout élément de $F$ associe son unique antécédent dans $E$ est évidemment bijective : c'est la \emph{bijection réciproque} de~$f$, notée~$f^{-1}$.
\end{remark}
\begin{example}[Exemples]
\begin{enumerate}
\item \label{phi} Soit l'application 
\[
\phi\::\;\R\smallsetminus\{1\}\to\R\,,\quad x\longmapsto \frac{2x}{x-1}\;.
\]

Donnons-nous un réel $y$ quelconque et recherchons ses antécédents, qui sont les solutions dans $\R\smallsetminus\{1\}$ de l'équation $\phi(x)=y$, que nous résolvons ici :
\begin{align*}
\frac{2x}{x-1}=y &\iff 2x=y(x-1)\text{ et } x\neq 1\,,\\
&\iff x(2-y)=-y\text{ et } x\neq 1\,,\\
&\iff x(y-2)=y\text{ et } x\neq 1\,.
\end{align*}
\begin{itemize}
\item\textit{Si $y=2$}, l'équation est équivalente à $0=2$ et n'a donc pas de solution. Le réel $2$ n'a pas d'antécédent par $\phi$.
\item\textit{Si $y\neq 2$}, l'équation admet \[x=\frac{y}{y-2}\] pour unique solution (il est clair en effet que $y/(y-2)$ ne peut être égal à $1$).
\end{itemize}


En résumé, le réel $2$ ne possède aucun antécédent et les réels différents de $2$ possèdent un antécédent et un seul. L'application $\phi$ est donc injective, mais n'est pas surjective.
\item Soit maintenant l'application
\[
\psi\::\;\R\smallsetminus\{1\}\to\R\smallsetminus\{2\}\,,\quad x\longmapsto \frac{2x}{x-1}\;.
\]

On notera que les applications $\phi$ et $\psi$ ne diffèrent que par leur ensemble d'arrivée. Cependant, l'étude faite ci-dessus en \ref{phi} prouve que $\psi$ est bijective et que sa bijection réciproque est 
\[
\psi^{-1}\::\;\R\smallsetminus\{2\}\to\R\smallsetminus\{1\}\,,\quad x\longmapsto \frac{x}{x-2}\;.
\]
\item L'application $\theta$ définie par 
\[
\theta\::\;\R\to\R\,,\quad x\longmapsto x^2-1
\]
n'est ni injective ni surjective. En effet $\theta(x)$ est nul si et seulement si $x^2=1$, c.-à-d si et seulement si $x=-1$ ou $x=1$ : le réel $0$ possède donc deux antécedents pour $\theta$. Par ailleurs, pour tout réel~$x$,~$x^2\geq0$, donc $\theta(x)\geq-1$ : le réel $-2$, par exemple, ne possède aucun antécédent par $\theta$.
\end{enumerate}
\end{example}
\subsection{Composée de deux applications}

Soit deux applications $f\::\;E\to F$ et $g\::\;F\to G$, on appelle \emph{application composée de~$f$ par~$g$} et on note $g\rond f$ l'application de $E$ dans $G$ définie par :
\[g\rond f\::\; E\to G\,,\quad x\longmapsto g\rond f(x) = g\bigl(f(x)\bigr).\]

Notons qu'il est important pour définir $g\rond f$ que l'ensemble d'arrivée de $f$ coïncide avec l'ensemble de départ de~$g$.

\begin{example}
Soit 
\[
f\::\;\R^*\to\R\,,\; x\mapsto \frac1x\;\text{ et }\;g\::\:\R\to\R\,,\; x\mapsto x^2+1\,.
\]
Déterminons $g\rond f$ qui est une application de $\R^*$ dans $\R$.

On a pour tout $x\in\R^*$,
\begin{align*}
g\rond f(x) &= g\bigl(f(x)\bigr),\\
&={\bigl(f(x)\bigr)}^2+1,\\
&={\left(\frac1x\right)}^2+1,\\
\intertext{ou, en réduisant au même dénominateur,}
g\rond f(x)&= \frac{1+x^2}{x^2}\;.
\end{align*}
\begin{remark}
On notera que la même lettre $x$ intervient dans les définitions de~$f$ et~$g$. Il s'agit bien sûr d'une lettre muette, qui pourrait dans chaque cas être remplacée par n'importe quelle autre lettre (en évitant tout de même les lettres $f$ et $g$!).
\end{remark}
\end{example}

\begin{thm}Soit deux applications $f\::\;E\to F$ et $g\::\;F\to G$. Si $f$ et $g$ sont des bijections, alors l'application composée $g\rond f$ est une bijection dont la bijection réciproque est $f^{-1}\rond g^{-1}$. 
\end{thm}

\begin{proof}
Soit deux bijections $f\::\;E\to F$ et $g\::\;F\to G$. % et un élément $a$ de $E$. 
%Si $a$ est un antécédent de $b$ par $g\rond f$, on a $g\rond f(a)=c$, soit $g\bigl(f(a)\bigr)=c$. 
\begin{enumerate}
\item\label{gofsurj} Donnons nous un élément $c$ quelconque de $G$. Les applications~$g$ et~$f$ étant surjectives, $c$ possède un antécédent~$b$ par $g$  et $b$ possède lui-même un antécédent $a$ par $f$. On a alors 
\[g\rond f(a) =g\bigl(f(a)\bigr)=g(b)=c.\]
L'élément $c$ admet $a$ pour antécédent par $g\rond f$ qui est donc  est donc application surjective.
\item Supposons maintenant qu'il existe un élément $c$ de $G$ et $a$ et $a'$ éléments de $E$ tels que~$g\rond f(a)=g\rond f(a')$. Alors  $g\bigl(f(a)\bigr)=g\bigl(f(a')\bigr)$ et puisque $g$ est injective on a, d'après la proposition \eqref{condinj2} p.~\pageref{condinj2},  $f(a) = f(a')$; l'application $f$ étant elle-même injective, on obtient finalement~$a=a'$. On a donc prouvé que 
\[\forall(a,a')\in E\times E, \;\bigl(g\rond f(a)= g\rond f(a')\implies a=a'\bigr),\]
autrement dit que $g\rond f$ est injective.
\item L'application $g\rond f$ est donc surjective et injective : elle est bijective. On remarque alors en employant les notations du point \ref{gofsurj} ci-dessus \mbox{que $a=f^{-1}(b)$} et $b=g^{-1}(c)$, \mbox{d'où $a=f^{-1}\bigl(g^{-1}(c)\bigr)$}, ce qui achève la démonstration en prouvant que 
\[{\bigl(g\rond f\bigr)}^{-1}=f^{-1}\rond g^{-1}.\qedhere\]
\end{enumerate}
\end{proof}

\begin{remark}
La réciproque de ce théorème est fausse. Considérons par exemple les applications suivantes :
\[
f\::\;\R_+\to\R\,,\; x\mapsto \sqrt{x}\;\text{ et }\;g\::\;\R\to\R_+\,,\; x\mapsto x^2.
\]
Pour tout réel $x$ positif, on a $g\bigl(f(x)\bigr)=\bigl(\sqrt{x}\bigr)^2=x$, par définition de la racine carrée. Par conséquent, on a 
\[g\rond f \::\;\R_+\to\R_+\,,\quad x\longmapsto x,\]
qui est à l'évidence une bijection. Cependant, $f$ n'est pas surjective (les nombres strictement négatifs n'ont pas d'antécédent) et $g$ n'est pas injective (deux nombres opposés non nuls ont la même image).
\end{remark}

On a néanmoins le théorème suivant:
\begin{thm}
Soit deux applications $f\::\;E\to F$ et $g\::\;F\to G$. Si $g\rond f$ est injective, $f$ est injective. Si $g\rond f$ est surjective, $g$ est surjective.
\end{thm}

\begin{proof}
\begin{itemize}
\item Supposons  $g\rond f$ injective et soit $x$ et $y$ éléments de $E$ tels que~\mbox{$f(x)=f(y)$}. Montrons que nécessairement $x=y$, ce qui établira que~$f$ est injective.

Puisque $f(x)=f(y)$, $g\bigl(f(x)\bigr)=g\bigl(f(y)\bigr)$, soit $g\rond f(x)=g\rond f(y)$ : on en déduit que~$x=y$, car $g\rond f$ est injective par hypothèse. Par conséquent~$f$ est injective.
\item Supposons  $g\rond f$ surjective et soit $z$ un élément de $G$. L'application~$g\rond f$ étant surjective, il existe un élément $x$ de $E$ tel que $g\rond f(x)=z$, soit~$g\bigl(f(x)\bigr)=z$. L'élément~$z$ admet donc $f(x)$ pour antécédent par $g$, ce qui prouve que~$g$ est surjective. \qedhere
\end{itemize}
\end{proof}
\endinput