Теория моделей, матлогика. Полные теории

[Iv_Vol]

Пусть $T$ - теория сигнатуры $\sigma = <\leqslant>$, задаваемая следующей системой аксиом:
$ A1: \forall x (x \leqslant x)$
$ A2: \forall x \forall y ((x\leqslant y \wedge y\leqslant x) \to x = y)$
$ A3: \forall x \forall y \forall z ((x\leqslant y \wedge y \leqslant z) \to x\leqslant z)$
$ A4: \forall x \forall y (x\leqslant y \vee y \leqslant x)$
$ A5: \forall x \forall y ((x\leqslant y \wedge \neg x = y) \to \exists z (x \leqslant z \wedge z \leqslant y \wedge \neg x = z \wedge \neg z = y)) $

Сколько существует полных теорий сигнатуры $\sigma$, расширяющих теорию $T$?

Получается, что в задаче нужно найти все возможные теории, которые содержат в себе А1-А5, расширяя теорию $T$ и являются полными.

Аксиомы, заданные условием задачи мне понятны, $A1$- рефлексивность, $A2$- антисимметричность, $A3$ - транзитивность,$A4$- условие того, что порядок в двух элементах определяется однозначно, $A5$ - условие того, что если неравенство строгое, то между двумя элементами всегда найдется третий.

Вот определение вызывает у меня проблемы:
Теория $T$ называется полной, если для любой формулы $A$ теория содержит $A$ или $\neg A$ .

Объясните, пожалуйста, определение полной теории, или подскажите, где об этом можно почитать.

[iifat]

А что тут понимать? Просто привыкнуть надо, наверное. Всё, что мы можем записать в рамках теории, мы можем доказать либо опровергнуть.

[Iv_Vol]

iifat в сообщении #1179790 писал(а):

Всё, что мы можем записать в рамках теории, мы можем доказать либо опровергнуть.

Да, я понимаю, когда речь идет об абстрактных теориях. Я не понимаю, как это применить на практике. Как записать хотя бы одну теорию Т1, которая будет расширять Т и являться полной?
Прочесываю интернет, но кроме определений не могу ничего найти :(

[Karan]

Например, можно взять какую-то конкретную модель и множество истинных утверждений в ней.

Поправьте, пожалуйста, формулы в первом сообщении - формулы должны быть целиком в долларах, а не отдельные знаки. И маленькие формулы типа $A$, $\neg A$, $T$, $T_1$ тоже оформить надо.

[Karan]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Karan]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[Iv_Vol]

Karan
Возьмем, к примеру, множество вещественных чисел. Аксиомы этой теории будут верны, вещественные числа можно упорядочить и множество является плотным, те между каждыми двумя элементами найдется третий. Тогда чем я могу расширить эту теорию?
Запишем:
$\forall x \exists z (z \leqslant x) $
Но ведь добавив лишь это одно утверждение мы не сделаем теорию полной?
Допустим, я написал некое множество утверждений, которые расширяют теорию до полной. А теперь я поменяю их местами (относительно друг друга). Будет ли это новой теорией?
Если нет, то получается что полная теория будет только одна?

[arseniiv]

Вы уже расширили аксиоматическую теорию $T$ теорией алгебраической системы $\langle\mathbb R,\leqslant\rangle$. Сама она — не $T$, в ней действительно больше формул, в том числе упоминающаяся вами $\forall x \exists z (z \leqslant x)$.

Iv_Vol в сообщении #1179878 писал(а):

Допустим, я написал некое множество утверждений, которые расширяют теорию до полной. А теперь я поменяю их местами (относительно друг друга). Будет ли это новой теорией?

Нельзя «поменять местами» элементы множества. Для множества определены только вхождение/невхождение туда элемента, но ни их порядка, ни кратности.

[Iv_Vol]

arseniiv
Понял, спасибо, одним вопросом стало меньше

Нашел теорему, по которой если не существует конечных моделей и любые две счётные модели изоморфны, то теория полна.
Значит, обязательно к добавлению условие отсутствия минимума.
Тогда нужно еще разобраться с изоморфными моделями. Да и будут ли таким образом исчерпываться все полные теории?

[arseniiv]

Iv_Vol в сообщении #1179892 писал(а):

Нашел теорему, по которой если не существует конечных моделей и любые две счётные модели изоморфны, то теория полна.

Теория алгебраической системы полна практически по определению, если что.

Iv_Vol в сообщении #1179892 писал(а):

Тогда нужно еще разобраться с изоморфными моделями. Да и будут ли таким образом исчерпываться все полные теории?

Если имелись в виду всё-таки неизоморфные, то т. к. теория модели полной теории с той же сигнатурой не может не совпадать с последней (проверьте), это будет означать, что у какой-то полной теории нет модели. Это бывает, если в определение полной теории не включали непротиворечивость, но обычно интересуют всё же непротиворечивые.

[Iv_Vol]

Итак, я попробую заново
Аксиомы 1-5 являются теорией линейного плотного порядка. В счетной мощности (мы ведь рассматриваем только счетные модели) есть только четыре не изоморфные друг другу модели. Отличаются они наличием концевых элементов:
1) без концевых вообще
2) есть наибольший, но нет наименьшего
3) есть наименьший, но нет наибольшего
4) есть и наименьший, и наибольший

для двух моделей, которые содержатся в одной и той же группе (1-4) можно установить изоморфизм

рассмотрим для первой группы: Берем $X$ и $Y$ - два счетных плотных л.у.м. без концевых. Строим изоморфизм в n элементов. Получаем два подмножества $Xn$, $Yn$ и взаимно однозначное соответствие между ними, с сохранением порядка. Берем некий элемент из $X$, которого нет в $Xn$, сравниваем с элементами из $Xn$. Он либо больше, либо меньше, либо где-то между ними. В любом случае мы можем найти аналогичный элемент в $Y$. Добавляем эти элементы в $Xn$ и $Yn$, создавая соответствие между ними.
Нужно сделать так, чтобы все элементы из обоих множеств оказались охваченными. Т.к. каждое из них счетное - нумеруем их и выбираем элемент с наименьшим номером. Например на четных $n$ - из $Y$, а на нечетных - из $X$. Таким образом устанавливаем изоморфизм.

Подобным образом можно действовать для любой группы.
Итого - 4 полных теории.

Все ли верно?

[knizhnik]

Iv_Vol в сообщении #1179781 писал(а):

Сколько существует полных теорий сигнатуры $\sigma$, расширяющих теорию $T$?

Бесконечно много. Противоречивая теория по определению полна, а неверных утверждений для вашей теории можно придумать в неограниченном количестве. А если теория непротиворечива и если найден способ дополнить ее непротиворечиво до полноты, то можно взять любую из добавленных аксиом и приписать к ней любую теорему через конъюнкцию. Или любое предложение через дизъюнкцию. И получится снова полная теория.

[arseniiv]

Теория — это множество формул, замкнутое относительно логического следования. Вы не можете добавить просто одну формулу, не добавив к ней конъюнкцию её с чем-то, содержащимся в старом варианте теории.

[knizhnik]

Теория первого порядка - это множество аксиом. Более подробно: предложений, записанных в логике первого порядка. Множества будут различны, если синтаксически различны их элементы.

[Karan]

knizhnik в сообщении #1180055 писал(а):

Противоречивая теория по определению полна, а неверных утверждений для вашей теории можно придумать в неограниченном количестве.

То, что неверных утверждений много, не имеет значения, противоречивая теория все равно единственна.

knizhnik в сообщении #1180055 писал(а):

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

И получится то же самое, потому что конъюнкция теорем - это теорема.

knizhnik в сообщении #1180065 писал(а):

Теория первого порядка - это множество аксиом.

Нет, теория - это множество теорем.

knizhnik, прошу воздержаться в "Помогите решить/разобраться" от ответов на вопросы, в которых Вы не разбираетесь.