avatar

L’ensemble des descriptibles.


21-09-2015 10:01 by carado

Aujourd’hui, je vais postuler plusieurs sous-ensembles de $\mathbb{R}$.

Pour ceux qui sont pas au courant, $\mathbb{R}$ est l’ensemble des nombre réels, et il est indénombrable — c’est à dire, entre autres, qu’on ne peut pas assigner un entier raturel ($0;1;2;3;…$) à chaque nombre réel.

Cependant, l’ensemble des séquences de caractères finies ($A;AA;AAA;...;AB;ABA;ABAA;...;B;BA;...$) est dénombrable, et l’ensemble des textes sensés finis en français en est un sous ensemble. Et à nouveau, l’ensemble des descriptions de nombres, c’est à dire l’ensemble des séquences de caractères qui peuvent décrire un nombre (finies mais peuvent être arbitrairement longues), est un sous-ensemble de l’ensemble des textes français.

Du coup, l’ensembles des nombres réels qu’on peut décrire, définir, ou dont on peut parler en général — que j’assigne ici comme $\mathbb{R}_{D}$, réels descriptibles — est dénombrable, et il y a infiniment plus de nombres réels dont on ne pourra jamais parler (du moins avec des médias et langues discrètes et non continues). Ce second ensemble, disjoint de $\mathbb{R}_{D}$, est $\mathbb{R}_{I}$.

$$\mathbb{R}_{D} \uplus \mathbb{R}_{I} = \mathbb{R} $$

Pour être clair — et sachant que $\mathbb{N}$ est l’ensemble des nombres réels et $\#$ l’opérateur qui indique la taille d’un ensemble —, $\aleph_{1} = \#\mathbb{R} = \#\mathbb{R}_{I} > \#\mathbb{N} = \#\mathbb{R}_{D} = \aleph_{0}$.

Autre point intéréssant: posons $\mathbb{R}_{G}$ comme l’ensemble des nombres qui peuvent être générés par un algorithme fini éxécuté pour un temps infini. Par exemple, on peut imaginer que pour générer $\pi$, on peut utiliser un algorithme qui génère les décimales une à une avec une des nombreuses fonctions d’approximation de pi.

À nouveau, comme un algorithme fini est une séquence finie de symboles discrets, $\mathbb{R}_{G}$ est dénombrable.

Je vais non seulement postuler que $\mathbb{R}_{G} \subset \mathbb{R}_{D}$, c’est à dire que tout nombre générable est descriptible (après tout, on peut utiliser « Le nombre généré avec l’algorithme suivant: » suivi de l’algorithme comme description), mais que $\mathbb{R}_{G} = \mathbb{R}_{D}$, c’est à dire que les deux ensembles sont les mêmes.

En somme, avec n’importe quel méthode basée sur des séquences finies de symboles dénombrables, on se retrouve avec un sous-ensemble infiniment plus petit de $\mathbb{R}$, et l’ensemble du reste est « très grand » (indénombrable) mais on ne peut en mentionner de façon usuelle aucun élément, parce que si on pouvait le mentionner, il serait descriptible.

Comment on pourrait décrire un membre de $\mathbb{R}_{I}$ ?

  • Avec un langage à éléments continus; par exemple, si on parle une langue où chaque mot est un réel. De façon générale, si on peut dire une quantité indénombrable de choses différentes en un temps fini
  • Avec des descriptions/algorithmes infinis. C’est pas vraiment compliqué: vu que les réels sont essentiellement des séquences infinies de chiffres, si on mentionne de façon infinie les chiffres un à un, ça marche.

Pas très inspiré, cet article, désolé. Je voulais juste poser les bases d’un peu de dénombrabilité, vu qu’il se peut que j’en reparle plus tard. Notemment, j’aime beaucoup faire ce que j’appelle dénombrer des ensembles: les mettre en bijection soit avec $\mathbb{R}$, soit avec $[n], n \in \mathbb{N}$ — notemment pour avoir une représentation canonique d’objets mathématiques finis. Il se peut que je fasse quelque chose là-dessus en Haskell.

Bonne journée à vous o/