Ensemble dénombrable

En mathématiques , un ensemble est dénombrable s'il est fini ou s'il peut être mis en correspondance bijective avec l'ensemble des nombres naturels . De manière équivalente, un ensemble est dénombrable s'il existe une fonction injective de lui dans les nombres naturels ; cela signifie que chaque élément de l'ensemble peut être associé à un nombre naturel unique, ou que les éléments de l'ensemble peuvent être comptés un par un, bien que le comptage puisse ne jamais se terminer en raison d'un nombre infini d'éléments.

En termes plus techniques, en supposant l' axiome du choix dénombrable , un ensemble est dénombrable si sa cardinalité (le nombre d'éléments de l'ensemble) n'est pas supérieure à celle des nombres naturels. Un ensemble dénombrable qui n'est pas fini est dit dénombrablement infini .

Le concept est attribué à Georg Cantor , qui a prouvé l'existence d' ensembles indénombrables , c'est-à-dire d'ensembles qui ne sont pas dénombrables ; par exemple l'ensemble des nombres réels .

Bien que les termes « dénombrable » et « dénombrablement infini » tels que définis ici soient assez courants, la terminologie n'est pas universelle. Un style alternatif utilise dénombrable pour signifier ce qui est appelé ici dénombrablement infini, et au plus dénombrable pour signifier ce qui est appelé ici dénombrable.

Les termes énumérable et dénombrable peuvent également être utilisés, par exemple en se référant respectivement à dénombrable et dénombrablement infini, les définitions varient et il faut faire attention à la différence avec récursivement énumérable .

Un ensemble est dénombrable si :

• Sa cardinalité est inférieure ou égale à ( aleph-null ), la cardinalité de l'ensemble des nombres naturels .
• Il existe une fonction injective de à .
• Il existe une application bijective entre et un sous-ensemble de .

Toutes ces définitions sont équivalentes.

Un ensemble est dénombrablement infini si :

• Sa cardinalité est exactement .
• Il existe une application injective et surjective (et donc bijective ) entre et .
• Les éléments de peuvent être disposés dans une séquence infinie , où est distinct de et chaque élément de est répertorié.

Un ensemble est indénombrable s'il n'est pas dénombrable, c'est-à-dire que son cardinal est supérieur à .

En 1874, dans son premier article sur la théorie des ensembles , Cantor a prouvé que l'ensemble des nombres réels est indénombrable, montrant ainsi que tous les ensembles infinis ne sont pas dénombrables. En 1878, il a utilisé des correspondances biunivoques pour définir et comparer les cardinalités. En 1883, il a étendu les nombres naturels avec ses ordinaux infinis et a utilisé des ensembles d'ordinaux pour produire une infinité d'ensembles ayant des cardinalités infinies différentes.

Un ensemble est une collection d' éléments et peut être décrit de plusieurs manières. Une façon consiste simplement à lister tous ses éléments ; par exemple, l'ensemble constitué des entiers 3, 4 et 5 peut être noté , appelé forme de liste. Cela n'est toutefois efficace que pour les petits ensembles ; pour les ensembles plus grands, cela prendrait du temps et serait sujet à des erreurs. Au lieu de lister chaque élément individuellement, on utilise parfois des points de suspension ("...") pour représenter de nombreux éléments entre l'élément de départ et l'élément de fin d'un ensemble, si l'auteur pense que le lecteur peut facilement deviner ce que ... représente ; par exemple, on suppose que ... désigne l'ensemble des entiers de 1 à 100. Même dans ce cas, cependant, il est toujours possible de lister tous les éléments, car le nombre d'éléments de l'ensemble est fini. Si nous numérotons les éléments de l'ensemble 1, 2, et ainsi de suite, jusqu'à , cela nous donne la définition habituelle des "ensembles de taille ".

Certains ensembles sont infinis ; ces ensembles ont plus de éléments où est un entier quelconque qui peut être spécifié. (Quelle que soit la taille de l'entier spécifié , comme , les ensembles infinis ont plus de éléments.) Par exemple, l'ensemble des entiers naturels, dénotable par , a une infinité d'éléments, et nous ne pouvons pas utiliser n'importe quel nombre naturel pour donner sa taille. Il pourrait sembler naturel de diviser les ensembles en différentes classes : mettre tous les ensembles contenant un élément ensemble ; tous les ensembles contenant deux éléments ensemble ; ... ; enfin, mettre tous les ensembles infinis ensemble et les considérer comme ayant la même taille. Cette vision fonctionne bien pour les ensembles dénombrablement infinis et était l'hypothèse dominante avant les travaux de Georg Cantor. Par exemple, il existe une infinité d'entiers impairs, une infinité d'entiers pairs et également une infinité d'entiers au total. Nous pouvons considérer que tous ces ensembles ont la même « taille » car nous pouvons arranger les choses de telle sorte que, pour chaque entier, il existe un entier pair distinct : ou, plus généralement, (voir l'image). Ce que nous avons fait ici est d'arranger les entiers et les entiers pairs dans une correspondance bijective (ou bijection ), qui est une fonction qui mappe entre deux ensembles de telle sorte que chaque élément de chaque ensemble corresponde à un seul élément de l'autre ensemble. Cette notion mathématique de « taille », cardinalité, est que deux ensembles sont de la même taille si et seulement s'il y a une bijection entre eux. Nous appelons tous les ensembles qui sont en correspondance bijective avec les entiers dénombrablement infinis et disons qu'ils ont une cardinalité .

Georg Cantor a montré que tous les ensembles infinis ne sont pas dénombrables. Par exemple, les nombres réels ne peuvent pas être mis en correspondance bijective avec les nombres naturels (entiers non négatifs). L'ensemble des nombres réels a une cardinalité plus grande que l'ensemble des nombres naturels et est dit indénombrable.

Par définition, un ensemble est dénombrable s'il existe une bijection entre et un sous-ensemble des entiers naturels . Par exemple, définissons la correspondance Puisque chaque élément de est associé à exactement un élément de , et vice versa, cela définit une bijection, et montre que est dénombrable. De même, nous pouvons montrer que tous les ensembles finis sont dénombrables.

En ce qui concerne le cas des ensembles infinis, un ensemble est dénombrable infini s'il existe une bijection entre et tous les . À titre d'exemple, considérons les ensembles , l'ensemble des entiers positifs , et , l'ensemble des entiers pairs. Nous pouvons montrer que ces ensembles sont dénombrables infinis en présentant une bijection aux nombres naturels. Cela peut être réalisé en utilisant les affectations et , de sorte que Tout ensemble dénombrable infini est dénombrable, et tout ensemble dénombrable infini est dénombrable infini. De plus, tout sous-ensemble des nombres naturels est dénombrable, et plus généralement :

L'ensemble de toutes les paires ordonnées de nombres naturels (le produit cartésien de deux ensembles de nombres naturels) est dénombrablement infini, comme on peut le voir en suivant un chemin comme celui de l'image :

Le mappage résultant se déroule comme suit :

Cette forme de mappage triangulaire généralise de manière récursive les -uplets de nombres naturels, c'est-à-dire où et sont des nombres naturels, en mappant de manière répétée les deux premiers éléments d'un -uplet à un nombre naturel. Par exemple, peut s'écrire comme . Puis correspond à 5 donc correspond à , puis correspond à 39. Puisqu'un 2-uplet différent, c'est-à-dire une paire telle que , correspond à un nombre naturel différent, une différence entre deux n-uplets par un seul élément suffit à garantir que les n-uplets soient mappés à des nombres naturels différents. Ainsi, une injection de l'ensemble des -uplets à l'ensemble des nombres naturels est prouvée. Pour l'ensemble des -uplets constitué par le produit cartésien d'un nombre fini d'ensembles différents, chaque élément de chaque tuple a la correspondance avec un nombre naturel, donc chaque tuple peut être écrit en nombres naturels puis la même logique est appliquée pour prouver le théorème.

L'ensemble de tous les entiers et l'ensemble de tous les nombres rationnels peuvent intuitivement sembler beaucoup plus grands que . Mais les apparences peuvent être trompeuses. Si une paire est traitée comme le numérateur et le dénominateur d'une fraction vulgaire (une fraction sous la forme de où et sont des entiers), alors pour chaque fraction positive, nous pouvons trouver un nombre naturel distinct qui lui correspond. Cette représentation inclut également les nombres naturels, puisque chaque nombre naturel est aussi une fraction . Nous pouvons donc en conclure qu'il existe exactement autant de nombres rationnels positifs qu'il existe d'entiers positifs. Cela est également vrai pour tous les nombres rationnels, comme on peut le voir ci-dessous.

De la même manière, l’ensemble des nombres algébriques est dénombrable.

Parfois, plusieurs mappages sont utiles : un ensemble à montrer comme dénombrable est mappé biunivoque (injection) vers un autre ensemble , puis est prouvé comme dénombrable si est mappé biunivoque vers l'ensemble des nombres naturels. Par exemple, l'ensemble des nombres rationnels positifs peut facilement être mappé biunivoque vers l'ensemble des paires de nombres naturels (2-uplets) car est mappé vers . Puisque l'ensemble des paires de nombres naturels est mappé biunivoque (en fait, correspondance biunivoque ou bijection) vers l'ensemble des nombres naturels comme indiqué ci-dessus, l'ensemble des nombres rationnels positifs est prouvé comme dénombrable.

Sachant qu'il existe d'innombrables ensembles, on peut se demander si ce dernier résultat peut être poussé plus loin. La réponse est « oui » et « non », on peut l'étendre, mais il faut pour cela supposer un nouvel axiome.

Par exemple, étant donné des ensembles dénombrables , nous attribuons d'abord à chaque élément de chaque ensemble un tuple, puis nous attribuons à chaque tuple un index en utilisant une variante de l'énumération triangulaire que nous avons vue ci-dessus :

Nous avons besoin de l’ axiome du choix dénombrable pour indexer tous les ensembles simultanément.

Cet ensemble est la réunion des suites de longueur 1, des suites de longueur 2, des suites de longueur 3, chacune étant un ensemble dénombrable (produit cartésien fini). On parle donc d'une réunion dénombrable d'ensembles dénombrables, qui est dénombrable par le théorème précédent.

Les éléments de tout sous-ensemble fini peuvent être ordonnés en une suite finie. Il n'existe qu'un nombre dénombrable de suites finies, donc il n'existe qu'un nombre dénombrable de sous-ensembles finis.

Ceux-ci découlent des définitions de l'ensemble dénombrable en tant que fonctions injectives/surjectives.

Le théorème de Cantor affirme que siest un ensemble etest son ensemble de puissance , c'est-à-dire l'ensemble de tous les sous-ensembles de, alors il n'existe pas de fonction surjective deà. Une preuve est donnée dans l'article Théorème de Cantor . Comme conséquence immédiate de cela et du théorème de base ci-dessus, nous avons :

Pour une élaboration de ce résultat, voir l'argument diagonal de Cantor .

L'ensemble des nombres réels est indénombrable, et il en est de même pour l'ensemble de toutes les suites infinies de nombres naturels.

S'il existe un ensemble qui est un modèle standard (voir modèle interne ) de la théorie des ensembles ZFC, alors il existe un modèle standard minimal (voir Univers constructible ). Le théorème de Löwenheim–Skolem peut être utilisé pour montrer que ce modèle minimal est dénombrable. Le fait que la notion de « non-dénombrabilité » ait un sens même dans ce modèle, et en particulier que ce modèle M contienne des éléments qui sont :

• sous-ensembles de M , donc dénombrables,
• mais indénombrable du point de vue de M ,

était considéré comme paradoxal aux débuts de la théorie des ensembles ; voir le paradoxe de Skolem pour en savoir plus.

Le modèle standard minimal inclut tous les nombres algébriques et tous les nombres transcendants effectivement calculables , ainsi que de nombreux autres types de nombres.

Les ensembles dénombrables peuvent être totalement ordonnés de diverses manières, par exemple :

• Ordres de puits (voir aussi nombre ordinal ) :
  • L'ordre habituel des nombres naturels (0, 1, 2, 3, 4, 5, ...)
  • Les entiers dans l'ordre (0, 1, 2, 3, ...; −1, −2, −3, ...)
• Autres ( pas bien ordonnés) :
  • L'ordre habituel des entiers (..., −3, −2, −1, 0, 1, 2, 3, ...)
  • L'ordre habituel des nombres rationnels (Ne peut pas être explicitement écrit sous forme de liste ordonnée !)

Dans les deux exemples d'ordres de puits ici, tout sous-ensemble a un élément minimal ; et dans les deux exemples d'ordres sans puits, certains sous-ensembles n'ont pas d' élément minimal . C'est la définition clé qui détermine si un ordre total est également un ordre de puits.