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

\begin{document}
\maketitle

\subsection{Универсальные функции}
$K=\{g \mid g: N^n \rightarrow N\}$\\
Ф-ия $f : N^{n+1} \rightarrow N$ является универсальной для класса $K$, если:
\begin{enumerate}
	\item $\forall m \in \mathbb{N} \quad f(m,x_1,...,x_n) \in K$
	\item $\forall g(x_1,...,x_n) \in K \quad  \exists m \in \mathbb{N} : f(m,x_1,...,x_n) = g(x_1,...,x_n)$
\end{enumerate}
$ K = \{ f(m,x_1,...,x_n) \mid m \in \mathbb{N} \}$

\subsubsection{Замечание}
	Класс $K$ имеет универсальную ф-ию $ \Leftrightarrow$ он конечен или счётен.
	
\subsubsection{Определение}
	Класс всех частичных ф-ий не имеет УФ.
	
\subsubsection{Следствие}
	ПРФ, ОРФ, ЧРФ имеют УФ.

\subsubsection{Предложение}
	$h : N \rightarrow N$ взаимно-однозначна. $f(x_0, \overline{x})$ - УФ для $K^n$. $f(h(x_0), \overline{x})$ - УФ для $K^n$.
	\begin{enumerate}
		\item $\forall m \in \mathbb{N} \quad \overline{x}) = f(m', \overline{x}) = k^n$
		\item $\forall g(\overline{x}) \in K^n \quad \exists m' : f(m', \overline{x}) = g(\overline{x}) \quad m=h^{-1} (m')$\\
			$f(m', \overline{x}) = f(h(m), \overline{x}) = g(\overline{x})$
	\end{enumerate}
	
\subsubsection{Следствие}
	Если $K^n$ имеет УФ, то $K^n$ имеет конт. (континуум?) УФ.
	
\subsubsection{Следствие}
	ПРФ$^n$,ОРФ$^n$,ЧРФ$^n$ имеют конт. УФ.
	
\subsubsection{Теорема}
	\begin{enumerate}
		\item ПРФ$^n$ не имеет У-ПРФ$^{n+1}$.
		\item ОРФ$^n$ не имеет У-ОРФ$^{n+1}$.
		\item ОРФ$^n$ не имеет У-ЧРФ$^{n+1}$.
	\end{enumerate}
	\begin{proof}  От противного:
		\begin{enumerate}
		\item
			Предположим, что $f(x_0, \overline{x})$ - ПРФ$^{n+1}$ и УФ для ПРФ$^{n}$\\
			$f(x_1,...,x_n) = f(x_1, x_1,...x_n) + 1 \in$ ПРФ $^{n}$\\
			$\exists m \in \mathbb{N} : f(m, x_1,...,x_n) = g(x_1,...,x_n)$\\
			$f(m,m,...,m) = f(m,...,m) = f(m,m,...,m) + 1$. противоречие.
		\item аналогично, только заменить ПРФ на ОРФ.
		\item
			$f(x_0, \overline{x})$ - ЧРФ$^{n+1}$, УФ для ПРФ$^{n}$\\
			Тогда $\forall k_0,k_1,...,k_m \in \mathbb{N} \quad f(k_0,k_1,...,k_m) \in $ OРФ$^{n}$\\
			$f(k_0, k_1,..., k_n)$ - определена. $  \Rightarrow f$ - ОРФ. Противоречие.
		\end{enumerate}
	\end{proof}

\subsubsection{Теорема}
	ЧРФ$^{n}$ имеет У-ЧРФ$^{n+1}$.\\
	\begin{proof}
		$f(x_0, x_1,...,x_n) = l(\mu y [ |T^n (x_0,x_1,...,x_n, l(y, r(y)-1| = 0 ] )$
		\begin{enumerate}
			\item $m \in \mathbb{N} : f(m, x_1,...,x_n) \in $ ЧРФ$^{n}$.
			\item $g(x_1,...x_n) \in$ ЧРФ$^{n}  \Rightarrow g(x_1,...,x_n = ??? \Rightarrow $ П - выч. $g(x)$.\\$a=\gamma(\text{П})$.
			\item $g(x_1,...,x_n)$ - не определена $ \Rightarrow \forall z,f \in \mathbb{N} \quad T^n(a,x_1,...,x_n,z,f)=0$.\\
				$ \displaystyle T^n(a,x_1,...,x_n,z,f) =
					\begin{cases} 1, \quad a=\gamma(\text{П}) \quad bq_11^{x_1+1}0...1^{x_n+1}  \overset{\text{П}}\Rightarrow ... \le t \text{ шагов} \\ 0 \end{cases}$
			\item $g(x_1,...,x_n) = z$\\
				$\exists t: 0q_11^{x_1+1}0...1^{x_n+1}0  \overset{\text{П}}{\Rightarrow} 0q_01^{z+1}0$\\
				$T^n(a, x_1,...x_n, z, t) = 1$\\
				$\forall z' ,t' : T^n(a, x_1,...x_n, z, t) = 1   \Rightarrow z' = z,\, t' \ge t$\\
				$y \leftrightharpoons c(z,t) \, y' \leftrightharpoons c(z', t') \quad y \le y'$\\
				$y =  \operatorname{min} \{ y'\mid T^n(a, x_1,...x_n, l(y'), r(y')) = 1 \} \quad f(a, x_1,...x_n) = z$.
		\end{enumerate}
	\end{proof}

\subsubsection{Определение}
	$ \varphi^2 (x_0, x_1) \leftrightharpoons l(\mu y [T^1 (x_0, x_1, l(y), r(y) - 1) = 0])$
	
\subsubsection{Следствие}
	$\varphi^2$ - УФ для ЧРФ$^2$.
	
\subsubsection{Определение}
	$\varphi^{n+1} (x_0, x_1, ...x_n) \leftrightharpoons \varphi^2(x_0, c^n(x_1,...x_n))$\\
	$c(x,y) = z \quad l(z)=x, \, r(z) = y$\\
	$c^n(x_1,...,x_n) = z \quad c_\xi^n (z) = x_i ...$\\

\subsubsection{хрень}
	\begin{enumerate}
		\item $\forall m \in \mathbb{N} \quad \varphi^{n+1}(m, x_1,...,x_n) = \varphi^2 (m,c^n(x_1,...,x_n))$\\
			$\varphi^{n+1}(m,x_1,...,x_n) \in$ ЧРФ$^{n}$
		\item $g(x_1,...,x_n) \in$  ЧРФ$^{n}$\\
			$ h(c^n(x_1,...,x_n))$
	\end{enumerate}

	


\end{document}
