Relations binaires et applications
Feuille d'exercices
I) Relations binaires
Dire si les relations suivantes sont réflexives, symétriques, antisymétriques, transitives :
- $E=\Z$ et $x\Rr y \iff x=-y$ ;
- $E=\R$ et $x\Rr y \iff \cos^2 x+\sin^2 y=1$ ;
- $E=\N$ et $x\Rr y \iff \exists p,q \ge 1, \ y=px^q$ ($p$ et $q$ sont des entiers).
Quelles sont parmi les exemples précédents les relations d'ordre et les relations d'équivalence (auquel cas, donner les classes d'équivalence) ?
- Corrigé : commande LaTeX inconnue : \Rrx, \Rry, \Rrz (absente des macros reconnues — coquille probable ou macro légitime à ajouter à la liste)
A - Relations d'équivalence
Sur $\R^2$, on définit la relation $\Rr$ par $$ (x, y) \Rr (x', y') \iff x = x'. $$ Démontrer que $\Rr$ est une relation d'équivalence, puis déterminer la classe d'équivalence d'un élément $(x_0, y_0) \in \R^2$.
On définit une relation binaire $\Rr$ sur $\Z$ par $x \Rr y$ si, et seulement si, $x + y$ est pair. Montrer que $\Rr$ est une relation d'équivalence et préciser ses classes d'équivalence.
- Soient $E$ et $F$ deux ensembles et $f : E \to F$ une application. Pour tous $x, x' \in E$, on dit que $x \sim x'$ si $f(x) = f(x')$. Montrer que $\sim$ est une relation d'équivalence sur $E$ et décrire la classe d'équivalence de $x$ pour $\sim$ pour tout $x \in E$.
- Dans cette question, $E = \C$, $F = \R_+$ et $f$ est la fonction $z \mapsto |z|$. Déterminer un ensemble de représentants des classes d'équivalence de $\sim$.
- Dans cette question, $E = \R^*_+$, $F = \R$ et $f$ est la fonction $x \mapsto x \ln x$. Calculer le cardinal de la classe d'équivalence de $x$ pour $\sim$ pour tout $x \in \R^*_+$.
- Soient $A$ un ensemble et $B \in \Ps(A)$. Dans cette question, $E = F = \Ps(A)$ et $f$ est l'application $X \mapsto X \cap B$. Montrer que $\Ps(B)$ est un ensemble de représentants des classes d'équivalence de $\sim$.
- ★★ On revient au cas général de la question $1)$ et on note $\bar{x}$ la classe d'équivalence de $x$ pour $\sim$ pour tout $x \in E$. On veut définir une application $\bar{f} : E/\!\sim \to F$ en posant $\bar{f}(\bar{x}) = f(x)$ pour tout $x \in E$, mais cette définition pose a priori problème. Quel problème ? Montrer que le problème n'en est pas un, puis que $\bar{f}$ est injective.
B - Relation d'ordre
Soit $f: E \to \R$ une application injective. On définit sur $E$ une relation binaire $\preccurlyeq$ par $$ x \preccurlyeq y \iff f(x) \le f(y) $$
- Montrer que $\preccurlyeq$ est une relation d'ordre sur $E$.
- S'agit-il d'une relation d'ordre totale ?
On définit une relation binaire $\preccurlyeq$ sur $\R_+^*$ par : $$ x \preccurlyeq y \iff \exists n \in \N, y = x^n $$ Montrer que $\preccurlyeq$ est une relation d'ordre. Cet ordre est-il total ?
Soit $E$ l'ensemble des couples $\pa{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 : $\pa{I, f} \preccurlyeq \pa{J, g} \iff I \subset J$ et $\restrict{g}{I} = f$. Montrer que $\preccurlyeq$ est une relation d'ordre sur $E$.
Soient $E$ un ensemble et $\preccurlyeq$ une relation d'ordre sur $E$. Pour tous $x, y \in E$, on notera $xy$ le couple $(x, y)$ pour alléger.
- Pour tous $xy, x'y' \in E^2$, on dit que $xy \preccurlyeq^\circ x'y'$ si $x \preccurlyeq x'$ et $y \preccurlyeq y'$.
- Montrer que $\preccurlyeq^\circ$ est une relation d'ordre.
- Montrer que si $E$ possède au moins deux éléments, $\preccurlyeq^\circ$ n'est pas totale.
- Pour tous $xy, x'y' \in E^2$, on dit que $xy \preccurlyeq^\star x'y'$ si $x \prec x'$ ou $\pa{x = x' \et y \preccurlyeq y'}$.
- Montrer que $\preccurlyeq^\star$ est une relation d'ordre.
- Montrer que si $\preccurlyeq$ est totale, $\preccurlyeq^\star$ l'est aussi.
Soit $E$ un ensemble.
- Soit $\Rr$ une relation binaire sur $E$. Pour tous $x, y \in E$, on dit que $x \Rr^{\text{tr}} y$ si : $$
\exists n \in \N^*, \hquad \exists x_0, \dots, x_n \in E, \hquad x = x_0 \text{ et } \pa{\forall k \in \Intn{0}{n-1}, \, x_k \Rr \,x_{k+1}} \text{ et } x_n = y.
$$ La relation $\Rr^{\text{tr}}$ ainsi définie est appelée la clôture transitive de $\Rr$.
- Montrer que $\Rr^{\text{tr}}$ est transitive.
- Montrer que si $\Rr$ est réflexive, $\Rr^{\text{tr}}$ l'est aussi.
- Montrer que si $\Rr$ est symétrique, $\Rr^{\text{tr}}$ l'est aussi.
- On rappelle qu'une relation binaire sur $E$ n'est jamais qu'une partie de $E \times E$.
- ★ Soient $\preccurlyeq$ une relation d'ordre sur $E$ et $u, v \in E$ deux éléments pour lesquels $u \not\preccurlyeq v$ et $v \not\preccurlyeq u$. Montrer que $\pa{\preccurlyeq \cup \pae{\pa{u, v}}}^{\text{tr}}$ est une relation d'ordre sur $E$.
- ★★ En déduire que si $E$ est fini, toute relation d'ordre sur $E$ est incluse dans une relation d'ordre totale (théorème d'extension de Szpilrajn).
II) Applications
A - Applications explicites
Soient $f : n \mapsto n + 1$ et $g : n \mapsto \max \pae{0, n - 1}$ définies sur $\N$. Montrer que $g \circ f = \text{Id}_{\N}$, mais que $f$ et $g$ ne sont pas bijectives de $\N$ sur $\N$. Que faut-il en retenir ?
Soit $s: \N \to \N^*$ l'application définie par $s(n) = n+1$. Montrer que l'application $s$ est bijective :
- En vérifiant injectivité et surjectivité.
- En comptant le nombre d'antécédents.
- En déterminant une application susceptible d'être sa bijection réciproque.
Les applications suivantes sont-elles injectives ? surjectives ? bijectives ?
- $(x, y) \mapsto 2y$ de $\R^2$ dans $\R$.
- $(x, y) \mapsto (1, x - y, y)$ de $\R^2$ dans $\R^3$.
- $(x, y) \mapsto (2x + y, 3x - 2y)$ de $\R^2$ dans $\R^2$.
- $(x, y, z) \mapsto (x + y + z, x - y - z, x)$ de $\R^3$ dans $\R^3$.
- $x \mapsto x^2 + 1$ de $\R$ dans $\R$.
- $z \mapsto z^2 + 1$ de $\C$ dans $\C$.
- $(a, b) \mapsto a + b\sqrt{2}$ de $\Z \times \Z$ dans $\R$.
- $f \mapsto f(1) - f(0)$ de $\R^\R$ dans $\R$.
- On note $f$ la fonction $x \mapsto \sin \pa{\f{\pi}{x}}$ sur $\R^*_+$. Déterminer $f\pa{\Intoo{0}{1}}$ et $f^{-1}\pa{\{0\}}$.
- Déterminer l'image réciproque de $\Intff{-1}{2}$ par la fonction $x \mapsto \sqrt{x^2+x+1}$.
- On note $f$ la fonction $x \mapsto \f{x}{1+x^2}$. Déterminer l'image de $f$ et $f^{-1}\pa{\Intff{\f{1}{4}}{1}}$.
Proposer une bijection de $\Intff{-1}{1}$ sur $\Intff{a}{b}$ pour tous $a, b \in \R$ pour lesquels $a < b$.
- Proposer une bijection explicite de $\N$ sur $\Z$.
- En exploitant le théorème de factorisation première, proposer une injection de $\N^k$ dans $\N$ pour tout $k \in \N^*$.
- Montrer que l'application : $$ \pa{m, n} \mapsto \f{\pa{m + n}\pa{m + n + 1}}{2} + n $$ est bijective de $\N^2$ sur $\N$.
Déterminer toutes les injections $f : \N \to \N$ pour lesquelles $f(n) \leq n$ pour tout $n \in \N$.
Soient $E_1, F_1, E_2, F_2$ quatre ensembles non vides et $f_1 : E_1 \to F_1$ et $f_2 : E_2 \to F_2$ deux applications.
- Pour tout $(x_1, x_2) \in E_1 \times E_2$, on pose : $$
\phi(x_1, x_2) = (f_1(x_1), f_2(x_2)).
$$
- Montrer que $\phi$ est injective sur $E_1 \times E_2$ si et seulement si $f_1$ l'est sur $E_1$ et $f_2$ l'est sur $E_2$.
- Même question avec « surjective » à la place d'« injective ».
- On suppose que $E_1 \cap E_2 = F_1 \cap F_2 = \emptyset$ et que $f_1$ et $f_2$ sont bijectives. Construire une bijection de $E_1 \sqcup E_2$ sur $F_1 \sqcup F_2$.
- Montrer que l'application $(A, B) \mapsto (2A) \cup (2B + 1)$ est bijective de $\Ps(\N)^2$ sur $\Ps(\N)$.
- On note $\phi$ l'application $X \mapsto X \cap 2\N$ de $\Ps(\N)$ dans $\Ps(\N)$.
- $\phi$ est-elle injective ?
- $\phi$ est-elle surjective ? Déterminer son image.
- Soient $E$ un ensemble et $A$ une partie de $E$. On note $\phi$ l'application $X \mapsto X \cup A$ de $\Ps(E)$ dans lui-même.
- $\phi$ est-elle injective ?
- $\phi$ est-elle surjective ? Déterminer son image.
- Soient $E$ un ensemble et $A$ et $B$ deux parties de $E$. On note $f$ l'application $X \mapsto \pa{X \cap A, X \cap B}$ de $\Ps(E)$ dans $\Ps(A) \times \Ps(B)$. Montrer que :
- $f$ est injective si et seulement si $A \cup B = E$.
- $f$ est surjective si et seulement si $A \cap B = \emptyset$.
Soit $E$ un ensemble. Pour toutes parties $A, B$ de $E$, on appelle différence symétrique de $A$ et $B$ la partie de $E$ : $$ A \Delta B = (A \setminus B) \cup (B \setminus A). $$
- Exprimer $\one_{A \Delta B}$ en fonction de $\one_A$ et $\one_B$.
- Montrer que $A \Delta B = (A \cup B) \setminus (A \cap B)$.
- Montrer que $\Delta$ est associative, i.e. que pour tous $A, B, C \in \Ps(E)$ : $$ A \Delta (B \Delta C) = (A \Delta B) \Delta C. $$
- Corrigé : commande mathématique hors de tout $ : \Delta, \cap, \cup, \setminus (probablement un $ manquant autour)
B - Applications implicites
Soient $f : E \to F$ une application et $B, B'$ deux parties de $F$.
- Montrer que $B \subset B' \then f^{-1}(B) \subset f^{-1}(B')$.
- Montrer que $f^{-1}\pa{B \cup B'} = f^{-1}(B) \cup f^{-1}(B')$.
- Montrer que $f^{-1}\pa{B \cap B'} = f^{-1}(B) \cap f^{-1}(B')$.
- Montrer que $f^{-1}\pa{\overline{B}} = \overline{f^{-1}(B)}$, les complémentaires étant pris respectivement dans $F$ et dans $E$.
- Montrer que $f\pa{f^{-1}(B)} \subset B$. Trouver contre-exemple de l'inclusion réciproque.
- Montrer que $f$ est surjective si et seulement si $$\forall B \subset F, \hquad f\pa{f^{-1}(B)} = B.$$
- Soit $g : F \to G$ une application. Montrer que $$\forall C \subset G, \hquad (g \circ f)^{-1}(C) = f^{-1}\pa{g^{-1}(C)}.$$
- Corrigé : commande mathématique hors de tout $ : \cap, \circ, \cup, \in (probablement un $ manquant autour)
Soient $f : E \to F$ une application et $A, A'$ deux parties de $E$.
- Montrer que $A \subset A' \then f(A) \subset f(A')$.
- Montrer que $f\pa{A \cup A'} = f(A) \cup f(A')$.
- Montrer que $f\pa{A \cap A'} \subset f(A) \cap f(A')$.
- Montrer, à l'aide d'un contre-exemple, que l'inclusion réciproque est fausse en général.
- Montrer que $f$ est injective si et seulement si $$ \forall A, A' \subset E, \hquad f\pa{A \cap A'} = f(A) \cap f(A'). $$
- Montrer que $f\pa{\overline{A}} \supset f(E) \but f(A)$.
- Montrer que $A \subset f^{-1}\pa{f(A)}$.
- Montrer que $f$ est injective si et seulement si $$\forall A \subset E, \hquad f^{-1}\pa{f(A)} = A.$$
- Soit $B$ une partie de $F$. Montrer que $f\pa{A \cap f^{-1}(B)} = f(A) \cap B$.
- Soit $g : F \to G$ une application. Montrer que $(g \circ f)(A) = g\pa{f(A)}$.
- Corrigé : commande mathématique hors de tout $ : \circ, \exists, \in (probablement un $ manquant autour)
On pourra retenir de ces exercices que si $f$ est bijective, les applications ${A \mapsto f(A)}$ de $\Ps(E)$ dans $\Ps(F)$ et $B \mapsto f^{-1}(B)$ de $\Ps(F)$ dans $\Ps(E)$ sont bijectives et réciproques l'une de l'autre.
Soit $f: E \to I$ une application surjective. On pose $A_i = f^{-1}\pa{\pae{i}}$ pour tout $i \in I$. Montrer que les $A_i$ sont non vides, deux à deux disjoints, de réunion égale à $E$.
Soient $E$ un ensemble et $f : E \to E$ une application. On suppose que $f \circ f = f$ et que $f$ est injective ou surjective. Montrer que $f = \Id_E$.
Soient $f : E \to F$ et $g : F \to E$ deux applications telles que $f \circ g \circ f$ soit bijective. Montrer que $f$ et $g$ sont bijectives.
- Soient $f : F \to E$ et $g : G \to E$ deux applications. Montrer qu'il existe une application $h : G \to F$ telle que $g = f \circ h$ si, et seulement si, $g(G) \subset f(F)$. À quelle condition cette application $h$ est-elle unique ?
- Soient $f : E \to F$ et $g : E \to G$ deux applications. Montrer qu'il existe une application $h : F \to G$ telle que $g = h \circ f$ si, et seulement si, $$ \forall x, y \in E, \quad f(x) = f(y) \then g(x) = g(y). $$ À quelle condition $h$ est-elle unique ?
Soient $E$ et $F$ des ensembles et $f : E \to F$ une application.
- Soit $A$ une partie de $E$. Vrai ou faux ? Justifier.
- Si $f$ est injective, alors $\restrict{f}{A}$ l'est aussi. Et la réciproque ?
- Si $f$ est surjective, alors $\restrict{f}{A}$ l'est aussi. Et la réciproque ?
- Soit $\pa{A_n}_{n \in \N}$ une suite de parties de $E$ de réunion $E$ et croissante pour l'inclusion. Montrer que si $\restrict{f}{A_n}$ est injective pour tout $n \in \N$, alors $f$ l'est aussi.
Glissez une image, collez-la (Ctrl+V), ou parcourez un fichier — ou collez directement l'énoncé en texte.