Mathématiques universitaires — Licence 1 · Bachelor Year 1

1Logique, 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 mathématique, comment les connecteurs et les quantificateurs combinent les assertions, quels coups sont autorisés dans une démonstration — puis construit, sur cette base, les deux langages universels des mathématiques : les ensembles et les applications.

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 $P$ , $Q$ , $R$ :

$\lnot(\lnot P) \iff P$ ;
lois de De Morgan : $\lnot(P \land Q) \iff (\lnot P) \lor (\lnot Q)$ et $\lnot(P \lor Q) \iff (\lnot P) \land (\lnot Q)$ ;
$(P \implies Q) \iff \bigl((\lnot P) \lor Q\bigr)$ , d’où $\lnot(P \implies Q) \iff P \land (\lnot Q)$ ;
contraposition : $(P \implies Q) \iff \bigl((\lnot Q) \implies (\lnot P)\bigr)$ ;
$(P \iff Q) \iff \bigl((P \implies Q) \land (Q \implies P)\bigr)$ ;
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 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 $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 $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 universelle est en défaut. Pour la seconde règle : « aucun $x$ ne vérifie $P$ » signifie que l’ensemble $\{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 : 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 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 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 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, $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 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 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…

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

Lorsqu’on démontre une assertion 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.

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.
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.
Les démonstrations à l’envers. Partir de la conclusion souhaitée et en déduire une assertion 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.
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 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

$P(0)$ est vraie, et
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 $\exists!\,x,\ P(x)$ est deux assertions, 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). 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 $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 d’ensembles sont des ensembles ordinaires, et le Chapitre 2 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 et 1.12.

Proposition 1.18 (Algèbre des ensembles)

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

$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)$ ;
De Morgan : $\overline{A \cup B} = \overline{A} \cap \overline{B}$ et $\overline{A \cap B} = \overline{A} \cup \overline{B}$ ;
$A \subseteq B \iff \overline{B} \subseteq \overline{A}$ .

Démonstration. Chaque identité traduit une règle de la Proposition 1.3 au moyen du dictionnaire (appartenir ou non à $A$ ) $\leftrightarrow$ (assertion 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 (6), et la dernière assertion 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. — Les lois de De Morgan 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 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 $E$ (l’ensemble de départ) exactement un élément $f(x)$ de l’ensemble $F$ (l’ensemble 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 réciproque : $f^{-1}(B)$ est définie pour toute $f$ . Les images réciproques 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).

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 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 $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 $f \colon E \to F$ est bijective si et seulement s’il existe une application $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, avec $(f^{-1})^{-1} = f$ .

Démonstration. ( $\Rightarrow$ ) Si $f$ est bijective, 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. Pour $y \in F$ , $x = g(y)$ vérifie $f(x) = y$ : $f$ est surjective.

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, 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 annoncés. Le calcul livre tout d’un coup : pour chaque $y$ de l’ensemble d’arrivée il y a exactement une solution $x$ , donc $f$ est bijective, 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. 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 d’arrivée a été correctement annoncé ( $f$ n’est pas surjective sur $\R$ ).

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

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

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

Démonstration. (1) Si $g(f(x)) = g(f(x'))$ , l’injectivité de $g$ donne $f(x) = f(x')$ , puis l’injectivité de $f$ donne $x = x'$ . Si $z \in G$ , la surjectivité de $g$ fournit $y$ avec $g(y) = z$ , puis la surjectivité de $f$ fournit $x$ avec $f(x) = y$ , de sorte que $g(f(x)) = z$ . Dans le cas bijectif, 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 conclut.

(2) Si $f(x) = f(x')$ alors $g(f(x)) = g(f(x'))$ , et l’injectivité de $g \circ f$ donne $x = x'$ . Si $z \in G$ , la surjectivité 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 (2), on ne peut pas renforcer les conclusions : $g \circ f$ bijective n’oblige pas $f$ à être surjective ni $g$ à être injective. 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, 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 intérieure pour l’injectivité et vers l’application extérieure pour la surjectivité, jamais dans l’autre sens. (L’Exercice 1.9 construit le même phénomène avec des ensembles 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 ( $f(-1) = f(1)$ ) ni surjective ( $-1$ n’a pas d’antécédent). En restreignant l’ensemble de départ et l’ensemble d’arrivée, $f \colon \R_+ \to \R_+$ , $x \mapsto x^2$ est bijective, de réciproque $y \mapsto \sqrt y$ . L’injectivité ou la surjectivité d’une application dépend des ensembles 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 $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, 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 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 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 de $E$ provient ainsi d’exactement une relation d’équivalence (« ê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 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 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 ; ses classes sont les $n$ ensembles d’entiers ayant un reste donné dans la division par $n$ . Cet exemple devient l’anneau $\Z/n\Z$ au Chapitre 7.

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.

Exemple 1.35 (Deux ordres sur la grille $\N^2$ )

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 produit). C’est bien un ordre — chaque axiome est hérité coordonnée par coordonnée — mais un ordre 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 lexicographique). La transitivité demande une vérification en deux cas mais elle est vraie, et deux couples quelconques sont désormais comparables : l’ordre est total. Les deux ordres classent le même ensemble différemment — $(0, 100) \preceq_{\mathrm{lex}} (1, 0)$ alors que l’ordre produit ne dit rien — ce qui rappelle qu’un ordre est une structure que l’on choisit, et non une propriété de l’ensemble. 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 sont la notion mathématique de « même taille ». Pour les ensembles finis, cela devient le calcul de dénombrement du Chapitre 2, où chaque formule est secrètement une bijection ; pour les ensembles 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) ne sont rien d’autre que des applications $\N \to \R$ , si bien que les assertions sur les suites sont des assertions sur un ensemble d’applications ; et l’algèbre linéaire mesurera les espaces vectoriels non pas par des bijections mais par des bijections linéaires, dont l’existence est gouvernée par un unique nombre, la dimension (Chapitre 19). Chaque fois qu’une nouvelle notion de « mêmeté » apparaît — équipotence, isomorphisme de groupes (Chapitre 7), isomorphisme linéaire — le schéma du Théorème 1.24 se répète : être « le même », c’est être relié par une application 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 est le pain quotidien des Chapitres 11 et 13 : 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, où la partition du Théorème 1.31 acquiert une structure algébrique propre. Les relations d’ordre, les majorants et les bornes supérieures deviennent le cœur axiomatique de $\R$ au Chapitre 10. Les injections, surjections et bijections reviennent comme les applications linéaires du Chapitre 20, où l’injectivité se teste sur un seul vecteur (le noyau) ; et le devoir maison ci-dessous transforme la simple notion de bijection en une théorie des tailles des ensembles infinis, dont les conclusions (dénombrabilité de $\Q$ , non-dénombrabilité de $\R$ ) refont surface aux Chapitres 10 et 12.

1.7 Exercices

Exercice 1.1 ★

Écrire la négation de chaque assertion, sans employer le mot « non » :

$\forall x \in \R,\ \exists y \in \R,\ x + y > 0$ ;
$\exists x \in \R,\ \forall y \in \R,\ xy = 0$ ;
$\forall \varepsilon > 0,\ \exists \delta > 0,\ \forall x \in \R,\ \abs{x} \leq \delta \implies \abs{f(x)} \leq \varepsilon$ (pour une application fixée $f \colon \R \to \R$ ).

Décider ensuite si les assertions (1) et (2) sont vraies.

Solution

Solution de Exercice 1.1.

Négations, en faisant passer $\lnot$ à travers chaque quantificateur (Proposition 1.5) et en utilisant $\lnot(P \implies Q) \iff P \land \lnot Q$ :

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

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

Exercice 1.2 ★

Soient $P, Q$ des assertions. À 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

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 fausse, en l’occurrence : l’implication de départ est vraie, voir le Chapitre 14).

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

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.

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$ :

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

Solution

Solution de Exercice 1.4.

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 .$
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 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

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 :

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

Solution

Solution de Exercice 1.6.

$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}$ .
En utilisant (1) et la distributivité (Proposition 1.18) : $(A \cup B) \cap \overline{C} = (A \cap \overline{C}) \cup (B \cap \overline{C})$ .
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, décider (avec démonstration) si elle est injective, surjective, bijective :

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

Pour $h$ , ajuster l’ensemble d’arrivée pour la rendre bijective et calculer la réciproque.

Solution

Solution de Exercice 1.7.

$f$ est injective ( $n + 1 = m + 1 \implies n = m$ ) mais non surjective : $0$ n’a pas d’antécédent dans $\N$ .
$g$ est bijective : $n \mapsto n - 1$ en est un inverse à gauche et à droite sur $\Z$ .
$h$ est injective : $\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 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 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 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$ .

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

Solution

Solution de Exercice 1.8.

$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')$ .
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\}$ .
( $\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. ( $\Rightarrow$ ) Soit $f$ injective et $y \in f(A) \cap f(A')$ : $y = f(x) = f(x')$ avec $x \in A$ , $x' \in A'$ ; l’injectivité 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 et que $g$ est surjective. Donner un exemple où ni $f$ ni $g$ n’est bijective.

Solution

Solution de Exercice 1.9.

$g \circ f = \mathrm{id}_E$ est injective et surjective, donc d’après la Proposition 1.26 (2), $f$ est injective et $g$ est surjective. 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 et $g$ n’est pas injective.

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 et décrire la classe d’équivalence de chaque réel $x$ . Quelles classes ont exactement un élément ?

Solution

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 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. Démontrer qu’il n’existe pas de surjection 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

Solution de Exercice 1.11.

Soit $f \colon E \to \mathcal{P}(E)$ une application 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. (En particulier aucun ensemble n’est en bijection avec son ensemble des parties : il y a « plus » de parties de $\N$ que d’entiers.)

Exercice 1.12 ★★★

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

Démontrer que $f$ est surjective si et seulement si $\Phi$ est injective.
Démontrer que $f$ est injective si et seulement si $\Phi$ est surjective.

Solution

Solution de Exercice 1.12.

( $\Rightarrow$ ) Soit $f$ surjective 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. ( $\Leftarrow$ ) Si $f$ n’est pas surjective, 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.
( $\Rightarrow$ ) Soit $f$ injective et $A \subseteq E$ . Posons $B = f(A)$ ; alors $f^{-1}(B) = \{x : f(x) \in f(A)\}$ , et l’injectivité donne $f(x) \in f(A) \iff x \in A$ , donc $\Phi(B) = A$ : $\Phi$ est surjective. ( $\Leftarrow$ ) Si $f$ n’est pas injective, prenons $x \neq x'$ avec $f(x) = f(x')$ . Toute image réciproque $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.

1.8 Problème : comparer les infinis

Problème 1.1

Quand deux ensembles ont-ils « le même nombre d’éléments » ? La réponse de Cantor — lorsqu’il existe une bijection entre eux — se révèle utilisable même pour des ensembles 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 fabriquent une bijection), 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 existent, et en masse, sans qu’on en exhibe un seul. Dans tout le problème, pour des ensembles $E$ et $F$ , on écrit $E \preceq F$ lorsqu’il existe une injection de $E$ dans $F$ , et $E \approx F$ (« $E$ et $F$ sont équipotents ») lorsqu’il existe une bijection de $E$ sur $F$ .

Partie I — Le vocabulaire de la comparaison.

Montrer que $\approx$ se comporte comme une relation d’équivalence : $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 et Proposition 1.26.)
Montrer que $\preceq$ est transitive, et qu’une injection $f \colon E \to F$ induit toujours $E \approx f(E)$ .
Soit $E \neq \emptyset$ . Montrer que $E \preceq F$ si et seulement s’il existe une surjection de $F$ sur $E$ .
Vérifier que $n \mapsto n + 1$ est une bijection 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 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. 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$ .

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.
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.)
Montrer que $h$ est injective. (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$ .)
Montrer que $h$ est surjective : é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$ .
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.
Deux applications. (a) Montrer que $\intcc01 \approx \intoo01$ . (b) Montrer que $\varphi(p, q) = 2^p(2q + 1) - 1$ définit une bijection de $\N \times \N$ sur $\N$ — injectivité par un argument de parité, surjectivité par récurrence forte (Théorème 1.12). Ainsi $\N \times \N \approx \N$ : le plan des points entiers n’est pas plus gros que la droite.

Partie III — Ensembles dénombrables. On dit qu’un ensemble $E$ est au plus dénombrable lorsque $E \preceq \N$ , et dénombrable lorsque $E \approx \N$ .

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$ .)
En déduire qu’un ensemble 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.
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.
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 ; puis appliquer la question 12.)
Montrer qu’une réunion dénombrable d’ensembles 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$ .)
Montrer que l’ensemble des parties finies de $\N$ est dénombrable. (Envoyer une partie finie $F$ sur $\sum_{i \in F} 2^i$ ; démontrer l’injectivité 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.)

Partie IV — Diagonalisation. On note $\{0,1\}^{\N}$ l’ensemble de toutes les applications $u \colon \N \to \{0, 1\}$ , c’est-à-dire l’ensemble des suites binaires.

Construire une bijection entre $\mathcal{P}(\N)$ et $\{0,1\}^{\N}$ (fonctions indicatrices).
(L’argument diagonal) Soit $\Phi \colon \N \to \{0,1\}^{\N}$ une application 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) pour $E = \N$ .
Admettre — comme cela est familier depuis le secondaire, et comme on l’établira rigoureusement au Chapitre 10 — 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.
En déduire que $\R$ n’est pas dénombrable, et que l’ensemble $\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 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 — qu’un polynôme non nul de degré $n$ a au plus $n$ racines réelles.

Montrer que tout nombre rationnel est algébrique, et trouver des polynômes explicites à coefficients entiers annulant $\sqrt 2$ et $\sqrt 2 + \sqrt 3$ .
Pour $n \in \N$ fixé, montrer que l’ensemble 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.)
En déduire que l’ensemble de tous les polynômes à coefficients entiers est dénombrable.
Démontrer le théorème de Cantor sur les nombres algébriques : l’ensemble $\mathcal{A}$ des nombres réels algébriques est dénombrable.
Conclure : il existe des nombres réels transcendants, et l’ensemble des nombres transcendants 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 sans en nommer un seul. (Démontrer qu’un nombre précis comme $\pi$ est transcendant est bien plus difficile et dépasse ce volume.)

Solution

Solution de Problème 1.1.

1. Réflexive : $\mathrm{id}_E$ est une bijection de $E$ sur lui-même. Symétrique : si $f \colon E \to F$ est bijective, le Théorème 1.24 fournit $f^{-1} \colon F \to E$ , elle-même bijective. Transitive : si $f \colon E \to F$ et $g \colon F \to G$ sont des bijections, la Proposition 1.26 (1) dit que $g \circ f \colon E \to G$ est une bijection. (Ce n’est qu’une relation d’équivalence « au sens large » : la collection de tous les ensembles n’est pas elle-même un ensemble, à cause des paradoxes qu’évoque Exercice 1.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, $g \circ f$ est injective d’après la Proposition 1.26 (1) : $E \preceq G$ . Pour le second point, corestreignons $f$ à son image : l’application $\tilde f \colon E \to f(E)$ , $x \mapsto f(x)$ , est surjective par construction de $f(E)$ et injective parce que $f$ l’est, donc bijective : $E \approx f(E)$ .

3. ( $\Rightarrow$ ) Soit $f \colon E \to F$ injective 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é), et $s(y) = a$ sinon. Pour tout $x \in E$ , $s(f(x)) = x$ , donc tout $x$ est atteint : $s$ est surjective. ( $\Leftarrow$ ) Soit $s \colon F \to E$ surjective. 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.

4. $n \mapsto n + 1$ envoie $\N$ dans $\N^*$ , est injective ( $n + 1 = m + 1 \implies n = m$ ) et surjective (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é : 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é : $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é 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 (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é 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.

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é 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, donc bijective.

9. Si $E \preceq F$ et $F \preceq E$ , choisissons des injections $f \colon E \to F$ et $g \colon F \to E$ ; les questions 5 à 8 construisent une bijection $h \colon E \to F$ , donc $E \approx F$ . L’énoncé est non trivial parce que les deux injections données n’ont aucun lien — aucune n’a besoin d’être surjective, et aucune formule mélangeant naïvement $f$ et $g$ ne définit une application : tout le contenu réside dans la 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 ; et $x \mapsto \frac{x + 1}3$ envoie $\intcc01$ injectivement dans $\intcc{\frac13}{\frac23} \subseteq \intoo01$ (c’est une application affine de pente non nulle). D’après la question 9, $\intcc01 \approx \intoo01$ — une bijection qu’il serait fort désagréable d’écrire explicitement. (b) Injectivité. 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é. 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 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 $\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) 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é découle de la stricte monotonie. Surjectivité sur $A$ : supposons qu’un certain $a \in A$ ne soit jamais atteint. Comme $\varphi(a + 1) \geq a + 1 > a$ , l’ensemble 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 $\N \to A$ , et $A$ est dénombrable.

12. Soit $E \preceq \N$ via une injection $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 finis et les ensembles dénombrables 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. Alors $(x, y) \mapsto \varphi\bigl(f(x), g(y)\bigr)$ est une injection $E \times F \to \N$ : si les images coïncident, l’injectivité 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 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 ; pour $r = 0$ prendre $0/1$ ). L’application $r \mapsto (p, q)$ est alors injective : 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 $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é de $\varphi$ donne $n(x) = n(x') = n$ et $f_n(x) = f_n(x')$ , donc $x = x'$ par injectivité 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. Donc $\Psi(F) \neq \Psi(F')$ : $\Psi$ est injective et l’ensemble des parties 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 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, chacune est une bijection : $\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, et d’après la question 3 il n’existe pas non plus d’injection $\{0,1\}^{\N} \to \N$ : $\{0,1\}^{\N}$ n’est pas au plus dénombrable. À travers le dictionnaire de la question 17, une application $\Phi \colon \N \to \{0,1\}^{\N}$ est une application $f \colon \N \to \mathcal{P}(\N)$ , et $d$ correspond à l’ensemble $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 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 $\R \to \N$ se restreindrait en une injection 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 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. Précisément : dans $\R$ , les rationnels forment un ensemble dénombrable tandis que leur complémentaire ne l’est pas ; aucune bijection ne pourra jamais apparier $\R \setminus \Q$ avec $\Q$ — il y a strictement « plus » d’irrationnels que de rationnels, bien que les deux ensembles 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, 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 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 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 : 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 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 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 existent et forment même un ensemble non dénombrable, tandis que les nombres algébriques — 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 faciles au lieu d’une bijection astucieuse, et a servi pour $\intcc01 \approx \intoo01$ , pour $\Q$ et dans toute la partie V ; la bijection 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, et pourtant elle montre qu’au sens de l’équipotence presque tout nombre réel est transcendant. Nommer un transcendant précis — $\pi$ ou $\eu$ — a exigé des mathématiques entièrement différentes et des décennies de travail supplémentaire.

Termes définis dans ce chapitre

Voir les 395 termes du glossaire