Lipsum.dev

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 xx, yy, zz, …
  • 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 00 ou 11

Par exemple, x(x=0y(x=y+y)){\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 00 et ++.

Dans cette formule, \forall et \exists quantifient respectivement les variables xx et yy.

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 PP est une formule quelconque, les formule P¬P{P \lor \lnot P} (principe du tiers-exclu) et ¬¬P    P{\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 00
  • des symboles de fonction SS (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. x(¬S(x)=0)\forall x (\lnot S(x) = 0)
  2. xy(S(x)=S(y)    x=y)\forall x \forall y (S(x) = S(y) \implies x = y)
  3. y(y=0x(S(x)=y))\forall y (y = 0 \lor \exist x (S(x) = y))
  4. x(x+0=x)\forall x (x + 0 = x)
  5. xy(x+S(y)=S(x+y))\forall x \forall y (x + S(y) = S(x + y))
  6. x(x×0=0)\forall x (x \times 0 = 0)
  7. xy(x×S(y)=(x×y)+x)\forall x \forall y (x \times S(y) = (x \times y) + x)

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

La formule xy(x=y+y)(x=y+y+S(0)){\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,+,×,0)(E, S, +, \times, 0) telle que :

  • EE est un ensemble
  • SS, ++, ×\times sont des fonctions bien définies sur EE
  • 00 une constante de EE
  • les axiomes 1 à 7, interprétés dans cette structure, sont vrais

N\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\N que l’on a en tête lorsque l’on définit une théorie de l’arithmétique, on dira que N\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\N.

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

Un modèle non standard

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

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

Je vous laisse vérifier les affirmations suivantes :

  • La structure (E,S,+,×,0)(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 XX).

Φ\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 φ(x)\varphi(x) à une variable libre xx, on ajoute l’axiome 8φ8_{\varphi} suivant :

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

💡 Notons que ces axiomes 8φ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φ8_{\varphi} et donc que N\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φ8_{\varphi} correspondant à la formule φ(x):y(x=y+y)(x=y+y+S(0)){\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 m0m \geq 0, la séquence de Goodstein de graine mm consiste en la suite (G(m,n))n0(G(m, n))_{n \geq 0} définie par G(m,0)=mG(m, 0) = m et la relation de récurrence suivante :

  • Si G(m,n)=0G(m, n) = 0, alors G(m,n+1)=0G(m, n+1) = 0
  • Sinon :
    • on écrit la représentation héréditaire en base 2+n2 + n de G(m,n)G(m, n)
    • on remplace les occurrences de 2+n2 + n par 3+n3 + n
    • on soustrait 11
    • le nombre obtenu est G(m,n+1)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=3m = 3, la séquence atteint 00 en 55 itérations :

basereprésentation héréditairevaleur
G(3,0)G(3, 0)b=2b1+1b^{1} + 13
G(3,1)G(3, 1)b=3b1b^{1}3
G(3,2)G(3, 2)b=4333
G(3,3)G(3, 3)b=5222
G(3,4)G(3, 4)b=6111
G(3,5)G(3, 5)b=7000

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

basereprésentation héréditairevaleur
G(7,0)G(7, 0)b=2bb1+b1+1b^{b^{1}} + b^{1} + 17
G(7,1)G(7, 1)b=3bb1+b1b^{b^{1}} + b^{1}30
G(7,2)G(7, 2)b=4bb1+3b^{b^{1}} + 3259
G(7,3)G(7, 3)b=5bb1+2b^{b^{1}} + 23127
G(7,4)G(7, 4)b=6bb1+1b^{b^{1}} + 146657
G(7,5)G(7, 5)b=7bb1b^{b^{1}}823543
G(7,6)G(7, 6)b=8b7×7+b6×7+b5×7+b4×7+b3×7+b2×7+b1×7+7b^{7} \times 7 + b^{6} \times 7 + b^{5} \times 7 + b^{4} \times 7 + b^{3} \times 7 + b^{2} \times 7 + b^{1} \times 7 + 716777215

Considérons l’énoncé Γ:mnG(m,n)=0\Gamma: \forall m \exists n G(m,n) = 0. Il signifie que toutes les séquences de Goodstein atteignent 00 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)=0G(m,n) = 0 n’est pas écrite dans le langage de l’arithmétique de Peano, qui ne connait pas le symbole GG.

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

💡 En fait, pour toute fonction ff pouvant être calculée par un algorithme (ce qui est le cas de GG), les formules comme f(x)=yf(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\N, mais qu’est-ce que N\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\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 :

ωω1+ω1+1>ωω1+ω1>ωω1+3>ωω1+2>ωω1+1>ωω1>ω7×7+ω6×7+ω5×7+ω4×7+ω3×7+ω2×7+ω1×7+7ω^{ω^{1}} + ω^{1} + 1 > ω^{ω^{1}} + ω^{1} > ω^{ω^{1}} + 3 > ω^{ω^{1}} + 2 > ω^{ω^{1}} + 1 > ω^{ω^{1}} \\ > ω^{7} \times 7 + ω^{6} \times 7 + ω^{5} \times 7 + ω^{4} \times 7 + ω^{3} \times 7 + ω^{2} \times 7 + ω^{1} \times 7 + 7

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

En généralisant cette observation, on montre que si la suite (G(m,n))n(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\N : c’est le théorème de Goodstein.

💡 L’addition et la multiplication des ordinaux ne sont pas commutatives, par exemple 7×ω7=ω7ω7×77 \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’à ε0\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 TT (de la logique du premier ordre) vérifie :

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

Alors TT est incomplète.

De façon très informelle, la démonstration consiste à construire un énoncé GG 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 GG ou de ¬G\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φ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 PP ou ¬P\lnot P pour tout énoncé PP 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