Paradoxes

Le paradoxe du Barbier

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

Le conseil municipal d'un village vote un arrêté municipal qui enjoint à son barbier de raser tous les habitants du village qui ne se rasent pas eux-mêmes et seulement ceux-ci.

Qui va raser le barbier ?

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…

On réalise qu'on ne peut pas écrire ce que l'on veut, on ne peut pas définir un ensemble en toute liberté. Un premier garde-fou est de n'autoriser que les élément d'un ensemble bien défini. Ainsi on pourra noter $\{x\in\mathbb{R}, x^2 < 4\}$ car les $x$ sont choisis dans un ensemble bien défini, ici $\mathbb{R}$.

Construction axiomatique

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.

Le tiers-exclus est le principe selon lequel une assertion est soit vraie, soit fausse mais pas les deux et pas autre chose. Dans le paradoxe de Russel, $N \in N$ n'est ni vrai ni faux…

Quand il s'agit d'infinis, il arrive qu'au lieu de démontrer qu'une propriété $P$ est vraie, on démontre que $P$ ne peut être fausse (raisonnement par l'absurde). Mais dans le cas du paradoxe de Russel, prouver que $N \in N$ ne peut être faux ne permet pas de conclure que $N \in N$ est vrai…

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.

Axiomes de Peano

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

Écriture formelle

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.

Conjecture de Goldbach

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 ?

Paradoxe de Richard

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.

$n$	$p_n(n)$	$p_n(n)$
1	$n$ est divisible par 2	Faux
2	$n$ est premier	Vrai
3	$n$ est un carré	Faux
…	…	…
$N$	$n$ n'est pas richardien	…

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

Le nombre $N$ est-il richardien ?

Comme dans le paradoxe de Russel, on retrouve une idée d'autoréférence. C'est au moment où l'énoncé porte sur lui-même que l'on rencontre des problèmes.

Le paradoxe de Richard est plus subtile et nécessite plus de précautions.

Problème méta

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é.