question de logique

[ilelogique]

Bonjour,
une théorie dont l'ensemble des énoncés décidables est récursive est-elle complète ?
Merci,
-----

[Médiat]

Bonjour,

Je ne vois aucune raison, pour qu'une théorie soit complète, il faut que tous les énoncés soient décidables.

Peut-être faites-vous une confusion entre "énoncé décidable/indécidable" et "théorie décidable/indécidable".

[ilelogique]

Merci,
non je ne crois pas confondre.
En fait je me suis en effet trompé.
Je pensais avancer cet argument pour justifier que AP n'est pas récursive mais je n'en ai pas tant besoin.
Pour tout vous avouer, j'ose prétendre la chose suivante :
Il existe dans l'arithmétique (AP) des énoncés dont la décidabilité n'est pas décidable.

Je l'argumente ainsi :

Nous savons grâce à Gödel que pour tout énoncé A de l'arithmétique (notée AP) il existe un prédicat Théo(A) qui code le fait que A soit un théorème de AP (on a «*théo(A)=il existe y tel que prov(A,Y)*») donc le prédicat «*Dec(A)=théo(A) ou théo(nonA)*» est un prédicat affirmant que A est décidable dans AP, il devrait être codable aussi. Or si j'appelle E l'ensemble des énoncés décidables et G celui des énoncés indécidables dans AP alors E étant récursivement énumérable mais non récursif, on a G qui n'est pas récursivement énumérable (sinon E serait récursif), donc si pour toute formule A on a Dec(A) qui est dans E alors, si la décidabilité au sens de Gödel implique celle au sens de Turing (ce qu'on peut raisonnablement croire...), il existe un algorithme (une machine de Turing) qui s'arrête à coup sûr et décide pour chaque formule A de la validité de Dec(A), si bien qu'on saurait pour toute formule A si elle est décidable ou non, ce qui est contradictoire avec l'incomplétude de la théorie, donc je déduis qu'il existe une formule A telle que Dec(A) est dans G, c'est à dire l'existence d'une formule dont la décidabilité n'est pas décidable... Ceci impliquerait bien sûr qu'il y aurait une formule dont la décidabilité de la décidabilité ne serait pas décidable et donc l'existence, par induction, d'une chaine infinie...

Non ?

[Médiat]

on saurait pour toute formule A si elle est décidable ou non, ce qui est contradictoire avec l'incomplétude de la théorie

Je ne comprends pas ce point.

[A voir en vidéo sur Futura]

[ilelogique]

Oui vous avez raison, c'est plutôt contradictoire avec le fait que E n'est pas récursif, c'est ça ?

[ilelogique]

Ou bien qu'est-ce qui ne va pas dans la preuve ?

[inviteaf48d29f]

Je suis assez d'accord avec Mediat, lorsque vous dites : "si bien qu'on saurait pour toute formule A si elle est décidable ou non, ce qui est contradictoire avec l'incomplétude de la théorie"
c'est ce que vous cherchez à démontrer, vous ne pouvez pas l'utiliser.

L’incomplétude de la théorie fait qu'il existe au moins une formule A qui n'est pas décidable. Ce que vous dites là c'est que c'est alors contradictoire de dire que que la décidabilité de toute formule est décidable, ie que si on a une formule B alors Dec(B) est décidable. Mais ce n'est pas contradictoire, cet argument n'est pas suffisant.
On pourrait tout à fait imaginer qu'il existe une formule A indécidable et que pour tout B, Dec(B) est décidable. Du moment que A n'est pas de la forme Dec(B), mais ça n'est pas un problème.

[ilelogique]

Oui il ne faut pas dire "incomplétude" mais "non récursif" ?
En effet si Dec(A) est dans E pour tout A, alors il y aurait un algorithme décidant (en temps fini) pour toute formule F si F est dans E ou dans G, et E et G seraient récursifs, ce qui, je crois, est faux dans AP, non ?

Et on a bien qu'il existe un énoncé dont la décidabilité n'est pas décidable, non ??

[inviteaf48d29f]

En effet si Dec(A) est dans E pour tout A, alors il y aurait un algorithme décidant (en temps fini) pour toute formule F si F est dans E ou dans G

Encore une fois ce "alors" c'est ce que vous cherchez à démontrer, ça n'est pas du tout évident a priori.

Essayez peut-être d'écrire une vraie démonstration plutôt qu'un assemblage d'idées mises côte à côte, le problème de vos démonstrations c'est qu'elles sont très difficiles à lire et à comprendre de quoi vous parlez et où vous allez. J'ai peur de vous dire des bêtises et en tout cas de ne pas pouvoir vous aider beaucoup si vous ne rédigez pas un peu mieux ce que vous essayez de montrer.

[ilelogique]

Bonjour,
je ne crois pas que le "alors" dont vous parlez soit ce que je souhaite prouver.
j'essaie de redire :
je me place dans une théorie contenant l'arithmétique AP.
J'appelle E l'ensemble des énoncés décidables et G celui des énoncés indécidables. On sait que E est récursivement énumérable mais non récursif, donc G n'est pas récursivement énumérable.
Pour tout énoncé F, je note dec(F) = théo(F) ou théo(nonF). Ce prédicat est codable au sens de Gödel puisqu'on sait que théo(F) l'est.
Je suppose que pour tout F on a dec(F) qui est dans E.
Dans ce cas, en supposant que la décidabilité de Gödel coïncide avec celle de Turing, il existe un algorithme qui peut dire en un temps fini pour tout énoncé F si dec(F) est vrai ou faux, cet algorithme dira donc pour tout énoncé F si il est dans E ou dans G.
Donc G serait récursivement énumérable.
Contradiction.
Donc il existe un énoncé F tel que dec(F) est dans G.
Il existe ainsi un énoncé dont la décidabilité n'est pas décidable.

Qu'est-ce qui ne va pas dans ce que je dis svp ?

[invite6754323456711]

Bonjour,
une théorie dont l'ensemble des énoncés décidables est récursive est-elle complète ?

[HS]
Comment traduis-tu ces réflexions, portant sur un domaine loin du sens commun, dans les spectacles basés sur le principe "Une démarche scientifique ne peut pas exister sans pensée critique" ?
[/HS]

Patrick

[invite245dfd04]

Par définition ce sont des énoncés impossibles à démontrer ainsi que leurs négations. Mais cette notion
est toujours relative à un système de démonstrations (ou système formel), et il ne faut pas la
confondre avec celle de problèmes indécidables qui elle, est absolue.
Une fonction est calculable s'il existe une façon finie de la décrire qui permette effectivement d'en
calculer toutes les valeurs.
Lorsqu'on connait un algorithme pour résoudre un problème il est alors naturel de chercher à le généraliser (i.e. être plus tolérant dans les jeux de données acceptés).
A l'inverse quand on sait qu'un problème est indécidable, on cherche alors à en trouver des sous-problèmes décidables.

[invite6754323456711]

Par définition ce sont des énoncés impossibles à démontrer ainsi que leurs négations. ...

J'ai déjà lu cela quelque part avec les mêmes caractéristiques de présentation lié à un couper/coller sans reformatage

Patrick

[ilelogique]

Pour répondre à U sans fil : j'ai reconnu à mon deuxième message que je faisais erreur, merci de juger, svp, ma dernière proposition de preuve du fait qu'"il existe un énoncé dont la décidabilité n'est pas décidable", et non mes conneries, certes nombreuses...
Non ?

[ilelogique]

Je ne crois pas dire tant de choses fausses dans mes spectacles, je tâche de me documenter au préalable, la preuve... Venez y assister pour juger ! Je vous invite tous de bon cœur le 22 mars à la BNF !!

[invite6754323456711]

Je ne crois pas dire tant de choses fausses dans mes spectacles, je tâche de me documenter au préalable, la preuve... Venez y assister pour juger ! Je vous invite tous de bon cœur le 22 mars à la BNF !!

C'est un malentendu, ma question n'était pas une critique, mais un vrai intérêt sur ce genre d'exercice. Si vous passez dans le sud ouest de la France je viendrais avec grand plaisir.

Patrick

[Deedee81]

Salut,

Je vous invite tous de bon cœur le 22 mars à la BNF !!

Je ne savais pas qu'on organisait des spectacles à la Banque Nationale de France
(bref, c'est quoi la BNF ?)

[Amanuensis]

Bibliothèque Nationale de France? Spectacle sur le site de la Bibliothèque François Mitterrand à Paris? (En tout cas, c'est comme ça qu'un parisien comprend "à la BNF"...)

(Et il me semble qu'il n'y a pas de Banque Nationale de France, c'est juste "Banque de France"...)

[ilelogique]

Bonjour,
oui c'est bien à la bibliothèque : http://www.apmep-iledefrance.org/
Pas de souci, U100fil, avec plaisir, je peux vous tenir au courant par mail si vous le souhaitez...

Sinon, je vous remets ma dernière proposition (désolé d'insister mais je dois savoir, pour un article, si je peux ou non affirmer qu'il existe des énoncés dont la décidabilité n'est pas décidable...) :
je me place dans une théorie contenant l'arithmétique AP.
J'appelle E l'ensemble des énoncés décidables et G celui des énoncés indécidables. On sait que E est récursivement énumérable mais non récursif, donc G n'est pas récursivement énumérable.
Pour tout énoncé F, je note dec(F) = théo(F) ou théo(nonF). Ce prédicat est codable au sens de Gödel puisqu'on sait que théo(F) l'est.
Je suppose que pour tout F on a dec(F) qui est dans E.
Dans ce cas, en supposant que la décidabilité de Gödel coïncide avec celle de Turing, il existe un algorithme qui peut dire en un temps fini pour tout énoncé F si dec(F) est vrai ou faux, cet algorithme dira donc pour tout énoncé F si il est dans E ou dans G.
Donc G serait récursivement énumérable.
Contradiction.
Donc il existe un énoncé F tel que dec(F) est dans G.
Il existe ainsi un énoncé dont la décidabilité n'est pas décidable.

Qu'est-ce qui ne va pas dans ce que je dis svp ?

[Deedee81]

Bibliothèque Nationale de France? Spectacle sur le site de la Bibliothèque François Mitterrand à Paris? (En tout cas, c'est comme ça qu'un parisien comprend "à la BNF"...)

(Et il me semble qu'il n'y a pas de Banque Nationale de France, c'est juste "Banque de France"...)

Merci,
(je devrais aller plus souvent en France )

[inviteaf48d29f]

J'arrive beaucoup mieux à lire la preuve maintenant et elle me semble tout à fait valable, je ne vois plus de point douteux.

[Médiat]

Bonjour,

il existe un algorithme qui peut dire en un temps fini pour tout énoncé F si dec(F) est vrai ou faux

Etes-vous en train de dire que AP est décidable ?

[Deedee81]

Bonjour,

A lire :
http://www.pourlascience.fr/ewb_page...lcul-32661.php

Très intéressant. La méthode permet par exemple de calculer ce qui n'est pas nécessairement calculable par une machine de Turing (par exemple le problème de l'arrêt). Bien entendu Delahaye explique pourquoi.

Très instructif.

[ilelogique]

Bonsoir,
désolé, je n'avais pas vu que vous aviez répondu.

Pour répondre à Médiat, on sait que E (l'ensemble des énoncés décidables de AP) est récursivement énumérable mais non récursif (donc E et à fortiori AP n'est pas décidable), donc il me semble que ça veut dire qu'il existe une machine de Turing qui pour tout énoncé dira après un temps fini si l'énoncé est dans E ou pas.

non ?

Qui ne valide pas ma preuve svp ?
merci.

Pour l'article cité, oui, ça a l'air intéressant mais on ne peut pas lire la suite sans acheter...

[Médiat]

Bonsoir,

on sait que E (l'ensemble des énoncés décidables de AP) est récursivement énumérable

Vous avez une référence pour ce théorème ?

[Médiat]

Bonjour,

Vous avez une référence pour ce théorème ?

Ne cherchez pas, j'ai lu trop vite (du coup c'est moi qui ai fait une confusion entre décidabilité logique et algorithmique).

[ilelogique]

Au quai,
pas de sous si...
Mais donc, quid ?
validez-vous ou pas ?
qu'apportez-vous contre ?
ou bien est-il vrai ce que je propose ?
Merci.

[ilelogique]

Il existe des énoncés dont la décidabilité n'est pas décidable...
Ou bien pas ?

[ilelogique]

Excusez-moi d'insister, mais si personne ne me répond, dois-je en conclure :
- Que vous êtes d'accord avec ma proposition ?
- Que vous êtes en train de chercher à la réfuter ?
- Que ça ne vous parait pas intéressant ?

je la remets, au cas où... :


On se place dans une théorie contenant l'arithmétique AP.
J'appelle E l'ensemble des énoncés décidables et G celui des énoncés indécidables. On sait que E est récursivement énumérable mais non récursif, donc G n'est pas récursivement énumérable.
Pour tout énoncé F, je note dec(F) = théo(F) ou théo(nonF). Ce prédicat est codable au sens de Gödel puisqu'on sait que théo(F) l'est.
Je suppose que pour tout F on a dec(F) qui est dans E.
Dans ce cas, en supposant que la décidabilité de Gödel coïncide avec celle de Turing, il existe un algorithme qui peut dire en un temps fini pour tout énoncé F si dec(F) est vrai ou faux, cet algorithme dira donc pour tout énoncé F si il est dans E ou dans G.
Donc G serait récursivement énumérable.
Contradiction.
Donc il existe un énoncé F tel que dec(F) est dans G.
Il existe ainsi, dans AP, un énoncé dont la décidabilité n'est pas décidable.

[ilelogique]

Je ne comprends pas,
quelqu'un peut-il me dire, svp, pourquoi personne ne répond à ma question ?
elle n'en est pas digne ??
Merci,