7-leccia.tex

\subsection{Лекция 7}

\begin{theorem} \  

    \begin{enumerate}
        \item $T$ -- модельно полна; 
        \item Для любой $\mathbb{A} \models T$, теория $T \cup D(\mathbb{A})$ полна; 
        \item (Тест Робинсона) Для любых $\mathbb{A}, \mathbb{B} \models T$ из $\mathbb{A} \subseteq \mathbb{B}$ следует, что любое $\Sigma_1$-предложение в сигнатуре $\sigma_A$, которое истинно в $\mathbb{B}$, будет истинно и в $\mathbb{A}$; 
        \item $\Sigma_1 = \Pi_1$ по модулю $T$, то есть любая $\Sigma_1$-формула $\varphi(\overline{x})$ равносильна подходящей $\Pi_1$-формуле $\psi(\overline{x})$ в $T$ (то есть $T \models \forall \overline{x}~(\varphi(\overline{x}) \leftrightarrow \psi (\overline{x}))$); 
        \item Любая формула $\varphi(\overline{x})$ равносильна подходящей $\Pi_1$-формуле в $T$.
    \end{enumerate}
\end{theorem}

\begin{remark}
    Пока мы ввели иерархию только для предложений. Она точно так же строится для формул со свободными переменными.
\end{remark}

\begin{proof}
    На практиках мы уже доказали $1 \Rightarrow 2$, $2 \Rightarrow 3$.

    % 3=>4
    Нетривиальным является следствие $3 \Rightarrow 4$. Пусть $\varphi(\overline{y})$ -- $\Sigma_1$-формула. Нам нужно найти $\Pi_1$-формулу $\psi(\overline{y})$ такую, что $T \models \forall \overline{y}~(\varphi(\overline{y}) \leftrightarrow \psi(\overline{y}))$. Скажем, $\overline{y} = (y_1, \ldots, y_k)$, обогатим сигнатуру константными символами $\overline{c} = (c_1, \ldots, c_k)$. Тогда достаточно доказать, что $T \models \varphi(\overline{c}) \leftrightarrow \psi(\overline{c})$. 

    Пусть $\Gamma = \{\gamma\in \Pi_1 \mid T \models \varphi(\overline{c}) \rightarrow \gamma\}.$
    Достаточно доказать, что $T \cup \Gamma \models \varphi(\overline{c})$. Действительно, если это так, то для конечного подмножества $\Gamma$ выполнено $T \cup \{\gamma_1, \ldots, \gamma_m\} \models \varphi$, тогда $\psi = \gamma_1 \wedge \ldots \wedge \gamma_k \in \Pi_1$ -- искомая формула.

    Рассмотрим произвольную модель $\mathbb{A}\models T\cup\Gamma$. Наша цель -- показать, что $\mathbb{A}\models\varphi$. Сначала докажем, что $T\cup\{\varphi\}\cup D(\mathbb{A})$ имеет модель. Предположим противное, тогда по теореме о компактности для некоторых $\{\delta_1, \ldots, \delta_m\}\subseteq D(\mathbb{A})$ у $T\cup \{\varphi\} \cup \{\delta_1, \ldots, \delta_m\}$ нет модели. Пусть $\delta = \delta_1\wedge\ldots\wedge\delta_m$. По определению диаграммы, $\mathbb{A}\models \exists \overline{x}~\delta(\overline{x})$. С другой стороны, из-за отсутствия модели, $T\cup\{\varphi\}\models \forall x \neg \delta(\overline{x})$, поэтому $T\models \varphi\rightarrow \forall \overline{x}~\neg \delta(\overline{x})$. По определению $\Gamma$, $\forall \overline{x}~\neg\delta(\overline{x})\in \Gamma$, значит эта формула верна в $\mathbb{A}$. Но и её отрицание верно в $\mathbb{A}$. Противоречие.

    Пусть $\mathbb{B}\models T\cup\{\varphi\}\cup D(\mathbb{A})$. Тогда $\mathbb{A}\subseteq\mathbb{B}$, $\varphi$ -- $\Sigma_1$-предложение. Тогда из пункта 3 получаем $\mathbb{A}\models \varphi$, что мы и пытались доказать.
    %Для любой $\mathbb{A} \models T \cup \Gamma$, $\mathbb{A} \models \varphi$, имеет ли $T \cup \{\varphi\} \cup D(\mathbb{A})$ модель? Предоложим противное, так конечное $T \cup \{\varphi\} \cup D(\mathbb{A})$ не имеет модели. $\mathbb{A} \models \exists \overline{x} \delta(\overline{x})$ ($\delta = \delta_1 \wedge \ldots wedge \delta_m$, $\delta_i = \delta_i(d_1, \ldots, d_m)$, $\delta_i \in D(\mathbb{A})$). $T \cup \{\varphi\} \models \forall \overline{x} \neg \delta(\overline{x})$, а значит, 

    %\[ 
        %T \models (\varphi \rightarrow \forall \overline{x} \neg \delta(\overline{x})) \text{\rotatebox[origin=c]{180}{$\models$}} \mathbb{A},
    %\]

    %противоречие.
    
    % 4=>5
    $4\Rightarrow 5$. Рассмотрим произвольную $\varphi$. Она лежит на одном из уровней иерархии формул. Расссмотрим только случаи $\varphi\in \Pi_2$ и $\varphi\in\Sigma_2$. В остальных случаях рассуждения аналогичны.

    Для формулы $\varphi(\overline{z})\in\Pi_2$ существует запись в виде $\forall \overline{x}~\exists \overline{y}~\psi(\overline{x}, \overline{y}, \overline{z})$. Формула $\exists \overline{y}~\psi(\overline{x}, \overline{y}, \overline{z})$ лежит в $\Sigma_1$, поэтому по пункту 4 существует $\psi'(\overline{x}, \overline{z})\in\Pi_1$, эквивалентная ей по модулю $T$. Значит $\varphi \equiv_T \forall \overline{x}~\psi' \in \Pi_1$.

    Для формулы $\varphi\in\Sigma_2$ выполнено $\neg\varphi\in\Pi_2$. Поэтому $\exists\psi\in\Pi_1$ такая, что $\neg\varphi \equiv_T \psi$. Тогда $\varphi\equiv_T\neg\psi\in\Sigma_1$. А $\neg\psi$ в свою очередь эквивалентна формуле $\Pi_1$ из пункта 4.

    % 5=>1
    $5 \Rightarrow 1$. Нам нужно, чтобы выполнялось $\mathbb{A} \subseteq \mathbb{B} \Rightarrow \mathbb{A} \preceq \mathbb{B}$, где $\mathbb{A}$ и $\mathbb{B}$ -- модели $T$. Рассмотрим произвольную формулу $\varphi$. Из пункта 5 следует существование универсальной формулы $\psi$ с условием $\varphi(\overline{x}) \equiv_T \psi(\overline{x})$.
    %, $\overline{a} \in \mathbb{A}$, $\varphi^{\mathbb{A}}(\overline{a}) = \varphi(\overline{a})$. % Это было пояснение чего мы хотим 
    %Значит, 

    %\[ 
        %\psi(\overline{x}) = \forall \overline{y} \theta(\overline{x}, \overline{y})
    %\]

    %из утверждения в этом пункте.
    Для $\overline{a}\in\mathbb{A}$, если $\mathbb{B} \models \varphi(\overline{a})$, то и $\mathbb{B} \models  \psi(\overline{a})$, из универсальности $\mathbb{A} \models \psi(\overline{a})$, из равносильности $\mathbb{A}\models\varphi(\overline{a})$. Мы доказали $\mathbb{B}\models\varphi\Rightarrow\mathbb{A}\models\varphi$. Для доказательства в обратную сторону можно рассмотреть формулу $\neg\varphi$.
\end{proof} 

\begin{prop}[Свойства модельно полных теорий] \ 

    \begin{enumerate}
        \item Любая модельно полная теория $\Pi_2$-аксиоматизируемая;
        \item (Тест Линдстрёма) Если теория $\Pi_2$-аксиоматизируема, не имеет конечных моделей и категорична в некоторой мощности $\lambda \geq |\text{For}_\sigma|$, то она модельно полна; 
        \item Если модельно полная теория $T$ имеет модель, котоаря вкладывается в любую модель $T$, то $T$ -- полная; 
        \item Если для любых двух моделей модельно полной теории $T$ существует третья модель, в которую они обе вкладываются, то $T$ полна.  
    \end{enumerate}
\end{prop}

\begin{proof} \

    \begin{enumerate}
        % доказательство пункта 1
        \item $T$ -- модель полная. Достаточно доказать, что $\text{Mod}(T)$ замкнут относительно объединения цепей (по теореме Чэна-Лося-Сушко)
         
        \[ 
            \mathbb{A}_0 \subseteq \mathbb{A}_1 \subseteq \ldots \quad \mathbb{A} = \bigcup_n \mathbb{A}_n,
        \]

        где $\mathbb{A}_i \models T_i$.
        % Правда ли, что $\mathbb{A} \models T$?
        Из модельной полноты имеем $\mathbb{A}_0 \preceq \mathbb{A}_1 \preceq \ldots$, отсюда нетрудно показать, что $\mathbb{A}_n \preceq \mathbb{A}$, тогда $T \text{\rotatebox[origin=c]{180}{$\models$}} \mathbb{A}_n \equiv \mathbb{A}$. 
        
        % доказательство пункта 2
        \item Остаётся на совесть юных читателей! (доказательство не было закончено)
        %TODO: написать набросок доказательства с конца седьмой - начала восьмой лекции

        % доказательство пункта 3
        \item $\mathbb{A}$ -- структура, изоморфная подструктуре любой модели $\mathbb{B} \models T$, тогда из модельной полноты $\forall \mathbb{B}~(\mathbb{A} \preceq \mathbb{B})$. Для любой $\varphi$ выполнено либо $\mathbb{A} \models \varphi$, либо $\mathbb{A} \models \neg \varphi$. Тогда одна из этих формул верна во всех моделях $T$, откуда и получим, что из $T$ следует либо эта формула, либо её отрицание. 

        % доказательство пункта 4
        \item Рассмотрим $\mathbb{A}, \mathbb{B}$ -- модели $T$. По предположению, существует третья модель $\mathbb{C}$ с двумя подструктурами $\mathbb{A}', \mathbb{B}'$, причём выполнено $\mathbb{A}\simeq\mathbb{A}'\subseteq\mathbb{C}$ и аналогичное для $\mathbb{B}$. $T$ модельно полна, поэтому $\text{Th}(\mathbb{A}')=\text{Th}{\mathbb(C)}$. Значит $\text{Th}(\mathbb{A})=\text{Th}(\mathbb{C})=\text{Th}(\mathbb{B})$. Значит $T$ полна.
        % Я не понимаю, зачем нужно использовать \text{Th}, а не сделать declaremathoperator, но придерживаюсь традиций этого документа конспекта.
    \end{enumerate}
\end{proof}