Comments on Que signifie : P=NP indépendant de ZFC ?

DM (2011-05-29T16:21:34Z)

En fait, je pensais en termes un peu « philosophiques ». La plupart des énoncés indécidables sont ésotériques et/ou parlent de preuves dans la logique. Là, on aurait un énoncé assez « concret » et combinatoire, servant d'argument dans divers raisonnement à portée concrète (crypto clef publique, p.ex.)…

Mazoit (2011-05-19T08:18:16Z)

Je trouve l'histoire du « vrai » amusante parce que j'ai pas mal évolué sur ce point.

Maintenant, mon point de vue est le suivant. On a des objets intuitifs (comme les entiers) avec lesquels ont forme des propositions (2+2=4, \forall n \exists m m>n, …). On peut directement tester la véracité « intuitive » de la première mais pas de la seconde. Cela ne change pas le fait qu'intuitivement, on puisse imaginer tester la seconde pour toute les valeurs possibles de n. Les propositions sont donc intuitivement vraie ou fausse.

Mais pour certifier que certaines propositions sont vraie, on se donne des règles qui vont permettre de démontrer des choses. Ça passe pas une modélisation des objets et des règles d'inférences. Dans l'ideal, la modélisation des objets correspondrait à l'idée intuitive qu'on s'en fait et les règles d'inférences permettraient de démontrer tout ce qui est intuitivement vraie et juste ce qui est intuitivement vrai.

J'interprète « le Théorème « sur lequel on (et sans doute moi) raconte beaucoup de bétises » comme le fait que, bad luck, on ne peut pas prouver tout ce qui est intuitivement vrai.

On peut donc imaginer:
- que la modélisation des objets est fidèle et qu'on puisse ajouter des axiomes qui seraient intuitivement faux et faire comme s'ils étaient vrais sans que ça ne pose de problèmes ;
- qu'aucune modélisation des entiers ne soit parfaitement fidèle et donc qu'on puisse ajouter des axiomes pour préciser les choses ;
- d'autres choses encore.

Sauf que moi, j'en perds mon intuition. Si on prends l'axiome du choix, intuitivement il est vrai. Mon intuition est fondée sur des ensembles finis il est vrai dans ce cadre. Sauf que Banach-Tarski… Donc vrai, faux, je ne sais pas. J'ai donc décidé de ne plus m'intéresser à ce qui est intuitivement vrai. Je pose des axiomes qui me semblent raisonnables (qui ne soient pas complètement contradictoires avec mon intuition) et puis j'essaye de modeler mon intuition en fonction des théorèmes qui découle de ces axiomes. Ce qui est « vrai » ne m'intéresse pas.

Vicnent (2011-05-16T13:39:07Z)

Ruxor : pour te connaitre un peu au sens de "je te connais comme on peut connaitre quelqu'un dont on lit le blog depuis longtemps", je peux t'assurer que sur la partie "sérieux problème", c'est au mieux très maladroit, au pire insultant et surtout très arrogant, même si avant de lire ta justification (J'ai lu la suite, et je suis d'accord avec toi : c'est quoi 'vrai' etc. Je pense que c'est juste mal exprimé et tendancieux.), j'avais une petite idée de ce que tu voulais indiquer.

Pour le reste, c'est une belle entrée qui demande un peu de temps et de calme.

Kenny (2011-05-16T02:06:26Z)

Je peux très bien être ultraformaliste (dans le sens ou le vrai mathématique
n'existe pas en tant que tel, il n'y a que du vrai "dans X") et admettre
que le monde qui nous entoure puisse être bien décrit par telle ou telle théorie
mathématique, qui n'est vue ici que comme un moyen pour exprimer une théorie physique (qui est falsifiable, elle).
Si la calculatrice affiche bien le même résultat pour les
deux opérations, ce n'est pas le résultat associé de ZFC qui est confirmé, c'est la théorie physique qui dit : "cet objet (la calculatrice) que j'ai construit ainsi, va produire tel ou tel résultat (sortie) si j'appuie sur telles ou telles touches (entrée)". Les détails étant exprimables dans la théorie ZFC (ou PA, ou autres, peu importe) dans le sens ou l'entrée et la sortie sont reliés par un théorème de ZFC. J'insiste sur le fait que ZFC n'est pas testé, c'est plutôt le fait que j'ai réussi à construire un objet qui se conforme bien aux règles de ZFC qui est expérimentalement vérifié.

D'autre part, je peux aussi être ultraformaliste et ne pas chercher une démonstration de CH parce que je pense que ZFC est consistant (au sens physique : je pense que ce jeu de symboles à partir de ZFC ne peux pas aboutir à une contradiction, ce qui est expérimentalement vérifié, mais peut se révéler faux, bien sûr). Du coup, je ne cherche pas une démonstration de CH pour pas perdre de temps.

Pour le dernier point, un ultraformaliste n'admet "vrai" aucun énoncé de l'arithmétique, justement. Il peut seulement
être vrai dans X, faux dans Y, etc.

Ruxor (2011-05-15T23:09:03Z)

Kenny → Cf. ma dernière réponse à Touriste. Si on veut être ultra-formaliste et considérer que tout ce qu'on fait en maths est un petit jeu typographique où on manipule des suites de symboles dénuées de sens le but étant de construire des suites appelées « démonstrations » dont la dernière ligne est appelée « théorème », c'est une position inattaquable. Mais il faut en assumer les conséquences : si je tape 12345×67890 sur ma calculatrice et qu'ensuite je tape 67890×12345, je ne dois pas spécialement m'attendre à trouver le même résultat, parce que ce qui pour les matheux un peu platonistes est un théorème qui me garantit que je trouverai le même résultat (la commutativité de l'addition) est réduit à une suite de symboles sans signification (c'est « vrai dans ZFC » au sens démontré dans ZFC, mais pourquoi serait-ce forcément vrai sur ma calculatrice si ZFC n'est qu'un jeu typographique ?). Et plus concrètement, un formaliste pur doit continuer à chercher dans ZFC une démonstration de l'hypothèse du continu, parce que le théorème qui dit qu'elle n'est pas décidable si ZFC est consistant est juste un théorème de ZFC, donc de nouveau dénué de signification, ça ne dit pas que sur ma feuille de papier je ne vais pas pouvoir trouver de démonstration de l'hypothèse du continu (dans ZFC).

Si on admet que ZFC peut faire des prévisions correctes sur ce qui va se passer dans ma calculatrice ou sur ma feuille de papier (que ce soit le fait que 12345×67890 soit pareil que 67890×12345 ou le fait qu'il soit impossible autant que j'essaie de démontrer l'hypothèse du continu ou l'inconsistance des axiomes de Peano), alors on n'est plus purement formaliste, on a admis que le petit jeu formel auquel on joue est capable de dire des choses sur le monde qui nous entoure, y compris sur le petit jeu formel lui-même. La position encore très formaliste mais pas aussi ultra-formaliste que celle du paragraphe précédent est de dire « OK, j'admets que ZFC a des conséquences qui sont vraies si elles sont testables sur ma feuille de papier » (donc si ZFC dit que les axiomes de Peano sont consistants, j'admets que je ne pourrai pas trouver de démonstration de 0=1 dans les axiomes de Peano). L'ennui, c'est que si on essaie de n'admettre comme « vrais » pour les énoncés arithmétiques *que* ceux qui sont démontrables dans ZFC, alors *ce principe lui-même* a des conséquences qui échappent à ce principe lui-même ! (Pour commencer, on est bien obligé d'admettre que ZFC est consistant, parce que s'il prouvait 0=1, on aurait effectivement zéro balle dans une boîte quand il y en a une, ce qui n'est pas le cas. Or ZFC ne prouve pas que ZFC est consistant : on a été obligé d'admettre comme « vrai » quelque chose que ZFC ne prouve pas.) Donc la position s'effondre.

Kenny (2011-05-15T22:34:50Z)

Je ne vois pas pourquoi la position du formaliste serait celle que tu lui donnes.
Un formaliste pur serait plutôt pour équivalence entre "être vrai" et "être démontrable". Il ne reste plus qu'une tautologie :
"Je ne considère vrai dans X, que ce qui est démontrable dans X". Le X pouvant
être ZFC, PA, etc… en mathématiques, ou bien un cadre métamathématique quelconque(suffisant pour parler de théories, langages, etc).
Et là, l’auto-contradiction dont tu parles n'apparaît plus.

Camille (2011-05-15T22:24:56Z)

Merci. Si c'est juste le sucre syntaxique habituel alors ça me va !

Cela dit je suis toujours turlupinée par le *vrai* de ton deuxième paragraphe avec Serre et HR. Je ne vois pas ce qu'il signifie. Quand au dernier paragraphe à cette heure-ci il me fait mal aux neurones. Je réessaye… Non je ne comprend vraiment rien.

C'est assez marrant de se dire qu'on peut faire des maths sans comprendre ça. Mais c'est assez flippant aussi. T'as des conseils de lectures sur le sujet pour un matheux ordinaire ?

Ruxor (2011-05-15T21:58:19Z)

Camille → Je ne vois vraiment pas comment je peux expliquer ce que « vrai » veut dire, à part que « “2+2=4” est vrai » signifie la même chose que « 2+2=4 » (ou « “‘2+2=4’ est vrai” est vrai » et ainsi de suite)… C'est juste la façon dont on lit une implication : « A⇒B » se lit « si A [est vrai] alors B [est vrai] », le « est vrai » est là pour la clarté syntaxique (enfin, c'est un peu raté côté clarté si ça plonge les lecteurs dans un profond désarroi philosophique). Donc, quand je dis « si HR n'est pas réfutable dans ZFC, alors HR est vraie », ça veut dire « “HR n'est pas réfutable dans ZFC” ⇒ HR » (et je peux démontrer ceci dans ZFC ou dans des systèmes beaucoup plus faibles, comme Peano ou IΣ_1).

Et je ne suis pas d'accord avec l'idée que quand les matheux non-logiciens disent « vrai » ils veulent dire « démontrable ». Il se trouve, oui, que la façon dont on sait que les choses sont vraies, en mathématiques, c'est normalement qu'on en a une démonstration. Mais quand Serre fait remarquer que nous avons beaucoup de raisons de penser que l'hypothèse de Riemann est *vraie* (des raisons du style : expériences numériques, généralisations naturelles qui semblent aussi vraies, transposition à d'autres cadres, analogie avec les distributions de valeurs propres de matrices aléatoires, etc.), je ne crois vraiment pas qu'il confonde et s'imagine que ce sont des raisons de penser qu'elle est *démontrable*.

Et ce qui est rigolo, c'est que la position purement formaliste « je ne considère comme vraies que les choses pour lesquelles il existe une démonstration dans ZFC » ne tient pas, parce que cette position revient à tenir pour vrai au moins l'axiome « si P est un énoncé arithmétique et si ZFC démontre P, alors P est vrai » (je répète que « est vrai » est juste du sucre syntaxique : l'affirmation est « si ZFC démontre P alors P »), et cet axiome est exprimable dans le langage de ZFC et ce n'est pas un théorème de ZFC. (Donc, si on veut, la position « je ne tiens pour vraies que les conséquences de ZFC » est auto-contradictoire…)

Bon, comme les gens ont des avis vraiment enflammés sur la question, je rajoute ça dans ma TORANT-list.

Camille (2011-05-15T17:11:45Z)

David, j'ai peine à croire que tu ne fais pas semblant de ne pas comprendre.

<<
Si un théoricien des nombres dit que « depuis les résultats de Wiles, nous savons que le théorème de Fermat est vrai », les gens ne lui demandent pas « qu'est-ce que vous voulez dire au juste par “vrai” ? vrai dans quels entiers naturels ? ».
>>

Non. Evidemment. Quand un matheux non logicien nous dit qu'un énoncé éloigné de la logique est vrai, on comprend qu'il veut dire que c'est un théorème (on peut éventuellement se poser des questions sur le jeu d'axiome utilisé par contre).

<<
Mais quand un logicien essaie de parler à un non-logicien, le non-logicien a tendance à demander précisément ça.
>>

Oui. Evidemment. Quand la personne qui parle sait que vrai et faux ont un sens précis en théorie des modèles et quand on a des raisons de soupçonner que peut-être il l'utilise dans ce sens là il est naturel de lui poser la question. Surtout quand on n'y connait pas grand chose à tout cela. Et surtout quand la personne insiste sur le mot vrai (attention, je ne l'utilise pas comme chez les matheux ordinaire pour dire "est un théorème). Ou quand il le met en italique. Alors on se demande si on peut remplacer "vrai" par "est un théorème" ou pas etc. Des questions naturelles non ? Au moins quand on n'est pas familier avec tout cela.

Je ne comprend toujours pas ce que tu ne comprends pas en fait.

Bon et puis, que veux-tu dire "vrai" alors dans ton texte ? (Je me suis arrêté à la première occurence du mot).

Ruxor (2011-05-15T11:45:12Z)

hijodelachingada → L'affirmation Consis(Peano) qui signifie par définition « les axiomes de Peano démontrent 0=1 » n'est ni prouvable ni réfutable dans les axiomes de Peano. Ça veut dire que le système formel Peano + ¬Consis(Peano) est consistant : il n'en demeure pas moins que ¬Consis(Peano) est faux (comme tu le dis, c'est un axiome débile : tu peux le prendre si ça t'amuse, mais un axiome qui dit « il existe chez Peano une démonstration de 0=1 » sans qu'il y ait une telle démonstration, ben c'est juste faux, même si ça n'apporte pas de contradiction).

Touriste → Je sais que tu aimes bien jouer à ce petit jeu comme quoi tu ne sais pas ce que « vrai » veut dire. Je ne peux rien répondre à part que je te laisse jouer tout seul à ce jeu. Je laisse juste deux idées à ta réflexion :

‣ Le fait que Banach-Tarski ou sa négation puissent être des théorèmes selon les axiomes qu'on prend, ça signifie juste que tout le monde n'est pas d'accord sur ce qu'est « un ensemble », c'est aussi peu profond que de faire remarquer que xy=yx peut ou peu ne pas être vrai dans un anneau, selon que par « anneau » on désigne les anneaux commutatifs ou les anneaux non nécessairement commutatifs… Cela ne dit rien de spécialement intelligent sur le « vrai ». (De même, on peut décider de jouer dans un système formel dans lequel on aura permuté le sens du symbole 3 et du symbole 4, de sorte que 2+2=3, ça ne rend pas spécialement vrai le fait que 2+2=3.)

‣ Mais par ailleurs, si tu veux jouer au formaliste pur et dur « la seule chose qui m'intéresse, ce sont les théorèmes que je vois effectivement découler de ZFC (et je dis juste que ce sont des théorèmes, parce que je ne sais pas ce que “vrai” signifie) », alors tu dois aussi considérer tous les énoncés du style « machin est indémontrable » comme des blabla typographiques dénués de sens. Par exemple, si un matheux démontre, dans ZFC, « HR n'est pas démontrable dans ZFC si ZFC est consistant », est-ce que tu vas cesser de chercher une démonstration de HR ? Si oui, tu reconnais quand même que ce que ZFC démontre (au moins sur les entiers naturels) a une certaine pertinence. Ou, a contrario, si un matheux démontre, dans ZFC, « HR *est* démontrable dans ZFC », qu'est-ce que tu en fais ? (Je souligne ça, parce que l'axiome « toute conséquence arithmétique de ZFC est vraie » est quelque chose qui est exprimable dans ZFC, et qui n'est pas un théorème de ZFC (si celui-ci est consistant), c'est même un axiome assez fort.)

BR (2011-05-15T10:36:58Z)

Si on prouve que p=NP est indépendant de ZFC, il va de soit que cette preuve démontrerait de façon irréfutable que l'énoncé P différent de NP est vrai. Je ne comprend pas pourquoi Ruxor affirme qu'au contraire, cela prouverait que P=NP est vrai!

Touriste (2011-05-15T10:05:39Z)

Premier temps : la remarque sur "vrai et la peinture" m'agace, et j'envisage de poster un commentaire pour dire que c'est bien gentil de casser du sucre sur le lecteur, mais que je n'ai pas compris ce que tu entendais par "vrai".

Deuxième temps : je prends le temps de lire la phrase et j'ai _l'impression_ d'avoir compris, qu'en effet dans le contexte où tu l'utilises le mot "vrai" peut se passer d'explications.

Troisième temps : je lis le dernier commentaire (dernier à l'instant où je tape ça), précisément la remarque : "hijodelachingada → Non, justement, la démontrabilité est relative à un système d'axiomes, mais la vérité, c'est juste la vérité." Et là je ne comprends de nouveau plus. Pour moi ton "vrai" utilisé dans la phrase "nous savons que le théorème de Fermat est vrai" veut dire (autant que ma compréhension soit elle même communicable) "vrai au niveau méta", c'est-à-dire disposant d'une démonstration (au sens informel du mot et non au sens de la logique formelle : un truc imprimé quelque part, ou du moins exposé dans un séminaire) dont j'ai entendu parler, ou pas (la question de savoir s'il peut exister des théorèmes vrais dont je n'ai jamais entendu parler ressemble à celle de savoir si les arbres font du bruit en tombant dans les forêts où je ne me promène pas - je suis assez agnostique sur ce point). L'embêtant, c'est que c'est absolument orthogonal à ta dernière phrase qui semble distinguer "démontrable" et "vrai" alors que pour moi c'est absolument synonyme.

Maintenant une "démonstration au sens informel", ça repose plus ou moins implicitement sur un système d'axiomes (au sens "meta" encore : des choses qui sont précisées plus haut dans le livre, peut-être non explicitement si elles sont peu saugrenues), et l'existence d'une démonstration dépend du système d'axiomes utilisé.

Soyons concret, prenons Banach-Tarski. Je ne comprends vraiment pas en tournant ça dans tous les sens comment on peut le faire interagir avec ta formule "la vérité, c'est juste la vérité." Pour moi, ça peut très évidemment être vrai dans un livre et faux dans un autre, selon les choix préalables d'axiomatisation faits entre les pages 1 et 5. Ce m'est tellement évident que je n'intuite même pas une opinion alternative. Qu'en est-il ?

Je me sens toujours très neuneu quand le mot "vrai" apparaît, j'ai l'impression que quelque chose de très simple et bien connu de tous m'échappe.

hijodelachingada (2011-05-15T04:09:20Z)

« hijodelachingada → Non, justement, la démontrabilité est relative à un système d'axiomes, mais la vérité, c'est juste la vérité. »

Mon niveau de maths étant merdique, il y a quelque chose que je ne dois pas saisir. Ce que j'aurais dit : si HR est indécidable dans ZFC, je peux sortir un axiome débile D de telle sorte que HR soit réfutable dans ZFC+D (exemple D = ¬HR). À partir de là, j'ai du mal à parler de « vérité ».

Je n'aurais rien contre un cours de peinture, même si je ne suis pas doué non plus pour ce genre de choses…

Ruxor (2011-05-14T23:05:50Z)

Ma remarque sur la vérité est surtout là parce que je suis assez agacé, à chaque fois que j'essaie d'expliquer ce genre de choses, que les gens partent dans ces questions oiseuses. Si un théoricien des nombres dit que « depuis les résultats de Wiles, nous savons que le théorème de Fermat est vrai », les gens ne lui demandent pas « qu'est-ce que vous voulez dire au juste par “vrai” ? vrai dans quels entiers naturels ? ». Mais quand un logicien essaie de parler à un non-logicien, le non-logicien a tendance à demander précisément ça. Or la question n'est pas plus intelligente dans ce contexte.

Il est vrai que l'observation du fait que les axiomes de Peano ont plusieurs modèles sérieusement différents (non « élémentairement équivalents ») et que même parmi les modèles élémentairement équivalents aux entiers naturels il y a encore beaucoup de choses (non isomorphes) peut faire perdre un peu de vue que les entiers naturels sont, justement, naturels. Mais (comme Poizat l'explique fort bien dans son livre de théorie des modèles), c'est juste le signe que la logique du premier ordre est trop faible pour caractériser complètement les entiers naturels, pas qu'on a découvert une multiplicité ou un phénomène incompréhensible sur les entiers naturels. Le logicien ne mérite pas plus que n'importe quel autre mathématicien qu'on lui demande « quels entiers naturels ? » ou « qu'est-ce que c'est que la vérité ? »…

Les autres modèles des axiomes de Peano sont juste des cheap plastic imitations des entiers naturels. :-)

hijodelachingada → Non, justement, la démontrabilité est relative à un système d'axiomes, mais la vérité, c'est juste la vérité.

hijodelachingada (2011-05-14T22:52:54Z)

« Autrement dit, si on prouve l'indécidabilité (1&2) de HR dans ZFC, on prouve au moins sa vérité (l'item (1)) »

J'aurais indiqué par clarté « sa vérité dans S » avec S le système d'axiomes adéquat (Peano j'imagine).

Mon niveau en maths ne t'autorise pas à préjuger de mon talent en peinture. Les musées d'art moderne sont remplis d'œuvres de personnes qui ont malheureusement suivi tes conseils.

Camille (2011-05-14T20:03:09Z)

@f3et

Je ne suis vraiment pas convaincu. Je pense que la plupart des matheux se contentent de démontrer des théorèmes et n'utilisent tout simplement pas le mot vrai ou faux (ou alors ils l'utilisent dans le sens de "est un théorème"). Et je pense aussi que beaucoup ignorent plus ou moins complètement la théorie des modèles.

f3et (2011-05-14T18:19:39Z)

Ben parce que, justement, c'est avoir un sérieux problème etc. Ce n'est pas du mépris, c'est juste que tout matheux qui se respecte sait, en effet, que la question de Ponce Pilate NE SE POSE PAS en mathématiques : VRAI y est un terme primitif, par exemple, ou au contraire un terme parfaitement défini de la théorie des modèles. Dans tous les contextes du type "P=NP est vrai", le sens de vrai est aussi clair que dans l'affirmation "2+2=4 est vrai", et, comme le disait Don Juan, il est difficile de trouver quelque chose de plus vrai que ça…

ooten (2011-05-14T12:22:41Z)

Le post de Ruxor me semble on ne peut plus clair surtout si on lit ceux qu'il a produit sur le même sujet. Maintenant je pense que ces considérations (à la lumière de ce que je peux comprendre, je ne suis qu'un amateur et je dois en dire des bêtises) logiques sont stériles et sans intérêt pour les domaines étudiés (HR, P=NP ou le théorème de Fermat-Wiles), c'est juste bien pour le logicien de trouver et d'adapter une axiomatique idoine pour tout ces problèmes.

D'ailleurs y-a-il un seul résultat intéressant qui ne serait pas de la logique, de l'informatique ou des fondements des mathématiques (Axiomatiques de l'arithmétique, ordinaux …) et non démontrable ? Je ne le crois pas.

Ce qui pourrait peut-être être intéressant c'est de réfléchir à des notions de non démontrabilité et d'indécidabilité qui ne seraient plus de Godel ou de turing, si c'est possible et si ça a un sens.

Camomille (2011-05-14T10:38:56Z)

Je ne comprend pas trop pourquoi tu évacues avec tant de mépris les questions de vraie/faux en math (questions que la plupart des matheux ne se sont jamais posées ou n'ont jamais complètement éclaircies).

T (2011-05-13T23:33:42Z)

Un article intéressant à ce sujet :
« Is P Versus NP Formally Independent? »
www.scottaaronson.com/papers/pnp.pdf

Kenny (2011-05-13T22:47:43Z)

Le passage :
"Je pense que quelqu'un qui commence à demander "qu'est-ce que "vrai" veut dire" a un sérieux problème et ferait mieux de faire de la peinture que des mathématiques" est sacrément méprisant. Enfin peut-être que c'est pas voulu,
mais ça apparait ainsi.
La notion de "vrai" est-elle si triviale, qu'avoir des difficultés à la définir précisément montre
une totale inaptitude à faire des mathématiques ?
Mais superbe entrée à part ça.