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

Автор темы ivvol 
ОбъявленияПоследний пост
ОбъявлениеПравила и принципы форума «Высшая математика»28.10.2009 15:17
ОбъявлениеВакансия: Разработчик WebCrawler и аналитик данных16.11.2015 10:19
ОбъявлениеАспирантура в Норвегии и Германии07.12.2015 14:00
25.12.2016 16:52
Теория моделей, матлогика. Полные теории
Добрый вечер!
Пусть $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$?

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

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

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

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

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



Редактировалось 1 раз(а). Последний 25.12.2016 16:53.
25.12.2016 18:53
Пояснения
Теория моделей, матлогика. Полные теории new
Добрый вечер!
Пусть T - теория сигнатуры $σ=<\le>$, задаваемая следующей системой аксиом:
A1-$∀x(x\lex)$
A2-$∀x∀y((x\ley∧y\lex)→x=y)$
A3-$∀x∀y∀z((x\ley∧y\lez)→x\lez)$
A4-$∀x∀y(x\ley∨y\lex)$
A5-$∀x∀y((x\ley∧¬x=y)→∃z(x\lez∧z\ley∧¬x=z∧¬z=y))$

Ваша аксиоматика представляет теорию линейного плотного порядка. Она в счетной мощности "почти" категорична, точнее имеет четыре попарно неизоморфные счетные модели. Эти модели определяются наличием/отсутствием концевых элементов (наименьший и наибольший элементы называем концевыми).
Для начала докажите, что два линейных плотных порядка без концевых элементов счетной мощности изоморфны. Потом разберитесь, какие варианты неизоморфных моделей возможны (в зависимости от крайних элементов).
Потом - теорема о полноте.
Замечания: 1) знак меньше или равно записывается здесь как простое \le, иначе Ваши формулы не читаются.
2)
Цитата

Вот определение вызывает у меня проблемы:
Теория T называется полной, если для любой формулы $A$ теория содержит $A$ или $¬A$ .
Проблема, вероятно, связана с непривычным использованием термина "содержит" = "принадлежит". Здесь принадлежность формулы теории означает, что формула доказуема из приведенных аксиом (т.е. принадлежит множеству доказуемых формул = дедуктивному замыканию).
Это и есть определение полной теории. Любая формула либо доказуема, либо опровержиа (доказуемо отрицание).
3)
Цитата

Нашел теорему, по которой если не существует конечных моделей и любые две счётные модели изоморфны, то теория полна.
Это есть следствие теоремы о полноте и теоремы Левенгейма-Сколема (впрочем, она сама - следствие теоремы полноты).
4)
Цитата

множество вещественных чисел
Это множество не является счетным и в этой мощности неизоморфных моделей сильно много.
Счетным является множество рациональных чисел.



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

Все верно?

Получается 4 варианта моделей, и, соответственно, полных теорий (я ведь все правильно понял?):
1) без концевых вообще
2) есть наибольший, но нет наименьшего
3) есть наименьший, но нет наибольшего
4) есть и наименьший, и наибольший

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

Итого, ответ - 4 полные теории



Редактировалось 1 раз(а). Последний 25.12.2016 20:17.
26.12.2016 09:58
Примерно так
Набросок доказательства подходящий, ответ верный.
Надо быть готовым ответить на вопрос, почему количество полных расширений равно количеству неизоморфных моделей счетной мощности.
26.12.2016 11:30
Ответ на вопрос
Потому что модели из разных групп (1-4) задаются разными расширениями первоначальной теории.
Так, например, для 1ой группы в теорию добавятся следующие аксиомы:

$ \forall x \exists y (x \le y) & \neg (x = y) $ - отсутствие максимального элемента
$ \forall x \exists z (z \le x) & \neg (x = z) $ - отсутствие минимального

Соответственно, четыре попарно неизоморфных класса моделей, четыре различных расширения.
26.12.2016 16:27
Это хорошо, но еще осталось
Цитата

Потому что модели из разных групп (1-4) задаются разными расширениями первоначальной теории.
Так, например, для 1ой группы в теорию добавятся следующие аксиомы:
Действительно, здесь очень важно было заметить, что предъявленные модели не только попарно не изоморфны, но еще и не элементарно эквивалентны (т.е. имеют различные теории; множество формул, выполняющихся на данной модели, образуют полную непротиворечивую теорию этой модели).
Это важно, т.к. в несчетной мощности неизоморфных моделей о-чень много (как Вы думаете, сколько их в мощности континуум), а расширяющих теорий только 4. Т.е. имеются неизоморфные, но элементарно эквивалентные модели.

Осталось обосновать вторую часть: почему нет пятой расширяющей непротиворечивой полной теории? Т.е. каждая теория связана с моделью.
27.12.2016 20:21
Остаток
Я понимаю, что все вариации счетных множеств исчерпываются четырьмя вариантами, но не придумаю, с чего начать доказательство отсутствия пятой :(
Пытался доказать через категоричность теорий, пользуясь пособием Дудакова по основам теории моделей, но безрезультатно. Может вы подскажете хорошую литературу по этой теме?
27.12.2016 22:52
Мысль
Вроде понял. Существует предложение о том что теория плотного линейного порядка без первого
и последнего элемента не является A-категоричной для любого несчетного
кардинала A. Доказательство есть как раз в пособие Дудакова.
Получается, что пятой полной теории не может быть, потому что остались только несчетные модели, которые друг другу не изоморфны, хоть их и очень много. (сюда попадают и модели, множество которых имеет мощность континуум)
27.12.2016 23:45
С чего начать:
Факты:
1. Если две модели изоморфны, то их теории совпадают (в любых языках, а не только первой ступени).
2. Теорема о полноте.
Если Т - непротиворечивая теория в языке первой ступени сигнатура которого не более чем счетна, то она
имеет модель мощности не более чем счетной.
3. Предположим, что W - некоторая полная непротиворечивая теория расширяющая данную Вашу теорию. Тогда имеет не более чем счетную модель. Но т.к. Ваша теория не имеет конечных моделей, то она имеет счетную модель. Но эта модель изоморфна одной из четырех моделей. Следовательно, W совпадает с одной из 4-х теорий.

Дополнение:
Если выполняется аксиома выбора (обычно это молчаливо предполагается), то теорема о полноте распространяется на несчетные языки:
Непротиворечивая теория имеет модель мощности не меньше мощности языка.
В частности, отсюда следует теореме Левенгейма-Сколема на подъем:
Если теория имеет бесконечную модель, то она имеет модели в любой мощности не меньшей мощности языка (т.е. мощности моделей сколь угодно большие).
Верна и теорема Левенгейма-Сколема на спуск:
Если М - модель теории и ее мощность превосходит мощность языка, то эта модель содержит элементарныее подмодели мощностей не меньших мощности языка. (т.е. в модели теории содержаться подмодели всех малых мощностей от мощности языка и более).

По моделям можно судить о полноте теории.
Если теория Т категорична в какой-нибудь бесконечной мощности, то она полна.
При этом теория может не быть категорична в других мощностях.
Пример 1. Теория линейного плотного порядка без концевых элементов категорична в счетной мощности и, значит, полна. Эта теория не категорична в несчетных мощностях. Это можете подоказывать.
Пример 2. Теория алгебраически замкнутых полей характеристики ноль категорична в любой несчетной мощности. Значит, она полна. Эта теория некатегорична в счетной мощности.

Больше сведений о категоричности в мощностях полных теорий можно узнать из книжек по теории моделей. Самая простенькая и небольшая - Дж. Сакс, Теория насыщенных моделей.
22.01.2017 18:28
А для конечного?
А если взять некоторое расширение нашей теории, для которого будет существовать класс моделей, состоящих из одного элемента (те в множесте, на котором задана модель - всего один элемент) - будет ли эта теория полной? Или как доказать, что она не полная?
Как вариант, нужно придумать такое высказывание, для которого ни $\phi$, ни $\neg \phi$ не содержатся в этой теории, но мне пока на ум ни одной не пришло.



Редактировалось 1 раз(а). Последний 22.01.2017 18:29.
23.01.2017 00:02
Вопрос оригинальный
Цитата

А если взять некоторое расширение нашей теории, для которого будет существовать класс моделей, состоящих из одного элемента (те в множестве, на котором задана модель - всего один элемент) - будет ли эта теория полной?
Приведенная Вами теория не имеет конечных моделей, следовательно, никакое ее расширение таких моделей не имеет. Собственно, как было замечено, расширений у данной теории немного.
Возможно, Вы имели ввиду не данную теорию, а просто теорию линейного порядка. Такая теория имеет конечные модели любой мощности ( с любым конечным числом элементов). Для любого $n$ имеется ровно одна (с точностью до изоморфизма) модель из $n$ элементов. Ей соответствует теория (разумеется, полная), которую можно получить дописав одну аксиому:
Существуют $x_1<...<x_n$ такие, что для любого $x$ имеет место $x_1=x\bigveex_2=x\bigvee....\bigveex_n=x$.



Редактировалось 1 раз(а). Последний 23.01.2017 00:09.
23.01.2017 00:52
Но все таки
Возьмем аксиомы, заданные условием задачи и прибавим к ним еще одну $ \forall x \forall y (x=y)$. Таким образом получается, что для множества, например M={1}, все аксиомы верны:
$ 1 \leqslant 1 $ - верно
$ (1 \leqslant 1) \wedge (1 \leqslant 1) \rightarrow (1 = 1)$ - верно
$ (1 \leqslant 1) \wedge (1 \leqslant 1) \rightarrow (1 \leqslant 1)$ - верно
$ (1 \leqslant 1) \vee (1 \leqslant 1)$ - верно
$ ((1 \leqslant 1) \wedge \neg (1 = 1)) \rightarrow ((1 \leqslant 1) \wedge (1 \leqslant 1) \wedge \neg (1 = 1) \wedge \neg (1 = 1))$ -верно ($0 \rightarrow 0 = 1$)
$ (1=1) $ - верно
получается что есть. поправьте, если я не прав.

Выписка из Вики:
"Если на алгебраических системах A и B истинны одни и те же замкнутые формулы, то A и B называются элементарно эквивалентными. Таким образом, если A и B элементарно эквивалентны, тогда теория полна.

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

Теорема: Если любые две модели непротиворечивой теории $\mathcal T$ элементарно эквивалентны, она полна.

Доказательство: От противного, пусть $\mathcal T$ неполна, и значит, существует замкнутая формула $\varphi$ такая, что $\{\varphi,\neg\varphi\}$ не лежит в $\mathcal T$. Образуем теории $\mathcal T_1 = \{\chi : \mathcal T,\varphi \models \chi\}$, $\mathcal T_2 = \{\chi : \mathcal T,\neg\varphi \models \chi\}$, обе непротиворечивые и имеющие потому хотя бы по модели, скажем, соответственно $\mathcal M_1,\mathcal M_2$. В $\mathcal M_1$ формула $\varphi$ истинна, в $\mathcal M_2$ ложна, так что они не элементарно эквивалентны; противоречие.
23.01.2017 23:22
Все верно
В моем предыдущем посте предлагался более общий вид расширений, имеющих только одну конечную модель.
То, что существует линейный порядок, содержащий единственный элемент, Вы доказали. Рассмотрением кусочка натурального ряда легко доказывается, что существует линейный порядок с любым данным конечным числом элементов.
Вот это утверждение:
Цитата

Если на алгебраических системах A и B истинны одни и те же замкнутые формулы, то A и B называются элементарно эквивалентными. Таким образом, если A и B элементарно эквивалентны, тогда теория полна.
непонятно, что означает. Но похоже, что что-то неверное. Хорошо бы иметь ссылку из Вики.
А это утверждение верное:
Цитата

Если полная теория T имеет конечную модель A, то все модели теории T изоморфны A, в частности, все они содержат такое же количество элементов. Следовательно, для конечных алгебраических систем понятия элементарной эквивалентности и изоморфизма совпадают.
Но препод может попросить доказательство. Оно несложно. Если $М$ - конечная модель полной теории, то берем новые (не входящие в сигнатуру) константы для каждого элемента модели. Рассмотрим $D$ - конъюнкцию всех атомарных формул и их отрицаний , содержащих только константы, включая и новые, которые выполняются в данной модели.
Потом заменим новые константы различными переменными и свяжем всю формулу кванторами существования. Т.к. эта формула истинна в модели полной теории, то она доказуема и выполняется в любой модели. Но полученная формула определяет модель с точностью до изоморфизма.
Заполните пробелы в этом доказательстве. В этом рассуждении мы молчаливо предположили, что сигнатура конечна (только конечное число атомарных формул можно собрать в одну конъюнкцию), но это не существенно.
Теорема об ее-эквивалентности любых двух моделей доказана верно.
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти