La logique c’est pas logique !

Le 2 octobre 2010  - Ecrit par  Pierre Colmez Voir les commentaires (14)

C’est ce qu’a déclaré ma fille quand on lui a expliqué que
$p\Rightarrow q$ est vrai [1]
si $p$ est faux.
Il faut bien avouer que la logique réserve parfois des surprises de taille.

L’Institute for Advanced Study de Princeton fête ses 80 ans cette année, ce qui a donné lieu à deux journées de gala avec des conférences données par des orateurs prestigieux. Dans l’une d’entre elles, Vladimir Voevodsky nous a expliqué, probablement en hommage a Gödel (un des grands anciens de l’Institut), pourquoi il pensait que l’arithmétique était non consistante. Pensée un peu angoissante, mais pas totalement absurde, l’arithmétique
élémentaire étant nettement plus mystérieuse que ce que l’on pourrait imaginer comme le montre l’exemple des suites de Goodstein.

On part d’un entier $n$ que l’on écrit en base $2$, les exposants (et les exposants d’exposants, etc.) étant
aussi écrits en base $2$ : par exemple,
$21$ sera écrit sous la forme $2^{2^2}+2^2+1$. On remplace les
$2$ par des $3$ ; on enlève $1$, on réécrit le résultat en base $3$, on remplace les $3$ par des $4$,
on enlève $1$, on réécrit le résultat en base
$4$, et on continue. Par exemple,
en partant de $21=2^{2^2}+2^2+1$, on obtient successivement
$3^{3^3}+3^3+1$, puis $3^{3^3}+3^3$, puis $4^{4^4}+4^4$,
puis $4^{4^4}+3\cdot 4^3+3\cdot 4^2+3\cdot 4+3$, puis
$5^{5^5}+3\cdot 5^3+3\cdot 5^2+3\cdot 5+3$, etc.
Ce dernier nombre a déjà plus de $20\,000$ chiffres en écriture
décimale, et il est clair que la suite explose très très vite...

Pourtant, « la » vérité est que cette suite tend [2] vers $0$, quel que soit le choix du terme initial $n$ (i.e. est constante, égale à $0$, à partir d’un certain rang), mais que
ceci n’est pas démontrable [3] dans l’arithmétique ordinaire
(de Peano)...

Notes

[1Elle a un peu mieux accepté cette bizarrerie
quand sa sœur lui a expliqué que son prof lui avait dit qu’il fallait nier la phrase pour comprendre : $p\Rightarrow q$ veut dire qu’on ne peut pas avoir $p$ sans avoir $q$, et donc le contraire est que l’on peut avoir $p$ et $\overline q$ (où $\overline q$ est la négation de $q$), et donc que $p\Rightarrow q$ est la même chose que « $\overline p$ ou $q$ », et donc
est vrai si $p$ est faux.

[2Si tous les termes sont non nuls, et si on remplace par $\omega$ les $2$, $3$, $4$, $5$, etc. qui apparaissent dans les écritures des termes successifs
de cette suite, où $\omega$ est un ordinal infini, on obtient une
suite strictement décroissante d’ordinaux, ce qui est impossible...

[3Les ordinaux de la note précédente ne sont pas des objets de l’arithmétique de Peano ; je ne sais pas comment on démontre que le résultat n’est pas prouvable dans l’arithmétique de Peano, et j’avoue que ce flou participe à la magie de
l’énoncé...

Partager cet article

Pour citer cet article :

Pierre Colmez — «La logique c’est pas logique !» — Images des Mathématiques, CNRS, 2010

Commentaire sur l'article

Voir tous les messages - Retourner à l'article

  • La logique c’est pas logique !

    le 3 octobre 2010 à 19:04, par François Loeser

    Quelques remarques sur le post de Pierre Colmez et le commentaire de Patrick Popescu-Pampu :

    1) L’article de Goodstein est paru dans le Journal of Symbolic Logic en 1947, sous le titre « Transfinite ordinals in recursive number theory ». Dès l’origine le lien était fait avec un théorème de Gentzen (1936) sur la consistance de l’arithmétique de Peano. L’énoncé de Gentzen est le suivant « l’induction jusqu’à l’ordinal \epsilon_0 entraine la consistance de l’arithmétique ». Ici je simplifie un peu, car il s’agit de l’induction pour une classe très réduite d’énoncés. L’ordinal \epsilon_0 est la limite (ou l’union) des ordinaux \omega_n définis par \omega_0 = \omega et \omega_n + 1 = \omega_n^\omega. Ici \omega désigne le plus petit ordinal dénombrable, c’est à dire les entiers. Il résulte du théorème de Gödel que l’induction jusqu’à l’ordinal \epsilon_0 (énoncé que l’on peut formuler dans le langage de l’arithmétique) n’est pas démontrable à partir des axiomes de Peano.

    2) Le théorème de Goodstein est certainement vrai dans le sens suivant : pour chaque entier n fixé, il existe une preuve dans l’arithmétique de Peano de la suite de Goodstein de terme initial n, à savoir la suite elle même (qui finit par valoir 0). Ce qui n’est pas démontrable c’est l’énoncé pour tout n (il y a une grande différence entre l’existence, pour chaque entier n, d’une démonstration pour un énoncé E (n), et l’existence d’une démonstration pour l’énoncé \forall n E (n)).

    3) Pour chaque entier n, appelons h (n) le plus entier tel que la suite de Goodstein de terme initial n s’annule à partir de h (n). Il a été démontré par Weiermann que la fonction h croit plus vite que toute fonction définissable dans l’arithmétique de Peano. Ceci fournit, me semble-t-il une bonne explication au fait qu’il ne soit pas possible de démontrer que h est effectivement une fonction dans l’arithmétique de Peano.

    4) Je ne vois pas en quoi le théorème de Goodstein aurait un rapport avec la non consistance éventuelle de l’arithmétique. Celle-ci, mais c’est une opinion personelle, me semble extrêmement improbable. Rappelons que le collègue qui la démontrerait empocherait illico les six millions de dollars des prix Clay restants. En effet la non consistance de Peano entrainerait a fortiori celle de Zermelo-Frenkel, et donc on aurait une démonstration de tous les énoncés formulables dans le langage de la théorie des ensembles...

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?