Hypothèse de Riemann indécidable ?

[invite234bc7a5]

Bonsoir leg,

Vous faites peut-être une confusion entre le Théorème de Complétude de Gödel (démontré en 1929, publié en 1930) et ses Théorèmes d'Incomplétude (démontrés en 1930, publiés en 1931) car ce sont ces derniers dont l'importance a été beaucoup exagérée (selon l'avis de Gödel lui-même) du moins dans certains domaines auxquels ils n'étaient pas destinés.

En revanche le Théorème de Complétude (de la Logique du premier ordre) est insuffisamment connu. Il est indispensable pour comprendre la notion d'indécidabilité (les Théorèmes d'Incomplétude peuvent être utiles mais il vaut mieux en parler après).

Après avoir évoqué deux préjugés, concernant l'un la notion de preuve (croyance selon laquelle la méthode axiomatique donne la seule forme de preuve scientifiquement valable en Mathématiques) et l'autre selon lequel si quelque chose devait être fait concernant le choix des axiomes, cela aurait déjà été fait (après quoi l'on passe de "on ne peut rien faire du point de vue axiomatique" à "on ne peut rien faire du tout"), il y a à mon avis deux autres questions qui peuvent rendre incompréhensible la notion d'indécidabilité:

- le problème de la description (ou de la connaissance) des objets mathématiques: si l'on estime que se donner des axiomes est indispensable pour décrire ou connaître l'objet que l'on veut étudier, et si la démonstration formelle à partir des axiomes échoue, il peut être difficile de comprendre comment on peut aboutir à la notion de vérité (dans un modèle) par d'autres moyens

- le problème de l'existence des objets mathématiques: si l'on considère que définir un objet par un ensemble d'axiomes est indispensable pour garantir l' "existence" de cet objet (à condition bien sûr que cet ensemble d'axiomes ne soit pas contradictoire), on est confronté au même problème que celui concernant la description.

Je reparlerait du Théorème de Complétude à moins que quelqu'un l'ai fait avant moi.
-----

[invite234bc7a5]

On va présenter le Théorème de Complétude de Gödel et voir comment il permet de classer les différents cas que l'on peut avoir concernant une proposition indécidable, donc de mieux les comprendre.

On se place dans le cadre de ce qu'on appelle la Logique du premier ordre (on parle aussi de Calcul(s) des Prédicats du premier ordre). On ne rentrera pas dans tous les détails, voir pour cela les nombreux cours de Logique que l'on peut trouver, y compris sur internet.

On considère un langage formel formé de symboles, avec lesquels on peut écrire des formules. Certaines formules sont appelées formules closes ou propositions . Une théorie T est un ensemble de propositions. On peut étudier une théorie selon les points de vue suivant:

1°) Point de vue syntaxique (ou déductif):

On se donne des règles de démonstration formelle (souvent on garde les mêmes pour différentes théories). Les proposition qui sont éléments de la théorie T seront appelées les axiomes. En utilisant éventuellement certains axiomes, et les règles de démonstration, on distingue certaines formules dont on dira qu'elles sont "démontrables dans T" (on les qualifie aussi de "théorèmes de T").

Il convient de noter que la vérification d'une démonstration peut être faite par une machine ou par quelqu'un qui ne connaît rien de la théorie étudiée, car une démonstration formelle obéit à des règles très précises qu'on peut mettre en oeuvre sans attribuer un sens aux symboles manipulés.

Une théorie permettant de démontrer toutes les formules du langage est dite inconsistante (ou contradictoire). Si au moins une formule ne peut pas être démontrée dans T, on dit que T est consistante (ou non contradictoire).

2°) point de vue sémantique:

Une "réalisation" d'un langage est une structure formée d'un ensemble non vide muni éventuellement d'opérations, de relations et de fonctions, permettant de donner un sens aux symboles du langage. Par exemple on pourra considérer l'ensemble IN des entiers naturels, muni de l'opération d'addition, de la relation "est divisible par" et de la fonction "successeur" qui à un entier n fait correspondre le suivant n+1.

Des règles précisées permettent, une réalisation étant choisie, de faire correspondre à chaque formule une propriété portant sur les éléments de l'ensemble utilisé pour cette réalisation. Par exemple si l'on considère la réalisation évoquée plus haut, une telle propriété concernera les entiers naturels. Une telle propriété sera soit vraie, soit fausse.

Une réalisation du langage, telle que chaque proposition de T (donc chaque axiome) est traduite par une propriété vraie, est appelée un modèle de T.
Autrement dit un modèle d'une théorie est une structure dans laquelle tous les axiomes de cette théorie sont vrais.

Pour une formule donnée, au lieu de dire qu'elle se traduit dans un modèle de T par une propriété vraie (respectivement: fausse) on dira plus simplement que la formule est vraie (resp. fausse) dans ce modèle. On démontre facilement qu'une formule F est vraie dans un modèle M si et seulement si sa négation non F est fausse dans M. Cela résulte des "règles de traduction" évoquées plus haut.

Si une formule F est vraie dans tous les modèles d'une théorie T, on dit que F est une conséquence de T.

[invite234bc7a5]

(suite)

On va évidemment s'interroger sur les liens qu'il y a entre les deux points de vue, et en particulier entre "la formule F est démontrable dans la théorie T (est un théorème de T)" et " la formule F est une conséquence de T (est vraie dans tous les modèles de T)".

Il n'est pas si évident que les deux points de vue soient équivalents, car les méthodes utilisées dans chacun d'eux sont très différentes.

Dans une démonstration formelle on utilise des règles purement "mécaniques", sans liberté d'action.

Dans l'étude de la vérité ou fausseté d'une formule dans un modèle, on utilise les règles de la théorie des ensembles, qui n'ont de rapport évident ni avec les règles de démonstration formelle ni avec les axiomes de la théorie étudiée. On peut aussi faire appel à son intuition pour construire des raisonnements, pourvu que ceux-ci soient scientifiquement convaincants.

Cependant les règles de démonstration formelle sont choisies de telle façon que si une formule est démontrable dans une théorie T, alors elle est conséquence de T, c'est à dire est vraie dans tous les modèles de T. Ceci peut se prouver sans trop de difficultés.

La question inverse: "si une formule est conséquence de T, est-elle démontrable dans T ?" est considérablement plus difficile, ne serait-ce qu'en raison du choix énorme, voire quasi illimité, que nous avons pour construire des modèles. En 1928, Hilbert et Ackermann constataient qu'en pratique on avait toujours pu effectuer la démonstration d'une formule qu'on savait être conséquence d'une théorie donnée, et ils jugeaient probable qu'il continuerait d'en être ainsi, mais doutaient qu'on puisse un jour le démontrer.

Et pourtant c'est ce qu'a fait Gödel l'année suivante, prouvant ainsi:

Théorème de Complétude de la Logique du premier ordre (Gödel, 1929/1930):

Pour toute théorie T (du premier ordre) et toute formule F, F est démontrable dans T si et seulement si F est vraie dans tous les modèles de T.

[invite234bc7a5]

(suite)

Notons que "démontrable / non démontrable" est relatif à un ensemble d'axiomes (les règles de démonstration étant supposées fixées par ailleurs) et que "vrai / faux" est relatif à un modèle de cet ensemble d'axiomes.

Etant donnés une théorie (ensemble d'axiomes) T, supposée non contradictoire, et une formule F, listons les différents cas possibles:


Point de vue syntaxique (déductif): trois cas qui s'excluent mutuellement:

1) F est démontrable dans T

2) non F est démontrable dans T

3) ni F ni non F ne sont démontrables dans T; on dit alors que F est indécidable dans T (non F l'est également).


Point de vue sémantique:

Si l'on considère un seul modèle M de T, il y a deux cas: F est vraie dans M / F est fausse dans M.

Si l'on considère tous les modèles de T, il y a 3 cas:

a) F est vraie dans tous les modèles de T

b) F est fausse dans tous les modèles de T (ce qui revient à dire que non F est vraie dans tous les modèles)

c) F est vraie dans au moins un modèle de T et fausse dans au moins un modèle de T


Le Théorème de Complétude nous montre que les cas 1), 2) et 3) correspondent respectivement aux cas a), b) et c).


Si maintenant l'on sait qu'une formule F est indécidable dans T, et si l'on ne s'intéresse qu'à un seul modèle M de T, a priori on a deux cas possibles:

I) F est vraie dans M; dans ce cas elle est fausse dans au moins un autre modèle de T, sinon elle serait démontrable formellement dans T

II) F est fausse dans M; dans ce cas elle est vraie dans au moins un autre modèle de T, sinon sa négation non F serait démontable formellement dans T.


On peut essayer, en raisonnant directement dans M (ou "par d'autres moyens", façon de parler à discuter), de savoir et de prouver lequel de ces deux cas est le bon.


On peut parfois utiliser le fait de connaître des liens entre les différents modèles de T: voir une des interventions de Médiat dans la discussion sur "Goldbach indécidable".



J'espère que tout ceci permettra d'y voir plus clair, car le début de cette discussion sur l'Hypothèse de Riemann était quand même très confus.

[leg]

Bonjour et merci pour ces explications, et effectivement de mon côté il y a surement confusion sans l'hombre d'un doute.
mais si on reprend vos dernières explications:

3) ni F ni non F ne sont démontrables dans T; on dit alors que F est indécidable dans T (non F l'est également).

donc, c'est que l'on à pu démontrer que c'est indémontrable..dans T; Et ce, pour tous les modèles de T...de plus F ne peut être une conséquence de T

cela ne veut donc pas dire pour autant , que F est indécidable dans tous les modèles ...? et, ce cas 3) correspond au cas c) . Sauf si on ne s'intéresse qu' à un seul modèle de T

Ou alors on a montré que lorsque F est indécidable ou non F, cela ne peut être que dans un modèle de T par exemple M. Ce qui reviendrait à dire que F, ne peut être indécidable dans tous les modèles de T , alors la ok..

Point de vue sémantique:

Si l'on considère un seul modèle M de T, il y a deux cas: F est vraie dans M / F est fausse dans M.

donc ceci , correspond au 3ème cas , c) en principe...



Si l'on considère tous les modèles de T, il y a 3 cas:

a) F est vraie dans tous les modèles de T

b) F est fausse dans tous les modèles de T (ce qui revient à dire que non F est vraie dans tous les modèles)

c) F est vraie dans au moins un modèle de T et fausse dans au moins un modèle de T
donc cela veut dire que l'on ne s'intéresse qu'à un et un seul modèle de T


Le Théorème de Complétude nous montre que les cas 1), 2) et 3) correspondent respectivement aux cas a), b) et c).


Si maintenant l'on sait qu'une formule F est indécidable dans T, et si l'on ne s'intéresse qu'à un seul modèle M de T, a priori on a deux cas possibles:

I) F est vraie dans M; dans ce cas elle est fausse dans au moins un autre modèle de T, sinon elle serait démontrable formellement dans T

II) F est fausse dans M; dans ce cas elle est vraie dans au moins un autre modèle de T, sinon sa négation non F serait démontable formellement dans T.


Peut être que les bons arguments, et pour être suffisamment convaincant concernant Goldbach, n'ont pas encore été trouvés, pour la même raison que l'on ne peut pas dire aussi que c'est indécidable; car ce dernier cas, risque d'être encore plus difficile à démontrer.

D'autant plus qu'un jour on va nous dire que ce n'est qu'une conséquence du T F A, (théorème Fondamentale de l'arithmétique), et que l'on va admettre que cette conjecture est vraie...
c'est à dire , qu'un entier naturel positif se décompose de façon unique en facteurs premiers, et que l'on pourra dire qu'un entier 2n se décompose en somme de deux premiers, de plusieurs façons et que n impair, en fait de même mais avec trois premiers....

[invite868286e5]

Salut à tous,

Ca tombe vraiment bien que vous discutiez sur ce sujet car je me pose vraiment une question fondamentale sur les maths: Est-ce que tous les principes mathématiques démontrés seraient toujours valables si notre conception de la métrique (je ne sais même pas si c'est le bon mot) , n'était pas binaire: paire/impaire?

++

[leg]

si je comprend ta question, en quoi le système binaire est en rapport avec les démonstration mathématique...? ce système est tout simplement une représentation utilisé en informatique, non ? c'est à dire que l'on on aurait pu représenter les nombres par des carottes et des navets si cela avait une raison d'être ou une utilisation , je plaisante bien sur..

[invite6754323456711]

ses Théorèmes d'Incomplétude (démontrés en 1930, publiés en 1931) car ce sont ces derniers dont l'importance a été beaucoup exagérée (selon l'avis de Gödel lui-même) du moins dans certains domaines auxquels ils n'étaient pas destinés.

Que pensez-vous de cet article et de celui-ci ?

Patrick

[invite868286e5]

pourquoi je demande ça, c'est parceque le concept même des nombres entiers ou non, etc. est un concept intimement lié à la "quantité de quelque chose" et que je ne comprends pas très bien comment il serait possible de trouver une logique de type algorithmique par rapport à eux-mêmes...

Je vais essayer d'expliciter: à la base, les nombres servent à dénombrer, l'homme dans sa grande compréhension de l'univers, c'est rendu compte que mettre 100 noisettes sur une table, c'était pas super simple... Il représente donc chaque noisette par le nombre 1... Cependant, comment représenter quand il y a plus d'une noisette sur la table? bon allé deux noisettes, c'est "2". Il se rend compte ensuite, que 8 noisettes = c'est 4 ensembles de 2 noisettes ou 4+4 etc.

Un peu plus tard, il se rend compte qu'il peut compter des tartes et que ces tartes peuvent être subdivisées en part égale ou non... Chaque part pouvant être représentée mathématiquement par rapport à la tarte d'origine ou par rapport à un autre morceau...

Intrinsèquement, on a dès lors un gros souci puisque les nombres en eux mêmes ne peuvent encore et toujours que représenter une quantité de quelque chose... les nombres ne peuvent servir qu'à compter. Ce que je veux dire, c'est que dans le chiffre "8", tu ne dis pas si tes noisettes sont en ligne, forme un carré, ou représente un truc super chaotique. En gros, tes nombres n'ont qu'une seule et unique dimension.

D'ailleurs, pour représenter quelque chose dans notre monde en 3 dimensions, tu dois utiliser un étalon. 1m = ceci, 1kg=ceci, etc.

Donc le fait de faire une représentation de la distribution des nombres premiers est une absurdité car cela revient à tenter de savoir quelle est la distance entre mes deux noisettes en sachant seulement qu'il y en a 2.

You know what i mean?

[invite179e6258]

You know what i mean?

pas trop non. Peut-être qu'il suffit de rappeler que les maths ne se réduisent pas à l'étude des nombres entiers. Mais tu parles de théorie de la démonstration et là oui, il y a un rapport avec les nombres entiers. D'ailleurs il me semble que si on admet des procédés de démonstration non-finis, il a été démontré que l'arithmétique de Peano était complète.

[invite868286e5]

pas trop non. Peut-être qu'il suffit de rappeler que les maths ne se réduisent pas à l'étude des nombres entiers. Mais tu parles de théorie de la démonstration et là oui, il y a un rapport avec les nombres entiers. D'ailleurs il me semble que si on admet des procédés de démonstration non-finis, il a été démontré que l'arithmétique de Peano était complète.

qu'ils soient entiers ou non, ca ne change rien. Il n'y a pas de logique à chercher sur les nombres en eux-mêmes... C'est comme si tu conceptualises un concept

[invite234bc7a5]

Bonjour,

leg, commenter tout votre message d'aujourd'hui serait très long, il vaut mieux le faire en plusieurs fois. Dans ce message je ne vais donc insister que sur quelques points. Et d'abord:

donc, c'est que l'on à pu démontrer que c'est indémontrable..dans T; Et ce, pour tous les modèles de T...de plus F ne peut être une conséquence de T


Le fait qu'on soit dans le cas 3) ne veut pas dire qu'on le sache forcément. On peut être dans le cas 3) en le sachant (et en l'ayant prouvé), mais on peut aussi l'être sans le savoir. Vous voyez à quel point tout ceci demande d'être précis!


Par ailleurs le verbe "démontrer" est généralement utilisé dans l'intention de dire qu'on va prouver (ou qu'on a prouvé) quelque chose, mais il faut se souvenir qu'il y a de nombreuses méthodes différentes de preuve! Il serait plus prudent d'utiliser un verbe différent pour chaque type de preuve.

Dans les expression "démontrable dans T" ou "démontrable formellement", on parle de démonstration à l'aide des "règles de démonstration" utilisées dans le point de vue syntaxique. Ce sont des règles très précises qu'on utilise "mécaniquement"; je pense qu'il faudrait que vous regardiez dans des cours de Logique des exemples de telles démonstrations formelles.

Quand on utilise un autre type de preuve que celui dont je viens de parler, je préfère dire "prouver". Donc je dirais par exemple "on a prouvé que c'est indémontrable dans T", au lieu de dire "on a démontré que c'est indémontrable dans T".
En effet, pour prouver qu'une formule F n'est pas démontrable dans T, on n'utilise pas la démonstration formelle à l'aide des "règles de démonstration" syntaxiques. On utilise une preuve indirecte; par exemple on choisit un modèle M de T et on prouve que F est fausse dans M; on en déduit que F n'est pas démontrable dans T car si elle était démontrable dans T elle serait vraie dans tous les modèles, donc vraie dans M.

Bien sûr on a quand même le droit d'écrire "démontrer que F est indémontrable dans T" mais alors il faut faire extrêmement attention au sens de chaque mot. C'est pourquoi dans mes explications j'utiliserais plutôt "prouver que F est indémontrable dans T".

que c'est indémontrable..dans T; Et ce, pour tous les modèles de T

Vous faites ici une confusion. Dans la définition de "démontrable dans T" ou de "indémontrable dans T" on ne parle pas de modèle. Relisez ce qui concerne le point de vue syntaxique.
En revanche on peut utiliser des modèles pour une démonstration indirecte, à l'aide du Théorème de Complétude, de "démontrable dans T" ou "indémontrable dans T", mais dans la conclusion qu'on en tire on ne parle plus de ces modèles.


cela ne veut donc pas dire pour autant , que F est indécidable dans tous les modèles

Attention, encore une fois, la définition du mot "indécidable" ne fait pas intervenir les modèles. Une formule F est indécidable ou bien elle n'est pas indécidable; mais dire que F est indécidable dans un modèle n'a aucun sens.

Je vous laisse réfléchir déjà sur ces points et vous conseille de relire toutes les explications en faisant attention au sens de chaque mot. Bon courage!

[leg]

ok je comprend les nuances, mais effectivement je ne les cernais pas avec rigueur, et ces confusions qui m'ont fait poser ces questions. merci pour ces explications qui enlève cette "brume"..
bonne soirée et merci encore, idomeneo

[leg]

je viens de lire les deux articles mentionné par ù100fil il semblerait alors que l'on va se retrouver avec plus de conjecture et ou formule indécidable que démontrable dans un sens ou dans l'autre.
certaine phrase laisserait d'ailleurs penser que Syracuse et ou Goldbach, serait , ou irait vers l'indécidabilité...

pour Syracuse, l'ensemble de la structure arithmétique tend ver l'infini, car on peut remarquer, que l'ensemble des suites ou vols de Syracuse ne se terminent pas obligatoirement au rang n = 4, et n+1= 2 , et que les vols 2ⁿ - 1 tendent vers l'infini, de même que les suites arithmétiques et géométriques, qui les ordonnent..
jusqu'à maintenant Syracuse est vraie, pour qu'elle raison mathématique, cette structure arithmétique, ferait apparaître tout à coups, un vol infini ou un vol qui boucle sur une autre boucle que 4, 2 ,4, 2....aucune .
donc vers indécidable....?

[Médiat]

Que pensez-vous de cet article et de celui-ci ?

Bonjour,

J'avais, modestement, fait une revue de l'article "Presque tout est indécidable" : http://forums.futura-sciences.com/le...decidable.html.

Il m'avait semblé que certains points pouvaient passer inaperçus lors d'une lecture rapide.

[invite6754323456711]

J'avais, modestement, fait une revue de l'article "Presque tout est indécidable" : http://forums.futura-sciences.com/le...decidable.html.

Il m'avait semblé que certains points pouvaient passer inaperçus lors d'une lecture rapide.

Ok.
Vous ne donnez pas de réponse du pourquoi de cette démarche basée sur les probabilités pour caractériser l'incomplétude.


Dans la recherche de primalité il est aussi fait usage de probabilité pour détecter si un nombre est premier ou tout au moins s’il a de bonnes chances de l’être tel que par exemple le test de Miller-Rabin.

Patrick

[leg]

J'aurais peut être du, lire votre post concernant ces articles, car effectivement certaine phrase manque d'éclaircissement dans ces deux articles, et surtout l'utilisation des probabilités, qui ne saurait être avant tout une probabilité et non une exactitude, ainsi que le hasard qui ne veut rient dire, si ce n'est notre ignorance dans certain domaine, mais c'est tout...

J'ai retenu une phrase de Dyson:

Toute preuve devrait se fonder sur une propriété déterminée des chiffres.
L’affirmation est vraie uniquement par chance et elle ne peut pas être démontrée, parce qu’il n’y a pas de raisons mathématiques à cela. »
L’énoncé de Dyson est peut-être vrai et indécidable –

Si on prend l’exemple flagrant de Syracuse, où pendant des années et ce depuis le début de cette conjecture, la plupart des mathématiciens et chercheurs de cette conjecture, n’ont-ils pas dit que la suite U_n des itérés (« itération ») était aléatoire, donc que la valeur des itérés était le fruit du hasard ….alors qu’il s’agit d’une structure arithmétique très simple et ordonnée… !
Heureusement que le Hasard n’a pas rendu cette conjecture indécidable, quand bien même elle le serait.

Mais surtout, pour qu’elle raison mathématique, cette structure ferait apparaître un vol i’ , où sa suite U_n d’itérations tend vers l’infini , donc des itérés de plus en plus grand sans jamais redescendre sou la valeur U₀ de départ, et de plus, qui ne peuvent se trouver dans aucune suite U_n finie, sur U_n = 4 ; U_n+1 =2 ; quelque soit les vols i < i’ et par conséquent finis sur 4 et 2 .

Il est facile de répondre : aucune, raison mathématique ou arithmétique.

Alors elle est vraie par chance et non démontrable, donc indécidable… ! et j’ai gagné

[leg]

@ù100fil
effectivement dans les tests de recherche concernant des grands nombres premiers, la probabilité est utilisé mais on ne connaît pas la probabilité d'échecs...
il n'y a qu'à voir pour les nombres de Mersenne on en est q'au 43ème....vrai, sur des millions testé...

si c'est pour le même résultat, qui de toutes les façons il faudra une preuve juste ou une démonstration, pour dire si une conjecture probablement vraie ou fausse, est vraie ou l'inverse, comme pour les grands premiers.
Alors, elles ont de beaux jours devant elles....

[invite6754323456711]

effectivement dans les tests de recherche concernant des grands nombres premiers, la probabilité est utilisé mais on ne connaît pas la probabilité d'échecs...

Je viens de trouver une réponse, de l'intérêt de se poser la question de l'incomplétude pour une famille aléatoire, qui est lié au fait que l'axiomatique est récursive.

Patrick

[Médiat]

Bonsoir Patrick,

Désolé de ne pas avoir répondu plus tôt, ce message m'avait échappé, en tout état de cause, vous avez raison.