Nous montrerons qu’il y a plus de fonctions de nombres naturels qu’on ne peut en écrire sur une liste infinie.

1Soit N l’ensemble des nombres naturels positifs : 1, 2, 3,... Les fonctions de N dans {0,1} peuvent être représentées par des suites infinies de 0 et de 1 de façon naturelle. Par exemple, la fonction

2f(n) = 1, si n est impair ; f(n) = 0, si n est pair,

3devient la suite

410101010...

5faisant alterner les 1 et les 0. En général, la fonction h est représentée par la suite dont le nième élément est h(n), c’est-à-dire

6h(1) h(2) h(3)... h(n)...

7Nous démontrons maintenant que chaque liste infinie de fonctions de N dans {0,1} est incomplète. Supposons que L est une telle liste de fonctions. Le premier élément de L est une certaine fonction f₁, le second élément est une fonction f₂, et ainsi de suite, c’est-à-dire que pour chaque nombre naturel positif n il y a un même élément sur la liste que nous notons f_n. Il serait commode d’imaginer les fonctions écrites les unes sous les autres : d’abordf1 (représentée par sa suite binaire), puis f₂, et ainsi de suite. Nous avons ainsi une matrice infinie de 0 et de 1, telle que

8(f₁) 0 0 0 1 0 0 1 1 0 0...

9(f₂) 0 1 1 0 1 0 0 0 1 1 0...

10(f₃) 1 1 1 0 1 1 0 0 0 1 0 0...

11...

12(f_n) f_n(1) f_n(2)... fn(n)...

13La diagonale de cette matrice est la suite binaire

14f₁(1) f₂(2) f₃(3) … f_n(n) … (1)

15Soit g la fonction définie, pour chaque n dans N, par

16g(n) = 0, si fn (n) = 1

17g(n) = 1, si fn (n) = 0

18Autrement dit, la suite correspondant à g est obtenue de la suite diagonale (1) par le changement des 1 en 0 et des 0 en 1. Par exemple, en supposant que les trois premières fonctions sur la liste sont telles qu’elles figurent cidessus, la chaîne diagonale commence 0 1 1..., alors g commence 1 0 0...

19Cette fonction g n’est pas sur la liste L. Car, étant donné n’importe quel fm sur L, par la définition de g, nous avons g(m) ≠ fm(m). Puisque g et f_m prennent des valeurs différentes pour un nombre naturel, à savoir m, ils ne peuvent être égaux. La fonction g est, par conséquent, manquante, et la liste donnée est incomplète. À noter qu’il ne donnerait rien d’essayer de retaper la liste originelle en y intégrant g. L’argument ci-dessus s’applique à n’importe quelle liste ; dès lors, la nouvelle liste sera également incomplète—une fonction autre que g sera manquante.

20Les fonctions de N à {0, 1} forment un sous-ensemble propre de toutes les fonctions de N à N. Comme les fonctions dans le plus petit ensemble ne peuvent pas toutes apparaître sur une liste unique, à fortiori aucune liste complète de celles du plus grand ensemble ne saurait non plus exister.