Relations

Exercice 784. 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 785. 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 786. 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 787. 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 788. 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 789. 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 790. 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 791. 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 792. 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 793. 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 794. 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 795. 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 796. 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$.