Является ли полной теория $% \{ \exists x P(x), \exists x Q(x), \forall x(\neg P(x) \vee \neg Q(x)) \} $% сигнатуры {P, Q} (т.е. двух одноместных предикатных символов)?

задан 9 Дек '16 2:44

изменен 9 Дек '16 3:35

Условие надо сформулировать точно. Теория бывает не у самих сигнатур, а у моделей определённой сигнатуры. Далее, вместо "их", наверное, имелось в виду "из", то есть это опечатка. А заглавной буквы X в конце быть не должно.

(9 Дек '16 3:26) falcao
10|600 символов нужно символов осталось
1

Теперь условие исправлено, и это хорошо.

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

У нас имеются два свойства: P и Q. Для любого из свойств существует элемент, им обладающий, и никакой элемент не обладает сразу двумя свойствами.

Рассмотрим одну модель, в которой есть два элемента. Первый из них обладает свойством P, но не обладает свойством Q. Второй элемент -- наоборот.

В другой модели оставим эти два элемента, добавляя к ним третий, не обладающий никаким из двух свойств.

Формула $%(\forall x)(P(x)\lor Q(x))$% истинна на первой модели и ложна на второй. Это значит, что ни сама эта формула, ни её отрицание, не выводимы из аксиом теории. Тем самым, она неполна.

ссылка

отвечен 9 Дек '16 4:17

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×872
×408

задан
9 Дек '16 2:44

показан
724 раза

обновлен
9 Дек '16 4:17

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru