Противоречивость теорий

[pink Elephant]

Даны две теории $T_1$ и $T_2$ над сигнатурой $\sigma$. Доказать(или опровергнуть), что если $T_1$$\cup$$T_2$ не имеет модели, то $\exists\varphi:T_1\vdash\varphi,T_2\vdash\neg\varphi$.
Тут надо сделать одно важное уточнение, что мой преподаватель вводит определение теории немного не так, как в некоторых источниках. А именно, теория это набор утверждений, замкнутых относительно вывода, то есть про непротиворечивость ничего не сказано.
Долго думал над задачей, но так и не пришел даже к определенному выводу о том, что нужно делать -- доказывать или опровергать. Но склоняюсь к тому, что все же опровергать. Идей было много, но все ни к чему не привели. Пробовал контрпример придумать, но уперся в то, что нужно тогда все формулы найти выводимые из теории и доказать, что других нету, а это сделать я не смог.

[mihaild]

Теорему о том, что наличие модели равносильно непротиворечивости, вы знаете?

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

(Оффтоп)

А в каких источниках требуется непротиворечивость теории? Доказывается ли в них, что теория, в которой мы рассуждаем - действительно теория?

[pink Elephant]

mihaild в сообщении #1191501 писал(а):

Теорему о том, что наличие модели равносильно непротиворечивости, вы знаете?

Да, конечно, без нее даже смысл задачи было бы трудно уловить.

mihaild в сообщении #1191501 писал(а):

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

Я пока писал пример теории $T_1$ вроде бы придумал доказательство. Пусть $T_1$ противоречиво. Тогда $T_1$ содержит абсолютно все предложения над сигнатурой. Возьмем за $\varphi$ любое предложение из $T_2$, тогда $T_1$ содержит его отрицание. Аналогично для $T_2$. Теперь рассмотрим случай, когда ни $T_1$, ни $T_2$ не являются противоречивыми. Если их объединение противоречиво, то значит оно содержит некоторое $\varphi$ и $\neg\varphi$, причем одновременно в $T_1$ или в $T_2$ они лежать не могут, в силу их непротиворечивости. Только как доказать, что противоречивая теория содержит все предложения над сигнатурой?

[mihaild]

pink Elephant в сообщении #1191507 писал(а):

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

$\bot \rightarrow A$ является тавтологией исчисления высказываний. Подставив вместо пропозициональных переменных формулы исчисления предикатов в тавтологию исчисления высказываний, мы получаем тавтологию исчисления предикатов. В частности, выводимую.

Сначала не заметил, что у вас требуется замкнутость теории относительно выводимости. Тогда $T_1 \cup T_2$ может вообще не быть теорией.

[pink Elephant]

mihaild в сообщении #1191510 писал(а):

Сначала не заметил, что у вас требуется замкнутость теории относительно выводимости. Тогда $T_1 \cup T_2$ может вообще не быть теорией.

Ну, я не точно процитировал задачу. Там было "множество предложений $T_1 \cup T_2$ не имеет модели".

mihaild в сообщении #1191510 писал(а):

$\bot \rightarrow A$ является тавтологией исчисления высказываний. Подставив вместо пропозициональных переменных формулы исчисления предикатов в тавтологию исчисления высказываний, мы получаем тавтологию исчисления предикатов. В частности, выводимую.

Теперь понял и разобрался, спасибо.

[mihaild]

Пусть $T_1 \cup T_2$ противоречива. Тогда из некоторого конечного набора утверждений, входящих в $T_1 \cup T_2$, выводится противоречие. Часть из этих утверждений входит в $T_1$, часть в $T_2$; обозначим конъюнкции этих частей $A$ и $B$. Имеем $\vdash A \wedge B \rightarrow \bot$. Что можно сказать про выводимость $B$ и $\neg B$ в $T_1$ и $T_2$?

[pink Elephant]

pink Elephant в сообщении #1191507 писал(а):

Пусть $T_1$ противоречиво. Тогда $T_1$ содержит абсолютно все предложения над сигнатурой. Возьмем за $\varphi$ любое предложение из $T_2$, тогда $T_1$ содержит его отрицание. Аналогично для $T_2$. Теперь рассмотрим случай, когда ни $T_1$, ни $T_2$ не являются противоречивыми. Если их объединение противоречиво, то значит оно содержит некоторое $\varphi$ и $\neg\varphi$, причем одновременно в $T_1$ или в $T_2$ они лежать не могут, в силу их непротиворечивости.

А это доказательство получается неправильное? Просто я думал, что этого достаточно. Тогда попробую дальше поразбираться.

mihaild в сообщении #1191528 писал(а):

обозначим конъюнкции этих частей $A$ и $B$. Имеем $\vdash A \wedge B \rightarrow \bot$

Я правильно понял, что $A$ это все утверждения лежащие $T_1$, которые входят в конечный набор противоречивых утверждений $T_1 \cup T_2$, а $B$ соответственно лежащие в $T_2$? Просто мне тогда не понятно что это такое --

mihaild в сообщении #1191528 писал(а):

Имеем $\vdash A \wedge B \rightarrow \bot$

[mihaild]

pink Elephant в сообщении #1191769 писал(а):

А это доказательство получается неправильное?

Нет, т.к. может быть, что $\varphi$ не лежит в $T_1 \cup T_2$, а только выводится из него.
Например, возьмите $\varphi = \bot$.

pink Elephant в сообщении #1191769 писал(а):

что $A$ это все утверждения лежащие $T_1$, которые входят в конечный набор противоречивых утверждений $T_1 \cup T_2$, а $B$ соответственно лежащие в $T_2$?

Да (точнее, не сами утверждения, а их конъюнкция).

$A$ и $B$ некоторые формулы, $\bot$ тоже, $A \wedge B \rightarrow \bot$ - тоже. Запись $\vdash X$ означает "$X$ выводится в исчислении высказываний".

[pink Elephant]

mihaild в сообщении #1191771 писал(а):

Да (точнее, не сами утверждения, а их конъюнкция).

Не могу все равно понять что такое конъюнкция утверждений в теории. Туплю немного(

mihaild в сообщении #1191771 писал(а):

$\bot$ тоже

Я вот конкретно это не совсем понял, думал это обозначение противоречивости. Теперь вообще не понимаю что это означает.

[arseniiv]

Это формула-противоречие. Либо конкретная формула $\bot$, если она входит в язык логики (и ложная в любой интерпретации по определению), либо просто любое противоречие, скажем, $\psi\wedge\neg\psi$ для какой-нибудь формулы $\psi$.

[pink Elephant]

arseniiv в сообщении #1191774 писал(а):

Это формула-противоречие. Либо конкретная формула $\bot$, если она входит в язык логики (и ложная в любой интерпретации по определению), либо просто любое противоречие, скажем, $\psi\wedge\neg\psi$ для какой-нибудь формулы $\psi$.

Спасибо) Теперь разобрался в формулировке вопроса.

mihaild в сообщении #1191528 писал(а):

Что можно сказать про выводимость $B$ и $\neg B$ в $T_1$ и $T_2$?

Ну, $B$ выводится из $T_2$ так как лежит в ней. $\neg B$ не выводится из $T_2$, так как если $T_2$ противоречива, то в $B$ уже есть противоречие и $\neg B$ тождественно ложно. Если $T_2$ непротиворечива, то $\neg B$ не выводится из-за определения непротиворечивости. И, видимо, $\neg B$ должен выводиться из $T_1$, так как $A\wedge B\rightarrow \bot$, но я не понимаю почему.

[mihaild]

pink Elephant в сообщении #1191781 писал(а):

$\neg B$ не выводится из $T_2$, так как если $T_2$ противоречива, то в $B$ уже есть противоречие и $\neg B$ тождественно ложно

Если $T_2$ противоречива, то в ней выводится $\neg B$ (и вообще что угодно), но это неважно. Важно, что $T_2 \vdash B$.

pink Elephant в сообщении #1191781 писал(а):

И, видимо, $\neg B$ должен выводиться из $T_1$, так как $A\wedge B\rightarrow \bot$, но я не понимаю почему.

Попробуйте воспользоваться теоремой о дедукции и перенести $A$ влево от $\vdash$.

[pink Elephant]

mihaild в сообщении #1191881 писал(а):

Попробуйте воспользоваться теоремой о дедукции и перенести $A$ влево от $\vdash$.

Воспользуемся допустимым правилом ГИП и раскроем конъюнкцию в импликацию.
$\vdash(A\wedge B)\to \perp$
$\vdash A\to(B\to \perp)$
А тут теорема о дедукции
$A \vdash (B\to \perp)$
И теперь из этого мы можем утверждать, что из $A$ следует противоречивость $B$. А значит из $A\vdash \varphi$ и $B\vdah \neg\varphi$. Ничего не упустил?

[mihaild]

pink Elephant в сообщении #1191900 писал(а):

из $A$ следует противоречивость $B$

Немного неточно: $B$ - это формула, а не теория, формулы не бывают противоречивыми. Правильно "из $A$ выводится $\neg B$".

pink Elephant в сообщении #1191900 писал(а):

А значит из $A\vdash \varphi$ и $B\vdah \neg\varphi$.

А что такое $\varphi$? Мы начали с того, что $A \wedge B \rightarrow \bot$, $A$ - конъюнкция некоторых аксиом $T_1$, $B$ - конъюнкция некоторых аксиом $T_2$.
Теперь у нас есть $T_2 \vdash B$ и $A \vdash \neg B$. Но нам нужна была выводимость не из $A$, а из $T_1$...

[pink Elephant]

mihaild в сообщении #1191905 писал(а):

Но нам нужна была выводимость не из $A$, а из $T_1$

Ну, еще раз воспользоваться теоремой о дедукции. Даны гипотезы $T_2\backslash A$ и есть вывод $A \to \neg B$. Тогда переносим $A$ влево и получаем $T_2\backslash A, A \to \neg B$ или тоже самое, что $T_2 \to \neg B$.