Ensemble dénombrable - Définition

Quelques exemples d'intervention du dénombrable

Le dénombrable est une notion tellement élémentaire qu'on la retrouve dans à peu près tous les domaines des mathématiques. On préfère par exemple parler de famille (mathématiques) dénombrable plutôt que de suite indexée par les entiers naturels, quand on veut mettre l'accent sur le fait que l'ordre n'est pas important (voir par exemple famille sommable).

Topologie

On remarque que l'ensemble Q des rationnels est un sous-ensemble dénombrable dense de l’ensemble R des réels. Cette propriété se généralise aux Rⁿ, et elle conduit à la notion d'espace séparable. Elle a pour conséquence qu'un intervalle ouvert de R est déterminé par son intersection avec Q. Si cet intervalle est non vide, on montre facilement que cette intersection est infinie dénombrable. Une famille d'intervalles ouverts non vides disjoints deux à deux est donc au plus dénombrable, puisque l'on peut définir une surjection de l'intersection de la réunion de cette famille avec Q, qui est donc dénombrable, dans l'ensemble des intervalles de la famille. On peut montrer que tout ouvert de R est réunion dénombrable d'intervalles ouverts, et une autre propriété de R, celle d'avoir une base dénombrable d'ouverts, les intervalles ouverts dont les bornes sont rationnelles, conduit à la notion d'espace à base dénombrable.

Logique mathématique

En algèbre c'est une banalité de remarquer que par exemple un groupe ayant un nombre fini de générateurs est au plus dénombrable. Par exemple deux réflexions du plan engendrent un groupe fini (groupe diédral) ou infini mais dénombrable, suivant que l'angle entre les deux axes de la réflexion est ou non un multiple rationnel de π.

Tout élément de ce groupe est en fait représenté par une suite finie des générateurs du groupe. C'est un cas particulier d'un phénomène plus général. On a vu que l'ensemble des mots d'un langage fini ou dénombrable est dénombrable. Cette propriété a des conséquences importantes en logique. Il est toujours possible de montrer qu'une théorie du premier ordre exprimée dans un langage fini ou dénombrable (comme l'arithmétique de Peano ou la théorie des ensembles) a un modèle dénombrable. C'est une forme faible du théorème de Löwenheim-Skolem, que l'on déduit directement de la démonstration du théorème de complétude. Dans le cas de la théorie des ensembles c'est ce que l'on a appelé le paradoxe de Skolem, mais c'est une propriété utile, et qui a été utilisée par Paul Cohen pour ses preuves d'indépendance de l'hypothèse du continu et de l'axiome du choix.

Calculabilité

L'informatique ne manipule que le dénombrable. Mais une propriété plus exigeante est utile. Un ensemble est fini ou dénombrable quand il est vide ou l'image d'une fonction définie sur N, donc d'une certaine façon « énumérable » par une fonction définie sur les entiers. Pour qu'un ensemble soit récursivement énumérable on demande que de plus cette fonction soit calculable (au sens calculable par une machine). Il existe des ensembles dénombrables qui ne sont pas récursivement énumérables : si l'ensemble des propositions démontrables d'une théorie est toujours récursivement énumérable (pour les théories récursivement axiomatisables, celles que l'on rencontre habituellement en mathématiques), l'ensemble des propositions qui ne sont pas démontrables ne l'est pas. Ces deux ensembles, qui sont finalement des ensembles de mots sur un alphabet fini (ou dénombrable) sont pourtant tous les deux dénombrables.