Lycée Lakanal, Sceaux Pour le 18/09/2024, 19h00

MP – Mathématiques
A. Troesch

DM no 2 : Cardinaux, dénombrabilité

Ce DM est à rendre au format numérique, scanné en pdf en un seul fichier n’excédant pas 10 Mo. L’envoi se fera
via Cahier-de-Prépa avant la date et heure ci-dessus (attention, il ne sera plus possible de faire le transfert après cet
horaire)

NB : Les parties II et III du problème 2 sont facultatives, ainsi que les questions IV-7,8,9.

Exercice 1 – (Bases de voisinages)

Soit K “ R ou C, a P K et Wa Ă Vpaq. On dit que Wa est une base de voisinages de a si pour tout V P Vpaq, il existe
W P Wa tel que W Ă V .
On appelle base globale de voisinages une partie W de PpKq telle que pour tout a P E, l’ensemble Wpaq “ W X Vpaq
soit une base de voisinages de a.
1. Montrer que si Wa est une base de voisinages de a, et pun q P KN , alors pun q admet une limite a si et seulement
si :
@W P Wa , DN P N, @n ě N, un P W.
Soit U P PpKq. On dit que U est un ouvert si U est un voisinage de tous ses points.
2. (a) Justifier que les intervalles ouverts de R sont des ouverts de R, et que les boules ouvertes de C sont des
ouverts de C.
(b) Donner un ouvert de R qui n’est pas un intervalle.
3. Montrer que si W est une base globale de voisinages,
ď alors tout ouvert U est une union d’éléments de W.
Autrement dit, il existe Y Ă W, tel que U “ V.
V PY
4. Montrer que les intervalles ouverts sa, br tels que pa, bq P Q2 et a ă b forment une base globale de voisinages de
R. En déduire que R possède une base globale de voisinages dénombrable.
5. Décrire de la même manière une base globale de voisinages de C formée de boules ouvertes, et dénombrable.
6. Soit U une partie de K non vide. Montrer l’équivalence entre les 2 propriétés suivantes :
‚ U est ouvert ;
‚ U est une union au plus dénombrable de boules ouvertes.
On rappelle que par union dénombrable, on entend une union prise sur un ensemble d’indices au plus dénom-
brable.

Exercice 2 – (Nombre de discontinuités d’une fonction réglée)

Soit f : R Ñ R. On dit que f est réglée si elle admet une limite à droite et à gauche en tout point x de R.
Pour x P R, on note

δpxq “ maxpf pxq, lim f pyq, lim f pyqq ´ minpf pxq, lim f pyq, lim f pyqq.
yÑx´ yÑx` yÑx´ yÑx`

On pose, pour tout ε ą 0,

Aε “ tx P R, δpxq ě εu.
1. Soit ε ą 0.
(a) Soit x P Aε . Montrer qu’il existe η ą 0 tel que pour tout py, zq Psx ´ η, xr2 Ysx, x ` ηr2 , |f pyq ´ f pzq| ď 2ε .
(b) En déduire que Bpx, ηq X Aε “ txu.
2. Soit a ă b deux réels. On suppose que Aε X ra, bs est infini.
(a) À l’aide d’un théorème sur les suites réelles bornées, montrer qu’il existe une suite convergente pxn q P AN
ε
telle que les xn soient 2 à 2 distincts. On note c sa limite.
(b) Justifier à l’aide d’une question précédente que c R Aε .
(c) Justifier l’existence de η ą 0 et de ε1 Ps0, εr tels que pour tout py, zq P Bpc, ηq,

|f pyq ´ f pzq| ď ε1 .

1
 (d) En déduire une contradiction en considérant la suite pxn q.
Qu’en déduit-on pour l’ensemble Aε X ra, bs ?
3. Déduire de la question précédente que Aε est au plus dénombrable.
4. En considérant une suite strictement décroissante εn Ñ 0, en déduire que l’ensemble des points de discontinuité
de f est au plus dénombrable.

Problème 1 – (Formule du crible de Poincaré)

Dans ce petit problème, nous nous intéressons à une généralisation de la formule du cardinal d’une union de 2 ensembles.
Le but est de démontrer que pour n P N˚ , si A1 , . . . An sont des parties d’un ensemble E de cardinal fini, alors
ˇ ˇ ˇ ˇ
ˇďn ˇ ÿ ˇč ˇ
|I|`1 ˇ
ˇ Ai ˇ “ ˇ Ai ˇ . (1)
ˇ ˇ ˇ
p´1q
ˇi“1 ˇ ˇiPI ˇ
IPPpv1,nwqzt∅u

Partie I – Première démonstration de la formule du crible

On propose une première démonstration, par récurrence sur n. On fixe un ensemble fini E.
1. Justifier que la formule (1) valide lorsque n “ 1 et n “ 2.
2. Soit n ě 2. On suppose que la formule (1) est valide pour tout n-uplets pA1 , . . . , An q de parties de E. On se
donne pA1 , . . . , An`1 q un n ` 1-uplet de parties de E.
(a) Montrer que
ˇ ˇ ˇ ˇ ˇ ˇ
ˇn`1 ˇ ˇč ˇ ˇ č ˇˇ
ˇď ˇ ÿ ÿ
Ai ˇ “ |An`1 | ` p´1q|I|`1 ˇ Ai ˇ ´ p´1q|I|`1 ˇAn`1 X Ai ˇ .
ˇ ˇ ˇ
ˇ
ˇ i“1 ˇ ˇiPI ˇ ˇ iPI
ˇ
IPPpv1,nwqzt∅u IPPpv1,nwqzt∅u

(b) Comparer ˇ ˇ ˇ ˇ
ÿ ˇ č ˇˇ ÿ ˇč ˇ
p´1q|I|`1 ˇAn`1 X Ai ˇ et p´1q|I| ˇ Ai ˇ .
ˇ ˇ ˇ
cIPPpv1,n`1wq
ˇ iPI
ˇ ˇiPI ˇ
IPPpv1,nwqzt∅u
c n`1PI
(c) Terminer la preuve de la formule (1).

Partie II – Deuxième démonstration de la formule du crible

Cette démonstration s’appuie sur des dénombrements et l’utilisation de fonctions indicatrices.
Soit E un ensemble fini, et pA1 , . . . , An q P PpEqn . Pour x P E, on note

Ipxq “ ti P v1, nw | x P Ai u.

Ainsi, Ipxq est un entier compris entre 0 et n.

1. Soit x P E, et ℓ P v0, nw. Montrer que
ˆ ˙
ÿ Ipxq
1Ş Ai pxq “ .
iPI ℓ
IPPℓ pv1,nwq

ˆ ˙
Ipxq
On rappelle que, par convention, si ℓ ą Ipxq, “ 0.
ℓ
2. Justifier que
n ˆ ˙
ÿ Ipxq
p´1qℓ “1´1Ť
n pxq.
ℓ“0
ℓ Ai
i“1

3. En déduire la formule (1).

Partie III – Application de la formule du crible au dénombrement des surjections

Soit E et F deux ensembles de cardinaux respectifs n et m. On note SpE, F q l’ensemble des applications surjectives
de E dans F .
Pour b P F , on note Fb “ tf P F E , b R Impf qu.

2
 ˇ ˇ
ˇč ˇ
1. Soit k P v1, mw, et B P Pk pF q. Montrer que ˇ Fb ˇ “ pm ´ kqn .
ˇ ˇ
ˇ ˇ
bPB
2. En déduire que
m ˆ ˙
ÿ
m´k m n
|SpE, F q| “ p´1q k .
k“0
k

Problème 2 – Théorème de Cantor-Bernstein

Dans ce problème, nous proposons plusieurs preuves du théorème de Cantor-Bernstein. Ce théorème affirme qu’étant
donnés deux ensembles E et F , s’il existe une injection f : E Ñ F et une injection g : F Ñ E, alors il existe une
bijection de E dans F .
Nous nous donnons, dans tout le problème, deux ensembles E et F , et deux injections f : E Ñ F et g : F Ñ E.

Dans ce problème, on désigne par AE A le complémentaire dans E d’un sous-ensemble A de E (et de même pour la
complémentation dans F ).

Question préliminaire
Soit E et F deux ensembles, et tE1 , E2 u une partition de E et tF1 , F2 u une partition de F . Ainsi, E “ E1 Z E2 et
F “ F1 Z F2 . On suppose qu’il existe deux bijections f1 : E1 Ñ F1 et f2 : E2 Ñ F2 . À l’aide de f1 et f2 , construire
une bijection f : E Ñ F (on ne se contentera pas de décrire la construction, on s’appliquera également à prouver que
la fonction f est bien bijective).

Partie I – Une première démonstration

1. Dans cette question, nous montrons un lemme préliminaire, cas particulier du lemme du point fixe de Knaster-
Tarski. Soit φ : PpEq Ñ PpEq une application croissante définie sur les parties de E. La croissance de φ s’entend
au sens de l’inclusion ; ainsi, pour tous sous-ensembles A et B de E, si A Ă B, alors φpAq Ă φpBq. On pose S
le sous-ensemble de PpEq défini par :

S “ tA P PpEq | φpAq Ă Au,

et on définit M par : č
M“ A.
APS

(a) Justifier que S est non vide.

(b) Montrer que φpM q Ă M
(c) Montrer que φpM q P S et en déduire que M Ă φpM q.
Ainsi, toute φ : PpEq Ñ PpEq croissante admet un point fixe M P PpEq, c’est-à-dire vérifiant φpM q “ M .
2. On définit φ : PpEq Ñ PpEq par :
φpAq “ AE pg pAF f pAqqq ,
c’est-à-dire le complémentaire de l’image directe par g du complémentaire de l’image directe par f de l’en-
semble A.
Montrer que φ admet un point fixe M P PpEq, qu’on se donne pour la suite de cette partie.
3. Montrer que f définit par restriction et corestriction une application f1 : M Ñ f pM q, et que f1 est bijective.
4. Soit N “ AF f pM q.
(a) Décrire gpN q.
(b) Montrer que g définit par restriction et corestriction une application g1 : N Ñ AE M , et que g1 est une
bijection.
5. Construire à l’aide de f1 et g1 une bijection h : E Ñ F .

Partie II – Une deuxième démonstration

3
 1. Dans cette question, on montre le lemme suivant : si B est un sous-ensemble de E, et s’il existe une application
injective u : E Ñ B, alors il existe une bijection v : E Ñ B. Soit donc B un sous-ensemble de E et u : E Ñ B
une application injective. On pose C0 “ AE B, et on définit une suite pCn qnPN de sous-ensembles de E par
Cn`1 “ upCn q, pour tout n P N, et on définit :
`8
ď `8
ď
C“ Cn et C1 “ Cn .
n“0 n“1

Soit enfin D “ AE C.
(a) Montrer que D Ă B,
(b) Montrer que tD, Cu est un recouvrement disjoint de E (i.e. une partition à parts éventuellement vides), et
tD, C 1 u est un recouvrement disjoint de B.
(c) Montrer que upCq “ C 1 .
(d) En déduire, à l’aide de la question préliminaire, l’existence d’une bijection v de E dans B.
2. En considérant u “ g ˝ f dans le problème de Cantor-Bernstein, montrer l’existence d’une bijection de E sur F .

Partie III – Une troisième démonstration

Soit x un élément de E. On définit une suite (éventuellement finie) associée à x par récurrence de la manière suivante :
on pose u0 pxq “ x, et pour tout n P N, si un pxq est défini, on pose un`1 pxq l’unique antécédent (s’il existe) de un pxq
par f ou g (selon que un pxq est dans E ou F ). Si cet antécédent n’existe pas, ou si un pxq n’est pas défini, alors un`1 pxq
n’est pas défini.
Ainsi, la suite est définie en commençant par prendre un antécédent par f , puis par g, puis par f , et à nouveau par
g, etc., tant que c’est possible. Trois cas peuvent se produire :
‚ La suite pun pxqq est finie et s’arrête dans E (donc le dernier terme défini est dans E). On définit l’ensemble EE
comme étant l’ensemble des x de E pour lesquels cette situation se produit.
‚ La suite pun pxqq est finie et s’arrête dans F (donc le dernier terme défini est dans F ). On définit l’ensemble EF
comme étant l’ensemble des x de E pour lesquels cette situation se produit.
‚ La suite pun pxqq est infinie. On définit l’ensemble E8 comme étant l’ensemble des x de E pour lesquels cette
situation se produit.
1. Justifier que tEE , EF , E8 u est un recouvrement disjoint de E
2. En définissant de la même manière FE , FF et F8 en partant des points de F , montrer que f définit par
restriction une bijection de EE dans FE , et que g définit par restriction une bijection de FF dans EF .
3. Montrer que f définit une bijection de E8 dans F8 et conclure.

Partie IV – Quelques applications classiques

On dit que deux ensembles E et F ont même cardinal si et seulement s’il existe une bijection de E dans F . On montre
par des exemples l’intérêt du théorème de Cantor-Berstein dans la théorie des cardinaux. Attention, tous les exemples
donnés ci-dessous n’utilisent pas nécessairement ce théorème. Les trois dernières questions sont indépendantes des
précédentes.
1. Montrer que PpNq et t0, 1uN ont même cardinal (on pourra construire explicitement une bijection en associant
à un sous-ensemble de N une certaine application ; on vérifiera scrupuleusement qu’il s’agit bien d’une bijection)
2. Montrer que t0, 1uN et NN ont même cardinal (on pourra construire explicitement une bijection en construisant
pour une fonction f à valeurs dans N, une fonction à valeurs dans t0, 1u, la valeur des f piq déterminant la
position des 1 dans la suite des images).
N
3. Montrer que PpNq et v0, 9w ont même cardinal.
N
4. Montrer que v0, 9w et r0, 1r ont même cardinal (on pourra utiliser le développement en base 10, en admettant
l’unicité d’un développement propre, c’est-à-dire ne terminant pas par une infinité de 9)
5. Montrer que r0, 1r et R ont même cardinal.
6. Montrer que PpNq et R ont même cardinal.
7. Montrer que R2 et R ont même cardinal (on pourra mélanger les développements décimaux de deux réels)
8. Montrer que PpRq et RR ont même cardinal.
9. Trouver une deuxième preuve du résultat de la question précédente.