Logique, ensembles et applications : corrigé des exercices de maths sup.

Corrigé de l’exercice 1 : Négation de propositions quantifiées

1. La phrase s’écrit \(\forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ x = y^2\). Sa négation est \(\exists x \in \mathbb{R},\ \forall y \in \mathbb{R},\ x \neq y^2\). C’est la négation qui est vraie : pour \(x = -1\), on a \(y^2 \geq\, 0 > -1\) pour tout réel \(y\). La phrase de départ est donc fausse.
2. « \(f\) est bornée » s’écrit \(\exists M \in \mathbb{R},\ \forall x \in \mathbb{R},\ |f(x)| \leq\, M\). Sa négation est \(\forall M \in \mathbb{R},\ \exists x \in \mathbb{R},\ |f(x)| > M\).
3. « \(f\) est croissante » s’écrit \(\forall (x, y) \in \mathbb{R}^2,\ x \leq\, y \Rightarrow f(x) \leq\, f(y)\). La négation d’une implication \(A \Rightarrow B\) est \(A \wedge \neg B\). La négation est donc \(\exists (x, y) \in \mathbb{R}^2,\ x \leq\, y \text{ et } f(x) > f(y)\). Attention : ce n’est pas « \(f\) est décroissante ».
4. La convergence vers \(0\) s’écrit \(\forall \varepsilon > 0,\ \exists N \in \mathbb{N},\ \forall n \geq\, N,\ |u_n| \leq\, \varepsilon\). Sa négation est \(\exists \varepsilon > 0,\ \forall N \in \mathbb{N},\ \exists n \geq\, N,\ |u_n| > \varepsilon\).
5. « \(f\) est périodique » s’écrit \(\exists T > 0,\ \forall x \in \mathbb{R},\ f(x + T) = f(x)\). Sa négation est \(\forall T > 0,\ \exists x \in \mathbb{R},\ f(x + T) \neq f(x)\). Remarquez que la condition \(T > 0\) reste inchangée : seul le quantificateur change.

Point de méthode : les ensembles qui suivent un quantificateur (\(\varepsilon > 0\), \(n \geq\, N\)) ne se nient jamais ; on ne nie que la propriété finale.

Corrigé de l’exercice 2 : Ordre des quantificateurs

1. Soit \(x \in \mathbb{R}\). Le réel \(y = -x\) vérifie \(x + y = 0\). \(P_1\) est vraie.
2. Supposons qu’un réel \(y\) convienne pour tout \(x\). Avec \(x = 0\), on obtient \(y = 0\). Avec \(x = 1\), on obtient \(y = -1\). C’est contradictoire. \(P_2\) est fausse, et sa négation est \(\forall y \in \mathbb{R},\ \exists x \in \mathbb{R},\ x + y \neq 0\).
3. Soit \(n \in \mathbb{N}\). L’entier \(m = n + 1\) vérifie \(m > n\). \(P_3\) est vraie.
4. Soit \(m \in \mathbb{N}\). Pour \(n = m\), l’inégalité \(m > n\) est fausse. Ainsi, aucun \(m\) ne convient. \(P_4\) est fausse, et sa négation est \(\forall m \in \mathbb{N},\ \exists n \in \mathbb{N},\ m \leq\, n\).
5. Le réel \(x = 1\) vérifie \(1 \times y = y\) pour tout \(y\). \(P_5\) est vraie.
6. Pour \(y = 0\), on a \(xy = 0 \neq 1\) quel que soit \(x\). \(P_6\) est fausse, et sa négation est \(\exists y \in \mathbb{R},\ \forall x \in \mathbb{R},\ xy \neq 1\).

Les couples \((P_1, P_2)\) et \((P_3, P_4)\) montrent qu’échanger un \(\forall\) et un \(\exists\) change le sens. En effet, dans \(P_1\), le réel \(y\) dépend de \(x\) ; dans \(P_2\), il devrait convenir pour tous les \(x\) à la fois.

Corrigé de l’exercice 3 : Implication, réciproque et contraposée

1. On dresse la table en notant V pour vrai et F pour faux. Si \(P\) et \(Q\) sont vraies, les deux énoncés sont vrais. Si \(P\) est vraie et \(Q\) fausse, \(P \Rightarrow Q\) est fausse, et \(\neg P \vee Q\) aussi. Si \(P\) est fausse, les deux énoncés sont vrais, quelle que soit la valeur de \(Q\). Les tables coïncident, donc \((P \Rightarrow Q) \Leftrightarrow (\neg P \vee Q)\). D’après les lois de De Morgan, la négation de \(P \Rightarrow Q\) est \(P \wedge \neg Q\).
2. La réciproque est « \(x^2 > 4 \Rightarrow x > 2\) ». Elle est fausse : \(x = -3\) vérifie \(x^2 = 9 > 4\) mais pas \(x > 2\). La contraposée est « \(x^2 \leq\, 4 \Rightarrow x \leq\, 2\) ». Or l’implication de départ est vraie : si \(x > 2\), alors \(x > 0\), et en multipliant \(x > 2\) par \(x\) puis par \(2\), on obtient \(x^2 > 2x > 4\). Par conséquent, l’implication et sa contraposée sont vraies, la réciproque est fausse.
3. La contraposée s’énonce ainsi : si \(n\) est impair, alors \(4\) divise \(n^2 – 1\). Supposons \(n = 2k + 1\) avec \(k \in \mathbb{Z}\). Alors \(n^2 – 1 = 4k^2 + 4k = 4k(k+1)\), qui est un multiple de \(4\). La contraposée est vraie, donc si \(4\) ne divise pas \(n^2 – 1\), alors \(n\) est pair.
4. Prouvons la contraposée : si \(x^2 – 2x = y^2 – 2y\), alors \(x = y\). D’abord, on factorise :
   \[x^2 – 2x – (y^2 – 2y) = (x – y)(x + y) – 2(x – y) = (x – y)(x + y – 2).\]
   Ce produit est nul. Or \(x > 1\) et \(y > 1\), donc \(x + y – 2 > 0\). Par conséquent, \(x – y = 0\). La contraposée est établie, donc \(x \neq y \Rightarrow x^2 – 2x \neq y^2 – 2y\).

Corrigé de l’exercice 4 : Raisonnements par l’absurde

1. Si \(3\) ne divise pas \(p\), le reste de \(p\) dans la division par \(3\) vaut \(1\) ou \(2\). Si \(p = 3k + 1\), alors \(p^2 = 3(3k^2 + 2k) + 1\). Si \(p = 3k + 2\), alors \(p^2 = 9k^2 + 12k + 4 = 3(3k^2 + 4k + 1) + 1\). Dans les deux cas, \(p^2\) a pour reste \(1\). Donc \(3\) ne divise pas \(p^2\). Par contraposition, si \(3\) divise \(p^2\), alors \(3\) divise \(p\).
2. Supposons par l’absurde que \(\sqrt{3} = \frac{p}{q}\) avec \(p \in \mathbb{Z}\), \(q \in \mathbb{N}^{*}\), la fraction étant irréductible. En élevant au carré, \(p^2 = 3q^2\). Ainsi, \(3\) divise \(p^2\), donc \(3\) divise \(p\) d’après la question 1. On écrit \(p = 3p^{\prime}\) : alors \(9p^{\prime 2} = 3q^2\), soit \(q^2 = 3p^{\prime 2}\). De même, \(3\) divise \(q\). Ainsi, \(3\) divise \(p\) et \(q\), ce qui contredit l’irréductibilité. Donc \(\sqrt{3}\) est irrationnel.
3. Supposons par l’absurde \(x \neq 0\). Alors \(\varepsilon = \frac{|x|}{2}\) est strictement positif. L’hypothèse donne \(|x| \leq\, \frac{|x|}{2}\), donc \(\frac{|x|}{2} \leq\, 0\). C’est impossible puisque \(|x| > 0\). Par conséquent, \(x = 0\).
4. Supposons par l’absurde que \(m = \sqrt{n^2 + 1}\) soit un entier. D’une part, \(n^2 < n^2 + 1\). D’autre part, \(n^2 + 1 < n^2 + 2n + 1 = (n+1)^2\), car \(n \geq\, 1\). Ainsi \(n^2 < m^2 < (n+1)^2\), puis \(n < m < n + 1\), car la fonction racine carrée est strictement croissante. Or aucun entier n’est strictement compris entre deux entiers consécutifs. Donc \(\sqrt{n^2 + 1}\) n’est pas un entier.

Point de méthode : dans un raisonnement par l’absurde, annoncez dès la première ligne l’hypothèse faite, puis signalez clairement la contradiction obtenue.

Corrigé de l’exercice 5 : Disjonction des cas

1. Soit \(k \in \mathbb{Z}\). Si \(k\) est pair, \(k = 2j\) et \(k(k+1) = 2j(k+1)\) est pair. Si \(k\) est impair, \(k + 1\) est pair et le produit l’est aussi. Ensuite, soit \(n\) impair : \(n = 2k + 1\). Alors \(n^2 – 1 = 4k^2 + 4k = 4k(k+1)\). Comme \(k(k+1) = 2j\) pour un entier \(j\), on obtient \(n^2 – 1 = 8j\). Ainsi, \(8\) divise \(n^2 – 1\) pour tout entier impair \(n\).
2. On étudie le signe de \(x – 1\) et de \(x + 2\).
   • Si \(x \leq\, -2\), les deux quantités sont négatives : \(g(x) = (1 – x) + (-x – 2) = -2x – 1\).
   • Si \(-2 \leq\, x \leq\, 1\), on a \(x – 1 \leq\, 0 \leq\, x + 2\) : \(g(x) = (1 – x) + (x + 2) = 3\).
   • Si \(x \geq\, 1\), les deux quantités sont positives : \(g(x) = (x – 1) + (x + 2) = 2x + 1\).

   Ainsi, \(g(x) = -2x – 1\) sur \(]-\infty, -2]\), \(g(x) = 3\) sur \([-2, 1]\) et \(g(x) = 2x + 1\) sur \([1, +\infty[\).

3. Résolvons \(g(x) = 5\) cas par cas. Sur \(]-\infty, -2]\), l’équation \(-2x – 1 = 5\) donne \(x = -3\), qui appartient bien à l’intervalle. Sur \([-2, 1]\), l’équation \(3 = 5\) n’a pas de solution. Sur \([1, +\infty[\), l’équation \(2x + 1 = 5\) donne \(x = 2\), qui convient. L’ensemble des solutions de \(g(x) = 5\) est \(\{-3, 2\}\). De même, pour l’inéquation : sur \(]-\infty, -2]\), \(-2x – 1 \leq\, 5\) équivaut à \(x \geq\, -3\), d’où \([-3, -2]\). Sur \([-2, 1]\), l’inégalité \(3 \leq\, 5\) est toujours vraie. Enfin, sur \([1, +\infty[\), \(2x + 1 \leq\, 5\) équivaut à \(x \leq\, 2\), d’où \([1, 2]\). L’ensemble des solutions de \(g(x) \leq\, 5\) est \([-3, 2]\).

La figure ci-dessous confirme ces résultats : la courbe de \(g\) coupe la droite \(y = 5\) aux abscisses \(-3\) et \(2\), et reste en dessous entre ces deux valeurs.

Corrigé de l’exercice 6 : Analyse-synthèse et équation fonctionnelle

1. Analyse. Soit \(f\) une solution et \(x \in \mathbb{R}\). La relation appliquée en \(-x\) donne \(f(-x) + 2f(x) = x^2 – x\). On pose \(a = f(x)\) et \(b = f(-x)\). On obtient le système :
   \[\begin{cases} a + 2b = x^2 + x \\ 2a + b = x^2 – x \end{cases}\]
   On multiplie la seconde ligne par \(2\) et on retranche la première : \(3a = 2x^2 – 2x – x^2 – x = x^2 – 3x\). Nécessairement, \(f(x) = \dfrac{x^2}{3} – x\) pour tout réel \(x\).
2. Synthèse. Posons \(f(x) = \frac{x^2}{3} – x\). Alors \(f(-x) = \frac{x^2}{3} + x\), et
   \[f(x) + 2f(-x) = \frac{x^2}{3} – x + \frac{2x^2}{3} + 2x = x^2 + x.\]
   Cette fonction convient. Il existe donc une unique solution : \(x \mapsto \dfrac{x^2}{3} – x\).

Corrigé de l’exercice 7 : Fonctions paires et impaires par analyse-synthèse

1. Soit \(f\) paire et impaire, et \(x \in \mathbb{R}\). Alors \(f(x) = f(-x) = -f(x)\), donc \(2f(x) = 0\). Ainsi, \(f\) est la fonction nulle.
2. Analyse. Supposons \(f = p + i\) avec \(p\) paire et \(i\) impaire. Pour tout réel \(x\), on a \(f(x) = p(x) + i(x)\) et \(f(-x) = p(x) – i(x)\). En additionnant puis en soustrayant, on obtient
   \[p(x) = \frac{f(x) + f(-x)}{2}, \qquad i(x) = \frac{f(x) – f(-x)}{2}.\]
   Le couple \((p, i)\) est donc unique. Synthèse. Définissons \(p\) et \(i\) par ces formules. D’abord, \(p(-x) = \frac{f(-x) + f(x)}{2} = p(x)\), donc \(p\) est paire. Ensuite, \(i(-x) = \frac{f(-x) – f(x)}{2} = -i(x)\), donc \(i\) est impaire. Enfin, \(p(x) + i(x) = f(x)\). La décomposition existe et elle est unique.
3. Pour \(f(x) = e^x\), on obtient \(p(x) = \frac{e^x + e^{-x}}{2} = \mathrm{ch}\,x\) et \(i(x) = \frac{e^x – e^{-x}}{2} = \mathrm{sh}\,x\). Pour \(f(x) = (x+1)^2 = x^2 + 2x + 1\), on a \(f(-x) = x^2 – 2x + 1\). Par conséquent, \(p(x) = x^2 + 1\) et \(i(x) = 2x\) dans le second cas, et \(e^x = \mathrm{ch}\,x + \mathrm{sh}\,x\) dans le premier.

La figure ci-dessous montre la décomposition de l’exponentielle : la courbe de \(\mathrm{ch}\) est symétrique par rapport à l’axe des ordonnées, celle de \(\mathrm{sh}\) par rapport à l’origine.

Corrigé de l’exercice 8 : Récurrences simples

1. Pour \(n \geq\, 1\), notons \(\mathcal{P}(n)\) : « \(\sum_{k=1}^{n} k^3 = (\frac{n(n+1)}{2})^2\) ». Initialisation : pour \(n = 1\), les deux membres valent \(1\). Hérédité : soit \(n \geq\, 1\) tel que \(\mathcal{P}(n)\) est vraie. Alors
   \[\sum_{k=1}^{n+1} k^3 = \frac{n^2(n+1)^2}{4} + (n+1)^3 = \frac{(n+1)^2 (n^2 + 4n + 4)}{4} = (\frac{(n+1)(n+2)}{2})^2.\]
   Ainsi \(\mathcal{P}(n+1)\) est vraie. Par récurrence, la formule vaut pour tout \(n \geq\, 1\).
2. Notons \(\mathcal{P}(n)\) : « \(2^n \geq\, n^2\) », pour \(n \geq\, 4\). Initialisation : \(2^4 = 16 = 4^2\). Hérédité : soit \(n \geq\, 4\) tel que \(2^n \geq\, n^2\). Alors \(2^{n+1} \geq\, 2n^2\). De plus,
   \[2n^2 – (n+1)^2 = n^2 – 2n – 1 = (n – 1)^2 – 2 \geq\, 9 – 2 > 0,\]
   car \(n – 1 \geq\, 3\). Donc \(2^{n+1} \geq\, (n+1)^2\). La propriété vaut pour tout \(n \geq\, 4\), mais elle est fausse pour \(n = 3\), car \(2^3 = 8 < 9\).
3. L’argument de chevauchement exige que les deux groupes de \(n\) crayons aient au moins un crayon commun. Or, pour \(n = 1\), le groupe compte deux crayons : en retirant le premier, il reste le second, et en retirant le dernier, il reste le premier. Les deux groupes sont disjoints. L’hérédité est fausse de \(n = 1\) à \(n = 2\), et toute la chaîne s’effondre. Une hérédité doit être valable pour tout \(n\) à partir du rang initial.

Corrigé de l’exercice 9 : Récurrence double

1. Notons \(\mathcal{P}(n)\) : « \(u_n = 2^n + 1\) ». Initialisation : \(u_0 = 2 = 2^0 + 1\) et \(u_1 = 3 = 2^1 + 1\). Hérédité : soit \(n \in \mathbb{N}\) tel que \(\mathcal{P}(n)\) et \(\mathcal{P}(n+1)\) sont vraies. Alors
   \[u_{n+2} = 3(2^{n+1} + 1) – 2(2^n + 1) = 3 \cdot 2^{n+1} – 2^{n+1} + 1 = 2^{n+2} + 1.\]
   Par récurrence double, \(u_n = 2^n + 1\) pour tout \(n \in \mathbb{N}\).
2. Initialisation : \(F_1 = 1 \leq\, 2^0\) et \(F_2 = F_1 + F_0 = 1 \leq\, 2^1\). Hérédité : soit \(n \geq\, 1\) tel que \(F_n \leq\, 2^{n-1}\) et \(F_{n+1} \leq\, 2^n\). Alors
   \[F_{n+2} = F_{n+1} + F_n \leq\, 2^n + 2^{n-1} \leq\, 2^n + 2^n = 2^{n+1}.\]
   Par récurrence double, \(F_n \leq\, 2^{n-1}\) pour tout \(n \geq\, 1\).
3. Initialisation : \(F_1 = 1 \geq\, \frac{2}{3} = (\frac{3}{2})^{-1}\) et \(F_2 = 1 = (\frac{3}{2})^0\). Hérédité : soit \(n \geq\, 1\) tel que les inégalités sont vraies aux rangs \(n\) et \(n + 1\). Alors
   \[F_{n+2} \geq\, (\frac{3}{2})^{n-1} + (\frac{3}{2})^{n-2} = (\frac{3}{2})^{n-2} \times \frac{5}{2}.\]
   Or \(\frac{5}{2} = \frac{10}{4} \geq\, \frac{9}{4} = (\frac{3}{2})^2\). Donc \(F_{n+2} \geq\, (\frac{3}{2})^{n}\). Ainsi, \(F_n \geq\, (\frac{3}{2})^{n-2}\) pour tout \(n \geq\, 1\).

Point de méthode : dans une récurrence double, l’hérédité utilise deux rangs ; il faut donc vérifier deux valeurs initiales, sinon la preuve ne démarre pas.

Corrigé de l’exercice 10 : Récurrence forte

1. On a \(u_1 = u_0 = 1\), puis \(u_2 = u_0 + u_1 = 2\), et \(u_3 = 1 + 1 + 2 = 4\). Notons \(\mathcal{P}(n)\) : « \(u_n = 2^{n-1}\) », pour \(n \geq\, 1\). Initialisation : \(u_1 = 1 = 2^0\). Hérédité forte : soit \(n \geq\, 1\) tel que \(\mathcal{P}(1), \ldots, \mathcal{P}(n)\) sont vraies. Alors, grâce à la somme des termes d’une suite géométrique,
   \[u_{n+1} = u_0 + \sum_{k=1}^{n} 2^{k-1} = 1 + (2^n – 1) = 2^n.\]
   Par récurrence forte, \(u_n = 2^{n-1}\) pour tout \(n \geq\, 1\).
2. Notons \(\mathcal{P}(n)\) : « \(n\) est une somme de puissances de \(2\) deux à deux distinctes ». Initialisation : \(1 = 2^0\). Hérédité forte : soit \(n \geq\, 1\) tel que \(\mathcal{P}(1), \ldots, \mathcal{P}(n)\) sont vraies.
   • Si \(n + 1\) est pair, on écrit \(n + 1 = 2m\) avec \(1 \leq\, m \leq\, n\). Par hypothèse, \(m = 2^{j_1} + \cdots + 2^{j_r}\) avec des exposants distincts. Alors \(n + 1 = 2^{j_1 + 1} + \cdots + 2^{j_r + 1}\), et les exposants restent distincts.
   • Si \(n + 1\) est impair, alors \(n + 1 \geq\, 3\) et \(n + 1 = 2m + 1\) avec \(1 \leq\, m \leq\, n\). On décompose \(2m\) comme ci-dessus : tous ses exposants sont au moins égaux à \(1\). On ajoute \(2^0\), qui est donc distinct des autres termes.

   Par récurrence forte, tout entier \(n \geq\, 1\) est une somme de puissances de \(2\) distinctes.

3. On suit la démarche : \(45 = 1 + 2 \times 22\), puis \(22 = 2 \times 11\), \(11 = 1 + 2 \times 5\), \(5 = 1 + 2 \times 2\) et \(2 = 2^1\). En remontant : \(5 = 2^0 + 2^2\), \(11 = 2^0 + 2^1 + 2^3\), \(22 = 2^1 + 2^2 + 2^4\). Finalement, \(45 = 2^0 + 2^2 + 2^3 + 2^5 = 1 + 4 + 8 + 32\).

Corrigé de l’exercice 11 : Égalités et inclusions d’ensembles

1. Soit \(x \in E\). On raisonne par équivalences :
   \[\begin{aligned} x \in A \setminus (B \cup C) \Leftrightarrow x \in A \text{ et } x \notin B \text{ et } x \notin C \\ \Leftrightarrow (x \in A \text{ et } x \notin B) \text{ et } (x \in A \text{ et } x \notin C) \\ \Leftrightarrow x \in (A \setminus B) \cap (A \setminus C). \end{aligned}\]
   La première ligne utilise la loi de De Morgan : \(x \notin B \cup C\) équivaut à \(x \notin B\) et \(x \notin C\). Les deux ensembles sont donc égaux.
2. Soit \(x \in E\). Raisonnons par disjonction des cas. Si \(x \in A\), alors \(x\) appartient aux deux membres. Si \(x \notin A\), alors \(x \in A \cup (B \cap C)\) équivaut à \(x \in B\) et \(x \in C\). De même, \(x \in (A \cup B) \cap (A \cup C)\) équivaut alors à \(x \in B\) et \(x \in C\). Dans tous les cas, les appartenances coïncident : l’égalité est démontrée.
3. Si \(A = B\), alors \(A \cap B = A = A \cup B\). Réciproquement, supposons \(A \cap B = A \cup B\). Alors \(A \subset A \cup B = A \cap B \subset B\). De même, \(B \subset A \cup B = A \cap B \subset A\). Par double inclusion, \(A = B\).
4. Soit \(x \in B\). Si \(x \in A\), alors \(x \in A \cap B \subset A \cap C\), donc \(x \in C\). Sinon, \(x \in A \cup B \subset A \cup C\) et \(x \notin A\), donc \(x \in C\). Dans les deux cas, \(x \in C\) : ainsi, \(B \subset C\).

Remarquez qu’aucune des deux hypothèses de la question 4 ne suffit seule. Par exemple, avec \(A = E\), la première est toujours vraie, quel que soit \(B\).

Corrigé de l’exercice 12 : Ensemble des parties

1. On range les parties selon leur nombre d’éléments : \(\varnothing\), \(\{1\}\), \(\{2\}\), \(\{3\}\), \(\{1, 2\}\), \(\{1, 3\}\), \(\{2, 3\}\), \(\{1, 2, 3\}\). L’ensemble \(\mathcal{P}(E)\) compte \(8\) éléments.
2. Supposons \(\mathcal{P}(A) \subset \mathcal{P}(B)\). Comme \(A \subset A\), on a \(A \in \mathcal{P}(A)\), donc \(A \in \mathcal{P}(B)\), c’est-à-dire \(A \subset B\). Réciproquement, supposons \(A \subset B\), et soit \(X \in \mathcal{P}(A)\). Alors \(X \subset A \subset B\), donc \(X \in \mathcal{P}(B)\). L’équivalence est démontrée.
3. Soit \(X\) un ensemble. Alors \(X \in \mathcal{P}(A \cap B)\) équivaut à \(X \subset A \cap B\). Cela équivaut à \(X \subset A\) et \(X \subset B\), donc à \(X \in \mathcal{P}(A) \cap \mathcal{P}(B)\). Ainsi, \(\mathcal{P}(A \cap B) = \mathcal{P}(A) \cap \mathcal{P}(B)\).
4. Si \(X \subset A\) ou \(X \subset B\), alors \(X \subset A \cup B\). D’où l’inclusion. Prenons ensuite \(A = \{1\}\) et \(B = \{2\}\). La partie \(\{1, 2\}\) appartient à \(\mathcal{P}(A \cup B)\), mais ni à \(\mathcal{P}(A)\) ni à \(\mathcal{P}(B)\). L’inclusion est donc stricte dans cet exemple.

Corrigé de l’exercice 13 : Produit cartésien

1. Soit \((x, y) \in E \times F\). On a \((x, y) \in (A \times B) \cap (C \times D)\) si et seulement si \(x \in A\), \(y \in B\), \(x \in C\) et \(y \in D\). Autrement dit, \(x \in A \cap C\) et \(y \in B \cap D\). Ainsi, \((A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D)\).
2. Soit \((x, y) \in A \times B\). Alors \(x \in A \subset A \cup C\) et \(y \in B \subset B \cup D\). Le cas \((x, y) \in C \times D\) est identique. L’inclusion est démontrée.
3. Le couple \((0, 2)\) vérifie \(0 \in A \cup C\) et \(2 \in B \cup D\). Cependant, \((0, 2) \notin A \times B\) car \(2 \notin B\), et \((0, 2) \notin C \times D\) car \(0 \notin C\). L’inclusion est donc stricte. Sur la figure de l’énoncé, \((A \cup C) \times (B \cup D)\) contient aussi les deux carrés « croisés » \([0, 1] \times [2, 3]\) et \([2, 3] \times [0, 1]\).
4. Soit \((x, y) \in E \times F\). On a \((x, y) \notin A \times B\) si et seulement si \(\neg(x \in A \text{ et } y \in B)\), c’est-à-dire \(x \notin A\) ou \(y \notin B\). Cela équivaut à \((x, y) \in \overline{A} \times F\) ou \((x, y) \in E \times \overline{B}\). Le complémentaire de \(A \times B\) est donc \((\overline{A} \times F) \cup (E \times \overline{B})\).

Corrigé de l’exercice 14 : Fonctions indicatrices et différence symétrique

1. Les parties \(A \setminus B = A \cap \overline{B}\) et \(B \setminus A\) sont disjointes. Pour deux parties disjointes \(X\) et \(Y\), on a \(\mathbf{1}_X \mathbf{1}_Y = \mathbf{1}_{X \cap Y} = 0\), donc \(\mathbf{1}_{X \cup Y} = \mathbf{1}_X + \mathbf{1}_Y\). Par ailleurs, \(\mathbf{1}_{A \cap \overline{B}} = \mathbf{1}_A (1 – \mathbf{1}_B)\). Ainsi,
   \[\mathbf{1}_{A \Delta B} = \mathbf{1}_A – \mathbf{1}_A \mathbf{1}_B + \mathbf{1}_B – \mathbf{1}_A \mathbf{1}_B = \mathbf{1}_A + \mathbf{1}_B – 2\,\mathbf{1}_A \mathbf{1}_B.\]
   De plus, une indicatrice ne prend que les valeurs \(0\) et \(1\), donc \(\mathbf{1}_A^2 = \mathbf{1}_A\). En développant, \((\mathbf{1}_A – \mathbf{1}_B)^2 = \mathbf{1}_A – 2\,\mathbf{1}_A \mathbf{1}_B + \mathbf{1}_B\). Les deux formules sont démontrées.
2. On a \(A \Delta B = \varnothing\) si et seulement si \(\mathbf{1}_{A \Delta B}\) est nulle. D’après la question 1, cela équivaut à \((\mathbf{1}_A(x) – \mathbf{1}_B(x))^2 = 0\) pour tout \(x\), donc à \(\mathbf{1}_A = \mathbf{1}_B\). Ainsi, \(A \Delta B = \varnothing \Leftrightarrow A = B\).
3. Soit \(x \in E\), \(a = \mathbf{1}_A(x)\) et \(b = \mathbf{1}_B(x)\). On examine les quatre cas. Si \((a, b) = (0, 0)\), alors \(a + b – 2ab = 0\). Si \((a, b) = (1, 0)\) ou \((0, 1)\), on trouve \(1\). Si \((a, b) = (1, 1)\), on trouve \(0\). Or les restes de \(a + b\) modulo \(2\) valent respectivement \(0\), \(1\), \(1\) et \(0\). Donc \(\mathbf{1}_{A \Delta B}(x)\) est le reste de \(\mathbf{1}_A(x) + \mathbf{1}_B(x)\) modulo \(2\).
4. Soit \(x \in E\), et \(a\), \(b\), \(c\) les valeurs en \(x\) des indicatrices de \(A\), \(B\), \(C\). D’après la question 3, \(\mathbf{1}_{A \Delta B}(x) \equiv a + b \ [2]\). En appliquant encore la question 3, puis la compatibilité des congruences avec l’addition, \(\mathbf{1}_{(A \Delta B) \Delta C}(x) \equiv a + b + c \ [2]\). De même, \(\mathbf{1}_{A \Delta (B \Delta C)}(x) \equiv a + b + c \ [2]\). Or ces deux nombres valent \(0\) ou \(1\) : congrus modulo \(2\), ils sont égaux. Les indicatrices coïncident. Par conséquent, \((A \Delta B) \Delta C = A \Delta (B \Delta C)\).

Point de méthode : pour une égalité impliquant beaucoup d’opérations ensemblistes, passer aux indicatrices transforme la preuve en calcul sur \(0\) et \(1\).

Corrigé de l’exercice 15 : Recouvrements disjoints et partitions

1. (a) L’élément \(2\) appartient à \(\{1, 2\}\) et à \(\{2, 3\}\) : les parties ne sont pas disjointes. Ce n’est pas une partition. (b) Les trois parties sont non vides, deux à deux disjointes, et leur réunion vaut \(E\) : c’est une partition. (c) C’est un recouvrement disjoint, mais il contient \(\varnothing\). Seule la famille (b) est une partition de \(E\).
2. Chaque intervalle \([k, k+1[\) contient \(k\), il est donc non vide. Soit \(x \in \mathbb{R}\). Par définition de la partie entière, \(k = \lfloor x \rfloor\) est l’unique entier tel que \(k \leq\, x < k + 1\). Ainsi, \(x\) appartient à exactement un intervalle de la famille. La famille est une partition de \(\mathbb{R}\).
3. Soit \(x \in E\). Quatre cas s’excluent mutuellement. Si \(x \in A\) et \(x \in B\), alors \(x \in A \cap B\) seulement. Si \(x \in A\) et \(x \notin B\), alors \(x \in A \setminus B\) seulement. Si \(x \notin A\) et \(x \in B\), alors \(x \in B \setminus A\) seulement. Enfin, si \(x \notin A\) et \(x \notin B\), alors \(x \in \overline{A \cup B}\) seulement. Tout élément de \(E\) appartient donc à exactement une des quatre parties : c’est un recouvrement disjoint. Ce n’est pas toujours une partition : si \(A \subset B\), la partie \(A \setminus B\) est vide.

Corrigé de l’exercice 16 : Image directe et image réciproque

1. Si \(x \in [-1, 2]\), alors \(0 \leq\, x^2 \leq\, 4\). Réciproquement, tout \(y \in [0, 4]\) vaut \(f(\sqrt{y})\) avec \(\sqrt{y} \in [0, 2]\). Donc \(f([-1, 2]) = [0, 4]\). Comme \(f\) est croissante sur \([0, +\infty[\), \(f([1, 3]) = [1, 9]\). Ensuite, \(1 \leq\, x^2 \leq\, 4\) équivaut à \(1 \leq\, |x| \leq\, 2\). Par ailleurs, un carré n’est jamais négatif, et \(x^2 \leq\, 4\) équivaut à \(|x| \leq\, 2\). En résumé : \(f([-1, 2]) = [0, 4]\), \(f([1, 3]) = [1, 9]\), \(f^{-1}([1, 4]) = [-2, -1] \cup [1, 2]\), \(f^{-1}([-4, -1]) = \varnothing\) et \(f^{-1}([-1, 4]) = [-2, 2]\).
2. On a \(f(A) = [0, 4]\), donc \(f^{-1}(f(A)) = [-2, 2]\), qui contient strictement \(A = [0, 2]\). De même, \(f^{-1}(B) = [-2, 2]\), donc \(f(f^{-1}(B)) = [0, 4]\), strictement inclus dans \(B = [-1, 4]\). Ainsi, \(A \subsetneq f^{-1}(f(A))\) et \(f(f^{-1}(B)) \subsetneq B\). La première inclusion est stricte car \(f\) n’est pas injective ; la seconde, car \(f\) n’est pas surjective.
3. On a \(A_1 \cap A_2 = \{0\}\), donc \(f(A_1 \cap A_2) = \{0\}\). En revanche, \(f(A_1) = f(A_2) = [0, 1]\). Ainsi, \(f(A_1 \cap A_2) = \{0\} \subsetneq [0, 1] = f(A_1) \cap f(A_2)\).
4. Soit \(x \in A\). Alors \(g(x) \in g(A)\), donc \(x \in g^{-1}(g(A))\). Ensuite, soit \(y \in g(g^{-1}(B))\). Il existe \(x \in g^{-1}(B)\) tel que \(y = g(x)\). Or \(x \in g^{-1}(B)\) signifie \(g(x) \in B\). Donc \(A \subset g^{-1}(g(A))\) et \(g(g^{-1}(B)) \subset B\).

Corrigé de l’exercice 17 : Injections et surjections entre entiers

1. Si \(2n = 2n^{\prime}\), alors \(n = n^{\prime}\) : \(f\) est injective. En revanche, \(2n = 1\) n’a pas de solution entière, donc \(1\) n’a pas d’antécédent. Pour \(g\), tout \(m \in \mathbb{N}\) vérifie \(m = g(2m)\), donc \(g\) est surjective. Cependant, \(g(0) = g(1) = 0\). Ainsi, \(f\) est injective non surjective, et \(g\) est surjective non injective.
2. Pour tout \(n\), \(2n\) est pair, donc \(g(f(n)) = \frac{2n}{2} = n\). Ainsi, \(g \circ f = \mathrm{id}_{\mathbb{N}}\). En revanche, \(f(g(n)) = n\) si \(n\) est pair et \(f(g(n)) = n – 1\) si \(n\) est impair. Donc \(g \circ f = \mathrm{id}_{\mathbb{N}}\) mais \(f \circ g \neq \mathrm{id}_{\mathbb{N}}\), puisque \(f(g(1)) = 0\). Ni \(f\) ni \(g\) n’est bijective : une seule des deux égalités ne suffit pas.
3. On propose \(k : \mathbb{Z} \to \mathbb{N}\), avec \(k(m) = 2m\) si \(m \geq\, 0\) et \(k(m) = -2m – 1\) si \(m < 0\). Elle est à valeurs dans \(\mathbb{N}\), car \(-2m – 1 \geq\, 1\) pour \(m \leq\, -1\). Vérifions \(h \circ k = \mathrm{id}_{\mathbb{Z}}\). Si \(m \geq\, 0\), \(k(m)\) est pair et \(h(k(m)) = m\). Si \(m < 0\), \(k(m)\) est impair et \(h(k(m)) = -\frac{-2m – 1 + 1}{2} = m\). Vérifions \(k \circ h = \mathrm{id}_{\mathbb{N}}\). Si \(n\) est pair, \(h(n) = \frac{n}{2} \geq\, 0\) et \(k(h(n)) = n\). Si \(n\) est impair, \(h(n) = -\frac{n+1}{2} < 0\) et \(k(h(n)) = (n + 1) – 1 = n\). Donc \(h\) est bijective, et \(h^{-1}(m) = 2m\) si \(m \geq\, 0\), \(h^{-1}(m) = -2m – 1\) si \(m < 0\).

La figure ci-dessous représente \(h\) : les entiers pairs sont envoyés sur les entiers positifs, les impairs sur les entiers strictement négatifs, et chaque entier relatif reçoit exactement une flèche.

Corrigé de l’exercice 18 : Bijections explicites, restriction et prolongement

1. Pour \(x \neq 1\), l’égalité \(f(x) = 2\) donnerait \(2x + 1 = 2x – 2\), ce qui est impossible. Donc \(f\) est bien à valeurs dans \(\mathbb{R} \setminus \{2\}\). Soit \(y \neq 2\). Pour \(x \neq 1\),
   \[f(x) = y \Leftrightarrow 2x + 1 = y(x – 1) \Leftrightarrow x(2 – y) = -y – 1 \Leftrightarrow x = \frac{y + 1}{y – 2}.\]
   De plus, ce réel est différent de \(1\), car \(y + 1 = y – 2\) est impossible. Chaque \(y\) a donc exactement un antécédent. Ainsi, \(f\) est bijective et \(f^{-1}(y) = \dfrac{y + 1}{y – 2}\).
2. D’abord, \(|\varphi(x)| = \frac{|x|}{1 + |x|} < 1\), donc \(\varphi\) est à valeurs dans \(]-1, 1[\). Soit \(y \in ]-1, 1[\). Analyse : si \(\varphi(x) = y\), alors \(x\) et \(y\) sont de même signe, car \(1 + |x| > 0\). De plus, \(|y|(1 + |x|) = |x|\), donc \(|x|(1 – |y|) = |y|\), puis \(|x| = \frac{|y|}{1 – |y|}\). Avec le signe, \(x = \frac{y}{1 – |y|}\). Synthèse : pour ce réel, \(1 + |x| = \frac{1}{1 – |y|}\), donc \(\varphi(x) = \frac{y}{1 – |y|} \times (1 – |y|) = y\). Donc \(\varphi\) est bijective et \(\varphi^{-1}(y) = \dfrac{y}{1 – |y|}\).



3. On a \(u(0) = u(2) = 0\), donc \(u\) n’est pas injective. Par ailleurs, \(u(x) = (x – 1)^2 – 1 \geq\, -1\), donc \(-2\) n’a pas d’antécédent : \(u\) n’est pas surjective. Notons \(v\) l’application de \([1, +\infty[\) dans \([-1, +\infty[\) définie par \(v(x) = u(x)\) ; elle est bien définie car \(u \geq\, -1\). Soit \(y \geq\, -1\). Pour \(x \geq\, 1\), \(v(x) = y\) équivaut à \((x – 1)^2 = y + 1\). Comme \(x – 1 \geq\, 0\), cela équivaut à \(x – 1 = \sqrt{y + 1}\). Donc \(v\) est bijective et \(v^{-1}(y) = 1 + \sqrt{1 + y}\).
4. Analyse : soit \(g\) un prolongement impair de la racine carrée. Pour \(x \geq\, 0\), \(g(x) = \sqrt{x}\). Pour \(x < 0\), l’imparité donne \(g(x) = -g(-x) = -\sqrt{-x}\). Donc \(g\) est unique. Synthèse : définissons \(g\) ainsi. Pour \(x > 0\), \(g(-x) = -\sqrt{x} = -g(x)\). Pour \(x < 0\), \(g(-x) = \sqrt{-x} = -g(x)\). Enfin, \(g(0) = 0\). L’unique prolongement impair est \(g(x) = \sqrt{x}\) si \(x \geq\, 0\) et \(g(x) = -\sqrt{-x}\) si \(x < 0\).

Corrigé de l’exercice 19 : Composition et réciproque d’une composée

1. Soit \(x, x^{\prime} \in E\) tels que \(f(x) = f(x^{\prime})\). En appliquant \(g\), on obtient \((g \circ f)(x) = (g \circ f)(x^{\prime})\). L’injectivité de \(g \circ f\) donne alors \(x = x^{\prime}\). Donc \(f\) est injective.
2. Soit \(z \in G\). Par surjectivité de \(g \circ f\), il existe \(x \in E\) tel que \(z = g(f(x))\). Ainsi, \(y = f(x)\) est un antécédent de \(z\) par \(g\). Donc \(g\) est surjective.
3. Prenons \(E = G = \{0\}\), \(F = \{0, 1\}\), \(f(0) = 0\), et \(g\) constante égale à \(0\). Alors \(g \circ f\) est l’identité de \(\{0\}\), donc elle est bijective. Cependant, \(f\) n’est pas surjective, car \(1\) n’a pas d’antécédent. De plus, \(g\) n’est pas injective, car \(g(0) = g(1)\). Cet exemple répond à la question.
4. Par associativité, \(u \circ (u \circ u) = (u \circ u) \circ u = u \circ u \circ u = \mathrm{id}_E\). L’application \(v = u \circ u\) vérifie donc \(u \circ v = \mathrm{id}_E\) et \(v \circ u = \mathrm{id}_E\). D’après le théorème de caractérisation des bijections, \(u\) est bijective et \(u^{-1} = u \circ u\).
5. D’une part, \((g \circ f)(x) = (2x + 1)^3\). Comme \(t \mapsto t^3\) est une bijection de \(\mathbb{R}\) sur \(\mathbb{R}\), l’équation \((2x + 1)^3 = y\) équivaut à \(2x + 1 = \sqrt[3]{y}\), donc à \(x = \frac{\sqrt[3]{y} – 1}{2}\). D’autre part, \(f^{-1}(y) = \frac{y – 1}{2}\) et \(g^{-1}(y) = \sqrt[3]{y}\). Ainsi, \((f^{-1} \circ g^{-1})(y) = \frac{\sqrt[3]{y} – 1}{2}\). Les deux méthodes donnent \((g \circ f)^{-1}(y) = \dfrac{\sqrt[3]{y} – 1}{2}\). L’ordre compte : \(g^{-1} \circ f^{-1}\) donnerait \(\sqrt[3]{\frac{y – 1}{2}}\), qui est différent.

Corrigé de l’exercice 20 : Caractérisations par les images

1. Supposons \(f\) injective et soit \(A \subset E\). L’inclusion \(A \subset f^{-1}(f(A))\) est toujours vraie (exercice 16). Soit \(x \in f^{-1}(f(A))\). Alors \(f(x) \in f(A)\) : il existe \(a \in A\) tel que \(f(x) = f(a)\). Par injectivité, \(x = a \in A\). Réciproquement, supposons la propriété vraie pour toute partie. Soit \(x, x^{\prime}\) tels que \(f(x) = f(x^{\prime})\). Avec \(A = \{x\}\), on obtient \(x^{\prime} \in f^{-1}(\{f(x)\}) = f^{-1}(f(A)) = \{x\}\). Donc \(x^{\prime} = x\), et l’équivalence est démontrée.
2. Supposons \(f\) surjective et soit \(B \subset F\). L’inclusion \(f(f^{-1}(B)) \subset B\) est toujours vraie. Soit \(y \in B\). Par surjectivité, il existe \(x\) tel que \(y = f(x)\). Alors \(x \in f^{-1}(B)\), donc \(y \in f(f^{-1}(B))\). Réciproquement, prenons \(B = F\) : on a \(f^{-1}(F) = E\), donc \(f(E) = F\). Ainsi, \(f\) est surjective si et seulement si \(f(f^{-1}(B)) = B\) pour tout \(B\).
3. D’abord, \(A \cap A^{\prime} \subset A\) entraîne \(f(A \cap A^{\prime}) \subset f(A)\), et de même pour \(A^{\prime}\). L’inclusion \(f(A \cap A^{\prime}) \subset f(A) \cap f(A^{\prime})\) est donc toujours vraie. Supposons \(f\) injective. Soit \(y \in f(A) \cap f(A^{\prime})\) : \(y = f(a) = f(a^{\prime})\) avec \(a \in A\) et \(a^{\prime} \in A^{\prime}\). Par injectivité, \(a = a^{\prime} \in A \cap A^{\prime}\), donc \(y \in f(A \cap A^{\prime})\). Réciproquement, supposons l’égalité toujours vraie, et soit \(f(x) = f(x^{\prime})\). Avec \(A = \{x\}\) et \(A^{\prime} = \{x^{\prime}\}\), on a \(f(x) \in f(A) \cap f(A^{\prime}) = f(\{x\} \cap \{x^{\prime}\})\). Ainsi, \(\{x\} \cap \{x^{\prime}\}\) est non vide. Donc \(x = x^{\prime}\), et \(f\) est injective.

Point de méthode : pour exploiter une propriété vraie « pour toute partie », on la teste sur des singletons ou sur l’ensemble tout entier.

Corrigé de l’exercice 21 : Relation d’équivalence et cercles

1. Posons \(N(x, y) = x^2 + y^2\). La relation s’écrit \(N(x, y) = N(x^{\prime}, y^{\prime})\). Elle hérite donc des propriétés de l’égalité. Elle est réflexive, car \(N(x, y) = N(x, y)\). Elle est symétrique, car l’égalité l’est. Enfin, elle est transitive : si \(N(p) = N(q)\) et \(N(q) = N(r)\), alors \(N(p) = N(r)\). C’est une relation d’équivalence.
2. Soit \(r = \sqrt{a^2 + b^2}\). La classe de \((a, b)\) est l’ensemble des points \((x, y)\) tels que \(x^2 + y^2 = r^2\). C’est le cercle de centre \(O\) et de rayon \(r\) si \(r > 0\), et la classe de \((0, 0)\) est \(\{(0, 0)\}\). Pour \((1, 2)\), on a \(r = \sqrt{5}\). Par exemple, \((2, 1)\), \((-2, 1)\) et \((2, -1)\) sont dans la classe, car leurs coordonnées au carré ont pour somme \(5\).



3. Notons \(\Phi\) l’application qui à la classe de \((a, b)\) associe \(\sqrt{a^2 + b^2}\). Elle est bien définie : deux points de la même classe ont la même valeur de \(N\), donc le même rayon. Elle est injective : deux classes de même rayon \(r\) contiennent des points vérifiant \(N = r^2\), donc elles sont égales. Elle est surjective : tout \(r \geq\, 0\) est l’image de la classe de \((r, 0)\). Ainsi, \(\Phi\) est une bijection de l’ensemble des classes sur \([0, +\infty[\).
4. La relation \(\mathcal{S}\) est réflexive, car \(|x – x| = 0 \leq\, 1\), et symétrique, car \(|x – y| = |y – x|\). En revanche, \(0 \mathcal{S} 1\) et \(1 \mathcal{S} 2\), mais \(|0 – 2| = 2 > 1\). \(\mathcal{S}\) n’est pas transitive, donc ce n’est pas une relation d’équivalence.

Corrigé de l’exercice 22 : Congruences et sommes de deux carrés

1. Réflexivité : \(n\) divise \(a – a = 0\). Symétrie : si \(b – a = kn\), alors \(a – b = (-k)n\). Transitivité : si \(b – a = kn\) et \(c – b = ln\), alors \(c – a = (k + l)n\). C’est donc une relation d’équivalence. Pour \(n = 4\), la division euclidienne écrit tout entier \(a = 4q + r\) avec \(r \in \{0, 1, 2, 3\}\), d’où \(a \equiv r \ [4]\). De plus, deux restes distincts \(r\) et \(r^{\prime}\) de \(\{0, 1, 2, 3\}\) vérifient \(0 < |r – r^{\prime}| < 4\) : ils ne sont pas congrus. Il y a exactement quatre classes : \(4\mathbb{Z}\), \(1 + 4\mathbb{Z}\), \(2 + 4\mathbb{Z}\) et \(3 + 4\mathbb{Z}\).
2. Écrivons \(b – a = kn\) et \(d – c = ln\). D’une part, \((b + d) – (a + c) = (k + l)n\). D’autre part,
   \[bd – ac = b(d – c) + c(b – a) = (bl + ck)n.\]
   Donc \(a + c \equiv b + d \ [n]\) et \(ac \equiv bd \ [n]\).
3. Soit \(a \in \mathbb{Z}\) et \(r \in \{0, 1, 2, 3\}\) tel que \(a \equiv r \ [4]\). Par compatibilité avec le produit, \(a^2 \equiv r^2 \ [4]\). Or \(0^2 = 0\), \(1^2 = 1\), \(2^2 = 4 \equiv 0\) et \(3^2 = 9 \equiv 1\). Ainsi, \(a^2 \equiv 0\) ou \(a^2 \equiv 1 \ [4]\).
4. Si \(2027 = x^2 + y^2\), alors \(x^2 + y^2\) serait congru à \(0 + 0\), \(0 + 1\) ou \(1 + 1\) modulo \(4\), c’est-à-dire à \(0\), \(1\) ou \(2\). Or \(2027 = 4 \times 506 + 3\), donc \(2027 \equiv 3 \ [4]\). Par conséquent, \(2027\) n’est pas la somme de deux carrés d’entiers.
5. On a \(10 – 1 = 9\), donc \(10 \equiv 1 \ [9]\). Par récurrence et compatibilité avec le produit, \(10^k \equiv 1 \ [9]\) pour tout \(k \in \mathbb{N}\). Soit \(N = \sum_{k=0}^{p} c_k 10^k\) l’écriture décimale d’un entier. Par compatibilité, \(N \equiv \sum_{k=0}^{p} c_k \ [9]\). Pour \(2027\), la somme des chiffres vaut \(11\), et \(11 \equiv 2 \ [9]\). Ainsi, \(2027 \equiv 2 \ [9]\), ce que confirme \(2027 = 9 \times 225 + 2\).

Corrigé de l’exercice 23 : Classes modulo Z et partie entière

1. On a \(x – x = 0 \in \mathbb{Z}\). Ensuite, si \(x – y \in \mathbb{Z}\), alors \(y – x = -(x – y) \in \mathbb{Z}\). Enfin, si \(x – y\) et \(y – z\) sont entiers, leur somme \(x – z\) l’est aussi. Donc \(\sim\) est une relation d’équivalence, et la classe de \(a\) est \(\{a + k \mid k \in \mathbb{Z}\}\).
2. Analyse : soit \(t\) un élément de la classe de \(x\) dans \([0, 1[\). Alors \(t = x + k\) avec \(k \in \mathbb{Z}\), et \(0 \leq\, x + k < 1\). Ainsi, \(-k \leq\, x < -k + 1\), donc \(-k = \lfloor x \rfloor\) par unicité de la partie entière. Par conséquent, \(t = x – \lfloor x \rfloor\) : il y a au plus un tel élément. Synthèse : posons \(t = x – \lfloor x \rfloor\). D’une part, \(x – t = \lfloor x \rfloor \in \mathbb{Z}\), donc \(t \sim x\). D’autre part, \(\lfloor x \rfloor \leq\, x < \lfloor x \rfloor + 1\) donne \(0 \leq\, t < 1\). Chaque classe contient exactement un élément de \([0, 1[\) : pour la classe de \(x\), c’est \(x – \lfloor x \rfloor\).



3. Notons \(\psi(a) = \mathrm{cl}(a)\) pour \(a \in [0, 1[\). Soit \(C\) une classe et \(x \in C\). Le réel \(a = x – \lfloor x \rfloor\) appartient à \([0, 1[\) et à \(C\), donc \(\psi(a) = C\) : \(\psi\) est surjective. Ensuite, si \(\psi(a) = \psi(b)\), alors \(a\) et \(b\) sont deux éléments de \([0, 1[\) dans la même classe. D’après la question 2, \(a = b\). Ainsi, \(\psi\) est une bijection de \([0, 1[\) sur l’ensemble des classes. La figure ci-dessus l’illustre : la droite horizontale d’ordonnée \(0{,}4\) coupe la dent de scie exactement aux points de la classe de \(0{,}4\).
4. Supposons \(f\) compatible avec \(\sim\). Comme \(x \sim x + 1\), on a \(f(x + 1) = f(x)\) : \(f\) est \(1\)-périodique. Réciproquement, soit \(f\) une fonction \(1\)-périodique. Par récurrence, \(f(x + k) = f(x)\) pour tout \(k \in \mathbb{N}\). Pour \(k \in \mathbb{N}\), on a aussi \(f(x) = f((x – k) + k) = f(x – k)\). Donc \(f(x + k) = f(x)\) pour tout \(k \in \mathbb{Z}\). Si \(x \sim y\), alors \(y = x + k\) avec \(k\) entier, et \(f(y) = f(x)\). Les fonctions cherchées sont exactement les fonctions \(1\)-périodiques, par exemple \(x \mapsto \cos(2\pi x)\) ou \(x \mapsto x – \lfloor x \rfloor\).

Corrigé de l’exercice 24 : Ordre de divisibilité et ordres sur le plan

1. Réflexivité : \(a = 1 \times a\), donc \(a\) divise \(a\). Transitivité : si \(b = ka\) et \(c = lb\), alors \(c = (lk)a\). Antisymétrie : si \(b = ka\) et \(a = lb\) avec \(a, b \in \mathbb{N}^{*}\), alors \(a = lka\), donc \(lk = 1\). Comme \(k\) et \(l\) sont des entiers naturels, \(k = l = 1\) et \(a = b\). C’est donc une relation d’ordre. Elle n’est pas totale : \(2\) ne divise pas \(3\) et \(3\) ne divise pas \(2\). Sur \(\mathbb{Z}\), ce n’est plus une relation d’ordre, car \(2\) divise \(-2\) et \(-2\) divise \(2\) alors que \(2 \neq -2\).
2. On a \(D = \{1, 2, 3, 4, 6, 12\}\). Le schéma ci-dessous relie deux diviseurs quand l’un s’obtient à partir de l’autre en multipliant par un nombre premier. L’entier \(1\) divise tous les éléments de \(D\), et chaque élément de \(D\) divise \(12\). Le plus petit élément de \(D\) est \(1\) et le plus grand est \(12\). En revanche, \(2\) et \(3\), ou \(4\) et \(6\), ne sont pas comparables.



3. Réflexivité : \(x \leq\, x\) et \(y \leq\, y\). Antisymétrie : si \(x \leq\, x^{\prime} \leq\, x\) et \(y \leq\, y^{\prime} \leq\, y\), alors \(x = x^{\prime}\) et \(y = y^{\prime}\). Transitivité : elle découle de celle de \(\leq\,\) sur chaque coordonnée. C’est donc un ordre. Cependant, \((0, 1)\) et \((1, 0)\) ne sont pas comparables : on n’a ni \(0 \leq\, 1\) et \(1 \leq\, 0\), ni l’inverse. C’est une relation d’ordre partiel.
4. Réflexivité : \(x = x\) et \(y \leq\, y\). Antisymétrie : supposons \((x, y) \trianglelefteq (x^{\prime}, y^{\prime})\) et \((x^{\prime}, y^{\prime}) \trianglelefteq (x, y)\). Si l’on avait \(x < x^{\prime}\), la seconde relation exigerait \(x^{\prime} \leq\, x\), ce qui est impossible. Donc \(x = x^{\prime}\), puis \(y \leq\, y^{\prime}\) et \(y^{\prime} \leq\, y\), d’où \(y = y^{\prime}\). Transitivité : supposons \((x, y) \trianglelefteq (x^{\prime}, y^{\prime}) \trianglelefteq (x^{\prime\prime}, y^{\prime\prime})\). On a \(x \leq\, x^{\prime} \leq\, x^{\prime\prime}\). Si l’une des deux inégalités est stricte, alors \(x < x^{\prime\prime}\). Sinon, \(x = x^{\prime} = x^{\prime\prime}\) et \(y \leq\, y^{\prime} \leq\, y^{\prime\prime}\). Totalité : si \(x \neq x^{\prime}\), le couple de plus petite abscisse est inférieur à l’autre ; si \(x = x^{\prime}\), on compare \(y\) et \(y^{\prime}\), ce qui est toujours possible dans \(\mathbb{R}\). L’ordre lexicographique est un ordre total sur \(\mathbb{R}^2\).

Corrigé de l’exercice 25 : Problème sur les parties d’un ensemble et le théorème de Cantor

Partie A.

1. Soit \(A, B \subset E\) tels que \(\mathbf{1}_A = \mathbf{1}_B\). Alors \(A = \{x \in E \mid \mathbf{1}_A(x) = 1\} = \{x \in E \mid \mathbf{1}_B(x) = 1\} = B\). Donc \(\Phi\) est injective.
2. Soit \(x \in E\). On a \(\mathbf{1}_{A_u}(x) = 1\) si et seulement si \(x \in A_u\), c’est-à-dire \(u(x) = 1\). Sinon, \(\mathbf{1}_{A_u}(x) = 0\) et \(u(x) = 0\), puisque \(u\) est à valeurs dans \(\{0, 1\}\). Ainsi, \(\mathbf{1}_{A_u} = u\), donc \(u = \Phi(A_u)\) : \(\Phi\) est surjective. Par conséquent, \(\Phi\) est bijective et \(\Phi^{-1}(u) = u^{-1}(\{1\})\).

Partie B.

1. Notons \(\mathcal{P}_a\) l’ensemble des parties de \(E^{\prime}\) contenant \(a\), et \(\sigma(A) = A \cup \{a\}\). Pour \(A \subset E\), \(\sigma(A)\) est une partie de \(E^{\prime}\) qui contient \(a\). Injectivité : comme \(a \notin A\), on a \(A = \sigma(A) \setminus \{a\}\). Donc \(\sigma(A) = \sigma(A^{\prime})\) entraîne \(A = A^{\prime}\). Surjectivité : si \(X \in \mathcal{P}_a\), alors \(X \setminus \{a\} \subset E\) et \(\sigma(X \setminus \{a\}) = X\). Ainsi, \(\sigma\) est une bijection de \(\mathcal{P}(E)\) sur \(\mathcal{P}_a\).
2. Notons \(\mathcal{H}(n)\) : « tout ensemble à \(n\) éléments possède \(2^n\) parties ». Initialisation : l’ensemble vide a une seule partie, lui-même, et \(2^0 = 1\). Hérédité : soit \(E^{\prime}\) un ensemble à \(n + 1\) éléments, \(a \in E^{\prime}\) et \(E = E^{\prime} \setminus \{a\}\), qui a \(n\) éléments. Les parties de \(E^{\prime}\) se répartissent en deux groupes disjoints. Celles qui ne contiennent pas \(a\) sont les parties de \(E\) : il y en a \(2^n\). Celles qui contiennent \(a\) sont en bijection avec \(\mathcal{P}(E)\) d’après la question 1 : il y en a aussi \(2^n\). Au total, \(E^{\prime}\) a \(2^{n+1}\) parties, et la propriété est démontrée par récurrence.

Partie C.

1. Si \(\{x\} = \{x^{\prime}\}\), alors \(x \in \{x^{\prime}\}\), donc \(x = x^{\prime}\). L’application \(x \mapsto \{x\}\) est injective.
2. Supposons par l’absurde qu’il existe \(a \in E\) tel que \(f(a) = D\). Raisonnons par disjonction des cas. Si \(a \in D\), alors, par définition de \(D\), \(a \notin f(a) = D\) : contradiction. Si \(a \notin D\), alors \(a \notin f(a)\), donc \(a \in D\) par définition : contradiction. Ainsi, \(D\) n’a aucun antécédent par \(f\).
3. La partie \(D\) appartient à \(\mathcal{P}(E)\) et n’est pas atteinte par \(f\). Ceci vaut pour toute application \(f\). Il n’existe donc aucune surjection de \(E\) sur \(\mathcal{P}(E)\) : c’est le théorème de Cantor.
4. Supposons par l’absurde qu’il existe une surjection \(s : \mathbb{N} \to \{0, 1\}^{\mathbb{N}}\). D’après la partie A, \(\Phi^{-1}\) est une bijection de \(\{0, 1\}^{\mathbb{N}}\) sur \(\mathcal{P}(\mathbb{N})\). La composée \(\Phi^{-1} \circ s\) est alors une surjection de \(\mathbb{N}\) sur \(\mathcal{P}(\mathbb{N})\), ce qui contredit la question 3. Il n’existe aucune surjection de \(\mathbb{N}\) sur l’ensemble des suites à valeurs dans \(\{0, 1\}\).

Point de méthode : l’ensemble \(D\) est construit pour différer de chaque \(f(x)\) en l’élément \(x\) lui-même ; c’est l’argument diagonal, qui revient souvent aux concours.

Revenir aux énoncés des exercices

Pour aller plus loin en maths sup

• Le cours : logique, ensembles et applications, cours de maths sup
• Les énoncés : exercices de maths sup sur logique, ensembles et applications
• Chapitre suivant : Calculs algébriques : sommes, produits, inégalités
• Tester vos connaissances : QCM de maths sup par chapitre
• Le sommaire : tous les chapitres de maths sup et les chapitres de maths spé