Relations

Exercice 1413. On définit sur $\R$ la relation binaire $R$ par $xRy \iff \cos^2 x + \sin^2 y = 1$.\\
  1. Montrer que $R$ est une relation d'équivalence.\\
  2. Déterminer la classe d'équivalence de $x \in \R$.
Exercice 1414. On considère la relation $\preceq$ sur $\N$ définie par $\forall n,m \in \N^{2}$, $(n \preceq m) \iff \exists p \in \N ,\; m = n^{p}$.\\
  1. Vérifier que $\preceq$ est une relation d’ordre.\\
  2. Est-ce un ordre total ?
Exercice 1415. On considère la relation $//$ sur $\Z\times\N^{*}$ définie par\\ \[ \forall (a,b),(c,d)\in\Z\times\N^{*},\quad (a,b)//(c,d)\iff ad-bc=0. \] Démontrer que $//$ est une relation d'équivalence.
Exercice 1416. Soit $(E,\leqslant)$ un ensemble ordonné.\\ Pour tous $x,y \in E$, on définit une relation $C$ sur $E$ par \[ xCy \iff (x \leqslant y) \vee (y \leqslant x). \] Ainsi $xCy$ si et seulement si $x$ et $y$ sont comparables.\\
  1. La relation $C$ est-elle réflexive ?\\
  2. La relation $C$ est-elle symétrique ?\\
  3. La relation $C$ est-elle transitive ?
Exercice 1417. Soit $\mathcal{R}$ la relation définie sur $\R$ par :\\ \[ \forall (x,y) \in \R^2,\;\; x\mathcal{R}y \Longleftrightarrow (x=y=0)\;\;\lor\;\;xy>0.\\ \]
  1. Montrer que $\mathcal{R}$ est une relation d’équivalence. Décrire les classes d’équivalence associées.\\
  2. Montrer que $\mathcal{R}$ est une congruence sur $(\R,\times)$.
Exercice 1418. Étudier la relation définie sur $\N$ par : $x\mathcal{R}y \Longleftrightarrow \exists n \in \N^*,\;\; y=x^n$.

Exercice 1419. Démonstration

\\ Soit $E$ un ensemble et $\sim$ une relation d’équivalence sur $E$.\\ Pour tout $x \in E$, on note $\mathrm{cl}(x) = \{y \in E \mid y \sim x\}$.\\
  1. Montrer que pour tous $x,y \in E$ on a \[ \mathrm{cl}(x)=\mathrm{cl}(y) \Longleftrightarrow \mathrm{cl}(x)\cap\mathrm{cl}(y)\neq\varnothing \Longleftrightarrow x\sim y. \]
  2. En déduire que les classes d’équivalence de $\sim$ forment une partition de $E$.
Exercice 1420. Soit $\mathcal{C}$ l’ensemble des cercles du plan. On définit sur $\mathcal{C}$ la relation $\mathcal{R}$ de la façon suivante :\\ pour tous cercles $C_1$ et $C_2$, de centres respectifs $O_1$ et $O_2$, et de rayons $R_1$ et $R_2$, $C_1\mathcal{R}C_2$ si et seulement si $d(O_1,O_2)\leqslant R_2-R_1$.\\ Étudier la relation $\mathcal{R}$.
Exercice 1421. Soit $R$ une relation binaire sur un ensemble $E$. On suppose que $R$ est réflexive et transitive.\\
  1. On définit la relation binaire $S$ sur $E$ par : pour tous $x,y \in E$, on pose \[ xSy \Longleftrightarrow (xRy) \;\text{ et }\; (yRx). \] Montrer que $S$ est une relation d'équivalence.\\
  2. Pour tout $\bar x,\bar y \in E/S$ on pose \[ \bar x \,\bar R\, \bar y \Longleftrightarrow xRy. \] Montrer que $\bar R$ est correctement définie et que c'est une relation d'ordre.\\
  3. Montrer que la relation $R$ de divisibilité est un préordre sur $\Z$.\\ Quelles sont les classes d'équivalence de la relation $S$ associée\\ La relation d'ordre associée est-elle totale
Exercice 1422. Soit $E$ l’ensemble des fonctions de $\R$ dans $\R$.\\ Soit $\mathcal{R}$ la relation définie sur $E$ par la propriété suivante :\\ on dit que $f\mathcal{R}g$ si et seulement s’il existe un sous-ensemble $F \subset \R$, au plus dénombrable, tel que $f$ et $g$ coïncident sur $\R\setminus F$.\\ Montrer que $\mathcal{R}$ est une relation d’équivalence.
Exercice 1423. Soit $R$ une relation binaire sur un ensemble $E$ à la fois réflexive et transitive.\\ On définit les relations $S$ et $T$ par \[ xSy \Longleftrightarrow (xRy \; \mathrm{et} \; yRx) \] et \[ xTy \Longleftrightarrow (xRy \; \mathrm{ou} \; yRx). \] Les relations $S$ et $T$ sont-elles des relations d'équivalence ?
Exercice 1424. Soit $E$ un ensemble et $A$ une partie de $E$.\\ On définit une relation $R$ sur $\mathcal{P}(E)$ par \[ XRY \Longleftrightarrow X\cup A=Y\cup A. \]
  1. Montrer que $R$ est une relation d'équivalence. \\
  2. Décrire la classe d'équivalence de $X\in\mathcal{P}(E)$.
Exercice 1425. On définit une relation binaire $\preccurlyeq$ sur $\mathbb{R}_+^*$ par \[ x\preccurlyeq y \Longleftrightarrow \exists n\in\mathbb{N},\quad y=x^n. \] Montrer que $\preccurlyeq$ est une relation d'ordre.\\ Cet ordre est-il total ?
Exercice 1426. Soit \[ E=\{(x,y)\in\mathbb{R}^2\mid x\leqslant y\}. \] On définit une relation $\preccurlyeq$ sur $E$ par \[ (x,y)\preccurlyeq (x',y') \Longleftrightarrow (x,y)=(x',y') \; \mathrm{ou} \; y\leqslant x'. \] Montrer que $\preccurlyeq$ est une relation d'ordre sur $E$.
Exercice 1427. Soit $E$ l'ensemble des couples $(I,f)$ formés d'un intervalle $I$ et d'une fonction réelle définie sur $I$.\\ On définit une relation $\preccurlyeq$ sur $E$ par \[ (I,f)\preccurlyeq(J,g) \Longleftrightarrow I\subset J \quad \mathrm{et} \quad g_{\mid I}=f. \] Montrer que $\preccurlyeq$ est une relation d'ordre sur $E$.
Exercice 1428. Soient $A,B$ deux parties d'un ensemble $E$ ordonné par $\preccurlyeq$.\\ On suppose que $A$ et $B$ ont chacune un plus grand élément.\\ Qu'en est-il de $A\cup B$ lorsque l'ordre est total ? Lorsqu'il ne l'est pas ?\\ Que dire de $A\cap B$ ?
Exercice 1429. Soit $E$ un ensemble ordonné par une relation $\leqslant$.\\ Un tableau à $n$ lignes et $p$ colonnes est formé d'éléments $a_{i,j}\in E$.\\ On considère \[ \max_{1\leqslant j\leqslant p}\left(\min_{1\leqslant i\leqslant n}a_{i,j}\right) \quad \mathrm{et} \quad \min_{1\leqslant i\leqslant n}\left(\max_{1\leqslant j\leqslant p}a_{i,j}\right). \]
  1. Comparer ces deux nombres. \\
  2. Donner un exemple de non-égalité.
Exercice 1430. Si $(u_n)_{n \in \N}$ et $(v_n)_{n \in \N}$ sont deux suites de réels, on convient que $(u_n)\;R\;(v_n)$ si et seulement si, pour tout $n \in \N$, il existe $p,q \geqslant n$ tels que\\ \[ u_p \leqslant v_n \;\; et \;\; v_q \leqslant u_n. \]
  1. $R$ est-elle une relation d’ordre ? Est-elle une relation d’équivalence ?\\
  2. Notons $c$ une suite constante. Déterminer les suites $u$ telles que $u\;R\;c$.
Exercice 1431. Soit $E$ un ensemble fini et $O_E$ l’ensemble des ordres sur $E$.\\ Si $\leqslant_1$ et $\leqslant_2$ sont deux ordres sur $E$, on dit que $\leqslant_1$ implique $\leqslant_2$ si pour tout $(x,y) \in E^2$, on a\\ \[ x \leqslant_1 y \Rightarrow x \leqslant_2 y. \]
  1. Montrer que cela définit une relation d’ordre sur $O_E$.\\
  2. Montrer que $O_E$ admet un minimum pour cette relation.\\
  3. Quels sont les éléments maximaux de $O_E$ ?
Exercice 1432. \\
  1. Montrer que la relation $\sim$ définie sur $\N \times \N$ par\\ \[ (a,b)\sim(c,d)\Longleftrightarrow a+d=b+c\\ \] est une relation d’équivalence.\\
  2. Expliquer en quoi l’ensemble quotient (l’ensemble des classes d’équivalence) pour cette relation définit $\Z$.\\
  3. Montrer que la loi d’addition sur $\N^2$ est compatible avec la relation $\sim$, et qu’elle coïncide, par passage au quotient, avec l’addition de $\Z$.
Exercice 1433. Soit I un ensemble ordonné et $(E_i)_{i \in I}$ une famille d’ensembles ordonnés.\\ Toutes les relations d’ordre utilisées seront notées $\leqslant$.\\ On pose $E=\{(i,x) \mid i \in I \;\; \text{et} \;\; x \in E_i\}$ et on le munit de l’ordre suivant :\\ \[ (i,x) \leqslant (j,y) \iff (i < j \;\; \text{ou} \;\; (i=j \;\; \text{et} \;\; x \leqslant y)). \] Vérifier que c’est bien un ordre sur $E$.\\ On dit qu’un ensemble $(F,\leqslant)$ est bien ordonné lorsque toute partie non vide de $F$ possède un minimum.\\ Montrer que si $I$ et les $E_i$ sont tous bien ordonnés, alors $E$ est aussi bien ordonné.
Exercice 1434. Soit $(E,\leqslant)$ un ensemble ordonné.\\ Montrer que les propriétés suivantes sont équivalentes :\\
  • Toute partie non vide de $E$ possède un minimum.\\
  • $\leqslant$ est un ordre total et il n’existe aucune suite $(x_n)_{n\in\N}$ de $E$ strictement décroissante.\\
On dit dans ce cas que $\leqslant$ est un bon ordre sur $E$.
Exercice 1435. Soit $(E,\preccurlyeq)$ un ensemble ordonné.\\ On dit que $E$ est bien ordonné lorsque toute partie non vide de $E$ admet un plus petit élément.\\
    1. Montrer qu’un ensemble bien ordonné est totalement ordonné.\\ La réciproque est-elle vraie ?\\
    2. Montrer qu’un ensemble fini et totalement ordonné est bien ordonné.\\
  2. Démontrer que si $(E,\preccurlyeq)$ et $(E,\succcurlyeq)$ sont bien ordonnés, alors $E$ est un ensemble fini.\\
  3. On dit qu’un élément $x$ de $E$ admet un successeur $s$ dans $E$ lorsque\\ \[ x \prec s\;\;\text{et}\;\;\forall a \in E,\; (x \prec a) \Rightarrow (s \preccurlyeq a), \] où $\prec$ désigne l’ordre strict associé à $\preccurlyeq$.\\
    1. Montrer que si un élément $x$ de $E$ admet un successeur, alors celui–ci est unique. On le note $\mathrm{succ}(x)$.\\
    2. Dans le cas où $E$ est bien ordonné, montrer que pour tout élément $x$ de $E$, on a l’alternative suivante :\\ ou bien $x$ est un élément maximal (c’est–à–dire qu’il n’existe pas d’élément plus grand que $x$ dans $E$),\\ ou bien $x$ admet un successeur.
Exercice 1436. On considère sur $\mathcal{F}(E,E)$ la relation binaire $R$ définie par \[ fRg \Longleftrightarrow \exists \varphi\in\mathfrak{S}(E),\quad f\circ\varphi=\varphi\circ g. \]
  1. Montrer que $R$ est une relation d'équivalence.\\
  2. Décrire la classe d'équivalence d'une fonction donnée $f\in\mathcal{F}(E,E)$.
Exercice 1437. Soit $R$ une relation binaire réflexive et transitive.\\ On définit une relation $S$ par \[ xSy \Longleftrightarrow xRy \; \mathrm{et} \; yRx. \] Montrer que $S$ est une relation d'équivalence et que $R$ permet de définir une relation d'ordre sur les classes d'équivalences de $S$.
Exercice 1438. Soit $E$ un ensemble de cardinal $n$, $R$ une relation d'équivalence sur $E$ ayant $k$ classes d'équivalence et \[ G=\{(x,y)\in E^2\mid xRy\} \] le graphe de $R$, supposé de cardinal $p$.\\ Prouver que \[ n^2\leqslant kp. \]
Exercice 1439. On définit une relation binaire $\preccurlyeq$ sur \[ \{z\in\mathbb{C}\mid \mathrm{Im}(z)\geqslant0\} \] par \[ z\preccurlyeq z' \Longleftrightarrow |z| < |z'| \quad \mathrm{ou} \quad \left(|z|=|z'| \; \mathrm{et} \; \mathrm{Re}(z)\leqslant \mathrm{Re}(z')\right). \] Montrer qu'il s'agit d'une relation d'ordre total.
Exercice 1440. Soit $(E,\preccurlyeq)$ un ensemble ordonné tel que toute partie non vide admette un plus petit élément et un plus grand élément.\\ Montrer que $E$ est fini.
Exercice 1441. Soit $(E,\leqslant)$ un ensemble ordonné.\\ On dit qu’une partie $X$ de $E$ est libre si ses éléments sont deux à deux non comparables.\\ On note $L(E)$ l’ensemble des parties libres de $E$.\\ On définit sur $L(E)$ la relation $R$ par\\ \[ X \;R\; Y \iff \forall x \in X,\;\exists y \in Y,\; x \leqslant y. \]
  1. Montrer que $R$ est une relation d’ordre.\\
  2. Montrer que la fonction $\mathrm{Id}_{L(E)}$ est croissante de $(L(E),\subset)$ dans $(L(E),R)$.\\
  3. Sa réciproque est-elle croissante ?
Exercice 1442. Soit $(E,\leqslant)$ un ensemble ordonné fini.\\ On appelle chaîne de $E$ tout sous-ensemble de $E$ totalement ordonné, et cochaîne de $E$ tout sous-ensemble de $E$ formé d’éléments deux à deux incomparables.\\ Montrer que la longueur maximale d’une chaîne de $E$ est égale au minimum du nombre de parties d’une partition de $E$ dont toutes les parties sont des cochaînes de $E$.