pgcd, euclide,...

[cours-maths-dis.git] / ensembles / relbin13.tex

diff --git a/ensembles/relbin13.tex b/ensembles/relbin13.tex
index ed68ff352a00052ac392fdd9593298253da404dd..0ae73ee8bb4b3e8fb96507589368e79444ec952d 100755 (executable)
--- a/ensembles/relbin13.tex
+++ b/ensembles/relbin13.tex
@@ -28,19 +28,19 @@ que $x$ est \emph{en Relation avec} $y$. On note cela $x{\mathcal{R}}y$.
 Lorsque $E=F$, on parle de relation binaire définie dans l'ensemble $E$.
 Son graphe est une partie de $E^2$.
 Dans ce cas, il est possible que $x \mathcal{R} y$ sans que $y \mathcal{R} x$.
 Lorsque $E=F$, on parle de relation binaire définie dans l'ensemble $E$.
 Son graphe est une partie de $E^2$.
 Dans ce cas, il est possible que $x \mathcal{R} y$ sans que $y \mathcal{R} x$.

-(Penser à la relation \og est plus agé que \fg{}).
+(Penser à la relation \og est plus âgé que \fg{}).

 \end{Rem}
 
 
 
 \end{Rem}
 
 
 

-\begin{Exo}
-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 ?
-\end{Exo}
+% \begin{Exo}
+% Sur l'ensemble $\Z$ des entiers relatifs, on définit deux relations $\Sigma$ et $\Delta$:
+% \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 ?
+% \end{Exo}

 
 
 \section{Relations d'ordre}
 
 
 \section{Relations d'ordre}


@@ -60,7 +60,7 @@ dans un ensemble $E$.
 
 \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$): 
 
 \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,y)\in E^2,\ x {\mathcal{R}} y\ {\rm et}\ y {\mathcal{R}} x\Imp\ x=y$ 
+ $\qqs(x,y)\in E^2,\ x {\mathcal{R}} y\ {\rm et}\ y {\mathcal{R}} x\Imp\ x=y$.

 % ou encore
 % $\qqs x\in E,\ \qqs y\in E,\ (x,y)\in G ~{\rm et}\ (y,x)\in G\ \Imp x=y$
 % %
 % ou encore
 % $\qqs x\in E,\ \qqs y\in E,\ (x,y)\in G ~{\rm et}\ (y,x)\in G\ \Imp x=y$
 % %


@@ -82,9 +82,9 @@ $\qqs x\in E,\ \qqs y\in E,\qqs z \in E,\ x {\mathcal{R}} y\ {\rm et}\ y {\mathc
 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|$.
 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{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 = \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.
+% \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}
 
 \end{enumerate}
 \end{Exo}
 


@@ -101,13 +101,13 @@ $a \mathcal{R} b$ si et seulement si $a^b \leq b ^a$.
 
 
 
 
 
 

-\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}
+% \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}
 
 
 \subsection{Relation d'ordre}


@@ -126,7 +126,7 @@ On note $a|b$ si et seulement si $b$ est un multiple de $a$ ($\exists k \in \Net
 C'est une relation d'ordre définie dans $\Net$. En effet, elle est
 
 \begin{description}
 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[réflexive:] $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}
 \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}


@@ -134,10 +134,10 @@ C'est une relation d'ordre définie dans $\Net$. En effet, elle est
 \end{Ex}
 
 
 \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é}.
+% 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é}.

 
 
 
 
 
 


@@ -158,14 +158,15 @@ On considère\ldots
 \begin{enumerate}
 \item $E=\{1\vir 2\vir 3\vir 4\vir 5\vir 6\vir 7\vir 8\vir 9\}$ et on
 définit la relation binaire $\mathcal{R}$ dans $E$ par son graphe
 \begin{enumerate}
 \item $E=\{1\vir 2\vir 3\vir 4\vir 5\vir 6\vir 7\vir 8\vir 9\}$ et on
 définit la relation binaire $\mathcal{R}$ dans $E$ par son graphe

-$G=\{ $ (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (2,2), (2,3), (2,4), (2,6), (2,8), (2,9), (3,3), (4,3), (4,4), (4,6), (4,8), (4,9), (5,3), (5,4), (5,5), (5,6), (5,7), (5,8), 
-(5,9), (6,6), (6,8), (6,9), (7,7), (7,8), (7,9), (8,8), (9,9) $\}$
+$G=\{$(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (2,2), (2,3), (2,4), (2,6), (2,8), (2,9), (3,3), (4,3), (4,4), (4,6), (4,8), (4,9), (5,3), (5,4), (5,5), (5,6), (5,7), (5,8), 
+(5,9), (6,6), (6,8), (6,9), (7,7), (7,8), (7,9), (8,8), (9,9)$\}$

 (c'est-à-dire: $1{\mathcal{R}}1$, etc\ldots). 
 Justifier que cette relation est une relation d'ordre.
 
 \item Mêmes questions pour $E'=\{1\vir 2\vir 3\vir 4\vir 5\vir 6\}$ et
 (c'est-à-dire: $1{\mathcal{R}}1$, etc\ldots). 
 Justifier que cette relation est une relation d'ordre.
 
 \item Mêmes questions pour $E'=\{1\vir 2\vir 3\vir 4\vir 5\vir 6\}$ et

-$G'=\{$ (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), 
-(2,2), (2,4), (2,5), (2,6), (3,3), (3,4), (3,6), (4,4), (4,6), (5,5), (5,6), (6,6)$\}$.
+$G'=\{$(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), 
+(2,2), (2,4), (2,5), (2,6), (3,3), (3,4), (3,6), (4,4), (4,6), (5,5), (5,6), 
+(6,6)$\}$.

 \end{enumerate}
 \end{Exo}
 
 \end{enumerate}
 \end{Exo}
 


@@ -182,9 +183,8 @@ On se place encore dans ce paragraphe dans le cas où $E=F$.
 Soit ${\mathcal{R}}$ une relation binaire définie dans un ensemble (non vide) $E$, de graphe $G$.
 
 \begin{Def}[Relation symétrique]
 Soit ${\mathcal{R}}$ une relation binaire définie dans un ensemble (non vide) $E$, de graphe $G$.
 
 \begin{Def}[Relation symétrique]

-${\mathcal{R}}$ est dite \emph{symétrique} \index{relation!symétrique} si, dès que $x$ est en relation avec $y$, alors $y$ est en relation avec $x$
-$$\qqs x\in E,\ \qqs y\in E, (x,y)\in G \Imp (y,x)\in G$$
- Ou encore: $\qqs x\in E, \qqs y\in E,\ x {\mathcal{R}} y \Imp y {\mathcal{R}} x$.
+${\mathcal{R}}$ est dite \emph{symétrique} \index{relation!symétrique} si, dès que $x$ est en relation avec $y$, alors $y$ est en relation avec $x$:
+$\qqs x\in E, \qqs y\in E,\ x {\mathcal{R}} y \Imp y {\mathcal{R}} x$.

 \end{Def}
 
 
 \end{Def}
 
 


@@ -214,7 +214,7 @@ alors $y-x=(-k)\cdot n$; or, si $k\in\Z$, $(-k)\in\Z$, donc $y\equiv x\
 [n]$.
 \item[transitive:] si $x\equiv y\ [n]$ et $y\equiv z\ [n]$, $\exi
 k\in\Z$, $x-y=k\cdot n$ et $\exi l\in\Z$, $y-z=l\cdot n$. En
 [n]$.
 \item[transitive:] si $x\equiv y\ [n]$ et $y\equiv z\ [n]$, $\exi
 k\in\Z$, $x-y=k\cdot n$ et $\exi l\in\Z$, $y-z=l\cdot n$. En

-aditionnant membre à membre ces deux égalités, on obtient
+additionnant membre à membre ces deux égalités, on obtient

 $x-z=(k+l)\cdot n$, or $(k,l)\in\Z^2$, donc $k+l \in\Z$, donc
 $x\equiv z\ [n]$.
 \end{description}
 $x-z=(k+l)\cdot n$, or $(k,l)\in\Z^2$, donc $k+l \in\Z$, donc
 $x\equiv z\ [n]$.
 \end{description}


@@ -293,12 +293,9 @@ $x\mathcal{R}y$ ssi   $x.e^{y}= y.e^{x}$.
 
 \begin{Th}
 L'intersection de deux classes d'équivalence distinctes est vide.
 
 \begin{Th}
 L'intersection de deux classes d'équivalence distinctes est vide.

+On dit aussi que les classes sont deux à deux disjointes.

 \end{Th}
 
 \end{Th}
 

-\begin{Rem}
- On dit aussi que les classes sont deux à deux disjointes.
-\end{Rem}
-

 
 \begin{Pre}
 On considère deux classes, $\dot x$ et $\dot y$, soit $z\in\dot x\inter\dot y$; $\qqs t\in\dot x$, on a $(t,x)\in G$; mais
 
 \begin{Pre}
 On considère deux classes, $\dot x$ et $\dot y$, soit $z\in\dot x\inter\dot y$; $\qqs t\in\dot x$, on a $(t,x)\in G$; mais


@@ -355,7 +352,7 @@ Trouver la partition de $A$ induite par $\mathcal{R}$, c'est-à-dire trouver les
 
 
 
 
 
 

-\begin{Exo}[Une relation d'équivalence]
+\begin{Exo}

 On considère l'ensemble des points du plan rapporté à
 deux axes de coordonnées rectangulaires et deux points $P_1$ et
 $P_2$ de coordonnées respectives $(x_1,y_1)$ et $(x_2,y_2)$; on
 On considère l'ensemble des points du plan rapporté à
 deux axes de coordonnées rectangulaires et deux points $P_1$ et
 $P_2$ de coordonnées respectives $(x_1,y_1)$ et $(x_2,y_2)$; on


@@ -378,35 +375,31 @@ $P_1 {\mathcal{R}} P_2 \Ssi x_1y_1=x_2y_2\ {\rm et}\ x_1x_2\geqslant 0$
 % \end{Exo}
 
 
 % \end{Exo}
 
 

-\begin{Exo}
-Définir, par leurs graphes, les relations d'équivalence dans $E$ qui comportent respectivement le moins et le plus possible de points.
-Que peut-on dire de ces relations? 
-\end{Exo}

 
 
 
 

-\subsection{Ensemble-quotient}
+% \subsection{Ensemble-quotient}

 
 

-\begin{Def}[Ensemble-quotient]
-Il s'agit de l'ensemble des classes d'équivalence de tous les éléments de $E$.
-\end{Def}
+% \begin{Def}[Ensemble-quotient]
+% Il s'agit de l'ensemble des classes d'équivalence de tous les éléments de $E$.
+% \end{Def}

 
 
 
 

-\begin{Notation}
-$E/{\mathcal{R}}$.
-\end{Notation}
+% \begin{Notation}
+% $E/{\mathcal{R}}$.
+% \end{Notation}

 
 
 
 

-Pour parler aisément d'une classe, on choisit un de ses éléments, 
-et cet élément, surmonté d'un point, sert à représenter la classe en question.
-Une fois que ce choix est fait, il est définitif, et il n'est plus question d'évoquer les autres éléments de cette classe, il faut
-se tenir, sous peine d'incohérence, au choix qui a été fait.
+% Pour parler aisément d'une classe, on choisit un de ses éléments, 
+% et cet élément, surmonté d'un point, sert à représenter la classe en question.
+% Une fois que ce choix est fait, il est définitif, et il n'est plus question d'évoquer les autres éléments de cette classe, il faut
+% se tenir, sous peine d'incohérence, au choix qui a été fait.

 
 
 
 
 
 

-\begin{Ex}[Congruence modulo 4]
-On choisit pour représentants les entiers $<4$, donc 0, 1, 2 et 3.
-L'ensemble-quotient est $\Z/4\Z=\{\dot 0,\dot 1,\dot 2,\dot 3\}$.
-\end{Ex}
+% \begin{Ex}[Congruence modulo 4]
+% On choisit pour représentants les entiers $<4$, donc 0, 1, 2 et 3.
+% L'ensemble-quotient est $\Z/4\Z=\{\dot 0,\dot 1,\dot 2,\dot 3\}$.
+% \end{Ex}