Bertrand Russel, grand logicien du début XXe siècle, propose le paradoxe suivant :

La version mathématique du paradoxe s'écrit : $$N = \{x\,ensemble,\quad x\not\in x\}$$

Soit l'ensemble des ensembles qui ne se contiennent pas eux-mêmes.

$N$ est-il contenu dans $N$ ? La réponse est ni oui, ni non…

Les paradoxes comme celui de Russell conduisent à chercher un langage plus rigoureux qui empêcherait de les énoncer.

C'est la crise des fondements des mathématiques. Certains en sont arrivés à rejeter le principe du tiers-exclus.

David Hilbert propose d'adopter une approche axiomatique :

• On pose des vérités premières, les axiomes.
• Les démonstrations sont des enchaînements déductifs finis construits à partir des axiomes.
• Ainsi, on ne va pas se demander si une propriété est vraie, mais si elle est démontrable.

Pour définir l'ensemble des entiers naturels $\mathbb{N}$, Giuseppe Peano propose les axiomes suivants :

• dans $\mathbb{N}$, il existe un élément, noté $0$ ;
• tout élément $n$ de $\mathbb{N}$ admet un successeur noté $s(n)$, élément de $\mathbb{N}$ ;
• aucun élément de $\mathbb{N}$ n'a $0$ pour successeur ;
• deux entiers naturels ayant le même successeur sont égaux ;
• si un ensemble d'entiers naturels contient $0$ et le successeur de chacun de ses éléments, alors c'est ensemble est $\mathbb{N}$ – il s'agit du raisonnement par récurrence

Boole énonce les règles de logiques formelles. On sait alors comment articuler des propriétés pour former de nouvelles propriétés. On peut aussi reformuler les énoncés dans un langage non ambigu.

Dans ce nouveau langage, les axiomes de Peano prennent la forme :

• $0 \in \mathbb{N}$ ;
• $\forall x, x=0 \vee \exists y (x=s(y))$
• $\forall x \forall y, (sx = sy \Rightarrow x=y)$
• …

Une démonstration devra donc être une articulation de ces axiomes, utilisant les règles de l'algèbre de Boole, d'une longueur finie.

Le nouvel enjeu, dans cette approche axiomatique finitiste, est de démontrer des propriétés. Si on peut démontrer une propriété, c'est qu'elle est vraie. Mais pourrait-elle être vraie sans qu'on puisse la démontrer ?

Goldbach propose la conjecture (c'est à dire : on pense que c'est vrai mais on ne l'a pas encore démontré) suivante : Tout nombre paire supérieur à 2 est la somme de deux nombres premiers.

Par exemple : $10\,708 = 4\,967 + 5\,741$

On a vérifié que c'est vrai jusqu'à $4\cdot 10^{18}$ mais on ne l'a pas démontré.

Se pourrait-il que la conjecture soit toujours vraie mais qu'il soit impossible de le démontrer ?

Jules Richard, professeur de mathématiques dans un lycée de Dijon, propose un paradoxe : Supposons que je construises une liste numérotées de prédicats, c'est à dire des fonctions $p(n)$ qui renvoient Vrai ou Faux selon la valeur de $n$.

Par exemple $p_1(n) =$ « est divisible par 2 ». On peut dire alors que $p_1(1)$ est faux, mais $p_1(2)$ est vrai.

Ce qui nous intéresse est de savoir si $p_n{n}$ est vrai. On dit que $n$ est richardien si $p_n(n)$ est vrai.

Dans cette liste, 1 et 3 ne sont pas richardien. Mais 2 l'est.

Le nombre $N$ est-il richardien ?

Le paradoxe de Richard repose sur le fait qu'il faut d'abord construire la grille pour définir ce que c'est que d'être richardien.

Les propriétés « normales » dans la grille sont des propriétés portant sur les nombre. La propriété d'être richardien porte sur la grille. C'est une propriété d'un niveau différent, c'est une propriété sur les propriété, c'est une méta-propriété.

Alors que l'on refonde les mathématiques sur des bases axiomatiques, par exemple pour l'ensemble $\mathbb{N}$ qui est fondamental, on se pose les deux questions :

• est-on certains que les axiomes n'aboutissent pas à une contradiction (cohérence)
• peut-on démontrer toute propriété vraie (complétude)

Gödel va prouver que si c'est cohérent, alors c'est incomplet. Et la cohérence est justement une chose que l'on ne peut démontrer !

Pour arriver à ses fins, Gödel invente un codage :

Prenons une expression logique comme $(\exists x)(x = sy)$. On transforme l'expression en écrivant :

$$2^8 \times 3^4 \times 5^{11} \times 7 ^9 \times 11^8 \times 13^{11} \times 17^5 \times 19^7 \times 23^{13} \times 29^9$$

ce qui donne $38685626227668133590597632$

L'important ici n'est pas le résultat. L'important est que toute expression logique intervenant dans une propriété ou une démonstration peut être transformée en un nombre, de façon univoque.

Remarque : tout entier ne correspond pas à une expression. Seuls certains entiers codent une expression.

Par conséquent,

• soit $G$ est vrai et alors on a trouvé une propriété vraie qui n'est pas démontrable. $\mathbb{N}$ est incomplet.
• soit $G$ est faux et alors, donc $G$ est démontrable et on peut démontrer le faux, donc $\mathbb{N}$ est incohérent.