L'ensemble des phrases valides dans FO n'est pas décideable en conséquence de Rec. inséparabilité
-
05-11-2019 - |
Question
Deux langues données $ l_1 $ et $ l_2 $ sont appelées séparable récursivement si il existe une langue récursive $ r $ telle que $ l_1 subseseq r $ et $ l_2 cap r = videset $.
Considérons maintenant la logique de première commande et une axiomatisation finie de $ mathbb n $ (c'est sûrement une façon de faible, car nous n'avons pas d'induction). Ensuite, nous avons trois ensembles, 1) l'ensemble des phrases valides, c'est-à-dire celles dérivées des règles de la logique de premier ordre, 2) l'ensemble des phrases prouvables en utilisant les axiomes de $ mathbb n $ et l'ensemble des phrases de vérité, c'est-à-dire ceux remplis par $ mathbb n $. Aussi en superset de tout cela, nous avons l'ensemble des phrases de premier ordre qui ont un modèle, et contrairement à cet ensemble de phrases qui ne sont pas satisfaisantes, c'est-à-dire aucun modèle, qui est égal (par exhaustivité de la logique de premier ordre) de phrases incohérentes.
Maintenant, ce qui suit est soutenu:
Théorème: L'ensemble des phrases insatisfaisantes et l'ensemble des phrases prouvables à partir des axiomes choisis de $ mathbb n $ ne sont pas séparables récursivement.
À partir de cela, il s'ensuit que l'ensemble des phrases prouvables des axiomes elle-même, ainsi que les phrases de vérité, ainsi que l'ensemble des phrases satisfaisantes, ne sont pas récursives / décidables.
Mais cela implique-t-il que l'ensemble des phrases valides n'est pas décidable? Ceci est des états dans le texte classique Complexion informatique Par Cristos H. Papadimitriou, à la page 133. Mais comme cet ensemble est un sous-ensemble approprié des phrases prouvables, je ne vois pas que cela est impliqué par le théorème ci-dessus? Ou est-ce que je manque quelque chose?
Pas de solution correcte