Indécidabilité ?

merci Christophe (je ne suis pas l'auteur de ce fil).
mais ton point 6) me semble important ici (il "démontre" d'ailleurs ton point 7)): mais alors la tentative de Cohen (cf plus haut) de démontrer Riemann par l'indécidable est-elle absurde??
Bruno, merci. Mais peux-tu clarifier ton propos sur Syracuse et vous mettre d'accord sur les énoncés de ce type ?
merci

Pour Logic.

Ce que je dis c'est que l'énoncé de Goldbach s'écrit :
$$\forall\,p\ \exists\,q\ \exists\,r \cdots$$
A priori, ce n'est pas parce que $p$ est standard que $q$ et $r$ le sont ; mais dans le cas de l'énoncé de Goldbach, comme $2\,p$ est la somme de $q$ et de $r$ on a : $\max(q,r) < 2\,p$ ; or tout entier majoré par un entier standard est standard.

Autrement dit, un énoncé commençant par une suite de quantificateurs universels suivie d'une suite de quantificateurs existentiels {\bf bornés} est valide sur les entiers standards dès que sa négation n'est pas déductible des axiomes de Peano.

Bruno

salut
personne ne sait ???

Bruno, bonjour.

Cela a l'air de la réponse la plus "sage" qui puisse être donnée.

Même si elle laisse les rèveurs, les aventuriers téméraires sur leur faim.

Selon toi, nous devrions bannir du vocabulaire mathématique les mots "vrai", "faux" ou les expressions "ni vrai ni faux", "vrai ou faux"
pour les remplacer par "déductible...", "non déductible..." ?

Jules Renucci Écrivait:

---

> Selon toi, nous devrions bannir du vocabulaire
> mathématique les mots "vrai", "faux" ou les
> expressions "ni vrai ni faux", "vrai ou faux"
> pour les remplacer par "déductible...", "non
> déductible..." ?

Je sais que la question ne s'adresse pas à moi et je ne prétends pas répondre pour Bruno, mais je soutiens néanmoins cette position ; à titre personnel je n'utilise "vrai" et "faux" que pour les modèles, non pour les théories.

Pour répondre à Logic : par définition, une proposition p est indécidable dans une théorie T si T U {p} est consistante et T U {non p} est aussi consistante. C'est à dire qu'il existe des modèles dans lesquels p est "vrai" et d'autres dans lesquelles non p est "vrai". Pour les modèles le problème est légèrement différent car la théorie d'un modèle est complète, il n'y a donc pas de proposition indécidable pour cette théorie.

Bruno a fait remarquer que dans le cas particulier de la théorie de Péano un modèle particulier (le modèle standard) était "inclus" dans tous les modèles (je mets "inclus" entre guillemets car une simple inclusion ensembliste ne suffirait pas), ce qui permet pour certains énoncés indécidables dans la théorie de Péano d'affirmer que ces énoncés sont "vrais" dans le modèle standard (voir le post de Bruno pour plus d'explications et un exemple).

Je vois mal comment une proposition peut être indécidable dans une théorie et "vraie" dans tous les modèles de cette théorie (c'est contraditoire avec la définition), ce qui est par contre possible (mais ce n'est pas le cas de toutes, j'ai donné un exemple) c'est qu'une proposition indécidable dans Péano soit "vraie" dans le modèle standard (exemple de Bruno).

Je dois avouer que je ne connais pas les travaux de Turing auxquels tu fais allusion (si tu as un lien ...), aurait-il eu des préoccupation constructiviste ?

J'ai l'impression que le forum ne marche pas correctement par moments. S'il y a doublon je le cacherai.

Pour Mediat.

Je suis d'accord avec ton usage du terme d'énoncé vrai pour un modèle donné de la théorie ; les jours de pédanterie, j'utilise l'expression "sémantiquement valide" .

Pour Jules.

Salomon, lui, savait se tenir à ses proclamations. Justement le ";)" signifie que je suis le premier à violer mes principes (mathématiques) si je le juge utile.

Bruno

Logic Écrivait:

---

> merci à vous tous d'alimenter ce beau débat !
> Mediat et Bruno, faut-il en déduire que "vrai dans
> le modèle standard" signifie "vrai dans tous les
> modèles" puisque ce standard est inclu dans tous
> les autres ?

J'ai donné l'exemple d'une propriété indécidable dans Peano (donc sémantiquement valide (ça me plait bien ) dans au moins un modèle), mais "fausse" (c'est plus court B-)-) dans le modèle standard), si tu prends la négation de cette propriété elle est vrai dans le modèle standard et fausse dans d'autres modèles.

Intuitivement une propriété peut-être vraie pour tous les éléments standards, cela ne veut pas dire qu'elle est vraie pour tous les éléments de tous les modèles.

D'une façon plus générale, le théorème de Gödel dit que l'arithmétique de Peano n'est pas complète (il dit même plus que cela), il existe donc des propositions vraies dans le modèle standard (puisque sa théorie est complète) qui ne sont pas des théorèmes de la théorie de Peano, donc qui sont fausses dans d'autres modèles.

Je cite les propos de Marcus du Sautoy que j'évoquais ci-dessus :


> Voici l’intégralité de la citation prise dans le
> livre de Marcus du Sautoy, page 311 :
>
> « Si Cohen a le même succès et démontre que
> l’hypothèse de Riemann est indécidable à partir
> des axiomes des mathématiques, il aura prouvé que
> l’hypothèse est en fait vraie !
> Si elle est indécidable, alors, soit elle est
> fausse et nous ne pouvons le démontrer, soit elle
> est vraie et nous ne pouvons le démontrer. Mais si
> elle est fausse, alors un zéro doit échapper à la
> droite critique, un zéro que l’on peut utiliser
> pour prouver qu’elle est fausse. Elle ne peut être
> fausse sans que nous ne puissions le démontrer.
> Par conséquent, la seule façon qu’a l’hypothèse de
> Riemann d’être improuvable est d’être vraie, mais
> nous ne pouvons toujours pas démontrer que tous
> les zéros se situent le long de la droite. Turing
> fut l’un des premiers à entrevoir la possibilité
> d’une confirmation aussi étrange de l’hypothèse de
> Riemann. Mais rares sont ceux qui croient que
> c’est avec des ruses logiques de cette nature que
> l’on réussira à résoudre le huitième problème
> d’Hilbert. »

J'aimerais simplement que Mediat, Bruno, et d'autres me disent simplement s'ils contestent ces propos qui, je le redis, émanent d'un spécialiste, professeur à Oxford et qui intervient au Collège de France.
J'en profite pour, à nouveau, recommander la lecture de son ouvrage "La symphonie des nombres premeirs"

Bruno, voici les référence du livre en question :

Publié aux Editions Héloïse d'Ormesson
Traduit avec le concours du Ministère de la Culture et de la Communication
dans le cadre du Fonds Jules Verne
Traduit de l'anglais par Raymond Clarinard
Titre original : The Music of de Primes
Marcus du Sautoy 2OO6 Traduction française 2005

Ont partcipé à la lecture et aux corrections :

Leonard Aldeman, Sir Michael Berry, Enrico Bombieri, Paula Cohen,Jon Keating, Jeff Lagarias, Hugh Montgomery, Ron Rivest etc

cordialement,

non lg, dans ce cas précis, c'est jules qui a raison. L'hypothèse de Rieman est prouvablement équivalente à un énoncé qui affirme qu'une certaine équation diophantienne n'a pas de solution (je ne sais plus où je l'ai lu, mais je parierais gros). De même en ce qui concerne Syracuse.

L'indécidabilité (dans une théorie respectable) des énoncés du genre "il n'existe pas de solution à telle équa diophantienne" implique leur vérité.

Soit E une équation diophantienne: soit n un uplet d'entiers solution de E. L'énoncé "n est solution de E" est prouvable et il implique "il existe une solution pour E", qui donc est aussi prouvable.

En ce qui concerne l'énoncé strictement fidèle de Rieman (sans parler d'un équivalent), effectivement, il me semble qu'un zéro en dehors de la droite critique entraine la prouvabilité de l'existence de ce zéro. Ce n'est pas du tout évident*, certes, mais je crois que c'est connu.

*D'une part c'est un nombre complexe pas forcément accessible exactement au langage, d'autre part, quand bien même, il y a un petit travail à faire pour montrer que "c'est un zéro": compte-tenu de l'énoncé de Rieman, il me semble que sa complexité est inférieure à "pour tout entier n il existe un entier p tel que (n,p) est solution de E" (E étant une équation diophantienne bien choisie au départ). Faudrait demander ça au spécialistes du forum, il doivent savoir

bonjour,
Christophe comment peux-tu être si sûr que Golbach ne peut être prouvée indécidable et traduite en équation diophantienne sans solution ? Toi et Bruno devriez peut-être vous mettre d'accord sur ce point.
Lg, j'imagine mal un énoncé à la fois indécidable dans une théorie, impossible à démontrer faux quelque soit la machine utilisée ou le temps choisi, et pourtant impossible à démontrer vrai dans cette théorie si ce n'est "vrai jusqu' àun point et indécidable au-dessus"...
Jules, comment peux-tu affirmer si sûrement que Syracuse soit vraie si indécidable au vu des difficultés dont parlent nos intervenants ?
Il me semble que ce qui nous agite n'est autre que la définition originale de Godel de l'indécidabilité : nous aurions du mal à nous imaginer qu'une phrase comme "je suis démontrable" soit vraie dans tous les modèles sans être démontrable...et ceci est une source constante de confusion !

Logic Écrivait:

---

> bonjour,

> > Lg, j'imagine mal un énoncé à la fois indécidable
> dans une théorie, impossible à démontrer faux
> quelque soit la machine utilisée ou le temps
> choisi, et pourtant impossible à démontrer vrai
> dans cette théorie si ce n'est "vrai jusqu' àun
> point et indécidable au-dessus"...

je veux dire par là que jusqu'a une limite connue ces conjectures sont vraies: il n'y a pas de contre exemple!
donc si on arrivait à montrer qu'elle sont indécidable, c'est bien au dessus de ces limites connues sans contre exemple.


> Jules, comment peux-tu affirmer si sûrement que
> Syracuse soit vraie si indécidable au vu des
> difficultés dont parlent nos intervenants ?

dans un sens il a raison, c'est ce que ma répondu christophe; syracuse est pour linstant vrai jusqu'a une limite et si il montrait que cette conjecture est indécidable cela aurait la même équivalence que si elle était vraie. ce ne serait pas pour autant un théorème, ce que n'a pas dit jules.

Si Syracuse était faux, il existerait une suite d'entiers B, multiples de 3 qui tend vers l'infini et qui serait prouvable.

christophe chalons a écrit:

Contraposée: si (2) n'est pas prouvable dans l'arithmétique alors l'énoncé "non(2)" est vrai.

Si je comprends bien, c'est à dire si "vrai" dans cette phrase veut dire "vrai dans le modèle standard de l'arithmétique", alors ceci est un cas particulier (plus simple) de ce que disais Bruno dans un post précédent, ai-je bien compris ? Si oui, je trouve ce genre de phrase, hors contexte (ici le contexte est fixé par la phrase précédente, dans laquelle on comprend bien que entier signifie entier standard) bien dangereuse, différents échanges sur ce fil l'atteste.

Merci christophe pour ces précisions et explications.

Pour Jules Renucci.

1°) La date de parution de l'ouvrage prouve qu'il ne date pas de la période où le forcing semblait un jouet merveilleux. L'assertion de Marcus du Sautoy n'est donc certainement pas le fruit d'un enthousiasme excessif.

2°) Le nom de Cohen fait penser irrésistiblement au forcing, mais celui-ci n'a rien à faire en tant que tel dans cette histoire, donc j'ai déraillé sur ce point.

3°) Tel qu'il est exposé dans ce sujet, l'argument me semble douteux : en fait, nous n'avons pas de modèle standard des nombres réels donc "vrai" et "faux" me paraissent assez hypothétiques.

4°) Les arguments mis en avant par C.C. sur l'équivalence entre l'énoncé de l'hypothèse de Riemann et l'existence de solutions d'une équation diophantienne ouvrent des espaces où je me sens totalement incompétent. Donc la validité de mon doute s'arrête là. Désolé.

Bruno

Bonsoir à tous

Je cite ici un extrait d'un papier de Jean Paul DELAHAYEdont vous pouvez trouver l'intégralité sur le site " Interstices"
Citation :

"Prenons, pour le montrer, le cas simple de la conjecture de Goldbach : Tout nombre pair à partir de 4 est somme de deux nombres premiers. Si elle est fausse, c'est qu'il y a un nombre pair dont aucune décomposition sous forme de sommes de deux nombres ne comporte deux nombres premiers. Si un tel nombre existe, alors ce résultat d'arithmétique émentaire est toujours découvert par un système intéressant. Donc si une théorie montre que Goldbach est indécidable, alors elle montre qu'on ne peut trouver aucun nombre pair qui ne soit pas somme de deux nombres premiers, et donc elle démontre Goldbach.

On peut avancer le même raisonnement sur la conjecture de Riemann RH : si on démontrait qu'elle est indécidable vis-à-vis d'un système intéressant, on aurait démontré qu'elle est vraie (autrement dit, il n'y a pas d'espoir, même à long terme, qu'on se retrouve dans la situation de HC). Pour P non NP, rien de tel, et même si aujourd'hui on a repere une serie d'obstacles sur le chemin d'une preuve que cet énoncé est indécidable relativement à un système fort, on pourra peut-être y arriver, auquel cas se posera alors vraiment la question de l'adopter comme nouvel axiome. Autrement dit : il est encore moins justifié
d'adopter P non NP comme axiome que RH."


http://interstices.info/probleme-np

Logic,

Pour compléter : ce que je voulais dire par "dangereux" est parfaitement illustré par le texte de Jean Paul DELAHAYE cité par Jules Renucci.

Donc si une théorie montre que Goldbach est indécidable, alors elle montre qu'on ne peut trouver aucun nombre pair qui ne soit pas somme de deux nombres premiers, et donc elle démontre Goldbach.

Puisque cette phrase qui se présente comme un paradoxe (si je peux démontrer que je ne peux pas démontrer telle propriété, alors j'ai démontré cette propriété), alors que ce n'est un tour de passe-passe, la formulation rigoureuse serait :

Donc si une théorie contenant l'arithmétique de Peano montre que Goldbach est indécidable, alors elle montre qu'on ne peut trouver aucun nombre entier standard pair qui ne soit pas somme de deux nombres premiers standard, et donc elle démontre Goldbach pour le modèle standard.

Et adieu le paradoxe qui n'était qu'apparent (et à nouveau : cf. Bruno).

merci Mediat, nos messages se sont croisés. Je constate pourtant que les intervenants se divisent en deux : ceux qui pensent que Goldbach et Syracuse ne peuvent être indécidables, et ceux -comme toi- qui pensent le contraire. Un accord est-il possible ?
ensuite il me semblait que Godel avait démontré "je ne suis pas démontrable" pour tous les modèles ?? non ? alors comment traduirais-tu cette phrase à son tour ?

Je constate pourtant que les intervenants se divisent en deux : ceux qui pensent que Goldbach et Syracuse ne peuvent être indécidables, et ceux -comme toi- qui pensent le contraire. Un accord est-il possible ?

Je ne crois pas que le "désaccord" soit si profond, tout le monde, je pense, est persuadé que si Goldbach est indécidable, alors elle est vraie dans le modèle standard, la seule différence, c'est que je me refuse à l'écrire "si Goldbach est indécidable, alors elle est vraie", car hors contexte, ce n'est qu'un oxymore.

(Pour mémoire : la version "si Goldbach était indécidable, alors elle serait vraie dans tous les modèles" serait une demonstration (si c'était prouvé, ce qui n'est pas le cas) par l'absurde que Goldbach n'est pas indécidable)

Une tentative d'explication de cette différence peut tenir dans la différence entre un logicien (et un modèle-théoriste en particulier pour qui tous les modèles ont droit de cité) et un théoricien des nombres uniquement intéressé par le modèle standard (du coup, pour lui, ce modèle va sans dire)

Etonnant tout de même que Delahaye confonde entiers et entiers standard, non ?! ..

GG a écrit:

Etonnant tout de même que Delahaye confonde entiers et entiers standard, non ?! ..

Je ne crois pas qu'il les confonde, je crois qu'il fait un abus de langage (assez habituel, Girard fait le même, et ce ne sont pas les seuls) qui, hors contexte, peut être très mal compris (Je dois avouer que la forme paradoxale est tellement tentante que je ne serais pas étonné que cet abus de langage soit parfois volontaire (il s'agit d'un procès d'intention, j'en ai bien conscience, j'ai exprimé une autre explication, ci-dessus, hier à 20h47)).

Pour Logic.

Un énoncé E "vrai dans tous les modèles d'une théorie" alias "universellement valide dans tout modèle de la théorie" est déductible de cette théorie.

En effet, d'après le théorème de complétude du calcul des prédicats du premier ordre (ouf) toute théorie non contradictoire admet un modèle.

Donc si "T et (non E)" n'a pas de modèle, alors "T et (non E)" est une théorie contradictoire et, d'après le théorème de raisonnement par l'absurde, l'énoncé E est déductible de T.

Revenons à la phrase "je ne suis pas démontrable", si elle était vraie dans tous les modèles, elle serait démontrable (:P) !

Bruno

Jules Renucci a écrit:

Penses-tu sérieusement que des mathématiciens d'un tel poids se livreraient volontairement à des abus de langage uniquement dans le but de ruser avec la logique? Je pense que c'est leur faire un mauvais procès et que la meilleure formule eut été de ta part : "Je ne comprend pas la position de X ou de Y ..."

J'avoue ne pas bien cerner où tu veux en venir, dans le post que tu cites j'ai écrit :

Médiat a écrit:

(Je dois avouer que la forme paradoxale est tellement tentante que je ne serais pas étonné que cet abus de langage soit parfois volontaire (il s'agit d'un procès d'intention, j'en ai bien conscience, j'ai exprimé une autre explication, ci-dessus, hier à 20h47)).

J'ai mis en gras les passages qui, me semble-t-il, auraient dus t'apporter les explications nécessaires sur ma position.

Le fil est très long, je n'ai pas tout lu.

Par contre, il m'a semblé voir une confusion importante: personne n'a dit que Goldbach ou Syracuse ne peuvent être indécidables.

On a juste dit que leur indécidabilité implique leur vérité.

Le théorème est le suivant: si l'énoncé "la conjecture de Goldbach est indécidable" est prouvé dans une théorie T "correcte" (par exemple, Peano, ou ZF ou ZFC)) alors la théorie T est contradictoire.

Il se peut par contre tout à fait que la conjecture de Goldbach (ou autre de ce genre) soit indécidable.

Ensuite, il faut être attentif à "de quoi on parle". Par exemple, un entier n non standard contre-exemple à Goldbach donne lieu à une "preuve" (non standard) de "non(Goldbach)", preuve qui consiste juste à rédiger le "constat" que n est un contre-exemple.

Pour autant, un entier non standard n contre-exemple à goldbach suppose qu'on s'est placé dans un modèle de l'arithmétique (par exemple), que ce modèle contient un sous-ensemble A non plein d'entiers contenant 0 et stable par successeur, et que n n'est pas dans A, et que n n'est pas somme de 2 nombres premiers dans ce modèle. La "tradition populaire" (enfin du peuple logique) étant de dire que A contient tous les entiers standards (et peut-être plus!!!).

Pour "les êtres humains" l'existence d'un tel entier, dans un tel modèle n'est pas une réfutation acceptable de Goldbach.

Notez aussi une chose peu souvent mise en avant et pourtant banal. Il existe des preuves de choses qui sont fausses, dans la mesure où le mot "preuve" est défini correctement dans un modèle de l'arithmétique: dans tous les modèles contenant des entiers non standards de l'arithmétique, il existe une preuve (non standard) dont la conclusion est FAUSSE. Par exemple: prenez un entier non standard écrit sous la forme (1+1+1+1...+1) et prouvez qu'il est standard de la manière suivante:

1 est standard, donc 2 est standard, donc 3 est standard, .... donc (1+1+1..+1) est standard.

A propos de la phrase P:="je suis indémontrable": comme l'a rappelé Bruno, il existe des modèles où elle est fausse. Ces modèles contiennent une "preuve" de P.

De toute façon cette phrase n'a de sens que si vous précisez le sens que vous donnez au mot "démontrable". En maths, seul le mot "démontrable dans la théorie T" a un sens. La phrase P telle quelle est en quelque sorte une phrase dynamique qui change de sens avec le changement de sens du mot "démontrable".

Un aspect méconnu est très excitant des astuces Godélo-cantoriennes (mais méfiez-vous, il sont tous les 2 devenus très malheureux et se sont laissés ou fait mourir) est le théorème suivant, qu'on peut résumer en des termes non politiquement corrects:

Au fond, il existe des choses prouvées et fausses de quelque manière qu'on s'y prenne (et pourtant ça n'a pas l'air trop dangereux pour la science d'ignorer ce point)

Preuve: soit I l'énoncé "tout ce qui est prouvé est vrai" (en apparence, I parait être difficile à construire mathématiquement, mais en fait c'est juste de la logique du second ordre, associée (c'est là le "problème") à un prédicat "prouvable": $\forall X D(X)\to X$)

Soit P la phrase "mon contraire est démontrablement impliqué par I"

Supposons I et P, alors "I implique nonP" est prouvé (puisque P) et d'après I, I implique nonP, et donc non P et donc contradiction. Donc I implique bien nonP. Le raisonnement ainsi produit devrait être considéré comme une preuve du fait que I implique nonP et donc une preuve de P. Et, finalement, une preuve de nonI.

La seule chose que je puisse évoquer comme justification de ce que je vais dire maintenant est mon expérience de la logique (c'est un témoignage, rien de plus):

* il existe des preuves (non standards) de choses fausses, ces preuves sont autant des preuves que les entiers non standards d'un modèle sont des entiers pour le modèle.

* il existe un argument dynamique (celui que je viens d'écrire avant les "étoiles") qui conduit à la conclusion que selon toute vraisemblance il n'y a pas d'absolu: plus une preuve est subtile, plus elle pourrait être un "empaquetage" d'une preuve plus directe, concrete (mais plus longue) dont la conclusion est fausse***. Tout se passe un peu comme si le chemin qui mène du sûr au sûr que non était connexe et que la mégalomanie de certains axiomes nous rapprochent d'une frontière (qui n'existe pas, puisque connexité) entre les 2 territoires.


*** par exemple, il y a besoin d'un acte de foi supplémentaire pour croire que si ZFC démontre que telle équation diophantienne a une solution alors "elle en a vraiment une". Un truc amusant, mais qui paralyse vite les ordinateurs est la tentative de cerner la croissance de la fonction suivante: à chaque preuve DANS ZFC dont la conclusion est "telle equa E dioph a une solution" associer le premier uplet solution dans l'odre lexicographique de E


Pour illustrer tout ça, les participants à ce fil vont se régaler de l'exercice suivant:

On définit la fonction d'Akcermann A de la manière suivante (procedure récursive):

A(0,n):=n+1 pour tout n entier
A(n+1,p+1):=A(n,A(n+1,p))

Il est bien connu que le calcul A(n,p) se termine pour tout couple (n,p).

Prouvez que A(100,100) est standard de chez standard!

Conclusion: il ne faut pas abuser du mot "standard".