Ensemble dénombrable - Définition

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs est disponible ici.

Un ensemble E est dit dénombrable s'il est équipotent à l'ensemble des entiers naturels \mathbb{N}, c'est-à-dire s'il existe une bijection de E sur \mathbb{N} ; cela équivaut à l'existence d'une bijection de \mathbb{N} sur E.

Naïvement, dire qu'un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection...) E est dénombrable signifie qu'il est possible de compter un à un chacun de ses éléments, et de leur attribuer un rang : on peut numéroter les éléments de E sans omission ni répétition, en utilisant tous les entiers naturels.

L'ensemble des entiers naturels est dénombrable, car un ensemble est toujours équipotent à lui-même, et tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou...) ensemble équipotent à un ensemble dénombrable (En mathématiques, un ensemble est dit dénombrable, ou infini dénombrable, lorsque...) est lui-même dénombrable.

Un ensemble dénombrable est infini (Le mot « infini » (-e, -s ; du latin finitus,...), car équipotent à \mathbb{N}, qui est infini. Mais la réciproque est fausse : il existe des ensembles infinis non dénombrables. Le mathématicien (Un mathématicien est au sens restreint un chercheur en mathématiques, par extension toute...) Cantor, qui introduisit la notion de dénombrabilité, démontra que l'ensemble des nombres réels, noté \ \mathbb{R}, n'est pas dénombrable.

Vocabulaire

L'expression ensemble dénombrable a deux définitions :

  • Certaines publications emploient cette expression non seulement dans le sens (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but...) vu ci-dessus mais aussi pour désigner un ensemble fini (En mathématiques, un ensemble E est dit fini si et seulement s'il existe un entier n et une...)
  • D'autres utilisent cette expression uniquement pour les ensembles satisfaisant la définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la...), et préfèrent employer l'expression ensemble au plus dénombrable pour désigner un ensemble soit fini, soit dénombrable.

Il faut donc prendre garde à la convention utilisée lors de la lecture d'une publication sur le sujet. Dans cet article, c'est la seconde ( Seconde est le féminin de l'adjectif second, qui vient immédiatement après le premier ou qui...) acception qui sera utilisée.

Ensembles usuels et dénombrabilité

  • Par définition, l'ensemble \mathbb{N} des entiers naturels est dénombrable.
  • L'ensemble \mathbb{N}^* des entiers naturels non nuls est dénombrable. En effet, l'application \begin{matrix}\mathbb{N}^* & \longrightarrow & \mathbb{N} \\ n & \longmapsto & n-1\end{matrix} est bijective.
  • L'ensemble des entiers naturels pairs, noté 2\, \mathbb{N}, est dénombrable. En effet, l'application \begin{matrix}\mathbb{N} & \longrightarrow & \ 2\, \mathbb{N} \\ n & \longmapsto & 2\, n\end{matrix} est bijective.
  • L'ensemble des carrés parfaits, noté ici \mathbb{N}^{(2)}, est dénombrable. En effet, l'application \begin{matrix}\mathbb{N} & \longrightarrow & \ \mathbb{N}^{(2)} \\ n & \longmapsto & n^2\end{matrix} est bijective.
    On doit à Galilée la remarque qu'il y a " autant " de carrés parfaits que d'entiers naturels, mettant ainsi en défaut l'affirmation classique (qu'on trouve dans les Éléments d'Euclide): " Le tout est plus grand que la partie. "
  • L'ensemble \mathbb{Z} des entiers relatifs est dénombrable. En effet, l'application \begin{matrix}\mathbb{Z} & \longrightarrow & \mathbb{N} \\ n & \longmapsto & \left\{\begin{matrix} 2n & \mbox{si } n\in\mathbb{N} \\ -2n-1 & \mbox{si } n\in\mathbb{Z} \setminus \mathbb{N} \end{matrix}\right. \end{matrix} est bijective.
  • L'ensemble \mathbb{N}\times\mathbb{N} des couples d'entiers naturels est dénombrable, car l'application \begin{matrix}\mathbb{N}\times\mathbb{N} & \longrightarrow & \mathbb{N}^* \\ (n,m) & \longmapsto & 2^n(2m+1) \end{matrix} est bijective (tout entier naturel strictement positif se factorise de manière unique sous forme du produit d'une puissance (Le mot puissance est employé dans plusieurs domaines avec une signification particulière :) de 2, et d'un entier impair).
  • L'ensemble \mathbb{Q} des nombres rationnels est dénombrable (voir plus loin une démonstration de cette affirmation).
  • L'ensemble \overline{\mathbb{A}} des nombres algébriques (réels ou complexes) est dénombrable. Comme aucun des deux ensembles \mathbb{R} et \mathbb{C} n'est dénombrable, on en déduit l'existence de nombres (réels ou complexes) transcendants.

Quelques propriétés

Partie d'un ensemble dénombrable

Toute partie A de \mathbb{N} est au plus dénombrable.

En effet, si A est fini, alors a fortiori A est au plus dénombrable.

Supposons maintenant A infini. Étant une partie non-vide de \mathbb{N}, A admet donc un plus petit élément. Notons le a0.

Soit n\in\mathbb{N}. On suppose avoir prouvé l'existence d'éléments de A notés a_0,a_1,\ldots,a_n tels que :

(i) a_0 < a_1 < \ldots < a_n
(ii) \forall x\in A \setminus \{a_0, a_1, \ldots, a_n\}, a_n < x

L'ensemble A' = A \setminus \{a_0, a_1, \ldots, a_n\} n'est pas vide car A est infini, donc A' admet un plus petit élément que l'on note an + 1. On a alors :

a_{n+1}\in A' donc an < an + 1
\forall x\in A \setminus \{a_0, a_1, \ldots, a_n, a_{n+1}\} = A' \setminus \{a_{n+1}\}, a_{n+1} < x

On a ainsi montré par récurrence l'existence d'une suite (a_n)_{n\in\mathbb{N}} \in A^{\mathbb{N}} strictement croissante. Posons B = \{(a_n \;|\; n\in\mathbb{N}\}. B est dénombrable et inclus dans A. Montrons l'inclusion inverse (En mathématiques, l'inverse d'un élément x d'un ensemble muni d'une loi de...). Soit n élément de A. La suite (a_n)_{n\in\mathbb{N}} étant strictement croissante, on a n \le a_n, donc d'après (ii) n\notin A \setminus \{a_0, a_1, \ldots, a_n\}, donc n\in\{a_0, a_1, \ldots, a_n\} et donc n\in B.

On a ainsi prouvé que A = B, et donc que A est dénombrable.

Dans tous les cas, A est donc au plus dénombrable.

Toute partie d'un ensemble au plus dénombrable est au plus dénombrable.

Soit E un ensemble au plus dénombrable et F une partie de E. Soit \varphi une bijection de E sur une partie de \mathbb{N}. La restriction de \varphi à F est une bijection de F sur \varphi (F) qui est une partie de \mathbb N, donc au plus dénombrable d'après la propriété ci-dessus. F étant équipotent à \varphi (F) est elle-même au plus dénombrable.

Produit d'ensembles dénombrables

Tout produit cartésien (En mathématiques, le produit cartésien de deux ensembles X et Y, appelé...) d'une famille finie (En mathématiques, la notion de famille est une généralisation de celle de suite, suite finie ou...) d'ensembles dénombrables est dénombrable.

Soient A et B deux ensembles dénombrables. Il existe une bijection \varphi de A sur \mathbb{N} et une bijection ψ de B sur \mathbb{N}. Définissons:

\lambda : \begin{matrix}A\times B & \longrightarrow & \mathbb{N}\times\mathbb{N} \\ (x, y) & \longmapsto & (\varphi(x), \psi(y))\end{matrix}

Cette application est bijective de A \times B sur \mathbb{N}\times\mathbb{N} qui est dénombrable. Donc A \times B est dénombrable.

Une récurrence permet d'étendre ce résultat au produit cartésien de toute famille finie d'ensembles dénombrables.

Image et image réciproque (L'image réciproque d'une partie B d'un ensemble Y par une application est le sous-ensemble de X...) d'ensembles dénombrables

Soient E et F deux ensembles non vides, et f une application de E dans F.

1. Si f est injective et si F est au plus dénombrable, alors E est au plus dénombrable.

f étant injective, elle induit (L'induit est un organe généralement électromagnétique utilisé en électrotechnique chargé de...) une bijection de E sur f(E). Or, f(E) est une partie de F et est donc au plus dénombrable. E est donc au plus dénombrable.

2. Si f est surjective et si E est au plus dénombrable, alors F est au plus dénombrable.

E étant au plus dénombrable, il existe \varphi : E \to A bijective, avec A \subset \mathbb{N}. Or \mathbb{N} est bien ordonné, donc E peut être muni d'un bon ordre (défini ici explicitement, sans le recours habituel à l'axiome (Un axiome (du grec ancien αξιωμα/axioma,...) du choix), en posant :

\forall (a,b) \in E^2, a \leq_E b \Leftrightarrow \varphi(a) \le \varphi(b) ;

dès lors, toute partie non vide de E possède un minimum.

Soit y\in F; comme f est surjective, f − 1({y}) est un sous-ensemble (En mathématiques, un ensemble A est un sous-ensemble ou une partie d’un ensemble B, ou...) non vide de E. On définit alors :

g : F \to E, y \mapsto \min(f^{-1}(\{y\}) (\ g(y) est le plus petit antécédent de y par f)

Par construction, pour tout \ y \in F,\, f(g(y)) = y, donc l'application g est injective. L'ensemble E étant au plus dénombrable, il résulte de 1. que F est au plus dénombrable.

Corollaire (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une...) : les trois propositions suivantes sont équivalentes :

  • L'ensemble E est au plus dénombrable.
  • Il existe une injection (Le mot injection peut avoir plusieurs significations :) de E vers \mathbb{N}.
  • Il existe une surjection (En mathématiques, une surjection ou application surjective est une application pour laquelle...) de \mathbb{N} vers E.

Réunion d'ensembles dénombrables

La réunion (La Réunion est une île française du sud-ouest de l'océan Indien située...) de toute famille dénombrable d'ensembles dénombrables est dénombrable

Plus formellement, si I est un ensemble dénombrable et si (A_i)_{i\in I} est une famille d'ensembles dénombrables, alors A = \bigcup_{i\in I} A_i est un ensemble dénombrable. I étant dénombrable, il existe une bijection f de \mathbb{N} sur I, et pour tout i de I, Ai étant dénombrable, il existe une bijection λi de \mathbb{N} sur Ai. On pose alors :

\varphi : \begin{matrix} \mathbb{N}\times\mathbb{N} & \longrightarrow & A \\ (a,b) & \longmapsto & \lambda_{f(a)}(b) \end{matrix}.

\varphi est bien une application dont l'ensemble d'arrivée est A puisque f(a)\in I, donc \lambda_{f(a)}(b)\in A_{f(a)} \subset A.

Montrons que \varphi est surjective. Soit x\in A. Il existe i tel que x\in A_i. Soit a\in\mathbb{N} tel que i = f(a). x\in A_i et λi est une bijection de \mathbb{N} dans Ai, donc \exists b\in\mathbb{N}, x = \lambda_i(b) = \lambda_{f(a)}(b)\,, ce qui donne bien x = \varphi(a,b)\,

Ainsi, \varphi est surjective et \mathbb{N}\times\mathbb{N} est dénombrable, donc A est dénombrable.

Toute réunion finie d'ensembles dénombrables est dénombrable

Dans le cas où I est fini, il suffit de reprendre la démonstration précédente, mais avec f surjective de \mathbb N sur I.

Toute réunion au plus dénombrable d'ensembles au plus dénombrables est au plus dénombrable

Dans le cas où certains Ai sont finis, il suffit de reprendre la démonstration précédente, mais avec λi surjective de \mathbb N sur Ai.

Dénombrabilité de l'ensemble des rationnels

On justifie ici, à l'aide de certaines des propriétés précédemment établies, la dénombrabilité de l'ensemble \ \mathbb{Q} des rationnels.

L'application \ f : \mathbb{Z} \times \mathbb{N}^* \to \mathbb{Q}, (p,\, q) \mapsto \frac{p}{q} est surjective, car tout rationnel s'écrit d'au moins une manière sous la forme \frac{p}{q}, où \ p \in \mathbb{Z} et \ q \in \mathbb{N}^* ; de plus, \ \mathbb{Z} \times \mathbb{N}^* est dénombrable (produit cartésien de deux ensembles dénombrables).

L'existence de cette surjection implique alors que \ \mathbb{Q} est au plus dénombrable ; étant infini, il est donc dénombrable.

On peut aussi montrer que la suite (x_n)_{n \in \mathbb N} définie ci-dessous donne une bijection entre \mathbb N et l'ensemble des rationnels positifs ou nuls :

x0 = 0
\forall n \ge 0, x_{n+1} =  g(x_n) avec g(x) = {1 \over 1 + 2E(x) - x}, où E(x) désigne la partie entière (En mathématiques, la fonction partie entière est la fonction définie de la manière...) de x.

Voici les premières valeurs de la suite :

0, 1, {1 \over 2}, 2, {1\over 3}, {3\over 2}, {2\over 3}, 3, {1\over 4}, {4\over 3}, {3\over 5}, {5\over 2}, {2\over 5}, {5\over 3}, {3\over 4}, 4, {1\over 5}, {5\over 4}, {4\over 7}, {7\over 3}, {3\over 8}, \ldots
Page générée en 0.051 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
A propos - Informations légales | Partenaire: HD-Numérique
Version anglaise | Version allemande | Version espagnole | Version portugaise