Bertrand Russell est un matématicien et philosophe anglais (Trellech, 1872 - près de Penrhyndeudraeth, 1970).
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)`. Où `ccP(NN)` désigne l'ensemble des sous-ensembles de `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 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 :
George Cantor, mathématicien allemand (Saint Petersburg, 1845 - Allemagne, 1918) propose une version de cette démonstration exprimée d'une façon plus géométrique, et qui démontre en même temps la non dénombrabilité de l'ensemble des nombres réels :
Un sous-ensemble `e sube NN` est défini par sa fonction caractéristique, que l'on désigne par le même nom, `e : NN->{0,1}`. Pour tout entier `n in NN`, la valeur de `e(n)` vaut `0` si `n !in e` et vaut `1` si `n in e`. L'application `e : NN->{0,1}` est définie par la suite de booléens suivante qui est également désigné par le même nom :
`e = (e(0), e(1), e(2),..., e(n),...)`
Remarquez que cette suite correspond au développement décimale d'un nombre en base deux compris entre `0` et `1`.
D'une façon plus générale, une application `f : NN->E` est défini par la suite d'élément de `E` suivante, et que nous désignons par le même nom :
`f = (f(0), f(1), f(2),..., f(n),...)`
Si `ccP(NN)` est dénombrable, alors par définition de la dénombrabilité il existe une bijection `f : NN->ccP(NN)`. Cette bijection définie une suite de sous-ensembles que l'on nomme pareillement `f`. Et on décide de noter cette suite d'images de façon indicielle :
`f=(f_0,f_1,f_2,...,f_n,...)`
On va démontrer que `f` ne peut pas couvrir tout `ccP(NN)` ce qui contredira l'hypothèse, en construisant par le procédé de la diagonale de Cantor, à partir de la suite `f`, un sous-ensemble qui n'appartient pas à `f`.
Chaque ensemble `f_n` est aussi une fonction carctéristique et est donc aussi une suite de booléens :
`f_0 = (f_0(0), f_0(1), f_0(2),..., f_0(n),...)`
`f_1 = (f_1(0), f_1(1), f_1(2),..., f_1(n),...)`
`f_2 = (f_2(0), f_2(1), f_2(2),..., f_2(n),...)`
`f_3 = (f_3(0), f_3(1), f_3(2),..., f_3(n),...)`
...
`f_n = [f_n(0), f_n(1), f_n(2),..., f_n(n),...)`
...
Ici `f_i` représente aussi bien un ensemble que sa fonction caractéristique que l'on note par `x |-> f_i(x)`. Quelque soit un entier `k`, l'expression `f_i(k)` vaut `0` ou `1`, et représente l'appartenance de l'entier `k` à l'ensemble `f_i` :
`f_i(k)= 0` signifie que `k !in f_i`
`f_i(k)= 1` signifie que `k in f_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) = ¬ f_n(n)`
L'opérateur de négation `¬` signifie ici que lorsque `f_n(n)` vaut `1` alors `b(n)` est fixé à `0` et lorsque `f_n(n)` vaut `0` alors `b(n)` est fixé à `1`.
L'ensemble `b` ainsi construit ne peut pas appartenir à la suite `f`. En effet, il diffère de chaque ensemble `f_k` au moins par l'entier `k` puisque `b(k) != f_k(k)`. Si `k` appartient à `b` alors il n'appartient pas à `f_k`, et si `k` n'appartient pas à `b` alors il appartient à `f_k`. Par conséquent, aucun ensemble dénombrable `f` de sous-ensemble de `NN` ne peut épuiser `ccP(NN)`.
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, dans certain cas, 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 relatives aux objets calculables.
Cela est rendu possible grâce au concept de machine de Turing universelle vu dans le chapitre suivant. On considérera l'ensemble des parties énumérable de `NN` qui, lui, est dénombrable. Et on le notera de la même façon `ccP(NN)`. Ainsi est créé l'interprétation dite élémentarienne, qui, en gros, se débarasse une fois pour toute de la puissance du continu.