-\section{Relations}
-On se donne deux ensembles $E$ et $F$.
-
-\begin{Def}[Relation binaire, graphe]
-On dit que:
- \begin{itemize}
-\item l'on a défini une \emph{relation binaire} \index{relation binaire} ${\mathcal{R}}$ entre ces deux ensembles lorsque l'on s'est donné une partie $G$ de l'ensemble produit $E\times F$ ($G\sse E\times F$).
-\item Cette partie est appelée \emph{graphe} \index{graphe} de la relation binaire.
-\item Si $x (\in E)$ et $y (\in F)$ sont tels que $(x,y)\in G$, on dit que $x$ est \emph{en relation avec} $y$ par la relation ${\mathcal{R}}$.
- \end{itemize}
-\end{Def}
-
-
-Pour formaliser cette proposition, on utilise la notation
-$x {\mathcal{R}} y$ comme suit:
-
-\begin{Notation}
-$$x {\mathcal{R}} y \Ssi \quad\hbox{[\og x est en relation avec y\fg{} ]}\Ssi
-(x,y)\in G\quad\hbox{[$G$: graphe de la relation ${\mathcal{R}}$]}.$$
-\end{Notation}
-
-\begin{Exo}
-On se place dans l'ensemble $E = \{1,2,3,\hdots,20\}$.
-
-Représenter, dans le plan rapporté à deux axes de coordonnées rectangulaires, les graphes des relations binaires sur $E$ dont les définitions suivent:
-\begin{itemize}
-\item $x \mathcal{R} y \Longleftrightarrow x \leqslant y$.
-\item $x \mathcal{R} y \Longleftrightarrow x | y$: $x$ divise $y$.
-\item $x \mathcal{R} y \Longleftrightarrow x \equiv y[3]$: $x$ est congru à $y$ modulo 3.
-\item $x \mathcal{R} y \Longleftrightarrow y = x^2$.
-\end{itemize}
-\end{Exo}
-
-
-
-
-\begin{Rem}
-Lorsque $E=F$, on parle de relation binaire définie dans l'ensemble $E$.
-Son graphe est une partie de $E^2$.
-\end{Rem}
-
-\begin{Rem}
-Il est possible que $x \mathcal{R} y$ sans que $y \mathcal{R} x$.
-\end{Rem}
-
-
-\begin{Exo}
-A-t-on $y \mathcal{R} x$ quand $x \mathcal{R} y$, dans les relations binaires définies dans l'exercice précédent ?
-\end{Exo}
-
-\begin{Exo}
-Sur l'ensemble des mots de la langue française, on définit la relation: \og le mot M est lié au mot N s'ils coïncident quand on écrit M à l'envers \fg{}.
-
-Déterminer quelques couples de mots en relation, ainsi que des mots en relation avec eux-mêmes. Comment appelle-t-on de tels mots ?
-\end{Exo}
-
-
-\begin{Exoc}
-Sur l'ensemble $\Z$ des entiers relatifs, on définit deux relations, notées respectivement $\Sigma$ et $\Delta$, de la façon suivante:
-\begin{itemize}
- \item $x \Sigma y$ quand la somme $x+y$ est paire
-\item $x \Delta y$ quand la différence $x-y$ est paire
-\end{itemize}
-Sont-elles égales ?
-
-\noindent\textit{\underline{Réponse: }} $x \Sigma y \Leftrightarrow \exists k \in \Z, x+y = 2k \Leftrightarrow \exists k \in \Z, x+y-2y = 2k-2y = 2(k-y).$
-
-Donc $x \Sigma y \Leftrightarrow \exists k' \in \Z, x-y = 2k' \Leftrightarrow x \Delta y.$
-\end{Exoc}
-
-\section{Application d'un ensemble dans un autre}
-
-\subsection{Application et relation fonctionnelle}
-
-
-\begin{Def}[Application]
-Une \emph{application}\index{application} de l'ensemble $E$ dans l'ensemble $F$ est une relation binaire particulière ${\mathcal{R}}$ entre $E$ et $F$, dont le graphe $G$ doit posséder les propriétés suivantes:
-
-\begin{itemize}
- \item pour tout élément $x$ de $E$, il doit exister un élément $y$ de $F$ tel que $(x,y)$ soit élément de $G$;
- \item cet élément $y$ doit être unique.
-\end{itemize}
-\end{Def}
-
-
-
-\noindent Voici la formalisation (partielle) de ces propositions:
-
-\begin{itemize}
-\item $\qqs x\in E,\ \exi y\in F,\ (x,y)\in G$
-\item $\qqs x\in E,\ \qqs y\in F,\ \qqs y'\in F, [(x,y)\in G\ {\rm et}\ (x,y')\in G \Longrightarrow y=y']$.
-\end{itemize}
-
-\medskip
-
-Il existe un intermédiaire entre relation et application \ldots
-
-\begin{Def}[Relation fonctionnelle]
-On parle de \emph{relation fonctionnelle}\index{relation!fonctionnelle} quand tout élément de l'ensemble de départ possède au plus une image.
-\end{Def}
-
-\begin{Rem}
-Une application est donc une relation fonctionnelle particulière : tout élément de l'ensemble de départ possède exactement une image.
-\end{Rem}
-
-
-\begin{Exo}
-Parmi les relations suivantes de $\mathbb{R}$ vers $\mathbb{R}$, repérez les relations fonctionnelles, repérez les applications:
-\begin{enumerate}
-\item $\mathcal{R} = \{ (x,y) \in \mathbb{R}^2, |y| = \sqrt{x} \}$
-\item $\mathcal{R} = \{ (x,y) \in \mathbb{R}^2, xy = 1 \}$
-\item $\mathcal{R} = \{ (x,y) \in \mathbb{R}^2, y-x+2 = 0 \}$
-\end{enumerate}
-\end{Exo}
-
-%\noindent\textit{\underline{Réponse:}} Les deux dernières sont des relations fonctionnelles, et la dernière est la seule application.
-
-\subsection{Image et antécédent d'un élément}
-
-
-On suppose dorénavant que $\mathcal{R}$ est une application. Pour un $x$ donné de $E$, il lui correspond un et un seul $y$ de $F$ qui est en relation avec lui par ${\mathcal{R}}$.
-
-\begin{Def}
-Cet unique $y$ est alors appelé \emph{image}\index{image} de $x$ par l'application définie par ${\mathcal{R}}$.
-\end{Def}
-
-\begin{Notation}
-Si l'on désigne par $f$ cette application, l'expression \og $y$ est l'image de $x$ par $f$\fg{} est formalisée par $y=f(x)$.
-De plus, on formalise la proposition \og $f$ est une application de $E$ dans $F$\fg{} par $f: E\vers F$. La proposition \og $y$ est l'image de $x$ par $f$\fg{} peut aussi être traduite par: $f: x \fc y$.
-\end{Notation}
-
-
-
-\begin{Exo}
- Interpréter chacune des situations suivantes au moyen d'une application. Pour cela, on définira deux ensembles $A$ et $B$ ainsi que $f: A\vers B$. Préciser dans chaque cas pourquoi il s'agit bien d'une application.
-
-\begin{enumerate}
-\item Le registre d'un hôtel qui possède 55 chambres.
-\item Le numéro d'INSEE.
-\item La parité d'un entier naturel.
-\end{enumerate}
-
-\end{Exo}
-
-
-Réciproquement, soit $f$ une application\ldots
-
-\begin{Def}[Antécédent]
-Si $y$ est l'image de $x$ par $f$, alors $x$ est appelé un \emph{antécédent} \index{antécédent} de $y$ par $f$.
-\end{Def}
-
-Un quelconque élément $y$ de $F$ ne possède pas forcément d'antécédant par une application $f : E \longrightarrow F$. Et il n'y a pas forcément unicité quand il en possède : un $y$ de $F$ peut avoir plusieurs antécédants par une application $f$.
-
-Les cas particuliers où tout $y$ de $F$ possède au plus un antécédant, et au moins un antécédant, sont étudiés dans les deux sections suivantes.
-
-\subsection{Applications injectives}
-
-
-
-\begin{Def}[Injectivité]
-L'application $f:E \longrightarrow F$ est dite \emph{injective} \index{application!injective} quand tout $y \in F$ possède au plus un antécédant par $f$.
-\end{Def}
-
-
-\begin{Rem}
-Le terme injection\index{injection} est synonyme d'\og application injective\fg{}.
-\end{Rem}
-
-L'injectivité d'une application peut se caractériser de la manière suivante.
-
-\begin{Th}[Caractérisation des fonctions injectives]
-$$\hbox{\og $f:E \longrightarrow F$ est une application injective\fg{} } \Longleftrightarrow [ \forall x,x' \in E, f(x)=f(x') \Imp x=x' ]$$
-\end{Th}
-
-\begin{Exo}
-Prouver, en utilisant la caractérisation ci-dessus, que les applications suivantes sont injectives :
-\begin{enumerate}
-\item $f : \R \longrightarrow \R, x \fc 2x+3$.
-\item $f : \mathbb{R}^+ \longrightarrow \R, x \fc 3 x^2 +1$.
-\end{enumerate}
-\end{Exo}
-
-
-\begin{Exo}
-Prouver, en utilisant la caractérisation ci-dessus, que les applications suivantes ne sont pas injectives :
-\begin{enumerate}
-\item $f : \R \longrightarrow \R, x \fc |x|$.
-\item $f : \R \longrightarrow \R, x \fc x^2$.
-\end{enumerate}
-\end{Exo}
-
-
-\begin{Exo}
-Tracez le graphe d'une application qui est injective, et d'une application qui ne l'est pas. Trouver une caractérisation de l'injectivité d'une application $f :E \longrightarrow F$, à partir du nombre d'intersections entre la courbe $\mathcal{C}_f$ et les droites verticales $y=b, b\in F$.
-\end{Exo}
-
-
-\begin{Exo}
-Soit $f:E \longrightarrow F$ une application injective. Peut-elle perdre ce caractère injectif si on réduit l'ensemble d'arrivée ? Et si l'on réduit l'ensemble de départ ?
-
-Que se passe-t-il si l'on change «réduit» en «augmente» dans les précédentes questions ?
-\end{Exo}
-
-
-\begin{Exo}
-On suppose $g o f$ injective. Montrer que $f$ est injective. Est-ce que $g$ est obligatoirement injective ?
-\end{Exo}
-
-
-\subsection{Applications surjectives}
-
-La définition d'une application $f$ exige seulement que chaque élément $x$ de $E$ admette une image (unique) $y$ dans $F$, mais pas que tout élément $y$ de $F$ admette un antécédent dans $E$.
-S'il en est néanmoins ainsi, l'application est dite \emph{surjective}:
-\begin{Def}
- Une application \emph{surjective}\index{application!surjective} $f: E\vers F$ est une application telle que tout $y$ de $F$ admette un antécédent dans $E$.
-\end{Def}
-
-\begin{Rem}
-\emph{Surjection} est synonyme d'\og application surjective\fg{}. \index{surjection}
-\end{Rem}
-
-
-\begin{Exo}
-Tracez le graphe d'une application qui est surjective, et d'une application qui ne l'est pas.
-\end{Exo}
-
-\begin{Exo}
-Donnez des exemples (sous forme analytique) de fonctions surjectives, et de fonction qui ne le sont pas.
-\end{Exo}
-
-\subsection{Image d'un ensemble par une application}
-
-D'une manière générale, on peut considérer l'ensemble des images des éléments de $E$ par une application $f$ de $E$ dans $F$ (ils en ont tous une, et une seule).
-
-\begin{Def}[Image d'un ensemble par une application]
-Cet ensemble, qui est évidemment une partie de $F$, est noté $f<E>$, et est appelé \emph{image de $E$ par $f$}: $$f<E>=\{f(x)\in F \mid x\in E\}$$
-\end{Def}
-
-
-\begin{Rem}
-Si tous les éléments de $F$ ont un antécédent dans $E$ ($f$ est surjective), cela signifie que tout élément de $F$ est élément de $f<E>$, donc que $F\sse f<E>$. Comme on a remarqué par ailleurs que $f<E>\sse F$, on a, dans ce cas, $f<E>=F$.
-\end{Rem}
-
-
-
-Cette dernière remarque permet la formalisation suivante:
-
-\begin{Th}[Caractérisation de la surjectivité]
-$$\hbox{\og $f$ est (une application) surjective\fg{} } \Ssi f<E>=F$$
-\end{Th}
-
-
-\begin{Ex}
-Soit l'application \og élévation au carré \fg{} $f: x \longmapsto x^2$ de $\R$ dans $\R$. Elle est:
-\begin{itemize}
-\item non surjective: $f < \R > = \R^+$,
-\item non injective: $f(-2) = f(2) = 4$.
-\end{itemize}
-\end{Ex}
-
-\begin{Exo}
-On suppose $g o f$ surjective. Montrer que $g$ est surjective. Est-ce que $f$ est obligatoirement surjective ?
-\end{Exo}
-
-\subsection{Applications bijectives}
-
-
-\begin{Def}[Applications bijectives]
-Une application qui est à la fois injective et surjective est dite \emph{bijective} \index{application!bijective}.
-\end{Def}
-
-
-\begin{Rem}
-Synonyme d'\og application bijective\fg{}: bijection\index{bijection}.
-\end{Rem}
-
-\begin{Exo}
-Dans chaque cas, dire si l'application $f:A \vers B$ est injective, surjective ou bijective.
-
-\begin{enumerate}
-\item $A = \R, B = \R, f(x) = x+7$
-\item $A = \R, B = \R, f(x) = x^2+2x-3$
-\item $A = \{ x \in \R | 4 \leqslant x \leqslant 9 \}, B = \{ x \in \R | 21 \leqslant x \leqslant 96 \}, f(x) = x^2+2x-3$
-\item $A = \R, B = \R, f(x) = 3x-2|x|$
-\item $A = \R, B = \R, f(x) = e^x+1$
-\item $A = \N, B = \N, f(x) = x(x+1)$
-\end{enumerate}
-\end{Exo}
-
-
-\begin{Th}
-Dans le cas d'une bijection, à chaque élément $x$ de $E$ correspond un et un seul élément $y$ de $F$ (définition d'une application) et, réciproquement, à chaque (surjectivité) élément $y$ de $F$ correspond un et un seul (injectivité) élément $x$ de $E$.
-\end{Th}
-
-
-Cette dernière proposition est précisément l'affirmation de l'existence d'une application $g$ de $F$ dans $E$, telle que $x = g(y) \Longleftrightarrow f(x) = y $.
-
-
-
-
-\begin{Def}[Application inverse]
-Cette application est appelée \emph{application inverse}\index{application!inverse} de l'application $f$.
-\end{Def}
-
-\begin{Notation}
- On la note $f^{-1}$
-\end{Notation}
-
-\begin{Exo}
-Reprendre l'exercice précédent, en trouvant l'application réciproque des applications bijectives.
-\end{Exo}
-
-
-% \begin{Rem}
-% On peut démontrer que la bijectivité est une condition nécessaire et suffisante pour qu'une application admette une inverse.
-% \end{Rem}
-
-\begin{Ex}
-Soit l'application \og multiplication par 2 \fg{} $f: x \longmapsto 2 x$ de $\R$ dans $\R$. Elle est surjective et injective.
-Elle admet donc une application inverse: $f^{-1}: x \longmapsto \dfrac{x}{2}$.
-\end{Ex}
-
-\begin{Exo}
-Soit $f: \Z \vers \Z$ définie par $f(n) = n + (-1)^n$.
-\begin{enumerate}
- \item Montrer que $n$ et $f(n)$ sont toujours de parité différente.
-\item Montrer que $f$ est bijective.
-\item Calculer $f(f(n))$. En déduire une expression de $f^{-1}$ et résoudre l'équation $347 = n+(-1)^n$.
-\end{enumerate}
-
-\end{Exo}
-
-
-\section{Cardinal et puissance d'un ensemble}
-
-Il s'agit ici de proposer une réflexion sur la notion intuitive de \og nombre d'éléments d'un ensemble\fg{}, nécessaire pour pouvoir aborder ultérieurement les notions de dénombrabilité et de calculabilité, fondamentaux en informatique.
-
-
-\subsection{Cas des ensembles finis}
-
-
-On commence par prendre deux ensembles $E=\{a,b,c,d\}$ et $F=\{1,2,3\}$ et à remarquer que:
-\begin{itemize}
- \item il est possible de définir une injection de $F$ dans $E$, mais pas une surjection,
- \item de définir une surjection de $E$ sur $F$, mais pas d'injection,
-\end{itemize}
-\ldots tout simplement parce qu'il n'y a \og pas assez\fg{} d'éléments dans $F$ (ou \og trop\fg{} dans $E$).
-
-
-Si l'on veut pouvoir définir une bijection entre deux ensembles, il semble nécessaire et suffisant qu'ils aient le même \og nombre d'éléments\fg{} (on se limite ici au domaine fini).
-Cette notion intuitive, résultat immédiat d'une simple opération de comptage, est reliée à la notion mathématique de mise en bijection avec une partie de $\Net$ de la forme $\{1\vir 2\vir\ldots\vir n\}$.
- Ainsi, pour $n\in\Net$ donné, les ensembles à $n$ éléments sont tous ceux qui peuvent être mis en bijection avec $\{1\vir 2\vir\ldots\vir n\}$ (et, par convention, $\varnothing$ a 0 élément).
-
-
-\begin{Def}[Cardinal d'un ensemble fini]
-L'élément maximum $n$ de la partie finie $P=\{1\vir 2\vir\ldots\vir n\}$ de $\Net$ est un représentant du \emph{cardinal} \index{ensemble!cardinal}\index{cardinal} de tout ensemble en bijection avec $P$.
-\end{Def}
-
-
-
-Pas de problème donc lorsque l'on s'en tient aux ensembles finis, dont la définition mathématique est:
-
-
-\begin{Def}[Ensemble fini]
-Un ensemble est dit fini\index{ensemble!fini} s'il ne peut pas être mis en bijection avec une partie stricte de lui-même.
-\end{Def}
-
-
-\subsection{Cas des ensembles infinis}
-
-
-
-Lorsque l'on se pose la question du \og nombre d'éléments\fg{} d'un ensemble infini, on peut être tenté, dans un premier temps, de répondre par \og une infinité\fg{}, ce qui n'est pas satisfaisant pour au moins deux raisons:
-
-\begin{itemize}
- \item jusqu'à présent, le \og nombre d'éléments\fg{} était un entier, et l'infini n'est pas un nombre entier,
- \item cela laisserait supposer que tous les ensemble infinis ont le même \og nombre d'éléments\fg{}
-\end{itemize}
-
-
-
-Une réflexion plus appronfondie apparaît comme nécessaire. On décide donc de se calquer sur le domaine fini\ldots
-
-
-\begin{Def}[Puissance d'un ensemble infini]
-Deux ensembles ont \emph{même puissance}\index{ensemble!puissance}\index{puissance!d'un ensemble} (\og même nombre d'éléments\fg{}) si l'on peut les mettre en bijection.
-\end{Def}
-
-
-
-\begin{Ex}
-Il existe des bijections entre $\N$ et l'ensemble des entiers pairs ($2\N$) ou impairs ($2\N+1$), qui conduisent à des formulations du style \og il y a autant d'entiers que d'entiers pairs \fg{}.
-\end{Ex}
-
-
-\begin{Rem}
-$(2\N) \cup (2\N+1) = \N$, bien que ces trois ensembles \og on le même nombre d'éléments \fg{}, les deux premiers étants disjoints \ldots \'A rapprocher de $\infty\plinf=\infty$.
-\end{Rem}
-
-
-\begin{Rem}
-Pour ce genre de raisons, on a tendance à abandonner ce vocabulaire (sur les nombres d'individus) pour dire simplement que ces ensembles ont même puissance.
-\end{Rem}
-
-
-
-\subsection{Puissance d'un ensemble infini}
-
-
-Si $E$ est un ensemble infini, le résultat fondamental est:
-
-\begin{Th}
-Il est impossible de définir une surjection de $E$ sur $\mathcal{P}(E)$.
-\end{Th}
-
-\begin{Pre}
- Admis
-\end{Pre}
-
-Ce résultat montre que, même si $E$ est un ensemble infini, il ne peut être mis en bijection avec ${\cal P}(E)$, qui a donc \og strictement plus d'éléments\fg{} que $E$.
-Conséquemment, $\N$ et ses parties infinies, $\Z$, et même $\Q$ ont tous la même puissance, dite \emph{puissance du dénombrable} \index{puissance!du dénombrable}. Mais\ldots
-
-
-\begin{Def}[Puissance du continu]
-${\cal P}(\N)$ n'est pas dénombrable, et est de puissance strictement supérieure, dite \emph{puissance du continu}\index{puissance!du continu}, dite
- \emph{puissance de $\R$}.
-\end{Def}
-
-
-\noindent De même, ${\cal P}(\R)$ est de puissance strictement supérieure à $\R$, et ainsi de suite\ldots
-
-\begin{Th}
-$\R$ est indénombrable.
-\end{Th}
-
-\begin{Pre}[Démonstration de Cantor]
-Supposons que $\mathbb{R}$ soit dénombrable.
-On pourrait alors écrire la liste de TOUS les réels,
-à partir du premier, en écriture décimale $r_1$, $r_2$, $r_3$, etc.
-
-On choisit pour les nombres décimaux l'écriture qui ne comporte que des zéros à partir d'un certain rang, s'il y a ambiguïté.
-Ainsi, l'on préférera l'écriture 1 à 0,9999999\ldots \ldots (ces nombres sont égaux ; c'est-à-dire que l'on a affaire ici à deux représentations décimales d'un même nombre).
-
-
- Construisons alors le nombre $S$ de la manière suivante:
- \begin{enumerate}
- \item sa partie entière est 0,
- \item et pour sa partie décimale,
- \begin{itemize}
- \item le premier chiffre est différent du premier chiffre après la virgule de $r_1$,
- \item le deuxième chiffre est différent du deuxième chiffre après la virgule de $r_2$,
- \item \emph{etc.}
- \end{itemize}
- \end{enumerate}
-
-Le nombre $S$ ne fait alors pas partie de la liste des réels, ce qui est contradictoire: l'hypothèse $\mathbb{R}$ dénombrable (on peut numéroter tous les réels avec $\mathbb{N}$) est erronée.
-\end{Pre}
-\section{Relations d'ordre}
-Dans ce paragraphe, on se place dans le cas où $E=F$.
-Soit ${\mathcal{R}}$ une relation binaire définie dans un ensemble $E$, de graphe $G$.
-
-\subsection{Réflexivité, antisymétrie, transitivité}
-
-
-\begin{Def}[Réflexivité]
- ${\mathcal{R}}$ est dite \emph{réflexive} \index{relation!réflexive} quand tout élément de $E$ est en relation avec lui-même:
-$$\qqs x\in E,\ (x,x)\in G$$
-\end{Def}
-
-
-\begin{Rem}
- C'est-à-dire $\qqs x\in E,\ x {\mathcal{R}} x$, ou encore: la diagonale de $E^2$ est incluse dans $G$.
-\end{Rem}
-
-
-
-\begin{Def}[Antisymétrie]
- ${\mathcal{R}}$ est dite \emph{antisymétrique} \index{relation!antisymétrique} si, lorsque $x$ est en relation avec $y$, alors $y$ ne peut pas être en relation avec $x$ (sauf si $x=y$):
-
-$$\qqs x\in E,\ \qqs y\in E,\ (x,y)\in G ~{\rm et}\ (y,x)\in G\ \Imp x=y$$
-\end{Def}
-
-
-\begin{Rem}
- C'est-à-dire $\qqs(x,y)\in E^2,\ x {\mathcal{R}} y\ {\rm et}\ y {\mathcal{R}} x\Imp\ x=y$.
-\end{Rem}
-
-
-
-\begin{Def}[Transitivité]
- ${\mathcal{R}}$ est dite \emph{transitive} \index{relation!transitive} lorsque, si $x$ est en relation avec $y$, et si $y$ l'est avec $z$, alors $x$ est en relation avec $z$:
-$$\qqs x\in E,\qqs y\in E,\ \qqs z\in E,\ (x,y)\in G\ {\rm et}\ (y,z)\in G
-\Imp (x,z)\in G$$
-\end{Def}
-
-
-\begin{Rem}
-C'est-à-dire: $\qqs x\in E,\ \qqs y\in E,\qqs z \in E,\ x {\mathcal{R}} y\ {\rm et}\ y {\mathcal{R}} z \Imp x {\mathcal{R}} z$.
-\end{Rem}
-
-
-\begin{Exo}
-Les relations suivantes sont-elles réflexives, antisymétriques ou transitives ?
-\begin{enumerate}
-\item $A = \mathbb{R}$ et $x \mathcal{R} y$ si $|x| = |y|$.
-\item $A = \mathbb{R}$ et $x \mathcal{R} y$ si $sin^2 x + \cos^2 y = 1 $.
-\item $A = \mathbb{N}$ et $x \mathcal{R} y$ s'il existe $p$ et $q$ entiers tels que $y = p x^q$.
-\item $A$ est l'ensemble des points du plan, et $x \mathcal{R} y$ si la distance de $x$ à $y$ est inférieure à 52,7 km.
-\end{enumerate}
-\end{Exo}
-
-
-\begin{Exo}
-Sur un ensemble à $n$ éléments, combien y a-t-il de relations\ldots
-\begin{enumerate}
-\item réflexives~?
-\item symétriques~?
-\end{enumerate}
-\end{Exo}
-
-
-
-\begin{Exo}
-Déterminer quand une relation $\mathcal{R}$ dans un ensemble $A$ est
-\begin{enumerate}
-\item non réflexive,
-\item non symétrique,
-\item non transitive,
-\item non antisymétrique.
-\end{enumerate}
-\end{Exo}
-
-
-\begin{Exo}
-Donner des exemples de relation $\mathcal{R}$ dans $\{1,2,3\}$ ayant les propriétés suivantes:
-\begin{enumerate}
-\item $\mathcal{R}$ est symétrique,
-\item $\mathcal{R}$ n'est ni symétrique ni antisymétrique,
-\item $\mathcal{R}$ est transitive mais $\mathcal{R} \cup \mathcal{R}^{-1}$ n'est pas transitive.
-\end{enumerate}
-\end{Exo}
-
-
-\begin{Exo}
-Soit $\mathcal{R}$ et $\mathcal{S}$ deux relations dans $A$.
-\begin{enumerate}
-\item Montrer que si $\mathcal{R}$ et $\mathcal{S}$ sont transitives alors $\mathcal{R} \cap \mathcal{S}$ est transitive.
-\item Si $\mathcal{R}$ est antisymétrique alors $\mathcal{R} \cap \mathcal{S}$ est antisymétrique.
-\end{enumerate}
-\end{Exo}
-
-
-\subsection{Relation d'ordre}
-
-\begin{Def}[Relation d'ordre]
-${\mathcal{R}}$ est une \emph{relation d'ordre}\index{relation!d'ordre} lorsqu'elle est réflexive, antisymétrique et transitive.
-\end{Def}
-
-
-\begin{Ex}[Exemples de relations d'ordre]
-Quelques relations d'ordre:
-\begin{itemize}
-\item $(\R,\leqslant)$
-\item $({\cal P}(E),\sse)$
-\end{itemize}
-\end{Ex}
-
-\begin{Ex}[Relation de divisibilité]
-On note $a|b$ si et seulement si $b$ est un multiple de $a$ ($\exists k \in \Net, b=ka$).
-
-C'est une relation d'ordre définie dans $\Net$. En effet, elle est
-
-\begin{description}
-\item[reflexive:] $a=1a$, donc $a|a$ est vrai,
-\item[antisymétrique:] si $a|b$ et $b|a$, alors $\exists k,k' \in \Net, a=kb$ et $b=k'a$. Donc $a = kk' a$. Comme $a \neq 0$, $kk'=1$. Mais $k,k' \in \Net$, donc $k = k' = 1$, et $a = b$.
-\item[transitive:] si $a|b$ et $b|c$, alors alors $\exists k,k' \in \Net, a=kb$ et $b=k'c$. Donc $a = k k' c$: il existe $k'' \in \Net$ ($k''=k k'$) tel que $a = k''c$: $a|c$.
-\end{description}
-
-\end{Ex}
-
-
-La structure algébrique constituée par l'ensemble $E$, muni de la
-relation d'ordre ${\mathcal{R}}$, (c'est-à-dire: le couple $(E,{\mathcal{R}})$) est
-celle d'\emph{ensemble ordonné}\index{ensemble!ordonné}.
-
-
-
-\subsection{Ordre partiel, ordre total}
-
-Une relation d'ordre définie dans un ensemble $E$ peut posséder une propriété supplémentaire, celle selon laquelle tous les éléments de $E$ sont comparables entre eux.
-On formalise comme suit:
-
-
-\begin{Def}[Relation d'ordre totale]
-Une relation d'ordre qui possède cette dernière propriété est dite relation d'\emph{ordre total}\index{relation!d'ordre!totale}, et la structure algébrique correspondante est celle d'\emph{ensemble totalement ordonné}\index{ensemble!totalement ordonné}.
-\end{Def}
-
