\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage[T1]{fontenc}
\usepackage{amsmath, amsthm,amssymb,xcolor}
\usepackage{mathrsfs}
\usepackage[a4paper,margin=2cm]{geometry}
\usepackage{fancyhdr}
\usepackage{ifthen}

%% L'environnement exo

\newcommand{\priosymb}{\clubsuit}
\newcommand{\exoprio}{}

\newcounter{Exo}
\newenvironment{exo}[1][]{%
  \refstepcounter{Exo}
  \medskip\goodbreak\noindent%
  {\textbf{\textsc{Exercice~\arabic{Exo}}}}
  \ifthenelse{\equal{#1}{}}{}{(#1)} \exoprio
  \nobreak\par
}{%
  \par\setlength{\leftskip}{0pt}
}

% Exo prioritaire
\newenvironment{exop}[1][]{%
  \renewcommand{\exoprio}{$\priosymb$}
  \begin{exo}[#1]}
{%
  \end{exo}
}

\newcounter{Question}[Exo]
\newcommand{\question}{%
  \refstepcounter{Question}%
  \par\smallskip\setlength{\leftskip}{0pt}
  \nobreak\arabic{Question}.\kern1.5ex}

\newcounter{SubQuestion}[Question]
\newcommand\sousquestion{%
  \refstepcounter{SubQuestion}%
  \par\setlength{\leftskip}{2em}
  \nobreak\hspace{-1em}(\alph{SubQuestion})\kern1.5ex}

%% Mise en page
\setcounter{secnumdepth}{1}
\parindent0pt

%% Le titre de la planche
\newcommand{\titreTD}{
  \thispagestyle{empty}
  \par
  Université d'Aix-Marseille \hfill \filiere\\
  {\semestre}\hfill{\annee}

  \bigskip
  \noindent
  \framebox[\textwidth]{
    \vbox{
      \begin{center}
        \textbf{\planche}\\
        {\titreplanche}
      \end{center}
    }
  }
}

% En-tête
\pagestyle{fancy}
\fancyhead[L]{}
\fancyhead[C]{\small\slshape%
  \textsc{\ue~--~\planche}~--~{\titreplanche}}
\fancyhead[R]{}

\newcommand{\annee}{\oldstylenums{2019}-\oldstylenums{2020}}
\newcommand{\filiere}{Portail Descartes}
\newcommand{\semestre}{Semestre~1}
\newcommand{\ue}{Langage mathématique}
\newcommand{\planche}{Planche~5}
\newcommand{\titreplanche}{Relations d'équivalence}

%%
% Définitions locales à cette planche

\newcommand{\C}{\mathbb{C}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}

\newcommand{\et}{\text{ et }}
\newcommand{\ou}{\text{ ou }}
\newcommand{\si}{\text{si }}
\newcommand{\non}{\text{non}}
\newcommand{\ssi}{\text{ ssi }}
\newcommand{\alors}{\text{ alors }}

\newcommand{\Rel}[1][R]{\mathrel{\mathscr{#1}}}
\newcommand{\Parties}{\mathscr{P}}
\renewcommand{\Im}{\mathrm{Im}}

\begin{document}

\titreTD

Soit $E$ un ensemble; une relation $\sim$ sur $E$ est dite \emph{relation
  d'équivalence} si elle est:
\begin{description}
\item[réflexive:] $\forall x\in E,\,x\sim x$
\item [symétrique:] $\forall x\in E,\forall y\in E,\,\si x\sim y \alors y\sim
  x$
\item[transitive:] $\forall x\in E,\forall y\in E,\forall z\in E,\,\si x\sim
  y \et y\sim z \alors x\sim z$.
\end{description}

\section{Exemples simples de relations d'équivalence}

Précisez si les relations suivantes sont des relations d'équivalence. Si les
relations ne le sont pas, précisez laquelle (ou lesquelles) des trois
propriétés de définition n'est pas remplie.

\begin{exo}[Relations sur $E=\R$ ] \label{sim}
\question $x\sim y\ssi |x-y|<1$. \label{ques}
\question \label{smi} $x\sim y\ssi x-y\in \Q$.
\question \label{ism} $x\sim y\ssi x+y\in\Q$.
\end{exo}

\begin{exo}[Relations sur $E=\Z$.]\label{uau}
\question $x\sim y\ssi \frac{x-y}2\in\Z\ou\frac{x-y}3\in\Z$.\label{pop}
\question  $x\sim y\ssi x+y=2$.\label{pip}
\question  $x\sim y\ssi \exists p\in\Z,\exists q\in\Z\,\,x^p=y^q$.\label{kio}
\end{exo}

\begin{exo}[Relations sur l'ensemble $E$ des droites du plan ]\label{droit}
\question $d_1\sim\, d_2\ssi d_1\,||\,d_2$.\label{sqs}
\question  $d_1\sim\, d_2\ssi d_1\,\perp\, d_2$.\label{trt}
\end{exo}

\begin{exo}[Relations sur l'ensemble $E$ des applications $f:\R\to\R$]%
  \label{func}
\question $f\sim g\ssi $ l'ensemble $E_{f,g}:=\{x\in\R:\,f(x)\neq g(x)\}$ est
fini.\label{byu}
\question  $f\sim g\ssi $ l'ensemble $E_{f,g}$ est vide ou a un seul
élément.\label{byu1}
\end{exo}

\section{Construction de relations d'équivalence à partir des applications ou
  d'autres relations}

Il est parfois possible de construire une relation d'équivalence utile à partir
d'une application ou à partir d'une autre relation (d'équivalence ou non). Les
exercices de cette section proposent plusieurs situations de ce type.

\begin{exo}\label{cap}
Soit $E$ et $F$ deux ensembles, et $f:E\to F$ une application. On définit le
relation $\sim_f$ sur $E$ comme suit :
$$x\sim_f y \ssi f(x)=f(y).$$

Prouvez que $\sim$ est une relation d'équivalence.
\end{exo}

\begin{exo}\label{com} Soit $E=\{a,\,b,\,c,\,d\}$ et la relation $\sim$ sur $E$
dont l'ensemble suivant donne la liste de tous les couples $(x,y)$ tels que
$x\sim y$:
$$G_\sim = \{(a,a),\,(a,b),\,(a,c),\,(b,b),\,(b,a),\,
             (c,c),\,(c,a),\,(c,b),\,(d,d)\}.$$
\question Laquelle (ou lesquelles) des trois propriétés définissant une
relation d'équivalence n'est pas respectée par $\sim$?\label{unu}
\question Rajouter à l'ensemble $G_\sim$ un couple $(x,y)\in E\times E$ de sorte
que la nouvelle relation ainsi formée soit une relation
d'équivalence.\label{nu}
\end{exo}

\begin{exo}\label{homo}
Soit $E$ un ensemble, et $\sim_1$, $\sim_2$, deux relations d'équivalence sur
$E$. On définit la réunion des relations $\sim_1$ et $\sim_2$ comme étant
la relation $\Rel[U]$ sur $E$:
$$x\,\Rel[U] y \ssi (x \sim_1 y \ou x\sim_2 y),$$
et l'intersection des relations $\sim_1$ et $\sim_2$ comme la relation
$\Rel[S]$ sur $E$:
$$x\Rel[S] y \ssi (x \sim_1 y \et x\sim_2 y).$$
\question Est-ce que $\Rel[U]$ est une relation d'équivalence? \label{hom}
\question Même question pour $\Rel[S]$.\label{hm}
\end{exo}

\section{Classe d'équivalence d'un élément}

Soit $E$ un ensemble et $\sim$ une relation d'équivalence sur $E$. Pour tout
élément $x\in E$, le sous-ensemble
$$[x] = \{y\in E:\, x \sim y\}$$
de $E$ s'appelle la \emph{classe d'équivalence} de $x$ dans $E$. On a les
propriétés:
\begin{itemize}
\item $\forall x\in E, x\in [x],$
\item $\forall x\in E,\forall y\in E,\, x\sim y \ssi [x]=[y],$
\item $\forall x\in E,\forall y\in E,\, \non(x \sim y) \ssi
  [x] \cap [y] = \emptyset.$
\end{itemize}

\medskip
Les exercices suivants (\ref{bu2}-\ref{bely}) sont des cas particuliers de la
construction d'une relation d'équivalence décrite à l'exercice~\ref{cap}.

\begin{exo}\label{bu2}
Soit la relation $\sim$ sur $\R^2$ définie par:
$$(x,y)\sim (x',y')\ssi x=x'.$$

\question Trouvez une application $f:\R^2\to\R$ telle que la relation $\sim$
soit de la forme $\sim_f$.\label{bya}
\question  Déterminer $\left[(x_0,y_0)\right]$, la classe d'équivalence d'un
élément $(x_0,\,y_0)$ de $\R^2$.\label{bya1}
\end{exo}

\begin{exo}\label{buu}
Soit la relation $\sim$ sur $\C$ (l'ensemble des nombres complexes) définie par:
$$z\sim z'\ssi |z|=|z'|.$$
\question Trouvez une application $f:\C\to\R$ telle que la relation $\sim$ soit
de la forme $\sim_f$.\label{bhy}
\question Déterminer $\left[z_0\right]$, la classe d'équivalence d'un élément
$z_0$ de $\C$.\label{fty}
\end{exo}

\begin{exo}\label{bo}
Soit la relation $\sim$ sur $\R$ définie par :
$$x\sim y \ssi x^2-y^2=x-y.$$
\question Trouvez une application $f:\R\to\R$ telle que la relation $\sim$ soit
de la forme $\sim_f$.\label{isy}
\question  Déterminer $[1]$, la classe d'équivalence du nombre réel
$1$.\label{ccc}
\question  Trouvez tous les $a\in\R$ dont la classe d'équivalence $[a]$ est un
ensemble qui ne contient qu'un seul élément.\label{qsq}
\end{exo}

\begin{exo}\label{bu1}
Soit la relation $\sim$ sur $\R$ définie par:
$$x\sim y\ssi x e^y=y e^x.$$

\question Trouvez une application $f:\R\to\R$ telle que la relation $\sim$ soit
de la forme $\sim_f$.\label{rcr}
\question  Déterminer $\left[1\right]$, la classe d'équivalence de $1$, et
$[-1]$, la classe d'équivalence de $-1$.\label{gre}
\question Trouvez tous les $x\in\R$ dont la classe d'équivalence est un
ensemble qui ne contient qu'un seul élément.\label{got}
\end{exo}

\begin{exo}\label{bely}
Soit $E$ l'ensemble des applications $f:\R\to\R$, et la relation $\sim$ sur $E$
définie par:
$$f\sim g\ssi \exists a,b>0,\, a f(x)\leq g(x)\leq b f(x)\,\, \forall
x\in\R.$$
\question Prouvez que $\sim$ est une relation d'équivalence.\label{lab}
\question  Trouver toutes les constantes $s$ telles que $s+\arctan\in [1]$, la
classe d'équivalence de l'application\label{bit}
$$1:\R\to\R\qquad 1(x)=1\quad\forall x\in\R.$$
\end{exo}

\section{Ensemble quotient et application induite}

Soit $E$ un ensemble et $\sim$ une relation d'équivalence sur $E$. L'ensemble
$$E/{\sim}=\{[x]:\,x\in E\}$$
s'appelle l'\emph{ensemble quotient} de $E$ par $\sim$.

Soit $F$ un ensemble. Une application $f:E\to F$ est dite \emph{compatible}
avec $\sim$ si
$$\forall x\in E, \forall y\in E\;\;\;\,x\sim y\Rightarrow f(x)=f(y).$$

Si $f:E\to F$ est compatible avec $\sim$, on définit $\bar{f}$,
l'\emph{application induite} par $f$ sur $E/{\sim}$ comme étant l'application:
$$\bar f:E/{\sim}\to F,\;\quad \bar f([x]) = f(x),\,\forall x\in E.$$

\begin{exo}\label{rbu} Soit $f:E\to F$ une application, et $\sim_f$ la relation
d'équivalence définie à l'exercice~\ref{cap}.
\question\label{nicy} L'application $f$ est compatible avec $\sim_f$.
\question\label{nice} Le quotient de $f$ par $\sim_f$ met l'ensemble
$E/{\sim}_f$ en bijection avec $\Im(f)=\{f(x):\;x\in E\}$.
\end{exo}

\begin{exo}\label{cucu}
Soit la relation d'équivalence $\sim$ sur $\R$ définie par:
$$x\sim y\ssi \sin(x)=\sin(y).$$
\question Prouvez que l'ensemble quotient $\R/{\sim}$ est en bijection avec
l'ensemble $[-1,\,1]$.\label{coco}
\question Parmi les applications suivantes, laquelle (ou lesquelles) est (ou
sont) compatibles avec $\sim$:
$$\cos:\R\to\R,\quad\sin^2:\R\to\R,\quad\exp:\R\to\R\;?$$ \label{coca}
\end{exo}

\begin{exo}\label{y1y}
Soit la relation d'équivalence $\sim$ sur $\R$ définie par:
$$x\sim y\ssi x-y\in\Z.$$
\question\label{zéz} Prouvez que l'ensemble quotient $\R/{\sim}$ est en
bijection avec l'ensemble $\mathbb{U}$ de tous les nombres complexes de module
$1$.
\question\label{z&z} Est-ce que l'application $f:\R\to\R$, $f(x)=\sin(x)$ est
compatible avec $\sim$~? Et l'application $g:\R\to\R$, $g(x)=\sin(2\pi x)$?
\end{exo}

\begin{exo}\label{lm}
Soit $E$ l'ensemble des droites du plan. On définit la relation d'équivalence
$\sim$ sur $E$ par:
$$d_1\sim d_2\ssi d_1 \| \,d_2.$$

\question\label{tyrg} Prouvez que l'ensemble quotient $E/{\sim}$ est en
bijection avec l'ensemble des droites passant par l'origine.
\question\label{tyy} Prouvez aussi que l'ensemble $E/{\sim}$ est en bijection
avec l'ensemble $\R\cup\{\infty\}$.
\end{exo}

\section{Partition d'un ensemble}

Soit $E$ un ensemble non-vide. Une partition de $E$ est
un sous-ensemble $P$ de $\Parties(E)$, avec les propriétés suivantes:

\begin{enumerate}\renewcommand{\theenumi}{\roman{enumi}}%
\item $\emptyset\notin P$
\item $\forall A,B\in P,\, A=B \ou A\cap B=\emptyset$
\item $\bigcup_{A\in P}\,A=E.$
\end{enumerate}

En d'autres mots, une partition de $E$ est un ensemble de sous-ensembles de $E$
de telle sorte qu'aucun de ces sous-ensembles ne soit vide, qu'ils soient deux
à deux disjointes, et que leur réunion soit égale à $E$.

La propriété suivante fait le lien entre partitions d'un ensemble et relations
d'équivalence.

\begin{exo}\label{duop} Soit $P$ une partition de $E$.

Alors la relation $x\sim y$ ssi $(\exists A\in P,\;\;x,y\in A)$ est une
relation d'équivalence, dont $P$ est l'ensemble quotient.
\end{exo}

\begin{exo}\label{rrsim} Soit $E=\{1,2,3\}$. Combien de partitions de $E$
existe-t-il?
\end{exo}

\begin{exo}\label{rsim} Soit $a,b,c$ trois nombre réels. À quelles conditions
sur $a,b,c$, les trois ensembles $]-\infty,b]$, $]0,a[$ et $[c,+\infty[$
forment ils une partition de $\R$?.
\end{exo}

\begin{exo}\label{rsimm} Soit $E$ un ensemble non-vide. Peut-on trouver
$A,B\subset E$ tels que $A$, $A\cap B$ et $B$ soit une partition de $E$?
\end{exo}

\section{Un cas particulier: $\Z/n\Z$}

Dans les exercices qui suivent, $n$ est un nombre naturel plus grand ou égal à
2, fixé une fois pour toutes.

\begin{exo}\label{bah} Soit la relation $\sim$ sur $\Z$ définie comme :
$$x\sim y\,\ssi \frac{x-y}n\in\Z.$$

\question\label{wua} Prouvez que $x\sim y$ si et seulement si $x$ et $y$ ont le
même reste à la division euclidienne par $n$ (on dit aussi que $x$ et $y$ sont
égaux modulo $n$).
\question\label{wau} Démontrez  que $\sim$ est une relation d'équivalence, et
que l'addition et la multiplication sur $\Z$ sont compatibles avec $\sim$.
\end{exo}

\begin{exo}\label{ploi}
Notons $\Z/n\Z$ l'ensemble quotient de $\Z$ par $\sim$.

Combien d'éléments possède l'ensemble $\Z/n\Z$?
\end{exo}

\begin{exo}\label{onsa} Dans cet exercice (et dans cet exercice seulement) on
pose $n=12$.
\question\label{ons1} Donner la liste de tous les couples
$(\lambda,\eta)\in \{0,\,1,\,2,\,3,\,\dots,\,11\}^2$ tels que
$$[\lambda]\times[\eta]=[0].$$
\question\label{ons2} Résoudre l'équation
$$[x]^2- [5]\times[x]+ [6]=[0]$$
dans $x\in\{0,\,1,\,2,\,3,\,\dots,\,11\}$.
\end{exo}

\section{Exercices complémentaires}

\begin{exo}[Relations sur l'ensemble $E=\Parties(S)$ des parties d'un ensemble
  non-vide $S$]\label{part}
\question On fixe $K\subset S$, $K\neq\emptyset$. $A\sim B\ssi A\cap K=B\cap
K$.\label{red}
\question $A\sim B\ssi \exists K\subset S,K\neq\emptyset\,\,A\cap K=B\cap
K$.\label{tyr}
\end{exo}

\begin{exo}\label{drt} Soit $E$, $F$ et $G$ trois ensembles, $\sim$ une relation
d'équivalence sur $E$, $f:F\to E$ une application de $F$ dans $E$, et
$g:E\to G$ une application de $E$ dans $G$.

On définit la relation $\Rel[S]$ de $F$ dans $F$:
$$x\Rel[S] y \ssi f(x) \sim f(y),$$
et la relation $\Rel[U]$ de $G$ dans $G$ :
$$x\Rel[U] y \ssi (\exists u, v\in E\;\;\,u\sim v,\,\,\, x=g(u),\,\, y=g(v)).$$

\question Est-ce que $\Rel[S]$ est une relation d'équivalence?\label{rey}
\question Même question pour $\Rel[U]$.\label{rey1}
\end{exo}

\begin{exo}\label{bu}
Soit la relation $\sim$ sur $\R$ définie par:
$$x\sim y\ssi \sin^2(x)+\cos^2(y)=1.$$
\question  Trouvez une application $f:\R\to\R$ telle que la relation $\sim$
soit de la forme $\sim_f$.\label{sol}
\question Déterminer $[0]$, la classe d'équivalence du nombre réel
$0$. \label{sol1}
\end{exo}

\begin{exo}\label{mos}
Soit $E=\Parties(\R)$, l'ensemble des parties de $\R$. On définit une relation
$\sim$ sur $\Parties(\R)$ par:
$$A\sim B\ssi A\cup [0,\,1]=B\cup [0,\,1].$$
\question Trouvez une application $f:E\to E$ telle que la relation $\sim$ soit
de la forme $\sim_f$.\label{solll}
\question Déterminer $\left[\{0\}\right]$, la classe d'équivalence de l'élément
$\{0\}$ de $\Parties(\R)$.\label{hry}
\end{exo}

\begin{exo}\label{mal}
Soit les relations d'équivalence des exercices \ref{bu2}-\ref{bely}.

\question Déterminer un ensemble qui peut être identifié avec le quotient de la
relation.\label{usel}
\end{exo}

\bigskip

Les deux exercices suivants donnent les constructions de $\Z$ à partir de $\N$
(exercice (\ref{baba})) et de $\Q$ à partir de $\Z$ (exercice (\ref{babu})).

\begin{exo}\label{baba}
Soit $E=\N\times \N$, on définit sur $E$ deux opérations~: une addition
$$(a,\,b)\oplus(c,\,d) = (a+c,\,b+d)\quad\forall (a,\,b),\,(c,\,d)\in E,$$
et une multiplication
$$(a,\,b)\otimes(c,\,d) = \left(ac+bd,\,ad+bc\right)\quad\forall
(a,\,b),\,(c,\,d)\in E.$$

On considère la relation $\sim$ de $E$ dans $E$ par:
$$(a,\,b)\sim (c,\,d)\ssi a+d = b+c.$$

\question\label{simo} Prouvez que $\sim$ est une relation d'équivalence, et que
l'ensemble quotient $E/{\sim}$ est en bijection avec l'ensemble $\Z$ des
nombres entiers.
\question\label{simi} Prouvez que les opérations $\oplus$ et $\otimes$ sont
compatibles avec $\sim$, et que leur quotients sont les opérations d'addition et
multiplication (classiques) sur $\Z$.
\end{exo}

\begin{exo}\label{babu}
Soit $E=\Z\times \Z^*$, on définit sur $E$ deux opérations: une addition
$$(a,\,b)\oplus(c,\,d)=(ad+bc,\,bd)\quad\forall
(a,\,b),\,(c,\,d)\in E,$$ et une multiplication
$$(a,\,b)\otimes(c,\,d)=(ac,\,bd)\quad\forall
(a,\,b),\,(c,\,d)\in E.$$

On considère la relation d'équivalence $\sim$ de $E$ dans $E$ par :
$$(a,\,b)\sim (c,\,d)\ssi ad - bc = 0.$$

\question\label{simu}Prouvez que la relation $\sim$ est une relation
d'équivalence, et que l'ensemble quotient $E/{\sim}$ est en bijection avec
l'ensemble $\Q$ des nombres rationnels.
\question\label{simou} Prouvez  que les opérations $\oplus$ et $\otimes$ sont
compatibles avec $\sim$, et que leurs quotients sont les opérations d'addition
et de multiplication (classiques) sur $\Q$.
\end{exo}

\begin{exo}\label{en} Soit $n$ un nombre naturel.
\question\label{cqqa} Combien de solutions
$x\in\{0,\,1,\,2,\,3,\,\dots,\,n-1\}$ a l'équation
$$[2]\times[x]=[0]\,\,?$$
\question\label{vvv} Même question pour l'équation
$$[2]\times[x]=[1].$$
(les réponses dépendent de la parité de $n$).
\end{exo}

\begin{exo}\label{eze} (Théorème de Bézout).  Soit l'équation
$$[a]\times[x]=[1],$$
avec $a\in\{0,\,1,\,2,\,3,\,\dots,\,n-1\}$.

Prouvez que cette équation admet une solution
$x\in\{0,\,1,\,2,\,3,\,\dots,\,n-1\}$ si et seulement si $a$ et $n$ sont
premiers entre eux.
\end{exo}

\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:

