Ensemble dénombrable

Infos
Un ensemble E est dit dénombrable s'il est équipotent à l'ensemble des entiers naturels \mathbb, c'est-à-dire s'il existe une bijection de E sur \mathbb ; cela équivaut à l'existence d'une bijection de \mathbb sur E. Naïvement, dire qu'un ensemble 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 le
Ensemble dénombrable

Un ensemble E est dit dénombrable s'il est équipotent à l'ensemble des entiers naturels \mathbb, c'est-à-dire s'il existe une bijection de E sur \mathbb ; cela équivaut à l'existence d'une bijection de \mathbb sur E. Naïvement, dire qu'un ensemble 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 ensemble équipotent à un ensemble dénombrable est lui-même dénombrable. Un ensemble dénombrable est infini, car équipotent à \mathbb, qui est infini. Mais la réciproque est fausse : il existe des ensembles infinis non dénombrables. Le mathématicien Georg Cantor, qui introduisit la notion de dénombrabilité, démontra que l'ensemble des nombres réels, noté \mathbb, n'est pas dénombrable. Il mit ainsi en lumière une nouvelle classe d'ensembles, trop "grands" pour être mis en bijection avec les nombres naturels : les ensembles indénombrables.

Définitions

L'expression ensemble dénombrable a deux définitions :
- Certaines publications emploient cette expression non seulement dans le sens vu ci-dessus mais aussi pour désigner un ensemble fini ;
- D'autres utilisent cette expression uniquement pour les ensembles satisfaisant la définition, 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 acception qui sera utilisée.

Ensembles usuels et dénombrabilité

- Par définition, l'ensemble \mathbb des entiers naturels est dénombrable.
- L'ensemble \mathbb^
- des entiers naturels non nuls est dénombrable. En effet, l'application \begin\mathbb^
- & \longrightarrow & \mathbb \\ n & \longmapsto & n-1\end est bijective.
- L'ensemble des entiers naturels pairs, noté 2\, \mathbb, est dénombrable. En effet, l'application \begin\mathbb & \longrightarrow & \ 2\, \mathbb \\ n & \longmapsto & 2\, n\end est bijective.
- L'ensemble des carrés parfaits, noté ici \mathbb^, est dénombrable. En effet, l'application \begin\mathbb & \longrightarrow & \ \mathbb^ \\ n & \longmapsto & n^2\end 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 des entiers relatifs est dénombrable. En effet, l'application \begin\mathbb & \longrightarrow & \mathbb \\ n & \longmapsto & \left\\begin 2n & \mbox n\in\mathbb \\ -2n-1 & \mbox n\in\mathbb \setminus \mathbb \end\right. \end est bijective.
- L'ensemble \mathbb\times\mathbb des couples d'entiers naturels est dénombrable, car l'application \begin\mathbb\times\mathbb & \longrightarrow & \mathbb^
- \\ (n, m) & \longmapsto & 2^n(2m+1) \end est bijective (tout entier naturel strictement positif se factorise de manière unique sous forme du produit d'une puissance de 2, et d'un entier impair).
- L'ensemble \mathbb des nombres rationnels est dénombrable (voir plus loin une démonstration de cette affirmation).
- L'ensemble \overline\mathbb des nombres algébriques (réels ou complexes) est dénombrable. Comme aucun des deux ensembles \mathbb et \mathbb 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

Un ensemble est fini si pour un certain entier N, il est en bijection avec les N premiers entiers, soit , les entiers strictement plus petits que N. En particulier l'ensemble vide (cas N = 0) est bien entendu fini. Un segment initial de \mathbb est soit \mathbb lui-même, soit l'ensemble des entiers inférieurs à un entier donné. On peut montrer que : ;Pour toute partie A de \mathbb, il existe une bijection strictement croissante d'un segment initial de \mathbb dans A. ce dont on déduit, par définition d'une part des ensembles finis, d'autre part des ensembles dénombrables : ;Toute partie A de \mathbb est finie ou dénombrable. On peut supposer que cet ensemble A est non vide. On va utiliser le fait que \mathbb est bien ordonné, c'est-à-dire que tous sous-ensemble non vide de \mathbb possède un plus petit élément. En effet, on peut définir une suite (a_n) par récurrenceL'existence et l'unicité d'une suite définie par récurrence sur \mathbb se démontre en théorie des ensembles. de la façon suivante : :a_0 est le plus petit élément de A (qui existe forcément car A est non vide) ; :a_ est le plus petit élément de A supérieur à a_n s'il en existe un, est non défini sinon, ou si a_n n'est pas défini. Cette suite établit bien une bijection strictement croissante d'un segment initial des entiers dans A. boîte déroulante|titre=Démonstration|contenu=Par construction, soit cette suite est définie sur tous les entiers naturels, soit il existe un entier N tel qu'elle soit définie pour les N+1 premiers entiers et ceux-là seulement. Également par construction elle est strictement croissante, ce qui assure, par une récurrence immédiate, que si an est défini, alors an > n. On en déduit donc que si la suite est définie sur tout \mathbb, elle n'est pas bornée. Montrons maintenant que l'image de cette suite est A. Soit b un élément de A. Il existe un entier p tel que apb : soit que la suite ne soit pas bornée, soit qu'il existe un entier N tel que l'ensembles des élements de A supérieurs ou égaux à ap est vide. On peut donc définir, par la propriété de bon ordre, le plus petit entier n tel que anb. Par définition de la suite, si n=0 c'est que b=a0 le plus petit élément de A. Sinon c'est que n=m+1, et que an est le plus petit élément parmi les éléments de A strictement supérieurs à am, dont b justement fait partie, par définition de n. Donc ban, donc b = an. La suite a_n définie donc une bijection soit entre \mathbb et A, auquel cas par définition A est dénombrable, soit entre les N+1 premiers entiers et A, auquel cas A est par définition finie. Une conséquence immédiate de ce résultat (par composition des bijections qui assurent l'équipotence) est que : ;Toute partie d'un ensemble dénombrable est finie ou dénombrable. Une autre conséquence analogue, tout aussi immédiate, est que : ;Si A est subpotent à \mathbb, c'est-à-dire qu'il existe une injection de A dans \mathbb, alors A est fini ou dénombrable. On peut donc parler d'ensemble au plus dénombrable pour un ensemble fini ou dénombrable. On peut remarquer que si A est un sous-ensemble des N premiers entiers, c'est un sous-ensemble de \mathbb borné. comme le premier résultat établi une bijection croissante d'un segment initial de \mathbb dans A, celui-ci est nécessairement fini. On en déduit donc que : ;Tout sous-ensemble d'un ensemble fini est fini.

Produit d'ensembles dénombrables

; Tout produit cartésien d'une famille finie d'ensembles dénombrables est dénombrable. Soient A et B deux ensembles dénombrables. Il existe une bijection \varphi de A sur \mathbb et une bijection \psi de B sur \mathbb. Définissons: ::\lambda : \beginA\times B & \longrightarrow & \mathbb\times\mathbb \\ (x, y) & \longmapsto & (\varphi(x), \psi(y))\end Cette application est bijective de A \times B sur \mathbb\times\mathbb 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 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 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. Or \mathbb est bien ordonné, donc E peut être muni d'un bon ordre (défini ici explicitement, sans le recours habituel à l'axiome 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^(\y\) est un sous-ensemble non vide de E. On définit alors : :g : F \to E, y \mapsto \min(f^(\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 : les trois propositions suivantes sont équivalentes :
- L'ensemble E est au plus dénombrable.
- Il existe une injection de E vers \mathbb.
- Il existe une surjection de \mathbb vers E.

Réunion d'ensembles dénombrables

; La réunion 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 sur I. Les A_i étant dénombrables, il existe pour chaque i de I, une bijection de \mathbb sur A_i. D'après l'axiome du choix (dénombrable), on a donc une suite de fonction (\lambda_i)_i\in I, où \lambda_i est une bijection de \mathbb sur A_i. On pose alors : ::\varphi : \begin \mathbb\times\mathbb & \longrightarrow & A \\ (a, b) & \longmapsto & \lambda_(b) \end. \varphi est bien une application dont l'ensemble d'arrivée est A puisque f(a)\in I, donc \lambda_(b)\in 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 tel que i = f(a). x\in A_i et \lambda_i est une bijection de \mathbb dans A_i, donc \exists b\in\mathbb, x = \lambda_i(b) = \lambda_(b)\, , ce qui donne bien x = \varphi(a, b)\, Ainsi, \varphi est surjective et \mathbb\times\mathbb 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. L'axiome du choix n'est cependant pas nécessaire dans ce cas. ; Toute réunion au plus dénombrable d'ensembles au plus dénombrables est au plus dénombrable Dans le cas où certains A_i sont finis, il suffit de reprendre la démonstration précédente, mais avec \lambda_i surjective de \mathbb N sur A_i.

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 des rationnels. L'application f : \mathbb \times \mathbb^
- \to \mathbb, (p, \, q) \mapsto \frac est surjective, car tout rationnel s'écrit d'au moins une manière sous la forme \frac, où \ p \in \mathbb et \ q \in \mathbb^
- ; de plus, \ \mathbb \times \mathbb^
- est dénombrable (produit cartésien de deux ensembles dénombrables). L'existence de cette surjection implique alors que \mathbb 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 : ::x_0 = 0 ::\forall n \ge 0, x_ = g(x_n) avec g(x) = 1 \over 1 + 2E(x) - x, où E(x) désigne la partie entiè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

Notes

Voir aussi

- Hypothèse du continu
- Georg Cantor
- Ensemble indénombrable Catégorie:Théorie des ensembles Catégorie:Infini ar:مجموعة عدودة bg:Изброимо множество bn:গণনাযোগ্য সেট cs:Spočetná množina da:Tællelig mængde de:Abzählbarkeit en:Countable set es:Conjunto numerable fa:مجموعه شمارا fi:Numeroituva joukko he:קבוצה בת מנייה is:Teljanlegt mengi it:Insieme numerabile ja:可算無限集合 ko:가산 집합 lmo:Cungjuunt cüntàbil lt:Skaiti aibė nl:Aftelbare verzameling no:Tellbar pl:Zbiór przeliczalny pt:Conjunto contável ru:Счётное множество simple:Countable set sk:Spočítateľná množina sr:Пребројиво бесконачан скуп sv:Uppräknelig ta:எண்ணுறுமையும் எண்ணுறாமையும் zh:可數集
Sujets connexes
Antécédent (mathématiques)   Argument de la diagonale de Cantor   Axiome du choix   Bijection   Carré parfait   Ensemble   Ensemble bien ordonné   Ensemble indénombrable   Entier naturel   Euclide   Existence   Extremum   Galileo Galilei   Georg Cantor   Hypothèse du continu   Infini   Injection (mathématiques)   Nombre algébrique   Nombre rationnel   Nombre réel   Nombre transcendant   Partie entière   Surjection   Théorie des ensembles  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^