---
title: "Logique, ensembles et applications"
book: "Mathématiques universitaires — Licence 1"
subject: math
language: fr
chapter: 1
exercises: 12
source: https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications
---

# Chapitre 1 — Logique, ensembles et applications

Jusqu’ici, les démonstrations ont été menées avec une idée informelle mais honnête de ce que « démontrer » veut dire. Ce premier chapitre de mathématiques du supérieur explicite les règles du jeu : ce qu’est une [assertion](#def-b1-logic-statement) mathématique, comment les connecteurs et les quantificateurs combinent les [assertions](#def-b1-logic-statement), quels coups sont autorisés dans une démonstration — puis construit, sur cette base, les deux langages universels des mathématiques : les [ensembles](#def-b1-logic-sets) et les [applications](#def-b1-logic-map).

## 1.1 Assertions et connecteurs

**Définition 1.1 (Assertion, connecteurs).**

Une *assertion* (ou *proposition*) est une phrase qui est soit vraie (V), soit fausse (F) — exactement l’une des deux. À partir de deux assertions $P$ et $Q$, on forme :

- la *négation* $\lnot P$ (« non $P$ »), vraie exactement quand $P$ est fausse ;
- la *conjonction* $P \land Q$ (« $P$ et $Q$ »), vraie exactement quand les deux sont vraies ;
- la *disjonction* $P \lor Q$ (« $P$ ou $Q$ »), vraie exactement quand l’une au moins est vraie (ce « ou » est inclusif) ;
- l’ *implication* $P \implies Q$ , fausse exactement quand $P$ est vraie et $Q$ fausse ;
- l’ *équivalence* $P \iff Q$ , vraie exactement quand $P$ et $Q$ ont la même valeur de vérité.

**Remarque 1.2.**

La table de vérité de $P \implies Q$ mérite qu’on s’y arrête : quand $P$ est fausse, $P \implies Q$ est *vraie*, quel que soit $Q$. « Si $2 < 1$ alors $0 = 5$ » est une implication vraie. Une implication n’affirme rien sur ce qui se passe quand son hypothèse est en défaut.

**Proposition 1.3 (Règles de calcul sur les assertions).**

Pour toutes [assertions](#def-b1-logic-statement) $P$, $Q$, $R$ :

1. $\lnot(\lnot P) \iff P$ ;
2. [lois de De Morgan](#prop-b1-logic-rules) : $\lnot(P \land Q) \iff (\lnot P) \lor (\lnot Q)$ et $\lnot(P \lor Q) \iff (\lnot P) \land (\lnot Q)$ ;
3. $(P \implies Q) \iff \bigl((\lnot P) \lor Q\bigr)$ , d’où $\lnot(P \implies Q) \iff P \land (\lnot Q)$ ;
4. contraposition : $(P \implies Q) \iff \bigl((\lnot Q) \implies (\lnot P)\bigr)$ ;
5. $(P \iff Q) \iff \bigl((P \implies Q) \land (Q \implies  P)\bigr)$ ;
6. distributivité : $P \land (Q \lor R) \iff (P \land Q) \lor  (P \land R)$ et $P \lor (Q \land R) \iff (P \lor Q) \land  (P \lor R)$ .

**Démonstration.** Chaque équivalence se vérifie en comparant des tables de vérité : deux [assertions](#def-b1-logic-statement) composées construites à partir de $P$, $Q$, $R$ sont équivalentes exactement lorsqu’elles prennent la même valeur de vérité dans chacun des (quatre ou huit) cas. Écrivons une table en entier, pour la première loi de De Morgan :

| $P$ | $Q$ | $P \land Q$ | $\lnot(P \land Q)$ | $\lnot P$ | $\lnot Q$ | $(\lnot P) \lor (\lnot Q)$ |
| --- | --- | --- | --- | --- | --- | --- |
| V | V | V | F | F | F | F |
| V | F | F | V | F | V | V |
| F | V | F | V | V | F | V |
| F | F | F | V | V | V | V |

Les colonnes $4$ et $7$ coïncident, ce qui démontre la loi. Pour la contraposition, un raccourci verbal va plus vite : $P \implies Q$ est fausse exactement dans le cas ($P$ vraie, $Q$ fausse), et $(\lnot Q) \implies (\lnot P)$ est fausse exactement dans le cas ($\lnot Q$ vraie, $\lnot P$ fausse), c’est-à-dire ($Q$ fausse, $P$ vraie) — le même cas unique, donc les deux implications ont des tables identiques. Les autres règles se vérifient de la même façon ; notons que (3) ramène toute implication à une disjonction, si bien que (2) produit mécaniquement la règle de négation $\lnot(P \implies Q) \iff P
\land (\lnot Q)$ : pour contredire une implication, il faut exhiber un cas où l’hypothèse est vérifiée et la conclusion en défaut. ∎

## 1.2 Quantificateurs

**Définition 1.4 (Quantificateurs).**

Soit $P(x)$ une propriété d’un élément $x$ d’un [ensemble](#def-b1-logic-sets) $E$.

- $\forall x \in E,\ P(x)$ (« pour tout $x$ de $E$ , $P(x)$ ») est vraie quand tout élément de $E$ vérifie $P$ ;
- $\exists x \in E,\ P(x)$ (« il existe $x$ dans $E$ tel que $P(x)$ ») est vraie quand au moins un élément de $E$ vérifie $P$ .

On écrit $\exists!$ pour « il existe un unique ».

**Proposition 1.5 (Négation des quantificateurs).**

$$
\lnot\bigl(\forall x \in E,\ P(x)\bigr) \iff
\exists x \in E,\ \lnot P(x),
\qquad
\lnot\bigl(\exists x \in E,\ P(x)\bigr) \iff
\forall x \in E,\ \lnot P(x).
$$

**Démonstration.** Démontrons la première équivalence dans les deux sens ; la seconde est symétrique. Si $\forall x \in E,\ P(x)$ est fausse, alors les éléments de $E$ ne vérifient pas tous $P$ : l’[ensemble](#def-b1-logic-sets) $A = \{x \in E : \lnot P(x)\}$ ne peut être vide, et n’importe lequel de ses éléments témoigne de $\exists x \in E,\ \lnot P(x)$. Réciproquement, si un certain $x_0 \in
E$ vérifie $\lnot P(x_0)$, alors $x_0$ est un contre-exemple et l’[assertion](#def-b1-logic-statement) universelle est en défaut. Pour la seconde règle : « aucun $x$ ne vérifie $P$ » signifie que l’[ensemble](#def-b1-logic-sets) $\{x : P(x)\}$ est vide, c’est-à-dire que tout $x$ appartient à son complémentaire $A$. Appliquées en cascade à un préfixe de quantificateurs imbriqués, les deux règles donnent le procédé mécanique de l’[Exemple 1.8](#ex-b1-logic-limit) : la négation parcourt la phrase de gauche à droite, échangeant chaque $\forall$ en $\exists$ et chaque $\exists$ en $\forall$, et nie finalement le prédicat le plus intérieur. ∎

**Exemple 1.6 (Nier des phrases mathématiques courantes).**

Soit $f \colon \R \to \R$. La phrase « $f$ est croissante » s’écrit

$$
\forall x \in \R,\ \forall y \in \R,\quad
x \leq y \implies f(x) \leq f(y) ,
$$

et sa négation, d’après la [Proposition 1.5](#prop-b1-logic-negquant) et la règle $\lnot(P \implies Q) \iff P \land \lnot Q$ :

$$
\exists x \in \R,\ \exists y \in \R,\quad
x \leq y \ \text{ et }\ f(x) > f(y) :
$$

un seul couple témoin suffit. De même, « $f$ est bornée » s’écrit $\exists M \in \R,\ \forall x \in \R,\ \abs{f(x)} \leq M$, de négation

$$
\forall M \in \R,\ \exists x \in \R,\quad \abs{f(x)} > M :
$$

*quelle que soit* la borne proposée, un point la dépasse. L’idée à retenir : une négation correcte ne contient jamais de « non » appliqué à un bloc quantifié — c’est une nouvelle [assertion](#def-b1-logic-statement) positive, dans laquelle les rôles sont échangés : on produit désormais les témoins qu’on recevait auparavant.

**Exemple 1.7 (Ordre des quantificateurs).**

L’[ordre](#def-b1-logic-order) de deux quantificateurs différents compte :

$$
\forall x \in \R,\ \exists y \in \R,\ y > x
\quad\text{est vraie (prendre } y = x+1\text{),}
$$

$$
\exists y \in \R,\ \forall x \in \R,\ y > x
\quad\text{est fausse (aucun réel ne dépasse tous les réels).}
$$

Dans la première [assertion](#def-b1-logic-statement), $y$ peut dépendre de $x$ ; dans la seconde, un seul et même $y$ doit convenir pour tous les $x$. Deux quantificateurs identiques, en revanche, commutent toujours.

**Exemple 1.8 (Lire une définition à trois quantificateurs).**

La phrase « la suite $(u_n)$ converge vers $\ell$ » s’écrira dans le [Chapitre 11](https://one-course.com/books/math/3/fr/chapter/11-suites#ch-b1-seq) sous la forme

$$
\forall \varepsilon > 0,\ \exists N \in \N,\ \forall n \geq N,\quad
\abs{u_n - \ell} \leq \varepsilon .
$$

Sa négation, par la [Proposition 1.5](#prop-b1-logic-negquant) appliquée trois fois, est

$$
\exists \varepsilon > 0,\ \forall N \in \N,\ \exists n \geq N,\quad
\abs{u_n - \ell} > \varepsilon .
$$

Savoir nier de telles phrases mécaniquement, sans réfléchir à ce qu’elles signifient, est une véritable compétence : elle sépare le travail logique du travail mathématique.

## 1.3 Techniques de démonstration

**Méthode 1.9 (Les schémas de démonstration usuels).**

Pour démontrer…

1. *une implication $P \implies Q$ directement* : supposer $P$ , en déduire $Q$ ;
2. *par contraposition* : supposer $\lnot Q$ , en déduire $\lnot P$ — licite d’après la [Proposition 1.3](#prop-b1-logic-rules) (4) ;
3. *par l’absurde* : supposer l’ [assertion](#def-b1-logic-statement) fausse, en tirer une contradiction ;
4. *une équivalence* : démontrer les deux implications séparément (ou enchaîner des équivalences connues) ;
5. *une [assertion](#def-b1-logic-statement) « pour tout »* : se donner un $x$ *quelconque* de $E$ (« soit $x \in E$ ») et démontrer $P(x)$ ;
6. *une [assertion](#def-b1-logic-statement) « il existe »* : exhiber un témoin, ou démontrer l’existence indirectement ;
7. *par récurrence* : voir [Théorème 1.12](#thm-b1-logic-induction) .

Lorsqu’on démontre une [assertion](#def-b1-logic-statement) portant sur un élément quelconque mais bien choisi, il ne faut jamais lui prêter de propriétés supplémentaires : « soit $x \in \R$ » suivi de « comme $x > 0$… » ne démontre rien sur les $x$ négatifs.

**Remarque 1.10 (Pièges classiques des démonstrations).**

Quatre traquenards classiques, qu’il vaut la peine de nommer une fois.

1. *La réciproque à la place de la contraposée.* $Q \implies  P$ n’est *pas* équivalente à $P \implies Q$ ; seule $\lnot Q \implies \lnot P$ l’est. « S’il pleut, la rue est mouillée » n’autorise pas à conclure qu’il pleut d’une rue mouillée.
2. *Démontrer une équivalence par une seule implication.* Une affirmation « si et seulement si » est deux théorèmes ; annoncer quel sens on démontre, et démontrer les deux. Les chaînes de $\iff$ ne sont licites que si *chaque* maillon est réellement réversible — élever une équation au carré, par exemple, ne l’est pas.
3. *Les démonstrations à l’envers.* Partir de la conclusion souhaitée et en déduire une [assertion](#def-b1-logic-statement) vraie ne démontre rien (de $-1 = 1$ on tire le vrai $1 = 1$ en élevant au carré). Un calcul peut être *découvert* à l’envers, mais il doit être *écrit* à l’endroit, ou avec des équivalences explicites.
4. *Témoin fixé contre élément quelconque.* Pour démontrer $\exists x,\ P(x)$ , on peut exhiber un seul $x$ habilement choisi ; pour démontrer $\forall x,\ P(x)$ , le $x$ choisi doit rester quelconque. Confondre les deux — vérifier une [assertion](#def-b1-logic-statement) universelle sur un exemple — est l’erreur la plus fréquente dans les copies de débutants.

**Exemple 1.11 (Contraposition et absurde à l’œuvre).**

*Pour $n \in \N$ : si $n^2$ est pair alors $n$ est pair.* Par contraposition : si $n$ est impair, $n = 2k+1$, alors $n^2 = 4k^2 + 4k + 1$ est impair.

*$\sqrt 2$ est irrationnel.* Par l’absurde : supposons $\sqrt 2 = p/q$ avec $p, q \in \N^*$ et la fraction irréductible. Alors $p^2 = 2q^2$ est pair, donc $p$ est pair (point précédent), $p = 2r$ ; alors $q^2 = 2r^2$ est pair, donc $q$ est pair — ce qui contredit l’irréductibilité.

**Théorème 1.12 (Récurrence).**

Soit $P(n)$ une propriété de l’entier $n$. Si

1. $P(0)$ est vraie, et
2. pour tout $n \in \N$ , $P(n) \implies P(n+1)$ ,

alors $P(n)$ est vraie pour tout $n \in \N$.

*Récurrence forte :* la conclusion est inchangée si (2) est remplacée par : pour tout $n$, $\bigl(P(0) \land \dots \land
P(n)\bigr) \implies P(n+1)$.

**Démonstration.** C’est une propriété de $\N$ lui-même, équivalente à : *toute partie non vide de $\N$ admet un plus petit élément* (que nous admettons connue). En effet, supposons (1) et (2) vérifiées et posons $A = \{n \in \N : P(n) \text{ fausse}\}$. Si $A \neq \emptyset$, il admet un plus petit élément $m$ ; $m \neq 0$ d’après (1) ; alors $m - 1 \notin A$, donc $P(m-1)$ est vraie, et (2) donne $P(m)$ — contradiction. Donc $A = \emptyset$. Pour la récurrence forte, le même argument s’applique : $P(0), \dots, P(m-1)$ sont toutes vraies puisque $m$ est le plus petit élément de $A$. ∎

**Exemple 1.13 (Démontrer une existence et unicité).**

Une [assertion](#def-b1-logic-statement) $\exists!\,x,\ P(x)$ est *deux* [assertions](#def-b1-logic-statement), démontrées séparément : l’existence (exhiber ou construire un $x_0$ tel que $P(x_0)$) et l’unicité (supposer $P(x)$ et $P(x')$, en déduire $x = x'$). Exemple : *il existe un unique réel $x$ tel que $x^3 + x = 2$.* Existence : $x_0 = 1$ convient, puisque $1 + 1 = 2$. Unicité : si $x^3 + x = x'^3 + x'$, alors

$$
0 = (x^3 - x'^3) + (x - x')
= (x - x')\,\bigl(x^2 + xx' + x'^2 + 1\bigr),
$$

et le second facteur est strictement positif (il vaut $\bigl(x +
\tfrac{x'}2\bigr)^2 + \tfrac34 x'^2 + 1 \geq 1$), donc $x = x'$. Remarquons le partage des tâches : l’existence a reposé sur une intuition heureuse, l’unicité sur une algèbre valable pour des solutions *quelconques* — aucun des deux arguments ne fait le travail de l’autre, et oublier la seconde moitié est une tentation permanente une fois qu’une solution a été trouvée.

**Exemple 1.14.**

Pour tout $n \in \N^*$ : $\;\sum_{k=1}^n k = \frac{n(n+1)}{2}$. Initialisation $n = 1$ : les deux membres valent $1$. Hérédité : en supposant la formule au rang $n$,

$$
\sum_{k=1}^{n+1} k = \frac{n(n+1)}{2} + (n+1)
= (n+1)\Bigl(\frac n2 + 1\Bigr) = \frac{(n+1)(n+2)}{2}. \qedhere
$$

**Exemple 1.15 (La récurrence forte à l’œuvre).**

*Tout entier $n \geq 2$ est un produit de nombres premiers* (un nombre premier étant un entier $\geq 2$ dont les seuls diviseurs $\geq 1$ sont $1$ et lui-même ; les nombres premiers sont étudiés pour eux-mêmes au [Chapitre 6](https://one-course.com/books/math/3/fr/chapter/6-arithmetique-des-entiers#ch-b1-arith)). La récurrence ordinaire est ici impuissante : savoir que $95 = 5 \times 19$ se factorise ne dit rien de $96$. La récurrence forte convient exactement. Initialisation : $2$ est premier, donc produit (à un facteur) de nombres premiers. Hérédité : soit $n \geq 2$ et supposons que tout entier $m$ avec $2 \leq m \leq n$ est un produit de nombres premiers. Si $n + 1$ est premier, c’est fini. Sinon $n + 1 = ab$ avec $2 \leq a, b \leq n$ ; par l’hypothèse forte, $a$ et $b$ sont tous deux des produits de nombres premiers, donc $n + 1$ aussi. L’idée à retenir : la récurrence forte est l’outil adapté chaque fois que la « raison » de $P(n+1)$ se trouve à un rang antérieur imprévisible, et non au rang $n$.

## 1.4 Ensembles

**Définition 1.16 (Opérations sur les ensembles).**

Nous prenons la notion d’*ensemble* et la relation d’appartenance $x \in E$ comme primitives. Pour des ensembles $A, B$ inclus dans un ensemble ambiant $E$ :

- l’ *inclusion* : $A \subseteq B$ lorsque $\forall x,\ x \in  A \implies x \in B$ ; l’égalité $A = B$ lorsque $A \subseteq B$ et $B \subseteq A$ ;
- la *réunion* $A \cup B$ , l’ *intersection* $A \cap B$ , la *différence* $A \setminus B = \{x \in A : x \notin B\}$ , le *complémentaire* $\overline{A} = E \setminus A$ ;
- l’ *ensemble vide* $\emptyset$ , contenu dans tout ensemble ;
- l’ *ensemble des parties* $\mathcal{P}(E)$ : l’ensemble de toutes les parties de $E$ ;
- le *produit* $E \times F$ : l’ensemble des couples $(x, y)$ avec $x \in E$ , $y \in F$ .

**Exemple 1.17 (Se familiariser avec l’ensemble des parties).**

Pour $E = \{a, b\}$ :

$$
\mathcal P(E) = \bigl\{\, \emptyset,\ \{a\},\ \{b\},\ \{a, b\}
\,\bigr\},
$$

quatre éléments — et notons la discipline des types : $a \in E$ mais $\{a\} \in \mathcal P(E)$ ; les [assertions](#def-b1-logic-statement) $a \in \mathcal P(E)$ et $\{a\} \subseteq \mathcal P(E)$ sont toutes deux fausses telles qu’elles sont écrites (la seconde exigerait que $a$ soit une *partie* de $E$). En itérant à partir de rien : $\mathcal P(\emptyset) = \{\emptyset\}$ a un élément, $\mathcal P(\mathcal P(\emptyset)) = \{\emptyset, \{\emptyset\}\}$ en a deux, le suivant en a quatre — les [ensembles](#def-b1-logic-sets) d’[ensembles](#def-b1-logic-sets) sont des [ensembles](#def-b1-logic-sets) ordinaires, et le [Chapitre 2](https://one-course.com/books/math/3/fr/chapter/2-denombrement#ch-b1-counting) confirmera le doublement : $\abs{\mathcal P(E)} = 2^{\abs E}$. Garder les niveaux ($x$, $\{x\}$, $\{\{x\}\}$) bien distincts, c’est déjà la moitié du travail dans des exercices comme les Exercices [1.11](#exo-b1-logic-11) et [1.12](#exo-b1-logic-12).

**Proposition 1.18 (Algèbre des ensembles).**

Pour des parties $A, B, C$ de $E$ :

1. $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ et $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ ;
2. De Morgan : $\overline{A \cup B} = \overline{A} \cap  \overline{B}$ et $\overline{A \cap B} = \overline{A} \cup  \overline{B}$ ;
3. $A \subseteq B \iff \overline{B} \subseteq \overline{A}$ .

**Démonstration.** Chaque identité traduit une règle de la [Proposition 1.3](#prop-b1-logic-rules) au moyen du dictionnaire (appartenir ou non à $A$) $\leftrightarrow$ ([assertion](#def-b1-logic-statement) vraie ou fausse) : par exemple $x \in \overline{A \cup B}
\iff \lnot(x \in A \lor x \in B) \iff (x \notin A) \land (x \notin B)
\iff x \in \overline{A} \cap \overline{B}$. Le point (3) est la contraposition. Comme deuxième échantillon, la première loi de distributivité en entier :

$$
x \in A \cap (B \cup C)
\iff (x \in A) \land \bigl(x \in B \lor x \in C\bigr)
\iff \bigl(x \in A \land x \in B\bigr) \lor
\bigl(x \in A \land x \in C\bigr),
$$

par la distributivité de la [Proposition 1.3](#prop-b1-logic-rules) (6), et la dernière [assertion](#def-b1-logic-statement) se lit $x \in (A \cap B) \cup (A \cap C)$. Toute identité ensembliste de ce genre se démontre par cette unique traduction mécanique — raison pour laquelle aucune n’a besoin d’être apprise par cœur. ∎

**Méthode 1.19 (Démontrer une égalité d’ensembles).**

Pour démontrer $A = B$, on démontre les deux inclusions : soit $x \in
A$, on montre $x \in B$ ; puis soit $x \in B$, on montre $x \in A$. Autre possibilité : enchaîner des équivalences $x \in A \iff \dots \iff
x \in B$ lorsque chaque étape en est réellement une.

![Les lois de De Morgan en images : la région grisée de gauche est A ∪ B = A ∩ B (tout ce qui est hors des deux disques) ; à droite, A ∩ B = A ∪ B (tout sauf la lentille commune). Un dessin n’est pas une démonstration, mais il rend la démonstration par éléments de la impossible à mal retenir.](https://one-course.com/images/onecourse/chapters/math-3/b1-logic/fig-5465323f1d10.svg)

*Les [lois de De Morgan](#prop-b1-logic-rules) en images : la région grisée de gauche est $\overline{A \cup B} = \overline A \cap \overline B$ (tout ce qui est hors des deux disques) ; à droite, $\overline{A \cap B} = \overline
A \cup \overline B$ (tout sauf la lentille commune). Un dessin n’est pas une démonstration, mais il rend la démonstration par éléments de la [Proposition 1.18](#prop-b1-logic-setalgebra) impossible à mal retenir.*

## 1.5 Applications

**Définition 1.20 (Application, image, image réciproque).**

Une *application* (ou *fonction*) $f \colon E \to F$ associe à tout élément $x$ de l’[ensemble](#def-b1-logic-sets) $E$ (l’*[ensemble](#def-b1-logic-sets) de départ*) exactement un élément $f(x)$ de l’[ensemble](#def-b1-logic-sets) $F$ (l’*[ensemble](#def-b1-logic-sets) d’arrivée*). Pour $A \subseteq E$ et $B \subseteq F$ :

$$
f(A) = \{f(x) : x \in A\} \subseteq F,
\qquad
f^{-1}(B) = \{x \in E : f(x) \in B\} \subseteq E
$$

sont l’*image directe* de $A$ et l’*image réciproque* de $B$. La *composée* de $f \colon E \to
F$ et $g \colon F \to G$ est $g \circ f \colon E \to G$, $x \mapsto
g(f(x))$.

**Remarque 1.21.**

La notation $f^{-1}(B)$ ne présuppose *pas* l’existence d’une [application](#def-b1-logic-map) réciproque : $f^{-1}(B)$ est définie pour toute $f$. Les [images réciproques](#def-b1-logic-map) se comportent mieux que les images directes : $f^{-1}$ préserve réunions, intersections et complémentaires, alors que $f(A \cap A') \subseteq f(A) \cap f(A')$ peut être stricte ([Exercice 1.8](#exo-b1-logic-8)).

**Exemple 1.22 (Calculer images et images réciproques).**

Soit $f \colon \R \to \R$, $x \mapsto x^2$. Alors :

$$
f\bigl(\intcc{-1}{2}\bigr) = \intcc04, \qquad
f^{-1}\bigl(\intcc14\bigr) = \intcc{-2}{-1} \cup \intcc12, \qquad
f^{-1}(\{-1\}) = \emptyset .
$$

Pour la première : tout $x \in \intcc{-1}2$ vérifie $x^2 \in \intcc04$, et tout $y \in \intcc04$ est atteint sous la forme $y = (\sqrt y)^2$ avec $\sqrt y \in \intcc02 \subseteq \intcc{-1}2$ — notons que l’image n’est *pas* $\intcc14 = \{(-1)^2, 2^2\}$ : les images d’intervalles ne se calculent pas à partir des seules extrémités. Pour la deuxième : $1 \leq x^2 \leq 4 \iff 1 \leq \abs x \leq 2$, ce qui se scinde en deux morceaux. La troisième illustre qu’une [image réciproque](#def-b1-logic-map) peut être vide — $f^{-1}(B)$ a toujours un sens, si petite que soit l’intersection de $B$ avec l’image. Observons enfin sur cet exemple le phénomène de stricte inclusion de la remarque précédente : avec $A = \intcc{-1}0$ et $A' = \intcc01$, on a $f(A \cap A') = f(\{0\}) = \{0\}$, tandis que $f(A) \cap f(A') = \intcc01$.

**Définition 1.23 (Injective, surjective, bijective).**

Une [application](#def-b1-logic-map) $f \colon E \to F$ est :

- *injective* lorsque des éléments distincts ont des images distinctes : $\forall x, x' \in E,\ f(x) = f(x')  \implies x = x'$ ;
- *surjective* lorsque tout élément de $F$ est atteint : $\forall y \in F,\ \exists x \in E,\ f(x) = y$ ;
- *bijective* lorsqu’elle est les deux, c’est-à-dire lorsque tout $y \in F$ a exactement un antécédent.

**Théorème 1.24 (Application réciproque).**

Une [application](#def-b1-logic-map) $f \colon E \to F$ est [bijective](#def-b1-logic-inj) si et seulement s’il existe une [application](#def-b1-logic-map) $g \colon F \to E$ telle que $g \circ f =
\mathrm{id}_E$ et $f \circ g = \mathrm{id}_F$. Dans ce cas $g$ est unique ; on la note $f^{-1}$ et on l’appelle la *réciproque* de $f$, et $f^{-1}$ est elle-même [bijective](#def-b1-logic-inj), avec $(f^{-1})^{-1} = f$.

**Démonstration.** ($\Rightarrow$) Si $f$ est [bijective](#def-b1-logic-inj), tout $y \in F$ a un unique antécédent ; définissons $g(y)$ comme cet antécédent. Alors $f(g(y)) = y$ par construction, et $g(f(x)) = x$ parce que $x$ est *l’*antécédent de $f(x)$.

($\Leftarrow$) Supposons qu’une telle $g$ existe. Si $f(x) = f(x')$, en appliquant $g$ on obtient $x = x'$ : $f$ est [injective](#def-b1-logic-inj). Pour $y \in F$, $x = g(y)$ vérifie $f(x) = y$ : $f$ est [surjective](#def-b1-logic-inj).

Unicité : si $g$ et $h$ conviennent toutes deux, alors $g = g \circ
\mathrm{id}_F = g \circ (f \circ h) = (g \circ f) \circ h = h$. Enfin le couple d’identités est symétrique en $f$ et $g$, donc $g = f^{-1}$ est [bijective](#def-b1-logic-inj), de réciproque $f$. ∎

**Exemple 1.25 (Calculer une réciproque en pratique).**

Soit $f \colon \R \to \intoo0{+\infty}$, $f(x) = \eu^{2x+1}$. Pour l’inverser, résolvons $y = f(x)$ pour un $y > 0$ donné :

$$
y = \eu^{2x+1} \iff \ln y = 2x + 1 \iff x = \frac{\ln y - 1}2 ,
$$

chaque étape étant réversible sur les [ensembles](#def-b1-logic-sets) annoncés. Le calcul livre tout d’un coup : pour chaque $y$ de l’[ensemble](#def-b1-logic-sets) d’arrivée il y a exactement une solution $x$, donc $f$ est [bijective](#def-b1-logic-inj), et

$$
f^{-1} \colon \intoo0{+\infty} \to \R,
\qquad
f^{-1}(y) = \frac{\ln y - 1}2 .
$$

Une vérification rapide des deux composées ($f^{-1}(f(x)) =
\frac{(2x+1) - 1}2 = x$ et $f(f^{-1}(y)) = \eu^{\ln y} = y$) confirme le critère du [Théorème 1.24](#thm-b1-logic-inverse). L’idée à retenir : « résoudre en $x$ en surveillant les équivalences » est à la fois la démonstration d’existence, celle d’unicité et la formule — mais cela ne fonctionne que si l’[ensemble](#def-b1-logic-sets) d’arrivée a été correctement annoncé ($f$ n’est *pas* [surjective](#def-b1-logic-inj) sur $\R$).

**Proposition 1.26 (Composition et les trois propriétés).**

Soient $f \colon E \to F$ et $g \colon F \to G$.

1. Si $f$ et $g$ sont [injectives](#def-b1-logic-inj) (resp. [surjectives](#def-b1-logic-inj) , [bijectives](#def-b1-logic-inj) ), alors $g \circ f$ l’est aussi ; et dans le cas [bijectif](#def-b1-logic-inj) , $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ .
2. Si $g \circ f$ est [injective](#def-b1-logic-inj) , alors $f$ est [injective](#def-b1-logic-inj) . Si $g \circ f$ est [surjective](#def-b1-logic-inj) , alors $g$ est [surjective](#def-b1-logic-inj) .

**Démonstration.** (1) Si $g(f(x)) = g(f(x'))$, l’[injectivité](#def-b1-logic-inj) de $g$ donne $f(x) = f(x')$, puis l’[injectivité](#def-b1-logic-inj) de $f$ donne $x = x'$. Si $z \in G$, la [surjectivité](#def-b1-logic-inj) de $g$ fournit $y$ avec $g(y) = z$, puis la [surjectivité](#def-b1-logic-inj) de $f$ fournit $x$ avec $f(x) = y$, de sorte que $g(f(x)) = z$. Dans le cas [bijectif](#def-b1-logic-inj), on vérifie directement que $f^{-1} \circ g^{-1}$ est un inverse à gauche et à droite de $g \circ f$, et l’unicité du [Théorème 1.24](#thm-b1-logic-inverse) conclut.

(2) Si $f(x) = f(x')$ alors $g(f(x)) = g(f(x'))$, et l’[injectivité](#def-b1-logic-inj) de $g \circ f$ donne $x = x'$. Si $z \in G$, la [surjectivité](#def-b1-logic-inj) de $g \circ f$ fournit $x$ avec $g(f(x)) = z$ : alors $y = f(x)$ vérifie $g(y) = z$. ∎

**Exemple 1.27 (Le point (2) est optimal).**

Dans la [Proposition 1.26](#prop-b1-logic-comp) (2), on ne peut pas renforcer les conclusions : $g \circ f$ [bijective](#def-b1-logic-inj) n’oblige *pas* $f$ à être [surjective](#def-b1-logic-inj) ni $g$ à être [injective](#def-b1-logic-inj). Prenons $E = G = \{1\}$, $F = \{1, 2\}$, avec $f(1) = 1$ et $g(1) = g(2) = 1$ : alors $g \circ f = \mathrm{id}_E$ est [bijective](#def-b1-logic-inj), et pourtant $f$ manque l’élément $2$ et $g$ écrase les deux éléments. La morale est une règle de comptabilité précise : l’information de la composée descend vers l’[application](#def-b1-logic-map) *intérieure* pour l’[injectivité](#def-b1-logic-inj) et vers l’[application](#def-b1-logic-map) *extérieure* pour la [surjectivité](#def-b1-logic-inj), jamais dans l’autre sens. (L’[Exercice 1.9](#exo-b1-logic-9) construit le même phénomène avec des [ensembles](#def-b1-logic-sets) infinis, où il est le moteur des inverses d’un seul côté.)

**Exemple 1.28.**

$f \colon \R \to \R$, $x \mapsto x^2$ n’est ni [injective](#def-b1-logic-inj) ($f(-1) =
f(1)$) ni [surjective](#def-b1-logic-inj) ($-1$ n’a pas d’antécédent). En restreignant l’[ensemble](#def-b1-logic-sets) de départ et l’[ensemble](#def-b1-logic-sets) d’arrivée, $f \colon \R_+ \to \R_+$, $x \mapsto x^2$ est [bijective](#def-b1-logic-inj), de réciproque $y \mapsto \sqrt y$. L’[injectivité](#def-b1-logic-inj) ou la [surjectivité](#def-b1-logic-inj) d’une [application](#def-b1-logic-map) dépend des [ensembles](#def-b1-logic-sets) de départ et d’arrivée annoncés, et pas seulement de la formule.

## 1.6 Relations

**Définition 1.29 (Relation d’équivalence).**

Une *relation binaire* $\mathcal{R}$ sur un [ensemble](#def-b1-logic-sets) $E$ est une *relation d’équivalence* lorsqu’elle est : *réflexive* ($x \mathbin{\mathcal{R}} x$ pour tout $x$), *symétrique* ($x \mathbin{\mathcal{R}} y \implies y
\mathbin{\mathcal{R}} x$) et *transitive* ($x
\mathbin{\mathcal{R}} y$ et $y \mathbin{\mathcal{R}} z$ entraînent $x
\mathbin{\mathcal{R}} z$). La *classe d’équivalence* de $x$ est $\mathrm{cl}(x) = \{y \in E : x \mathbin{\mathcal{R}} y\}$.

**Exemple 1.30 (Vérifier les trois axiomes).**

Sur $\R$, déclarons $x \mathbin{\mathcal{R}} y$ lorsque $x - y \in \Z$. *Réflexive :* $x - x = 0 \in \Z$. *Symétrique :* si $x - y
\in \Z$ alors $y - x = -(x - y) \in \Z$. *Transitive :* si $x -
y \in \Z$ et $y - z \in \Z$, alors $x - z = (x - y) + (y - z) \in
\Z$ (somme d’entiers). Donc $\mathcal R$ est une [relation d’équivalence](#def-b1-logic-equiv), et $\mathrm{cl}(x) = x + \Z = \{x + k : k \in \Z\}$ : chaque classe contient exactement un représentant dans $\intco01$, sa *partie fractionnaire*. En revanche, la relation « $\abs{x - y}
\leq 1$ » sur $\R$ est réflexive et symétrique mais *pas* transitive ($0 \mathbin{\mathcal R} 1$ et $1 \mathbin{\mathcal R}
2$, alors que $\abs{0 - 2} > 1$) : la proximité ne se propage pas, et aucune [partition](#thm-b1-logic-partition) en classes n’existe — un contre-exemple utile à garder en tête quand la vérification des axiomes semble routinière.

**Théorème 1.31 (Les classes forment une partition).**

Soit $\mathcal{R}$ une [relation d’équivalence](#def-b1-logic-equiv) sur $E$. Alors les classes d’équivalence sont non vides, deux à deux disjointes ou égales, et leur réunion est $E$ : elles forment une *partition* de $E$. Réciproquement, toute [partition](#thm-b1-logic-partition) de $E$ provient ainsi d’exactement une [relation d’équivalence](#def-b1-logic-equiv) (« être dans le même morceau »).

**Démonstration.** $x \in \mathrm{cl}(x)$ par réflexivité, donc les classes sont non vides et de réunion $E$. Supposons $\mathrm{cl}(x) \cap \mathrm{cl}(y) \neq
\emptyset$, disons que $z$ appartient aux deux. Alors $x
\mathbin{\mathcal{R}} z$ et $y \mathbin{\mathcal{R}} z$, donc par symétrie et transitivité $x \mathbin{\mathcal{R}} y$. Alors, pour tout $t \in \mathrm{cl}(y)$, la transitivité donne $t \in \mathrm{cl}(x)$, et symétriquement : les deux classes sont égales. Pour la réciproque, soit $(E_i)_{i \in I}$ une [partition](#thm-b1-logic-partition) de $E$ et définissons $x \mathbin{\mathcal S} y$ par « un morceau contient à la fois $x$ et $y$ ». *Réflexive :* $x$ appartient à un morceau, qui le contient alors deux fois. *Symétrique :* la condition définissante est symétrique en $x$ et $y$. *Transitive :* si $x, y \in E_i$ et $y, z \in E_j$, alors $y \in E_i \cap E_j$, donc $E_i = E_j$ (des morceaux distincts sont disjoints) et $x, z$ partagent un morceau. La classe de $x$ pour $\mathcal S$ est exactement le morceau contenant $x$, donc les classes sont les morceaux donnés. Enfin la relation est déterminée par ses classes : deux [relations d’équivalence](#def-b1-logic-equiv) ayant les mêmes classes relient les mêmes couples, puisque chacune relie $x$ et $y$ exactement quand $y$ appartient à la classe de $x$ — d’où l’unicité annoncée. ∎

**Exemple 1.32.**

Sur $\Z$, la congruence modulo $n$ ($x \equiv y \pmod n$ lorsque $n$ divise $x - y$) est une [relation d’équivalence](#def-b1-logic-equiv) ; ses classes sont les $n$ [ensembles](#def-b1-logic-sets) d’entiers ayant un reste donné dans la division par $n$. Cet exemple devient l’anneau $\Z/n\Z$ au [Chapitre 7](https://one-course.com/books/math/3/fr/chapter/7-structures-algebriques#ch-b1-structures).

**Définition 1.33 (Relation d’ordre).**

Une relation $\preceq$ sur $E$ est un *ordre* lorsqu’elle est réflexive, *antisymétrique* ($x \preceq y$ et $y \preceq x$ entraînent $x = y$) et transitive. L’ordre est *total* lorsque deux éléments quelconques sont comparables, *partiel* sinon. Un élément $M \in A \subseteq E$ est un *plus grand élément* de $A$ lorsque $a \preceq M$ pour tout $a \in A$ ; les plus grands (et les plus petits) éléments sont uniques lorsqu’ils existent.

**Exemple 1.34.**

$(\R, \leq)$ est totalement ordonné. $(\mathcal{P}(E), \subseteq)$ est partiellement ordonné dès que $E$ a deux éléments : $\{a\}$ et $\{b\}$ ne sont pas comparables. La partie $A = \{\{a\}, \{b\}\}$ de $\mathcal{P}(\{a,b\})$ n’a pas de plus grand élément, et pourtant elle admet le majorant $\{a, b\}$ : la distinction entre plus grand élément et majorant reviendra, pour $\R$, au [Chapitre 10](https://one-course.com/books/math/3/fr/chapter/10-nombres-reels#ch-b1-reals).

**Exemple 1.35 (Deux ordres sur la grille N2\N^2N2).**

Sur les couples d’entiers naturels, comparons composante par composante : $(a, b) \preceq (a', b')$ lorsque $a \leq a'$ *et* $b \leq b'$ (l’*[ordre](#def-b1-logic-order) produit*). C’est bien un [ordre](#def-b1-logic-order) — chaque axiome est hérité coordonnée par coordonnée — mais un [ordre](#def-b1-logic-order) partiel : $(1, 3)$ et $(2, 0)$ sont incomparables. Comparons maintenant comme un dictionnaire : $(a, b) \preceq_{\mathrm{lex}} (a', b')$ lorsque $a < a'$, ou bien $a = a'$ et $b \leq b'$ (l’*[ordre](#def-b1-logic-order) lexicographique*). La transitivité demande une vérification en deux cas mais elle est vraie, et deux couples quelconques sont désormais comparables : l’[ordre](#def-b1-logic-order) est total. Les deux [ordres](#def-b1-logic-order) classent le même [ensemble](#def-b1-logic-sets) différemment — $(0, 100) \preceq_{\mathrm{lex}} (1, 0)$ alors que l’[ordre](#def-b1-logic-order) produit ne dit rien — ce qui rappelle qu’un [ordre](#def-b1-logic-order) est une structure que l’on *choisit*, et non une propriété de l’[ensemble](#def-b1-logic-sets). La comparaison lexicographique est aussi l’astuce standard pour transformer plusieurs critères de tri en un seul.

**Remarque 1.36 (Interlude : la taille comme bijection).**

Un thème discret de ce chapitre mérite d’être mis en lumière : les [bijections](#def-b1-logic-inj) sont la notion mathématique de « même taille ». Pour les [ensembles](#def-b1-logic-sets) finis, cela devient le calcul de dénombrement du [Chapitre 2](https://one-course.com/books/math/3/fr/chapter/2-denombrement#ch-b1-counting), où chaque formule est secrètement une [bijection](#def-b1-logic-inj) ; pour les [ensembles](#def-b1-logic-sets) infinis, cela devient le devoir maison ci-dessous, où $\N$, $\Q$ et $\R$ se révèlent avoir des tailles véritablement différentes. Le même dictionnaire réapparaît deux fois encore dans ce volume, sous des formes raffinées : les suites ([Chapitre 11](https://one-course.com/books/math/3/fr/chapter/11-suites#ch-b1-seq)) ne sont rien d’autre que des [applications](#def-b1-logic-map) $\N \to
\R$, si bien que les [assertions](#def-b1-logic-statement) sur les suites sont des [assertions](#def-b1-logic-statement) sur un [ensemble](#def-b1-logic-sets) d’[applications](#def-b1-logic-map) ; et l’algèbre linéaire mesurera les espaces vectoriels non pas par des [bijections](#def-b1-logic-inj) mais par des [bijections](#def-b1-logic-inj) *linéaires*, dont l’existence est gouvernée par un unique nombre, la dimension ([Chapitre 19](https://one-course.com/books/math/3/fr/chapter/19-dimension-finie#ch-b1-findim)). Chaque fois qu’une nouvelle notion de « mêmeté » apparaît — équipotence, isomorphisme de groupes ([Chapitre 7](https://one-course.com/books/math/3/fr/chapter/7-structures-algebriques#ch-b1-structures)), isomorphisme linéaire — le schéma du [Théorème 1.24](#thm-b1-logic-inverse) se répète : être « le même », c’est être relié par une [application](#def-b1-logic-map) inversible qui respecte la structure.

**Remarque 1.37 (Où ce chapitre sert).**

Partout — mais quelques endroits méritent d’être signalés. La gymnastique à trois quantificateurs de l’[Exemple 1.8](#ex-b1-logic-limit) est le pain quotidien des Chapitres [11](https://one-course.com/books/math/3/fr/chapter/11-suites#ch-b1-seq) et [13](https://one-course.com/books/math/3/fr/chapter/13-limites-et-continuite#ch-b1-continuity) : toute démonstration de limite est une partie jouée contre un $\varepsilon$ quelconque. Les classes d’équivalence réapparaissent comme les classes de congruence de $\Z/n\Z$ au [Chapitre 7](https://one-course.com/books/math/3/fr/chapter/7-structures-algebriques#ch-b1-structures), où la [partition](#thm-b1-logic-partition) du [Théorème 1.31](#thm-b1-logic-partition) acquiert une structure algébrique propre. Les [relations d’ordre](#def-b1-logic-order), les majorants et les bornes supérieures deviennent le cœur axiomatique de $\R$ au [Chapitre 10](https://one-course.com/books/math/3/fr/chapter/10-nombres-reels#ch-b1-reals). Les [injections](#def-b1-logic-inj), [surjections](#def-b1-logic-inj) et [bijections](#def-b1-logic-inj) reviennent comme les [applications](#def-b1-logic-map) linéaires du [Chapitre 20](https://one-course.com/books/math/3/fr/chapter/20-applications-lineaires#ch-b1-linmaps), où l’[injectivité](#def-b1-logic-inj) se teste sur un seul vecteur (le noyau) ; et le devoir maison ci-dessous transforme la simple notion de [bijection](#def-b1-logic-inj) en une théorie des *tailles des [ensembles](#def-b1-logic-sets) infinis*, dont les conclusions (dénombrabilité de $\Q$, non-dénombrabilité de $\R$) refont surface aux Chapitres [10](https://one-course.com/books/math/3/fr/chapter/10-nombres-reels#ch-b1-reals) et [12](https://one-course.com/books/math/3/fr/chapter/12-topologie-de-la-droite-reelle#ch-b1-topology).

## 1.7 Exercices

**Exercice 1.1 ★.**

Écrire la négation de chaque [assertion](#def-b1-logic-statement), sans employer le mot « non » :

1. $\forall x \in \R,\ \exists y \in \R,\ x + y > 0$ ;
2. $\exists x \in \R,\ \forall y \in \R,\ xy = 0$ ;
3. $\forall \varepsilon > 0,\ \exists \delta > 0,\ \forall x \in  \R,\ \abs{x} \leq \delta \implies \abs{f(x)} \leq \varepsilon$ (pour une [application](#def-b1-logic-map) fixée $f \colon \R \to \R$ ).

Décider ensuite si les [assertions](#def-b1-logic-statement) (1) et (2) sont vraies.

**Solution de Exercice 1.1.**

Négations, en faisant passer $\lnot$ à travers chaque quantificateur ([Proposition 1.5](#prop-b1-logic-negquant)) et en utilisant $\lnot(P \implies Q)
\iff P \land \lnot Q$ :

1. $\exists x \in \R,\ \forall y \in \R,\ x + y \leq 0$ ;
2. $\forall x \in \R,\ \exists y \in \R,\ xy \neq 0$ ;
3. $\exists \varepsilon > 0,\ \forall \delta > 0,\ \exists x \in  \R,\ \abs{x} \leq \delta \text{ et } \abs{f(x)} >  \varepsilon$ .

L’[assertion](#def-b1-logic-statement) (1) est vraie : étant donné $x$, prendre $y = -x + 1$ ; alors $x + y = 1 > 0$. L’[assertion](#def-b1-logic-statement) (2) est vraie : $x = 0$ vérifie $xy = 0$ pour tout $y$.

**Exercice 1.2 ★.**

Soient $P, Q$ des [assertions](#def-b1-logic-statement). À l’aide de tables de vérité, démontrer que $\lnot(P \implies Q) \iff P \land (\lnot Q)$, et en déduire la négation de : « si une fonction est dérivable alors elle est continue ».

**Solution de Exercice 1.2.**

Table de vérité, en écrivant V/F pour les quatre cas $(P, Q)$ :

| $P$ | $Q$ | $P \implies Q$ | $\lnot(P \implies Q)$ | $\lnot Q$ | $P \land \lnot Q$ |
| --- | --- | --- | --- | --- | --- |
| V | V | V | F | F | F |
| V | F | F | V | V | V |
| F | V | V | F | F | F |
| F | F | V | F | V | F |

Les colonnes $4$ et $6$ coïncident, ce qui démontre l’équivalence. La négation de « si une fonction est dérivable alors elle est continue » est donc : « il existe une fonction qui est dérivable et non continue » (une [assertion](#def-b1-logic-statement) fausse, en l’occurrence : l’implication de départ est vraie, voir le [Chapitre 14](https://one-course.com/books/math/3/fr/chapter/14-derivation#ch-b1-derivative)).

**Exercice 1.3 ★.**

Démontrer par contraposition : pour $x \in \R$, si $x^3 + x \geq 2$ alors $x \geq 1$. Démontrer ensuite par l’absurde qu’il n’existe pas de plus petit réel strictement positif.

**Solution de Exercice 1.3.**

*Contraposition.* Supposons $x < 1$. Alors $x^3 < 1$ (la fonction cube est croissante) et $x < 1$, donc $x^3 + x < 2$. Cela démontre la contraposée, donc l’[assertion](#def-b1-logic-statement).

*Absurde.* Supposons que $a > 0$ soit le plus petit réel strictement positif. Alors $a/2$ est strictement positif et $a/2 < a$ (puisque $a > 0$), ce qui contredit la minimalité. Donc un tel $a$ n’existe pas.

**Exercice 1.4 ★.**

Démontrer par récurrence que, pour tout $n \in \N$ :

1. $\sum_{k=0}^{n} 2^k = 2^{n+1} - 1$ ;
2. $4^n + 5$ est divisible par $3$ .

**Solution de Exercice 1.4.**

1. Initialisation $n = 0$ : $2^0 = 1 = 2^1 - 1$. Hérédité : en supposant l’identité au rang $n$, $$\sum_{k=0}^{n+1} 2^k = (2^{n+1} - 1) + 2^{n+1}  = 2 \cdot 2^{n+1} - 1 = 2^{n+2} - 1 .$$
2. Initialisation $n = 0$ : $4^0 + 5 = 6 = 3 \times 2$. Hérédité : si $4^n + 5 = 3m$, alors $$4^{n+1} + 5 = 4(4^n + 5) - 15 = 3(4m - 5),$$ qui est divisible par $3$.

**Exercice 1.5 ★.**

Trouver la faille dans la « démonstration » suivante que tous les crayons ont la même couleur. *Soit $P(n)$ : « dans tout [ensemble](#def-b1-logic-sets) de $n$ crayons, tous les crayons ont la même couleur ». $P(1)$ est clair. Supposons $P(n)$ et prenons $n+1$ crayons ; en retirant le dernier, les $n$ premiers ont même couleur ; en retirant le premier, les $n$ derniers ont même couleur ; donc les $n+1$ ont même couleur.*

**Solution de Exercice 1.5.**

L’hérédité suppose en douce que les deux groupes (« les $n$ premiers » et « les $n$ derniers ») se recoupent, de sorte que les crayons communs transportent la couleur d’un groupe à l’autre. Pour $n + 1 = 2$, les deux groupes sont $\{$premier crayon$\}$ et $\{$second crayon$\}$ : ils sont disjoints, et l’argument s’effondre. Ainsi $P(1) \implies P(2)$ n’a jamais été démontré, et la récurrence s’écroule — même si $P(n) \implies P(n+1)$ est valable pour tout $n \geq 2$.

**Exercice 1.6 ★.**

Soient $A, B, C$ des parties de $E$. Démontrer :

1. $A \setminus B = A \cap \overline{B}$ ;
2. $(A \cup B) \setminus C = (A \setminus C) \cup (B \setminus  C)$ ;
3. $A \subseteq B \iff A \cup B = B \iff A \cap B = A$ .

**Solution de Exercice 1.6.**

1. $x \in A \setminus B \iff x \in A \land x \notin B \iff x \in  A \land x \in \overline{B} \iff x \in A \cap \overline{B}$ .
2. En utilisant (1) et la distributivité ( [Proposition 1.18](#prop-b1-logic-setalgebra) ) : $(A \cup B) \cap \overline{C} = (A \cap \overline{C}) \cup  (B \cap \overline{C})$ .
3. Supposons $A \subseteq B$ . Alors $A \cup B \subseteq B$ (les deux morceaux sont dans $B$ ) et $B \subseteq A \cup B$ toujours, donc $A \cup B = B$ . Supposons $A \cup B = B$ : alors $A \cap B  \subseteq A$ toujours, et $A \subseteq A \cup B = B$ donne $A \subseteq A \cap B$ , donc $A \cap B = A$ . Supposons $A \cap B = A$ : alors $A = A \cap B \subseteq B$ . Les trois conditions sont donc équivalentes (on a démontré un cycle d’implications).

**Exercice 1.7 ★★.**

Pour chaque [application](#def-b1-logic-map), décider (avec démonstration) si elle est [injective](#def-b1-logic-inj), [surjective](#def-b1-logic-inj), [bijective](#def-b1-logic-inj) :

1. $f \colon \N \to \N$ , $n \mapsto n + 1$ ;
2. $g \colon \Z \to \Z$ , $n \mapsto n + 1$ ;
3. $h \colon \R \setminus \{1\} \to \R$ , $x \mapsto  \frac{x+1}{x-1}$ .

Pour $h$, ajuster l’[ensemble](#def-b1-logic-sets) d’arrivée pour la rendre [bijective](#def-b1-logic-inj) et calculer la réciproque.

**Solution de Exercice 1.7.**

1. $f$ est [injective](#def-b1-logic-inj) ( $n + 1 = m + 1 \implies n = m$ ) mais non [surjective](#def-b1-logic-inj) : $0$ n’a pas d’antécédent dans $\N$ .
2. $g$ est [bijective](#def-b1-logic-inj) : $n \mapsto n - 1$ en est un inverse à gauche et à droite sur $\Z$ .
3. $h$ est [injective](#def-b1-logic-inj) : $\frac{x+1}{x-1} = \frac{x'+1}{x'-1}$ donne $(x+1)(x'-1) = (x'+1)(x-1)$ , c’est-à-dire $xx' - x + x' - 1 =  xx' - x' + x - 1$ , donc $2x' = 2x$ . Elle n’est pas [surjective](#def-b1-logic-inj) sur $\R$ : résoudre $y = \frac{x+1}{x-1}$ donne $x(y - 1) = y + 1$ , qui n’a pas de solution quand $y = 1$ (l’équation s’écrit $0 = 2$ ). Avec l’ [ensemble](#def-b1-logic-sets) d’arrivée $\R \setminus \{1\}$ , le même calcul donne l’unique antécédent $x = \frac{y+1}{y-1}$ , donc $h \colon \R \setminus \{1\} \to \R \setminus \{1\}$ est [bijective](#def-b1-logic-inj) et $h^{-1}(y) = \frac{y+1}{y-1} = h(y)$ : $h$ est sa propre réciproque.

**Exercice 1.8 ★★.**

Soient $f \colon E \to F$, $A, A' \subseteq E$ et $B, B' \subseteq
F$.

1. Démontrer $f^{-1}(B \cap B') = f^{-1}(B) \cap f^{-1}(B')$ et $f(A \cup A') = f(A) \cup f(A')$ .
2. Démontrer $f(A \cap A') \subseteq f(A) \cap f(A')$ et donner un exemple où l’inclusion est stricte.
3. Démontrer : $f$ est [injective](#def-b1-logic-inj) si et seulement si $f(A \cap A')  = f(A) \cap f(A')$ pour toutes parties $A, A'$ .

**Solution de Exercice 1.8.**

1. $x \in f^{-1}(B \cap B') \iff f(x) \in B \cap B' \iff f(x) \in  B \land f(x) \in B' \iff x \in f^{-1}(B) \cap f^{-1}(B')$ . Pour les images : $y \in f(A \cup A')$ si et seulement si $y = f(x)$ pour un $x$ de $A$ ou de $A'$ , si et seulement si $y \in f(A)$ ou $y \in f(A')$ .
2. Si $y \in f(A \cap A')$ , alors $y = f(x)$ avec $x \in A$ et $x \in A'$ , donc $y \in f(A)$ et $y \in f(A')$ . Stricte inclusion : prendre $f \colon \R \to \R$ , $x \mapsto x^2$ , $A = \{-1\}$ , $A' = \{1\}$ : alors $f(A \cap A') =  f(\emptyset) = \emptyset$ tandis que $f(A) \cap f(A') = \{1\}$ .
3. ( $\Leftarrow$ ) Avec $A = \{x\}$ , $A' = \{x'\}$ pour $x \neq  x'$ : si $f(x) = f(x')$ , alors $f(A) \cap f(A') = \{f(x)\}$ tandis que $f(A \cap A') = \emptyset$ , ce qui contredit l’égalité supposée ; donc $f$ est [injective](#def-b1-logic-inj) . ( $\Rightarrow$ ) Soit $f$ [injective](#def-b1-logic-inj) et $y \in f(A) \cap f(A')$ : $y = f(x) =  f(x')$ avec $x \in A$ , $x' \in A'$ ; l’ [injectivité](#def-b1-logic-inj) donne $x = x' \in A \cap A'$ , donc $y \in f(A \cap A')$ . Avec (2), il y a égalité.

**Exercice 1.9 ★★.**

Soient $f \colon E \to F$ et $g \colon F \to E$ telles que $g \circ f =
\mathrm{id}_E$. Démontrer que $f$ est [injective](#def-b1-logic-inj) et que $g$ est [surjective](#def-b1-logic-inj). Donner un exemple où ni $f$ ni $g$ n’est [bijective](#def-b1-logic-inj).

**Solution de Exercice 1.9.**

$g \circ f = \mathrm{id}_E$ est [injective](#def-b1-logic-inj) et [surjective](#def-b1-logic-inj), donc d’après la [Proposition 1.26](#prop-b1-logic-comp) (2), $f$ est [injective](#def-b1-logic-inj) et $g$ est [surjective](#def-b1-logic-inj). Exemple : $E = \N$, $F = \Z$, $f$ l’inclusion $n \mapsto n$, et $g \colon \Z \to \N$, $g(n) = n$ pour $n \geq 0$ et $g(n) = 0$ pour $n < 0$. Alors $g(f(n)) = n$ pour tout $n \in \N$, mais $f$ n’est pas [surjective](#def-b1-logic-inj) et $g$ n’est pas [injective](#def-b1-logic-inj).

**Exercice 1.10 ★★.**

Sur $\R$, on définit $x \mathbin{\mathcal{R}} y \iff x^2 - y^2 = x - y$. Démontrer que $\mathcal{R}$ est une [relation d’équivalence](#def-b1-logic-equiv) et décrire la classe d’équivalence de chaque réel $x$. Quelles classes ont exactement un élément ?

**Solution de Exercice 1.10.**

$x^2 - y^2 = x - y \iff (x - y)(x + y) = x - y \iff (x - y)(x + y - 1)
= 0 \iff y = x$ ou $y = 1 - x$. *Réflexive :* $y = x$ convient. *Symétrique :* la condition « $y = x$ ou $y = 1 - x$ » est symétrique en $x$ et $y$ (si $y = 1 - x$ alors $x = 1 - y$). *Transitive :* supposons $x \mathbin{\mathcal{R}} y$ et $y
\mathbin{\mathcal{R}} z$ ; en parcourant les quatre cas, $z$ vaut $x$ ou $1 - x$ à chaque fois (par exemple $y = 1 - x$ et $z = 1 - y$ donnent $z = x$). Donc $\mathcal{R}$ est une [relation d’équivalence](#def-b1-logic-equiv) et $\mathrm{cl}(x) = \{x,\, 1 - x\}$. Cette classe a un seul élément exactement lorsque $x = 1 - x$, c’est-à-dire pour $x = \frac12$.

**Exercice 1.11 ★★★.**

(Cantor) Soit $E$ un [ensemble](#def-b1-logic-sets). Démontrer qu’il n’existe pas de [surjection](#def-b1-logic-inj) de $E$ sur $\mathcal{P}(E)$. *Indication : étant donnée $f \colon E \to \mathcal{P}(E)$, considérer $D = \{x \in E : x \notin
f(x)\}$.*

**Solution de Exercice 1.11.**

Soit $f \colon E \to \mathcal{P}(E)$ une [application](#def-b1-logic-map) quelconque et posons $D = \{x \in E : x \notin f(x)\} \in \mathcal{P}(E)$. Supposons $D = f(a)$ pour un certain $a \in E$. 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 par définition de $D$, $a \in D$ : contradiction. Ainsi $D$ n’est pas dans l’image de $f$, et $f$ n’est pas [surjective](#def-b1-logic-inj). (En particulier aucun [ensemble](#def-b1-logic-sets) n’est en [bijection](#def-b1-logic-inj) avec son [ensemble des parties](#def-b1-logic-sets) : il y a « plus » de parties de $\N$ que d’entiers.)

**Exercice 1.12 ★★★.**

Soit $f \colon E \to F$ une [application](#def-b1-logic-map). On définit $\Phi \colon
\mathcal{P}(F) \to \mathcal{P}(E)$ par $\Phi(B) = f^{-1}(B)$.

1. Démontrer que $f$ est [surjective](#def-b1-logic-inj) si et seulement si $\Phi$ est [injective](#def-b1-logic-inj) .
2. Démontrer que $f$ est [injective](#def-b1-logic-inj) si et seulement si $\Phi$ est [surjective](#def-b1-logic-inj) .

**Solution de Exercice 1.12.**

1. ( $\Rightarrow$ ) Soit $f$ [surjective](#def-b1-logic-inj) et $\Phi(B) = \Phi(B')$ . Pour $y \in B$ , choisissons $x$ tel que $f(x) = y$ ; alors $x  \in f^{-1}(B) = f^{-1}(B')$ , donc $y = f(x) \in B'$ . Ainsi $B  \subseteq B'$ , et symétriquement $B' \subseteq B$ : $\Phi$ est [injective](#def-b1-logic-inj) . ( $\Leftarrow$ ) Si $f$ n’est pas [surjective](#def-b1-logic-inj) , choisissons $y_0 \in F$ hors de l’image ; alors $f^{-1}(\{y_0\}) = \emptyset = f^{-1}(\emptyset)$ avec $\{y_0\} \neq \emptyset$ , donc $\Phi$ n’est pas [injective](#def-b1-logic-inj) .
2. ( $\Rightarrow$ ) Soit $f$ [injective](#def-b1-logic-inj) et $A \subseteq E$ . Posons $B = f(A)$ ; alors $f^{-1}(B) = \{x : f(x) \in f(A)\}$ , et l’ [injectivité](#def-b1-logic-inj) donne $f(x) \in f(A) \iff x \in A$ , donc $\Phi(B) = A$ : $\Phi$ est [surjective](#def-b1-logic-inj) . ( $\Leftarrow$ ) Si $f$ n’est pas [injective](#def-b1-logic-inj) , prenons $x \neq x'$ avec $f(x) = f(x')$ . Toute [image réciproque](#def-b1-logic-map) $f^{-1}(B)$ contient $x$ si et seulement si elle contient $x'$ ; donc $\{x\}$ n’est pas de la forme $\Phi(B)$ , et $\Phi$ n’est pas [surjective](#def-b1-logic-inj) .

## 1.8 Problème : comparer les infinis

**Problème 1.1.**

Quand deux [ensembles](#def-b1-logic-sets) ont-ils « le même nombre d’éléments » ? La réponse de Cantor — lorsqu’il existe une [bijection](#def-b1-logic-inj) entre eux — se révèle utilisable même pour des [ensembles](#def-b1-logic-sets) infinis, et elle scinde l’infini en tailles véritablement différentes. Ce problème construit toute la boîte à outils à partir des seules définitions de ce chapitre : le théorème de Cantor–Schröder–Bernstein (deux [injections](#def-b1-logic-inj) fabriquent une [bijection](#def-b1-logic-inj)), la dénombrabilité de $\Q$, la non-dénombrabilité de $\R$ par l’argument diagonal, et l’étonnante conclusion de Cantor en 1874 : *les [nombres transcendants](#pb-b1-logic-1) existent, et en masse*, sans qu’on en exhibe un seul. Dans tout le problème, pour des [ensembles](#def-b1-logic-sets) $E$ et $F$, on écrit $E
\preceq F$ lorsqu’il existe une [injection](#def-b1-logic-inj) de $E$ dans $F$, et $E
\approx F$ (« $E$ et $F$ sont *équipotents* ») lorsqu’il existe une [bijection](#def-b1-logic-inj) de $E$ sur $F$.

**Partie I — Le vocabulaire de la comparaison.**

1. Montrer que $\approx$ se comporte comme une [relation d’équivalence](#def-b1-logic-equiv) : $E \approx E$ ; si $E \approx F$ alors $F \approx E$ ; si $E \approx F$ et $F \approx G$ alors $E \approx G$ . (Citer précisément [Théorème 1.24](#thm-b1-logic-inverse) et [Proposition 1.26](#prop-b1-logic-comp) .)
2. Montrer que $\preceq$ est transitive, et qu’une [injection](#def-b1-logic-inj) $f \colon E \to F$ induit toujours $E \approx f(E)$ .
3. Soit $E \neq \emptyset$ . Montrer que $E \preceq F$ si et seulement s’il existe une [surjection](#def-b1-logic-inj) de $F$ sur $E$ .
4. Vérifier que $n \mapsto n + 1$ est une [bijection](#def-b1-logic-inj) de $\N$ sur $\N^* = \N \setminus \{0\}$, et que $$\sigma(n) = \frac n2 \ \ (n \text{ pair}), \qquad  \sigma(n) = -\frac{n+1}2 \ \ (n \text{ impair})$$ est une [bijection](#def-b1-logic-inj) de $\N$ sur $\Z$. Ainsi, retirer un point, ou doubler en passant aux négatifs, ne change pas la taille de $\N$.

**Partie II — Le théorème de Cantor–Schröder–Bernstein.** Soient $f \colon E \to F$ et $g \colon F
\to E$ deux [injections](#def-b1-logic-inj). On pose

$$
C_0 = E \setminus g(F), \qquad C_{n+1} = g\bigl(f(C_n)\bigr)
\ \ (n \in \N), \qquad C = \bigcup_{n \in \N} C_n,
$$

et on définit $h \colon E \to F$ en envoyant $x \in C$ sur $f(x)$, et $x \notin C$ sur l’unique $y \in F$ tel que $g(y) = x$.

5. Vérifier que $h$ est bien définie : si $x \notin C$ alors $x \in  g(F)$ , et l’élément $y$ tel que $g(y) = x$ est unique.
6. Montrer que $g\bigl(f(C)\bigr) = \bigcup_{n \geq 1} C_n  \subseteq C$ . (Les images directes commutent aux réunions : [Exercice 1.8](#exo-b1-logic-8) .)
7. Montrer que $h$ est [injective](#def-b1-logic-inj) . (Trois cas ; dans le cas mixte $x \in C$ , $x' \notin C$ , montrer que $h(x) = h(x')$ forcerait $x' \in g(f(C)) \subseteq C$ .)
8. Montrer que $h$ est [surjective](#def-b1-logic-inj) : étant donné $y \in F$ , distinguer les cas $g(y) \notin C$ et $g(y) \in C_n$ pour un certain $n \geq 1$ (pourquoi $g(y) \in C_0$ est-il impossible ?), et exhiber dans chaque cas un antécédent de $y$ .
9. Conclure par le *théorème de Cantor–Schröder–Bernstein* : si $E \preceq F$ et $F \preceq  E$ , alors $E \approx F$ . Commenter en une phrase ce qui rend cet énoncé non trivial.
10. Deux [applications](#def-b1-logic-map) . (a) Montrer que $\intcc01 \approx \intoo01$ . (b) Montrer que $\varphi(p, q) = 2^p(2q + 1) - 1$ définit une [bijection](#def-b1-logic-inj) de $\N \times \N$ sur $\N$ — [injectivité](#def-b1-logic-inj) par un argument de parité, [surjectivité](#def-b1-logic-inj) par récurrence forte ( [Théorème 1.12](#thm-b1-logic-induction) ). Ainsi $\N \times \N \approx  \N$ : le plan des points entiers n’est pas plus gros que la droite.

**Partie III — [Ensembles dénombrables](#pb-b1-logic-1).** On dit qu’un [ensemble](#def-b1-logic-sets) $E$ est *au plus dénombrable* lorsque $E \preceq \N$, et *dénombrable* lorsque $E \approx \N$.

11. Montrer que toute partie infinie $A \subseteq \N$ est dénombrable. (Définir $\varphi(n)$ par récurrence comme le plus petit élément de $A \setminus \{\varphi(0), \dots,  \varphi(n-1)\}$ ; montrer que $\varphi$ est strictement croissante, vérifie $\varphi(n) \geq n$ , et atteint tout élément de $A$ .)
12. En déduire qu’un [ensemble](#def-b1-logic-sets) est au plus dénombrable si et seulement s’il est fini ou dénombrable, et observer que la question 9 fournit le raccourci : si $E \preceq \N$ et $\N  \preceq E$ , alors $E$ est dénombrable.
13. Montrer que si $E$ et $F$ sont au plus dénombrables, alors $E \times F$ l’est aussi. En déduire que $\Z \times \N^*$ est dénombrable.
14. Montrer que $\Q$ est dénombrable. (Injecter $\Q$ dans $\Z  \times \N^*$ en écrivant chaque rationnel sous forme irréductible avec dénominateur positif — l’unicité de cette représentation est démontrée au [Chapitre 6](https://one-course.com/books/math/3/fr/chapter/6-arithmetique-des-entiers#ch-b1-arith) ; puis appliquer la question 12.)
15. Montrer qu’une réunion dénombrable d’ [ensembles](#def-b1-logic-sets) au plus dénombrables est au plus dénombrable : si chaque $E_n$ ( $n \in  \N$ ) est au plus dénombrable, alors $\bigcup_{n \in \N} E_n$ l’est aussi. (Envoyer $x$ sur le couple $(n, f_n(x))$ où $n$ est le *plus petit* indice tel que $x \in E_n$ .)
16. Montrer que l’ [ensemble des parties](#def-b1-logic-sets) *finies* de $\N$ est dénombrable. (Envoyer une partie finie $F$ sur $\sum_{i \in F}  2^i$ ; démontrer l’ [injectivité](#def-b1-logic-inj) en comparant le plus grand élément où deux parties finies diffèrent, à l’aide de $\sum_{k=0}^{m-1} 2^k = 2^m - 1$ tiré de l’ [Exercice 1.4](#exo-b1-logic-4) .)

**Partie IV — Diagonalisation.** On note $\{0,1\}^{\N}$ l’[ensemble](#def-b1-logic-sets) de toutes les [applications](#def-b1-logic-map) $u \colon \N \to \{0, 1\}$, c’est-à-dire l’[ensemble](#def-b1-logic-sets) des suites binaires.

17. Construire une [bijection](#def-b1-logic-inj) entre $\mathcal{P}(\N)$ et $\{0,1\}^{\N}$ (fonctions indicatrices).
18. (L’argument diagonal) Soit $\Phi \colon \N \to  \{0,1\}^{\N}$ une [application](#def-b1-logic-map) quelconque. Considérer la suite $d$ définie par $d(n) = 1 - \Phi(n)(n)$ . Montrer que $d$ n’est pas dans l’image de $\Phi$ , et en conclure que $\{0,1\}^{\N}$ n’est *pas* au plus dénombrable. Expliquer en une phrase pourquoi, à travers la question 17, c’est exactement le théorème de Cantor ( [Exercice 1.11](#exo-b1-logic-11) ) pour $E = \N$ .
19. Admettre — comme cela est familier depuis le secondaire, et comme on l’établira rigoureusement au [Chapitre 10](https://one-course.com/books/math/3/fr/chapter/10-nombres-reels#ch-b1-reals) — que tout $x \in  \intco01$ possède un unique développement décimal *propre* $x = 0.d_1 d_2 d_3\dots$ (c’est-à-dire ne se terminant pas par une infinité de $9$ ). Étant donnée une suite $(x_n)_{n \geq 1}$ d’éléments de $\intco01$ , construire $x \in \intco01$ tel que $x \neq x_n$ pour tout $n$ : choisir sa $n$ -ième décimale égale à $5$ si la $n$ -ième décimale de $x_n$ diffère de $5$ , et à $6$ sinon. Justifier soigneusement que $x$ est propre et évite tous les $x_n$ , et en conclure que $\intco01$ n’est pas au plus dénombrable.
20. En déduire que $\R$ n’est pas dénombrable, et que l’ [ensemble](#def-b1-logic-sets) $\R \setminus \Q$ des nombres irrationnels ne l’est pas non plus. En quel sens précis « la plupart » des nombres réels sont-ils irrationnels ?

**Partie V — Le théorème de Cantor de 1874 : les [nombres transcendants](#pb-b1-logic-1) existent.** Un nombre réel $x$ est *algébrique* lorsque $P(x) = 0$ pour un certain polynôme non nul $P$ à coefficients entiers, et *transcendant* sinon. Pour cette partie, on admet — c’est démontré au [Chapitre 8](https://one-course.com/books/math/3/fr/chapter/8-polynomes#ch-b1-poly) — qu’un polynôme non nul de degré $n$ a au plus $n$ racines réelles.

21. Montrer que tout nombre rationnel est algébrique, et trouver des polynômes explicites à coefficients entiers annulant $\sqrt 2$ et $\sqrt 2 + \sqrt 3$ .
22. Pour $n \in \N$ fixé, montrer que l’ [ensemble](#def-b1-logic-sets) des polynômes de degré au plus $n$ à coefficients entiers est dénombrable. (L’injecter dans $\Z^{n+1}$ et raisonner par récurrence sur $n$ avec la question 13.)
23. En déduire que l’ [ensemble](#def-b1-logic-sets) de *tous* les polynômes à coefficients entiers est dénombrable.
24. Démontrer le *théorème de Cantor sur les [nombres algébriques](#pb-b1-logic-1)* : l’ [ensemble](#def-b1-logic-sets) $\mathcal{A}$ des nombres réels algébriques est dénombrable.
25. Conclure : il existe des nombres réels [transcendants](#pb-b1-logic-1) , et l’ [ensemble](#def-b1-logic-sets) des [nombres transcendants](#pb-b1-logic-1) n’est pas dénombrable. Faire ensuite le bilan de tout le problème en quelques phrases : la chaîne $\N \approx \Z \approx \Q \approx \mathcal{A}$ , le saut strict vers $\R \approx$ (essentiellement) $\mathcal{P}(\N)$ , l’endroit où chaque outil (Cantor–Schröder–Bernstein, réunions dénombrables, la diagonale) a été décisif — et la force philosophique d’une démonstration établissant l’existence d’une infinité non dénombrable de [nombres transcendants](#pb-b1-logic-1) sans en nommer un seul. (Démontrer qu’un nombre *précis* comme $\pi$ est [transcendant](#pb-b1-logic-1) est bien plus difficile et dépasse ce volume.)

**Solution de Problème 1.1.**

**1.** *Réflexive :* $\mathrm{id}_E$ est une [bijection](#def-b1-logic-inj) de $E$ sur lui-même. *Symétrique :* si $f \colon E \to F$ est [bijective](#def-b1-logic-inj), le [Théorème 1.24](#thm-b1-logic-inverse) fournit $f^{-1} \colon F \to E$, elle-même [bijective](#def-b1-logic-inj). *Transitive :* si $f \colon E \to F$ et $g \colon F
\to G$ sont des [bijections](#def-b1-logic-inj), la [Proposition 1.26](#prop-b1-logic-comp) (1) dit que $g \circ f \colon E \to G$ est une [bijection](#def-b1-logic-inj). (Ce n’est qu’une [relation d’équivalence](#def-b1-logic-equiv) « au sens large » : la collection de tous les [ensembles](#def-b1-logic-sets) n’est pas elle-même un [ensemble](#def-b1-logic-sets), à cause des paradoxes qu’évoque [Exercice 1.11](#exo-b1-logic-11) ; ce sont les trois propriétés qui comptent.)

**2.** Si $f \colon E \to F$ et $g \colon F \to G$ sont [injectives](#def-b1-logic-inj), $g \circ f$ est [injective](#def-b1-logic-inj) d’après la [Proposition 1.26](#prop-b1-logic-comp) (1) : $E \preceq G$. Pour le second point, corestreignons $f$ à son image : l’[application](#def-b1-logic-map) $\tilde f \colon E \to
f(E)$, $x \mapsto f(x)$, est [surjective](#def-b1-logic-inj) par construction de $f(E)$ et [injective](#def-b1-logic-inj) parce que $f$ l’est, donc [bijective](#def-b1-logic-inj) : $E \approx f(E)$.

**3.** ($\Rightarrow$) Soit $f \colon E \to F$ [injective](#def-b1-logic-inj) et fixons $a \in E$ ($E \neq \emptyset$). Définissons $s \colon F \to E$ par : $s(y)$ est l’unique $x$ tel que $f(x) = y$ lorsque $y \in f(E)$ (unicité par [injectivité](#def-b1-logic-inj)), et $s(y) = a$ sinon. Pour tout $x \in E$, $s(f(x)) = x$, donc tout $x$ est atteint : $s$ est [surjective](#def-b1-logic-inj). ($\Leftarrow$) Soit $s \colon F \to E$ [surjective](#def-b1-logic-inj). Pour chaque $x \in
E$, choisissons un $y_x \in F$ tel que $s(y_x) = x$, et posons $u(x) = y_x$. Si $u(x) = u(x')$ alors $x = s(u(x)) = s(u(x')) = x'$ : $u \colon E \to F$ est [injective](#def-b1-logic-inj).

**4.** $n \mapsto n + 1$ envoie $\N$ dans $\N^*$, est [injective](#def-b1-logic-inj) ($n + 1 = m + 1 \implies n = m$) et [surjective](#def-b1-logic-inj) (tout $m \geq 1$ vaut $(m - 1) + 1$ avec $m - 1 \in \N$). Pour $\sigma$ : elle envoie les nombres pairs $0, 2, 4, \dots$ sur $0, 1, 2, \dots$ et les nombres impairs $1, 3, 5, \dots$ sur $-1, -2, -3, \dots$ [Injectivité](#def-b1-logic-inj) : les entrées paires arrivent dans $\N$ ($\sigma(n) = n/2 \geq 0$) et les entrées impaires arrivent dans les entiers strictement négatifs ($\sigma(n) = -(n+1)/2 \leq -1$), donc une collision ne peut se produire qu’à l’intérieur d’une classe de parité, où $\sigma$ est strictement monotone ($n/2 = m/2$ ou $(n+1)/2 = (m+1)/2$ force $n = m$). [Surjectivité](#def-b1-logic-inj) : $k \geq 0$ vaut $\sigma(2k)$ ; $k \leq -1$ vaut $\sigma(-2k - 1)$ avec $-2k - 1 \geq 1$ impair. Donc $\N \approx
\N^*$ et $\N \approx \Z$.

**5.** $C_0 = E \setminus g(F) \subseteq C$, donc $x \notin C$ entraîne $x \notin C_0$, c’est-à-dire $x \in g(F)$ : un certain $y \in
F$ vérifie $g(y) = x$. Si de plus $g(y') = x$, l’[injectivité](#def-b1-logic-inj) de $g$ donne $y' = y$. Ainsi la seconde clause de la définition de $h$ désigne un élément unique et bien défini $g^{-1}(x)$.

**6.** Les images directes commutent aux réunions ([Exercice 1.8](#exo-b1-logic-8) (1), appliquée à $f$ puis à $g$) :

$$
g\bigl(f(C)\bigr)
= g\Bigl(f\Bigl(\bigcup_{n \in \N} C_n\Bigr)\Bigr)
= \bigcup_{n \in \N} g\bigl(f(C_n)\bigr)
= \bigcup_{n \in \N} C_{n+1}
= \bigcup_{n \geq 1} C_n \subseteq C .
$$

**7.** Soient $x \neq x'$ dans $E$. Si les deux sont dans $C$, alors $h(x) = f(x) \neq f(x') = h(x')$ par [injectivité](#def-b1-logic-inj) de $f$. Si aucun n’est dans $C$, alors $g(h(x)) = x \neq x' = g(h(x'))$, donc $h(x) \neq
h(x')$. Si $x \in C$ et $x' \notin C$ (le cas mixte, quitte à échanger les noms) : supposons $h(x) = h(x')$, c’est-à-dire $f(x) = g^{-1}(x')$. En appliquant $g$ : $x' = g(f(x)) \in g(f(C))$, et la question 6 donne $x' \in C$ — contradiction. Donc $h(x) \neq h(x')$ dans tous les cas : $h$ est [injective](#def-b1-logic-inj).

**8.** Soit $y \in F$. *Cas 1 : $g(y) \notin C$.* Alors $h(g(y)) = g^{-1}(g(y)) = y$ : l’élément $g(y)$ est un antécédent. *Cas 2 : $g(y) \in C$*, disons $g(y) \in C_n$. Comme $g(y) \in
g(F)$, on a $g(y) \notin C_0 = E \setminus g(F)$, donc $n \geq 1$ et $g(y) \in C_n = g(f(C_{n-1}))$ : il existe $x \in C_{n-1}$ tel que $g(y) = g(f(x))$. L’[injectivité](#def-b1-logic-inj) de $g$ donne $y = f(x)$, et $x \in
C_{n-1} \subseteq C$, donc $h(x) = f(x) = y$. Dans les deux cas $y$ est atteint : $h$ est [surjective](#def-b1-logic-inj), donc [bijective](#def-b1-logic-inj).

**9.** Si $E \preceq F$ et $F \preceq E$, choisissons des [injections](#def-b1-logic-inj) $f \colon E \to F$ et $g \colon F \to E$ ; les questions 5 à 8 construisent une [bijection](#def-b1-logic-inj) $h \colon E \to F$, donc $E \approx
F$. L’énoncé est non trivial parce que les deux [injections](#def-b1-logic-inj) données n’ont aucun lien — aucune n’a besoin d’être [surjective](#def-b1-logic-inj), et aucune formule mélangeant naïvement $f$ et $g$ ne définit une [application](#def-b1-logic-map) : tout le contenu réside dans la [partition](#thm-b1-logic-partition) de $E$ en la région $C$ (où l’on recopie $f$) et son complémentaire (où l’on remonte $g$).

**10.** (a) L’inclusion $\intoo01 \to \intcc01$ est [injective](#def-b1-logic-inj) ; et $x \mapsto \frac{x + 1}3$ envoie $\intcc01$ injectivement dans $\intcc{\frac13}{\frac23} \subseteq \intoo01$ (c’est une [application](#def-b1-logic-map) affine de pente non nulle). D’après la question 9, $\intcc01 \approx
\intoo01$ — une [bijection](#def-b1-logic-inj) qu’il serait fort désagréable d’écrire explicitement. (b) *[Injectivité](#def-b1-logic-inj).* Supposons $2^p(2q + 1) = 2^{p'}(2q' + 1)$ avec, disons, $p \leq p'$. En divisant par $2^p$ : $2q + 1 = 2^{p' - p}(2q' +
1)$. Si $p' > p$, le membre de droite est pair et celui de gauche impair — impossible ; donc $p = p'$, puis $2q + 1 = 2q' + 1$ et $q = q'$. *[Surjectivité](#def-b1-logic-inj).* Montrons par récurrence forte que tout entier $m \geq 1$ est de la forme $2^p(2q + 1)$. Pour $m = 1$ : $p = q = 0$. Soit $m \geq 1$ et supposons l’[assertion](#def-b1-logic-statement) vraie pour tous les entiers de $\intint1m$. Si $m + 1$ est impair, $m + 1 = 2q + 1$ avec $p = 0$. Si $m + 1$ est pair, $m + 1 = 2m'$ avec $1 \leq m' \leq
m$ ; par hypothèse $m' = 2^p(2q + 1)$, donc $m + 1 = 2^{p+1}(2q + 1)$. Ainsi $\varphi(p, q) = 2^p(2q + 1) - 1$ atteint tout $n \in \N$, et $\varphi$ est une [bijection](#def-b1-logic-inj) $\N \times \N \to \N$.

**11.** Comme $A$ est infinie, $A \setminus \{\varphi(0), \dots,
\varphi(n - 1)\}$ n’est jamais vide, et la propriété du plus petit élément dans $\N$ (utilisée pour démontrer [Théorème 1.12](#thm-b1-logic-induction)) rend la définition par récurrence légitime. *Strictement croissante :* $\varphi(n + 1)$ appartient à $A \setminus \{\varphi(0), \dots, \varphi(n)\} \subseteq A \setminus
\{\varphi(0), \dots, \varphi(n - 1)\}$, dont le minimum est $\varphi(n)$ ; donc $\varphi(n + 1) \geq \varphi(n)$, et l’égalité est exclue, d’où $\varphi(n+1) > \varphi(n)$. *$\varphi(n) \geq n$ :* par récurrence, $\varphi(0) \geq 0$, et $\varphi(n + 1) \geq \varphi(n)
+ 1 \geq n + 1$. *L’[injectivité](#def-b1-logic-inj)* découle de la stricte monotonie. *[Surjectivité](#def-b1-logic-inj) sur $A$ :* supposons qu’un certain $a \in A$ ne soit jamais atteint. Comme $\varphi(a + 1) \geq a + 1 >
a$, l’[ensemble](#def-b1-logic-sets) des $n$ tels que $\varphi(n) > a$ est non vide ; soit $n$ son plus petit élément. Pour tout $k < n$, $\varphi(k) \leq a$, donc $\varphi(k) < a$ ($a$ n’est pas atteint). Alors $a$ appartient à $A \setminus \{\varphi(0), \dots, \varphi(n - 1)\}$ et $a < \varphi(n)$, ce qui contredit la minimalité définissant $\varphi(n)$. Donc $\varphi$ est une [bijection](#def-b1-logic-inj) $\N \to A$, et $A$ est dénombrable.

**12.** Soit $E \preceq \N$ via une [injection](#def-b1-logic-inj) $f$ ; alors $E
\approx f(E)$ (question 2). Si $f(E)$ est finie, $E$ est fini ; si $f(E)$ est infinie, la question 11 donne $f(E) \approx \N$, donc $E \approx \N$ par transitivité (question 1). Réciproquement, les [ensembles](#def-b1-logic-sets) finis et les [ensembles dénombrables](#pb-b1-logic-1) s’injectent évidemment dans $\N$. Le raccourci : $E \preceq \N$ et $\N \preceq E$ donnent $E \approx \N$ directement par Cantor–Schröder–Bernstein — aucun argument d’énumération n’est nécessaire.

**13.** Soient $f \colon E \to \N$ et $g \colon F \to \N$ des [injections](#def-b1-logic-inj). Alors $(x, y) \mapsto \varphi\bigl(f(x), g(y)\bigr)$ est une [injection](#def-b1-logic-inj) $E \times F \to \N$ : si les images coïncident, l’[injectivité](#def-b1-logic-inj) de $\varphi$ (question 10) donne $f(x) = f(x')$ et $g(y) = g(y')$, puis $x = x'$, $y = y'$. Pour $\Z \times \N^*$ : les deux facteurs sont dénombrables (question 4), donc $\Z \times \N^*
\preceq \N$ ; cet [ensemble](#def-b1-logic-sets) est infini (il contient $\{0\} \times \N^*$), donc dénombrable d’après la question 12.

**14.** Tout rationnel $r$ admet une unique représentation $r =
p/q$ avec $p \in \Z$, $q \in \N^*$ et la fraction irréductible (l’unicité est démontrée au [Chapitre 6](https://one-course.com/books/math/3/fr/chapter/6-arithmetique-des-entiers#ch-b1-arith) ; pour $r = 0$ prendre $0/1$). L’[application](#def-b1-logic-map) $r \mapsto (p, q)$ est alors [injective](#def-b1-logic-inj) : le couple détermine $r = p/q$. Ainsi $\Q \preceq \Z \times \N^* \preceq \N$ d’après la question 13. Comme $\N \subseteq \Q$ donne $\N \preceq \Q$, la question 12 (ou Cantor–Schröder–Bernstein directement) montre que $\Q \approx \N$ : les rationnels sont dénombrables.

**15.** Pour chaque $n$, fixons une [injection](#def-b1-logic-inj) $f_n \colon E_n \to
\N$. Pour $x \in \bigcup_n E_n$, soit $n(x)$ le *plus petit* $n$ tel que $x \in E_n$, et posons $u(x) = \varphi\bigl(n(x),
f_{n(x)}(x)\bigr) \in \N$. Si $u(x) = u(x')$, l’[injectivité](#def-b1-logic-inj) de $\varphi$ donne $n(x) = n(x') = n$ et $f_n(x) = f_n(x')$, donc $x = x'$ par [injectivité](#def-b1-logic-inj) de $f_n$. La réunion s’injecte donc dans $\N$ : elle est au plus dénombrable.

**16.** Posons $\Psi(F) = \sum_{i \in F} 2^i$ pour $F \subseteq \N$ finie ($\Psi(\emptyset) = 0$). Supposons $F \neq F'$ et soit $m$ le plus grand élément sur lequel elles diffèrent, disons $m \in F \setminus
F'$ (quitte à échanger les noms). Les éléments $> m$ appartiennent aux deux ou à aucune, donc ils contribuent également aux deux sommes ; en comparant les contributions des éléments $\leq m$ :

$$
\sum_{i \in F,\, i \leq m} 2^i \geq 2^m
> 2^m - 1 = \sum_{k=0}^{m-1} 2^k
\geq \sum_{i \in F',\, i \leq m} 2^i ,
$$

en utilisant la somme géométrique de l’[Exercice 1.4](#exo-b1-logic-4). Donc $\Psi(F) \neq \Psi(F')$ : $\Psi$ est [injective](#def-b1-logic-inj) et l’[ensemble des parties](#def-b1-logic-sets) finies de $\N$ est au plus dénombrable ; il est infini (il contient tous les singletons), donc dénombrable.

**17.** Envoyons $A \subseteq \N$ sur son indicatrice $\mathbf 1_A
\colon \N \to \{0,1\}$, $\mathbf 1_A(n) = 1$ si $n \in A$ et $0$ sinon ; envoyons $u \in \{0,1\}^{\N}$ sur $A_u = \{n \in \N : u(n) =
1\}$. Les deux [applications](#def-b1-logic-map) sont réciproques l’une de l’autre : $A_{\mathbf 1_A} = A$ et $\mathbf 1_{A_u} = u$ (vérifier la valeur en chaque $n$). D’après le [Théorème 1.24](#thm-b1-logic-inverse), chacune est une [bijection](#def-b1-logic-inj) : $\mathcal{P}(\N) \approx \{0,1\}^{\N}$.

**18.** Pour tout $n$, $d(n) = 1 - \Phi(n)(n) \neq \Phi(n)(n)$, donc les suites $d$ et $\Phi(n)$ diffèrent à l’indice $n$ : $d \neq
\Phi(n)$. Ainsi aucune $\Phi$ n’est [surjective](#def-b1-logic-inj), et d’après la question 3 il n’existe pas non plus d’[injection](#def-b1-logic-inj) $\{0,1\}^{\N} \to \N$ : $\{0,1\}^{\N}$ n’est pas au plus dénombrable. À travers le dictionnaire de la question 17, une [application](#def-b1-logic-map) $\Phi \colon \N \to \{0,1\}^{\N}$ est une [application](#def-b1-logic-map) $f \colon \N \to \mathcal{P}(\N)$, et $d$ correspond à l’[ensemble](#def-b1-logic-sets) $D = \{n : n \notin f(n)\}$ (en effet $d(n) = 1 \iff
\Phi(n)(n) = 0 \iff n \notin f(n)$) : l’argument diagonal *est* la démonstration de Cantor de l’[Exercice 1.11](#exo-b1-logic-11) pour $E = \N$.

**19.** Écrivons $x_n = 0.d_1(n)\,d_2(n)\,d_3(n)\dots$ sous forme propre et définissons $\delta_n = 5$ si $d_n(n) \neq 5$, $\delta_n = 6$ si $d_n(n) = 5$, puis $x = 0.\delta_1\delta_2\delta_3\dots$ Ce développement n’utilise que les chiffres $5$ et $6$, donc il ne se termine pas par une infinité de $9$ : c’est le développement propre d’un réel $x \in \intco01$. Pour chaque $n$, les $n$-ièmes décimales de $x$ et de $x_n$ diffèrent ($\delta_n \neq d_n(n)$ par construction) ; comme les développements propres sont uniques, $x \neq x_n$. Ainsi aucune suite n’épuise $\intco01$ : d’après la question 3 de nouveau, $\intco01$ n’est pas au plus dénombrable.

**20.** $\intco01 \subseteq \R$, donc une [injection](#def-b1-logic-inj) $\R \to \N$ se restreindrait en une [injection](#def-b1-logic-inj) de $\intco01$, ce qui contredit la question 19 : $\R$ n’est pas dénombrable. Si $\R \setminus \Q$ était au plus dénombrable, alors $\R = \Q \cup (\R \setminus \Q)$ serait une réunion de deux [ensembles](#def-b1-logic-sets) au plus dénombrables, donc au plus dénombrable d’après la question 15 (prendre $E_0 = \Q$, $E_n = \R \setminus \Q$ pour $n \geq 1$) — contradiction. Donc les irrationnels ne forment pas un [ensemble dénombrable](#pb-b1-logic-1). Précisément : dans $\R$, les rationnels forment un [ensemble dénombrable](#pb-b1-logic-1) tandis que leur complémentaire ne l’est pas ; aucune [bijection](#def-b1-logic-inj) ne pourra jamais apparier $\R \setminus \Q$ avec $\Q$ — il y a strictement « plus » d’irrationnels que de rationnels, bien que les deux [ensembles](#def-b1-logic-sets) soient infinis et tous deux denses.

**21.** $p/q$ (avec $q \neq 0$) est racine de $qX - p$, un polynôme non nul à coefficients entiers. $\sqrt 2$ est racine de $X^2 - 2$. Pour $x = \sqrt 2 + \sqrt 3$ : $x^2 = 5 + 2\sqrt 6$, donc $x^2 - 5 = 2\sqrt 6$ et $(x^2 - 5)^2 = 24$, c’est-à-dire

$$
x^4 - 10x^2 + 1 = 0 :
$$

$\sqrt 2 + \sqrt 3$ est racine de $X^4 - 10X^2 + 1$.

**22.** Envoyons $P = a_0 + a_1X + \dots + a_nX^n$ (de degré $\leq n$, à coefficients entiers) sur $(a_0, \dots, a_n) \in
\Z^{n+1}$ : c’est [injectif](#def-b1-logic-inj), puisqu’un polynôme est déterminé par ses coefficients. Par récurrence sur $n$ : $\Z^1 = \Z$ est dénombrable (question 4), et $\Z^{n+2} \approx \Z^{n+1} \times \Z$ est au plus dénombrable d’après la question 13. Chaque [ensemble](#def-b1-logic-sets) de polynômes entiers de degré borné est donc au plus dénombrable ; il est infini (il contient les constantes), donc dénombrable d’après la question 12.

**23.** L’[ensemble](#def-b1-logic-sets) de tous les polynômes entiers est $\bigcup_{n
\in \N} \{P : \deg P \leq n,\ P \text{ à coefficients entiers}\}$, une réunion dénombrable d’[ensembles dénombrables](#pb-b1-logic-1) : il est au plus dénombrable d’après la question 15, infini, donc dénombrable.

**24.** Pour chaque polynôme entier non nul $P$, l’[ensemble](#def-b1-logic-sets) des racines $R_P = \{x \in \R : P(x) = 0\}$ est fini (au plus $\deg P$ éléments, admis). D’après la question 23, les polynômes entiers non nuls peuvent être énumérés $P_0, P_1, P_2, \dots$ ; alors $\mathcal{A} =
\bigcup_{n \in \N} R_{P_n}$ est une réunion dénombrable d’[ensembles](#def-b1-logic-sets) finis (donc au plus dénombrables) : il est au plus dénombrable d’après la question 15. Il contient $\Q$ (question 21), donc il est infini : $\mathcal{A}$ est dénombrable.

**25.** Si $\R \setminus \mathcal{A}$ était au plus dénombrable, $\R = \mathcal{A} \cup (\R \setminus \mathcal{A})$ serait au plus dénombrable (question 15), ce qui contredit la question 20. Donc les [nombres transcendants](#pb-b1-logic-1) existent et forment même un [ensemble](#def-b1-logic-sets) non dénombrable, tandis que les [nombres algébriques](#pb-b1-logic-1) — qui comprennent tout nombre construit à partir des entiers par radicaux — ne forment qu’un maigre squelette dénombrable à l’intérieur de $\R$. Bilan de l’architecture : les questions 1 à 3 mettent en place le langage de la comparaison ; Cantor–Schröder–Bernstein (questions 5 à 9) permet de démontrer l’équipotence au moyen de deux [injections](#def-b1-logic-inj) faciles au lieu d’une [bijection](#def-b1-logic-inj) astucieuse, et a servi pour $\intcc01 \approx
\intoo01$, pour $\Q$ et dans toute la partie V ; la [bijection](#def-b1-logic-inj) de couplage (question 10) a alimenté les produits et les réunions dénombrables (questions 13 et 15), qui ont à leur tour alimenté $\Q$, les polynômes entiers et $\mathcal{A}$ ; l’argument diagonal (questions 18 et 19) a fourni l’unique inégalité stricte $\N \prec \R$ qui rend toute l’histoire non triviale. La conclusion de Cantor est philosophiquement frappante : la démonstration n’exhibe aucun [nombre transcendant](#pb-b1-logic-1), et pourtant elle montre qu’au sens de l’équipotence *presque tout* nombre réel est [transcendant](#pb-b1-logic-1). Nommer un [transcendant](#pb-b1-logic-1) précis — $\pi$ ou $\eu$ — a exigé des mathématiques entièrement différentes et des décennies de travail supplémentaire.