DM 03

Lycée Louis-Le-Grand, Paris Pour le 03/10/2023
MP2I – Mathématiques
A. Troesch
DM no 3 : Applications, relations
Suggestion de travail supplémentaire (à ne pas me rendre) : Si vous en avez le temps, vous pouvez regarder
le problème 2 de la sélection disponible sur mon site web (équivalence entre axiome du choix et lemme de Zorn)
Problème 1 – 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 \ E2 et
F “ F1 \ 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
1
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 partage de E (i.e. une partition à parts éventuellement vides), et tD, C 1 u est un
partage 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 partage de E (i.e. une partition à parts éventuellement vides).
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 se servir d’un exemple vu en cours d’une application
mélangeant les développements 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.
2
Problème 2 – Saturation d’un sous-ensemble pour une relation d’équivalence
Soit „ une relation d’équivalence sur un ensemble E. On définit, pour tout sous-ensemble A de E :
As “ ty P E | Dx P A, x „ yu.
On dit que As est la saturation de A pour la relation „. On dit que l’ensemble A est saturé si A “ As . On note SpEq
l’ensemble des parties saturées de E.
Par ailleurs, on note, pour toute partie A de E, Ac le complémentaire de A dans E. Enfin, pour tout x P A, on note
x sa classe d’équivalence, c’est-à-dire le sous-ensemble de E constitué des éléments y tels que y „ x.
1. (a) Montrer que pour tout A P PpEq, A Ă As .
(b) Déterminer ∅s et E s .
(c) Montrer que pour tout A P PpEq, pAs qs “ As (on dit que l’application de saturation est « idempotente »)
2. Soit A P PpEq.
ď
(a) Montrer que As “ x.
xPA
č
(b) Montrer que As “ B
BPSpEq tq AĂB
3. Soient A et B dans PpEq.

(a) Montrer que pA Y Bqs “ As Y B s
(b) Montrer que des deux inclusions pA X Bqs Ă As X B s et As X B s Ă pA X Bqs , une seule est toujours vraie,
et donner un contre-exemple pour l’autre.
4. Établir une inclusion entre pAs qc et pAc qs . À quelle condition a-t-on l’égalité ?
5. Soient p1 et p2 définies de E ˆ E dans E par p1 px, yq “ x et p2 px, yq “ y. Montrer que pour tout A P PpEq,
As “ p2 pp´1
1 pAq X Gq,
où G Ă E ˆ E est le graphe de la relation „.

6. On définit sur PpEq la relation R par :
ARB ðñ p@x P A, Dy P B, x „ yq.
(a) Montrer que R est reflexive et transitive. La relation R est-elle en général une relation d’équivalence ?
(b) Montrer que ARB et BRA si et seulement si As “ B s . La relation R est-elle une relation d’ordre ?
(c) On définit la relation S sur PpEq par ASB si et seulement As “ B s . Montrer que S est une relation
d’équivalence.
(d) Montrer que S respecte la relation R, c’est-à-dire : pour tout pA, B, A1 , B 1 q tels que ASA1 et BSB 1 , si ARB
alors A1 RB 1 .
(e) En déduire l’existence d’une relation R sur PpEq{S telle que pour tout pA, Bq P PpEq2 ,
ARB ðñ A R B.
La barre désigne ici la classe d’équivalence dans PpEq pour la relation S.

(f) Montrer que R est une relation d’ordre sur PpEq{S

DM 03

Transféré par

Droits d'auteur :

Formats disponibles

DM 03

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

DM 03

Transféré par

Droits d'auteur :

Formats disponibles

Lycée Louis-Le-Grand, Paris Pour le 03/10/2023

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

Partie I – Une première démonstration

S “ tA P PpEq | ϕpAq Ă Au,

(a) Justifier que S est non vide.

Partie II – Une deuxième démonstration

Partie III – Une troisième démonstration

Partie IV – Quelques applications classiques

3. Soient A et B dans PpEq.

où G Ă E ˆ E est le graphe de la relation „.

ARB ðñ p@x P A, Dy P B, x „ yq.

La barre désigne ici la classe d’équivalence dans PpEq pour la relation S.

Vous aimerez peut-être aussi