La logique c’est pas logique!

El 2 octubre 2010 - Escrito por Pierre Colmez Ver los comentarios (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)...

Notas

[1] Elle 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.

[2] Si 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...

[3] Les 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é...

Comentario sobre el artículo

La logique c’est pas logique!

le 2 de octubre de 2010 à 19:40, par Patrick Popescu-Pampu

Dans quel contexte Goodstein est-il tombé sur cette
suite ? Était-ce pour exhiber un exemple concret
d’énoncé indémontrable ? Y a-t-il beaucoup de tels
exemples frappants ?

Et en quel sens ’’« la » vérité est que cette suite tend vers 0’’,
puisque l’hypothèse contraire ne menne pas à des contradictions
dans l’arithmétique de Peano ? C’est au sens où on reconnaît
que certains axiomes de la théorie des ordinaux, permettant
de faire la preuve esquissée, sont reconnus comme vrais par
notre cerveau ?

Merci d’avance !
Répondre à ce message

Suites de Goodstein

le 3 de octubre de 2010 à 12:17, par Rémi Peyre
Autant que je sache, Goodstein n’a pas écrit son énoncé en vue de fabriquer un indécidable ; il s’agit surtout d’un joli exercice d’application de la théorie des ordinaux.

Maintenant, sur la question de « la » vérité :
- D’abord, je pense qu’on peut en effet considérer que la théorie des ordinaux (du moins celle des ordinaux « pas trop grands », car on n’a pas besoin d’aller plus loin pour Goodstein), est intuitivement vraie.
- Ensuite, d’après ce que j’ai compris en faisant quelques recherches, l’idée de base pour prouver l’indécidabilité du théorème de Goodstein est de montrer que ce théorème implique la consistance de la logique de Peano. (Rappelons que le second théorème d’incomplétude énonce qu’il est impossible de prouver que l’axiomatique de Peano est consistante à partir de cette axiomatique elle-même). J’ignore s’il y a en fait équivalence, mais faisons comme si. Or, si les axiomes de Peano sont « intuitivement vrais », il va de soi que leur consistance l’est également ! En d’autres termes, il n’est pas raisonnable de supposer que le théorème de Goodstein serait faux, à moins de vouloir rejeter toute l’axiomatique de Peano (puisqu’une axiomatique contradictoire n’est pas acceptable).
- Voilà pour les suites de Goodstein. Maintenant, il y a certainement d’autres énoncés qui sont indécidables mais qui ne sont pas équivalents à la consistance de l’axiomatique. À titre personnel (c’était aussi le point de vue de Gödel lui-même), j’estime que l’indécidabilité d’une proposition ne change rien au fait que celle-ci soit, « en vérité », ou bien juste ou bien fausse, mais pas les deux. C’est comme de savoir, mettons, si le tout premier humain à avoir franchi le détroit de Béring était un homme ou une femme : on ne saura vraisemblablement jamais, mais la réponse est unique malgré tout.
Répondre à ce message
La logique c’est pas logique!

le 3 de octubre de 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

La logique c’est pas logique!

le 4 de octubre de 2010 à 00:53, par Dimitri Karpov

Bonjour,
Je ne comprends pas un détail: pourquoi prouver la non consistance de ZF fournit automatiquement une démonstration des énoncés formulables dans le langage de la théorie des ensembles? Est-ce que ça ne dit pas seulement qu’il existe des preuves pour tous les énoncés formulables? Je suis pas très armé en logique, d’où la question peut-être naïve...
Répondre à ce message

La logique c’est pas logique!

le 4 de octubre de 2010 à 08:11, par François Loeser

Essentiellement par définition une théorie inconsistante dans un langage L démontre tout énoncé de L.
Répondre à ce message
La logique c’est pas logique!

le 4 de octubre de 2010 à 11:14, par Pierre-Yves Gaillard

Il y a une explication très claire dans Bourbaki, Théories des Ensembles, p. I.25 (édition de 1970).
Répondre à ce message

La logique c’est pas logique!

le 3 de octubre de 2010 à 10:05, par Pierre-Yves Gaillard

La non consistance de l’arithmétique est une conviction que j’ai depuis plusieurs années. Je l’avais gardée pour moi jusqu’à cet été. J’ai décidé alors de la mentionner sur ma page web. (Je l’ai «publiée» la première fois le 22 juillet ici.)

Mes motivations sont certainement beaucoup moins profondes que celles de Vladimir Voevodsky.

Savez-vous si cette opinion a été exprimée précédemment ?
Répondre à ce message
La vidéo

le 3 de octubre de 2010 à 11:36, par Pierre-Yves Gaillard

La vidéo est disponible ici.
Répondre à ce message
La logique c’est pas logique!

le 3 de octubre de 2010 à 15:31, par Lionel Fourquaux

Une autre façon de présenter les choses, au sujet de la table de vérité de p⇒q, qui a l’air de bien passer auprès de mes étudiants, est de leur expliquer qu’on veut que ∀n∈ℕ 4|n⇒2|n soit vrai, et cela a pour conséquence que 4|1⇒2|1 et 4|2⇒2|2 sont tous les deux vrais.
Répondre à ce message

La logique c’est pas logique!

le 3 de octubre de 2010 à 20:19, par Neotrad

Bonjour,

une phrase que j’aime beaucoup pour faire comprendre l’implication à mes étudiants : «mange ta soupe ou tu n’auras pas de dessert !».
Répondre à ce message

La logique c’est pas logique! p ⇒ q

le 4 de octubre de 2010 à 18:34, par Pierre Lescanne

☺Je suis d’accord avec votre fille, définir p ⇒ q comme q ∨ ¬ p n’est pas très logique. Moi ce que j’aimerais c’est que p ⇒ q signifiât d’une démonstration de p je peux construire une démonstration de q. C’est vrai qu’avec cette définition je perds le résultat ¬¬p ⇒ p, mais est-ce qu’on s’en sert suivent?
Répondre à ce message

La logique c’est pas logique! p ⇒ q

le 6 de octubre de 2010 à 11:45, par Pierre Lescanne

Est-ce qu’on s’en sert souvent?
Répondre à ce message

La logique c’est pas logique! Les suites de Goodstein

le 4 de octubre de 2010 à 19:03, par Pierre Lescanne

Ce qui fait marcher la démonstration de la terminaison des suites de Goodstein ça n’est pas tant le fait que l’on utilise ces «terrifiants» ordinaux, mais le fait que l’on puisse faire des récurrences sur des formules qui contiennent des quantifications non pas sur des entiers naturels, mais sur des ensembles d’entiers naturels, «pour tout ensemble A, la propriété P(A) est satisfaite» ; de ce fait on sort de la logique de Peano du premier ordre. Une fois que l’on accepte cela, la démonstration de la terminaison des suites de Goodstein est facile, je dirais presqu’élementaire et surtout ne nécessite pas le concept d’ordinal et je pourrais vous l’expliquer sans jargon.

Un petit point historique. Goodstein a démontré en 1947 la terminaison des suites qui portent son nom et ce sont Kirby et Paris qui ont démontré en 1982 que cela ne pouvait pas être fait dans l’arithmétique de Peano.

Pour démontrer que l’on ne peut pas démontrer la terminaison des suites de Goodstein dans l’arithmétique, une méthode peut consister à produire un modèle de l’arithmétique de Peano où une suite de Goodstein ne s’arrête pas. Ce modèle est un modèle non standard de l’arithmétique de Peano.
Répondre à ce message

«je pourrais vous l’expliquer sans jargon»

le 5 de octubre de 2010 à 06:30, par Pierre-Yves Gaillard

Vous écrivez : «je pourrais vous l’expliquer sans jargon». Je suis preneur !
Répondre à ce message

Dejar un comentario

Foro sólo para inscritos

Para participar en este foro, debe registrarte previamente. Gracias por indicar a continuación el identificador personal que se le ha suministrado. Si no está inscrito/a, debe inscribirse.

Conexión | inscribirse | ¿contraseña olvidada?

El autor

Pierre Colmez

Directeur de Recherche au CNRS, à l’Institut de Mathématiques de Jussieu.

La logique c’est pas logique!

Notas

Comentario sobre el artículo