Notion d'ensemble dénombrable

Définition

On dit qu'un ensemble E est dénombrable (countable en anglais) s'il existe une bijection entre l'ensemble N des entiers naturels et E. Rappelons qu'une bijection entre deux ensembles E et F est une fonction de E dans F telle que deux éléments distincts x et x' ont des images f(x) et f(x') distinctes (f(x) ≠ f(x')) et telle que tout élément y de F est l'image d'un élément x de E (y = f(x)).

Une fonction f de N dans un ensemble E associe a tout entier k un élement f(k) de E que l'on note x_k. La fonction f est bijective si les conditions suivantes sont remplies.

1. elle est injective, c'est-à-dire, x_j ≠ x_k pour tout i ≠ k,
2. elle est surjective, c'est-à-dire que E est égal à { x₀, x₁, x₂, ... } = { x_k | k ≥ 0 }

Exemples

Voici quelques exemples d'ensembles dénombrables

• L'ensemble N des entiers est bien sûr dénombrable.
• L'ensemble Z des entiers relatifs est aussi dénombrable. On pose x_2k = k et x_2k+1 = -k-1 pour tout entier k ≥ 0. Ceci donne l'énumération suivante 0,-1,1,-2,2,-3,3, ... de tous les entiers relatifs
• L'ensemble N × N, des couples (i,j) d'entiers est également dénombrable. Pour le montrer, il faut donner une suite x₀, x₁, x₂, ... de couples distincts qui parcourent tout l'ensemble N × N. L'idée générale est de parcourir les couples (i,j) par tranche de somme i+j. Le premier couple x₀ est le seul couple (i,j) telle que i+j = 0, c'est-à-dire x₀ = (0,0). Ensuite x₁ et x₂ sont les deux couples (i,j) telle que i+j = 1. On a x₁ = (0,1) et x₂ = (1,0). Ensuite on pose x₃ = (0,2), x₄ = (1,1) et x₅ = (2,0) et ainsi de suite.

  x9	...
  x5	x8	...
  x2	x4	x7	...
  x0	x1	x3	x6	...

• De la même façon, on montre que l'ensemble A^* des mots finis écrits sur un alphabet fini est dénombrable. On énumére les mots par longueur croissante. Si par exemple A = {a, b}, on a

  k	0	1	2	3	4	5	6	7	8	...
  xk	ε	a	b	aa	ab	ba	bb	aaa	aab	...

• On rappelle que tout nombre rationnel s'écrit p/q où p et q sont des entiers. Par contre cette écriture n'est pas unique. Pour énumérer tous les éléments de Q, on reprend l'énumération de N × N mais à chaque fois que l'on retrouve un rationnel déjà rencontré, on le saute.

Propriétés

Voici quelques propriétés des ensembles dénombrables

• Si E est inclus dans F et si F est dénombrable, alors E est fini ou dénombrable
• Si E et F sont dénombrables, alors l'union E ∪ F et le produit cartésien E × F sont deux ensembles dénombrables.
• Si chacun des ensembles E_i est dénombrable pour i ≥ 0, alors l'union des ensembles E_i est également dénombrable.

Un ensemble non dénombrable

Nous allons montrer que l'ensemble des suites infinies de 0 et de 1 n'est pas dénombrable. Soit S l'ensemble {(d_i)_{i ≥ 0} | d_i ∈ {0, 1} } des suites à valeurs dans {0, 1}. Nous allons montrer que S n'est pas dénombrable. On utilise un raisonnement par l'absurde. On suppose qu'il est dénombrable et on montre qu'on aboutit à une contradiction. Supposons qu'il existe une suite s₀, s₁, s₂, ... qui parcours tous les éléments de S. Chaque élément s de S s'écrit s = d₀, d₁, d₂, ... où les d_j sont des éléemnts de {0, 1}. Soit s_k = d_k,0, d_k,1, d_k,2... la k-ième suite s_k. On définit alors une suite d₀, d₁, d₂ ... de la manière suivante. Pour tout entier k ≥ 0, on pose

• d_k = 1 si d_k,k = 0,
• d_k = 0 sinon (c.-à-d. d_k,k = 1),

de sorte que d_k appartient à {0,1} et que d_k ≠ d_k,k pour tout k ≥ 0. On définit alors la suite s = d₀, d₁, d₂... où les d_k sont ceux qui viennent d'être définis. Montrons que s est différent de chacun des s_k. En effet chaque suite s_k diffère de s en la k-ième position par définition des d_k.Ceci est une contradiction puisqu'on avait supposé que la suite s₀, s₁, s₂, ... parcourrait tout les éléments de S alors qu'on vient justement de trouver une suite s qui est différents de tous les s_k.

Un ensemble E de mots peut être représenté par sa fonction caractéristique qui associe à chaque mot w la valeur 1 si w appartient à E et 0 sinon. En ordonnant les mots par longueur puis par ordre lexicographique pour une longueur fixée, cette fonction caractéristique peut être vue comme une suite à valeurs dans {0, 1}. Du coup, il s'ensuit que l'ensemble des langages n'est pas dénombrable.

Application à l'obtention d'un langage non récursivement énumérable

Nous allons utiliser le résultat précédent pour montrer qu'il existe des ensembles qui ne sont pas récursivement énumérables. Tout ensemble récursivement énumérables est donné par une machine de Turing. Comme chaque machine de Turing peut être codé par un mot fini sur un alphabet fixe, l'ensemble des machines de Turing est dénombrable. Il s'ensuit que l'ensemble des langages récursivement énumérables est aussi dénombrable. Par contre, l'ensemble de tous les langages n'est pas dénombrable. Il en découle que tous les langages ne sont pas récursivement énumérables. En fait il existe beaucoup plus de langages non récursivement énumérables que de langages récursivement énumérables.