\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-04-27}
\title{Лекции по матлогу}
\author{Зайцев Вадим}

\begin{document}
\maketitle

\subsubsection{Определение}
	$ A \subseteq \mathbb{N}^k$\\
	$X_A^*(x_1,..., x_n) = \begin{cases}1, \quad <x_1...x_n> \in A\\ hz \quad \end{cases} $
	
\subsubsection{Теорема}
	Пусть $A \subseteq \mathbb{N}^k$\\
	$A$ - РПМ $\Leftrightarrow X_A^*$ - ЧРФ.
	\begin{proof}\hfil
		\begin{description}
			\item[$ \Rightarrow )$] $A$ - РПМ $ \Rightarrow \exists f$ - ЧРФ: $A = \delta f$\\
				$\lambda_A^*(x_1...x_n) = S(O(f(x_1...x_n)))$
			\item[$\Leftarrow)$] $X_A^*$ - ЧРФ $ \Rightarrow A=\delta X_A^* \Rightarrow A$ - РПМ.
		\end{description}
	\end{proof}
	
\subsubsection{Определение}
	$f:\mathbb{N}^k \rightarrow \mathbb{N}$\\
	$G_f \leftrightharpoons \{ <x_1...x_n> \mid f(x_1...x_n)=y \}$ - график ф-ии $f$.
	
\subsubsection{Теорема о графике}
	$f$ - ЧРФ $\Leftrightarrow$ $G_f$ - РПМ.
	\begin{proof}
		\hfil
		\begin{description}
			\item[$ \Rightarrow )$] $f(x_1...x_k)$ - ЧРФ\\
				%$X_{G_f}^* (x_1...x_k, z) =  \operatorname{\overline{sg}}(\mu y[ |f(\overline{x})-y|=0]-z)$
				$X_{G_f}^* (x_1...x_k, z) = \overline{ \operatorname{sg}}(|f(x_1...x_n) - z|)$ -- ЧРФ
			\item[$\Leftarrow)$] $G_f$ - РПМ $ \Rightarrow $ $B$ - РМ, $G_f = \{ <\overline{x}, y> \mid \exists z <\overline{x}, y, z> \in B \}$\\
				%$X_B$ - ОРФ. $f(\overline{x}) = l(\mu t[\overline{ \operatorname{sg}}( X_b(\overline{x}, l(t), r(t))= 0)])$
				$X_B$ - ОРФ. $f(\overline{x}) = l(\mu t\underset{(*)}{\underbrace{[\overline{ \operatorname{sg}}( X_b(\overline{x}, l(t), r(t)))= 0]}})$\\
				\begin{enumerate}
					\item $f(\overline{x}) = y$\\
						$<\overline{x}, y> \in G_f  \Rightarrow \exists z : <\overline{x}, y, z> \in B  \Rightarrow \exists t : t = c(y,z) \quad <\overline{x}, l(t), r(t)> \in B$.\\
						$ \Rightarrow \overline{sg}(X_B^*(\overline{x}, l(t), r(t)) = 0$\\
						$l(\mu t[ * ]) = l(t) = y = f(\overline{x})$
					\item $f(\overline{x})$- не определено\\
						$\forall y : <\overline{x}, y> \not\in G_f  \Rightarrow \forall y , \forall z : <\overline{x}, y, z> \not\in B  \Rightarrow $\\
						$ \Rightarrow \forall t : t=c(y,z) \quad <\overline{x}, l(t), r(t)> \not\in B$\\
						$ \Rightarrow l(\mu t[*])$ - не определена.
				\end{enumerate}
		\end{description}
	\end{proof}

\subsubsection{Теорема о составном определении}
	$A_1...A_n \subseteq \mathbb{N}^k, \quad A_i \cap A_j = \varnothing \quad g_1(x_1...x_k)...g_n(x_1...x_k)$ - ЧРФ.\\
	Тогда $f(x_1...x_k) = \begin{cases}  g_1(x_1...x_k), \, \overline{x} \in A \\ \vdots \\ g_n(x_1...x_k), \, \overline{x} \in A \\ \text{не определено в п с} \end{cases}$ - ЧРФ\\
	\begin{proof}
		$A_1...A_n$ - РПМ $ \Rightarrow $ $B_1...B_n$ - РМ\\
		$A_i = \{ <x_1...x_n> \mid \exists y <x_1...x_n> \in B_i \}$\\
		$X_{B_i}$ - ОРФ. Могут быть 2 случая:
		\begin{enumerate}
			\item $g_1...g_n$ - ОРФ\\
				$ \displaystyle h(\overline{x}) = \mu y[ (\prod_{i=1}^n \overline{sg}(X_{B_i} (\overline{x},y))) = 0 ]$\\
				$ f(\overline{x}) = g_1(\overline{x}) \cdot X_{B_1}(\overline{x}, h(\overline{x})) + ... + X_{B_n}(\overline{x}, h(\overline{x}))$\\
				\begin{enumerate}
					\item $\exists i : <x_1...x_k> \in A_i$\\
						$ \Rightarrow \exists y : <x_1...x_k, y> \in B_i$\\
						$ \forall y : <x_1...x_n, y> \not\in B_? (i \ne j)$\\
						$ \Rightarrow  y- \operatorname{min} : <x_1...x_k, y> \in B_i$...
					\item
				\end{enumerate}

		\end{enumerate}

	\end{proof}



\section{Формальная арифметика Пеано}

\subsubsection{Определение}
	$  \sum_0 = < <^2, +^2, *^2, s^1, 0 >$\\
	$ T(\sum_0)$ - мно-во термов\\
	$ F(\sum_0)$ - мно-во формул\\
	$ S(\sum_0)$ - мно-во предложений\\
	$v_i$ - переменные
	
\subsubsection{Определение (Гёделевская нумерация термов и формул в сигнатуре $\sum_0$)}
	\begin{enumerate}
		\item $\gamma(0) = c(0,1)$ \\
			$\gamma(v_i) = c(1,i)$
		\item $\gamma((t)) = c(2, \gamma(t))$
		\item $\gamma(t+q) = c(3, c(\gamma(t), \gamma(q)))$
		\item $\gamma(t*q) = c(4, c(\gamma(t), \gamma(q)))$
		
		\item $ \gamma(t=q) = c(5, c(\gamma(t), \gamma(q)))$
		\item $\gamma(t<q) = c(6, c(\gamma(t), \gamma(q)))$
		\item $\gamma(\varphi \and \xi) = c(7, c(\gamma(\varphi), \gamma(\xi)))$
		\item $\gamma(\varphi \vee \xi) = c(8, c(\gamma(\varphi), \gamma(\xi)))$
		
		\item $\gamma(\varphi \rightarrow \xi) = c(9, c(\gamma(\varphi), \gamma(\xi)))$
		\item $\gamma(\neg \varphi) = c(10, \gamma(\varphi))$
		\item $\gamma(\exists v_i \varphi) = c(11, c(i, \gamma(\varphi)))$
		\item $\gamma(\forall v_i \varphi) = c(12, c(i, \gamma(\varphi)))$
	\end{enumerate}

\subsubsection{Предлоежеие}
	$\gamma(T(\sum_0))$, $\gamma(F(\sum_0))$, $\gamma(S(\sum_0))$ - ПРМ.

\end{document}
