\documentclass{article}

\usepackage[utf8]{inputenc}
\usepackage[TS1,T2A]{fontenc}
\usepackage[russian]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}

\hoffset=-3cm
\textwidth=18cm
\voffset=-3cm
\textheight=26cm

\date{2010-03-23}
\title{Лекции по матлогу}
\author{Зайцев Вадим}

\begin{document}
\maketitle

\subsubsection{теорема Гёделя о полноте}
	$\varphi$ - тождественно-истинна $\Leftrightarrow$ $\varphi$ - доказуема.
	\begin{proof} (от противного):\\
		Пусть $\varphi$ - тождественно-истинна и недоказума.\\
		$ \displaystyle \frac{\neg \varphi \vdash}{\vdash \varphi}$\\
		$\neg \varphi \vdash$ - доказумеа $ \Rightarrow \vdash \varphi$ - доказуема $ \Rightarrow \varphi$ - доказуема.\\
		$\neg \varphi \vdash$ - не доказумеа $ \Rightarrow \Gamma =\{ \neg \varphi \} \not\vdash  \Rightarrow $\\
		$ \Rightarrow \exists \mathfrak{A} : \exists \gamma : \mathfrak{A} \vDash \Gamma[\gamma]  \Rightarrow 
		\mathfrak{A} \vDash \neg \varphi [\gamma]  \Rightarrow \mathfrak{A} \not\vDash \varphi[\gamma]$. Противоречие. $\varphi$ - т.и.
	\end{proof}
	
\subsubsection{Теорема Мальцева о расширении}
	Пусть $\Gamma \subseteq S(\sigma), \quad \exists \mathfrak{B} : \mathfrak{B} \vDash \Gamma \quad ||\mathfrak{B}||\ge 0$.\\
	$\forall \lambda$ - кардинал $\exists \mathfrak{A} : ||A|| \ge \lambda$ и $\mathfrak{A} \vDash \Gamma$.\\
	Если для мно-ва предложение $\gamma$ существует бесконечная модель, то для неё существует модель сколь угодно большой мощности.
	\begin{proof}\hfill\\
		$C - const \quad c \cap \sigma = \varnothing \quad ||C||=\lambda$\\
		$\Gamma ' = \{\neg (c=d) \mid c,d \in C \}$\\
		$\Gamma'' = \Gamma \cup \Gamma'$\\
		Покажем $\Gamma''$ - совм. Для этого покажем, что $\Gamma''$ - локально совместна и воспользуемся теоремой Мальцева.\\
		$\Gamma_0'' \subseteq \Gamma'', \, \Gamma_0''$ - конечное.\\
		$\Gamma_0'' = \Gamma_0 \cup  \Gamma', \quad  \Gamma_0 \subseteq \Gamma, \,  \Gamma_0' \subseteq  \Gamma $\\
		$\mathfrak{B} \vDash  \Gamma_0, \quad  \sigma( \Gamma_0' ) = \{ c_1,...,c_k\}$\\
		$\mathfrak{B}$ - бесконечная, следовательно можно выделить конечное число чего-нибудь: $\exists b_1,...,b_k \in |\mathfrak{B}|: b_i \ne b_j$\\
		$\mathfrak{B} = \{  \mathfrak{B} \}^{\sigma'}, \quad \sigma' = \sigma \cup \{ c_1,...,c_k\}$\\
		$c_i^{\mathfrak{B}'} = b_i$\\
		\begin{tabular}{l}$\mathfrak{B}' \vDash  \Gamma_0'$ \\ $\mathfrak{B} \vDash  \Gamma_0  \Rightarrow \mathfrak{B}' \vDash  \Gamma_0$
		\end{tabular} $  \Rightarrow \mathfrak{B}' \vDash \Gamma_0''$\\
		$\Gamma_0''$ - совместа $ \Rightarrow \Gamma''$ - локально $ \Rightarrow \Gamma''$ - совместна $ \Rightarrow \exists \mathfrak{A}' : \mathfrak{A}' \vDash \Gamma''$.\\
		$\Gamma = \mathfrak{A}' \setminus \sigma  \quad \mathfrak{A} \vDash \Gamma \quad ||\mathfrak{A}|| \ge ||C||= \lambda$.
	\end{proof}
	
\subsubsection{Замечание}
	$\mathfrak{A, B} \in K(\sigma)$\\
	$\mathfrak{A} \equiv \mathfrak{B} \Leftrightarrow \mathfrak{B} \vDash  \operatorname{Th}(\mathfrak{A})$.\\

\subsubsection{Замечание}
	$\mathfrak{A, B} \in K(\sigma), \quad \mathfrak{A, B}$ - конечны $  \quad \Rightarrow \quad  (\mathfrak{A} \equiv \mathfrak{B} \Leftrightarrow \mathfrak{B} \equiv \mathfrak{A})$.

\subsubsection{Следствие}
	Если $\mathfrak{B}$ - бесконечная модель, $\alpha$ - бесконенчый кардинал, то $\exists \mathfrak{A} \equiv \mathfrak{B}$ и $||\mathfrak{A}|| \ge \alpha$.
	\begin{proof}
		$\Gamma =  \operatorname{Th}(\mathfrak{B})$.\\
		$\mathfrak{A}$ - бесконечна, $\mathfrak{B} \vDash  \operatorname{Th}(\mathfrak{B})$\\
		$\exists \mathfrak{A}: \mathfrak{A} \vDash \Gamma$ и $||\mathfrak{A}|| \ge \alpha$\\
		$\mathfrak{A} \vDash  \operatorname{Th}(\mathfrak{B})  \Rightarrow \mathfrak{A} \equiv \mathfrak{B}$.\
		С точки зрения тоерии моделей, невозможно различать бесконечные модели.
	\end{proof}
	
\subsubsection{Следствие (Теорема о нестандартной модели натуральных чисел)}
	Пусть $\mathfrak{N} = < N, \le, \cdot, +, 0, 1>$\\
	$\exists \mathfrak{M} : \mathfrak{M} \equiv \mathfrak{N} \quad \exists c \in |\mathfrak{M}| : \forall n \in \mathbb{N} \quad c \ge \underset{n}{\underbrace{1+1+...+1}}$
	\begin{proof}
		$\Gamma \leftrightharpoons  \operatorname{Th}(\mathfrak{N}) \quad \sigma(\Gamma) = \{ \le, \cdot, + , 0, 1 \} \quad \sigma' = \sigma(\Gamma) \cup \{ c \}$.\\
		$\varphi_n \leftrightharpoons ( c \ge \underset{n}{\underbrace{1+1+...+1}}) \quad \Gamma' = \{ \varphi_n \mid n \in \mathbb{N} \}$.\\
		$\Gamma'' = \Gamma \cup \Gamma'$\\
		$\Gamma_0'' \subseteq \Gamma''$ - конечно\\
		$\Gamma_0'' = \Gamma_0 \cup \Gamma_0'$\\
		$\Gamma_0, \Gamma_0'$ - конечн.\\
		$\Gamma_0'$ - конечно, то $m \leftrightharpoons  \operatorname{max} \{ n \mid \varphi_n \in \Gamma_0'\}$\\
		$\mathfrak{N}' = \mathfrak{M}^{\sigma'} \quad c^{\mathfrak{M}}  \leftrightharpoons  m$.\\
		Например, $\Gamma' = \{ \varphi_1, \varphi_2, ... \} \quad \Gamma_0' = \{ \varphi_2, \varphi_5, \varphi_100 \}$ - мы спокойно можем взять максимум.\\
		$\mathfrak{N}' \vDash \Gamma_0'$. Например, $\Gamma_0' = \{ \varphi_2, \varphi _3, \varphi_154 \}, \, m=154. \quad \varphi_2^{\mathfrak{N}'}=154 \ge 1+1, \quad \varphi_5^{\mathfrak{N}'}=154 \ge 1+1+1+1+1 $\\
		$\Gamma =  \operatorname{Th}(\mathfrak{N})  \Rightarrow \mathfrak{N} \vDash \Gamma$\\
		$\Gamma_0 \subseteq \Gamma  \Rightarrow \mathfrak{N} \vDash \Gamma_0$\\
		\begin{tabular}{r}$\mathfrak{N}' \vDash \Gamma_0'$ \\ $\mathfrak{N} \vDash \Gamma_0  \Rightarrow \mathfrak{N}' \vDash \Gamma_0'$ \end{tabular} $\} \Rightarrow \mathfrak{N}' \vDash \Gamma_0'' \quad \Gamma_0''$ - совместна $ \Rightarrow \Gamma''$ - локально совместна $ \Rightarrow \Gamma''$ - совместна.
		$\exists \mathfrak{M}' : \mathfrak{M}' \vDash \Gamma'' = \Gamma \cup \Gamma' \quad \mathfrak{M} \vDash \Gamma$\\
		$\mathfrak{M} = \mathfrak{M} \setminus \sigma \quad \mathfrak{M}\vDash \Gamma  \Rightarrow  \mathfrak{M} \vDash  \operatorname{Th}(\mathfrak{N})  \Rightarrow \mathfrak{M} \equiv \mathfrak{N}$
	\end{proof}

\section{Исчсления Гильбертовского типа}

\subsection{Аксиомы}
	1...10 - аналогично.\\
	\begin{enumerate}
		\item $\forall x \varphi(x) \rightarrow [\varphi]_t^x$
		\item $[\varphi]_t^x \rightarrow \exists x \varphi(x)$
		\item $ x = x$
		\item $x=y  \rightarrow ([\varphi]_x^z  \rightarrow [\varphi]_y^z)$
	\end{enumerate}
	
\subsection{Правила вывода}
	\begin{enumerate}
		\item $ \displaystyle \frac{\varphi, \varphi  \rightarrow \xi}{\xi}$
		\item $  \displaystyle \frac{\varphi  \rightarrow \xi}{\varphi \rightarrow \forall x \xi}$
		\item $ \displaystyle \frac{\xi  \rightarrow \varphi}{\exists x \varphi \rightarrow \xi},  \quad x \not\in  \operatorname{FV}(\varphi)$
	\end{enumerate}

\subsection{бла бла бла}

\subsubsection{Определение}
	Док-во ф-лы $\varphi\rhd\varphi$
	
\subsubsection{Определение}
	Вывод ф-лы $\varphi$ из мно-ва $\Gamma \quad \Gamma\rhd\varphi$
	
\subsubsection{Замечание}
	$\varphi$ - доказуема в $  \quad \Rightarrow  \quad \varphi = [\varphi]_{\varphi_1...\varphi_n}^{P_1...P_n}$ док-мы в ИПГТ.
	
\subsubsection{Теорема о дедукции}
	$\Gamma \cup \{ \varphi \} \rhd \varphi \Rightarrow \Gamma \rhd \varphi \rightarrow \xi$
	
\subsubsection{Следствие}
	$\varphi_1...\varphi_n \rhd \varphi  \quad \Rightarrow  \quad \rhd (\varphi_1 \rightarrow(\varphi_2 \rightarrow ... (\varphi_{n-1} \rightarrow \varphi_n)...)$
	
\subsubsection{Теорема}
	$\Gamma$ - конечно.
	\begin{enumerate}
		\item $\Gamma \rhd \varphi \Leftrightarrow \Gamma \vdash \varphi$ - доказуема
		\item $\rhd \varphi \Leftrightarrow \varphi$ - доказумеа.
	\end{enumerate}


\end{document}
