4- Les ensembles et la dénombrabilité

 

  1. Le paradoxe de Russel
  2. La non dénombrabilité de `ccP(NN)`

1) Le paradoxe de Russel

En théorie des ensembles on ne peut pas définire l'ensemble de tous les ensembles à cause du paradoxe de Russel : " L'ensemble de tous les ensembles qui ne se contiennent pas, se contient-il ? ". Quelque soit la réponse à cette question, oui ou non, cela abouti à une contradiction. Ce paradoxe dévoile la nature propositionnelle des ensembles, et s'exprime en relief d'une manière plus pertinente dans la démonstration de Cantor de la non dénombrabilité de `ccP(NN)`, l'ensemble des sous-ensembles de `NN`.

2) La non dénombrabilité de `ccP(NN)`

La démonstration se fait par l'absurde : Si `ccP(NN)` est dénombrable, alors par définition de la dénombrabilité il existe une bijection `f : NN-> ccP(NN)`. On peut alors définir un sous-ensemble `A` de `NN` constitué des éléments x qui n'appartiennent pas à `f(x)`.

`A = {x in NN " / " x !in f(x)}`

`A` est un élément de `ccP(NN)`, considérons son antécédent `a` via `f`. Nous avons `f(a) = A`. Il apparaît alors une contradiction :

Si nous supposons que `a !in f(a)`, cela implique d'après la définition de `A` que `a in A` c'est à dire que `a in f(a)`.

Et si nous supposons que `a in f(a)`, cela implique d'après la définition de `A` que `a !in A` c'est à dire que `a !in f(a)`.

Cantor (George Ferdinand Ludwig Philippe Cantor, 1845 Saint Petersburg - 1918 Allemagne) propose une version de cette démonstration exprimée d'une façon plus géométrique, et démontrant en même temps la non dénombrabilité de l'ensemble des nombres réels : Supposons `ccP(NN)` dénombrable. Soit une suite dénombrable `S =(a_0, a_1, a_2...)` quelconque de sous-ensembles de `NN`, représentées par leur fonction caractéristique, et qui s'apparente au développement "en nombre à virgule" en base deux de nombres réels compris entre `0` et `1` :

Suite `S` :

`a_0 = [a_0(0), a_0(1), a_0(2), a_0(3),..., a_0(n),...]`
`a_1 = [a_1(0), a_1(1), a_1(2), a_1(3),..., a_1(n),...]`
`a_2 = [a_2(0), a_2(1), a_2(2), a_2(3),..., a_2(n),...]`
`a_3 = [a_3(0), a_3(1), a_3(2), a_3(3),..., a_3(n),...]`
...
`a_n = [a_n(0), a_n(1), a_n(2), a_n(3),..., a_n(n),...]`
...

Ici `a_i"(.)"` que l'on note aussi `x |-> a_i(x)`, est la fonction caractéristique de l'ensemble `a_i`
`a_i(k)` vaut `0` ou `1`, et représente l'appartenance de l'entier `k` à l'ensemble `a_i`
`a_i(k)= 0` signifie que `k !in a_i`
`a_i(k)= 1` signifie que `k in a_i`

Construisons un ensemble `b` représenté par sa fonction caractéristique `b = [b(0), b(1), b(2), b(3),..., b(n),...]` par le procédé diagonal de Cantor, plus précisément en posant :

`b(n) = ¬ a_n(n)`

L'opérateur de négation `¬` signifie ici que lorsque `a_n(n)` vaut `1` alors `b(n)` est fixé à `0` et lorsque `a_n(n)` vaut `0` alors `b(n)` est fixé à `1`.

L'ensemble `b` ainsi construit ne peut pas appartenir à la suite `S`. En effet, il diffère de chaque ensemble `a_k` au moins par l'entier `k` puisque `b(k) != a_k(k)`. Si `k` appartient à `b` alors il n'appartient pas à `a_k`, et si `k` n'appartient pas à `b` alors il appartient à `a_k`. Par suite aucun ensemble dénombrable de sous-ensemble de `NN` ne peut épuiser `ccP(NN)`.

"Eléments de la théorie des fonctions et de l'analyse fonctionnelle"
A. Kolmogorov et S.Fomine, Editions Mir. Moscou.

Dans notre approche constructive, nous ne pouvons pas utiliser d'ensemble non dénombrable. Nous verrons en étudiant les fondements de l'informatique qu'il faudra même affiner cette exigence de dénombrabilité en une exigence plus forte encore dite d'énumérabilité. Pour définir nos ensembles constructifs, il est nécessaire de trouver une restriction constructive de `ccP(NN)`, qui conserve toutes ses propriétés constructives. Cela est rendu possible grâce au concept de machine de Turing universelle. (Voir 5- Les fondement de l'informatique, et l'énumérabilité). On considérera l'ensemble des parties calculable de `NN` qui, lui, est dénombrable. Et on le notera de la même façon `ccP(NN)` laissant au contexte le soin de lever l'ambiguité.


Dominique Mabboux-Stromberg
Chapitre suivant : 5- Les fondements de l'informatique, et l'énumérabilité