Le lièvre et la tortue

[invite6754323456711]

Bonsoir,

On prend un nombre naturel au hasard, par exemple 8 et on l'écrit en base 2 en utilisant que des puissances de 2.

8 = 2²⁺¹

Le lièvre arrive est remplace tout les 2 par 3 --> 3³⁺¹ = 81. On obtient un nombre bien plus grand car le lièvre court plus vite que la tortue.

La tortue arrive est soustrait 1 --> 80


Le lièvre écrit le nouveau nombre en base 3 et remplace les 3 par des 4 : 3³⁺¹ - 1 = 3³ × 2 + 3² × 2 + 3 × 2 + 2 --> 4⁴ × 2 + 4² × 2 + 4 × 2 + 2

La tortue elle soustrait toujours 1 ---> 4⁴ × 2 + 4² × 2 + 4 × 2 + 1 = 169

Donc à chaque étape, on incrémente la base (le lièvre), et on soustrait 1 (la tortue).

Qui gagne le lièvre ou la tortue ?

Peut-on le démontrer dans l'arithmétique de Peano ?

Patrick
-----

[invite6754323456711]

Bonsoir

Apparemment un flop ... sujet surement bien connu.

pour la tortue

Par exemple la suite de Goodstein issue de 4 en base 2 atteint 0 après 3 × 2^402653211 − 1 étapes.

Exemple donné par Alain Connes pour illustrer une proposition de nature universelle (pour tout nombre) vrai non démontrable dans un système formel.

Si une proposition universelle est démontrable, elle est vrai, mais la réciproque est fausse.

A l'inverse si une proposition existentielle est vrai, elle est démontrable, mais la réciproque est fausse. Exemple Il exite un entier n qui est pair et n'est pas la somme de deux nombres premiers.

Patrick
Pink Floyd - Another Brick in the Wall : http://www.youtube.com/watch?v=M_bvT-DGcWw

[Médiat]

Exemple donné par Alain Connes pour illustrer une proposition de nature universelle (pour tout nombre) vrai non démontrable dans un système formel.

Je suppose qu'Alain Connes est plus rigoureux que cela (bien qu'il soit un platonicien convaincu ).

Pour que les choses soient claires : le théorème de Goodstein est indécidable dans l'arithmétique de Peano (il y a des modèles où il est vrai et des modèles où il est faux), mais démontrable dans ZF (donc vrai dans tous les modèles de ZF).

Si une proposition universelle est démontrable, elle est vrai, mais la réciproque est fausse.

Exprimé ainsi, c'est une évidence (théorème de complétude de Gödel) dans un sens (et même pas besoin de préciser "universelle"), dans l'autre sens c'est est en contradiction avec ce même théorème.

A l'inverse si une proposition existentielle est vrai, elle est démontrable, mais la réciproque est fausse. Exemple Il exite un entier n qui est pair et n'est pas la somme de deux nombres premiers.

Même chose.

Je suppose qu'ici "vrai" veut dire "vrai dans le modèle standard de l'arithmétique", ce qui, à mes yeux, est un abus de langage difficile (impossible ?) à accepter hors contexte (et même en contexte pour un formaliste comme moi).

[invite6754323456711]

Je suppose qu'Alain Connes est plus rigoureux que cela (bien qu'il soit un platonicien convaincu ).

Pour que les choses soient claires : le théorème de Goodstein est indécidable dans l'arithmétique de Peano (il y a des modèles où il est vrai et des modèles où il est faux), mais démontrable dans ZF (donc vrai dans tous les modèles de ZF).

Exprimé ainsi, c'est une évidence (théorème de complétude de Gödel) dans un sens (et même pas besoin de préciser "universelle"), dans l'autre sens c'est est en contradiction avec ce même théorème.

Même chose.

Je suppose qu'ici "vrai" veut dire "vrai dans le modèle standard de l'arithmétique", ce qui, à mes yeux, est un abus de langage difficile (impossible ?) à accepter hors contexte (et même en contexte pour un formaliste comme moi).

J'ai repris le texte des propos recueillis par Olivier xxxx journaliste au magazine de la recherche lors d'un entretien avec Alain Connes.

L'objectif était de faire toucher du doigt le théorème de Gödel en cherchant à aller au delà de la simple interprétation que dans un système donné il y aura toujours une proposition indécidable.

"Alain Connes : Or le théorème de Gödel est bien plus méchant que cela. Il dit qu'il y aura toujours une proposition vraie qui ne sera pas démontrable dans le système."

Patrick

[A voir en vidéo sur Futura]

[Médiat]

L'objectif était de faire toucher du doigt le théorème de Gödel en cherchant à aller au delà de la simple interprétation que dans un système donné il y aura toujours une proposition indécidable.

Déjà, dit comme cela, c'est faux (ce n'est pas vrai pour n'importe quel système), je ne pense pas que ce soit la faute de Connes ...

"Alain Connes : Or le théorème de Gödel est bien plus méchant que cela. Il dit qu'il y aura toujours une proposition vraie qui ne sera pas démontrable dans le système."

Toujours la même ambiguité : que veux dire "vrai" ici ?

Je suppose qu'ici "vrai" veut dire "vrai dans le modèle standard de l'arithmétique", ce qui, à mes yeux, est un abus de langage difficile (impossible ?) à accepter hors contexte (et même en contexte pour un formaliste comme moi).

J'ose espérer que Connes l'a explicité sous une forme ou sous une autre ; si pour lui c'est une telle évidence qu'il n'a pas besoin de l'expliciter, alors c'est un très mauvais pédagogue (il reste l'hypothèse que le journaliste n'ait pas tout retranscrit, je te laisse trouver une troisième hypothèse ).

Le théorème d'incomplétude de Gödel est fantastique (d'autant plus avec les travaux récents de Calude par exemple, mais moins que le théorème de complétude), mais ce n'est pas en lui faisant dire des choses qu'il ne dit pas qu'on le rend plus fantastique encore.

Exercice : comment exprimer le théorème de complétude et le premier théorème d'incomplétude de Gödel avec le vocabulaire "vrai" tel que ci-dessus, sans donner l'impression que ces théorèmes sont contradictoires ?

Complétude : ce qui est vrai est exactement ce qui est démontrable.
Incomplétude : il existera toujours du vrai qui ne sera pas démontrable.

Personnellement, mais cela n'engage que moi, je trouve cette façon d'exprimer les choses inacceptable, et même s'il existe plusieurs façons de contourner le problème, il me semble que le plus sain est de donner une définition du mot "vrai" dans ce contexte avant de l'utiliser.

[invite6754323456711]

Toujours la même ambiguité : que veux dire "vrai" ici ?

Vrai fait référence à un théorème fondamental de la logique (pendant du théorème de complétude) si une proposition universelle est démontrable, elle est vrai.

L'exemple de la suite de la suite Goodstein porte sur l'arithmétique de Peano.

"Journaliste : Pouvez-vous donner un exemple parlant de proposition vraie non démontrable"


Patrick

[Médiat]

Vrai fait référence à un théorème fondamental de la logique (pendant du théorème de complétude) si une proposition universelle est démontrable, elle est vrai.

Tu n'as pas l'impression qu'il y a quelque chose que tu n'as pas compris ici, puisque le théorème de complétude dit : une proposition est démontrable si et seulement si elle est vraie. Encore une fois, tout est dans la définition de "vrai".

Le théorème auquel tu fais allusion je le connais très bien, il est dans mon document sur l'arithmétique que j'ai posté sur ce site (et, tu vas rire, avec justement l'exemple de la conjecture de Golbach), je conteste le vocabulaire qui induit en erreur (au profit d'un sensationnalisme journalistique) !

Pourquoi ne pas adopter un vocabulaire strictement non ambigu alors que ce serait si simple (mais moins impressionnant) ?

[invite6754323456711]

tout est dans la définition de "vrai".

Une formule satisfiable pour une interprétation donné non ?

Une interprétation I dans laquelle une formule close F est vraie est un modèle de F.

Patrick

[invite6754323456711]

Bonsoir Médiat,

Cela serait peu être profitable à tous le monde que tu donnes un contre exemple afin de bien comprendre le piège journalistique qui n'apparaît pas de manière immédiate.

Patrick

[Médiat]

Une formule satisfiable pour une interprétation donné non ?

Pour moi ceci est (presque) la définition de formule non réfutable dans une théorie, donc soit démontrable, soit indécidable, et dire que les énoncés indécidables sont vrais, moi cela me choque.

Cela serait peu être profitable à tous le monde que tu donnes un contre exemple afin de bien comprendre le piège journalistique qui n'apparaît pas de manière immédiate.

Je ne sais pas ce que tu veux dire par contre exemple, par contre ce que je veux dire par piège journalistique, c'est que la bonne formulation pourrait être (tel qu'il apparaît dans le document cité plus haut sauf que je remplace les symboles ésotériques) :

Soit T une théorie consistante qui contient l'arithmétique de Robinson, et soit (c'est à dire les énoncés universels)
1) si T démontre alors est "vrai" dans
2) si est indécidable dans T alors est "vrai" dans

Dans cette formulation le mot "vrai" n'apparaît clairement que dans un seul sens non ambigu "satisfait dans un modèle particulier et clairement identifié").

[JPL]

Reste-t-on dans Science ludique ou vaut-il mieux déplacer dans Mathématiques du Supérieur ?

[Médiat]

Reste-t-on dans Science ludique ou vaut-il mieux déplacer dans Mathématiques du Supérieur ?

Je rappelle que vous êtes ici dans la rubrique Science ludique : la science en s'amusant. La bonne humeur ne doit pas vous faire oublier :
1) que l'humour en question doit avoir une base scientifique ;

Ce fil a commencé avec une présentation ludique et a continué avec un contenu scientifique, c'est la définition même de ce sous-forum, non ?

La dessus, si toi et/ou ù100fil vouliez le déplacer, cela ne me gênerait nullement.

[JPL]

Je posais juste la question. L'argument éventuel pour un déplacement c'est que la discussion prend un tour qui pourrait intéresser les lecteurs du forum de math qui ne fréquentent pas forcément Sciences ludiques.
Ce sont les participants qui décident.

[invite6754323456711]

Bonsoir,

Initialement l'exercice se veut ludique, mais il semble que le fond cache un piège que soulève Médiat.


Patrick

[invite6754323456711]

L'argument éventuel pour un déplacement c'est que la discussion prend un tour qui pourrait intéresser les lecteurs du forum de math qui ne fréquentent pas forcément Sciences ludiques.
Ce sont les participants qui décident.

Si il peut y avoir d'autres avis Critiques (au sens positif du terme) pourquoi pas.

Patrick