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

[myoper]

Comment pouvez-vous imaginer que je puisse donner un avis sur un article que je n'aurais pas lu ? C'est méprisant, voire insultant.

Vous devriez vraiment vous relire avant de poster ce genre de phrase. Personne ne vous a demandé de donner votre avis sur cet article, mais seulement suggéré d'y jeter un oeil.

Alors quel intérêt sur un forum si ce n'est pour ne justement pas en discuter et d'autant plus que c'est censé représenter un argument ?

Vous disjonctez mon pauvre. C'est moi qui devrai me sentir insulté par cette comédie.

Par ailleurs les attaques personnelles et insultes ne sont pas des arguments et ne valident pas les affirmations péremptoires.
Elles sont donc interdites sur ce forum.
-----

[Matmat]

Quant à l'expression elle-même ("totalité de la réalité physique"), je faisais référence à la lubie positiviste de la "théorie du tout".

Oulà

lubie positiviste de la "théorie du tout" ??

De quel positivisme parlez vous là ?

[erik]

Oulà

lubie positiviste de la "théorie du tout" ??

De quel positivisme parlez vous là ?

Je dirais même plus de quelle "théorie du tout" ? (celle des physiciens ou celle des gens qui n'ont pas compris de quoi les physiciens parlent quand ils disent "théorie du tout")

[invite29cafaf3]

Je dirais même plus de quelle "théorie du tout" ? (celle des physiciens ou celle des gens qui n'ont pas compris de quoi les physiciens parlent quand ils disent "théorie du tout")

Simple.

La théorie de leibniz, parceque leibniz est tout.

[Matmat]

Simple.

La théorie de leibniz, parceque leibniz est tout.

Il est tout plutôt que rien

[SimonF]

Je viens de m'inscrire sur ce site et je profite du sujet (Gödel) pour squatter la discussion et poser une question:
Les différents énoncés de ce théorème font allusion à un certain niveau de complexité et l'arithmétique semble être la référence.
pour qu'un système satisfasse le théorème de Gödel il faut qu'il soit "suffisamment" complexe. Ma question est simple :
Comment définit-on cette complexité?
Existe-t-il un seuil de complexité au delà duquel le théorème s'applique?
Merci pour vos réponse.

[karlp]

Bonjour et bienvenue.
Je crois que le 2ème théorème d'incomplétude (si c'est de celui là dont il est question) concerne les systèmes formels qui contiennent l'arithmétique de Peano.
Sur ces questions, il faut toujours attendre l'éclairage infaillible de Médiat (que je salue, sachant qu'il ne manquera pas de passer par ici)

[Médiat]

Bonjour, et bienvenue,

Vous avez raison : pour que le théorème d'incomplétude de Gödel s'applique, il faut :

1) que la théorie soit du premier ordre
2) suffisamment complexe (pour que l’on puisse y exprimer l’arithmétique)
3) suffisamment simple pour être récursivement axiomatisable

La complexité dont il est question ici se mesure uniquement par le fait que l'on peut y définir l'arithmétique (sous-entendu de Peano)

Existe-t-il des théories plus simples que AP (avec au moins un axiome en moins), mais pour lesquelles le théorème de Gödel s'applique ?
Oui : le système Q de Robinson !

Existe-t-il des théories plus simples que le système Q, mais pour lesquelles le théorème de Gödel s'applique ?
Je ne sais pas ("plus simple" étant très flou), mais si on supprime soit l'addition, soit la multiplication au système Q, le théorème d'incomplétude ne s'applique plus.

Le point qui fait que la démonstration de Gödel fonctionne est la possibilité de coder les formules du langage dans la théorie, c'est donc cela qui mesure réellement la complexité minimale de la théorie pour que le théorème s'applique.

[EDIT]Bonjour cher karlp : je suis donc tellement prévisible

[karlp]

[EDIT]Bonjour cher karlp : je suis donc tellement prévisible

Pas toujours, mais sur ces sujet là un peu quand même

Vous venez de me détourner de mon travail: j'ai toujours eu énormément de mal avec l'idée de théorie "récursivement axiomatisable" (et d'ensemble récursivement énumérable) malgré mes nombreuses tentatives pour bien cerner ce dont il s'agit. Je crois parfois m'en faire une idée "intuitive"; mais je n'ai plus la moindre confiance dans cette fameuse "intuition"

[je n'oublie pas la promesse que je vous ai faites; je n'ai pas encore fini]

[karlp]

On trouve ces définitions (sur wikipedia entre autres) sur les ensembles récursivement énumérables

Intuitivement un ensemble est récursivement énumérable s'il existe un procédé mécanique (en gros qui peut être réalisé par un ordinateur) qui liste ses éléments. On dirait aussi qu'il existe un "programme" qui peut dire si un élément appartient à l'ensemble. Le même programme ne peut rien dire si l'élément n'appartient pas à l'ensemble.

En théorie de la calculabilité, un ensemble récursivement énumérable ou semi-décidable est un ensemble d'entiers (ou de codage aisé dans les entiers) tel qu'il existe une machine de Turing qui termine en acceptant sur l'entrée n si et seulement si n appartient à l'ensemble. De façon équivalente, il s'agit d'un ensemble tel qu'il existe une machine de Turing qui écrit successivement tous les éléments de l'ensemble (dans un ordre quelconque), d'où le terme (les fonctions récursives au sens de la logique mathématique sont les fonctions calculables par les machines de Turing).

Récursivement axiomatisable :

Une théorie récursivement axiomatisable, est une théorie qui peut être axiomatisée de façon qu'il soit possible de reconnaître de façon purement mécanique les axiomes parmi les énoncés du langage de la théorie

Si ces explications sont correctes, alors je les "comprends" (mais je veux maintenant comprendre ce que veut dire "semi décidable")

[Matmat]

Si ces explications sont correctes, alors je les "comprends" (mais je veux maintenant comprendre ce que veut dire "semi décidable")

Lorsque l'élément n'appartient pas à l'ensemble le programme ne répond pas, au lieu de répondre "faux" il ne répond rien, il ne répond jamais.

[Médiat]

Ces réponses sont correctes et c'est justement sur :
"de façon qu'il soit possible de reconnaître de façon purement mécanique les axiomes parmi les énoncés du langage de la théorie"
"Qu'est basée la démonstration de Gödel.

Semi-décidable a tout l'air d'être synonyme de récursivement axiomatisable (ce qui est moins fort que décidable : reconnaître qu'un énoncé est un axiome (ou une démonstration) est plus facile que de démontrer un théorème).

[karlp]

Merci Matmat et Mediat !
J'ai encore du travail, mais j'ai l'impression d'avancer

[Amanuensis]

Semi-décidable a tout l'air d'être synonyme de récursivement axiomatisable (ce qui est moins fort que décidable : reconnaître qu'un énoncé est un axiome (ou une démonstration) est plus facile que de démontrer un théorème).

??? Il me semblait que récursivement axiomatisable signifiait que l'ensemble des axiomes était décidable , et non pas semi-décidable (i.e., l'ensemble des axiomes est récursif, on peut calculer en un nombres fini d'étapes aussi bien l'appartenance ou la non appartenance d'une assertion à l'ensemble des axiomes).

La citation donnée par Karlp n'est pas en contradiction avec cela, et son message contient deux citations qui n'apparaissent pas parler de la même chose. En effet un ensemble récursif n'est pas la même notion de "récursivement énumérable". Un ensemble récursif est un ensemble décidable (cf. http://fr.wikipedia.org/wiki/Ensemble_r%C3%A9cursif).

[Matmat]

??? Il me semblait que récursivement axiomatisable signifiait que l'ensemble des axiomes était décidable , et non pas semi-décidable (i.e., l'ensemble des axiomes est récursif, on peut calculer en un nombres fini d'étapes aussi bien l'appartenance ou la non appartenance d'une assertion à l'ensemble des axiomes).

L'ensemble des théorèmes est semi-decidable et l' (un) ensemble des axiomes est décidable (dans cet ensemble de théorèmes).

[karlp]

Bonsoir Amenuensis

J'ai cru comprendre qu'une théorie récursivement axiomatisable était une théorie dont les théorèmes sont récursivement énumérables.
Une théorie récursivement énumérable est semi décidable: Matmat explique

Lorsque l'élément n'appartient pas à l'ensemble le programme ne répond pas, au lieu de répondre "faux" il ne répond rien, il ne répond jamais.

Donc il me semble que les axiomes sont bien énumérables.
(en fait je ne comprends pas ce que veut dire un "axiome décidable": un axiome est forcément démontrable à partir de lui même et, je suppose que la négation de l'axiome est nécessairement indémontrable)
Bonne soirée

[Médiat]

Il s'agit d'une faute de frappe je voulais écrire "Semi-décidable a tout l'air d'être synonyme de récursivement énumérable", l'exemple que je donne est lui correct.

[karlp]

Vous tombez bien Matmat : vous voulez bien m'expliquer ce que veut dire "l'ensemble des axiomes est décidable" ?

[Médiat]

(en fait je ne comprends pas ce que veut dire un "axiome décidable": un axiome est forcément démontrable à partir de lui même et, je suppose que la négation de l'axiome est nécessairement indémontrable)

Attention à ne pas confondre une proposition décidable et une théorie décidable.

[karlp]

J'ai cru comprendre qu'une théorie récursivement axiomatisable était une théorie dont les théorèmes sont récursivement énumérables.

Ceci n'est donc pas correct ?

[Médiat]

vous voulez bien m'expliquer ce que veut dire "l'ensemble des axiomes est décidable" ?

Qu'il existe un processus automatique qui si on lui donne en entrée une proposition est capable de répondre s'il s'agit d'un axiome ou non.

[karlp]

Attention à ne pas confondre une proposition décidable et une théorie décidable.

je suis en train de me noyer . Je ne sais pas ce qu'est une théorie décidable

[karlp]

Qu'il existe un processus automatique qui si on lui donne en entrée une proposition est capable de répondre s'il s'agit d'un axiome ou non.

En le distinguant des théorèmes ?

[Médiat]

Ceci n'est donc pas correct ?

Si c'est correct, car si l'ensemble des axiomes est décidable, on peut fabriquer automatiquement une démonstration d'un énoncé qui si le programme s'est arrêter, démontre le théorème (par contre si le programme ne s'est pas arrêté quand on regarde, cela ne prouve rien).

[Médiat]

Je reprends posément :
Théorie récursivement axiomatisable : intuitivement, on est capable de reconnaître en un temps fini si une proposition est un axiome ou non, par exemple dans l'arithmétique de Peano, il y a une infinité d'axiomes (à cause du schéma de récurrence), mais si, en entrée on fournit à un programme un énoncé où le schéma est spécialisé c'est à dire où on utilise une vraie formule explicite et non un nom de formule, alors le programme peut répondre en un temps fini si c'est bien un axiome (formule bien formée, et bonne application du schéma).

Dans les conditions précédentes, démontrer un théorème, consiste à écrire des axiomes, des règles d'inférence et aboutir à la formule que l'on veut démontrer, si c'est bien un théorème, la réponse arrivera en un temps fini, sinon le prgramme ne se termine jamais (ne serait-ce que pour démarrer, il y a une infinité dénombrable de sous ensembles finis des axiomes.

[Matmat]

Vous tombez bien Matmat : vous voulez bien m'expliquer ce que veut dire "l'ensemble des axiomes est décidable" ?

je voulais faire remarquer que le désaccord entre Amenensuis et Médiat n'avait pas lieu d'être , ils ont tous deux raisons me semble t'il.
Quand on affirme que l'ensemble des axiomes est récursif (décidable) , on parle de sa décidabilité dans l'ensemble des théorèmes de la théorie ( et non dans l'ensemble des énoncés du langage) , alors que quand on affirme que l'ensemble des théorème est semi-décidable on parle de semi-décidabilité d'un sous-ensemble de l'ensemble de tous les énoncés du langage.

[Amanuensis]

J'ai cru comprendre qu'une théorie récursivement axiomatisable était une théorie dont les théorèmes sont récursivement énumérables

Non. "récursivement axiomatisable" parle de l'ensemble des axiomes, pas de l'ensemble des théorèmes.

Et "décidable" ou "semi-décidable" sont d'abord des propriétés s'appliquant à des (sous-)ensembles : cela indique si on peut calculer l'appartenance et/ou la non-appartenance.

Pour faire la liaison entre ensembles et théories, faut passer par les assertions, les phrases.

Dans le cadre des "théories", on s'intéresse à des ensembles d'assertions, de "phrases", de chaînes de caractères, et plus précisément celles répondant à une certaine syntaxe.

Parmi toutes les chaînes de caractères possibles, le sous-ensemble des phrases bien construites ("grammaticalement" correctes, qui répondent à la syntaxe) est décidable.

Dans ce sous-ensemble, il y a le sous-ensemble des axiomes. Il peut être fini (auquel cas il est évidemment décidable), ou infini. Dans ce second cas, préciser que l'ensemble des axiomes est décidable indique juste qu'on sait "dire" (calculer) si une phrase bien construite est un axiome ou non.

Ensuite, parmi les phrases bien construites, il y a le sous-ensemble des théorèmes, qui contient tous les axiomes, et plus.

À cause du processus de démonstration (un processus récursif), l'ensemble des assertions démontrables (les théorèmes) est récursivement énumérable, c'est à dire semi-décidable.

Si la théorie est telle que l'ensemble des assertions démontrables contient toute assertion bien construite ou sa négation, la théorie est dite "décidable". (Si cet ensemble contient une assertion et sa négation, la théorie est "incohérente", et contient alors toutes les assertions grammaticalement correctes ; s'il y a des assertions grammaticalement corrects telle que ni elle ni sa négation est dans l'ensemble, elle est dite "indécidable".)

PS : Même si c'est redondant avec des messages d'autres provenances, dire la même chose dans des mots différents ne peut qu'aider.

[Amanuensis]

Quand on affirme que l'ensemble des axiomes est récursif (décidable) , on parle de sa décidabilité dans l'ensemble des théorèmes de la théorie ( et non dans l'ensemble des énoncés du langage)

??? Pour moi c'est bien dans l'ensemble des énoncés. Je ne vois d'ailleurs pas trop quel serait l'intérêt de la décidabilité dans l'ensemble des théorèmes, ce qui voudrait dire que "sachant qu'une assertion est un théorème, on peut calculer si c'est un axiome ou non" !?!

, alors que quand on affirme que l'ensemble des théorème est semi-décidable on parle de semi-décidabilité d'un sous-ensemble de l'ensemble de tous les énoncés du langage.

Oui

----

La question, dont je ne suis pas sûr de la réponse, est, selon moi, si le théorème de Gödel est restreint aux théories dont l'ensemble des axiomes est décidable en tant que sous-ensemble des énoncés, ou si il s'applique plus généralement aux cas d'ensembles d'axiome semi-décidable en tant que sous-ensemble des énoncés.

[karlp]

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

[invite6754323456711]

Pour faire la liaison entre ensembles et théories, faut passer par les assertions, les phrases.

Dans le cadre des "théories", on s'intéresse à des ensembles d'assertions, de "phrases", de chaînes de caractères, et plus précisément celles répondant à une certaine syntaxe.

Il y a t-il un lien avec la catégorie de l'analyse lexicale (par exemple un document XML bien formé) et l'analyse syntaxique relativement à une grammaire (par exemple un document XML valide) ?

http://users.polytech.unice.fr/~pfz/.../compil3-4.pdf


Patrick