Разобраться с формальными системами

[AlexDem]

Разбираю такое предложение:

Цитата:

Предложение $\varphi$ является следствием теории $T$, если в любой модели теории $T$ предложение $\varphi$ истинно. Теория $T$ в рекурсивном языке рекурсивно аксиоматизируема тогда и только тогда, когда множество всех следствий теории $T$ рекурсивно перечислимо.

Допустим у нас есть рекурсивно аксиоматизируемая теория и в ней присутствуют предложения, которые могут быть истинными или ложными в зависимости от интерпретации. Если задать интерпретацию для теории, часть из этих предложений станут истинными, т.е. множество истинных предложений возрастёт. Останется ли оно рекурсивно перечислимым?

По-моему - не всегда, т.к. добавив все эти предложения в качестве аксиом, получили бы полную и непротиворечивую теорию. Насколько я прав?

[epros]

По-моему, можно взять любое нерекурсивное подмножество предложений языка, дополнить его множеством следствий теории и вычесть из него множество отрицаний следствий теории. В итоге получим нерекурсивную интерпретацию теории.

А вот идея с добавлением ВСЕХ этих предложений в качестве аксиом, насколько я понимаю, не годится, поскольку у нас тогда получится нерекурсивное множество аксиом, чего в осмысленных теориях не бывает.

[AlexDem]

epros в сообщении #591594 писал(а):

поскольку у нас тогда получится нерекурсивное множество аксиом

Почему? По-моему, это так не всегда. И как раз в этом и состояло моё предположение, которое я хотел проверить (в силу цитаты в первом сообщении).

[epros]

AlexDem в сообщении #591600 писал(а):

Почему? По-моему, это так не всегда.

Что почему? Разумеется, теоретически мы имеем право рассматривать и нерекурсивно аксиоматизируемые теории. Но для такой теории невозможно проверить, является ли предложение аксиомой, так что на практике от такой теории мало проку - вряд ли в ней что-либо удастся реально доказать.

[AlexDem]

epros в сообщении #591602 писал(а):

Что почему?

Почему вдруг сразу получится нерекурсивное множество аксиом?

[epros]

AlexDem в сообщении #591605 писал(а):

Почему вдруг сразу получится нерекурсивное множество аксиом?

Если я правильно понял Вашу идею, у Вас было рекурсивно перечислимое множество следствий теории, и Вы хотели дополнить его до нерекурсивного множества? Причём дополнение - это и есть множество новых аксиом?

[AlexDem]

Нет. У меня была рекурсивная система аксиом теории. Из них по правилам вывода получаются все следствия теории, пусть это будет множество $D$. Дополнение $U \setminus D$ этого множества до множества всех формул $U$, насколько я понимаю, - это ещё не множество ложных формул, там есть как ложные, так и те, которые могут быть либо истинными, либо ложными в зависимости от интерпретации.

Выберем некоторую интерпретацию теории. Тогда все переменные получат свои значения, соответственно - все формулы станут либо истинными, либо ложными. Ставится вопрос о рекурсивной перечислимости множества истинных формул в заданной интерпретации.

PS: Занятно... Вот ещё из другого источника:

Цитата:

В любой формальной системе $F$ совокупность слов, выводимых из произвольного рекурсивно перечислимого множества слов $U$, является рекурсивно перечислимой.

С учётом цитаты в первом сообщении получается, что рекурсивной перечислимости множества аксиом достаточно для его рекурсивности?

[epros]

AlexDem в сообщении #591630 писал(а):

Ставится вопрос о рекурсивной перечислимости множества истинных формул в заданной интерпретации.

А что мешает выбрать нерекурсивную интерпретацию? Например, вот так:

epros в сообщении #591594 писал(а):

взять любое нерекурсивное подмножество предложений языка, дополнить его множеством следствий теории и вычесть из него множество отрицаний следствий теории

AlexDem в сообщении #591630 писал(а):

получается, что рекурсивной перечислимости множества аксиом достаточно для его рекурсивности?

Его - это множества аксиом? Рекурсивность (разрешимость) = перечислимость + перечислимость дополнения. Поэтому перечислимости, вообще говоря, недостаточно для рекурсивности.

[AlexDem]

epros в сообщении #591644 писал(а):

А что мешает выбрать нерекурсивную интерпретацию? Например, вот так:

epros в сообщении #591594 писал(а):

взять любое нерекурсивное подмножество предложений языка, дополнить его множеством следствий теории и вычесть из него множество отрицаний следствий теории

Разность множеств здесь может оказаться рекурсивной.

-- Вт июл 03, 2012 18:46:41 --

epros в сообщении #591644 писал(а):

Поэтому перечислимости, вообще говоря, недостаточно для рекурсивности.

Это понятно, но я же рассмотрел частный случай.

[AGu]

AlexDem в сообщении #591630 писал(а):

С учётом цитаты в первом сообщении получается, что рекурсивной перечислимости множества аксиом достаточно для его рекурсивности?

У одной и той же теории есть куча разных множеств аксиом. (Каждое из этих множеств аксиом порождает одно и то же множество следствий -- множество следствий данной теории.) Так вот, упомянутые Вами факты говорят о том, что из существования рекурсивно перечислимого множества аксиом следует существование (возможно, какого-то другого) рекурсивного множества аксиом.

[AlexDem]

Да, скорей всего - так, если в этих двух книгах нет расхождения в понятиях. Спасибо.