L'arithmétique sur les entiers est-elle une science expérimentale ?

[inviteface0172]

Ca ne changera pas les entiers (Peano c'est du béton armé) mais ça peut changer certaines démonstrations (je n'en ai pas en tête).

Il y a sur internet des listes fort longues de propositions strictement équivalentes à la puissance du continu ou à l'axiome du choix.
Doit y avoir des trucs sur les entiers là dedans ou en lien avec ceux-ci. En tout cas, il doit y avoir moyen d'y faire son petit marché.

Faudrait retrouver les liens car je n'ai pas tout ça en tête

Ah si, j'ai un exemple, trivial :
Soit l'ensemble P toutes les partitions possibles des entiers. Existe-t-il un sous-ensemble de P impossible à mettre en bijection avec N tout comme avec P ?
=> indécidable, c'est justement l'hypothèse du continu (qui répond par non à cette question).

Quand on voit les entiers, il peut sembler incroyable que cette question soit indécidable.... et pourtant !

Quand je dis cela ne change pas les entiers il faut comprendre, qu'on ne construit pas ainsi plusieurs types d' entiers comme on peut construire plusieurs types de géométries.
-----

[Médiat]

Toute formule indécidable d'une théorie permet de créer 2 nouvelles théories

[inviteface0172]

Toute formule indécidable d'une théorie permet de créer 2 nouvelles théories

Oui mais dans PC ou non PC, les entiers sont-ils différents ?
On dira que les entiers sont les même si les propriétés des entiers sur PC, sont également des propriétés des entiers sur non PC, et réciproquement.
PC : puissance du continu.

[Médiat]

On écrit plutôt HC(G) pour hypothèse du continu (généralisée).

Si une théorie a A pour axiome et une autre a nonA pour axiome, il est clair que les modèles de l'une ne seront pas des modèles de l'autre (et réciproquement).

[inviteface0172]

Si une théorie a A pour axiome et une autre a nonA pour axiome, il est clair que les modèles de l'une ne seront pas des modèles de l'autre (et réciproquement).

si les propriétés (des entiers) sont exprimées dans l'arithmétique de Peano, ce n'est pas si évident que cela, en tous les cas pour moi.

[Médiat]

AP n'est pas particulier ici, les modèles de la théorie des groupes abéliens ne sont pas les mêmes que les modèles de la théorie des groupes non abéliens, et c'est la même chose pour toutes les théories.

[inviteface0172]

Je reformule ma question : existe-t-il dans AP un indécidable P exprimable dans AP (logique du première ordre) ?

[Médiat]

Et il en existera toujours quelque soit l'extension récursive de AP (théorème d'incomplétude de Gödel)

[inviteface0172]

Et il existera toujours quelque soit l'extension récursive de AP (théorème de complétude de Gödel)

Pourrais-tu expliciter cette propriété du premier ordre indécidable dans AP ou me donner un lien vers cette dernière ?
Merci.

[Médiat]

http://forums.futura-sciences.com/de...ml#post5364776 et il en existe une infinité d'autres (dont un paquet d'équations diophantiennes telels que l'existence de solutions est indécidable (théorème de Matiyasevich))

[inviteface0172]

http://forums.futura-sciences.com/de...ml#post5364776 et il en existe une infinité d'autres (dont un paquet d'équations diophantiennes telels que l'existence de solutions est indécidable (théorème de Matiyasevich))

Quand je clique sur ton lien je tombe sur cette citation :

Bonjour,

Clairement non, ne serait-ce que l'exemple des suites de Goodstein.

Et ma question est :

Pourrais-tu expliciter cette propriété du premier ordre indécidable dans AP ou me donner un lien vers cette dernière ?
Merci.

Je n'ai pas l'impression que tu répondes à ma question, à moins que tu es mal compris ma question ou moi mal compris ta réponse.

[inviteface0172]

http://forums.futura-sciences.com/de...ml#post5364776

Maintenant si j'interprète ton lien comme faisant référence à l'auto-référence, je rappellerais que l'auto-référence est, selon moi, impossible avec une logique du première ordre stricte (privée de toute extension récursive), jusqu'à preuve du contraire.

[inviteface0172]

Bilan :
J'ai demander : existe-t-il dans AP un indécidable P exprimable dans AP (logique du première ordre) ?
Ce à quoi Médiat à répondu : "Et il en existera toujours quelque soit l'extension récursive de AP"
J'ai demandé d'en donner un exemple, d'une du première ordre.
J'intèrpéte la réponse de Médiat comme indiquant l'auto-réfèrence.
Or une logique du premier ordre stricte (sans extension récursive) ne permet pas l'auto-référence, deplus la logique dans laquelle j'attend ma réponse est celle de AP strictement (sans extension récursive).

Résultat, on en est toujours au même point où :
Personne n'a proposé pour l'instant dans AP strictement une propostion indécidable, ou même n'a prétendu qu'il en existait.

[Deedee81]

Salut,

J'intèrpéte la réponse de Médiat comme indiquant l'auto-réfèrence.

Je n'ai pas compris sa réponse comme ça. Mais étant moi-même incapable de répondre, on va attendre son explication.

[inviteface0172]

Salut,



Je n'ai pas compris sa réponse comme ça. Mais étant moi-même incapable de répondre, on va attendre son explication.

Bonjour,

Effectivement une réponse explicite de sa part sera mieux que mon interprétation qui peut être incorrecte.

[Médiat]

Bonjour,

J'ai demander : existe-t-il dans AP un indécidable P exprimable dans AP (logique du première ordre) ?
Ce à quoi Médiat à répondu : "Et il en existera toujours quelque soit l'extension récursive de AP"
J'ai demandé d'en donner un exemple, d'une du première ordre.
J'intèrpéte la réponse de Médiat comme indiquant l'auto-réfèrence.

Ma réponse pointait ... sur ma réponse déjà donnée : les suites de Goodstein dont la convergence est indécidable dans AP, j'ai aussi donné en exemple le théorème de Matiyasevich.

Or une logique du premier ordre stricte (sans extension récursive) ne permet pas l'auto-référence

Pourtant c'est bien le principe de la démonstration de Gödel

de plus la logique dans laquelle j'attend ma réponse est celle de AP strictement (sans extension récursive).

En parlant d'extension récursive de AP, je ne parlais pas de changer la logique, mais la théorie, tout en respectant les hypothèses du théorème d'incomplétude de Gödel.

Personne n'a proposé pour l'instant dans AP strictement une propostion indécidable, ou même n'a prétendu qu'il en existait.

Ben si : Gödel, Goodstein, Matiyasevich

[inviteface0172]

Bonjour,

Ben si : Gödel, Goodstein, Matiyasevich

Je suis désolé, comme dirait l'autre je comprend vite mais il faut m'expliquer lentement.

Soit U_n une suite Goodstein, alors
P : (U_n converge vers 0)
P est une proposition indécidable dans AP ?

C'est bien cela ?

Mais il me semblait que U_n était impossible à construire dans AP stirctement (sans extension récursive), non ?

[Médiat]

Une suite de Goodstein donnée est calculable (mais cela peut prendre du temps), ce qui est indécidable c'est "Toutes les suites de Goodstein convergent vers 0"

[inviteface0172]

Une suite de Goodstein donnée est calculable (mais cela peut prendre du temps), ce qui est indécidable c'est "Toutes les suites de Goodstein convergent vers 0"

une suite est une fonction des entiers, et dans "toutes les suites de Goodstein convergent vers 0" la quantification porte sur un ensemble de suite, c'est à dire un ensemble de fonction, ce qui n'est pas possible dans la logique du premier ordre....

Pourrais-tu éclaircir ce point ?
Merci.

[inviteface0172]

Une suite de Goodstein donnée est calculable

Sous-entends tu que toute fonction entière calculable est descriptible dans AP strictement (sans extension) ?

car tu réponds à cette question :

Mais il me semblait que U_n était impossible à construire dans AP stirctement (sans extension récursive), non ?

[Médiat]

une suite est une fonction des entiers, et dans "toutes les suites de Goodstein convergent vers 0" la quantification porte sur un ensemble de suite,

Non, la quantification porte sur U_0

[PlaneteF]

Toute formule indécidable d'une théorie permet de créer 2 nouvelles théories

Bonjour Médiat,

Petite remarque avec un peu de retard : Je pense qu'ici il est important de préciser qu'à partir d'une théorie cohérente, on peut créer 2 nouvelles théories cohérentes.

Cordialement

[Médiat]

Bonjour PlaneteF

Petite remarque avec un peu de retard : Je pense qu'il est important ici de préciser qu'à partir d'une théorie cohérente, on peut créer 2 nouvelles théories cohérentes.

Non, non cette précision n'est pas , mathématiquement, utile (pédagogiquement, je suis d'accord)

[PlaneteF]

Non, non cette précision n'est pas , mathématiquement, utile (pédagogiquement, je suis d'accord)

Je ne suis pas sûr de comprendre le sens de ta réponse, mais peut-être disons-nous la même chose. Donc je précise le sens de ma remarque qui était de dire :

* OK sans le terme "cohérent" mais c'est trivial donc pas de "valeur ajoutée" particulière.

* Avec le terme "cohérent" OK mais a priori c'était pas gagné du tout et en l'occurrence on obtient un résultat fondamental.

Cdt

[Médiat]

Quelques explications : il est question d'une formule indécidable dans une théorie donc

est consistante (sinon il n'y a pas d'indécidable)
est consistante (par définition d'une formule indécidable)
est consistante (par définition d'une formule indécidable)

Donc on est forcément dans le cas que vous citez.

[PlaneteF]

est consistante (par définition d'une formule indécidable)
est consistante (par définition d'une formule indécidable)

Pour moi ça c'est une conséquence du théorème de complétude en partant de la définition d'un indécidable qui est : et ... ce n'est pas la définition elle même ?! ... ou du moins pas celle que l'on donne habituellement, après on peut toujours partir d'une autre définition.

Cdt

[Médiat]

Justement, avec le théorème de complétude ces deux définitions sont équivalentes (tout ce que je voulais dire, c'est que la précision "cohérente" n'apporte aucune information, sauf à but pédagogique).

Le théorème de complétude est comme l'air, même si on ne le voit pas, il est indispensable à la survie

[PlaneteF]

Justement, avec le théorème de complétude ces deux définitions sont équivalentes (...)

Oui, et c'est bien ce que je voulais dire par "après on peut toujours partir d'une autre définition" ... sous-entendu "... et ensuite par le théorème de complétude on retombe sur l'autre définition". On dit donc bien la même chose depuis le début, de mon côté je voulais juste voir où tu voulais en venir.

(...) sauf à but pédagogique

J'étais effectivement dans cette idée là, déjà pour valider la compréhension des choses, et aussi comme je me plais à le dire souvent "Futura est potentiellement lu par des milliards de personnes à travers le monde"

Cdt

[PlaneteF]

déjà pour valider la compréhension des choses

Enfin valider la mienne de compréhension, pas la tienne !

[inviteface0172]

Non, la quantification porte sur U_0

1/Oui mais f : U_0->U_n, la fonction qui a U_0 associe (U_n) suite de Goodstein est calculable comme tu l'as rappellé cela suffit-il à en faire une fonction exprimable dans AP strictement ?

2/Comment change-t-on une théorie (sans changer la logique) pour la rendre récusirve ?
Si on ajoute un axiome, quel est-il ?
Sinon comment procéde-t-on ?

Je prèfére laisser Médiat se reposer et demander à quelqu'un d'autre, qui n'a pas peur des questions même bêtes.

Merci, encore à lui d'avoir accépter de répondre à mes questions.