Debian Codegraph @

texmf-dist/doc/lualatex/tango/examples/rel-bin.tex

raw
1 % !TEX TS-program = LuaLaTeX
2 %\documentclass[ColorTheme=Red]{dino-iPhone}
3
4 \tgotitle{Relations binaires}
5 \tgoshorttoc
6 \section*{Avertissement}
7 {\itshape
8 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.
9
10 }
11
12 \section{Généralités}
13 \subsection{Produit cartésien}
14 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$ :
15 \[z\in E\times F \iff \exists\, x \in E, \exists\, y\in F,\;\text{tels que}\; z=(x,y).\]
16
17 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.
18
19 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.
20
21 \subsection{Parties d'un ensemble}
22 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$ :
23 \[X\subset E \iff \forall x,\; (x\in X\implies x\in E).\]
24
25 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$.
26 \[X\in \Pt{E}\iff X\subset E.\]
27
28 \begin{alert}
29 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}$…
30 \end{alert}
31
32 \begin{example}[Exemples]
33 \begin{enumerate}
34 \item Si $E=\{a,b\}$, $\Pt{E}=\{\emptyset,\{a\},\{b\},E\}$.
35 \item Si $E=\emptyset$, $\Pt{E}=\{\emptyset\}$, $\Pt{\Pt{E}}=\{\emptyset,\{\emptyset\}\}$ et \[\Pt{\Pt{\Pt{E}}}=\{\emptyset,\{\emptyset\},\{\{\emptyset\}\},\{\emptyset,\{\emptyset\}\}\}.\]
36 \end{enumerate}
37 \end{example}
38
39 \subsubsection{Opérations dans l'ensemble des parties}
40 On définit l'union (notée $\cup$) et l'intersection (notée $\cap$) de deux parties de $E$ de la façon suivante :
41
42 \smallskip\par
43 \begin{itemize}
44 \item\textit{Union :} $x\in A\cup B \iff ((x\in A)\;\text{ou}\;(x\in B))$.
45 \item\textit{Intersection :} $x\in A\cap B \iff ((x\in A)\;\text{et}\;(x\in B))$.
46 \end{itemize}
47 \smallskip\par
48
49 À 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$.
50
51 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}$.
52 \smallskip\par
53 \begin{itemize}
54 \item\textit{Complémentaire :} $x\in \complement_E A \iff ((x\in E)\;\text{et}\;(x\notin A))$.
55 \end{itemize}
56
57 \smallskip
58 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$.
59 \smallskip\par
60 \begin{itemize}
61 \item\textit{Différence ensembliste :} $x\in A\smallsetminus B \iff ((x\in A)\;\text{et}\;(x\notin B))$.
62 \end{itemize}
63
64 \subsubsection{Partition d'un ensemble}
65 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 :
66 \begin{enumerate}
67 \item Tout élément de $\symcal{C}$ est non vide.
68 \item Tout élément de $E$ appartient à un élément de $\symcal{C}$ et un seul.\label{cond2}
69 \end{enumerate}
70
71 \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$.
72 \end{remark}
73
74 \subsection{Relation binaire entre deux ensembles}\label{relbin}
75 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}$:
76 \[\forall (x,y)\in E\times F, \; x\mathrel{\symcal{R}}y\iff(x,y)\in \symcal{G}.\]
77
78 \begin{example}[Exemples]
79 \begin{enumerate}
80 \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$.
81
82 %\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 :
83 %\[\forall (x,y) \in \R^2, \; x<y \iff (y-x)\in \R^{*}_+.\]
84 %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).
85 %\label{ord-strict}
86 %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$.
87
88 \item Le relation $p$ définie entre $\R$ et $\R_+$ par
89 \[\forall (x,y)\in \R\times \R_+,\; p(x,y)\iff y=x^2.\]
90 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.
91 \end{enumerate}
92 \end{example}
93
94 % Dans le cas d'une
95 %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)$.
96 %
97
98 \section{Relations d'équivalence}
99 \subsection{Définition}
100 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 :
101 \begin{enumerate}
102 \item Elle est \emph{réflexive}, c'est-à-dire que tout élément de $E$ est en relation avec lui même :
103 \[\forall x \in E,\; x\mathrel{\symcal{R}}x.\]
104 \item Elle est \emph{symétrique}:
105 \[\forall (x,y)\in E\times E,\; (x\mathrel{\symcal{R}}y \implies y\mathrel{\symcal{R}}x).\]
106 \item Elle est \emph{transitive} :
107 %\[
108 %\forall (x,y,z)\in E^3,\quad \left.\begin{aligned}
109 %x&\mathrel{\symcal{R}}y\\
110 %&\text{et}\\
111 %y&\mathrel{\symcal{R}}z
112 %\end{aligned}\right\}
113 %\implies x\mathrel{\symcal{R}}z
114 %\]
115 \[
116 \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).
117 \]
118 \end{enumerate}
119
120 \begin{example}[Exemples]
121 \begin{enumerate}
122 \item L'égalité est une relation d'équivalence sur tout ensemble, c'est une conséquence directe de la définition.
123 \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}.
124 \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.
125 \item La relation $\equiv$ définie dans l'ensemble $\Z$ des entiers par
126 \[\forall (m,n)\in\Z\times\Z,\; m\equiv n \iff (m-n) \text{ est un entier pair.}\]
127 est une relation d'équivalence.
128
129 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 :
130 \begin{enumerate}
131 \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.
132 \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.
133 \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
134 \[m-p=(m-n)+(n-p)=2(k+k'), \text{ où $(k+k')\in\Z$}\]
135 pour établir que $m\equiv p$. La relation $\equiv$ est donc transitive.
136 \end{enumerate}
137 \end{enumerate}
138 \end{example}
139 %\subsection{Exemples}
140
141 \subsection{Classes d'équivalence}
142 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é.
143 \[y\in\cl_{\symcal{R}} (x)\iff x\mathrel{\symcal{R}}y.\]
144
145 \begin{thm}
146 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$.
147 \end{thm}
148
149 \begin{proof}
150 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)$.
151
152 Nous allons procéder par double inclusion.
153 \begin{itemize}
154 \item Soit donc $y\in E$ tel que $x\in\cl(y)$. On sait que $y\mathrel{\symcal{R}}x$, donc,
155 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)$ :
156 \[\forall z\in E, (z\in\cl(x)\implies z\in\cl(y), \text{ donc }\cl (x)\subset\cl (y).\]
157 \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 :
158 pour tout $z$ appartenant à $\cl(y)$ on a à la fois~$x\mathrel{\symcal{R}}y$ et~$y\mathrel{\symcal{R}}z$,
159 donc par transitivité $x\mathrel{\symcal{R}}z$, soit~\mbox{$z\in\cl(x)$} :
160 \[\forall z\in E, (z\in\cl(y))\implies z\in\cl(x), \text{ donc }\cl (y)\subset\cl (x).\]
161 \item Finalement $\cl(x)=\cl(y)$.\qedhere
162 \end{itemize}
163 \end{proof}
164
165 \begin{remark}
166 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.
167 \end{remark}
168 %\end{document}
169 %\subsubsection{Notion de structure quotient}
170
171 \section{Relations d'ordre}
172 \subsection{Définition}
173 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 :
174 \begin{enumerate}
175 \item Elle est \emph{réflexive}, c'est-à-dire que tout élément de $E$ est en relation avec lui même :
176 \[\forall x \in E,\; x\preccurlyeq x.\]
177 \item Elle est \emph{antisymétrique}:
178 \[\forall (x,y)\in E\times E,\; \bigl((x\preccurlyeq y)\text{ et }(y\preccurlyeq x)\implies x=y\bigr).\]
179 \item Elle est \emph{transitive} :
180 %\[
181 %\forall (x,y,z)\in E^3,\quad \left.\begin{aligned}
182 %x&\mathrel{\symcal{R}}y\\
183 %&\text{et}\\
184 %y&\mathrel{\symcal{R}}z
185 %\end{aligned}\right\}
186 %\implies x\mathrel{\symcal{R}}z
187 %\]
188 \[
189 \forall (x,y,z)\in E^3,\; \bigl((x\preccurlyeq y\;\text{ et }\;y\preccurlyeq z)\implies x\preccurlyeq z\bigr).
190 \]
191 \end{enumerate}
192
193 \begin{remark}
194 La démonstration du résultat suivant est immédiate.
195
196 Une relation d'ordre $\preccurlyeq$ sur un ensemble $E$ étant donnée, la relation~$\succcurlyeq$, définie par
197 \[\forall (x,y) \in E^2, x\succcurlyeq y \iff y\preccurlyeq x\,,\]
198 est une relation d'ordre sur $\R$ nommée \emph{ordre inverse} de $\preccurlyeq$.
199 \end{remark}
200
201 %\begin{exemple}[Exemples]
202 %\begin{enumerate}
203 %\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
204 %\[\forall (x,y) \in \R^2, \; x\leq y \iff (y-x)\in \R_+\,,\]
205 %est bien une relation d'ordre. En effet :
206 %\begin{itemize}
207 %\item Pour tout $x$ réel, $x-x=0$ et $0\in \R_+$, ce qui assure que la relation~$\leq$ est \emph{réflexive}.
208 %\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}.
209 %\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}.
210 %\end{itemize}
211 %\end{enumerate}
212 %\end{exemple}
213
214 \subsection{Ordre dans les ensembles de nombres}
215 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.
216 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$).
217
218 %
219 \subsection{Un peu de vocabulaire}
220 On se donne dans ce paragraphe un ensemble $\symcal{E}$ sur lequel est définie une relation d'ordre~$\preccurlyeq$.
221 \subsubsection{Ordre total}
222 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
223 \XSmartphoneCommand{$\bigl((x\preccurlyeq y)\text{ ou }(y\preccurlyeq x)\bigr)$}
224 \SmartphoneCommand{%
225 \[
226 \bigl((x\preccurlyeq y)\text{ ou }(y\preccurlyeq x)\bigr)
227 \]%
228 }
229 est vraie.
230
231 \subsubsection{Majorants, minorants \& C\up{ie}}
232 Soit maintenant $\symcal{A}$ une partie de $\symcal{E}$.
233
234 \begin{itemize}
235 \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$.
236 \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$.
237 \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}$.
238 \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}$.
239 \end{itemize}
240
241
242
243 \begin{remark}
244 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.
245 \end{remark}
246
247 \begin{thm}
248 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.
249 \end{thm}
250 \begin{proof}
251 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.
252 \end{proof}
253
254 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}$.
255
256 \begin{alert}
257 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$.
258 \end{alert}
259
260 \section{Applications, fonctions}\label{Rfonc}
261 %%%Fonction caractéristique, cardinal de $\symcal{P}(E)$ ou $\symfrak{P}(E)$
262 \subsection{Définition}
263 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.
264
265 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 :
266
267 \begin{align*}&f\::\;E\to F\;,\quad x\longmapsto f(x)\,.\\
268 \intertext{Par exemple :}
269 &f\::\;\left]-1,1\right[\to\R\;,\quad x \longmapsto \frac{1}{x^2-1}\;,\\
270 \intertext{ou}
271 &g\::\;\Z\to\{0,1\}\;,\quad p\longmapsto
272 \begin{cases} 0&\text{ si $p$ est pair,}\\
273 1&\text{ sinon.}
274 \end{cases}
275 \end{align*}
276
277 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.
278
279 \begin{example}[Exemples]
280 \begin{enumerate}
281 \item Soit la fonction $f$ de la variable réelle $x$, telle que
282 \[f(x)=\frac{x}{x^2-4}\;.
283 \]
284 Déterminons l'ensemble de définition $\symcal{D}_f$ de la fonction $f$. On a
285 \begin{align*}
286 x\in \symcal{D}_f &\iff x^2-4\neq 0\\
287 &\iff x\neq -2 \text{ et } x\neq 2.
288 \end{align*}
289
290 Donc $\symcal{D}_f= \R\smallsetminus\{-2,2\}$.
291 \item Soit la fonction $g$ telle que $g(x)=\sqrt{1-x^2}$. Déterminons l'ensemble de définition de $g$. On a
292 \[
293 x\in \symcal{D}_g \iff 1-x^2\geq 0.
294 \]
295
296 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é).
297
298 Donc $\symcal{D}_g= \left[-1,1\right]$.
299 \end{enumerate}
300 \end{example}
301
302 \subsection{Antécédents, surjections, injections \& bijections}
303 \subsubsection{Notion d'antécédent}
304 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$.
305 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é.
306
307 Considérons par exemple la fonction \emph{carré} définie par
308 \[f\::\;\R\to\R\;,\quad x\longmapsto f(x)=x^2 \]
309 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$}.
310 \begin{itemize}
311 \item \textit{Si $y>0$} : $y$ admet deux antécédents qui sont $\sqrt{y}$ et $-\sqrt{y}$.
312 \item \textit{Si $y=0$} : le seul antécédent de $0$ est $0$.
313 \item \textit{Si $y<0$} : $y$ ne possède aucun antécédent.
314 \end{itemize}
315 \begin{remark}
316 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
317 \[g\::\;\R_+\to\R_+\;,\quad x\longmapsto g(x)=x^2. \]
318 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}$.
319 \end{remark}
320 \subsubsection{Surjections, injections et bijections}
321 \begin{remark}[Surjections]
322 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$.
323 \end{remark}
324 \begin{remark}[Injections]
325 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
326 \begin{gather}\forall(x,y)\in E\times E, \;\bigl(x\neq y\implies f(x)\neq f(y)\bigr).\label{condinj1}\\
327 \intertext{Ou, par contraposition, $f\::\;E\to F$ est injective si}
328 \forall(x,y)\in E\times E, \;\bigl(f(x)= f(y)\implies x=y\bigr).\label{condinj2}
329 \end{gather}
330
331 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$.
332 \end{remark}
333
334 \begin{remark}[Bijections]
335 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.
336
337 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}$.
338 \end{remark}
339 \begin{example}[Exemples]
340 \begin{enumerate}
341 \item \label{phi} Soit l'application
342 \[
343 \phi\::\;\R\smallsetminus\{1\}\to\R\,,\quad x\longmapsto \frac{2x}{x-1}\;.
344 \]
345
346 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 :
347 \begin{align*}
348 \frac{2x}{x-1}=y &\iff 2x=y(x-1)\text{ et } x\neq 1\,,\\
349 &\iff x(2-y)=-y\text{ et } x\neq 1\,,\\
350 &\iff x(y-2)=y\text{ et } x\neq 1\,.
351 \end{align*}
352 \begin{itemize}
353 \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$.
354 \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$).
355 \end{itemize}
356
357
358 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.
359 \item Soit maintenant l'application
360 \[
361 \psi\::\;\R\smallsetminus\{1\}\to\R\smallsetminus\{2\}\,,\quad x\longmapsto \frac{2x}{x-1}\;.
362 \]
363
364 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
365 \[
366 \psi^{-1}\::\;\R\smallsetminus\{2\}\to\R\smallsetminus\{1\}\,,\quad x\longmapsto \frac{x}{x-2}\;.
367 \]
368 \item L'application $\theta$ définie par
369 \[
370 \theta\::\;\R\to\R\,,\quad x\longmapsto x^2-1
371 \]
372 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$.
373 \end{enumerate}
374 \end{example}
375 \subsection{Composée de deux applications}
376
377 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 :
378 \[g\rond f\::\; E\to G\,,\quad x\longmapsto g\rond f(x) = g\bigl(f(x)\bigr).\]
379
380 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$.
381
382 \begin{example}
383 Soit
384 \[
385 f\::\;\R^*\to\R\,,\; x\mapsto \frac1x\;\text{ et }\;g\::\:\R\to\R\,,\; x\mapsto x^2+1\,.
386 \]
387 Déterminons $g\rond f$ qui est une application de $\R^*$ dans $\R$.
388
389 On a pour tout $x\in\R^*$,
390 \begin{align*}
391 g\rond f(x) &= g\bigl(f(x)\bigr),\\
392 &={\bigl(f(x)\bigr)}^2+1,\\
393 &={\left(\frac1x\right)}^2+1,\\
394 \intertext{ou, en réduisant au même dénominateur,}
395 g\rond f(x)&= \frac{1+x^2}{x^2}\;.
396 \end{align*}
397 \begin{remark}
398 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$!).
399 \end{remark}
400 \end{example}
401
402 \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}$.
403 \end{thm}
404
405 \begin{proof}
406 Soit deux bijections $f\::\;E\to F$ et $g\::\;F\to G$. % et un élément $a$ de $E$.
407 %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$.
408 \begin{enumerate}
409 \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
410 \[g\rond f(a) =g\bigl(f(a)\bigr)=g(b)=c.\]
411 L'élément $c$ admet $a$ pour antécédent par $g\rond f$ qui est donc est donc application surjective.
412 \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
413 \[\forall(a,a')\in E\times E, \;\bigl(g\rond f(a)= g\rond f(a')\implies a=a'\bigr),\]
414 autrement dit que $g\rond f$ est injective.
415 \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
416 \[{\bigl(g\rond f\bigr)}^{-1}=f^{-1}\rond g^{-1}.\qedhere\]
417 \end{enumerate}
418 \end{proof}
419
420 \begin{remark}
421 La réciproque de ce théorème est fausse. Considérons par exemple les applications suivantes :
422 \[
423 f\::\;\R_+\to\R\,,\; x\mapsto \sqrt{x}\;\text{ et }\;g\::\;\R\to\R_+\,,\; x\mapsto x^2.
424 \]
425 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
426 \[g\rond f \::\;\R_+\to\R_+\,,\quad x\longmapsto x,\]
427 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).
428 \end{remark}
429
430 On a néanmoins le théorème suivant:
431 \begin{thm}
432 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.
433 \end{thm}
434
435 \begin{proof}
436 \begin{itemize}
437 \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.
438
439 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.
440 \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
441 \end{itemize}
442 \end{proof}
443 \endinput