Le Paradoxe de Richard (1905)
Le Paradoxe de Jules Richard est un exemple remarquable de paradoxe causé par une hypothèse erronée. Comme celui-ci est un peu compliqué et d'énoncé complexe, nous nous limiterons à en donner une version simplifiée considérant des fonctions arithmétiques à une place au lieu de fonctions réelles.
Une phrase est définie comme une suite finie de termes (un blanc ou 26 lettres de l'alphabet) telle qu'un blanc ne soit ni en position initiale ni en position finale.
Se donner une définition, c'est se permettre d'énumérer les dites phrases par la méthode des digits, c'est-à-dire de représenter les entiers dans un système numéral à 27 ou 28 digits.
Ainsi, certaines phrases — par exemple "le carré de a" — décrivent en français des fonctions arithmétiques à une place. Rayons dans notre énumération de toutes les phrases toutes celles qui ne décrivent pas des fonctions de ce genre. On obtient alors une énumération P0, P1, P2, ... des phrases qui décrivent de telles fonctions. Notons alors les fonctions décrites respectivement f0(a), f1(a), f2(a), ...
Considérons la phrase : « La fonction dont la valeur pour chaque nombre naturel a est obtenue en ajoutant une unité à la valeur pour a de la fonction décrite par la phrase correspondant à a [dans notre énumération des phrases qui décrivent des fonctions arithmétiques à une place.] »
Dans cette phrase, nous pouvons remplacer la dernière partie entre crochets par une description détaillée de la construction exacte de l'énumération. Le tout conduite ainsi à une phrase P décrivant complètement la même fonction.
Cette phrase P décrit une fonction arithmétique, à savoir :
f(a) = fa(a) + 1
Or toute phrase décrivant une fonction arithmétique figure dans P0, P1, P2, ..., aussi en est-il de P.
Mais c'est impossible car :
⇒ ∀a, ∀k, Pk décrit fk(a) et ∀a, P décrit f(a) = fa(a) + 1.
⇒ ∀a = k, Pa décrit fa(a) et P décrit fa(a) + 1
⇒ ∀a = k, Pa ≠ P ⇒ Pa ≠ P
⇒ P ∉ {P0, P1, P2, ...}
La contradiction est causée par des hypothèses sous-jacentes erronées. En effet, alors que seule une infinité dénombrable de fonctions arithmétiques peut être décrite dans un langage donné — puisque l'ensemble de toutes les phrases constructibles dans ce langage est au plus infini dénombrable — on démontre par raisonnement diagonal que l'ensemble des fonctions arithmétiques n'est pas dénombrable.