Mesurer la taille des ensembles

Préliminaires

Exercice 1

1. Soit $X$ un ensemble, on définit une relation $ℛ$ sur $\wp \left(X\right)$ par :
   $AℛB$ ssi il existe une application bijective de $A$ sur $B$.
   Montrer que $ℛ$ est une relation d'équivalence.
2. On note $\le$ la relation sur $\raisebox{1ex}{$\wp \left(X\right)$}\!\left/ \!\raisebox{-1ex}{$ℛ$}\right.$ définie par :
   $X\le Y$ ssi il existe une application injective d'un élément de $X$ vers un élément de $Y$.
   Montrer que la définition de $\le$ est indépendante du choix des représentants de $X$ et $Y$.
3. Montrer que $\le$ est réflexive et transitive.

Exercice 2 (Théorème de Cantor-Bernstein)

Soit $A$ et $B$ deux ensembles et $f:A\to B$ et $g:B\to A$ des applications injectives. On pose $X_0=A\backslash g\left(B\right)$, pour tout $n$, $X_{n+1}=\left(g\circ f\right)\left(X_n\right)$, $X=\bigcup _{n\in \mathbb{N}}{X}_n$ et

$h:\mid \begin{array}{c}A\to A\backslash X_0\\ x\mapsto \{\begin{array}{c}(g\circ f)\left(x\right)\text{if}x\in X\\ x\text{sinon}\end{array}\end{array}$

1. Montrer que $g\left(B\right)=A\backslash X_0$ puis que cet ensemble est en bijection avec $B$.
2. Montrer que deux éléments respectivement dans $X$ et $A\backslash X$ ne peuvent avoir la même image.
3. Montrer que $h$ est injective.
4. Montrer que $h$ est bijective.
5. Montrer qu'il existe une bijection de $A$ dans $B$.
6. Montrer que la relation $\le$ définie dans le premier exercice est une relation d'ordre.

Quelques remarques

Les relations définies précédemment permettent de mesurer "la taille" des sous-ensembles de $X$. Ainsi les éléments d'une même classe d'équivalence ont "la même taille", que l'on note $\mid A\mid$ (pour un élément $A$), et que l'on appelle cardinalité de $A$. On n'est pas obligé de se restreindre à un $\wp \left(X\right)$, mais la définition générale nécessite d'autres outils qui ne sont pas abordées en classe préparatoire. On se contentera donc de définir la cardinalité de $A$ comme sa classe d'équivalence.

La relation d'ordre permet de dire si un ensemble est "plus grand" qu'un autre. Notons que pour l'instant on ne sait pas grand chose sur cette relation d'ordre pour les ensembles infinis. Par exemple il est possible d'obtenir une suite d'ensembles finis avec une taille strictement croissantes mais par contre il se pourrait que les ensembles infinis aient tous la même taille. De même l'ordre $\le$ est totale pour les ensembles finis, mais on ne peut a priori rien dire pour les ensembles infinis. L'exercice 3 donne une réponse au premier problème, mais le second nécessite l'axiome du choix qui ne fait pas partie du programme des classes préparatoires (*). Par conséquent, on admettra que la relation d'ordre $\le$ est totale. De même, on supposera que tout ensemble infini A possède une partie dénombrable (i.e en bijection avec $\mathbb{N}$) et donc $\mid A\mid \ge \mid \mathbb{N}\mid$.

Exercice 3 (Théorème de Cantor)

Soit $A$ un ensemble. Pour toute application $f:A\to \wp \left(A\right)$ on pose $A_f=\left\{x\in A|x\notin f\left(x\right)\right\}$.

1. Montrer qu'il existe une injection de $A$ dans $\wp \left(A\right)$
2. Montrer que pour toute application $f:A\to \wp \left(A\right)$, $A_f$ n'a pas d'antécédent.
3. En déduire que si $A,\wp \left(A\right)\in \wp \left(X\right)$ on a $\mid A\mid <\mid \wp \left(A\right)\mid$.

Classification des cardinalités de $\wp \left(ℝ\cup \wp \left(ℝ\right)\right)$

Par la suite, on s'intéressera à $X=ℝ\cup \wp \left(ℝ\right)$, et on note $S=\raisebox{1ex}{$\wp \left(X\right)$}\!\left/ \!\raisebox{-1ex}{$ℛ$}\right.$.

Exercice 4

1. Montrer que $S$ possède un plus petit et plus grand élément.
2. Montrer que $\left\{X\in S|X<\mid \mathbb{N}\mid \right\}$ (l'ensemble des classes d'ensembles finis) est au moins dénombrables.
3. En utilisant le théorème de Cantor, montrer que si $\mid \wp \left(\mathbb{N}\right)\mid \le \mid ℝ\mid$ (on montrera plus loin qu'il y a égalité), alors $\left\{X\in S|X\ge \mid \mathbb{N}\mid \right\}$ (l'ensemble des classes d'ensemble infinis) possède au moins 3 éléments.

Exercice 5 ($\mathbb{Z},\mathbb{Q}$)

1. Construire une bijection entre $\mathbb{N}$ et $\mathbb{Z}$.
2. Montrer que $\mathbb{Q}$ s'injecte dans $\mathbb{Z}\times \mathbb{N}$ puis dans $\mathbb{N}\times \mathbb{N}$
3. Montrer que $f:\mid \begin{array}{c}\mathbb{N}\times \mathbb{N}\to \mathbb{N}\\ \left(p,q\right)\mapsto 2^p(2q+1)\end{array}$ est injective.
4. Conclure que $\mathbb{N},\mathbb{Z},\mathbb{Q}$ ont la même cardinalité.

Exercice 6 ($ℝ$)

1. Soit $A,B$ deux ensembles en bijection, construire une bijection entre $\wp \left(A\right)$ et $\wp \left(B\right)$.
2. Soit $A$ un ensemble, montrer que $\wp \left(A\right)$ est en bijection avec ${\{0;1\}}^A$.
3. Montrer que l'application $f:\mid \begin{array}{c}ℝ\to \wp \left(\mathbb{Q}\right)\\ r\mapsto \left\{q\in \mathbb{Q}|q<r\right\}\end{array}$ est injective.
4. Montrer que pour toute suite ${\left(a_n\right)}_{n\in \mathbb{N}}$ d'éléments de $\{0;1\}$, la série $\sum _{n\ge 1}\frac{2a_n}{3^n}$ converge.
5. Montrer que $g:\mid \begin{array}{c}{\{0;1\}}^{\mathbb{N}}\to ℝ\\ {\left(a_n\right)}_{n\in \mathbb{N}}\mapsto \sum _{n=1}^{\infty }\frac{2a_n}{3^n}\end{array}$ est injective.
6. Montrer finalement que $\mid \wp \left(\mathbb{N}\right)\mid =\mid ℝ\mid$.

Exercice 7

1. Déduire de l'exercice précédent que $\mid \wp \left(\wp \left(\mathbb{N}\right)\right)\mid =\mid \wp \left(ℝ\right)\mid$
2. Que dire de $\wp \left(\wp \left(\mathbb{N}\right)\right)$ et $\wp \left(\wp \left({\mathbb{N}}^{*}\right)\right)$ ?
3. Montrer que $\mid X\mid =\mid \wp \left(\mathbb{N}\right)\cup \wp \left(\wp \left({\mathbb{N}}^{*}\right)\right)\mid$.
4. On définit maintenant l'application $f:\wp \left(\mathbb{N}\right)\cup \wp \left(\wp \left({\mathbb{N}}^{*}\right)\right)\to \wp \left(\wp \left(\mathbb{N}\right)\right)$ par :
   • Si $X\in \wp \left(\mathbb{N}\right)$, $f\left(X\right)=\left\{\left\{0\right\},\left\{x+1|x\in X\right\}\right\}$
   • Si $X\in \wp \left(\wp \left({\mathbb{N}}^{*}\right)\right),f\left(X\right)=X$

   Vérifier que $f$ est bien définie et est injective.

5. En déduire que $\mid \wp \left(\wp \left(\mathbb{N}\right)\right)\mid =\mid \wp \left(ℝ\right)\mid =\mid X\mid$.

Quelques remarques

Cette partie peut finalement se résumer par le diagramme suivant, représentant l'ensemble E des cardinalités :

0 1 2 3 ... $\mid \mathbb{N}\mid =\mid \mathbb{Z}\mid =\mid \mathbb{Q}\mid$ ∣ℕ∣ = ∣ℤ| = ∣ℚ∣ $\mid ℝ\mid =\mid \wp \left(\mathbb{N}\right)\mid$ |ℝ∣ = ∣℘(ℕ)∣ $\mid X\mid =\mid \wp \left(\wp \left(\mathbb{N}\right)\right)\mid =\mid \wp \left(ℝ\right)\mid$ ∣X∣ = ∣℘(℘(ℕ))∣=|℘(ℝ)|

Les plus petits éléments sont les cardinalités des ensembles finis, que l'on note usuellement 0, 1, 2... Vient ensuite les cardinalités des ensembles infinis ($\mid \mathbb{N}\mid$, $\mid \wp \left(\mathbb{N}\right)\mid$ et $\mid \wp \left(\wp \left(\mathbb{N}\right)\right)\mid$). Il est en fait possible de prolonger cette échelle par application successive de l'ensemble des parties à $\mathbb{N}$ et le passage à la borne supérieure (à l'instar du passage du fini/infini).

On peut toutefois se demander si entre deux barres successives, il n'y a pas de cardinalités intermédiaires, comme c'est le cas pour les ensembles finis. La cardinalité de $ℝ$ est appelée le continu (en référence à la droite continue) et "l'hypothèse du continu" est ainsi qu'il n'y a pas de cardinalité entre le dénombrable et le continu. "L'hypothèse du continu généralisée" exprime cette supposition pour tous les cardinaux infinis. On peut montrer par l'axiome du choix que (comme dit plus haut) le dénombrable est la plus petite cardinalité infinie. Par contre même en l'utilisant, les hypothèses du continu demeurent indécidables (on ne peut ni les prouver ni prouver leurs négations).

Dans la suite, on va placer sur l'échelle d'autres sous-ensembles infinis de $X$. Par la remarque précédente, elles ne pourront être que parmi les 3 trouvées.

Cardinalité de sous-ensembles de $ℝ$

Exercice 8 (intervalles de $ℝ$)

1. Montrer qu'il existe un intervalle ouvert borné en bijection avec $ℝ$.
2. En déduire que tout intervalle ouvert borné a la cardinalité du continu.
3. Généraliser le résultat précédent à tout intervalle, en utilisant Cantor-Bernstein.

Exercice 9 (ouverts et fermés)

1. Montrer que tout ouvert non vide a le cardinalité du continu.
2. Montrer qu'il existe des sous-ensemble fermé de toutes cardinalités finies, dénombrables et continue.

Remarque : le théorème de Cantor-Bendixson affirme que tout fermé indénombrable a la cardinalité du continu, mais sa preuve utilise des outils non enseignés en classe préparatoire.

Exercice 10 (ensemble des nombres algébriques)

Un nombre réel est dit algébrique si et seulement si il est racine d'un polynôme non nul à coefficients rationnels. Il est dit transcendant dans le Ůcas contraire. On note $A$ l'ensemble des nombres algébriques. Un polynôme non nul à coefficients rationnels de degré $n$ est assimilé au (n+1)-uplet de ses coefficients de plus bas degré.

1. Montrer que $A$ est au moins dénombrable.
2. Montrer qu'il existe un bon ordre sur $\mathbb{Q}$, i.e. tel que toute partie non vide possède un plus petit élément (utiliser l'exercice 5).
3. En déduire un bon ordre sur$\bigcup _{n\ge 1}{\mathbb{Q}}^{n+1}$ (utiliser l'ordre lexicographique)
4. Construire une application de $f:A\mapsto \bigcup _{n\ge 1}{\mathbb{Q}}^{n+1}$ telle que tout $r\in A$ est racine de $f\left(r\right)$.
5. En utilisant le théorème fondamental de l'algèbre et l'application $f$ précédente, construire une application injective $g:A\to \bigcup _{n\ge 1}{\mathbb{Q}}^{n+1}\times [1;n]$.
6. Montrer que pour tout $n\ge 1$, ${\mathbb{Q}}^{n+1}\times [1;n]$ s'injecte dans $\mathbb{N}\times \left\{n\right\}$.
7. Montrer que $\bigcup _{n\ge 1}\mathbb{N}\times \left\{n\right\}$ s'injecte dans $\mathbb{N}$
8. Conclure que $A$ est dénombrable.

Exercice 11 (ensemble des nombres transcendants)

1. Soit $E$ un ensemble et $f:F\to G$ une bijection entre deux sous-ensembles de $E$. On pose :

   $g:\mid \begin{array}{c}E\backslash F\to E\backslash G\\ x\mapsto \{\begin{array}{c}x\mathrm{si}x\notin G\\ f^{-1}\left(x\right)\sin \mathrm{on}\end{array}\end{array}$
   Montrer que $g$ est une bijection.

2. Montrer que $ℝ\backslash \mathbb{N}$ a la cardinalité du continu (utiliser les résultats de l'exercice 8).
3. Déduire des questions précédentes et de l'exercice 10 que l'ensemble des nombres transcendants a la cardinalité du continu.

Cardinalité de sous-ensembles de $\wp \left(ℝ\right)$

Exercice 12 (ensembles des ouverts/fermés/compacts)

1. Montrer que l'ensemble des ouverts, l'ensemble des fermés et l'ensemble des compacts de $ℝ$ ont au moins la cardinalité du continu.
2. Construire une bijection entre l'ensemble des ouverts et l'ensemble des fermés.
3. Soit $O$ l'ensemble des ouverts de $ℝ$. ${\mathbb{Q}}^2$ étant dénombrable, on considère une énumération ${\mathbb{Q}}^2=\left\{\left(a_n,b_n\right)|n\in \mathbb{N}\right\}$, et on définit la fonction :

   $f:\mid \begin{array}{c}O\to {\left({\mathbb{Q}}^2\right)}^{\mathbb{N}}\\ o\mapsto \left(n\mapsto \left({f\left(o\right)}_{n,1},{f\left(o\right)}_{n,2}\right)=\{\begin{array}{c}\left(a_n,b_n\right)\text{si}]a_n,b_n[\subseteq o\\ \left(0,0\right)\text{sinon}\end{array}\right)\end{array}$
   Montrer que pour tout $o\in O$, $o=\bigcup _{n\in \mathbb{N}}]{f\left(o\right)}_{n,1},{f\left(o\right)}_{n,2}[$.

4. En déduire que $f$ est injective.
5. Soient $E,F,G$ trois ensembles tel que $F$ s'injecte dans $G$. Montrer que $F^E$ s'injecte dans $G^E$.
6. On reprend les ensembles de la question précédente et on suppose de plus que F est non vide. Montrer que $E^F$s'injecte dans $E^G$.
7. Soient $E,F,G$ trois ensembles. Montrer que ${\left(E^F\right)}^G$ et $E^{F\times G}$ sont en bijection.
8. Montrer que $O$ s'injecte dans ${\mathbb{N}}^{\mathbb{N}}$
9. Montrer que $\mathbb{N}$ s'injecte dans ${\{0;1\}}^{\mathbb{N}}$ puis que ${\mathbb{N}}^{\mathbb{N}}$ s'injecte dans ${\{0;1\}}^{\mathbb{N}}$.
10. En déduire que l'ensemble des ouverts, l'ensemble des fermés et l'ensemble des compacts de $ℝ$ ont la cardinalité du continu.

Autres ensembles

Exercice 13 ($ℂ$)

1. Montrer que $\wp \left(\mathbb{N}\right)$ s'injecte dans $\wp \left(\mathbb{N}\right)\times \wp \left(\mathbb{N}\right)$.
2. Que dire de $\wp \left(\mathbb{N}\right)\times \wp \left(\mathbb{N}\right)$ et $\wp \left(\mathbb{N}\times \mathbb{N}\right)$ ?
3. En déduire que $\mid ℝ\times ℝ\mid =\mid ℝ\mid$.
4. Quelle est la cardinalité de $ℂ$ ?

Exercice 14 (${ℝ}^{ℝ}$)

On a montré dans l'exercice 12 que la cardinalité de ${\mathbb{N}}^{\mathbb{N}}$ était $\mid \wp \left(\mathbb{N}\right)\mid$. Regardons ce qu'il en est de ${ℝ}^{ℝ}$...

1. Montrer que ${\{0;1\}}^{{\{0;1\}}^{\mathbb{N}}}$ s'injecte dans ${ℝ}^{ℝ}$.
2. Montrer que ${ℝ}^{ℝ}$ est en bijection avec${\{0;1\}}^{\mathbb{N}\times {\{0;1\}}^{\mathbb{N}}}$.
3. Soit A et B deux ensembles dénombrables disjoints. Montrer que $A\cup B$ est dénombrable et que${\{0;1\}}^A\times {\{0;1\}}^B$ a pour cardinalité ${\{0;1\}}^{\mathbb{N}}$.
4. Quelle est alors la cardinalité de ${\{0;1\}}^{\mathbb{N}}\times {\{0;1\}}^{\mathbb{N}}$ ?
5. En déduire que ${\{0;1\}}^{\mathbb{N}\times {\{0;1\}}^{\mathbb{N}}}$ s'injecte dans ${\{0;1\}}^{{\{0;1\}}^{\mathbb{N}}}$.
6. Conclure que la cardinalité de ${ℝ}^{ℝ}$ est $\mid \wp \left(\wp \left(\mathbb{N}\right)\right)\mid$.

Exercice 15 (fonctions continues)

1. Montrer que l'ensemble des fonctions continues de $ℝ$ dans $ℝ$ a au moins la cardinalité du continu. En donner un majorant à l'aide de l'exercice 14.
2. Montrer que l'application

   $a:\mid \begin{array}{c}C\left(ℝ,ℝ\right)\to {ℝ}^{\mathbb{Q}}\\ f\mapsto f_{\mid \mathbb{Q}}\end{array}$
   est injective. (utiliser la densité de $\mathbb{Q}$)

3. En déduire que $C\left(ℝ,ℝ\right)$ a la cardinalité du continu.

Références

L'exercice 2 reprend la démonstration du théorème de Cantor-Bernstein telle qu'elle est exposée dans les notes de cours FIMFA ENS de Patrick Dehornoy « Logique et théorie des ensembles ». Le théorème de l'exercice 3 est du à Cantor qui a aussi montré les résultats de l'exercice 5 (dénombrabilité de $\mathbb{N},\mathbb{Z},\mathbb{Q}$) et de l'exercice 13 (cardinalité de $ℝ\times ℝ$). Les exercices 6, 12 et 15 s'inspirent du chapitre 4 du livre de Thomas Jech Set Theory, The Third Millennium Edition, Revised and Expanded. Les résultats de l'exercice 10 et 11 sur la cardinalité des nombres algébriques et transcendants ont été prouvés par Dedekind et Cantor.

---

(*) Toutefois, ceux qui connaissent un peu la théorie des ensembles peuvent essayer de montrer que :

• Si l'axiome du choix est vrai, alors la relation est totale (bien ordonner les ensembles et passer par les ordinaux pour obtenir une injection de l'un dans l'autre).
• Si la relation est totale, alors l'axiome du choix est vrai (pour bien ordonner un ensemble $X$, prendre le plus petit ordinal $\alpha$ ne s'injectant pas dans $X$ (montrer qu'il en existe un...) et ainsi obtenir une injection de $X$ dans $\alpha$)

• • Accueil
  • Actualité
  • A propos
  • Infos Logo
  • Infos techniques
  • Proposer article
  • Plan du site
  • Ouvrages
  • Mailing List
  • Imprimer
• • Algèbre
  • Analyse
  • Ensembles
  • Geometrie
  • Graphes
  • Logique
  • Probabilités
  • Recherche Opérationnelle
  • Statistiques

Cette page respecte les recommandations du W3C. Son contenu est sous licence Creative Commons.