conséquences de la complétude et de l'incomplétude

[karlp]

Bonjour à tous

J'aimerai essayer de récapituler ce que je crois avoir saisi pour demander aux âmes éclairées et patientes surtout si elles veulent bien pointer mes erreurs.

1) Une théorie récursivement axiomatisable est une théorie pour laquelle on possède un algorithme permettant de décider en un temps fini si une proposition est ou non un axiome.

2) Un ensemble d'axiome est récursif ou décidable si on peut dire, pour n'importe quelle EBF (expression bien formée) si elle est ou non un axiome.

3) Dois-je en conclure que pour toute théorie récursivement axiomatisable, l'ensemble des axiomes de la théorie est récursif ou décidable ?

4) Lorsqu'un programme s'arrête pour toute proposition qui est un théorème d'une théorie, on dit que l'ensemble des théorèmes est récursivement énumérable ou semi décidable: le programme ne s'arrête pas si la formule n'est pas un théorème.

5) Si une théorie est recursivement axiomatisable, alors l'ensemble des théorèmes est semi-décidable.

6) Si chaque assertion d'une théorie ou bien sa négation est démontrable, alors la théorie est décidable.

Questions:
7) Si une théorie est décidable, est-ce que cela implique que l'ensemble de ses théorèmes l'est aussi ? (j'ai du mal à concevoir que ce ne soit pas le cas)

8) Est-ce qu'on peut considérer que toute proposition non atomique peut être équivalente à une assertion ?

Merci à vous ( et toutes mes excuses si je vous fait bondir d'horreur)
-----

[Matmat]

Merci à tous les trois pour votre patience

J'ai, je l'espère, compris vos explications (j'y reviendrai demain pour vérifier)

Excellente soirée à vous

Ne me remerciez pas, je me rend compte que j'ai moi-même une lacune sur la récursivité de l'ensemble des axiomes, je ne comprend pas comment un programme peut décider d'un d'ensemble d'axiomes parmi tous les énoncés possibles du langage, "bien formées" d'accord, mais "axiome" je ne vois pas comment.

pour répondre à vos points 6) et 7) si la théorie est complète alors il suffit que la théorie soit récursivement axiomatisable pour être récursive (c'est à dire: l'ensemble des théorèmes est récursif)

[invite4492c379]

(...)
4) Lorsqu'un programme s'arrête pour toute proposition qui est un théorème d'une théorie, on dit que l'ensemble des théorèmes est récursivement énumérable ou semi décidable: le programme ne s'arrête pas si la formule n'est pas un théorème.
(...)

Hello,

juste une petite précision ... semi-décidable ne signifie pas «le programme boucle toujours si la formule n'est pas un théorême», il peut s'arrêter en répondant «ce n'est pas un théorême» pour certaines propositions et peut boucler indéfiniment pour d'autres.

[SimonF]

J'avoue être un peu dépassé par les réponses à ma question (je suis clairement pas au niveau) mais je crois comprendre que cette notion de mesure de la complexité d'un système n'est pas complètement définie. Il y a les PA, et quelques exemples de systèmes plus simples ou le théorème de Gödel s'applique encore, mais cette simplicité n'est pas mesurée, on ne peut donc pas vraiment parler de seuil de complexité à partir duquel le théorème de Gödel s'appliquerait.

On ne peut pas ou on ne sait pas?

Il y a-t-il eut des essais pour définir puis mesurer la complexité des systèmes?

Par ailleurs je ne sais pas si je suis franchement dans le bon forum, car ma question a déclenché toute une série d'échange sur la récursivité, la décidabilité, les axiomes et les théorèmes.
C'est vrai que le sujet du forum est "conséquences de la complétude et de l'incomplétude", alors que moi se serait plutôt "complétude et de l'incomplétude conséquence de la complexité?".
Bon si je vous ennuie dites le moi, je comprendrais sans problème, j'irai voir ailleurs (peut-être auriez-vous un conseil?).

[Médiat]

On ne sait pas : la démonstration du théorème de Gödel repose sur l'arithmétique, rien, a priori, n'interdit de trouver une autre démonstration utilisant d'autres mécanismes.

On ne peut pas (me semble-t-il) : il est très difficile de mesurer la complexité relative de deux théories de façon générale et universelle surtout si elles s'expriment dans des langages différents. Donc, comme je le disais précédemment, "suffisamment complexe" doit être compris comme "permettant d'exprimer AP".

Bien sur, il existe la notion de complexité de Kolmogorov, mais je ne crois pas que cela soit adapté au théorème de Gödel.

[Médiat]

je ne comprend pas comment un programme peut décider d'un d'ensemble d'axiomes parmi tous les énoncés possibles du langage, "bien formées" d'accord, mais "axiome" je ne vois pas comment.

Attention il n'est pas question de faire un programme universel qui soit capable de reconnaître le caractère axiome de n'importe quel énoncé, mais de reconnaître comme axiome un énoncé d'une théorie particulière.
A chaque théorie correspond un programme différent

[karlp]

J'avoue être un peu dépassé par les réponses à ma question (je suis clairement pas au niveau) mais je crois comprendre que cette notion de mesure de la complexité d'un système n'est pas complètement définie. Il y a les PA, et quelques exemples de systèmes plus simples ou le théorème de Gödel s'applique encore, mais cette simplicité n'est pas mesurée, on ne peut donc pas vraiment parler de seuil de complexité à partir duquel le théorème de Gödel s'appliquerait.

On ne peut pas ou on ne sait pas?

Il y a-t-il eut des essais pour définir puis mesurer la complexité des systèmes?

Par ailleurs je ne sais pas si je suis franchement dans le bon forum, car ma question a déclenché toute une série d'échange sur la récursivité, la décidabilité, les axiomes et les théorèmes.
C'est vrai que le sujet du forum est "conséquences de la complétude et de l'incomplétude", alors que moi se serait plutôt "complétude et de l'incomplétude conséquence de la complexité?".
Bon si je vous ennuie dites le moi, je comprendrais sans problème, j'irai voir ailleurs (peut-être auriez-vous un conseil?).

Bonjour SimonF
Je dois reconnaître que c'est de ma faute si le débat s'est orienté vers ces questions.

Il existe un article de Jean Paul Delahaye dans "Pour la science" (janiver 2009 si j'ai bonne mémoire, mais rien n'est moins sûr) qui associe directement l'indécidabilité à la complexité. Le titre doit être "presque tout est indécidable" ou quelque chose d'approchant.

[Médiat]

Un résumé de l'article de Jean Paul Delahaye : http://forums.futura-sciences.com/le...decidable.html.

[invitef17c7c8d]

Je ne pense pas que le théorème de Godel est un rapport avec la complexité mais plutôt avec celui du paradoxe du menteur.

Godel arithmétise la meta théorie, c'est à dire qu'il associe à toute proposition formelle est nombre: c'est ce qu'on appelle la godelisation.
Godel aboutit alors à deux théorèmes:
Le premier dit que si l'arithmétique est supposée cohérente (mais en dehors de l'arithmétique, c'est à dire dans un contexte métathéorique) alors toute proposition est indécidable.
Le deuxième dit que si la cohérence de l'arithmétique est ajoutée à l'arithmétique, alors on peut en déduire une proposition complète.

[Médiat]

Godel arithmétise la meta théorie, c'est à dire qu'il associe à toute proposition formelle est nombre: c'est ce qu'on appelle la godelisation.

Et c'est là qu'intervient la nécessité d'une théorie suffisamment complexe (dans le sens "contient AP")

Le premier dit que si l'arithmétique est supposée cohérente (mais en dehors de l'arithmétique, c'est à dire dans un contexte métathéorique) alors toute proposition est indécidable.

Ceci est faux (le théorème de Gödel ne dit pas cela).

Le deuxième dit que si la cohérence de l'arithmétique est ajoutée à l'arithmétique, alors on peut en déduire une proposition complète.

Pour moi, mais je peux me tromper, ceci ne veut rien dire.

[Matmat]

Attention il n'est pas question de faire un programme universel qui soit capable de reconnaître le caractère axiome de n'importe quel énoncé, mais de reconnaître comme axiome un énoncé d'une théorie particulière.
A chaque théorie correspond un programme différent

oui mais justement c'est bien comme ca que je le comprend et c'est précisemment pour cette raison que je pensais qu'un ensemble d'axiome ne pouvait être récursif qu'en tant que sous ensemble d'un ensemble de théorème ( et non dans l'ensemble de tous les énoncés du langage comme me le fesait remarquer Amenensuis ) ...
Je suis informaticien ( nul n'est parfait )... je fais des algorithme, si un mathématicien me dit: voici tous les énoncés d'un langage, trouvez moi un algorithme qui calcule un ensemble d'axiome ... je ne peux que lui répondre qu'il me manque une information capitale: de quelle théorie me parlez vous monsieur le mathématicien, Fournissez moi plutot l'ensemble d'énoncés que vous souhaiteriez vrais (fournissez moi un ensemble de théorème) et alors oui je pourrais vous faire un algorithme qui pourra décider un ensemble d'axiome générant cet ensemble de théorème: car mon algorithme recherche un sous ensemble d'un ensemble de théorème.

[Médiat]

Bonjour,
Alors je m'adresse à l'informaticien :

A coder dans les constantes du programme :
Langage = (0, +, x, s)
Formule bien formée = "les règles habituelles" (j'espère que vous ne m'en voudrez pas de botter ainsi en touche)
Axiome : "les axiomes de peano" moins la récurrence (cette liste est finie, vous pouvez donc la coder facilement dans votre programme)
Schéma de récurrence : il n'y en a qu'un, facile à coder, (mais attention il y a une variable qui représente une formule).

Input : une formule Phi

Résultat : Phi est bien formée ou non.
Phi est un axiome (de la liste finie) ou non, même si le nom des variable a changé.
Phi est une occurence du schéma, où la variable représentant la formule sur laquelle repose la récurrence est remplacé par une formule bien formée.

Pouvez-vous coder ce programme ?

[invite4492c379]

Pour le côté informatique de la chose ... décider si oui ou non une expression est bien formée est indépendante du fait ou non d'être un théorême ... l'expression 1+1=3 est bien formée sans pour autant être un théorême. Définir un langage formel est donner une grammaire formelle qui comprends des terminaux, des non-terminaux, des axiomes et des règles de productions. Pour une théorie il faut ajouter éventuellement d'autres axiomes et règles de productions.

[invite4492c379]

En même temps, les expressions bien formées sont les théorêmes de la grammaire formelle ...

[Amanuensis]

Fournissez moi plutot l'ensemble d'énoncés que vous souhaiteriez vrais (fournissez moi un ensemble de théorème) et alors oui je pourrais vous faire un algorithme qui pourra décider un ensemble d'axiome générant cet ensemble de théorème: car mon algorithme recherche un sous ensemble d'un ensemble de théorème.

Pas très utile, il me semble !

Car "fournir un ensemble de théorèmes" <=> "savoir calculer si un énoncé est un théorème ou non" => la théorie est décidable.

À la question "trouver un ensemble d'axiomes engendrant cette théorie", une réponse triviale est l'ensemble des théorèmes lui-même, et il est décidable par hypothèse !

(Une question moins triviale est s'il existe un ensemble fini d'axiomes engendrant la théorie...)

----

La question de fond des mathématiques axiomatiques c'est (était, question posée par Hilbert) dans l'autre sens, et précisément : étant donné un ensemble d'axiomes (disons décidable), peut-on calculer si un énoncé n'est pas un théorème ?

Le premier théorème de Gödel répond : non, dès lors que la théorie admet une sous-théorie isomorphe à l'arithmétique.

(J'ai omis des conditions, voir autres messages.)

[invitef17c7c8d]

Et c'est là qu'intervient la nécessité d'une théorie suffisamment complexe (dans le sens "contient AP")

J'ai l'impression que ce que tu appelles "contient AP" correspond au second théorème de Godel

Ceci est faux (le théorème de Gödel ne dit pas cela).

Bien faire attention au fait qu'il y a deux théorèmes!!

Le premier théorème dit que:
La cohérence implique G(m), or G(m) est indémontrable donc la cohérence est indémontrable. Donc l'arithmétique ne démontre pas la cohérence de l'arithmétique. C'est la conclusion du premier théorème.
Pour résumer le premier théorème :Supposons que l'arithmétique soit cohérente, alors l'arithmétique ne démontre pas G(m) et ne démontre pas notG(m). Par conséquent, G(m) est un énoncé indécidable.

Pour comprendre ce que Godel voulait nous dire, il faut comparer les deux théorèmes!!!
La merveille se situe dans le passage du théorème 1 au théorème 2
Maintenant encodons dans l'arithmétique la proposition métathéorique cohérence de l'arithmétique, alors on peut dériver G(m).
La théorie est plus forte que la métathéorie: c'est la conclusion du théorème 2.

Cette notion de cohérence dans la métathéorie (ou métamathématque) et/ou dans la théorie (arithmétique) est une notion délidate, subtile à saisir.

[Médiat]

Pour comprendre ce que Godel voulait nous dire, il faut comparer les deux théorèmes!!!

Mais avant il faut les lire, et je vous y enjoins fortement !!!!!

[invitef17c7c8d]

Pour préciser, G(m) correspond à un énoncé mathématique formel ou à un nombre dans l'arithmétique. Car ce que fait Godel, c'est associer à tout énoncé formel, un nombre unique dans l'arithmétique.
C'est en quelque sorte la même chose que ce que les programmateurs font en langage assembleur. Sauf que Godel a écrit son article en 1930 ...

[invitef17c7c8d]

Mais avant il faut les lire, et je vous y enjoins fortement !!!!!

Ce n'est pas gentil ce que vous dites!
Car vous savez qu'il y a dans son article, des démonstrations de lemmes extrèmement techniques (et par conséquent extrèmement ennuyeux) mais pas très profond.
L'essence et la profondeur de son article se situant essentiellement dans l'encodage de la métathéorie dans l'arithmétique.

[Matmat]

Pas très utile, il me semble !

C'est utile de faire d'un ensemble d'énoncés vrais (une théorie non axiomatique au départ) une théorie axiomatique dans laquelle ces énoncés vrais se déduisent d'axiomes, bref que ces énoncés soient des théorèmes d'une théorie axiomatisée... Recherche à posteriori des axiomes en fonction d'un ensemble de théorème (du moins d'un ensemble d'énoncés dont on voudrait qu'ils soient théorème, c'est à dire démontrables)

[Amanuensis]

C'est utile de faire d'un ensemble d'énoncés vrais (une théorie non axiomatique au départ) une théorie axiomatique dans laquelle ces énoncés vrais se déduisent d'axiomes, bref que ces énoncés soient des théorèmes d'une théorie axiomatisée... Recherche à posteriori des axiomes en fonction d'un ensemble de théorème (du moins d'un ensemble d'énoncés dont on voudrait qu'ils soient théorème, c'est à dire démontrables)

Je répète mon point : un ensemble d'axiomes est tout trouvé avec les hypothèses données! S'il y a quelque chose à chercher, c'est autre chose, par exemple avec des contraintes supplémentaires. Lesquelles?

[invite6754323456711]

Bonjour,

Syntaxe (indépendant d'un contexte) et sémantique (dépendant d'un contexte) semblent se rejoindre. Il y a t-il entre les approches théorie de la calculabilité et théorie des langages formels (qui inclus la théorie des automates) une plus féconde pour lever les ambiguïtés de définition ?

Patrick

[invite7863222222222]

Bonjour,

Syntaxe (indépendant d'un contexte) et sémantique (dépendant d'un contexte) semblent se rejoindre. Il y a t-il entre les approches théorie de la calculabilité et théorie des langages formels (qui inclus la théorie des automates) une plus féconde pour lever les ambiguïtés de définition ?

Patrick

Pardon ?

Peut-être devrais-je ouvrir un nouveau fi, mais les liens donnés m'ont fait réfléchir sur la notion d'algorithme en théorie de la calculabilité.

Une remarque d'un niveau très "primaire" est : j'ai l'impression qu'on restreint la notion d'algorithme en le représentant par un mot sur un alphabet fini.

J'imagine que c'est pour justement satisfaire au fait, que lorsqu'on parle d'algorithme, on aime à pouvoir les énumérer mais je n'arrive pas à comprendre pourquoi, pour les nombres on s'autorise à avoir des ensembles indénombrables et que pour les algorithmes on veut qu'il soit dénombrable. Est-ce que cela n'aboutit pas à retomber que sur des choses un peu trop évidentes.

La réponse, c'est surement que les mathématiques aiment plus la rigueur des démonstrations, plutôt que leur portée, mais enfin y'a un juste milieu, et il me semble pas trop y être au milieu avec cette définition d'algorithme. Enfin bon, c'est comme cela c'est surement juste une question de bagarre sur des définitions de mots.

Mais j'ai quand même peut être une question : est-ce qu'on peut dire quand même qu'une fonction peut être représentée par un mot (fini ou infini) sur un alphabet (fini ou infini) ?

[Médiat]

Une remarque d'un niveau très "primaire" est : j'ai l'impression qu'on restreint la notion d'algorithme en le représentant par un mot sur un alphabet fini.

Bonjour,
Un algorithme (quelque soit la définition) est codable dans un programme d'ordinateur, disposez-vous d'un ordinateur à la mémoire infinie ?

[invite7863222222222]

Pardon ? pas bien compris, le ton ironique.

J'ai pensé aussi, à cela, mais si on prend un ordinateur, alors on dispose d'un nombre fini d'algorithme, et non d'un nombre énumérable. C'est pourquoi je n'ai pas considéré la notion d'ordinateur, mais c'est justement peut être l'erreur ? Mais plus précisemment alors ?

[Médiat]

J'ai pensé aussi, à cela, mais si on prend un ordinateur, alors on dispose d'un nombre fini d'algorithme

La remarque visée était :

j'ai l'impression qu'on restreint la notion d'algorithme en le représentant par un mot sur un alphabet fini

Ma réponse, ironique ou non, est donc pertinente.

A votre autre remarque, la réponse est : Oui, sur un ordinateur donné, on ne peut coder que d'un nombre fini d'algorithmes, mais en ajoutant de la mémoire (quitte à attendre la prochaine génération) ou en multipliant les ordinateurs, il n'y a pas de limite (théorique), donc : dénombrable.

(Il va de soi que si on veut pratiquement construire les ordinateurs, la quantité de matière disponible va créer une limite finie.)

[invite7863222222222]

Je vais y réfléchir, je ne souhaite pas rentrer dans une polémique inutile.

[Matmat]

J'ai pensé aussi, à cela, mais si on prend un ordinateur, alors on dispose d'un nombre fini d'algorithme, et non d'un nombre énumérable. C'est pourquoi je n'ai pas considéré la notion d'ordinateur, mais c'est justement peut être l'erreur ? Mais plus précisemment alors ?

De toute manière même avec un seul algorithme on peut vérifier un nombre dénombrable d'énoncés. on ne demande pas d'avoir autant d'algorithme que d'énoncés à vérifier !

[invite7863222222222]

Je parle d'alphabet infini pas d'énoncés.

[invite4492c379]

Un langage formel est un ensemble L (qui peut-être infini) formé de chaînes (finies) formées à partir d'un alphabet (fini).
Je rappelle qu'a priori un algorithme n'est pas donné pour un architecture physique donnée ; même s'il n'existe pas d'ordinateur sur lequel on peut l'implémenter, un algorithme reste un algorithme (= objet d'étude de l'algorithmique).
L'algorithmique est une science avant d'être une technologie.