1

Cardinaux, dénombrabilité et rappels

ensemblistes

Nous faisons dans ce chapitre quelques rappels sur les cardinaux finis, et leur utilisation dans des questions
de dénombrement. Dans un second temps, nous quittons les révisions pour aborder le problème des cardinaux
infinis, beaucoup moins intuitif, l’objectif étant l’étude des ensembles de même cardinal que N, qu’on appelle
ensembles dénombrables. Les considérations sur les cardinaux infinis nous amèneront, tout comme Cantor en
son temps, à constater l’impossibilité de définir l’ensemble des ensembles. Cela nous amènera pour conclure à
quelques considérations sur l’axiomatisation de la théorie des ensembles, puis sur la construction des ensembles
usuels. Ce dernier point est davantage un pretexte pour reprendre deux points essentiels en mathématique et pas
toujours suffisamment développés en MPSI : la récurrence (et notamment les variantes que sont les récurrences
d’ordre k et la récurrence forte) et la notion d’ensemble quotient par une relation d’équivalence.

I Rappels sur les cardinaux finis

I.1 Ensembles finis, cardinaux
Nous rappelons la définition du cardinal d’un ensemble fini :
Définition 1.1.1 – Cardinal d’un ensemble fini
Soit E un ensemble.
‚ On dit que E est un ensemble fini s’il existe n P N et une bijection J1, nK Ñ E.
‚ L’entier n est alors unique, est appelé cardinal de E, et est noté |E| ou CardpEq ou 7E.

Ÿ Éléments de preuve.
L’unicité de n provient du fait qu’il ne peut pas exister de bijection de J1, nK dans J1, mK si n ‰ m, ce qui
n’est pas si évident que cela à montrer si on ne dispose d’aucun outil de cardinalité. Cela peut se faire en
montrant par récurrence sur n que si m ‰ n et f : J1, nK Ñ J1, mK, alors f n’est ni injective ni surjective.
Pour passer de n à n ` 1, considérer f pn ` 1q. Quitte à composer par une transposition bijective, on peut
considérer que f pn ` 1q “ m ` 1, ce qui permet d’enlever n d’un côté, m de l’autre (avec une discussion à
faire), pour se ramener à l’hypothèse de récurrence. ô

Lemme 1.1.2 – Finitude des sous-ensembles de J1, nK

Tout sous-ensemble F de J1, nK peut être mis en bijection avec un ensemble J1, mK, avec m § n.

Ÿ Éléments de preuve.
On peut ranger les éléments de F dans l’ordre : F “ tx1 † x2 † ¨ ¨ ¨ † xm u. ô
4 CHAPITRE 1. CARDINAUX, DÉNOMBRABILITÉ ET RAPPELS ENSEMBLISTES

Proposition 1.1.3 – Sous-ensemble d’un ensemble fini

Soit F un sous-ensemble de E. Si E est fini, alors F aussi.

Ÿ Éléments de preuve.
Restreindre et corestreindre une bijection E Ñ J1, nK et utiliser le lemme. ô

I.2 Rappel des propriétés calculatoires sur les cardinaux

Lemme 1.1.4 – Réexpression du cardinal
Soit E un ensemble fini, et A un sous-ensemble de E. Alors
ÿ
|A| “ 1A pkq.
kPE

Ÿ Éléments de preuve.
C’est évident intuitivement. Pour une bonne formalisation, par une bijection, on peut se ramener au cas
où A “ J1, pK et E “ J1, nK. ô

Proposition 1.1.5 – Cardinal d’une union disjointe

Soit A, B, A1 , . . . , An des ensembles finis.
1. Si A X B “ ?, alors |A Z B| “ |A| ` |B|.
2. Plus généralement, si pour tout pi, jq P J1, nK2 tel que i ‰ j, Ai X Aj “ ?, alors

|A1 Z ¨ ¨ ¨ Z An | “ |A1 | ` ¨ ¨ ¨ ` |An |.

Ÿ Éléments de preuve.
Le point 2 s’obtient du point 1 par récurrence. Le point 1 résulte du lemme et des propriétés des sommes
ô

Proposition 1.1.6 – Cardinal d’un complémentaire

Si A Ä B, alors |AB A| “ |B| ´ |A|.

Ÿ Éléments de preuve.
Écrire l’un des trois ensembles en jeu comme union disjointe des deux autres. ô

Corollaire 1.1.7 – Cardinal d’un sous-ensemble

Si A Ä B, alors |A| § |B|, avec égalité si et seulement si A “ B.

Ÿ Éléments de preuve.
Quel est le cardinal de AB A lorsqu’on est dans le cas d’égalité ? ô

Proposition 1.1.8 – Cardinal d’une union quelconque

Soit A et B des ensembles finis. On a :

|A Y B| “ |A| ` |B| ´ |A X B|.

Ÿ Éléments de preuve.
On peut décomposer en A Y B “ A Z pBzpA X Bqq ô
I Rappels sur les cardinaux finis 5

Proposition 1.1.9 – Cardinal d’un produit cartésien

1. Soit A et B deux ensembles finis. Alors |A ˆ B| “ |A| ˆ |B|.
2. Plus généralement, soit A1 , . . . , An des ensembles finis. Alors
π
n
|A1 ˆ ¨ ¨ ¨ ˆ An | “ |Ai |.
i“1

Ÿ Éléments de preuve.
Le point 2 s’obtient du 1 par récurrence.
Pour le point 1, découper en tranche, ou utiliser une bijection de J0, nm ´ 1K dans J0, n ´ 1K ˆ J0, m ´ 1K
définie par une opération arithmétique classique. ô

I.3 Grands principes combinatoires

Par définition même :
Proposition 1.1.10 – Injectivité, surjectivité, bijectivité et cardinal
Soit E et F deux ensembles finis, et soit f : E ݄ F une application. Alors :
1. Si f est bijective, CardpEq “ CardpF q.
2. Si f est injective, CardpEq § CardpF q
3. Si f est surjective, CardpEq • CardpF q

Ÿ Éléments de preuve.
Restreindre ou corestreindre de façon adéquate, de sorte à se ramener à une bijection. ô
Cela incite, pour des dénombrements (ou calculs de cardinaux, à se ramener par une bijection, à des modèles
simples et connus.

Méthode 1.1.11 – Combinatoire bijective

Pour dénombrer un ensemble fini E (c’est-à-dire pour déterminer son cardinal), une méthode classique
consiste à le mettre en bijection avec un ensemble dont le cardinal est connu.

Exemple 1.1.12
` ˘
Par définition des coefficients binomiaux, le cardinal de Pk pJ1, nKq est nk . En déduire le nombre de
l’ensemble des chemins monotones de p0, 0q à pa, bq dans N2 , chaque pas étant de longueur 1, et se faisant
vers la droite ou vers le haut.

Méthode 1.1.13 – Tri, partitionnement, principe additif

Si on peut trier les objets de E en plusieurs paquets disjoints E1 , . . . , En de cardinaux respectifs a1 , . . . , an ,
alors le cardinal de E est
ÿ
n
E“ ak .
k“1

Exemple 1.1.14
p ˆ
ÿ ˙ ˆ ˙
n`k n`k`1
Formule sommatoire, ou lemme de la chaussette : “ .
k“O
n n`1
6 CHAPITRE 1. CARDINAUX, DÉNOMBRABILITÉ ET RAPPELS ENSEMBLISTES

Méthode 1.1.15 – Choix successifs, principe multiplicatif

Dénombrer un ensemble se fait souvent en s’intéressant à la façon de construire un élément, en décomposant
sa construction de façon élémentaire en plusieurs étapes. Si un élément se construit en 2 étapes, et que :
‚ la première étape peut se faire de a façons différentes ;
‚ pour chaque choix de première étapes, la deuxième étape peut se faire de b façons différentes (le
nombre b ne dépendant pas de la première étape) ;
‚ toutes les constructions faites ainsi sont distinctes
alors le nombre total d’éléments est ab

Ÿ Éléments de preuve.
•
Une formalisation passe par un partionnement de l’ensemble E dénombré en Ek , où on a rangé les
kPJ1,aK
éléments à dénombrer dans des ensembles Ek , en les triant suivant le résultat de la première étape. La
troisième hypothèse certifie que l’union est disjointe (ce qui est représenté par le signe ` dans l’union), et
la deuxième hypothèse assure que les Ek sont tous de cardinal b.
Cette formalisation est équivalente au lemme du berger, stipulant que si f : E Ñ F est une surjection telle
que les images réciproques f ´1 ptyuq aient toutes même cardinal b, alors |E| “ b|F |. ô

Exemple 1.1.16
Dénombrement des injections, cardinal de Sn .

Remarque 1.1.17
Les deux méthodes peuvent être combinées, par exemple un tri, et pour chaque part du tri, une succession
de choix.

Exemple 1.1.18
ÿn ˆ ˙ˆ ˙ ˆ ˙
a b a`b
Formule de Vandermonde : “
k“0
k n´k n

Méthode 1.1.19 – Formalisation par couple, et lecture inverse

Une formalisation mathématique de deux choix successifs peut se faire sous forme d’un couple, en mettant
E en bijection avec un ensemble F de couples px, yq où x est le résultat du premier choix, y le résultat du
deuxième choix. Il y a souvent des contraintes entre x et y (liés à la façon de procéder au second choix).
Ces contraintes définissent une propriété satisfaite par x et y, qu’on note Ppx, yq. Ainsi

F “ tpx, yq | Ppx, yqu

. Sous cette forme on peut voir que la contrainte peut souvent être retournée en lisant le couple dans
l’autre sens : F et clariement en bijection avec

G “ tpy, xq | Ppx, yqu

Cela revient à intervertir le rôle des deux étapes, donc l’ordre dans lequel on effectue la construction.

Exemple 1.1.20
La formule du capitaine, ou comité-président.
II Dénombrabilité 7

Méthode 1.1.21 – Démonstration ou interprétation combinatoire d’une formule

‚ Interpréter combinatoirement une formule permet d’en avoir une compréhension intuitive et natu-
relle, qui aide à la retenir ou a la retrouver.
‚ Cela permet également éventuellement de la démontrer, comme la formule de Vandermonde ci-
dessus.
‚ Pour démontrer ou interpréter combinatoirement une formule, chercher un modèle adéquat, et
dénombrer de deux façons différentes, par exemple de façon directe et en effectuant un tri, ou bien
en effectuant des choix successifs dans des ordres différents etc.

Exemple 1.1.22
ÿn ˆ ˙
n
Interpréter combinatoirement la formule “ 2n .
k“0
k

Méthode 1.1.23 – Signes, principe de l’interrupteur

‚ Une formule combinatoire ne contient a priori que des termes positifs. Certaines formules contenant
aussi des signes négatifs peuvent quand même se démontrer combinatoirement, en réarrageant
l’égalité de sorte à passer les termes négatifs de l’autre côté. On a alors deux quantités à comparer,
ce qu’on peut faire combinatoirement, par exemple en établissant des bijections.
‚ Une situation classique : des signes qui alternent devant une expression avec des coefficients bino-
miaux : il s’agit de comparer des ensembles ayant des cardinaux de parité différente : pour cela, faire
entrer ou sortir un élément (interrupteur qu’on allume ou éteint). On illustre cela dans l’exemple
qui suit, qui est à peu près le plus simple du genre.

Exemple 1.1.24
ÿ
n ˆ ˙
n
Montrer combinatoirement que p´1q k
“ 0 si n ° 0.
k“0
k

II Dénombrabilité
II.1 Cardinaux infinis
On ne peut pas définir d’emblée (en tout cas pas simplement) de cardinal d’un ensemble infini. Cantor fait
une construction (compliquée) qui permet de définir des cardinaux (ou plutôt des classes cardinales) de façon
explicite, mais ce n’est pas l’objet de ce cours. Nous nous contentons de définir la condition d’égalité des
cardinaux.
Définition 1.2.1 – Ensembles de même cardinal
Soit E et F deux ensembles.
‚ On dit que E et F ont même cardinal s’il existe une bijection f : E Ñ F . On dit aussi que E est
équipotent à F .
‚ On dit que E est subpotent à F (ou que le cardinal de E est strictement inférieur à celui de F ) s’il
existe une injection de E dans F .

Remarque 1.2.2 – (HP)

‚ On peut montrer que la relation de subpotence vérifie les propriétés d’une relation d’ordre sur
les classes cardinales. L’antisymétrie provient d’un théorème classique dû à Cantor et Berstein,
affirmant que s’il existe une injection f : E Ñ F , et une injection g : F Ñ E, alors il existe une
bijection E Ñ F .
8 CHAPITRE 1. CARDINAUX, DÉNOMBRABILITÉ ET RAPPELS ENSEMBLISTES

‚ Avec l’axiome du choix que nous évoquerons plus loin, on peut montrer que cette « relation d’ordre »
est totale.

Attention, certaines intuitions sur les comparaisons de cardinaux d’ensembles finis peuvent être fausses dans ce
contexte.
Avertissement 1.2.3
Deux ensembles vérifiant une inclusion stricte E à F peuvent être de même cardinal. Pourtant F contient
strictement plus d’éléments que E.

Exemple 1.2.4 – Hôtel de Hilbert

f : N Ñ N˚ tel que f pnq “ n ` 1 est une bijection. Donc N et N˚ ont même cardinal.

II.2 Dénombrabilité
Définition 1.2.5 – Ensemble dénombrable
Soit E un ensemble. On dit que :
‚ E est dénombrable s’il est de même cardinal que N ;
‚ au plus dénombrable s’il est fini ou dénombrable.

Ainsi, E est dénombrable si et seulement s’il existe une bijection f : N Ñ E.

Proposition 1.2.6 – Dénombrabilité de N2

Le produit cartésien N2 est dénombrable.

Ÿ Éléments de preuve.
Construire une bijection en diagonales. Ou bien utiliser une bijection classique entre N2 et N˚ , basée sur
l’étude des facteurs pairs de la décomposition de n en produit de facteurs premiers. ô
Nous souhaitons caractériser les ensembles au plus dénombrables à l’aide des sous-ensembles de N. Pour cela,
nous commençons pas établir un lemme sur le cardinal des sous-ensembles de N.

Lemme 1.2.7
Tout sous-ensemble de N est au plus dénombrable.

Ÿ Éléments de preuve.
Considérer un sous-ensemble E P PpNq, non fini. Construire par récurrence une application injective de
J0, nK dans E, en rajoutant à chaque étape le minimum des éléments non encore utilisés. Cela définit une
bijection N Ñ E. ô

Proposition 1.2.8 – Première caractérisation des ensembles au plus dénombrables

Un ensemble E est au plus dénombrable si et seulement s’il peut être mis en bijection avec une partie de
N.

Ÿ Éléments de preuve.
Un sens est évident par les définitions de la finitude ou de la dénombrabilité. L’autre provient du lemme.
ô
Nous donnons une deuxième caractérisation des ensembles au plus dénombrables en terme de surjection ou
d’injection. Cette caractérisation est plus souple pour prouver les différentes propriétés de dénombrabilité liées
aux constrructions ensemblistes. Cette caractérisation nécessite un petit lemme.
II Dénombrabilité 9

Lemme 1.2.9 – Inversibilité à gauche ou droite des injections et surjections

Soit f : E Ñ F .
1. Si f est injective, il existe g : F Ñ E telle que g ˝ f “ idE , et g est alors surjective.
2. (avec AC) Si f est surjective, il existe g : E Ñ F telle que f ˝ g “ idF , et g est alors injective.

Ÿ Éléments de preuve.
On construit g associant à y un de ses antécédents. Dans le premier cas, on n’a pas le choix quand on est
dans l’image de f , et sinon, on définit g comme on veut. Dans le deuxième cas, on doit choisir parmi les
antécédents de y. ô

Remarque 1.2.10
‚ Ce sont en fait des équivalences.
‚ On utilise l’axiome du choix (qui affirme la possibilité de pouvoir faire simultanément une infinité
de choix).

Proposition 1.2.11 – Deuxième caractérisation des ensembles au plus dénombrables

Soit E un ensemble non vide. Les trois propriétés suivantes sont équivalentes :
(i) E est au plus dénombrable
(ii) il existe une fonction injective f : E ݄ N.
(iii) il existe une fonction surjective f : N ݄ E.

Ÿ Éléments de preuve.
‚ piq ùñ piiq : considérer une bijection E Ñ F Ä N, et composer par l’injection canonique.
‚ piiq ùñ piiiq : c’est l’inversibilité à gauche d’une injection
‚ piiiq ùñ piiq : c’est l’inversibilité à droite d’une surjection. Pourquoi l’axiome du choix n’est-il pas
nécessaire ici ?
‚ piiq ùñ piq : corestriction à l’image.
ô

II.3 Règles opératoires sur les ensembles dénombrables

Proposition 1.2.12 – Construction d’ensembles dénombrables
1. Si E et F sont au plus dénombrables, alors E ˆ F est au plus dénombrable.
2. Plus généralement, un produit E1 ˆ ¨ ¨ ¨ ˆ En d’un nombre fini d’ensembles au plus dénombrables
est au plus dénombrable. Si l’un d’eux est dénombrable et les autres non vides, alors le produit est
dénombrable.
3. Une union d’un nombre au plus dénombrable d’ensembles au plus dénombrables est au plus dé-
nombrable. Si l’un des ensembles est dénombrable, l’union est dénombrable.

Ÿ Éléments de preuve.
1. Construire une surjection par composition : N Ñ N ˆ N Ñ E ˆ F
2. Récurrence
3. Supposons les ensembles indexés sur I dénombrable. Construire une surjection
§
NÑNˆNÑI ˆNÑ Ai .
iPI

ô
10 CHAPITRE 1. CARDINAUX, DÉNOMBRABILITÉ ET RAPPELS ENSEMBLISTES

Corollaire 1.2.13
1. L’ensemble Z est dénombrable.
2. L’ensemble Np est dénombrable.
3. L’ensemble Q des rationnels est dénombrable.

Un résultat important sur les familles sommables découle de ces propriétés. On rappelle la définition suivante.

Définition 1.2.14 – Support d’une famille de scalaires

Soit a “ pai qiPI une famille de réels ou complexes. Le support de a est l’ensemble

J “ ti P I | ai ‰ 0u.

Proposition 1.2.15 – Support d’une famille sommable

Soit a “ pai qiPI une famille de réels ou complexes. Si a est sommable, alors le support de a est au plus
dénombrable.

Ÿ Éléments de preuve.
Se ramener au cas d’une famille réelle positive, en contrôlant le support de a en fonction de celui des parties
positives et négatives de ses parties réelles et imaginaires.
Dans le cas positif, exprimer le support en fonction des

I" “ ti P I | ai ° "u.

Que peut-on dire du cardinal de I" ? ô

II.4 Des ensembles infinis non dénombrables

Comme on l’a vu, des ensembles qui semblent bien plus gros que N sont dénombrables, donc ont dans les faits
« autant » d’éléments que N. Une question qui peut se poser alors est de savoir si tous les ensembles infinis ont
même cardinal, ou s’il existe d’autres cardinaux (plus gros). Un premier élément de réponse provient de l’étude
du cardinal de R, à partir de l’écriture décimale d’un nombre réel. On rappelle qu’un nombre réel admet un et
un seul développement décimal, à condition d’exclure les développements terminant uniquement par une infinité
de 9.

Théorème 1.2.16 – Cardinal de R, Cantor

L’ensemble des réels R est non dénombrable.

Ÿ Éléments de preuve.
(démonstration non exigible) Sinon, considérer une énumération pxn qnPN˚ de tous les réels, et considérer
un y tel que le n-ième chiffre après la virgule de y soit distinct de 0, 9 et du n-ième chiffre de xn . Le réel
y peut-il être dans l’énumération ? Pourquoi prendre la précaution de prendre les chiffres distincts de 0 et
9? ô
Cette preuve est connue sous le nom d’« argument diagonal de Cantor », dont une généralisation donne un
deuxième élément de réponse à la question initiale :

Théorème 1.2.17 – Cantor, HP

Soit X un ensemble infini. Alors CardpXq † CardpPpXqq (i.e. X est subpotent à PpXq, mais pas équipo-
tent)
III Conséquences ensemblistes (HP) 11

Ÿ Éléments de preuve.
S’il existe une surjection f : X Ñ PpXq, considérer Y Ä X constitué des éléments x tels que x R f pxq, et
obtenir une contradiction en considérant l’appartenance de c à Y , c étant un élément de X tel que f pcq “ Y .
ô
On peut donc construire une chaîne infinie d’ensembles ayant des cardinaux strictement croissants. Il y a donc
une infinité de cardinaux infinis distincts.
Remarque 1.2.18
En quoi le résultat précédent empêche-t-il l’existence d’un « ensemble des ensembles » ?

III Conséquences ensemblistes (HP)

III.1 La crise des fondements et l’axiomatisation de la théorie des ensembles
Remarques 1.3.1
‚ La dernière remarque montre qu’il n’est pas possible de considérer tout « groupement » d’objets
comme un ensemble. Les résultats de Cantor semblent donc suggérer que le point de vue formel
adopté jusqu’à la fin du XIXe siècle n’est donc pas valide. Georg Cantor en est conscient à partir
de 1896, date de ces travaux.
‚ La contradiction de cette théorie naïve des ensembles peut aussi être perçue au travers du paradoxe
de Russell (basée sur les principes diagonaux de Cantor) : en 1901, Bertrand Russell définissant

E “ tensembles F qui ne se contiennent pas eux-mêmesu,

si E était un ensemble :
˚ si E R E, alors par définition de E, E est élément de E, d’où une contradiction ;
˚ si E P E, alors, par définition de E, E n’est pas élément de E, d’où une contradiction.
Cet argument très simple montre que E ne peut pas être un ensemble.

Au début du XXe siècle, un petit groupe de mathématiciens, motivés par les 23 « problèmes de Hilbert » exposés
en 1900 au congrès international des mathématiciens (donc certains sont encore irrésolus de nos jours), se penche
sur une formalisation rigoureuse du socle mathématique que représente la théorie des ensembles. La tâche est
délicate, et il faudra plusieurs tentatives pour parvenir à une axiomatisation satisfaisante. L’axiomatisation
finalement retenue est celle de Zermelo et Fraenkel (ZF), à laquelle on rajoute souvent l’axiome du choix (ZFC).
Dans cette théorie, les éléments eux-même sont tous des ensembles.
Axiome 1.3.2 – les axiomes de la théorie de Zermelo-Fraenkel, HP
Voici les noms des différents axiomes, et leur interprétation intuitive :
‚ Axiome d’extentionnalité : c’est lui qui dit que deux ensembles sont égaux si et seulement si ils ont
mêmes éléments. Cet axiome est notamment à la base du principe de double-inclusion.
‚ Axiome de la paire : il affirme l’existence des paires ta, bu, lorsque a et b sont deux ensembles. En
particulier, l’axiome de la paire affirme aussi l’existence des singletons tau, pour un ensemble a
(prendre a “ b !)
‚ Axiome de la réunion : il donne la possibilité de construire des unions des éléments d’un ensemble
(ces éléments étant eux-même des ensembles)
‚ Axiome des parties : il affirme que si a est un ensemble, alors Ppaq aussi.
‚ Schéma d’axiome (i.e. série d’axiomes) de compréhension : il permet en particulier de définir un
ensemble par compréhension (comme sous-ensemble d’un ensemble donné, constitué des éléments
vérifiant une certaine propriété)
‚ Axiome de l’infini : il donne l’existence de l’infini, et notamment des ensembles infinis.
‚ Axiome de fondation : il dit en particulier qu’un ensemble ne peut pas s’appartenir (on ne peut pas
12 CHAPITRE 1. CARDINAUX, DÉNOMBRABILITÉ ET RAPPELS ENSEMBLISTES

avoir x P x). Plus généralement, il n’y a pas de cycle pour la relation d’appartenance.

Remarque 1.3.3
1. L’axiome de la paire, couplée à l’axiome de l’union, permet de considérer AYB pour tous ensembles
A et B
2. En itérant cet argument, on peut considérer l’union de n ensembles.
3. L’intersection d’une famille quelconque (non réduite à l’ensemble vide) d’ensembles s’obtient par
compréhension (axiome de compréhension, en se plaçant globalement dans un des ensembles don-
nés).
4. L’union d’une famille quelconque est plus délicate ; il faut déjà préciser ce qu’on entend par famille
pai qiPI : il s’agit d’une application d’un ensemble I dans un autre ensemble E qui à i P I associe
ai . Ainsi, les ai doivent eux-même être des éléments d’un ensemble. Dans ce cas, l’image tai , i P Iu
de cette famille est un ensemble (on peut la définir par compréhension), donc on peut considérer
l’union de ses éléments (axiome de l’union).
5. L’existence (et l’unicité) de l’ensemble vide provient de l’axiome de compréhension, à partir d’un
ensemble A quelconque (on sait qu’il existe au moins un ensemble, d’après l’axiome de l’infini ; de
toute façon, si ce n’était pas le cas, la théorie serait bien pauvre). L’ensemble vide peut alors se
définir par compréhension de la façon suivante :

? “ tx P A | x ‰ xu.

III.2 L’axiome du choix

L’axiome du choix est un axiome qui semble bien naturel, mais qui peut aussi avoir des conséquences surprenantes
(comme le paradoxe de Banach-Tarski, qui dit en gros qu’on peut « découper » une sphère à la façon d’un
puzzle de sorte à reconstituer deux sphères de même rayon que la première en réassemblant différemment les
morceaux...)
Axiome 1.3.4 – Axiome du choix, HP
Soit I un ensemble, et pAi qiPI une famille d’ensembles non vide. Alors, il existe (et on peut donc se donner)
une famille pai qiPI telle que pour tout i P I, ai P I.

Remarques 1.3.5
§
‚ L’axiome du choix équivaut à l’existence d’une fonction f : I ›Ñ Ei telle que pour tout i P I,
iPI
f piq P Ei , appelée fonction de choix. Il suffit en effet de poser f piq “ ai . Il se réexprime donc par la
propriété
˜ ¸I
§
Ei ‰ ?.
iPI

‚ Par définition formelle du symbole logique D, le fait que Da, a P A, permet de « disposer » d’un
élément a P A, donc d’en choisir un et de le poser. Le problème du choix ne se pose donc pas
lorsqu’il n’y a qu’un élément à choisir dans un ensemble.
Par itération finie (successive), le choix d’un nombre fini d’éléments n’est pas plus problématique.
L’axiome du choix n’apporte rien pour les familles finies, et il est inutile (et malvenu) de le men-
tionner dans ces situations.
‚ En revanche, le cas de familles infinies (i.e. I infini) est plus problématique, car en logique formelle,
où toute écriture est finie, l’existence d’éléments dans chacun des ensembles d’une famille infinie
d’ensembles ne peut pas s’obtenir par itération de quantificateurs existentiels. On peut donc poser
successivement des éléments dans chacun des ensembles, mais rien ne nous assure qu’on peut poser
III Conséquences ensemblistes (HP) 13

« simultanément » des éléments ai de chacun des Ai . C’est cette simultanéité qui est en jeu dans le
fait de considérer des familles pai qiPI .

Proposition 1.3.6 – AC ou pas AC, HP et très difficile

L’axiome du choix est indépendante de l’axiomatique ZF.
Autrement dit, il ne peut être ni démontré ni réfuté à partir de l’axiomatique ZF.

Ainsi, ZF (Zermelo-Fraaenkel sans AC) et ZFC (Zermelo-Fraaenkel avec AC) sont toutes les deux des théories
non contradictoires. En pratique, la plupart des mathématiciens utilisent l’axiomatique ZFC, car sans axiome
du choix, on ne va pas très loin.

Exemple 1.3.7
Nous avons déjà pu constater l’importance de l’axiome du choix dans des situations pourtant apparemment
simples, au travers de la démonstration du lemme 1.2.9 sur l’inversibilité à gauche ou droite des injections
et des surjections. Dans cet exemple :
1. Comprenez-vous bien pourquoi on a besoin d’axiome du choix pour inverser les surjections, mais
pas pour inverser les injections ?
2. A-t-on vraiment besoin de l’AC dans le cas où F est fini ? Et si E est fini ?
3. Pourquoi n’a-t-on pas besoin d’AC si E est un sous-ensemble de N ?

III.3 Une forme équivalente de l’axiome du choix : lemme de Zorn

Nous donnons dans ce paragraphe une forme équivalente de l’axiome du choix, souvent plus pratique à utiliser.
Pour cela, nous devons d’abord faire quelques rappels (ou compléments) sur les ordres partiels.
On rappelle qu’une relation d’ordre § sur un ensemble E est une relation réflexive, antisymétrique et transitive
En général, il peut exister des éléments x et y de E tels que x et y ne soient pas comparables (i.e. on n’a ni
x § y, ni y § x). On dit alors que l’ordre est partiel. Ceci est illustré dans l’ordre défini par dans la figure
1.1, dans lequel x § y si et seulement si on peut aller de x à y par une succession d’arêtes montantes. Une
telle représentation où on n’a pas représenté toutes les arêtes pouvant se déduire de la transitivité est appelée
« diagramme de couverture de la relation § ». On dira que y couvre x si x † y, et qu’aucun z ne peut s’insérer
strictement entre x et y. Cela correspond aux arêtes représentées du diagramme de couverture.
Dans ce contexte, certains éléments vérifient des propriétés de minimalité ou de maximalité intéressantes sans
pour autant être un minimum ou un maximum. Par exemple, dans l’exemple 1.1, x6 ne possède aucun majorant
strict, mais n’est pas pour autant un maximum, car il n’est pas plus grand que tout élément. C’est ceci qui va
différencier la notion d’élément maximum et la notion d’élément maximal.

Définition 1.3.8 – Élément minimal, maximal, HP

Soit pE, §q un ensemble muni d’une relation d’ordre.
1. Un élément m de E est appelé élément minimal de E s’il n’existe pas d’élément x de E tel que
x † m.
2. Un élément M de E est appelé élément maximal s’il n’existe pas d’élément x de E tel que x ° M .

Ainsi, m est mimimal si pour tout x P E comparable à m, x • m. Mais il peut aussi exister des éléments
incomparables à m, et dans ce cas, m n’est pas minimum.

Exemple 1.3.9
Dans l’exemple de la figure 1.1 :
‚ x1 est le seul élément minimal. Il est aussi le minimum.
14 CHAPITRE 1. CARDINAUX, DÉNOMBRABILITÉ ET RAPPELS ENSEMBLISTES

x7 x6

x4 x5

x8
x2 x3

x1

Figure 1.1 – Une relation d’ordre

‚ x6 est un élément maximal, mais pas maximum, car par exemple, x6 et x7 ne sont pas comparables.
‚ x7 et x8 sont également maximaux, mais pas maximums.

Proposition 1.3.10 – Existence d’un élément maximal

Soit E un ensemble fini et non vide muni d’une relation d’ordre §. Alors E admet au moins un élément
maximal.

Ÿ Éléments de preuve.
Par l’absurde, partir de x0 P E, puis, xn étant construit, puisqu’il n’est pas maximal, considérer xn`1 ° xn .
ô
L’existence d’un élément maximal lorsque E est infini n’est pas systématique, comme le montre le cas de R.
Mais l’axiome du choix va permettre de donner une condition d’existence (l’énoncé est même équivalent à l’AC).
Pour donner cette condition, nous avons besoin d’une définition supplémentaire.

Définition 1.3.11 – Ensemble inductif, HP

Soit pE, §q un ensemble ordonné non vide. On dit que E est un ensemble inductif si pour tout sous-
ensemble F Ä E totalement ordonné, F admet un majorant dans E.

Théorème 1.3.12 – Lemme de Zorn, ou de Kuratowski-Zorn, HP, admis et difficile

(Avec AC) Tout ensemble inductif admet un élément maximal.

Ÿ Éléments de preuve.
Voir le problème 2 de la sélection disponible sur mon site web. ô
IV Ensembles usuels 15

Remarque 1.3.13
Le lemme de Zorn est en fait équivalent à l’axiome du choix.

Nous terminons cette section fortement hors programme par une application du lemme de Zorn en algèbre
linéaire. Vous avez démontré l’année dernière qu’un espace vectoriel de dimension finie admet nécessairement une
base. Vous vous êtes peut-être demandé si cela reste vrai en dimension quelconque. De même pour l’existence de
supplémentaires. Les deux propriétés résultent, avec AC, d’une généralisation du théorème de la base incomplète.
Théorème 1.3.14 – Théorème de la base incomplète en dimension infinie, avec AC, HP
Soit E un espace vectoriel sur K, L une partie libre de E et G une partie génératrice. Il existe G0 Ä G telle
que G0 X L “ ? et L Z G0 forme une base de E.

Ÿ Éléments de preuve.
‚ Considérer
H “ tG 1 Ä G | G 1 libre et VectpLq X VectpG 1 q “ t0uu,
ordonné par inclusion. Montrer que H est inductif.
‚ Considérer alors un élément maximal G0 . Si L Y G0 n’est pas une base de E, rajouter à G0 un élément
pour contredire sa maximalité.
ô

Corollaire 1.3.15 – Existence de bases et de supplémentaires, avec AC, HP

Soit E un espace vectoriel sur K.
1. E admet au moins une base.
2. Tout sous-espace F de E admet un supplémentaire dans E.

IV Ensembles usuels
IV.1 L’ensemble N des entiers naturels
La construction de N est hors programme.
Définition 1.4.1 – Définition inductive de N
L’ensemble N est caractérisé par :
(i) l’existence d’un élément « initial » noté 0
(ii) l’existence, pour tout x P N d’un élément successeur, noté x ` 1
(iii) l’existence, pour tout x P N différent de l’élément initial 0, d’un unique élément prédecesseur y tel
que x soit sucesseur de y
(iv) la minimalité de N (au sens de l’inclusion) : si E Ä N vérifie 0 P E, ainsi que la stabilité par successeur
et prédecesseur (pour x ‰ 0), alors E “ N.

La construction des ordinaux de Cantor (dans le cadre formel de la théorie des ensembles) permet de justifier
l’existence d’un tel ensemble N.
Si N est un ensemble vérifiant (i), (ii) et (iii), on définit une relation d’ordre x § y ssi x “ y ou bien y s’obtient
de x en itérant un nombre fini de fois la relation successeur.
Proposition 1.4.2 – Axiome de récurrence et propriété fondamentale
Soit N un ensemble vérifiant les points (i), (ii) et (iii) de la définition précédente. Alors les propriétés
suivantes sont équivalentes :
(iv) N est minimal (au sens précédent).
16 CHAPITRE 1. CARDINAUX, DÉNOMBRABILITÉ ET RAPPELS ENSEMBLISTES

(iv’) N vérifie l’axiome de récurrence : pour toute propriété P définie sur N ,

pPp0q ^ @n P N, Ppnq ùñ Ppn ` 1qq ùñ p@n P N, Ppnqq

(iv”) N vérifie la propriété fondamentale : toute partie non vide et majorée de N admet un plus grand
élément.

Remarque 1.4.3
La propriété fondamentale (iv”) équivaut aussi à l’existence d’un minimum de toute partie non vide.

Ÿ Éléments de preuve.
‚ (iv) ùñ (iv’) : considérer P vérifiant pPp0q ^ @n P N, Ppnq ùñ Ppn ` 1qq. Considérer E “ tn P
N, Ppnqu. Montrer que E vérifie (i), (ii) et (iii).
‚ (iv’) ùñ (iv”) : récurrence sur la valeur d’un majorant.
‚ (iv”) ùñ (iv) : Considérer E Ä N tel que 0 P E et vérifiant (ii) et (iii). Si N zE ‰ ?, considérer son
minimum m ‰ 0 et obtenir une contradiction portant sur le prédecesseur de m.
Même si c’est redondant, on donne également les implications suivantes, qui sont assez instructives (no-
tamment (iv”) ùñ (iv’) qui donne une façon de remplacer une preuve par récurrence par une preuve par
minimalité, ce qui simplifie parfois la rédaction).
‚ (iv’) ùñ (iv) : si E Ä N vérifie (i), (ii) et (iii), considérer la propriété Ppnq : n P E.
‚ (iv”) ùñ (iv’) : si (iv”) est vérifié, soit P une propriété satisfaisant les hypothèses de l’axiome de
récurrence (initialisation et hérédité). Si P contredit l’axiome de récurrence, considérer m le minimum
des éléments tels que Ppmq soit faux, et obtenir une contradiction avec m ´ 1.
ô
Ainsi, la propriété (iv) de la définition de N est souvent remplacée par l’axiome de récurrence ou par la propriété
fondamentale.
Vous avez déjà largement utilisé l’axiome de récurrence pour démontrer des propriétés dépendant d’un entier.
Nous en donnons des variantes, classiques, mais qui ne sont pas toujours vues en MPSI.

Méthode 1.4.4 – Récurrence d’ordre k

Il s’agit d’une variante du principe de récurrence, s’exprimant ainsi :

ppPp0q ^ ¨ ¨ ¨ ^ Ppk ´ 1qq ^ p@n P N, Ppnq ^ ¨ ¨ ¨ ^ Ppn ` k ´ 1q ùñ Ppn ` kqqq ùñ @n P N, Ppnq.

‚ Principe : on utilise la propriété aux k rangs précédents pour montrer l’hérédité.

‚ Schéma de rédaction :
˚ Initialisation : montrer Pp0q, . . . , Ppk ´ 1q.
˚ Hérédité : poser n • 0, supposer Ppnq, . . . , Ppn ` k ´ 1q, en déduire Ppn ` kq.
˚ Conclure en faisant appel au principe de récurrence.

Avertissement 1.4.5
Ne pas oublier d’initialiser pour les k premières valeurs ! (sinon la première implication de l’hérédité n’est
pas valable)

On peut bien sûr adapter le principe dans le cas où le rang initial n’est pas 0.

Exemple 1.4.6
Soit pFn qnPN définie par F0 “ 0, F1 “ 1 et pour tout n • 0, Fn`2 “ Fn`1 ` Fn (suite de Fibonacci).
Montrer que pour tout n P N, Fn est pair si et seulement si n est multiple de 3.
IV Ensembles usuels 17

Pour votre culture, ce dernier exemple est une situation particulière du résultat plus général suivant :

@pm, nq P pN˚ q2 , Fm^n “ Fm ^ Fn ,

avec m “ 3 (ici, ^ désigne le pgcd).

Voici une dernière variante du principe de récurrence :

Méthode 1.4.7 – Récurrence forte

La récurrence forte est basée sur la propriété formelle suivante :

pPp0q ^ p@n • 1, Pp0q ^ ¨ ¨ ¨ ^ Ppn ´ 1q ùñ Ppnqqq ùñ @n P N, Ppnq.

‚ Principe : on suppose la propriété vraie à tous les rangs précédents pour la montrer à un rang
donné.
‚ Schéma de rédaction :
˚ Initialisation pour Pp0q (une seule valeur suffit ici)
˚ Poser n ° 0, supposer Ppkq vrai pour tout k † n, et montrer qu’alors Ppnq est vrai.
˚ Conclure en faisant référence au principe de récurrence.

Exemples 1.4.8
On rappelle qu’un nombre n P N˚ est premier s’il est distinct de 1 et si ses seuls diviseurs sont 1 et n. On
dit que n est composé si n ‰ 1 et n n’est pas premier. Par définition, il existe alors d1 et d2 tous deux
distincts de 1 tels que n “ d1 d2 .
1. Montrer que tout nombre entier n • 2 admet un diviseur premier.
2. Montrer que tout nombre entier n • 1 admet une décomposition en produit de nombres premiers
(on rappelle que par convention, un produit vide est égal à 1).

Remarque 1.4.9
On retiendra du dernier exemple que le principe de récurrence forte est en particulier très utile dans de
nombreuses questions liées à des propriétés de divisibilité.

Théorème 1.4.10
Les trois principes de récurrence ci-dessus sont équivalents

Ÿ Éléments de preuve.
Le principe de récurrence forte et le principe de récurrence d’ordre k impliquent chacun le principe ré-
currence simple, car qui peut le plus, peut le moins. Réciproquement, poser respectivement Qpnq “
Pp0q ^ ¨ ¨ ¨ ^ Ppnq ou Qpnq “ Ppn ´ k ` 1q ^ ¨ ¨ ¨ ^ Ppnq (éventuellement en complétant Ppnq par la
propriété toujours vraie pour n négatif), et appliquer le principe de récurrence simple à Q. ô

IV.2 Z, Q et R
Pour étendre la définition des entiers afin de définir des ensembles plus gros, on utilise ensuite à peu près
systématiquement la même technique : on construit des objets sans se préoccuper des redondances, puis on
« quotiente » par une relation d’équivalence pour gommer formellement les redondances. C’est cette notion
d’ensemble quotient (idée centrale dans toutes les branches des mathématiques) que je veux mettre en avant
dans ce paragraphe ; les constructions de Z, Q et R ne sont que des prétextes et illustrations.
18 CHAPITRE 1. CARDINAUX, DÉNOMBRABILITÉ ET RAPPELS ENSEMBLISTES

Définition 1.4.11 – Ensemble quotient par une relation d’équivalence

Soit E un ensemble, muni d’une relation d’équivalence R. L’ensemble quotient E{R est l’ensemble des
classes d’équivalences de E par R.

Ainsi, si pour tout x, x P PpEq représente la classe d’équivalence de x (donc tous les y P E équivalents à x),
alors
E{R “ tx, P Eu.
Formellement, E{R P PpPpEqq, mais en pratique, on se préoccupe peu de cette nature ensembliste. Il s’agit
intuitivement de construire un nouvel ensemble avec les éléments de E, dans lequel on considère que x et y sont
égaux dès lors que xRy dans E.

Exemples 1.4.12
1. À partir des entiers naturels, on veut construire Z, qui peut être obtenu (avec redondance) comme
l’ensemble des x ´ y, avec x et y dans N. Un deuxième couple px1 , y 1 q définit le même entier relatif
si
x ´ y “ x1 ´ y 1 .
Pour que cette relation soit intrinsèque à N (puisque pour le moment Z n’est pas connu), on la
réécrit
x ` y 1 “ x1 ` y.

On munit donc l’ensemble N ˆ N de la relation R

px, yqRpx1 , y 1 q ñ x ` y 1 “ x1 ` y.

L’ensemble Z peut alors être défini comme l’ensemble N2 {R.

On remarque que formellement, par cette construction, N Ç Z, mais on peut identifier les éléments
n de N à la classe des couples pn, 0q dans Z. L’ensemble de ces classes pn, 0q définit un sous-ensemble
N Ä Z, qui vérifie les mêmes propriétés que N, et qu’on peut donc prendre comme nouveau N, de
sorte à avoir N Ä Z.
2. La construction de Q est exactement la même à partir de Z que celle de Z à partir de N en remplaçant
la différence par le quotient, et en interdisant le quotient par 0 : on construit formellement des
couples pa, bq P Z ˆ Z˚ (ou Z ˆ N˚ suffit), qui représenteront les fractions ab . Pour gommer les
redondances, on quotiente par la relation

pa, bqRpa1 , b1 q ñ ab1 “ a1 b.

C’est d’ailleurs la même construction qui permet de définir les fractions rationnelles KpXq à partir
des polynômes KrXs.

C’est un peu plus compliqué de définir R à partir de Q, mais le principe est globalement le même : contruire un
plus gros ensemble, en s’arrangeant pour vérifier les propriétés voulues (par exemple en rajoutant des éléments
manquants), puis en quotientant pour gommer les redondances.
Plusieurs constructions sont valides, basés sur l’équivalence entre :
‚ la propriété fondamentale de R
‚ la description des intervalles par les bornes (notamment les intervalles minorés et non majorés, donnant
la construction par coupures de Dedekind)
‚ la propriété des suites adjacentes
‚ la convergence des suites de Cauchy (construction de Meray)