Logique, arithmétique de Peano et incomplétude

26 mars 2023 — Logique, Incomplétude, Gödel

Le but de cet article est d’introduire, à l’aide de quelques exemples de théories arithmétiques, la notion d’incomplétude en logique (du premier ordre).

Nous évoquerons aussi le (premier) théorème d’incomplétude de Gödel, que nous tâcherons d’éclairer par différents exemples d’application et de non-application.

Les définitions seront informelles et nous donnerons peu de preuves — pour un cours d’introduction à la logique, vous pouvez par exemple consulter le livre de Jacques Patarin.

Formule logique (du premier ordre)

La logique du premier ordre s’intéresse à des formules construites en utilisant les différents symboles :

• $\land$ (conjonction), $\lor$ (disjonction), $\lnot$ (négation), $\implies$ (implication)
• des symboles de variables comme $x$, $y$, $z$, …
• les quantificateurs $\forall$ (universel) et $\exists$ (existentiel)
• le symbole $=$ (égalité)

En fonction de la théorie étudiée, les formules pourront également comporter des symboles non logiques :

• des symboles de fonctions, comme $+$, $\times$
• des symboles de constantes, comme $0$ ou $1$

Par exemple, ${\forall x (x = 0 \lor \exists y (x = y + y))}$ est une formule de la logique du premier ordre d’une théorie dont le langage comporte les symboles $0$ et $+$.

Dans cette formule, $\forall$ et $\exists$ quantifient respectivement les variables $x$ et $y$.

Les quantificateurs servent à lier les variables et une formule sans variable libre (non liée) est appelée un énoncé.

Règles de déduction

Les règles d’inférence permettent de construire des formules vraies à partir d’autres formules. Nous considérerons ici les règles de la logique classique.

En particulier, si $P$ est une formule quelconque, les formule ${P \lor \lnot P}$ (principe du tiers-exclu) et ${\lnot \lnot P \implies P}$ (reductio ad absurdum) sont vraies (d’autres logiques existent).

Arithmétique de Robinson

L’arithmétique de Robinson est une théorie qui introduit

• un symbole de constante $0$
• des symboles de fonction $S$ (successeur), $+$ et $\times$

Et qui pose les axiomes (énoncés de la logique du premier ordre que l’on décrète vrais) suivants :

1. $\forall x (\lnot S(x) = 0)$
2. $\forall x \forall y (S(x) = S(y) \implies x = y)$
3. $\forall y (y = 0 \lor \exist x (S(x) = y))$
4. $\forall x (x + 0 = x)$
5. $\forall x \forall y (x + S(y) = S(x + y))$
6. $\forall x (x \times 0 = 0)$
7. $\forall x \forall y (x \times S(y) = (x \times y) + x)$

Exercice : Démontrer ${S(0) + S(0) = S(S(0))}$ dans l’arithmétique de Robinson.

La formule ${\forall x \exists y (x = y + y) \lor (x = y + y + S(0))}$, que l’on notera $\Phi$, est un autre énoncé de l’arithmétique de Robinson.

Nous allons montrer que $\Phi$ et $\lnot \Phi$ sont deux énoncés indémontrables de l’arithmétique de Robinson.

L’existence d’un tel énoncé (indémontrable et dont la négation est indémontrable) signifie que la théorie est incomplète.

Notion de modèle

Un modèle de l’arithmétique de Robinson est une structure $(E, S, +, \times, 0)$ telle que :

• $E$ est un ensemble
• $S$, $+$, $\times$ sont des fonctions bien définies sur $E$
• $0$ une constante de $E$
• les axiomes 1 à 7, interprétés dans cette structure, sont vrais

$\N$ muni de ses opérations usuelles est un modèle de l’arithmétique de Robinson dans lequel $\Phi$ est vraie : tout nombre entier est pair ou impair.

Comme c’est généralement $\N$ que l’on a en tête lorsque l’on définit une théorie de l’arithmétique, on dira que $\N$ est le modèle standard de cette théorie.

Si $\lnot \Phi$ était un théorème de l’arithmétique de Robinson, $\Phi$ ne serait pas vraie dans $\N$.

Ainsi : $\lnot \Phi$ n’est pas démontrable dans l’arithmétique de Robinson.

Un modèle non standard

Considérons l’ensemble $E$ des polynômes $P$ à coefficients entiers dont le coefficient dominant est positif ou nul.

• $0$ désigne le polynôme nul
• L’addition et la multiplication sont celles des polynômes
• $S$ est définie par $S(P) = P + 1$

Je vous laisse vérifier les affirmations suivantes :

• La structure $(E, S, +, \times, 0)$ ainsi définie est un modèle (non standard) de l’arithmétique de Robinson. En particulier, une fois interprétés dans cette structure, les axiomes 1 à 7 sont vrais.
• L’énoncé $\Phi$ est faux dans ce modèle (indice : considérer le cas du polynôme $X$).

$\Phi$ étant faux dans ce modèle, il ne peut être un théorème de l’arithmétique de Robinson.

Ces deux résultats nous permettent d’affirmer que l’arithmétique de Robinson est incomplète.

Cet exemple est inspiré d’une réponse sur math.stackexchange.com.

Arithmétique de Peano

L’arithmétique de Peano s’obtient en enrichissant l’arithmétique de Robinson d’un schéma d’axiomes, qui formalisent le raisonnement par récurrence.

Pour toute formule $\varphi(x)$ à une variable libre $x$, on ajoute l’axiome $8_{\varphi}$ suivant :

$(\varphi(0) \land \forall x (\varphi(x) \implies \varphi(x+1))) \implies \forall x \varphi(x)$

💡 Notons que ces axiomes $8_{\varphi}$ sont énumérables par un algorithme. Par ailleurs, ce schéma d’axiomes est parfois présenté sous une forme légèrement différente (notamment sur Wikipedia). Ces deux formulations sont équivalentes.

Nous n’avons pas vraiment défini ce que sont les entiers naturels, j’affirme donc sans justification particulière qu’ils vérifient les axiomes $8_{\varphi}$ et donc que $\N$ est un modèle de l’arithmétique de Peano (là encore, le modèle standard).

En particulier, $\lnot \Phi$ n’est (toujours) pas démontrable dans l’arithmétique de Peano.

En revanche, et je vous laisse en construire une preuve, $\Phi$ est un théorème de l’arithmétique de Peano (indice : utiliser l’axiome $8_{\varphi}$ correspondant à la formule ${\varphi(x): \exists y (x = y + y) \lor (x = y + y + S(0))}$).

Cela n’indique pas pour autant que l’arithmétique de Peano soit complète et d’ailleurs, comme nous allons le voir, elle ne l’est pas…

Le théorème de Goodstein

Pour tout entier $m \geq 0$, la séquence de Goodstein de graine $m$ consiste en la suite $(G(m, n))_{n \geq 0}$ définie par $G(m, 0) = m$ et la relation de récurrence suivante :

• Si $G(m, n) = 0$, alors $G(m, n+1) = 0$
• Sinon :
  • on écrit la représentation héréditaire en base $2 + n$ de $G(m, n)$
  • on remplace les occurrences de $2 + n$ par $3 + n$
  • on soustrait $1$
  • le nombre obtenu est $G(m, n+1)$

Voici un programme en Python qui calcule cette séquence et en voici ci-dessous des exemples pour certaines graines.

Pour $m = 3$, la séquence atteint $0$ en $5$ itérations :

Pour $m = 7$, la croissance est extrêmement rapide :

Considérons l’énoncé $\Gamma: \forall m \exists n G(m,n) = 0$. Il signifie que toutes les séquences de Goodstein atteignent $0$ en un nombre fini d’itérations.

Nous allons ci-dessous énoncer trois affirmations à propos de $\Gamma$. Ces affirmations sont non triviales, nous en donnerons au mieux une ébauche de justification.

(a) $\Gamma$ est un énoncé de l’arithmétique de Peano

Ceci n’a a priori rien d’évident car la formule $G(m,n) = 0$ n’est pas écrite dans le langage de l’arithmétique de Peano, qui ne connait pas le symbole $G$.

Néanmoins, on pourrait — mais ce serait très fastidieux — la réécrire comme une formule à deux variables libres utilisant les symboles $0, S, +, \times, \forall, \exists, \lnot, \lor, \land, =$.

💡 En fait, pour toute fonction $f$ pouvant être calculée par un algorithme (ce qui est le cas de $G$), les formules comme $f(x) = y$ peuvent se réécrire dans le langage de l’arithmétique de Peano.

(b) $\Gamma$ est vrai dans le modèle standard

Le modèle standard de l’arithmétique est $\N$, mais qu’est-ce que $\N$ ?

Pour le définir, il faut faire appel à la théorie des ensembles, une théorie de la logique du premier ordre dont le langage comporte en particulier la constante $\emptyset$ et la relation $\in$.

Cette théorie permet de construire un ensemble noté $\N$.

Elle permet aussi de construire d’autres objets et notamment les nombres ordinaux.

En particulier, on peut définir un ordinal $\omega$, des opérations (addition, multiplication et exponentiation) et une relation d’ordre sur les ordinaux tels que l’inégalité suivante ait un sens :

(J’ai ici réécrit la séquence des représentations héréditaires en base $b$ des $(G(7,n))_{0 \leq n \leq 6}$ en remplaçant les lettres $b$ par des $\omega$.)

En généralisant cette observation, on montre que si la suite $(G(m, n))_n$ n’est pas nulle à partir d’un certain rang, on peut lui faire correspondre une suite strictement décroissante d’ordinaux, ce qui est impossible — tout ensemble d’ordinaux admet un plus petit élément.

On en déduit que $\Gamma$ est vrai dans $\N$ : c’est le théorème de Goodstein.

💡 L’addition et la multiplication des ordinaux ne sont pas commutatives, par exemple $7 \times ω^{7} = ω^{7} \neq ω^{7} \times 7$ dans la somme développée plus haut.
Cette entrée du blog de David Madore permet d’appréhender la notion d’ordinal et les opérations sur ceux-ci — on pourra voir également ici pour un cours sur le sujet.

(c) $\Gamma$ n’est pas démontrable dans l’arithmétique de Peano

La preuve décrite ci-dessus du théorème de Goodstein sur les entiers naturels fait appel à d’autres constructions de la théorie des ensembles, à savoir les ordinaux (jusqu’à $\varepsilon_0$).

En 1982, il a été montré par les mathématiciens Kirby et Paris que l’énoncé de Goodstein n’est pas démontrable dans l’arithmétique de Peano (cet article en dit un peu plus à ce sujet).

💡 On peut en déduire qu’il existe un modèle non standard de l’arithmétique de Peano dans lequel l’énoncé de Goodstein est faux. Un tel modèle est cependant difficile à expliciter et je ne développerai pas cet aspect ici.

L’arithmétique de Peano est incomplète.

C’est une conséquence des points (a) + (b) + (c) ci-dessus.

Ceci étant, ce n’est pas la façon la plus directe d’arriver à ce résultat, ni la façon dont il fut prouvé historiquement.

En 1931, Gödel a en effet démontré un résultat concernant les théories du premier ordre qui contiennent l’arithmétique de Peano. Ce résultat fut amélioré par Rosser en 1936 et peut s’énoncer ainsi :

Théorème d’incomplétude de Gödel-Rosser

Si une théorie $T$ (de la logique du premier ordre) vérifie :

1. les axiomes de $T$ sont énumérables par un algorithme
2. $T$ permet de formaliser l’arithmétique de Peano
3. $T$ est cohérente (elle ne prouve jamais un énoncé et sa négation)

Alors $T$ est incomplète.

De façon très informelle, la démonstration consiste à construire un énoncé $G$ de la théorie qui dit « Je ne suis pas démontrable. ». Un tel énoncé est formulable dans une théorie qui vérifie les deux premières hypothèses ci-dessus. Une preuve de $G$ ou de $\lnot G$ ne peut alors exister sans rendre la théorie incohérente.

Je termine cet article en donnant un exemple de non application de ce théorème, qui illustre l’importance des hypothèses.

Complétude de l’arithmétique de Presburger

L’arithmétique de Presburger est la théorie obtenue en retirant à l’arithmétique de Peano le symbole $\times$ : on conserve donc uniquement les axiomes 1 à 5 et les axiomes $8_{\varphi}$ du schéma de récurrence où $\varphi$ n’utilise pas ce symbole.

L’arithmétique de Presburger vérifie les conditions 1 et 3 du théorème d’incomplétude, mais pas la condition 2.

L’arithmétique de Presburger est complète : elle permet de démontrer $P$ ou $\lnot P$ pour tout énoncé $P$ qu’elle est capable d’exprimer.

💡 Cette théorie a en fait une expressivité beaucoup plus faible que l’arithmétique de Peano. L’ajout de la multiplication permet par exemple (notamment grâce à la fonction $\beta$ de Gödel), d’exprimer arithmétiquement les formules faisant intervenir des fonctions calculables par un algorithme — nous l’avons mentionné dans le point (a) à propos du théorème de Goodstein. Ce n’est pas possible dans l’arithmétique de Presburger.

Maths et applications, avec les mains et avec du code 💻
Suivre sur Twitter

• ← Compression JPEG et composantes principales
• Autour des harmoniques sphériques →