Recherchez sur tout Techno-Science.net
       
Techno-Science.net : Suivez l'actualité des sciences et des technologies, découvrez, commentez
Catégories
Techniques
Sciences
Encore plus...
Techno-Science.net
Partenaires
Organismes
 CEA
 ESA
Sites Web
Photo Mystérieuse

Que représente
cette image ?
 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | +
Ensemble dénombrable

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 d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un tout », comme...) 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 l'univers.) ensemble équipotent à un ensemble dénombrable (Un ensemble E est dit dénombrable s'il est équipotent à l'ensemble des entiers naturels , c'est-à-dire s'il existe une bijection de E sur  ; cela équivaut à...) est lui-même dénombrable.

Un ensemble dénombrable est infini (Le mot « infini » (-e, -s ; du latin finitus, « limité »), est un adjectif servant à qualifier quelque chose qui n'a pas de limite en nombre ou en taille.), car équipotent à \mathbb{N}, qui est infini. Mais la réciproque est fausse : il existe des ensembles infinis non dénombrables. Le mathématicien 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 l'extension radicale de l'espérance de vie humaine. Par une évolution progressive allant du...) vu ci-dessus mais aussi pour désigner un ensemble fini (En mathématiques, un ensemble E est dit fini si et seulement si E est vide ou s'il existe un entier n et une bijection de E dans l'ensemble des n premiers entiers naturels.)
  • 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 division entre les définitions réelles et les définitions nominales.), 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 s'ajoute à quelque chose de nature identique. La seconde est une unité de mesure du temps. La seconde d'arc est une...) 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 (Galilée ou Galileo Galilei (né à Pise le 15 février 1564 et mort à Arcetri près de Florence, le 8 janvier 1642) est un physicien et astronome italien du XVIIe siècle, célèbre pour avoir jeté les fondements des sciences mécaniques ainsi...) 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 (En mathématiques, une démonstration permet d'établir une proposition à partir de propositions initiales, ou précédemment démontrées...) 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 (Le vide est ordinairement défini comme l'absence de matière dans une zone spatiale.) 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 composition interne · notée multiplicativement, est un élément y...). 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 (Une fonction f: X → Y est dite bijective ou est une bijection si pour tout y dans l’ensemble d'arrivée Y il existe un et un seul x dans...) 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 est l'ensemble de tous les couples, dont la première composante appartient à X et la seconde à Y. On généralise...) d'une famille finie (En mathématiques, la notion de famille est une généralisation de celle de suite, suite finie ou suite indexée par les entiers. Ainsi on pourra parler, en algèbre...) 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 constitué des éléments dont l'image par f appartient à B : .) 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 recevoir l'induction de l'inducteur et de la transformer en...) 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 (Le mot axiome vient du grec αξιωμα (axioma), qui signifie "qui est considéré comme digne ou convenable" ou "qui est considéré comme...) 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 encore B est sur-ensemble de A, si tout élément du sous-ensemble A est aussi élément du sur-ensemble B....) 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 assertion qui peut être établie comme vraie au travers d'un raisonnement logique construit à partir...) : 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 (Une fonction est dite surjective ou est une surjection si pour tout y dans l'ensemble d'arrivée Y, il existe au moins un élément x de la source X tel que...) 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 dans l'archipel des Mascareignes à environ 700 kilomètres à l'est de Madagascar et à 170...) 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 suivante :) 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
Source: Wikipédia publiée sous licence CC-BY-SA 3.0.

Vous pouvez soumettre une modification à cette définition sur cette page. La liste des auteurs de cet article est disponible ici.