Éducation Nationale Française · PSI

Dénombrabilité

⌚ ~51 min ▢ 6 blocs ✓ 28 exercices ➣ Prérequis : Applications, Dénombrement

Conventions

Tout au long de ce chapitre, nous adoptons les conventions et la notation rappelée suivantes.

Entiers. $\mathbb{N} = \{0, 1, 2, \dots\}$ et $\mathbb{N}^* = \mathbb{N} \setminus \{0\}$. Pour $a \le b$ dans $\mathbb{Z}$, l'intervalle d'entiers est $\llbracket a, b \rrbracket = \{a, a+1, \dots, b\}$ (rappelé de Dénombrement).
Applications. Injection, surjection, bijection, l'application réciproque $f^{-1}$ d'une bijection et la composition $g \circ f$ sont utilisées telles qu'établies dans Applications. Une composée de bijections est une bijection.
Permutations. Pour un ensemble $E$, $\mathfrak{S}(E)$ désigne l'ensemble des permutations de $E$, c'est-à-dire les bijections $E \to E$. Lorsque $E = \{1, \dots, n\}$, c'est le groupe symétrique $\mathfrak{S}_n$ de Groupe symétrique.
« Au plus dénombrable ». C'est une seule expression, définie plus bas ; c'est l'objet récurrent du chapitre, plus utile que « dénombrable » seul.

I Les ensembles dénombrables

Pour un ensemble fini, le cardinal est un entier qui dit « combien ». Pour un ensemble infini, un tel entier n'existe pas — mais on peut tout de même comparer. L'ensemble infini de référence est $\mathbb{N}$ lui-même, et un ensemble est déclaré dénombrable lorsque ses éléments peuvent être mis en correspondance un à un avec les entiers, c'est-à-dire énumérés en une suite $x_0, x_1, x_2, \dots$ qui liste chaque élément exactement une fois. Cette section fixe cette définition, démontre le premier fait non trivial — toute partie infinie de $\mathbb{N}$ est dénombrable — et introduit les ensembles « au plus dénombrables », véritable objet du reste du chapitre.

Signaler une erreur

Définition — Ensemble dénombrable

Un ensemble $E$ est dit dénombrable s'il existe une bijection $\mathbb{N} \to E$. De façon équivalente, $E$ est dénombrable lorsque ses éléments peuvent s'écrire comme une suite $E = \{x_n \mid n \in \mathbb{N}\}$ où $n \mapsto x_n$ est injective : chaque élément de $E$ apparaît exactement une fois. Une telle suite est appelée une énumération de $E$.

Exemple — L'ensemble $\mathbb{N}^*$

L'application $\mathbb{N} \to \mathbb{N}^*$, $n \mapsto n + 1$, est une bijection : elle est injective, et tout entier strictement positif $m$ est l'image de $m - 1$. Donc $\mathbb{N}^*$ est dénombrable. On remarque que $\mathbb{N}^*$ est une partie stricte de $\mathbb{N}$, et possède pourtant « autant » d'éléments — phénomène impossible pour les ensembles finis, et caractéristique des ensembles infinis.

Exemple — Les entiers naturels pairs

Soit $2\mathbb{N} = \{0, 2, 4, 6, \dots\}$ l'ensemble des entiers naturels pairs. L'application $\mathbb{N} \to 2\mathbb{N}$, $n \mapsto 2n$, est une bijection, donc $2\mathbb{N}$ est dénombrable. L'énumération est $x_n = 2n$. Là encore, une partie stricte de $\mathbb{N}$, d'apparence « plus mince », se révèle dénombrable.

Proposition — Parties infinies de $\mathbb{N}$

Toute partie infinie de $\mathbb{N}$ est dénombrable.

Preuve

Soit $A \subseteq \mathbb{N}$ infinie. On construit une énumération de $A$ en listant ses éléments par ordre croissant. Toute partie non vide de $\mathbb{N}$ possède un plus petit élément (bon ordre de $\mathbb{N}$) ; on l'utilise à chaque étape.

Construction. On définit une suite $(a_n)_{n \in \mathbb{N}}$ par récurrence : $a_0 = \min A$ et $a_{n+1} = \min\{x \in A \mid x > a_n\}$. Chaque ensemble $\{x \in A \mid x > a_n\}$ est non vide : s'il était vide, $A$ serait contenu dans $\llbracket 0, a_n \rrbracket$, donc fini, contrairement à l'hypothèse. Ainsi chaque $a_n$ est bien défini et appartient à $A$.
Injectivité. Par construction $a_{n+1} > a_n$ pour tout $n$, donc $(a_n)$ est strictement croissante, et $n \mapsto a_n$ est injective. Une récurrence immédiate donne aussi $a_n \ge n$ pour tout $n$.
Surjectivité. Soit $x \in A$. Comme $a_n \ge n$, l'ensemble $\{n \in \mathbb{N} \mid a_n \le x\}$ est majoré par $x$ ; il est non vide, car $a_0 = \min A \le x$. Soit $n$ son plus grand élément, donc $a_n \le x$. Si $a_n < x$, alors $x$ appartient à $A$ et vérifie $x > a_n$, d'où $x \ge \min\{y \in A \mid y > a_n\} = a_{n+1}$ ; mais $n$ est le plus grand indice tel que $a_n \le x$, donc $a_{n+1} > x$ — contradiction. Par conséquent $a_n = x$, et $x$ est atteint.

Ainsi $n \mapsto a_n$ est une bijection $\mathbb{N} \to A$, et $A$ est dénombrable.

Exemple — $\mathbb{Z}$ est dénombrable

Montrer que $\mathbb{Z}$ est dénombrable.

Correction

On énumère les entiers en alternant le signe : $0, -1, 1, -2, 2, -3, 3, \dots$. Formellement, on définit $\varphi : \mathbb{N} \to \mathbb{Z}$ par $$ \varphi(n) = \begin{cases} \ \dfrac{n}{2} & \text{si } n \text{ est pair},\\ -\dfrac{n+1}{2} & \text{si } n \text{ est impair}. \end{cases} $$ Les indices pairs $0, 2, 4, \dots$ sont envoyés sur $0, 1, 2, \dots$ et les indices impairs $1, 3, 5, \dots$ sur $-1, -2, -3, \dots$, donc tout entier est atteint exactement une fois : $\varphi$ est une bijection. Donc $\mathbb{Z}$ est dénombrable.

Définition — Ensemble au plus dénombrable

Un ensemble $E$ est dit au plus dénombrable s'il est fini ou dénombrable. Intuitivement, $E$ est au plus dénombrable lorsque ses éléments peuvent être listés en une suite (finie ou infinie) — l'idée d'une telle liste est rendue précise par les caractérisations de la section suivante.

Compétences à pratiquer

Exhiber une bijection explicite
Énumérer une partie de $\mathbb{N}$

II Caractériser la dénombrabilité

Exhiber explicitement une bijection avec $\mathbb{N}$ est souvent malaisé. En pratique on ne le fait presque jamais directement : on construit plutôt une injection vers $\mathbb{N}$, ou une surjection depuis $\mathbb{N}$, et l'on laisse un critère général conclure. Cette section démontre trois de ces critères — par une partie de $\mathbb{N}$, par une injection, par une surjection — puis enregistre la stabilité de « au plus dénombrable » par parties et par images. Ensemble, ils forment la boîte à outils utilisée dans tous les raisonnements ultérieurs.

Signaler une erreur

Proposition — Au plus dénombrable par une partie de $\mathbb{N}$

Un ensemble $E$ est au plus dénombrable si et seulement s'il existe une bijection entre $E$ et une partie de $\mathbb{N}$.

Preuve

($\Rightarrow$) Supposons $E$ au plus dénombrable. Si $E$ est dénombrable, une bijection $\mathbb{N} \to E$ réalise déjà $E$ en bijection avec la partie $\mathbb{N}$ de $\mathbb{N}$. Si $E$ est fini et non vide, de cardinal $n \ge 1$, alors par la définition du cardinal de Dénombrement il existe une bijection $\llbracket 1, n \rrbracket \to E$, et $\llbracket 1, n \rrbracket \subseteq \mathbb{N}$ ; et l'ensemble vide est lui-même une partie de $\mathbb{N}$, en bijection avec lui-même.
($\Leftarrow$) Supposons qu'il existe une bijection $E \to A$ avec $A \subseteq \mathbb{N}$. Si $A$ est fini, alors $E$ est fini par équipotence (Dénombrement). Si $A$ est infini, alors $A$ est dénombrable par la proposition précédente, donc $E$, en bijection avec un ensemble dénombrable, est dénombrable. Dans les deux cas $E$ est au plus dénombrable.

Proposition — Au plus dénombrable par une injection

Un ensemble $E$ est au plus dénombrable si et seulement s'il existe une injection $E \to \mathbb{N}$.

Preuve

($\Rightarrow$) Si $E$ est au plus dénombrable, la proposition précédente fournit une bijection $f : E \to A$ avec $A \subseteq \mathbb{N}$. Composer $f$ avec l'inclusion $A \hookrightarrow \mathbb{N}$ donne une injection $E \to \mathbb{N}$.
($\Leftarrow$) Réciproquement, soit $f : E \to \mathbb{N}$ une injection. En restreignant l'ensemble d'arrivée à son image, $f$ devient une bijection $E \to f(E)$, et $f(E) \subseteq \mathbb{N}$. Par la proposition précédente, $E$ est au plus dénombrable.

Proposition — Au plus dénombrable par une surjection

Un ensemble non vide $A$ est au plus dénombrable si et seulement s'il existe une surjection $\mathbb{N} \to A$.

Preuve

($\Rightarrow$) Supposons $A$ non vide et au plus dénombrable. Si $A$ est dénombrable, toute bijection $\mathbb{N} \to A$ est en particulier une surjection. Si $A$ est fini, $|A| = n \ge 1$ et une bijection $g : \llbracket 1, n \rrbracket \to A$ existe ; on définit $f : \mathbb{N} \to A$ par $f(k) = g(k+1)$ pour $0 \le k \le n-1$ et $f(k) = g(1)$ pour $k \ge n$. Toute valeur $g(1), \dots, g(n)$ est atteinte, donc $f$ est une surjection.
($\Leftarrow$) Supposons qu'il existe une surjection $f : \mathbb{N} \to A$. Pour chaque $a \in A$ l'ensemble $f^{-1}(\{a\})$ est non vide (surjectivité), il possède donc un plus petit élément. On définit $g : A \to \mathbb{N}$ par $g(a) = \min f^{-1}(\{a\})$. Alors $g$ est injective : si $g(a) = g(b)$, appliquer $f$ donne $a = f(g(a)) = f(g(b)) = b$. Par le critère d'injection, $A$ est au plus dénombrable.

Proposition — Stabilité par parties et par images

Soit $E$ un ensemble au plus dénombrable. Alors :

toute partie de $E$ est au plus dénombrable ;
pour toute application $f$ définie sur $E$, l'image $f(E)$ est au plus dénombrable.

Preuve

Parties. Soit $F \subseteq E$. Comme $E$ est au plus dénombrable, il existe une injection $E \to \mathbb{N}$ ; sa restriction à $F$ est une injection $F \to \mathbb{N}$, donc $F$ est au plus dénombrable.
Images. Si $E = \varnothing$ alors $f(E) = \varnothing$, qui est au plus dénombrable. Si $E \neq \varnothing$, alors $E$ est non vide et au plus dénombrable, donc il existe une surjection $\mathbb{N} \to E$ ; composer avec $f$ donne une surjection $\mathbb{N} \to f(E)$. Comme $f(E)$ est non vide, le critère de surjection le rend au plus dénombrable.

Méthode — Montrer qu'un ensemble est au plus dénombrable

Pour montrer qu'un ensemble $E$ est au plus dénombrable, choisir celle des trois voies qui est la plus simple :

exhiber une bijection $\mathbb{N} \to E$ (cela prouve $E$ dénombrable, la conclusion la plus forte) ;
exhiber une injection $E \to \mathbb{N}$, ou vers un ensemble déjà connu comme au plus dénombrable ;
lorsque $E$ est non vide, exhiber une surjection $\mathbb{N} \to E$, ou depuis un ensemble déjà connu comme au plus dénombrable.

Pour renforcer « au plus dénombrable » en « dénombrable », vérifier de plus que $E$ est infini.

Exemple — Le groupe symétrique $\mathfrak{S}_n$

Pour $n \in \mathbb{N}^*$, le groupe symétrique $\mathfrak{S}_n = \mathfrak{S}(\llbracket 1, n \rrbracket)$ (rappelé de Groupe symétrique) est fini, avec $|\mathfrak{S}_n| = n!$ ; étant fini, il est au plus dénombrable. En revanche $\mathfrak{S}(\mathbb{N})$, l'ensemble des permutations de $\mathbb{N}$, est infini — et il se révélera non dénombrable, fait établi dans les exercices par un argument diagonal.

Compétences à pratiquer

Appliquer les critères d'injection et de surjection

III Opérations sur les ensembles dénombrables

La dénombrabilité est robuste : les opérations ensemblistes qui construisent de nouveaux ensembles — produits finis et réunions dénombrables — maintiennent au plus dénombrable un ensemble au plus dénombrable. Le moteur commun est un seul résultat : $\mathbb{N}^2$ est dénombrable. Une fois le plan des couples d'entiers énuméré, produits et réunions suivent. Cette section démontre le moteur, puis les deux théorèmes d'opérations, et en récolte les exemples standard $\mathbb{N}^p$, $\mathbb{Z}^2$, $\mathbb{Q}$.

Signaler une erreur

Proposition — $\mathbb{N}^2$ est dénombrable

L'ensemble $\mathbb{N} \times \mathbb{N}$ est dénombrable.

Preuve

On énumère les couples le long des diagonales $D_k = \{(i, j) \in \mathbb{N}^2 \mid i + j = k\}$. La diagonale $D_k$ contient exactement $k + 1$ couples, à savoir $(k, 0), (k-1, 1), \dots, (0, k)$, et les diagonales $D_0, D_1, D_2, \dots$ forment une partition de $\mathbb{N}^2$. En numérotant les couples diagonale par diagonale, et à l'intérieur de $D_k$ par $j$ croissant, les couples de $D_0, \dots, D_{k-1}$ utilisent déjà $$ 1 + 2 + \dots + k = \frac{k(k+1)}{2} $$ numéros, donc le couple $(i, j)$ avec $i + j = k$ reçoit le numéro $$ \varphi(i, j) = \frac{(i+j)(i+j+1)}{2} + j. $$ Par construction $\varphi : \mathbb{N}^2 \to \mathbb{N}$ attribue les entiers $0, 1, 2, \dots$ aux couples consécutivement, chaque couple recevant exactement un entier et chaque entier étant utilisé exactement une fois. Donc $\varphi$ est une bijection et $\mathbb{N}^2$ est dénombrable.

Exemple — Une injection par puissances de nombres premiers

Il existe une seconde voie vers la même conclusion, par une injection explicite plutôt qu'une énumération. L'application $(p, q) \mapsto 2^p\, 3^q$ est une injection $\mathbb{N}^2 \to \mathbb{N}$ : si $2^p 3^q = 2^{p'} 3^{q'}$, alors l'unicité de la factorisation en nombres premiers impose $p = p'$ et $q = q'$. Par le critère d'injection $\mathbb{N}^2$ est au plus dénombrable, et comme il est infini il est dénombrable. La bijection diagonale ci-dessus énumère explicitement $\mathbb{N}^2$ ; cette injection est la voie la plus rapide lorsqu'on a seulement besoin du caractère au plus dénombrable.

Proposition — Produits finis

Un produit cartésien $E_1 \times \dots \times E_p$ de $p \ge 1$ ensembles au plus dénombrables est au plus dénombrable. Si de plus chaque facteur est dénombrable, le produit est dénombrable.

Preuve

La démonstration n'est pas exigible. D'abord, $\mathbb{N}^p$ est dénombrable pour tout $p \ge 1$ : par récurrence, $\mathbb{N}^1 = \mathbb{N}$ est dénombrable, et $\mathbb{N}^{p+1} = \mathbb{N}^p \times \mathbb{N}$ est en bijection avec $\mathbb{N} \times \mathbb{N} = \mathbb{N}^2$ via une bijection $\mathbb{N}^p \to \mathbb{N}$ (hypothèse de récurrence), qui est dénombrable. Soient maintenant $E_1, \dots, E_p$ au plus dénombrables ; chacun porte une injection $f_i : E_i \to \mathbb{N}$, donc $(x_1, \dots, x_p) \mapsto (f_1(x_1), \dots, f_p(x_p))$ est une injection $E_1 \times \dots \times E_p \to \mathbb{N}^p$. Par le critère d'injection le produit est au plus dénombrable. Si de plus chaque $E_i$ est dénombrable, chacun est infini, donc le produit aussi, et un ensemble infini au plus dénombrable est dénombrable. Le produit est restreint à $p \ge 1$ car le produit vide est un singleton, fini et non dénombrable.

Proposition — Réunions dénombrables

Soit $(E_k)_{k \in K}$ une famille d'ensembles au plus dénombrables indexée par un ensemble au plus dénombrable $K$. Alors la réunion $\bigcup_{k \in K} E_k$ est au plus dénombrable. En particulier, une réunion finie ou dénombrable d'ensembles finis ou dénombrables est au plus dénombrable.

Preuve

La démonstration n'est pas exigible. On écarte les morceaux vides : si tous les $E_k$ sont vides, ou si $K = \varnothing$, la réunion est $\varnothing$, qui est au plus dénombrable. Sinon, soit $K'$ l'ensemble des indices $k$ tels que $E_k \neq \varnothing$ ; il est non vide et, en tant que partie de $K$, au plus dénombrable, donc il existe une surjection $m \mapsto k(m)$ de $\mathbb{N}$ sur $K'$. Pour chaque $k \in K'$, l'ensemble $E_k$ est non vide et au plus dénombrable, donc une surjection $\mathbb{N} \to E_k$ existe ; on en fixe une, notée $\varphi_k$, pour chaque $k \in K'$. Alors $$ \psi : \mathbb{N}^2 \to \bigcup_{k \in K} E_k, \qquad (n, m) \mapsto \varphi_{k(m)}(n) $$ est une surjection : tout élément de la réunion appartient à un $E_k$ non vide avec $k = k(m)$, et vaut $\varphi_k(n)$ pour un certain $n$. En composant $\psi$ avec une surjection $\mathbb{N} \to \mathbb{N}^2$ (qui existe puisque $\mathbb{N}^2$ est dénombrable), on obtient une surjection $\mathbb{N} \to \bigcup_{k \in K} E_k$. La réunion est non vide, donc par le critère de surjection elle est au plus dénombrable.

Exemple — $\mathbb{N}^p$, $\mathbb{Z}^2$ et $\mathbb{Q}$

Montrer que chacun des ensembles suivants est dénombrable.

$\mathbb{N}^p$ pour $p \in \mathbb{N}^*$ ;
$\mathbb{Z}^2$ ;
$\mathbb{Q}$.

Correction

$\mathbb{N}^p$ est le produit cartésien de $p \ge 1$ copies de l'ensemble dénombrable $\mathbb{N}$, donc dénombrable par la proposition sur les produits finis.
$\mathbb{Z}$ est dénombrable, donc $\mathbb{Z}^2 = \mathbb{Z} \times \mathbb{Z}$ est un produit de deux ensembles dénombrables, donc dénombrable.
Tout rationnel admet une unique représentation irréductible $\frac{p}{q}$ avec $p \in \mathbb{Z}$, $q \in \mathbb{N}^*$ et $\gcd(|p|, q) = 1$. L'application $\mathbb{Q} \to \mathbb{Z} \times \mathbb{N}^*$ envoyant un rationnel sur ce couple $(p, q)$ est injective. Or $\mathbb{Z} \times \mathbb{N}^*$ est un produit de deux ensembles dénombrables, donc dénombrable ; par le critère d'injection $\mathbb{Q}$ est au plus dénombrable, et étant infini il est dénombrable.

Méthode — Démontrer la dénombrabilité par opérations

Pour montrer qu'un ensemble est au plus dénombrable sans construire une bijection à la main, l'exprimer à partir d'ensembles déjà connus comme au plus dénombrables ($\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, tout $\mathbb{N}^p$) :

comme produit fini de tels ensembles ;
comme réunion finie ou dénombrable de tels ensembles ;
comme image d'un tel ensemble par une application, ou comme partie d'un tel ensemble.

Chaque opération préserve « au plus dénombrable », donc la conclusion est immédiate.

Un dernier point du programme trouve sa place ici comme renvoi plutôt que comme résultat. Le programme officiel mentionne, comme capacité, que le support d'une famille sommable de nombres complexes est au plus dénombrable. Les familles sommables ne sont pas définies dans ce chapitre — elles relèvent de Séries numériques et vectorielles, où cet énoncé même est démontré. On le signale seulement : une fois la sommabilité disponible, le support d'une famille sommable est exactement le type d'ensemble au plus dénombrable que le présent chapitre caractérise.

Signaler une erreur

Compétences à pratiquer

Démontrer la dénombrabilité par opérations

IV Les ensembles non dénombrables

Jusqu'ici tout ensemble infini s'est révélé dénombrable. Place au cas contraire. Comme « dénombrable » signifie « en bijection avec $\mathbb{N}$ », on dit qu'un ensemble est non dénombrable lorsqu'il n'est pas au plus dénombrable — ni fini ni dénombrable ; un ensemble fini n'est donc pas non dénombrable. Le résultat phare est que $\mathbb{R}$ est non dénombrable : il y a véritablement plus d'une taille d'infini. La démonstration est l'argument diagonal de Cantor, la technique la plus importante du chapitre.

Signaler une erreur

Théorème — $\mathbb{R}$ est non dénombrable

L'ensemble $\mathbb{R}$ n'est pas au plus dénombrable. Déjà l'intervalle $[0, 1[$ est non dénombrable.

Preuve

La démonstration n'est pas exigible. On travaille dans $[0, 1[$, où tout nombre admet un développement décimal $0{,}d_1 d_2 d_3 \dots$ de chiffres $d_k \in \{0, \dots, 9\}$. Pour rendre le développement unique, on utilise le développement propre — celui qui ne se termine pas par une infinité de $9$. Supposons, par l'absurde, que $[0, 1[$ soit au plus dénombrable ; il est infini, donc dénombrable, et comme $\mathbb{N}^*$ est lui-même dénombrable, ses éléments s'énumèrent en $[0,1[ = \{x_k \mid k \in \mathbb{N}^*\}$, où $x_k = 0{,}d_{k1} d_{k2} d_{k3} \dots$ est le développement propre de $x_k$.
On construit un nombre $y = 0{,}e_1 e_2 e_3 \dots$ en choisissant, pour chaque $k \in \mathbb{N}^*$, un chiffre $e_k \in \{1, \dots, 8\}$ avec $e_k \neq d_{kk}$ — par exemple $e_k = 4$ si $d_{kk} \neq 4$, et $e_k = 5$ sinon. Comme chaque $e_k$ appartient à $\{1, \dots, 8\}$, le développement de $y$ n'a pas de queue de $9$ : il est lui-même propre, et $y \in [0, 1[$. Pour chaque $k$, les développements propres de $y$ et de $x_k$ diffèrent au $k$-ième chiffre ($e_k \neq d_{kk}$), donc $y \neq x_k$. Ainsi $y$ est un élément de $[0, 1[$ égal à aucun $x_k$, ce qui contredit $[0,1[ = \{x_k \mid k \in \mathbb{N}^*\}$.
Donc $[0, 1[$ est non dénombrable. Comme $[0, 1[ \subseteq \mathbb{R}$ et qu'une partie d'un ensemble au plus dénombrable est au plus dénombrable, $\mathbb{R}$ ne peut être au plus dénombrable : $\mathbb{R}$ est non dénombrable.

Exemple — Nombres irrationnels et intervalles

L'ensemble $\mathbb{R} \setminus \mathbb{Q}$ des nombres irrationnels est non dénombrable. En effet, si $\mathbb{R} \setminus \mathbb{Q}$ était au plus dénombrable, alors $\mathbb{R} = \mathbb{Q} \cup (\mathbb{R} \setminus \mathbb{Q})$ serait une réunion de deux ensembles au plus dénombrables ($\mathbb{Q}$ est dénombrable), donc au plus dénombrable — ce qui contredit le théorème. Ainsi « presque tous » les réels sont irrationnels, au sens de la taille. De même tout intervalle $I$ ayant au moins deux points est non dénombrable : en choisissant $a < b$ dans $I$, l'application affine $t \mapsto a + t(b - a)$ est une injection $[0, 1[ \to [a, b[ \subseteq I$, et un ensemble recevant une injection d'un ensemble non dénombrable est lui-même non dénombrable.

Méthode — Démontrer qu'un ensemble est non dénombrable

Pour montrer qu'un ensemble $E$ est non dénombrable, utiliser soit :

un argument diagonal — supposer une énumération de $E$ et construire un élément de $E$ qui diffère du $k$-ième élément listé à la « coordonnée $k$ », contredisant l'énumération ;
une comparaison — exhiber une injection $U \to E$ depuis un ensemble $U$ déjà connu comme non dénombrable (un intervalle non trivial, $\mathbb{R} \setminus \mathbb{Q}$, $\mathbb{R}$). Si $E$ recevait une telle injection et était au plus dénombrable, $U$ le serait aussi.

Pour aller plus loin

Le programme PC s'arrête ici. Les extensions MP (cadres plus abstraits, modes de convergence supplémentaires, espérance conditionnelle) sont signalées mais non exigibles au niveau PC.

Signaler une erreur

Compétences à pratiquer

Démontrer qu'un ensemble est non dénombrable

V Pour aller plus loin

Compétences à pratiquer

Combiner les outils du chapitre