Logique, ensembles, applications et relations (Exercices) · Révisions prépa · Ridami

Algèbre · 1re année

Logique, ensembles, applications et relations

Application du cours4 points

1. Tables de vérité, négations et quantificateurs

Dans tout l'exercice, $P$ , $Q$ , $R$ sont des assertions et $f$ une fonction de $ℝ$ dans $ℝ$ .

À l'aide de tables de vérité : (a) montrer que $[(P \Rightarrow Q) et (Q \Rightarrow R)] \Rightarrow (P \Rightarrow R)$ est une tautologie ; (b) montrer que $[P \Rightarrow (Q et R)] ⟺ [(P \Rightarrow Q) et (P \Rightarrow R)]$ est une tautologie ; (c) montrer que $(P \Rightarrow Q) \Rightarrow (Q \Rightarrow P)$ n'est pas une tautologie.
Traduire avec des quantificateurs, puis écrire la négation : (a) $f$ est périodique ; (b) $f$ est constante ; (c) $f$ s'annule au plus une fois ; (d) la suite réelle $(u_{n})$ est stationnaire.
Répondre par vrai ou faux en justifiant : (a) $\forall x \in ℝ, \exists y \in ℝ, x = y^{2} - 2$ ; (b) $\exists y \in ℝ, \forall x \in ℝ, x y = x$ ; (c) $\forall n \in ℕ, \exists m \in ℕ, n < m \leq n + 2 et m impair$ ; (d) $\exists m \in ℕ, \forall n \in ℕ, n \leq m$ ; (e) $\forall x \in ℝ, \forall y \in ℝ, (x^{2} = y^{2} \Rightarrow x = y)$ .

Voir le corrigé

1. (a) Notons $T$ l'assertion. Rappelons que $A \Rightarrow B$ n'est fausse que si $A$ est vraie et $B$ fausse.

$P$	$Q$	$R$	$P \Rightarrow Q$	$Q \Rightarrow R$	les deux	$P \Rightarrow R$	$T$
V	V	V	V	V	V	V	V
V	V	F	V	F	F	F	V
V	F	V	F	V	F	V	V
V	F	F	F	V	F	F	V
F	V	V	V	V	V	V	V
F	V	F	V	F	F	V	V
F	F	V	V	V	V	V	V
F	F	F	V	V	V	V	V

La dernière colonne ne contient que V : $T est une tautologie$ (transitivité de l'implication, fiche §2).

(b) Les deux membres ne sont faux que lorsque $P$ est vraie et que l'une au moins de $Q$ , $R$ est fausse :

$P$	$Q$	$R$	$P \Rightarrow (Q et R)$	$P \Rightarrow Q$	$P \Rightarrow R$	$(P \Rightarrow Q) et (P \Rightarrow R)$
V	V	V	V	V	V	V
V	V	F	F	V	F	F
V	F	V	F	F	V	F
V	F	F	F	F	F	F
F	⋅	⋅	V	V	V	V

(Quand $P$ est fausse, toutes les implications sont vraies, quelles que soient $Q$ et $R$ .) Les deux colonnes coïncident : l'équivalence est une tautologie. On retient : pour montrer « $P \Rightarrow (Q$ et $R)$ », on peut montrer séparément $P \Rightarrow Q$ et $P \Rightarrow R$ .

(c) Prenons $P$ fausse et $Q$ vraie : $P \Rightarrow Q$ est vraie, $Q \Rightarrow P$ est fausse, donc $(P \Rightarrow Q) \Rightarrow (Q \Rightarrow P)$ est fausse. Une ligne fausse suffit : ce n'est pas une tautologie. Une implication vraie peut avoir une réciproque fausse.

2. (a) $f$ est périodique : $\exists T > 0, \forall x \in ℝ, f (x + T) = f (x)$ . Négation : $\forall T > 0, \exists x \in ℝ, f (x + T) \neq f (x)$ .

(b) $f$ est constante : $\exists c \in ℝ, \forall x \in ℝ, f (x) = c$ (ou $\forall x, y \in ℝ, f (x) = f (y)$ ). Négation : $\forall c \in ℝ, \exists x \in ℝ, f (x) \neq c$ (ou $\exists x, y \in ℝ, f (x) \neq f (y)$ ).

(c) $f$ s'annule au plus une fois : $\forall x, y \in ℝ, (f (x) = 0 et f (y) = 0) \Rightarrow x = y$ . Négation (fiche §2 : non $(A \Rightarrow B) \equiv A$ et non $B$ ) : $\exists x, y \in ℝ, f (x) = 0, f (y) = 0 et x \neq y$ ; autrement dit $f$ s'annule en deux points distincts au moins.

(d) $(u_{n})$ est stationnaire : $\exists N \in ℕ, \forall n \geq N, u_{n} = u_{N}$ . Négation : $\forall N \in ℕ, \exists n \geq N, u_{n} \neq u_{N}$ .

3. (a) Faux. Négation : $\exists x \in ℝ, \forall y \in ℝ, x \neq y^{2} - 2$ . Le réel $x = - 3$ convient : $y^{2} - 2 = - 3$ imposerait $y^{2} = - 1 < 0$ .

(b) Vrai : $y = 1$ convient, car $x \cdot 1 = x$ pour tout $x$ . Ici le même $y$ sert pour tous les $x$ .

(c) Vrai. Soit $n \in ℕ$ . Parmi les deux entiers consécutifs $n + 1$ et $n + 2$ , l'un est impair (disjonction de cas selon la parité de $n$ : si $n$ est pair, $m = n + 1$ ; sinon $m = n + 2$ ). Cet $m$ vérifie $n < m \leq n + 2$ .

(d) Faux. Négation : $\forall m \in ℕ, \exists n \in ℕ, n > m$ ; il suffit de prendre $n = m + 1$ . ( $ℕ$ n'a pas de plus grand élément.)

(e) Faux. Contre-exemple : $x = 1$ , $y = - 1$ : $x^{2} = y^{2} = 1$ mais $x \neq y$ . L'assertion devient vraie si l'on se restreint à $x, y \in ℝ_{+}$ .

Après avoir comparé avec le corrigé :

Application du cours6 points

2. Choisir son raisonnement

(Contraposée.) Soient $a, b \in ℝ$ . Montrer que : $(\forall ε > 0, a \leq b + ε) \Rightarrow a \leq b$ .
(Absurde.) (a) Montrer qu'il n'existe aucun couple $(a, b) \in ℤ^{2}$ tel que $a^{2} - 4 b = 2$ . (b) Montrer que le réel $\frac{\ln 3}{\ln 2}$ est irrationnel.
(Disjonction de cas.) Montrer que, pour tout $n \in ℤ$ , l'entier $n (n^{2} + 2)$ est divisible par $3$ .
(Contre-exemple.) L'assertion « pour tout $n \in ℕ$ , l'entier $n^{2} + n + 41$ est premier » est-elle vraie ?
(Analyse-synthèse.) Déterminer toutes les fonctions $f : ℝ \to ℝ$ telles que $\forall x, y \in ℝ, f (x) f (y) - f (x y) = x + y .$

Voir le corrigé

1. On montre la contraposée : $a > b \Rightarrow \exists ε > 0, a > b + ε$ . Supposons $a > b$ et posons $ε = \frac{a - b}{2} > 0$ . Alors $b + ε = \frac{a + b}{2}$ et $a - (b + ε) = \frac{a - b}{2} > 0$ , donc $a > b + ε$ . La contraposée est prouvée, donc l'implication aussi : $(\forall ε > 0, a \leq b + ε) \Rightarrow a \leq b$ . (Cet argument resservira constamment en Analyse.)

2. (a) Raisonnons par l'absurde : supposons $a^{2} - 4 b = 2$ avec $a, b \in ℤ$ . Alors $a^{2} = 2 (2 b + 1)$ est pair, donc $a$ est pair (fiche §5 : si $a$ était impair, $a^{2}$ serait impair). Écrivons $a = 2 c$ avec $c \in ℤ$ : $4 c^{2} - 4 b = 2$ , soit $2 (c^{2} - b) = 1$ . Le membre de gauche est pair, $1$ est impair : c'est absurde. $Aucun couple ne convient.$

(b) On a $\ln 3 > 0$ et $\ln 2 > 0$ , donc $\frac{\ln 3}{\ln 2} > 0$ . Supposons par l'absurde $\frac{\ln 3}{\ln 2} = \frac{p}{q}$ avec $p, q \in ℕ^{*}$ . Alors $q \ln 3 = p \ln 2$ , c'est-à-dire $\ln (3^{q}) = \ln (2^{p})$ , d'où $3^{q} = 2^{p}$ par injectivité de $\ln$ sur $] 0, + \infty [$ . Or $3^{q}$ est impair (produit de nombres impairs) et $2^{p}$ est pair car $p \geq 1$ : contradiction. $\frac{\ln 3}{\ln 2} \notin ℚ$ .

3. Tout entier $n$ s'écrit $3 k$ , $3 k + 1$ ou $3 k + 2$ avec $k \in ℤ$ (division euclidienne par $3$ ).

Si $n = 3 k$ : $n (n^{2} + 2) = 3 k (n^{2} + 2)$ est un multiple de $3$ .
Si $n = 3 k + 1$ : $n^{2} + 2 = 9 k^{2} + 6 k + 3 = 3 (3 k^{2} + 2 k + 1)$ , multiple de $3$ .
Si $n = 3 k + 2$ : $n^{2} + 2 = 9 k^{2} + 12 k + 6 = 3 (3 k^{2} + 4 k + 2)$ , multiple de $3$ .

Dans les trois cas, $3 ∣ n (n^{2} + 2)$ .

4. Non. Pour $n = 40$ : $40^{2} + 40 + 41 = 1600 + 81 = 1681 = 41^{2}$ , qui n'est pas premier. Un seul contre-exemple suffit à réfuter un « pour tout », même si l'assertion est vraie pour $n = 0, 1, \dots, 39$ (on peut aussi prendre $n = 41$ : $41^{2} + 41 + 41 = 41 \times 43$ ).

5. Analyse. Soit $f$ une solution.

Avec $x = y = 0$ : $f (0)^{2} - f (0) = 0$ , donc $f (0) \in {0, 1}$ .
Avec $y = 0$ et $x$ quelconque : $f (x) f (0) - f (0) = x$ , c'est-à-dire $f (0) (f (x) - 1) = x$ . Si $f (0) = 0$ , on obtient $0 = x$ pour tout réel $x$ , ce qui est faux pour $x = 1$ . Donc $f (0) = 1$ , et alors $f (x) - 1 = x$ .

Nécessairement : $f (x) = x + 1$ pour tout $x \in ℝ$ . Il y a donc au plus une solution.

Synthèse. Soit $f : x \mapsto x + 1$ . Pour tous $x, y$ : $f (x) f (y) - f (x y) = (x + 1) (y + 1) - (x y + 1) = x + y$ . Elle convient.

Conclusion : $une seule solution, f (x) = x + 1$ . Sans la synthèse, on aurait seulement prouvé que toute solution est de cette forme, pas qu'il en existe une.

Après avoir comparé avec le corrigé :

Application du cours5 points

3. Quatre récurrences

Montrer que, pour tout $n \in ℕ$ , $7$ divise $3^{2 n + 1} + 2^{n + 2}$ .
(a) Prouver l'inégalité $3^{n} \geq n^{3}$ pour chaque entier $n \geq 3$ . (b) L'hérédité de la question (a) est-elle valable à partir de $n = 2$ ? L'inégalité est-elle vraie pour $n \in {0, 1, 2}$ ?
Soit $(u_{n})$ la suite définie par $u_{0} = 2$ , $u_{1} = 3$ et $u_{n + 2} = 3 u_{n + 1} - 2 u_{n}$ pour tout $n \in ℕ$ . Montrer que $u_{n} = 2^{n} + 1$ pour tout $n \in ℕ$ .
Soit $(v_{n})$ la suite définie par $v_{0} = 1$ et, pour tout $n \in ℕ$ , $v_{n + 1} = v_{0} + v_{1} + \dots + v_{n}$ . (a) Calculer $v_{1}$ , $v_{2}$ , $v_{3}$ , $v_{4}$ et conjecturer une formule pour $n \geq 1$ . (b) Démontrer la conjecture par récurrence forte. (c) Retrouver le résultat par une récurrence simple, en comparant $v_{n + 1}$ et $v_{n}$ .

Voir le corrigé

1. Soit $P (n)$ : « $7 ∣ 3^{2 n + 1} + 2^{n + 2}$ ».

Initialisation : $3^{1} + 2^{2} = 7$ , donc $P (0)$ est vraie.
Hérédité : soit $n \in ℕ$ tel que $P (n)$ ; écrivons $3^{2 n + 1} + 2^{n + 2} = 7 k$ avec $k \in ℤ$ . Alors $3^{2 n + 3} + 2^{n + 3} = 9 \cdot 3^{2 n + 1} + 2 \cdot 2^{n + 2} = 9 (3^{2 n + 1} + 2^{n + 2}) - 7 \cdot 2^{n + 2} = 7 (9 k - 2^{n + 2}),$ donc $P (n + 1)$ est vraie.

Par récurrence, $7 ∣ 3^{2 n + 1} + 2^{n + 2} pour tout n \in ℕ$ .

2. (a) Soit $P (n)$ : « $3^{n} \geq n^{3}$ », pour $n \geq 3$ .

Initialisation : $3^{3} = 27 = 3^{3}$ , donc $P (3)$ est vraie (avec égalité).
Hérédité : soit $n \geq 3$ tel que $3^{n} \geq n^{3}$ . Alors $3^{n + 1} = 3 \cdot 3^{n} \geq 3 n^{3}$ . Il reste à voir que $3 n^{3} \geq (n + 1)^{3}$ . Comme $n \geq 3$ , on a $1 + \frac{1}{n} \leq \frac{4}{3}$ , donc $(n + 1)^{3} = n^{3} {(1 + \frac{1}{n})}^{3} \leq \frac{64}{27} n^{3} \leq 3 n^{3}$ , car $64 \leq 81$ . Ainsi $3^{n + 1} \geq (n + 1)^{3}$ .

Par récurrence, $3^{n} \geq n^{3} pour tout n \geq 3$ .

(b) Pour $n = 2$ , l'étape « $3 n^{3} \geq (n + 1)^{3}$ » s'écrit $24 \geq 27$ : elle est fausse. L'hérédité ne se démontre pas ainsi à partir de $2$ , d'où le choix du rang $3$ . Les petits cas se vérifient directement : $3^{0} = 1 \geq 0$ , $3^{1} = 3 \geq 1$ , $3^{2} = 9 \geq 8$ . Finalement l'inégalité est vraie pour tout $n \in ℕ$ , mais la récurrence ne démarre qu'au rang $3$ .

3. Le terme $u_{n + 2}$ dépend de deux termes précédents : on fait une récurrence double. Soit $P (n)$ : « $u_{n} = 2^{n} + 1$ ».

Initialisation : $u_{0} = 2 = 2^{0} + 1$ et $u_{1} = 3 = 2^{1} + 1$ : $P (0)$ et $P (1)$ sont vraies.
Hérédité : soit $n \in ℕ$ tel que $P (n)$ et $P (n + 1)$ . Alors $u_{n + 2} = 3 (2^{n + 1} + 1) - 2 (2^{n} + 1) = 6 \cdot 2^{n} - 2 \cdot 2^{n} + 3 - 2 = 4 \cdot 2^{n} + 1 = 2^{n + 2} + 1.$

Donc $P (n + 2)$ est vraie et, par récurrence double, $u_{n} = 2^{n} + 1 pour tout n$ .

4. (a) $v_{1} = v_{0} = 1$ ; $v_{2} = v_{0} + v_{1} = 2$ ; $v_{3} = 1 + 1 + 2 = 4$ ; $v_{4} = 1 + 1 + 2 + 4 = 8$ . Conjecture : $v_{n} = 2^{n - 1}$ pour $n \geq 1$ .

(b) Soit $P (n)$ : « $v_{n} = 2^{n - 1}$ », pour $n \geq 1$ .

Initialisation : $v_{1} = 1 = 2^{0}$ .
Hérédité forte : soit $n \geq 1$ tel que $P (k)$ soit vraie pour tout $k \in [⁣ [1, n] ⁣]$ . Alors, avec la somme géométrique $1 + 2 + \dots + 2^{n - 1} = 2^{n} - 1$ : $v_{n + 1} = v_{0} + \sum_{k = 1}^{n} v_{k} = 1 + \sum_{k = 1}^{n} 2^{k - 1} = 1 + (2^{n} - 1) = 2^{n} .$

Donc $P (n + 1)$ est vraie et, par récurrence forte, $v_{n} = 2^{n - 1} pour tout n \geq 1$ . La récurrence est forte parce que $v_{n + 1}$ utilise tous les termes précédents.

(c) Pour $n \geq 1$ : $v_{n + 1} = (v_{0} + \dots + v_{n - 1}) + v_{n} = v_{n} + v_{n} = 2 v_{n}$ . La suite $(v_{n})_{n \geq 1}$ est géométrique de raison $2$ et de premier terme $v_{1} = 1$ : une récurrence simple donne $v_{n} = 2^{n - 1}$ . Une récurrence forte peut souvent être remplacée par une récurrence simple bien choisie.

Après avoir comparé avec le corrigé :

Application du cours5 points

4. Ensembles, images, injections : des exemples concrets

Dans $E = [⁣ [1, 8] ⁣]$ , on considère $A = {1, 2, 3, 4}$ , $B = {2, 4, 6, 8}$ et $C = {3, 4, 5}$ . Déterminer $A \cap B$ , $A \cup C$ , $∁_{E} B$ , $A ∖ B$ , $A Δ B$ , $𝒫 (A \cap B)$ , et vérifier l'égalité $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ sur cet exemple.
Soit $f : ℝ \to ℝ$ , $x \mapsto x^{2} - 2 x$ . (a) Déterminer $f ([0, 3])$ et $f ([- 1, 1])$ . (b) Déterminer $f^{- 1} ({3})$ , $f^{- 1} ([- 1, 0])$ et $f^{- 1} (] - \infty, - 2])$ . (c) $f$ est-elle injective ? surjective ? (d) Montrer que $g : [1, + \infty [\to [- 1, + \infty [$ , $x \mapsto x^{2} - 2 x$ , est bijective et expliciter $g^{- 1}$ .
Soient $f, g : ℕ \to ℕ$ définies par $f (n) = n + 3$ , et $g (n) = n - 3$ si $n \geq 3$ , $g (n) = 0$ si $n \leq 2$ . (a) Calculer $g \circ f$ et $f \circ g$ . (b) Étudier l'injectivité et la surjectivité de $f$ et de $g$ . (c) Que retenir de cet exemple ?

Voir le corrigé

1. $A \cap B = {2, 4}$ ; $A \cup C = {1, 2, 3, 4, 5}$ ; $∁_{E} B = {1, 3, 5, 7}$ ; $A ∖ B = {1, 3}$ ; $B ∖ A = {6, 8}$ , donc $A Δ B = {1, 3, 6, 8}$ ; $𝒫 (A \cap B) = {\emptyset, {2}, {4}, {2, 4}}$ (quatre parties : $2^{2}$ ). Ensuite $B \cup C = {2, 3, 4, 5, 6, 8}$ , donc $A \cap (B \cup C) = {2, 3, 4}$ ; et $A \cap C = {3, 4}$ , donc $(A \cap B) \cup (A \cap C) = {2, 4} \cup {3, 4} = {2, 3, 4}$ . Les deux ensembles coïncident, comme l'annonce la distributivité (fiche §7).

2. Forme canonique : $f (x) = (x - 1)^{2} - 1$ . Donc $f$ est strictement décroissante sur $] - \infty, 1]$ , strictement croissante sur $[1, + \infty [$ , de minimum $f (1) = - 1$ .

(a) Sur $[0, 3]$ : $f$ décroît de $f (0) = 0$ à $f (1) = - 1$ , puis croît jusqu'à $f (3) = 3$ . Par continuité (valeurs intermédiaires) et monotonie sur chaque morceau, $f ([0, 1]) = [- 1, 0]$ et $f ([1, 3]) = [- 1, 3]$ , d'où $f ([0, 3]) = [- 1, 3]$ . Sur $[- 1, 1]$ , $f$ décroît de $f (- 1) = 3$ à $f (1) = - 1$ : $f ([- 1, 1]) = [- 1, 3]$ . Deux parties différentes peuvent avoir la même image.

(b) $f (x) = 3 ⟺ x^{2} - 2 x - 3 = 0 ⟺ (x + 1) (x - 3) = 0$ : $f^{- 1} ({3}) = {- 1, 3}$ . $f (x) \in [- 1, 0] ⟺ - 1 \leq (x - 1)^{2} - 1 \leq 0 ⟺ (x - 1)^{2} \leq 1 ⟺ ∣ x - 1 ∣ \leq 1$ (la minoration est toujours vraie) : $f^{- 1} ([- 1, 0]) = [0, 2]$ . $f (x) \leq - 2 ⟺ (x - 1)^{2} \leq - 1$ , impossible : $f^{- 1} (] - \infty, - 2]) = \emptyset$ .

(c) $f (- 1) = f (3) = 3$ avec $- 1 \neq 3$ : $f$ n'est pas injective. Le réel $- 2$ n'a pas d'antécédent (question (b)) : $f$ n'est pas surjective.

(d) Soit $y \in [- 1, + \infty [$ . Pour $x \geq 1$ : $g (x) = y ⟺ (x - 1)^{2} = 1 + y ⟺ x - 1 = \sqrt{1 + y} (car x - 1 \geq 0 et 1 + y \geq 0) .$ L'équation a donc une unique solution $x = 1 + \sqrt{1 + y}$ , qui appartient bien à $[1, + \infty [$ . Tout élément de l'ensemble d'arrivée a exactement un antécédent : $g$ est bijective et $g^{- 1} (y) = 1 + \sqrt{1 + y}$ pour $y \geq - 1$ .

3. (a) Pour tout $n \in ℕ$ , $f (n) = n + 3 \geq 3$ , donc $g (f (n)) = n$ : $g \circ f = {I d}_{ℕ}$ . Pour $n \geq 3$ , $f (g (n)) = n - 3 + 3 = n$ ; pour $n \leq 2$ , $f (g (n)) = f (0) = 3$ . Ainsi $f \circ g \neq {I d}_{ℕ}$ (par exemple $(f \circ g) (0) = 3$ ).

(b) $f$ est injective : $n + 3 = m + 3 \Rightarrow n = m$ . Elle n'est pas surjective : $0$ n'a pas d'antécédent ( $n + 3 \geq 3$ ). $g$ est surjective : pour $m \in ℕ$ , $g (m + 3) = m$ . Elle n'est pas injective : $g (0) = g (3) = 0$ . (On pouvait le prévoir : $g \circ f = I d$ est injective, donc $f$ est injective ; elle est surjective, donc $g$ est surjective, fiche §9.)

(c) L'égalité $g \circ f = {I d}_{E}$ seule ne rend ni $f$ ni $g$ bijective ; il faut aussi $f \circ g = {I d}_{F}$ pour conclure.

Après avoir comparé avec le corrigé :

Niveau devoir7 points

5. Parties saturées par une application

Soit $f : E \to F$ une application. Une partie $A$ de $E$ est dite saturée (pour $f$ ) si $f^{- 1} (f (A)) = A$ .

Montrer que $A \subset f^{- 1} (f (A))$ pour toute partie $A$ de $E$ .
Soit $B \subset F$ . Montrer que $f (f^{- 1} (B)) \subset B$ , puis que $f^{- 1} (B)$ est saturée.
En déduire qu'une partie $A$ de $E$ est saturée si et seulement s'il existe $B \subset F$ tel que $A = f^{- 1} (B)$ .
Soient $A$ et $A^{'}$ deux parties saturées. Montrer que $A \cup A^{'}$ , $A \cap A^{'}$ et $∁_{E} A$ sont saturées.
Établir l'équivalence : $f$ injective $⟺$ chaque partie de $E$ est saturée.
Dans cette question, $E = F = ℝ$ et $f (x) = x^{2}$ . (a) Déterminer $f^{- 1} (f ([- 1, 2]))$ . La partie $[- 1, 2]$ est-elle saturée ? (b) Montrer qu'une partie $A$ de $ℝ$ est saturée si et seulement si elle est symétrique, c'est-à-dire : $\forall x \in ℝ, x \in A ⟺ - x \in A$ .

Voir le corrigé

1. Soit $x \in A$ . Alors $f (x) \in f (A)$ par définition de l'image directe, donc $x \in f^{- 1} (f (A))$ par définition de l'image réciproque. D'où $A \subset f^{- 1} (f (A))$ .

2. Soit $y \in f (f^{- 1} (B))$ : il existe $x \in f^{- 1} (B)$ tel que $y = f (x)$ ; or $x \in f^{- 1} (B)$ signifie $f (x) \in B$ , donc $y \in B$ . Ainsi $f (f^{- 1} (B)) \subset B$ . Posons $A = f^{- 1} (B)$ . L'image réciproque respecte l'inclusion, donc $f^{- 1} (f (A)) \subset f^{- 1} (B) = A$ . Avec la question 1, on obtient $f^{- 1} (f (A)) = A$ : $f^{- 1} (B) est satur \overset{ˊ}{e} e$ .

3. Si $A$ est saturée, $B = f (A)$ convient puisque $A = f^{- 1} (f (A))$ . Réciproquement, si $A = f^{- 1} (B)$ , la question 2 montre que $A$ est saturée. D'où l'équivalence : les parties saturées sont exactement les images réciproques.

4. D'après la question 3, écrivons $A = f^{- 1} (B)$ et $A^{'} = f^{- 1} (B^{'})$ avec $B, B^{'} \subset F$ . L'image réciproque respecte toutes les opérations (fiche §8) : $A \cup A^{'} = f^{- 1} (B \cup B^{'}), A \cap A^{'} = f^{- 1} (B \cap B^{'}), ∁_{E} A = f^{- 1} (∁_{F} B) .$ Ce sont trois images réciproques, donc trois parties saturées (question 3).

5. ( $\Rightarrow$ ) Supposons $f$ injective et soit $A \subset E$ . Soit $x \in f^{- 1} (f (A))$ : $f (x) \in f (A)$ , donc il existe $a \in A$ tel que $f (x) = f (a)$ ; l'injectivité donne $x = a \in A$ . Ainsi $f^{- 1} (f (A)) \subset A$ et, avec la question 1, $A$ est saturée. ( $\Leftarrow$ ) Supposons toutes les parties saturées. Soient $x, x^{'} \in E$ tels que $f (x) = f (x^{'})$ . La partie ${x}$ est saturée : $f^{- 1} ({f (x)}) = {x}$ . Or $f (x^{'}) = f (x)$ donc $x^{'} \in f^{- 1} ({f (x)}) = {x}$ , d'où $x^{'} = x$ : $f$ est injective.

6. (a) $f ([- 1, 2]) = [0, 4]$ (car $x^{2}$ décrit $[0, 1]$ sur $[- 1, 0]$ et $[0, 4]$ sur $[0, 2]$ ) et $f^{- 1} ([0, 4]) = {x ∣ x^{2} \leq 4} = [- 2, 2]$ . Donc $f^{- 1} (f ([- 1, 2])) = [- 2, 2] \neq [- 1, 2]$ : la partie $[- 1, 2]$ n'est pas saturée.

(b) Supposons $A$ saturée et soit $x \in A$ . Alors $f (- x) = x^{2} = f (x) \in f (A)$ , donc $- x \in f^{- 1} (f (A)) = A$ . En appliquant ce résultat à $- x$ , on obtient aussi $- x \in A \Rightarrow x \in A$ : $A$ est symétrique. Réciproquement, supposons $A$ symétrique et soit $x \in f^{- 1} (f (A))$ : il existe $a \in A$ tel que $x^{2} = a^{2}$ , donc $x = a$ ou $x = - a$ ; dans les deux cas $x \in A$ par symétrie. Ainsi $f^{- 1} (f (A)) \subset A$ , et $A$ est saturée (question 1).

Après avoir comparé avec le corrigé :

Niveau devoir7 points

6. Composition, projections et involutions

Partie A (résultats du cours). On considère deux applications $f : E \to F$ et $g : F \to G$ .

Prouver que l'injectivité de $g \circ f$ entraîne celle de $f$ .
Prouver que la surjectivité de $g \circ f$ entraîne celle de $g$ .

Partie B. Soit $p : E \to E$ une application telle que $p \circ p = p$ . On note $I n v (p) = {x \in E ∣ p (x) = x}$ . 3. Montrer que $p (E) = I n v (p)$ . 4. Montrer l'équivalence des trois assertions : (i) $p$ est injective ; (ii) $p = {I d}_{E}$ ; (iii) $p$ est surjective. 5. Exemple : $p : ℝ \to ℝ$ , $x \mapsto E (x)$ (partie entière). Vérifier que $p \circ p = p$ , déterminer $p (ℝ)$ et en déduire, sans autre calcul, que $p$ n'est ni injective ni surjective.

Partie C. Soit $s : E \to E$ telle que $s \circ s = {I d}_{E}$ . 6. Montrer que $s$ est bijective et que $s^{- 1} = s$ . 7. Exemple : pour $x \in ℝ ∖ {1}$ , on pose $s (x) = \frac{x + 1}{x - 1}$ . (a) Montrer que $s$ définit une application de $ℝ ∖ {1}$ dans $ℝ ∖ {1}$ . (b) Calculer $s \circ s$ et en déduire que $s$ est bijective. Résoudre l'équation $\frac{x + 1}{x - 1} = 3$ sans calcul nouveau.

Voir le corrigé

1. Soient $x, x^{'} \in E$ tels que $f (x) = f (x^{'})$ . En appliquant $g$ : $g (f (x)) = g (f (x^{'}))$ , c'est-à-dire $(g \circ f) (x) = (g \circ f) (x^{'})$ . L'injectivité de $g \circ f$ donne $x = x^{'}$ : $f$ est injective.

2. Soit $z \in G$ . Comme $g \circ f$ est surjective, il existe $x \in E$ tel que $g (f (x)) = z$ . Alors $y = f (x) \in F$ vérifie $g (y) = z$ : tout élément de $G$ a un antécédent par $g$ , donc $g$ est surjective.

3. ( $\subset$ ) Soit $y \in p (E)$ : $y = p (x)$ avec $x \in E$ . Alors $p (y) = p (p (x)) = (p \circ p) (x) = p (x) = y$ , donc $y \in I n v (p)$ . ( $\supset$ ) Si $x \in I n v (p)$ , alors $x = p (x) \in p (E)$ . D'où $p (E) = I n v (p)$ : l'image de $p$ est l'ensemble de ses points fixes.

4. (i) $\Rightarrow$ (ii) : soit $x \in E$ . On a $p (p (x)) = p (x)$ , et l'injectivité de $p$ donne $p (x) = x$ . Donc $p = {I d}_{E}$ . (ii) $\Rightarrow$ (iii) : ${I d}_{E}$ est surjective. (iii) $\Rightarrow$ (i) : si $p$ est surjective, $p (E) = E$ , donc $I n v (p) = E$ par la question 3 : $p (x) = x$ pour tout $x$ , et $p = {I d}_{E}$ est injective. Ainsi, pour une application vérifiant $p \circ p = p$ , injective, surjective et égale à l'identité, c'est la même chose.

5. Pour tout réel $x$ , $E (x) \in ℤ$ et la partie entière d'un entier est lui-même : $E (E (x)) = E (x)$ , donc $p \circ p = p$ . Tout entier $k$ vérifie $E (k) = k$ , donc $ℤ \subset p (ℝ)$ , et $p (ℝ) \subset ℤ$ : $p (ℝ) = ℤ$ . Comme $ℤ \neq ℝ$ , on a $p \neq {I d}_{ℝ}$ et, d'après la question 4, $p$ n'est ni injective ni surjective.

6. $s \circ s = {I d}_{E}$ est injective et surjective. Par la partie A (avec $f = g = s$ ), $s$ est injective et surjective, donc bijective. En composant $s \circ s = {I d}_{E}$ à gauche par $s^{- 1}$ : $s = s^{- 1}$ .

7. (a) Pour $x \neq 1$ , $s (x)$ existe. Si l'on avait $s (x) = 1$ , on aurait $x + 1 = x - 1$ , soit $1 = - 1$ : impossible. Donc $s (x) \in ℝ ∖ {1}$ et $s$ est bien une application de $ℝ ∖ {1}$ dans lui-même.

(b) Pour $x \neq 1$ : $s (s (x)) = \frac{\frac{x + 1}{x - 1} + 1}{\frac{x + 1}{x - 1} - 1} = \frac{\frac{2 x}{x - 1}}{\frac{2}{x - 1}} = x .$ Donc $s \circ s = I d$ et, par la question 6, $s est bijective et s^{- 1} = s$ . L'équation $s (x) = 3$ a donc pour unique solution $x = s^{- 1} (3) = s (3) = \frac{4}{2} = 2$ (vérification : $\frac{2 + 1}{2 - 1} = 3$ ).

Après avoir comparé avec le corrigé :

Niveau devoir7 points

7. Une relation d'équivalence et ses classes

Partie A. Soit $f : E \to F$ . On définit sur $E$ la relation $x ℛ y ⟺ f (x) = f (y)$ .

Prouver que $ℛ$ est réflexive, symétrique et transitive, et que la classe de $x$ est $c l (x) = f^{- 1} ({f (x)})$ .
Montrer que la correspondance $φ : E / ℛ \to f (E)$ , $c l (x) \mapsto f (x)$ définit bien une application (c'est-à-dire que $f (x)$ ne dépend pas du représentant choisi dans la classe), puis qu'elle est bijective.

Partie B. On définit sur $ℝ$ la relation $x 𝒮 y ⟺ x^{3} - 3 x = y^{3} - 3 y$ , et on note $h (t) = t^{3} - 3 t$ . 3. Justifier en une ligne que $𝒮$ est une relation d'équivalence. 4. Vérifier que $x^{3} - 3 x - (y^{3} - 3 y) = (x - y) (x^{2} + x y + y^{2} - 3)$ . 5. Déterminer les classes de $2$ , de $1$ , de $0$ et de $3$ . 6. Dresser le tableau de variations de $h$ et en déduire, selon la valeur de $x$ , le nombre d'éléments de $c l (x)$ .

Voir le corrigé

1. Réflexivité : $f (x) = f (x)$ . Symétrie : $f (x) = f (y) \Rightarrow f (y) = f (x)$ . Transitivité : $f (x) = f (y)$ et $f (y) = f (z)$ entraînent $f (x) = f (z)$ . Ce sont les propriétés de l'égalité dans $F$ : $ℛ$ est une relation d'équivalence. Ensuite $y \in c l (x) ⟺ f (y) = f (x) ⟺ f (y) \in {f (x)} ⟺ y \in f^{- 1} ({f (x)})$ .

2. Bonne définition. Si $c l (x) = c l (x^{'})$ , alors $x ℛ x^{'}$ (fiche §10), c'est-à-dire $f (x) = f (x^{'})$ : la valeur attribuée à la classe ne dépend pas du représentant. Injectivité. Si $φ (c l (x)) = φ (c l (x^{'}))$ , alors $f (x) = f (x^{'})$ , donc $x ℛ x^{'}$ et $c l (x) = c l (x^{'})$ . Surjectivité. Tout $y \in f (E)$ s'écrit $f (x)$ avec $x \in E$ , et $y = φ (c l (x))$ . Donc $φ est une bijection de E / ℛ sur f (E)$ : il y a « autant » de classes que de valeurs prises par $f$ .

3. $x 𝒮 y ⟺ h (x) = h (y)$ : c'est la relation de la partie A pour $f = h$ , donc une relation d'équivalence.

4. $x^{3} - y^{3} = (x - y) (x^{2} + x y + y^{2})$ et $- 3 x + 3 y = - 3 (x - y)$ , d'où $h (x) - h (y) = (x - y) (x^{2} + x y + y^{2} - 3)$ .

5. D'après la question 4, $y \in c l (x) ⟺ y = x$ ou $y^{2} + x y + x^{2} - 3 = 0$ .

$x = 2$ : $y^{2} + 2 y + 1 = 0 ⟺ y = - 1$ . Donc $c l (2) = {- 1, 2}$ (vérification : $h (- 1) = h (2) = 2$ ).
$x = 1$ : $y^{2} + y - 2 = 0 ⟺ (y - 1) (y + 2) = 0$ . Donc $c l (1) = {- 2, 1}$ ( $h (1) = h (- 2) = - 2$ ).
$x = 0$ : $y^{2} = 3$ . Donc $c l (0) = {- \sqrt{3}, 0, \sqrt{3}}$ .
$x = 3$ : $y^{2} + 3 y + 6 = 0$ a pour discriminant $9 - 24 < 0$ : aucune solution réelle. Donc $c l (3) = {3}$ .

6. $h^{'} (t) = 3 (t^{2} - 1)$ : $h$ est strictement croissante sur $] - \infty, - 1]$ , strictement décroissante sur $[- 1, 1]$ , strictement croissante sur $[1, + \infty [$ , avec $h (- 1) = 2$ , $h (1) = - 2$ , $\lim_{- \infty} h = - \infty$ , $\lim_{+ \infty} h = + \infty$ . Pour un réel $c$ , par stricte monotonie et continuité sur chacun des trois intervalles, l'équation $h (t) = c$ a : une solution si $c > 2$ ou $c < - 2$ ; deux solutions si $c = \pm 2$ ; trois solutions si $- 2 < c < 2$ . Il reste à situer $c = h (x)$ :

$h (x) - 2 = x^{3} - 3 x - 2 = (x + 1)^{2} (x - 2)$ , donc $h (x) > 2 ⟺ x > 2$ et $h (x) = 2 ⟺ x \in {- 1, 2}$ ;
$h (x) + 2 = x^{3} - 3 x + 2 = (x - 1)^{2} (x + 2)$ , donc $h (x) < - 2 ⟺ x < - 2$ et $h (x) = - 2 ⟺ x \in {- 2, 1}$ .

Bilan, puisque $c l (x)$ est l'ensemble des solutions de $h (t) = h (x)$ : $card c l (x) = {\begin{cases} 1 & si ∣ x ∣ > 2, \\ 2 & si x \in {- 2, - 1, 1, 2}, \\ 3 & si x \in] - 2, 2 [∖ {- 1, 1} . \end{cases}$

Après avoir comparé avec le corrigé :

Niveau devoir6 points

8. Deux relations d'ordre

Partie A. On définit sur $ℝ$ la relation $x ≼ y ⟺ y - x \in ℕ$ .

Vérifier que $≼$ définit un ordre sur $ℝ$ .
Deux réels sont-ils toujours comparables ? Déterminer l'ensemble des réels comparables à $0$ .
Soit $A = {\frac{1}{2}, 2, \frac{7}{2}, 3}$ . On dit que $a \in A$ est un élément maximal de $A$ s'il n'existe aucun $b \in A$ tel que $a ≼ b$ et $b \neq a$ . (a) $A$ admet-elle un majorant dans $(ℝ, ≼)$ ? un plus grand élément ? (b) Déterminer les éléments maximaux de $A$ .

Partie B. On ordonne $ℕ^{*}$ par la divisibilité : $a ∣ b ⟺ \exists k \in ℕ^{*}, b = k a$ . 4. Rappeler pourquoi c'est une relation d'ordre, et montrer qu'elle n'est pas totale. 5. Soit $B = {4, 6, 10}$ . Déterminer les majorants et les minorants de $B$ , sa borne supérieure et sa borne inférieure. $B$ a-t-elle un plus grand élément ?

Voir le corrigé

1. Réflexivité : $x - x = 0 \in ℕ$ . Antisymétrie : si $y - x \in ℕ$ et $x - y \in ℕ$ , alors $y - x$ est un entier naturel dont l'opposé est aussi un entier naturel, donc $y - x = 0$ et $x = y$ . Transitivité : si $y - x \in ℕ$ et $z - y \in ℕ$ , alors $z - x = (z - y) + (y - x) \in ℕ$ . Donc $≼ est une relation d’ordre$ .

2. $x$ est comparable à $0$ si $x - 0 \in ℕ$ ou $0 - x \in ℕ$ , c'est-à-dire $x \in ℕ$ ou $- x \in ℕ$ : l'ensemble des réels comparables à $0$ est $ℤ$ . Ainsi $0$ et $\frac{1}{2}$ ne sont pas comparables : l'ordre n'est pas total.

3. (a) Supposons que $M$ majore $A$ . Alors $M - \frac{1}{2} \in ℕ$ et $M - 2 \in ℕ$ , donc leur différence $(M - \frac{1}{2}) - (M - 2) = \frac{3}{2}$ serait un entier relatif : c'est faux. $A$ n'a aucun majorant, donc a fortiori aucun plus grand élément.

(b) Comparons les éléments deux à deux : $\frac{7}{2} - \frac{1}{2} = 3 \in ℕ$ , donc $\frac{1}{2} ≼ \frac{7}{2}$ ; $3 - 2 = 1 \in ℕ$ , donc $2 ≼ 3$ ; les autres différences ( $\frac{3}{2}$ , $\frac{5}{2}$ , $\frac{1}{2}$ et leurs opposés) ne sont pas entières. Donc $\frac{1}{2}$ et $2$ ne sont pas maximaux, alors que rien dans $A$ n'est au-dessus de $\frac{7}{2}$ ni de $3$ : les éléments maximaux sont $\frac{7}{2} et 3$ . Il y en a deux : un élément maximal n'est pas un plus grand élément quand l'ordre est partiel.

4. $a = 1 \cdot a$ (réflexivité) ; si $b = k a$ et $a = k^{'} b$ avec $k, k^{'} \in ℕ^{*}$ , alors $a = k k^{'} a$ , donc $k k^{'} = 1$ , $k = k^{'} = 1$ et $a = b$ (antisymétrie, qui utilise la positivité) ; si $b = k a$ et $c = k^{'} b$ , alors $c = (k k^{'}) a$ (transitivité). Elle n'est pas totale : $2 ∤ 3$ et $3 ∤ 2$ .

5. Un majorant de $B$ est un entier divisible par $4$ , par $6$ et par $10$ , c'est-à-dire un multiple commun. Comme $4 = 2^{2}$ , $6 = 2 \cdot 3$ , $10 = 2 \cdot 5$ , les multiples communs sont les multiples de $2^{2} \cdot 3 \cdot 5 = 60$ . La borne supérieure est le plus petit des majorants pour la divisibilité : $60$ divise tous les autres, donc $\sup B = 60$ . Les minorants sont les diviseurs communs : ${1, 2}$ ; tous deux divisent $2$ , donc $\inf B = 2$ . $B$ n'a pas de plus grand élément, car $60 \notin B$ (aucun des trois nombres ne divise les deux autres) ; elle n'a pas non plus de plus petit élément ( $2 \notin B$ ).

Après avoir comparé avec le corrigé :

Synthèse, niveau concours10 points

9. Problème : point fixe sur $𝒫 (E)$ et théorème de Cantor-Bernstein

Partie A — Un point fixe. Soit $E$ un ensemble et $Φ : 𝒫 (E) \to 𝒫 (E)$ une application croissante pour l'inclusion : $X \subset Y \Rightarrow Φ (X) \subset Φ (Y)$ . On pose $ℱ = {X \in 𝒫 (E) ∣ Φ (X) \subset X}$ et $M = ⋂_{X \in ℱ} X$ (intersection de toutes les parties de $ℱ$ ).

Montrer que $ℱ$ n'est pas vide.
Montrer que $Φ (M) \subset M$ .
Montrer que $Φ (M) \in ℱ$ , puis que $Φ (M) = M$ . Montrer enfin que $M$ est inclus dans toute partie $X$ telle que $Φ (X) = X$ .

Partie B — Théorème de Cantor-Bernstein. Soient $f : E \to F$ et $g : F \to E$ deux applications injectives. Pour $X \subset E$ , on pose $Φ (X) = E ∖ g (F ∖ f (X))$ . 4. Montrer que $Φ$ est croissante pour l'inclusion. On note $M$ la partie obtenue dans la partie A. 5. Montrer que $E ∖ M = g (F ∖ f (M))$ . 6. Justifier que l'on définit une application $h : E \to F$ en posant : $h (x) = f (x)$ si $x \in M$ , et, si $x \notin M$ , $h (x)$ est l'unique $y \in F ∖ f (M)$ tel que $g (y) = x$ . 7. Montrer que $h$ est injective. 8. Montrer que $h$ est surjective. Énoncer le résultat obtenu.

Partie C — Un exemple. On prend $E = ℕ$ , $F = 2 ℕ$ (entiers naturels pairs), $f (n) = 4 n$ et $g : 2 ℕ \to ℕ$ l'inclusion ( $g (m) = m$ ). On note $I$ l'ensemble des entiers naturels impairs. 9. Montrer que $Φ (X) = I \cup f (X)$ pour toute partie $X$ de $ℕ$ . 10. Montrer que $M = {4^{k} m ∣ k \in ℕ, m \in I}$ , puis expliciter $h$ et donner $h (0), h (1), \dots, h (8)$ .

Voir le corrigé

1. $Φ (E)$ est une partie de $E$ , donc $Φ (E) \subset E$ et $E \in ℱ$ .

2. Soit $X \in ℱ$ . Comme $M$ est l'intersection des éléments de $ℱ$ , on a $M \subset X$ , donc par croissance $Φ (M) \subset Φ (X) \subset X$ . Ainsi $Φ (M)$ est inclus dans chaque $X \in ℱ$ , donc dans leur intersection : $Φ (M) \subset M$ .

3. En appliquant la croissance de $Φ$ à l'inclusion $Φ (M) \subset M$ : $Φ (Φ (M)) \subset Φ (M)$ , c'est-à-dire $Φ (M) \in ℱ$ . Par définition de $M$ , on en déduit $M \subset Φ (M)$ . Avec la question 2, $Φ (M) = M$ . Si $Φ (X) = X$ , alors en particulier $Φ (X) \subset X$ , donc $X \in ℱ$ et $M \subset X$ : $M$ est le plus petit point fixe de $Φ$ .

4. Soient $X \subset Y \subset E$ . Alors $f (X) \subset f (Y)$ , donc $F ∖ f (Y) \subset F ∖ f (X)$ , puis $g (F ∖ f (Y)) \subset g (F ∖ f (X))$ , et en passant au complémentaire dans $E$ (qui renverse les inclusions) : $Φ (X) \subset Φ (Y)$ . $Φ$ est croissante (deux passages au complémentaire, chacun renverse l'inclusion).

5. $M = Φ (M) = E ∖ g (F ∖ f (M))$ ; en passant au complémentaire : $E ∖ M = g (F ∖ f (M))$ .

6. Si $x \in M$ , $h (x) = f (x)$ est bien défini. Si $x \notin M$ , alors $x \in g (F ∖ f (M))$ par la question 5 : il existe $y \in F ∖ f (M)$ tel que $g (y) = x$ , et il est unique car $g$ est injective. À chaque $x$ correspond donc un et un seul $h (x) \in F$ : $h$ est une application.

7. Soient $x, x^{'} \in E$ tels que $h (x) = h (x^{'})$ . Remarquons que $h (M) = f (M)$ et $h (E ∖ M) \subset F ∖ f (M)$ : ces deux ensembles sont disjoints.

Si $x, x^{'} \in M$ : $f (x) = f (x^{'})$ et $f$ est injective, donc $x = x^{'}$ .
Si $x, x^{'} \notin M$ : en notant $y = h (x) = h (x^{'})$ , on a $x = g (y) = x^{'}$ .
Si $x \in M$ et $x^{'} \notin M$ (ou l'inverse) : $h (x) \in f (M)$ et $h (x^{'}) \notin f (M)$ , donc $h (x) \neq h (x^{'})$ ; ce cas est impossible.

Donc $h est injective$ .

8. Soit $y \in F$ . Si $y \in f (M)$ , $y = f (x) = h (x)$ pour un $x \in M$ . Sinon $y \in F ∖ f (M)$ ; posons $x = g (y)$ . Alors $x \in g (F ∖ f (M)) = E ∖ M$ , et $h (x)$ est l'unique antécédent de $x$ par $g$ dans $F ∖ f (M)$ , c'est-à-dire $y$ . Donc $h$ est surjective, et finalement bijective. Théorème de Cantor-Bernstein : s'il existe une injection de $E$ dans $F$ et une injection de $F$ dans $E$ , alors il existe une bijection de $E$ sur $F$ .

9. $f (X)$ est formé d'entiers pairs. $F ∖ f (X)$ est l'ensemble des entiers pairs qui ne sont pas dans $f (X)$ , et $g$ ne le change pas. Son complémentaire dans $ℕ$ contient les impairs et les pairs qui sont dans $f (X)$ : $Φ (X) = I \cup f (X)$ .

10. Notons $S = {4^{k} m ∣ k \in ℕ, m \in I}$ .

$S$ est un point fixe : $Φ (S) = I \cup {4^{k + 1} m ∣ k \in ℕ, m \in I}$ ; le premier ensemble correspond à $k = 0$ et le second à $k \geq 1$ , donc $Φ (S) = S$ . Par la question 3, $M \subset S$ .
$S \subset M$ : soit $X \in ℱ$ , c'est-à-dire $I \cup f (X) \subset X$ . Montrons par récurrence sur $k$ que $4^{k} m \in X$ pour tout $m \in I$ . Pour $k = 0$ , $m \in I \subset X$ . Si $4^{k} m \in X$ , alors $4^{k + 1} m = f (4^{k} m) \in f (X) \subset X$ . Donc $S \subset X$ pour tout $X \in ℱ$ , d'où $S \subset M$ .

Ainsi $M = {4^{k} m ∣ k \in ℕ, m impair}$ : ce sont les entiers non nuls dont l'exposant de $2$ est pair. Pour $n \notin M$ , $n$ est pair ( $I \subset M$ ) et son antécédent par l'inclusion $g$ est $n$ lui-même. Donc $h (n) = {\begin{cases} 4 n & si n \in M, \\ n & sinon. \end{cases}$ $0 \notin M$ ( $0$ n'est pas de la forme $4^{k} m$ avec $m$ impair), $2 \notin M$ , $6 \notin M$ , $8 = 4 \cdot 2 \notin M$ , et $1, 3, 4, 5, 7 \in M$ : $h (0) = 0, h (1) = 4, h (2) = 2, h (3) = 12, h (4) = 16, h (5) = 20, h (6) = 6, h (7) = 28, h (8) = 8.$ On obtient une bijection explicite de $ℕ$ sur $2 ℕ$ , différente de $n \mapsto 2 n$ .

Après avoir comparé avec le corrigé :

Synthèse, niveau concours10 points

10. Problème : la relation d'équivalence engendrée par une application

On fixe un ensemble $E$ non vide et une application $f$ de $E$ dans lui-même. On pose $f^{0} = {I d}_{E}$ et $f^{n + 1} = f \circ f^{n}$ pour $n \in ℕ$ . On définit sur $E$ la relation $x \sim y ⟺ \exists (p, q) \in ℕ^{2}, f^{p} (x) = f^{q} (y) .$

Partie A — Propriétés générales.

Montrer que $f^{n + m} = f^{n} \circ f^{m}$ pour tous $n, m \in ℕ$ .
Prouver que $\sim$ est réflexive, symétrique et transitive.
Soit $x \in E$ . Montrer que $f^{n} (x) \in c l (x)$ pour tout $n \in ℕ$ , puis que $f^{- 1} (c l (x)) = c l (x)$ .

Partie B — Exemples. 4. $E = ℤ$ et $f (n) = n + 2$ . Déterminer les classes. 5. $E = ℕ$ et $f (n) = E ⁣ (\frac{n}{2})$ . Montrer, par récurrence forte, que pour tout $x \in ℕ$ il existe $p \in ℕ$ tel que $f^{p} (x) = 0$ . En déduire les classes. 6. $E = [⁣ [1, 8] ⁣]$ et $f$ donnée par le tableau :

$x$	1	2	3	4	5	6	7	8
$f (x)$	2	3	1	5	4	6	6	7

Déterminer les classes.

Partie C — Cas bijectif. 7. On suppose $f$ bijective. Montrer que $x \sim y$ si et seulement s'il existe $n \in ℕ$ tel que $y = f^{n} (x)$ ou $x = f^{n} (y)$ .

Voir le corrigé

1. Fixons $m \in ℕ$ et raisonnons par récurrence sur $n$ . Pour $n = 0$ : $f^{0 + m} = f^{m} = {I d}_{E} \circ f^{m} = f^{0} \circ f^{m}$ . Si $f^{n + m} = f^{n} \circ f^{m}$ , alors $f^{(n + 1) + m} = f \circ f^{n + m} = f \circ (f^{n} \circ f^{m}) = (f \circ f^{n}) \circ f^{m} = f^{n + 1} \circ f^{m}$ (associativité de la composition). D'où $f^{n + m} = f^{n} \circ f^{m}$ pour tous $n, m$ . En particulier, $f^{n} \circ f^{m} = f^{m} \circ f^{n}$ .

2. Réflexivité : $p = q = 0$ donne $f^{0} (x) = f^{0} (x)$ . Symétrie : si $f^{p} (x) = f^{q} (y)$ , alors $f^{q} (y) = f^{p} (x)$ . Transitivité : supposons $f^{p} (x) = f^{q} (y)$ et $f^{r} (y) = f^{s} (z)$ . En appliquant $f^{r}$ à la première égalité et $f^{q}$ à la seconde, et en utilisant la question 1 : $f^{p + r} (x) = f^{r} (f^{p} (x)) = f^{r} (f^{q} (y)) = f^{q + r} (y) = f^{q} (f^{r} (y)) = f^{q} (f^{s} (z)) = f^{q + s} (z) .$ Donc $x \sim z$ , avec les exposants $p + r$ et $q + s$ . $\sim est une relation d’ \overset{ˊ}{e} quivalence$ .

3. Avec $p = n$ et $q = 0$ : $f^{n} (x) = f^{0} (f^{n} (x))$ , donc $x \sim f^{n} (x)$ , c'est-à-dire $f^{n} (x) \in c l (x)$ . Montrons $f^{- 1} (c l (x)) = c l (x)$ . Si $y \in c l (x)$ , alors $f (y) \sim y \sim x$ , donc $f (y) \in c l (x)$ et $y \in f^{- 1} (c l (x))$ . Réciproquement, si $f (y) \in c l (x)$ , alors $y \sim f (y)$ (cas $n = 1$ ) et $f (y) \sim x$ , donc $y \sim x$ par transitivité. Les classes sont donc des parties saturées au sens de l'exercice 5.

4. Par récurrence immédiate, $f^{p} (n) = n + 2 p$ . Donc $x \sim y ⟺ \exists p, q \in ℕ, x + 2 p = y + 2 q$ . Si $x \sim y$ , alors $x - y = 2 (q - p)$ est pair. Réciproquement, si $x - y = 2 k$ avec $k \in ℤ$ : pour $k \geq 0$ , $f^{0} (x) = x = y + 2 k = f^{k} (y)$ ; pour $k < 0$ , $f^{- k} (x) = x - 2 k = y = f^{0} (y)$ . Donc $x \sim y ⟺ x - y$ pair : il y a $deux classes, les pairs et les impairs$ .

5. Soit $P (x)$ : « il existe $p \in ℕ$ tel que $f^{p} (x) = 0$ ».

$P (0)$ est vraie avec $p = 0$ .
Soit $x \geq 0$ tel que $P (k)$ soit vraie pour tout $k \in [⁣ [0, x] ⁣]$ . Considérons $x + 1 \geq 1$ : $f (x + 1) = E ⁣ (\frac{x + 1}{2}) \leq \frac{x + 1}{2} < x + 1$ , donc $k = f (x + 1) \in [⁣ [0, x] ⁣]$ . Par hypothèse il existe $p$ tel que $f^{p} (k) = 0$ , et alors $f^{p + 1} (x + 1) = f^{p} (f (x + 1)) = 0$ .

Par récurrence forte, $P (x)$ est vraie pour tout $x$ . (La récurrence est forte car $f (x + 1)$ vaut environ la moitié de $x + 1$ , pas $x$ .) Pour $x, y \in ℕ$ , prenons $p, q$ avec $f^{p} (x) = 0 = f^{q} (y)$ : $x \sim y$ . Il y a $une seule classe : ℕ$ .

6. On suit les flèches $x \to f (x)$ . $1 \to 2 \to 3 \to 1$ : $1, 2, 3$ sont dans la même classe. $4 \to 5 \to 4$ : $4 \sim 5$ . $8 \to 7 \to 6 \to 6$ : $f^{2} (8) = 6 = f (7) = f^{0} (6)$ , donc $6, 7, 8$ sont équivalents. Aucun élément d'un de ces trois blocs n'est envoyé dans un autre ; chaque bloc est stable par $f$ , donc deux éléments de blocs différents ont des itérés dans des blocs différents et ne sont pas équivalents. Les classes sont ${1, 2, 3}, {4, 5}, {6, 7, 8}$ .

7. ( $\Leftarrow$ ) Si $y = f^{n} (x)$ , alors $f^{n} (x) = f^{0} (y)$ ; si $x = f^{n} (y)$ , alors $f^{0} (x) = f^{n} (y)$ . Dans les deux cas $x \sim y$ . ( $\Rightarrow$ ) Supposons $f^{p} (x) = f^{q} (y)$ . Par récurrence, chaque $f^{k}$ est injective (composée d'injections, fiche §9).

Si $p \geq q$ : $f^{q} (f^{p - q} (x)) = f^{p} (x) = f^{q} (y)$ , donc $f^{p - q} (x) = y$ par injectivité de $f^{q}$ ; on prend $n = p - q$ .
Si $p < q$ : de même $f^{p} (x) = f^{p} (f^{q - p} (y))$ donne $x = f^{q - p} (y)$ ; on prend $n = q - p$ .

Lorsque $f$ est une bijection d'un ensemble fini, les classes sont les « cycles » de $f$ : c'est le point de départ de l'étude des permutations dans le chapitre « Structures algébriques ».

Après avoir comparé avec le corrigé :

Synthèse, niveau concours10 points

11. Problème : fonctions caractéristiques et différence symétrique

Classique du programme : fonction caractéristique (indicatrice). Classique du programme : différence symétrique.

Soit $E$ un ensemble. Pour $A \subset E$ , la fonction caractéristique de $A$ est l'application $𝟙_{A} : E \to {0, 1}$ qui vaut $1$ sur $A$ et $0$ sur $E ∖ A$ . Pour $A, B \subset E$ , la différence symétrique est $A Δ B = (A ∖ B) \cup (B ∖ A)$ .

Partie A — Calculs avec les fonctions caractéristiques (3 points)

Montrer que $𝟙_{A \cap B} = 𝟙_{A} 𝟙_{B}$ et $𝟙_{\overline{A}} = 1 - 𝟙_{A}$ , puis que $𝟙_{A \cup B} = 𝟙_{A} + 𝟙_{B} - 𝟙_{A} 𝟙_{B}$ . Montrer enfin que $A = B ⟺ 𝟙_{A} = 𝟙_{B}$ .
Établir que $𝟙_{A Δ B} = 𝟙_{A} + 𝟙_{B} - 2 𝟙_{A} 𝟙_{B}$ .

Partie B — Structure de $(𝒫 (E), Δ)$ (4 points)

Pour $u, v, w \in {0, 1}$ , on pose $θ (u, v) = u + v - 2 u v$ . Vérifier que $θ (u, v) \in {0, 1}$ , puis que $θ (θ (u, v), w) = θ (u, θ (v, w))$ . En déduire que, pour $A, B, C \subset E$ , $(A Δ B) Δ C = A Δ (B Δ C)$ . Décrire l'ensemble $A Δ B Δ C$ à l'aide du nombre de parties parmi $A, B, C$ qui contiennent un élément donné.
Montrer que $A Δ B = B Δ A$ , $A Δ \emptyset = A$ et $A Δ A = \emptyset$ . Que dire de $A Δ B$ lorsque $B \subset A$ ?

Partie C — L'équation $A Δ X = B$ (3 points)

Ici, les parties $A$ et $B$ de $E$ sont fixées, et l'on cherche les parties $X$ de $E$ telles que $A Δ X = B$ .

Résoudre l'équation, par analyse et synthèse : montrer qu'elle possède une unique solution, que l'on exprimera à l'aide de $A$ et $B$ .
Soit $f_{A} : 𝒫 (E) \to 𝒫 (E)$ , $X \mapsto A Δ X$ . Calculer $f_{A} \circ f_{A}$ . Que peut-on dire de $f_{A}$ ? Déduire de ce qui précède l'implication $A Δ B = A Δ C \Rightarrow B = C$ .
Application. Résoudre, dans $𝒫 ([⁣ [1, 6] ⁣])$ , l'équation ${1, 2, 3} Δ X = {2, 3, 4}$ . Puis, lorsque $E$ est fini, calculer le nombre d'éléments de $A Δ B$ en fonction de ceux de $A$ , de $B$ et de $A \cap B$ , à l'aide de l'égalité $Card A = \sum_{x \in E} 𝟙_{A} (x)$ .

Voir le corrigé

1. Soit $x \in E$ . Le produit $𝟙_{A} (x) 𝟙_{B} (x)$ vaut $1$ si et seulement si les deux facteurs valent $1$ , c'est-à-dire si $x \in A$ et $x \in B$ ; il vaut $0$ sinon. C'est donc $𝟙_{A \cap B} (x)$ . Pour $x \in A$ , $1 - 𝟙_{A} (x) = 0$ ; pour $x \notin A$ , $1 - 𝟙_{A} (x) = 1$ : on obtient $𝟙_{\overline{A}}$ . Pour la réunion, $A \cup B = \overline{\overline{A} \cap \overline{B}}$ , donc $𝟙_{A \cup B} = 1 - 𝟙_{\overline{A} \cap \overline{B}} = 1 - (1 - 𝟙_{A}) (1 - 𝟙_{B}) = 𝟙_{A} + 𝟙_{B} - 𝟙_{A} 𝟙_{B} .$ Enfin, si $A = B$ , les deux fonctions coïncident par définition. Réciproquement, si $𝟙_{A} = 𝟙_{B}$ , alors pour tout $x \in E$ : $x \in A ⟺ 𝟙_{A} (x) = 1 ⟺ 𝟙_{B} (x) = 1 ⟺ x \in B$ , donc $A = B$ . $■$

2. La réunion $(A ∖ B) \cup (B ∖ A)$ est disjointe, donc $𝟙_{A Δ B} = 𝟙_{A ∖ B} + 𝟙_{B ∖ A}$ (si $x$ est dans l'une, il n'est pas dans l'autre). Or $A ∖ B = A \cap \overline{B}$ , donc $𝟙_{A ∖ B} = 𝟙_{A} (1 - 𝟙_{B})$ et de même $𝟙_{B ∖ A} = 𝟙_{B} (1 - 𝟙_{A})$ . Ainsi $𝟙_{A Δ B} = 𝟙_{A} - 𝟙_{A} 𝟙_{B} + 𝟙_{B} - 𝟙_{A} 𝟙_{B} = 𝟙_{A} + 𝟙_{B} - 2 𝟙_{A} 𝟙_{B} . ■$ En termes de valeurs : $𝟙_{A Δ B} (x) = θ (𝟙_{A} (x), 𝟙_{B} (x))$ avec $θ (u, v) = u + v - 2 u v$ ; ce nombre vaut $1$ si $x$ est dans exactement un des deux ensembles.

3. Table de $θ$ sur ${0, 1}^{2}$ : $θ (0, 0) = 0$ , $θ (0, 1) = θ (1, 0) = 1$ , $θ (1, 1) = 1 + 1 - 2 = 0$ ; donc $θ (u, v) \in {0, 1}$ . Calculons, pour $u, v, w \in {0, 1}$ (le résultat $θ (u, v)$ est dans ${0, 1}$ , on peut donc le réinjecter dans $θ$ ) : $θ (θ (u, v), w) = (u + v - 2 u v) + w - 2 w (u + v - 2 u v) = u + v + w - 2 u v - 2 u w - 2 v w + 4 u v w .$ Cette expression est symétrique en $(u, v, w)$ . En permutant les rôles : $θ (u, θ (v, w)) = θ (θ (v, w), u)$ (car $θ (a, b) = θ (b, a)$ ), qui est la même expression avec $(v, w, u)$ , donc la même valeur. D'où l'égalité. Pour $A, B, C \subset E$ et $x \in E$ , en posant $u = 𝟙_{A} (x)$ , $v = 𝟙_{B} (x)$ , $w = 𝟙_{C} (x)$ , la question 2 donne $𝟙_{(A Δ B) Δ C} (x) = θ (θ (u, v), w) = θ (u, θ (v, w)) = 𝟙_{A Δ (B Δ C)} (x)$ . Les deux fonctions caractéristiques coïncident : par la question 1, $(A Δ B) Δ C = A Δ (B Δ C)$ . $■$ On note $A Δ B Δ C$ cet ensemble. Sa fonction caractéristique en $x$ vaut $u + v + w - 2 (u v + u w + v w) + 4 u v w$ : si $x$ est dans aucun des trois ensembles, $0$ ; dans exactement un, $1$ ; dans exactement deux, $2 - 2 = 0$ ; dans les trois, $3 - 6 + 4 = 1$ . Donc $x \in A Δ B Δ C$ si et seulement si $x$ appartient à un nombre impair de ces trois ensembles (un ou trois).

4. Commutativité : la définition est symétrique en $A$ et $B$ (réunion de $A ∖ B$ et $B ∖ A$ ). $A Δ \emptyset = (A ∖ \emptyset) \cup (\emptyset ∖ A) = A \cup \emptyset = A$ . $A Δ A = (A ∖ A) \cup (A ∖ A) = \emptyset$ . Si $B \subset A$ : $B ∖ A = \emptyset$ donc $A Δ B = A ∖ B$ . Conclusion : $Δ$ est associative, commutative, a pour élément neutre $\emptyset$ , et toute partie $A$ est son propre symétrique ( $A Δ A = \emptyset$ ).

5. Analyse. Si $X$ est solution, alors $A Δ (A Δ X) = A Δ B$ . Par associativité, $(A Δ A) Δ X = \emptyset Δ X = X$ ; donc $X = A Δ B$ . Synthèse. Posons $X = A Δ B$ . Alors $A Δ X = A Δ (A Δ B) = (A Δ A) Δ B = \emptyset Δ B = B$ : c'est bien une solution. L'équation a donc une unique solution : $X = A Δ B$ .

6. $f_{A} \circ f_{A} (X) = A Δ (A Δ X) = X$ (calcul de la question 5), donc $f_{A} \circ f_{A} = {I d}_{𝒫 (E)}$ . Une application dont la composée avec elle-même est l'identité est bijective et égale à sa réciproque (fiche, composition) : $f_{A}$ est une involution de $𝒫 (E)$ . Si $A Δ B = A Δ C$ , alors $f_{A} (B) = f_{A} (C)$ ; comme $f_{A}$ est injective, $B = C$ . $■$

7. D'après la question 5, avec $A = {1, 2, 3}$ et $B = {2, 3, 4}$ : $X = A Δ B = {1, 4}$ (éléments dans exactement un des deux ensembles ; ${2, 3}$ est dans les deux). Vérification : ${1, 2, 3} Δ {1, 4} = {2, 3, 4}$ . $✓$ Pour $E$ fini, sommons la relation de la question 2 sur tous les $x \in E$ : $Card (A Δ B) = \sum_{x} 𝟙_{A Δ B} (x) = \sum_{x} 𝟙_{A} (x) + \sum_{x} 𝟙_{B} (x) - 2 \sum_{x} 𝟙_{A \cap B} (x) .$ Le résultat est donc $n_{A} + n_{B} - 2 n_{A \cap B}$ , où $n_{Y}$ désigne le nombre d'éléments de $Y$ . (Exemple : $3 + 3 - 2 \times 2 = 2$ , qui est bien le nombre d'éléments de ${1, 4}$ .)

Après avoir comparé avec le corrigé :

Synthèse, niveau concours12 points

12. Le principe des tiroirs

Classique du programme : principe des tiroirs.

Principe des tiroirs. Soient $A$ et $B$ deux ensembles finis. Si $Card A > Card B$ , alors toute application $f : A \to B$ n'est pas injective : il existe $a \neq a^{'}$ dans $A$ tels que $f (a) = f (a^{'})$ .

(2 points) Démontrer ce principe par récurrence sur $n = Card B \geq 1$ , avec l'hypothèse $P (n)$ : « pour tout ensemble fini $A$ de cardinal strictement supérieur à $n$ et tout ensemble $B$ de cardinal $n$ , aucune application de $A$ dans $B$ n'est injective ». On utilisera que, pour $a \in A$ , $Card (A ∖ {a}) = Card A - 1$ .
Soit $n \in ℕ^{*}$ et $S$ une partie de $[⁣ [1, 2 n] ⁣]$ à $n + 1$ éléments. (a) (2 points) Montrer que $S$ contient deux entiers consécutifs, et que deux entiers de $S$ au moins sont premiers entre eux. On pourra utiliser l'application $s \mapsto E ⁣ (\frac{s + 1}{2})$ de $S$ dans $[⁣ [1, n] ⁣]$ . (b) (2 points) Montrer que $S$ contient deux entiers distincts dont l'un divise l'autre. On écrira chaque $s \in S$ sous la forme $s = 2^{α} m$ avec $m$ impair. (c) (1 point) Montrer que le nombre $n + 1$ ne peut pas être remplacé par $n$ dans (a) ni dans (b) : exhiber, dans chaque cas, une partie de $[⁣ [1, 2 n] ⁣]$ à $n$ éléments qui ne convient pas.
(2 points) On place $5$ points dans un carré de côté $2$ (bord compris). Montrer que deux d'entre eux sont à une distance au plus égale à $\sqrt{2}$ .
(3 points) Soient $n \geq 1$ et $a_{1}, \dots, a_{n}$ des entiers relatifs. Établir l'existence d'indices $0 \leq i < j \leq n$ pour lesquels $n$ divise $a_{i + 1} + \dots + a_{j}$ . Appliquer ce résultat à $n = 6$ et $(a_{1}, \dots, a_{6}) = (4, 7, 5, 9, 2, 8)$ en exhibant deux blocs de termes consécutifs de somme divisible par $6$ .

Voir le corrigé

1. Initialisation ( $n = 1$ ) : $B = {b}$ et $Card A \geq 2$ . Toute application $f : A \to B$ envoie deux éléments distincts de $A$ sur $b$ : elle n'est pas injective. Hérédité. Supposons $P (n)$ et soient $B$ de cardinal $n + 1$ , $A$ de cardinal $\geq n + 2$ et $f : A \to B$ . Raisonnons par l'absurde : supposons $f$ injective. Fixons $a_{0} \in A$ et posons $b_{0} = f (a_{0})$ , $A^{'} = A ∖ {a_{0}}$ , $B^{'} = B ∖ {b_{0}}$ . Pour $a \in A^{'}$ , $f (a) \neq f (a_{0}) = b_{0}$ par injectivité : $f$ induit une application $f^{'} : A^{'} \to B^{'}$ , injective. Or $Card A^{'} \geq n + 1 > n = Card B^{'}$ , ce qui contredit $P (n)$ . Donc $f$ n'est pas injective : $P (n + 1)$ est vraie. Par récurrence, $P (n)$ est vraie pour tout $n \geq 1$ . Si $B = \emptyset$ , aucune application n'existe depuis un ensemble non vide, et le principe est vide de sens. $■$

2. (a) Pour $s \in [⁣ [1, 2 n] ⁣]$ , $E ⁣ (\frac{s + 1}{2}) \in [⁣ [1, n] ⁣]$ : on a $1 \leq \frac{s + 1}{2} \leq n + \frac{1}{2}$ . Cette application $φ$ de $S$ (de cardinal $n + 1$ ) dans $[⁣ [1, n] ⁣]$ n'est pas injective (question 1) : il existe $s \neq s^{'}$ dans $S$ avec $φ (s) = φ (s^{'}) = j$ . Or $φ (s) = j ⟺ j \leq \frac{s + 1}{2} < j + 1 ⟺ 2 j - 1 \leq s < 2 j + 1 ⟺ s \in {2 j - 1, 2 j}$ . Donc ${s, s^{'}} = {2 j - 1, 2 j}$ : deux entiers consécutifs. Un diviseur commun $d$ de $2 j - 1$ et $2 j$ divise leur différence $1$ : leur pgcd est $1$ et ils sont premiers entre eux. $■$

(b) Pour $s \in S$ , soit $α$ le plus grand entier tel que $2^{α}$ divise $s$ (il existe : $2^{0} = 1$ divise $s$ et $2^{α} \leq s$ pour tout $α$ convenable). Alors $m = \frac{s}{2^{α}}$ est un entier impair, sinon $2^{α + 1}$ diviserait $s$ . Comme $m \leq s \leq 2 n$ , $m$ est un élément de $I = {1, 3, \dots, 2 n - 1}$ , qui a $n$ éléments. L'application $s \mapsto m$ de $S$ dans $I$ n'est pas injective : il existe $s \neq s^{'}$ de même partie impaire $m$ ; $s = 2^{α} m$ , $s^{'} = 2^{β} m$ avec $α \neq β$ (sinon $s = s^{'}$ ). Si $α < β$ , alors $s^{'} = 2^{β - α} s$ et $s$ divise $s^{'}$ (sinon, symétriquement). $■$

(c) Pour (b) : $S = {n + 1, \dots, 2 n}$ a $n$ éléments, et si $a < b$ sont dans $S$ avec $a ∣ b$ , alors $b \geq 2 a \geq 2 n + 2 > 2 n$ : impossible. Pour (a) : $S = {2, 4, \dots, 2 n}$ a $n$ éléments, et deux de ses éléments sont pairs, donc admettent le diviseur commun $2$ : aucun couple n'est premier entre eux (et aucun couple n'est consécutif). Le nombre $n + 1$ ne peut donc pas être abaissé.

3. Plaçons le carré dans un repère orthonormé, de sommets $(0, 0)$ , $(2, 0)$ , $(2, 2)$ , $(0, 2)$ . Découpons-le en quatre carrés fermés de côté $1$ : $Q_{i j} = [i, i + 1] \times [j, j + 1]$ avec $i, j \in {0, 1}$ . Chaque point appartient à au moins un $Q_{i j}$ (un point du bord commun à deux petits carrés appartient aux deux) ; choisissons-en un pour chaque point, ce qui définit une application des $5$ points dans l'ensemble des $4$ petits carrés. Par le principe des tiroirs, deux points distincts $M (x, y)$ , $M^{'} (x^{'}, y^{'})$ sont dans un même carré $Q_{i j}$ : $∣ x - x^{'} ∣ \leq 1$ et $∣ y - y^{'} ∣ \leq 1$ , donc $M M^{'} = \sqrt{(x - x^{'})^{2} + (y - y^{'})^{2}} \leq \sqrt{1 + 1} = \sqrt{2}$ . $■$

4. Posons $S_{0} = 0$ et $S_{k} = a_{1} + \dots + a_{k}$ pour $k \in [⁣ [1, n] ⁣]$ : on a $n + 1$ entiers $S_{0}, \dots, S_{n}$ . Notons $r_{k} \in [⁣ [0, n - 1] ⁣]$ le reste de $S_{k}$ lorsqu'on le divise par $n$ . L'application $k \mapsto r_{k}$ va de $[⁣ [0, n] ⁣]$ (cardinal $n + 1$ ) dans $[⁣ [0, n - 1] ⁣]$ (cardinal $n$ ) : elle n'est pas injective. Il existe donc $i < j$ avec $r_{i} = r_{j}$ , d'où $S_{j} - S_{i} = n (q_{j} - q_{i})$ , multiple de $n$ , c'est-à-dire $n ∣ a_{i + 1} + \dots + a_{j}$ . $■$ Application, $n = 6$ : $S_{0}, \dots, S_{6} = 0, 4, 11, 16, 25, 27, 35$ de restes modulo $6$ respectivement $0, 4, 5, 4, 1, 3, 5$ . On a $r_{1} = r_{3} = 4$ : $a_{2} + a_{3} = 7 + 5 = 12 = 2 \times 6$ ; et $r_{2} = r_{6} = 5$ : $a_{3} + a_{4} + a_{5} + a_{6} = 5 + 9 + 2 + 8 = 24 = 4 \times 6$ .

Après avoir comparé avec le corrigé :

Révisions prépa

Algèbre · 1re année

Logique, ensembles, applications et relations

Application du cours4 points

1. Tables de vérité, négations et quantificateurs

Dans tout l'exercice, $P$ , $Q$ , $R$ sont des assertions et $f$ une fonction de $ℝ$ dans $ℝ$ .

À l'aide de tables de vérité : (a) montrer que $[(P \Rightarrow Q) et (Q \Rightarrow R)] \Rightarrow (P \Rightarrow R)$ est une tautologie ; (b) montrer que $[P \Rightarrow (Q et R)] ⟺ [(P \Rightarrow Q) et (P \Rightarrow R)]$ est une tautologie ; (c) montrer que $(P \Rightarrow Q) \Rightarrow (Q \Rightarrow P)$ n'est pas une tautologie.
Traduire avec des quantificateurs, puis écrire la négation : (a) $f$ est périodique ; (b) $f$ est constante ; (c) $f$ s'annule au plus une fois ; (d) la suite réelle $(u_{n})$ est stationnaire.
Répondre par vrai ou faux en justifiant : (a) $\forall x \in ℝ, \exists y \in ℝ, x = y^{2} - 2$ ; (b) $\exists y \in ℝ, \forall x \in ℝ, x y = x$ ; (c) $\forall n \in ℕ, \exists m \in ℕ, n < m \leq n + 2 et m impair$ ; (d) $\exists m \in ℕ, \forall n \in ℕ, n \leq m$ ; (e) $\forall x \in ℝ, \forall y \in ℝ, (x^{2} = y^{2} \Rightarrow x = y)$ .

Voir le corrigé

1. (a) Notons $T$ l'assertion. Rappelons que $A \Rightarrow B$ n'est fausse que si $A$ est vraie et $B$ fausse.

$P$	$Q$	$R$	$P \Rightarrow Q$	$Q \Rightarrow R$	les deux	$P \Rightarrow R$	$T$
V	V	V	V	V	V	V	V
V	V	F	V	F	F	F	V
V	F	V	F	V	F	V	V
V	F	F	F	V	F	F	V
F	V	V	V	V	V	V	V
F	V	F	V	F	F	V	V
F	F	V	V	V	V	V	V
F	F	F	V	V	V	V	V

La dernière colonne ne contient que V : $T est une tautologie$ (transitivité de l'implication, fiche §2).

(b) Les deux membres ne sont faux que lorsque $P$ est vraie et que l'une au moins de $Q$ , $R$ est fausse :

$P$	$Q$	$R$	$P \Rightarrow (Q et R)$	$P \Rightarrow Q$	$P \Rightarrow R$	$(P \Rightarrow Q) et (P \Rightarrow R)$
V	V	V	V	V	V	V
V	V	F	F	V	F	F
V	F	V	F	F	V	F
V	F	F	F	F	F	F
F	⋅	⋅	V	V	V	V

2. (a) $f$ est périodique : $\exists T > 0, \forall x \in ℝ, f (x + T) = f (x)$ . Négation : $\forall T > 0, \exists x \in ℝ, f (x + T) \neq f (x)$ .

(d) $(u_{n})$ est stationnaire : $\exists N \in ℕ, \forall n \geq N, u_{n} = u_{N}$ . Négation : $\forall N \in ℕ, \exists n \geq N, u_{n} \neq u_{N}$ .

3. (a) Faux. Négation : $\exists x \in ℝ, \forall y \in ℝ, x \neq y^{2} - 2$ . Le réel $x = - 3$ convient : $y^{2} - 2 = - 3$ imposerait $y^{2} = - 1 < 0$ .

(b) Vrai : $y = 1$ convient, car $x \cdot 1 = x$ pour tout $x$ . Ici le même $y$ sert pour tous les $x$ .

(d) Faux. Négation : $\forall m \in ℕ, \exists n \in ℕ, n > m$ ; il suffit de prendre $n = m + 1$ . ( $ℕ$ n'a pas de plus grand élément.)

(e) Faux. Contre-exemple : $x = 1$ , $y = - 1$ : $x^{2} = y^{2} = 1$ mais $x \neq y$ . L'assertion devient vraie si l'on se restreint à $x, y \in ℝ_{+}$ .

Après avoir comparé avec le corrigé :

Application du cours6 points

2. Choisir son raisonnement

(Contraposée.) Soient $a, b \in ℝ$ . Montrer que : $(\forall ε > 0, a \leq b + ε) \Rightarrow a \leq b$ .
(Absurde.) (a) Montrer qu'il n'existe aucun couple $(a, b) \in ℤ^{2}$ tel que $a^{2} - 4 b = 2$ . (b) Montrer que le réel $\frac{\ln 3}{\ln 2}$ est irrationnel.
(Disjonction de cas.) Montrer que, pour tout $n \in ℤ$ , l'entier $n (n^{2} + 2)$ est divisible par $3$ .
(Contre-exemple.) L'assertion « pour tout $n \in ℕ$ , l'entier $n^{2} + n + 41$ est premier » est-elle vraie ?
(Analyse-synthèse.) Déterminer toutes les fonctions $f : ℝ \to ℝ$ telles que $\forall x, y \in ℝ, f (x) f (y) - f (x y) = x + y .$

Voir le corrigé

3. Tout entier $n$ s'écrit $3 k$ , $3 k + 1$ ou $3 k + 2$ avec $k \in ℤ$ (division euclidienne par $3$ ).

Si $n = 3 k$ : $n (n^{2} + 2) = 3 k (n^{2} + 2)$ est un multiple de $3$ .
Si $n = 3 k + 1$ : $n^{2} + 2 = 9 k^{2} + 6 k + 3 = 3 (3 k^{2} + 2 k + 1)$ , multiple de $3$ .
Si $n = 3 k + 2$ : $n^{2} + 2 = 9 k^{2} + 12 k + 6 = 3 (3 k^{2} + 4 k + 2)$ , multiple de $3$ .

Dans les trois cas, $3 ∣ n (n^{2} + 2)$ .

5. Analyse. Soit $f$ une solution.

Avec $x = y = 0$ : $f (0)^{2} - f (0) = 0$ , donc $f (0) \in {0, 1}$ .
Avec $y = 0$ et $x$ quelconque : $f (x) f (0) - f (0) = x$ , c'est-à-dire $f (0) (f (x) - 1) = x$ . Si $f (0) = 0$ , on obtient $0 = x$ pour tout réel $x$ , ce qui est faux pour $x = 1$ . Donc $f (0) = 1$ , et alors $f (x) - 1 = x$ .

Nécessairement : $f (x) = x + 1$ pour tout $x \in ℝ$ . Il y a donc au plus une solution.

Synthèse. Soit $f : x \mapsto x + 1$ . Pour tous $x, y$ : $f (x) f (y) - f (x y) = (x + 1) (y + 1) - (x y + 1) = x + y$ . Elle convient.

Conclusion : $une seule solution, f (x) = x + 1$ . Sans la synthèse, on aurait seulement prouvé que toute solution est de cette forme, pas qu'il en existe une.

Après avoir comparé avec le corrigé :

Application du cours5 points

3. Quatre récurrences

Montrer que, pour tout $n \in ℕ$ , $7$ divise $3^{2 n + 1} + 2^{n + 2}$ .
(a) Prouver l'inégalité $3^{n} \geq n^{3}$ pour chaque entier $n \geq 3$ . (b) L'hérédité de la question (a) est-elle valable à partir de $n = 2$ ? L'inégalité est-elle vraie pour $n \in {0, 1, 2}$ ?
Soit $(u_{n})$ la suite définie par $u_{0} = 2$ , $u_{1} = 3$ et $u_{n + 2} = 3 u_{n + 1} - 2 u_{n}$ pour tout $n \in ℕ$ . Montrer que $u_{n} = 2^{n} + 1$ pour tout $n \in ℕ$ .
Soit $(v_{n})$ la suite définie par $v_{0} = 1$ et, pour tout $n \in ℕ$ , $v_{n + 1} = v_{0} + v_{1} + \dots + v_{n}$ . (a) Calculer $v_{1}$ , $v_{2}$ , $v_{3}$ , $v_{4}$ et conjecturer une formule pour $n \geq 1$ . (b) Démontrer la conjecture par récurrence forte. (c) Retrouver le résultat par une récurrence simple, en comparant $v_{n + 1}$ et $v_{n}$ .

Voir le corrigé

1. Soit $P (n)$ : « $7 ∣ 3^{2 n + 1} + 2^{n + 2}$ ».

Initialisation : $3^{1} + 2^{2} = 7$ , donc $P (0)$ est vraie.
Hérédité : soit $n \in ℕ$ tel que $P (n)$ ; écrivons $3^{2 n + 1} + 2^{n + 2} = 7 k$ avec $k \in ℤ$ . Alors $3^{2 n + 3} + 2^{n + 3} = 9 \cdot 3^{2 n + 1} + 2 \cdot 2^{n + 2} = 9 (3^{2 n + 1} + 2^{n + 2}) - 7 \cdot 2^{n + 2} = 7 (9 k - 2^{n + 2}),$ donc $P (n + 1)$ est vraie.

Par récurrence, $7 ∣ 3^{2 n + 1} + 2^{n + 2} pour tout n \in ℕ$ .

2. (a) Soit $P (n)$ : « $3^{n} \geq n^{3}$ », pour $n \geq 3$ .

Initialisation : $3^{3} = 27 = 3^{3}$ , donc $P (3)$ est vraie (avec égalité).
Hérédité : soit $n \geq 3$ tel que $3^{n} \geq n^{3}$ . Alors $3^{n + 1} = 3 \cdot 3^{n} \geq 3 n^{3}$ . Il reste à voir que $3 n^{3} \geq (n + 1)^{3}$ . Comme $n \geq 3$ , on a $1 + \frac{1}{n} \leq \frac{4}{3}$ , donc $(n + 1)^{3} = n^{3} {(1 + \frac{1}{n})}^{3} \leq \frac{64}{27} n^{3} \leq 3 n^{3}$ , car $64 \leq 81$ . Ainsi $3^{n + 1} \geq (n + 1)^{3}$ .

Par récurrence, $3^{n} \geq n^{3} pour tout n \geq 3$ .

3. Le terme $u_{n + 2}$ dépend de deux termes précédents : on fait une récurrence double. Soit $P (n)$ : « $u_{n} = 2^{n} + 1$ ».

Initialisation : $u_{0} = 2 = 2^{0} + 1$ et $u_{1} = 3 = 2^{1} + 1$ : $P (0)$ et $P (1)$ sont vraies.
Hérédité : soit $n \in ℕ$ tel que $P (n)$ et $P (n + 1)$ . Alors $u_{n + 2} = 3 (2^{n + 1} + 1) - 2 (2^{n} + 1) = 6 \cdot 2^{n} - 2 \cdot 2^{n} + 3 - 2 = 4 \cdot 2^{n} + 1 = 2^{n + 2} + 1.$

Donc $P (n + 2)$ est vraie et, par récurrence double, $u_{n} = 2^{n} + 1 pour tout n$ .

4. (a) $v_{1} = v_{0} = 1$ ; $v_{2} = v_{0} + v_{1} = 2$ ; $v_{3} = 1 + 1 + 2 = 4$ ; $v_{4} = 1 + 1 + 2 + 4 = 8$ . Conjecture : $v_{n} = 2^{n - 1}$ pour $n \geq 1$ .

(b) Soit $P (n)$ : « $v_{n} = 2^{n - 1}$ », pour $n \geq 1$ .

Initialisation : $v_{1} = 1 = 2^{0}$ .
Hérédité forte : soit $n \geq 1$ tel que $P (k)$ soit vraie pour tout $k \in [⁣ [1, n] ⁣]$ . Alors, avec la somme géométrique $1 + 2 + \dots + 2^{n - 1} = 2^{n} - 1$ : $v_{n + 1} = v_{0} + \sum_{k = 1}^{n} v_{k} = 1 + \sum_{k = 1}^{n} 2^{k - 1} = 1 + (2^{n} - 1) = 2^{n} .$

Donc $P (n + 1)$ est vraie et, par récurrence forte, $v_{n} = 2^{n - 1} pour tout n \geq 1$ . La récurrence est forte parce que $v_{n + 1}$ utilise tous les termes précédents.

Après avoir comparé avec le corrigé :

Application du cours5 points

4. Ensembles, images, injections : des exemples concrets

Dans $E = [⁣ [1, 8] ⁣]$ , on considère $A = {1, 2, 3, 4}$ , $B = {2, 4, 6, 8}$ et $C = {3, 4, 5}$ . Déterminer $A \cap B$ , $A \cup C$ , $∁_{E} B$ , $A ∖ B$ , $A Δ B$ , $𝒫 (A \cap B)$ , et vérifier l'égalité $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ sur cet exemple.
Soit $f : ℝ \to ℝ$ , $x \mapsto x^{2} - 2 x$ . (a) Déterminer $f ([0, 3])$ et $f ([- 1, 1])$ . (b) Déterminer $f^{- 1} ({3})$ , $f^{- 1} ([- 1, 0])$ et $f^{- 1} (] - \infty, - 2])$ . (c) $f$ est-elle injective ? surjective ? (d) Montrer que $g : [1, + \infty [\to [- 1, + \infty [$ , $x \mapsto x^{2} - 2 x$ , est bijective et expliciter $g^{- 1}$ .
Soient $f, g : ℕ \to ℕ$ définies par $f (n) = n + 3$ , et $g (n) = n - 3$ si $n \geq 3$ , $g (n) = 0$ si $n \leq 2$ . (a) Calculer $g \circ f$ et $f \circ g$ . (b) Étudier l'injectivité et la surjectivité de $f$ et de $g$ . (c) Que retenir de cet exemple ?

Voir le corrigé

2. Forme canonique : $f (x) = (x - 1)^{2} - 1$ . Donc $f$ est strictement décroissante sur $] - \infty, 1]$ , strictement croissante sur $[1, + \infty [$ , de minimum $f (1) = - 1$ .

(c) $f (- 1) = f (3) = 3$ avec $- 1 \neq 3$ : $f$ n'est pas injective. Le réel $- 2$ n'a pas d'antécédent (question (b)) : $f$ n'est pas surjective.

(c) L'égalité $g \circ f = {I d}_{E}$ seule ne rend ni $f$ ni $g$ bijective ; il faut aussi $f \circ g = {I d}_{F}$ pour conclure.

Après avoir comparé avec le corrigé :

Niveau devoir7 points

5. Parties saturées par une application

Soit $f : E \to F$ une application. Une partie $A$ de $E$ est dite saturée (pour $f$ ) si $f^{- 1} (f (A)) = A$ .

Montrer que $A \subset f^{- 1} (f (A))$ pour toute partie $A$ de $E$ .
Soit $B \subset F$ . Montrer que $f (f^{- 1} (B)) \subset B$ , puis que $f^{- 1} (B)$ est saturée.
En déduire qu'une partie $A$ de $E$ est saturée si et seulement s'il existe $B \subset F$ tel que $A = f^{- 1} (B)$ .
Soient $A$ et $A^{'}$ deux parties saturées. Montrer que $A \cup A^{'}$ , $A \cap A^{'}$ et $∁_{E} A$ sont saturées.
Établir l'équivalence : $f$ injective $⟺$ chaque partie de $E$ est saturée.
Dans cette question, $E = F = ℝ$ et $f (x) = x^{2}$ . (a) Déterminer $f^{- 1} (f ([- 1, 2]))$ . La partie $[- 1, 2]$ est-elle saturée ? (b) Montrer qu'une partie $A$ de $ℝ$ est saturée si et seulement si elle est symétrique, c'est-à-dire : $\forall x \in ℝ, x \in A ⟺ - x \in A$ .

Voir le corrigé

1. Soit $x \in A$ . Alors $f (x) \in f (A)$ par définition de l'image directe, donc $x \in f^{- 1} (f (A))$ par définition de l'image réciproque. D'où $A \subset f^{- 1} (f (A))$ .

Après avoir comparé avec le corrigé :

Niveau devoir7 points

6. Composition, projections et involutions

Partie A (résultats du cours). On considère deux applications $f : E \to F$ et $g : F \to G$ .

Prouver que l'injectivité de $g \circ f$ entraîne celle de $f$ .
Prouver que la surjectivité de $g \circ f$ entraîne celle de $g$ .

Voir le corrigé

Après avoir comparé avec le corrigé :

Niveau devoir7 points

7. Une relation d'équivalence et ses classes

Partie A. Soit $f : E \to F$ . On définit sur $E$ la relation $x ℛ y ⟺ f (x) = f (y)$ .

Prouver que $ℛ$ est réflexive, symétrique et transitive, et que la classe de $x$ est $c l (x) = f^{- 1} ({f (x)})$ .
Montrer que la correspondance $φ : E / ℛ \to f (E)$ , $c l (x) \mapsto f (x)$ définit bien une application (c'est-à-dire que $f (x)$ ne dépend pas du représentant choisi dans la classe), puis qu'elle est bijective.

Voir le corrigé

3. $x 𝒮 y ⟺ h (x) = h (y)$ : c'est la relation de la partie A pour $f = h$ , donc une relation d'équivalence.

4. $x^{3} - y^{3} = (x - y) (x^{2} + x y + y^{2})$ et $- 3 x + 3 y = - 3 (x - y)$ , d'où $h (x) - h (y) = (x - y) (x^{2} + x y + y^{2} - 3)$ .

5. D'après la question 4, $y \in c l (x) ⟺ y = x$ ou $y^{2} + x y + x^{2} - 3 = 0$ .

$x = 2$ : $y^{2} + 2 y + 1 = 0 ⟺ y = - 1$ . Donc $c l (2) = {- 1, 2}$ (vérification : $h (- 1) = h (2) = 2$ ).
$x = 1$ : $y^{2} + y - 2 = 0 ⟺ (y - 1) (y + 2) = 0$ . Donc $c l (1) = {- 2, 1}$ ( $h (1) = h (- 2) = - 2$ ).
$x = 0$ : $y^{2} = 3$ . Donc $c l (0) = {- \sqrt{3}, 0, \sqrt{3}}$ .
$x = 3$ : $y^{2} + 3 y + 6 = 0$ a pour discriminant $9 - 24 < 0$ : aucune solution réelle. Donc $c l (3) = {3}$ .

$h (x) - 2 = x^{3} - 3 x - 2 = (x + 1)^{2} (x - 2)$ , donc $h (x) > 2 ⟺ x > 2$ et $h (x) = 2 ⟺ x \in {- 1, 2}$ ;
$h (x) + 2 = x^{3} - 3 x + 2 = (x - 1)^{2} (x + 2)$ , donc $h (x) < - 2 ⟺ x < - 2$ et $h (x) = - 2 ⟺ x \in {- 2, 1}$ .

Après avoir comparé avec le corrigé :

Niveau devoir6 points

8. Deux relations d'ordre

Partie A. On définit sur $ℝ$ la relation $x ≼ y ⟺ y - x \in ℕ$ .

Vérifier que $≼$ définit un ordre sur $ℝ$ .
Deux réels sont-ils toujours comparables ? Déterminer l'ensemble des réels comparables à $0$ .
Soit $A = {\frac{1}{2}, 2, \frac{7}{2}, 3}$ . On dit que $a \in A$ est un élément maximal de $A$ s'il n'existe aucun $b \in A$ tel que $a ≼ b$ et $b \neq a$ . (a) $A$ admet-elle un majorant dans $(ℝ, ≼)$ ? un plus grand élément ? (b) Déterminer les éléments maximaux de $A$ .

Voir le corrigé

Après avoir comparé avec le corrigé :

Synthèse, niveau concours10 points

9. Problème : point fixe sur $𝒫 (E)$ et théorème de Cantor-Bernstein

Montrer que $ℱ$ n'est pas vide.
Montrer que $Φ (M) \subset M$ .
Montrer que $Φ (M) \in ℱ$ , puis que $Φ (M) = M$ . Montrer enfin que $M$ est inclus dans toute partie $X$ telle que $Φ (X) = X$ .

Voir le corrigé

1. $Φ (E)$ est une partie de $E$ , donc $Φ (E) \subset E$ et $E \in ℱ$ .

5. $M = Φ (M) = E ∖ g (F ∖ f (M))$ ; en passant au complémentaire : $E ∖ M = g (F ∖ f (M))$ .

7. Soient $x, x^{'} \in E$ tels que $h (x) = h (x^{'})$ . Remarquons que $h (M) = f (M)$ et $h (E ∖ M) \subset F ∖ f (M)$ : ces deux ensembles sont disjoints.

Si $x, x^{'} \in M$ : $f (x) = f (x^{'})$ et $f$ est injective, donc $x = x^{'}$ .
Si $x, x^{'} \notin M$ : en notant $y = h (x) = h (x^{'})$ , on a $x = g (y) = x^{'}$ .
Si $x \in M$ et $x^{'} \notin M$ (ou l'inverse) : $h (x) \in f (M)$ et $h (x^{'}) \notin f (M)$ , donc $h (x) \neq h (x^{'})$ ; ce cas est impossible.

Donc $h est injective$ .

10. Notons $S = {4^{k} m ∣ k \in ℕ, m \in I}$ .

$S$ est un point fixe : $Φ (S) = I \cup {4^{k + 1} m ∣ k \in ℕ, m \in I}$ ; le premier ensemble correspond à $k = 0$ et le second à $k \geq 1$ , donc $Φ (S) = S$ . Par la question 3, $M \subset S$ .
$S \subset M$ : soit $X \in ℱ$ , c'est-à-dire $I \cup f (X) \subset X$ . Montrons par récurrence sur $k$ que $4^{k} m \in X$ pour tout $m \in I$ . Pour $k = 0$ , $m \in I \subset X$ . Si $4^{k} m \in X$ , alors $4^{k + 1} m = f (4^{k} m) \in f (X) \subset X$ . Donc $S \subset X$ pour tout $X \in ℱ$ , d'où $S \subset M$ .

Après avoir comparé avec le corrigé :

Synthèse, niveau concours10 points

10. Problème : la relation d'équivalence engendrée par une application

Partie A — Propriétés générales.

Montrer que $f^{n + m} = f^{n} \circ f^{m}$ pour tous $n, m \in ℕ$ .
Prouver que $\sim$ est réflexive, symétrique et transitive.
Soit $x \in E$ . Montrer que $f^{n} (x) \in c l (x)$ pour tout $n \in ℕ$ , puis que $f^{- 1} (c l (x)) = c l (x)$ .

$x$	1	2	3	4	5	6	7	8
$f (x)$	2	3	1	5	4	6	6	7

Déterminer les classes.

Partie C — Cas bijectif. 7. On suppose $f$ bijective. Montrer que $x \sim y$ si et seulement s'il existe $n \in ℕ$ tel que $y = f^{n} (x)$ ou $x = f^{n} (y)$ .

Voir le corrigé

5. Soit $P (x)$ : « il existe $p \in ℕ$ tel que $f^{p} (x) = 0$ ».

$P (0)$ est vraie avec $p = 0$ .
Soit $x \geq 0$ tel que $P (k)$ soit vraie pour tout $k \in [⁣ [0, x] ⁣]$ . Considérons $x + 1 \geq 1$ : $f (x + 1) = E ⁣ (\frac{x + 1}{2}) \leq \frac{x + 1}{2} < x + 1$ , donc $k = f (x + 1) \in [⁣ [0, x] ⁣]$ . Par hypothèse il existe $p$ tel que $f^{p} (k) = 0$ , et alors $f^{p + 1} (x + 1) = f^{p} (f (x + 1)) = 0$ .

Si $p \geq q$ : $f^{q} (f^{p - q} (x)) = f^{p} (x) = f^{q} (y)$ , donc $f^{p - q} (x) = y$ par injectivité de $f^{q}$ ; on prend $n = p - q$ .
Si $p < q$ : de même $f^{p} (x) = f^{p} (f^{q - p} (y))$ donne $x = f^{q - p} (y)$ ; on prend $n = q - p$ .

Lorsque $f$ est une bijection d'un ensemble fini, les classes sont les « cycles » de $f$ : c'est le point de départ de l'étude des permutations dans le chapitre « Structures algébriques ».

Après avoir comparé avec le corrigé :

Synthèse, niveau concours10 points

11. Problème : fonctions caractéristiques et différence symétrique

Classique du programme : fonction caractéristique (indicatrice). Classique du programme : différence symétrique.

Partie A — Calculs avec les fonctions caractéristiques (3 points)

Montrer que $𝟙_{A \cap B} = 𝟙_{A} 𝟙_{B}$ et $𝟙_{\overline{A}} = 1 - 𝟙_{A}$ , puis que $𝟙_{A \cup B} = 𝟙_{A} + 𝟙_{B} - 𝟙_{A} 𝟙_{B}$ . Montrer enfin que $A = B ⟺ 𝟙_{A} = 𝟙_{B}$ .
Établir que $𝟙_{A Δ B} = 𝟙_{A} + 𝟙_{B} - 2 𝟙_{A} 𝟙_{B}$ .

Partie B — Structure de $(𝒫 (E), Δ)$ (4 points)

Pour $u, v, w \in {0, 1}$ , on pose $θ (u, v) = u + v - 2 u v$ . Vérifier que $θ (u, v) \in {0, 1}$ , puis que $θ (θ (u, v), w) = θ (u, θ (v, w))$ . En déduire que, pour $A, B, C \subset E$ , $(A Δ B) Δ C = A Δ (B Δ C)$ . Décrire l'ensemble $A Δ B Δ C$ à l'aide du nombre de parties parmi $A, B, C$ qui contiennent un élément donné.
Montrer que $A Δ B = B Δ A$ , $A Δ \emptyset = A$ et $A Δ A = \emptyset$ . Que dire de $A Δ B$ lorsque $B \subset A$ ?

Partie C — L'équation $A Δ X = B$ (3 points)

Ici, les parties $A$ et $B$ de $E$ sont fixées, et l'on cherche les parties $X$ de $E$ telles que $A Δ X = B$ .

Résoudre l'équation, par analyse et synthèse : montrer qu'elle possède une unique solution, que l'on exprimera à l'aide de $A$ et $B$ .
Soit $f_{A} : 𝒫 (E) \to 𝒫 (E)$ , $X \mapsto A Δ X$ . Calculer $f_{A} \circ f_{A}$ . Que peut-on dire de $f_{A}$ ? Déduire de ce qui précède l'implication $A Δ B = A Δ C \Rightarrow B = C$ .
Application. Résoudre, dans $𝒫 ([⁣ [1, 6] ⁣])$ , l'équation ${1, 2, 3} Δ X = {2, 3, 4}$ . Puis, lorsque $E$ est fini, calculer le nombre d'éléments de $A Δ B$ en fonction de ceux de $A$ , de $B$ et de $A \cap B$ , à l'aide de l'égalité $Card A = \sum_{x \in E} 𝟙_{A} (x)$ .

Voir le corrigé

Après avoir comparé avec le corrigé :

Synthèse, niveau concours12 points

12. Le principe des tiroirs

Classique du programme : principe des tiroirs.

(2 points) Démontrer ce principe par récurrence sur $n = Card B \geq 1$ , avec l'hypothèse $P (n)$ : « pour tout ensemble fini $A$ de cardinal strictement supérieur à $n$ et tout ensemble $B$ de cardinal $n$ , aucune application de $A$ dans $B$ n'est injective ». On utilisera que, pour $a \in A$ , $Card (A ∖ {a}) = Card A - 1$ .
Soit $n \in ℕ^{*}$ et $S$ une partie de $[⁣ [1, 2 n] ⁣]$ à $n + 1$ éléments. (a) (2 points) Montrer que $S$ contient deux entiers consécutifs, et que deux entiers de $S$ au moins sont premiers entre eux. On pourra utiliser l'application $s \mapsto E ⁣ (\frac{s + 1}{2})$ de $S$ dans $[⁣ [1, n] ⁣]$ . (b) (2 points) Montrer que $S$ contient deux entiers distincts dont l'un divise l'autre. On écrira chaque $s \in S$ sous la forme $s = 2^{α} m$ avec $m$ impair. (c) (1 point) Montrer que le nombre $n + 1$ ne peut pas être remplacé par $n$ dans (a) ni dans (b) : exhiber, dans chaque cas, une partie de $[⁣ [1, 2 n] ⁣]$ à $n$ éléments qui ne convient pas.
(2 points) On place $5$ points dans un carré de côté $2$ (bord compris). Montrer que deux d'entre eux sont à une distance au plus égale à $\sqrt{2}$ .
(3 points) Soient $n \geq 1$ et $a_{1}, \dots, a_{n}$ des entiers relatifs. Établir l'existence d'indices $0 \leq i < j \leq n$ pour lesquels $n$ divise $a_{i + 1} + \dots + a_{j}$ . Appliquer ce résultat à $n = 6$ et $(a_{1}, \dots, a_{6}) = (4, 7, 5, 9, 2, 8)$ en exhibant deux blocs de termes consécutifs de somme divisible par $6$ .

Voir le corrigé

Après avoir comparé avec le corrigé :

$P$	$Q$	$R$	$P \Rightarrow Q$	$Q \Rightarrow R$	les deux	$P \Rightarrow R$	$T$
V	V	V	V	V	V	V	V
V	V	F	V	F	F	F	V
V	F	V	F	V	F	V	V
V	F	F	F	V	F	F	V
F	V	V	V	V	V	V	V
F	V	F	V	F	F	V	V
F	F	V	V	V	V	V	V
F	F	F	V	V	V	V	V

$P$	$Q$	$R$	$P \Rightarrow Q$	$Q \Rightarrow R$	les deux	$P \Rightarrow R$	$T$
V	V	V	V	V	V	V	V
V	V	F	V	F	F	F	V
V	F	V	F	V	F	V	V
V	F	F	F	V	F	F	V
F	V	V	V	V	V	V	V
F	V	F	V	F	F	V	V
F	F	V	V	V	V	V	V
F	F	F	V	V	V	V	V

$P$	$Q$	$R$	$P \Rightarrow Q$	$Q \Rightarrow R$	les deux	$P \Rightarrow R$	$T$
V	V	V	V	V	V	V	V
V	V	F	V	F	F	F	V
V	F	V	F	V	F	V	V
V	F	F	F	V	F	F	V
F	V	V	V	V	V	V	V
F	V	F	V	F	F	V	V
F	F	V	V	V	V	V	V
F	F	F	V	V	V	V	V

$P$	$Q$	$R$	$P \Rightarrow Q$	$Q \Rightarrow R$	les deux	$P \Rightarrow R$	$T$
V	V	V	V	V	V	V	V
V	V	F	V	F	F	F	V
V	F	V	F	V	F	V	V
V	F	F	F	V	F	F	V
F	V	V	V	V	V	V	V
F	V	F	V	F	F	V	V
F	F	V	V	V	V	V	V
F	F	F	V	V	V	V	V

1. Tables de vérité, négations et quantificateurs

2. Choisir son raisonnement

3. Quatre récurrences

4. Ensembles, images, injections : des exemples concrets

5. Parties saturées par une application

6. Composition, projections et involutions

7. Une relation d'équivalence et ses classes

8. Deux relations d'ordre

9. Problème : point fixe sur 𝒫(E) et théorème de Cantor-Bernstein

10. Problème : la relation d'équivalence engendrée par une application

11. Problème : fonctions caractéristiques et différence symétrique

12. Le principe des tiroirs

1. Tables de vérité, négations et quantificateurs

2. Choisir son raisonnement

3. Quatre récurrences

4. Ensembles, images, injections : des exemples concrets

5. Parties saturées par une application

6. Composition, projections et involutions

7. Une relation d'équivalence et ses classes

8. Deux relations d'ordre

9. Problème : point fixe sur 𝒫(E) et théorème de Cantor-Bernstein

10. Problème : la relation d'équivalence engendrée par une application

11. Problème : fonctions caractéristiques et différence symétrique

12. Le principe des tiroirs

9. Problème : point fixe sur $𝒫 (E)$ et théorème de Cantor-Bernstein

9. Problème : point fixe sur $𝒫 (E)$ et théorème de Cantor-Bernstein

$P$	$Q$	$R$	$P \Rightarrow Q$	$Q \Rightarrow R$	les deux	$P \Rightarrow R$	$T$
V	V	V	V	V	V	V	V
V	V	F	V	F	F	F	V
V	F	V	F	V	F	V	V
V	F	F	F	V	F	F	V
F	V	V	V	V	V	V	V
F	V	F	V	F	F	V	V
F	F	V	V	V	V	V	V
F	F	F	V	V	V	V	V

$P$	$Q$	$R$	$P \Rightarrow Q$	$Q \Rightarrow R$	les deux	$P \Rightarrow R$	$T$
V	V	V	V	V	V	V	V
V	V	F	V	F	F	F	V
V	F	V	F	V	F	V	V
V	F	F	F	V	F	F	V
F	V	V	V	V	V	V	V
F	V	F	V	F	F	V	V
F	F	V	V	V	V	V	V
F	F	F	V	V	V	V	V