Indécidabilité (suite)

[danslideal]

**** Critique de la modération : MP uniquement, il faut vous l'écrire combien fois pour que vous compreniez ? ***
Une suite de proposition infinie longue, qui forme un raisonnement infiniment longue, tous valable,

Devient il "indécidable" dans une théorie.
Autrement dit, l'impossibilité à calculer les termes d'une suite de Goodman impliqu'elle qu'elle soit indécidable.

Ou bien au contraire, le fait qu'on puisse systématiquement produire les étapes (mais qu'on s'arrête à cause du temps) ne justifie pas qu'on le considére comme décidable (mais inconnu).
-----

[invite58633955]

Bonjour,
Il me semble que ce que vous entendez par indecidable, n'est precsiement pas ce que la communauté des logiciens entend en general par indecidable.

Je me permet de vous donner mon point de vue sur la chose (bien que non logicien), que l'on me corrige si je dis une enormité.

Vous avez des objets que vous voulez etudier...les "modèles" et vous avez "dessus", une structure formelle qui permet de les etudier, c'est ce qu'on appelle l'axiomatique. C'est un appareillage qui permet de pouvoir saisir une partie (et une partie seulement des informations sur ce modèle). L'indecidabilité concerne seulement le "coté" axiomatique. Vous avez des propostions que l'on peut enoncer sur le modèle et pourtant l'axiomatique dessus ne vous permet ni de les demontrer ni d'en demontrer leur négation.

C'est l'exemple des suites de Goodstein. Dans le modèle standard des entiers, il est "clair" que la convergence de ces suites vers 0 est vrai ou fausse, puisqu'une algorithme peut trancher. Il s'avère que l'on peut meme demontrer qu'elle est vrai (en utilisant une axiomatique plus puissante que celle de Peano) donc oui dans le modèle standard de N, ces suites tendent vers 0.

Cependant il n'est pas possible de trancher ce fait avec l'axiomatique de Peano, les outils de deductions crées par cette axiomatique ne sont pas assez "fins" pour trancher de la question de la convergence de cette suite ou non. La preuve c'est que l'on peut créer d'autres modèles (je ne les connais pas personnellement) dans lesquels l'axiomatique de Peano s'applique toujours, (mais plus celle de ZFC, qui permet justement de prouver que ces suites convergent dans le modele standard des entiers) mais dans lesquelles ces suites divergent.

Voila, l'indecidabilité d'une proprosition dans une axiomatique, c'est simplement ca. (du moins ce que j'en comprends).

[danslideal]

Il s'avère que l'on peut meme demontrer qu'elle est vrai (en utilisant une axiomatique plus puissante que celle de Peano) donc oui dans le modèle standard de N, ces suites tendent vers 0.

Ok..
Si c'est le "double" infinie algoritmique, je vois pas en quoi cela changerait quelque chose ..
Comprenez que je n'avale pas ça spontanément, parce que quand vous construisez la suite vous n'utiliser rien qui ne soit pas dans l'axiomatique de Peano. "+1", "-1", "*" et "^" ça n'a rien d'extraordinaire. Evidemment, vous considéré que "^" n'est pas dans l'arithmétique de peano, alors x² > 0 est indécidable, et je vois pas pourquoi vous allez chercher une suite compliqué pour une chose simple..

D'ailleurs je ne vois pas trop quelle ensemble différent de N pourrait obéir à l'arithmétique de peano.. si vous avez un exemple, ne vous génez pas !

[Médiat]

Je me permet de vous donner mon point de vue sur la chose (bien que non logicien), que l'on me corrige si je dis une enormité.

Ce que vous dites est correct.

Cependant il n'est pas possible de trancher ce fait avec l'axiomatique de Peano

C'est bien pourquoi j'avais demandé quelle définition de IN danslideal utilise, et sa réponse "l'axiomatique de Peano" m'a permis de répondre que le "théorème de Goodstein" était indécidable dans ce cadre.

[A voir en vidéo sur Futura]

[Médiat]

D'ailleurs je ne vois pas trop quelle ensemble différent de N pourrait obéir à l'arithmétique de peano.. si vous avez un exemple, ne vous génez pas !

Vous qui citez le théorème d'incomplétude de Gödel, comme si vous le connaissiez (le théorème, pas Gödel), vous pouvez écrire cela ? Etonnant !

[invite58633955]

Ok..
Si c'est le "double" infinie algoritmique, je vois pas en quoi cela changerait quelque chose ..
Comprenez que je n'avale pas ça spontanément, parce que quand vous construisez la suite vous n'utiliser rien qui ne soit pas dans l'axiomatique de Peano. "+1", "-1", "*" et "^" ça n'a rien d'extraordinaire. Evidemment, vous considéré que "^" n'est pas dans l'arithmétique de peano, alors x² > 0 est indécidable, et je vois pas pourquoi vous allez chercher une suite compliqué pour une chose simple..

D'ailleurs je ne vois pas trop quelle ensemble différent de N pourrait obéir à l'arithmétique de peano.. si vous avez un exemple, ne vous génez pas !

Justement, et c'est c'est ce qu'affirme en "substance" le théorème d'incompletude de Godel, si vous prenez le modèle standard des entiers aucune axiomatique (verifiant certaines conditions techniques) n’épuisera l'ensemble des propositions vrai dans ce modèle. Vous pourrez toujours ecrire une proposition vraie dans votre modèle mais que votre systeme axiomatique ne permet pas de prouver.

Pour les modèles non standards de l'axiomatique de Péano.
Vous pouvez jeter un oeil ici
Il doit y avoir des references un peu plus profondes, je n'en ai pas personnellement sous la main.

[danslideal]

Vous qui citez le théorème d'incomplétude de Gödel, comme si vous le connaissiez (le théorème, pas Gödel), vous pouvez écrire cela ? Etonnant !

pouvez vous répondre à ma question ?
De nous deux, c'est vous qui faites un concours de citation..

[invite58633955]

Ce que vous dites est correct.

C'est bien pourquoi j'avais demandé quelle définition de IN danslideal utilise, et sa réponse "l'axiomatique de Peano" m'a permis de répondre que le "théorème de Goodstein" était indécidable dans ce cadre.

Je sais tres bien que tout etais clair pour vous, . Et c'est bien ainsi que j'avais compris votre question.

Merci de votre confirmation de mes propos.

[danslideal]

Justement, et c'est c'est ce qu'affirme en "substance" le théorème d'incompletude de Godel, si vous prenez le modèle standard des entiers aucune axiomatique (verifiant certaines conditions techniques) n’épuisera l'ensemble des propositions vrai dans ce modèle. Vous pourrez toujours ecrire une proposition vraie dans votre modèle mais que votre systeme axiomatique ne permet pas de prouver.

Pour les modèles non standards de l'axiomatique de Péano.
Vous pouvez jeter un oeil ici
Il doit y avoir des references un peu plus profondes, je n'en ai pas personnellement sous la main.

Admettons.
Donc on a un ensemble d'objet qui satisfait à l'arithmétique de peano
(pour lequel chaque nombre est un successeur de 0)
Mais qui ne satisfait pas au théoréme de GoodStein.
ça me parait infiniment impossible à croire..

Et comme, par magie, les nombres "hypernaturels" ne sont pas définit dans Wiki, ben je suis pas convaincu.. voyez ?
Et comme en plus, la justication précédent, apporté par Médiat, faisait simplement référence à la suite infinie de démonstration, ça me montre à quelle point vous maitrisez tous la question..

Donc le jour ou on m'apportera les axiomes de ces arithmétiques non standard, je vous croirez, pas avant ! Désolé.

**** Pas d'insultes ****

[invite58633955]

Admettons.
Donc on a un ensemble d'objet qui satisfait à l'arithmétique de peano
(pour lequel chaque nombre est un successeur de 0)
Mais qui ne satisfait pas au théoréme de GoodStein.
ça me parait infiniment impossible à croire..
Et comme, par magie, les nombres "hypernaturels" ne sont pas définit dans Wiki, ben je suis pas convaincu.. voyez ?

Donc le jour ou on m'apportera les axiomes de ces arithmétiques non standard, je vous croirez, pas avant ! Désolé.

Non, mais justement, les axiomes sont les memes!
Une axiomatique ne definit pas entierement un modèle. Un modèle satisfait l'axiomatique ou non. Mais il n'est nullement garanti l'unicité d'un modèle satisfaisant une axiomatique donné.
Avez vous lu le lien que je vous ai envoyé?

Si vous n'etes pas au courrant de l'existence de modèle non standard de l'axiomatique de Peano, peut etre commencez par vous renseigner la dessus.
On trouve une litterature abondante a ce sujet si je ne m'abuse.
Par exemple le bouquin de Kaye "Models of Peano Arithmetic" (je ne l'ai personellement pas lu, mais un ami a moi, qui s'interessait un peu au catégories de modèles m'en avait parlé)

[Médiat]

Et comme, par magie, les nombres "hypernaturels" ne sont pas définit dans Wiki, ben je suis pas convaincu.. voyez ?

Pas de chance : http://en.wikipedia.org/wiki/Hypernatural, mais pas de chance, cela n'a rien à voir.

Donc le jour ou on m'apportera les axiomes de ces arithmétiques non standard, je vous croirez, pas avant ! Désolé.

Facile : les axiomes de Peano !

[invite58633955]

JE me permet de rajouter, autant je suis tout a fait capable de vous prouver que dans ZFC, les suites de Goodstein convergent vers 0, c'est une argument facile, pour peu qu'on connait la théorie des ordinaux, autant vous montrer que le théorème est effectivement indecidable dans l'axiomatique de Peano est qqch dont je suis incapable et n'est pas un théorème trivial.
Lisez en la preuve si vous voulez vous en convaincre.
Pour ma part je suis incapable de ne serait ce que vous indiquer les idées de la preuve.

[danslideal]

Pas de chance : http://en.wikipedia.org/wiki/Hypernatural, mais pas de chance, cela n'a rien à voir.


Facile : les axiomes de Peano !

Excusez moi. Encore !

"In non-standard analysis, a hyperinteger N is a hyperreal number equal to its own integer part."

"The system of hyperreal numbers represents a rigorous method of treating the infinite and infinitesimal quantities. The hyperreals, or nonstandard reals, *R, are an extension of the real numbers R that contains numbers greater than anything of the form

1 + 1 + ... + 1.


Donc en gros, vous tendez de me faire croire qu'une arithmétique basé sur des "hyperrééls" (plus grand que tout les entiers) rend le théoréme de goodstein "faux" ?
**** Grossièreté *****
Si vous voulez j'ai mieux :

soit H hyperréél

m(0) = H
m(n) = m(n-1) -1

m converge vers 0

Cette phrase est indécidable. Et pour cause : l'axiome portant sur les hyperréél est référent à l'axiomatique de peano :

Je m'explique :

h hyperréél, plus grand que " n importe quelle 1 + 1 + ... + 1"


" plus grand que " n importe quelle 1 + 1 + ... + 1"" fait référence avec l'axiomatique de peano pour la contredire.


Votre proposition "indécidable" est donc "autoréférente".

Tout ça pour ça.. franchement, merci.

[invite19431173]

Insultes + grossièretés = fermeture de ce fil.

Pour la modération.