% ���������� �������� 20.04.2000
\chapter{$m$-���������� � �������� ������������ ��������}\label{chapt06}

\section{$m$\� ����������}\label{m-reducibility}%
        \index{$m$\� ����������}

�� ��� ����������� � ����� ��ɣ���: ����� ��������
�������������� ���������� ���������~$X$ (��������, ��������� ����
������� ���� ���\� �� ������̣���� �������), �� ����������, ��� ����
�� ��� ���� ���������, �� � ����� ������������ ���������~$K$
���� ���������. ��� ����� �� ������� ���������� �������~$f$ ���,
����� �������������� ������ �����~$n$ ���������~$K$ ������������
��������������� �����~$f(n)$ ���������~$X$.

������ �� ������ ����� �������� ����� ��������.

�������, ��� ���������~$A$ ����������� ����� $m$\� \emph{��������}%
\index{$m$\� ����������} �
������� ���������~$B$ ����������� �����, ���� ���������� �����
������̣���� ����������
�������~$f\colon \bbN\hm\to\bbN$ � �����
���������:
        $$
x \in A \Leftrightarrow f(x) \in B
        $$
��� ����~$x\in \bbN$.
����� ������� ���������� \emph{$m$\� ��������~$A$ �~$B$}.
      \index{$m$\� �������� �������}\index{�������!$m$\� ��������}%
�����������:~$A\hm\lem B$.%
     \index{$\lem$}%

\begin{theorem}
        \label{m-reducibility-lemma}%
(\textsf{�})~����~$A \hm\lem B$ � $B$~���������, �� $A$~���������.
        %
(\textsf{�})~����~$A \hm\lem B$ � $B$~�����������, �� $A$~�����������.
        %
(\textsf{�})~$A\hm\lem A$; ����~$A\hm\lem B$ �~$B\hm\lem C$, ��~$A\hm\lem C$.
        %
(\textsf{�})~����~$A\hm\lem B$, ��~$\bbN\setminus A
                 \hm\lem \bbN\setminus B$.
        %
\end{theorem}

\begin{proof}
        %
��� ��� �������� ����� ��������. �����~$A\hm\lem B$ � �� ����� �����������
�������� ���~$B$. ����� ������, ����������� �� ������~$x$
���������~$A$, �� ���������~$f(x)$ � ������, ����������� ��~$f(x)$
���������~$B$. ������� �������,~$a(x)\hm=b(f(x))$,
���� $a$\� ������������������
�������\index{������������������ �������}\index{�������!������������������}
���������~$A$, � $b$\� ������������������ �������
���������~$B$; ������� ���� $b$~���������, �� � $a$~��������� ��� ����������
���������� �������.

����� �� ��������� ����� �������� ��� \��
����������������������\index{���������������������� �������}%
\index{�������!����������������������}\��\ �������, ������� ��
��������������~$B$ ������� ��������������~$A$. ����� ������� � �����:
���������~$A$ �������� ����������\index{��������} �������������
���������~$B$ ���
���������� �����������~$f$, � ������ �����������.

������������� �������, ��������, $m$\� ������~$A$ �~$A$. ����
�������~$f$ ������~$A$ �~$B$, � �������~$g$ ������~$B$ �~$C$,
��
        $$
  x \in A \Leftrightarrow f(x) \in B \Leftrightarrow g(f(x))\in C,
        $$
��� ��� ���������� �������~$g$ �~$f$ ������~$A$ �~$C$.

�������, �������, ��������~$A$ �~$B$, ����� �������
�~$\bbN\setminus A$ �~$\bbN\setminus B$.
        %
\end{proof}

�����~\��$m$\��\ � �������� ����������� ���������� ��
������� \�� many\� one\� reducibility\��; �������, ���
��������~M.\,������\glossary{������@\������}
� ��ϣ� �������� �� ������ ���������
����������, ������ ����� ����� �������� \�� mapping
reducibility\��\ (���������� � ������� �����������),
�������� �����~$m$ � �����������.

�������, ��� ��� ����������� �� ����������� ������������
�������� � ����������, ���� ��� �������� ������ � ����� ��
��������: ����� �� �����������~$A\hm\lem \bbN\setminus A$,
���� ������~$A\hm\lem A$.

\begin{problem}
        %
��������, ���~$A\hm{\not\lem} \bbN\setminus A$ ��� �������������
������������� ���������~$A$.
        %
\end{problem}

�������, ��� ���������~$\varnothing$ �~$\bbN$ ��������
������� �������� ��� $m$\� ����������.
��������, ����� ���������� ���������~$A$
�������� � ������ ���������~$B$, ���� ������ $B$~�� ��������
������ � �� ��������� �~$\bbN$. � ����� ����, ����~$p\hm\in
B$, $q\hm\notin B$ � $A$~���������, �� �������� ������� �����
��������� ���:
        $$
f(x) = \mathbf{if}\ x \in A\ \mathbf{then}\ p\ \mathbf{else}\ q\ \mathbf{fi}.
        $$
���� �� $B$~����� ��� ��������� �~$\bbN$, �� ������ ������
��������� (��������������~$\bbN$) �������� �~$B$.

\begin{problem}
        %
���������� �� ��������� ����������� �����, � �������� $m$\� ��������
����� ��������� ����������� �����?
        %
\end{problem}

\section{$m$\� ������ ���������}\label{m-complete}

\begin{theorem}
        \label{m-complete-existence}%
����� ������������ �������� ���������� ���������� � �����
������ $m$\� ����������, �� ���� ���������, � ������� $m$\� ��������
����� ������������ ���������.
        %
\end{theorem}

\begin{proof}
        %
������� �������� ������������� ��������� (��������� ���� ������� ��
��� � �� �������). ����� $U\hm\subset
\bbN\hm\times\bbN$\� ������������ ��������� ���
����������� �����, ������������� ��� ������ ������������
�������� ����������� �����. ���������� ���������~$V$ �������
���� ���, �������� �~$U$ (��� �����\� �� ���������� ���������
���~$\langle x,y\rangle \hm\leftrightarrow [x,y]\hm\in \bbN$).
������� �������,
        $$
V = \{ [x,y] \mid \langle x,y\rangle \in U\}.
        $$
����� $T$\� ������������ ������������ ���������. �����~$T\hm=U_n$
��� ���������~$n$ � ������
        $$
x\in T \Leftrightarrow x \in U_n \Leftrightarrow \langle n,x\rangle \in U
                                 \Leftrightarrow [n,x] \in V.
        $$
����� �������, �������~$x\hm\mapsto [n,x]$ ������~$T$ �~$V$.
        %
\end{proof}

���������� ������������ $m$\� ���������� ������������ ���������
�������� $m$\� \emph{�������} (������, $m$\� \emph{�������
� ������ ������������ ��������}\index{$m$\� ������
���������}\index{���������!$m$\� ������}).


�������, ��� ����~$K\lem A$ ��� ������������ ��������~$K$ �~$A$
� ��� ���� $K$~�������� $m$\� ������, �� � $A$~�������� $m$\� ������
(� ���� ��������������).

���� ������������� ��������� �������� �������, �� ��� ���������
����� $m$\� �����:

\begin{theorem}
        \label{diagonal-m-complete}%
����� $U\hm\subset\bbN\hm\times\bbN$\� ������� �������������
���������\index{������� ������������� ���������} ��� ������
������������ ��������.
����� ���
\�� ������������ �������\index{������������
�������}\��~$D \hm= \{ x \mid \langle x, x\rangle \hm\in U\}$
�������� $m$\� ������.
        %
\end{theorem}

(� ���������, ��������� ���� �������������� �������� ��������
$m$\� ������.)

\begin{proof}
        %
��������, $D$~�����������. ����� $K$\� ������������
������������ ���������. ���������� ������������ ���������
���~$V \hm= K \hm\times \bbN$. ��� �������~$V_n$ ����� ���� �����
(���~$n\hm\notin K$), ���� ��������� �� ����~$\bbN$ (���~$n\hm\in
K$).

��������� ���������~$U$ �������� �������, ���������� �����
������̣���� �������~$s$, ��� �������~$V_n\hm=U_{s(n)}$. �������
�������, $U_{s(n)}$~��������� �~$\bbN$ ���~$n\hm\in K$ �
����� ���~$n\hm\notin K$. �������������,~$s(n)\hm\in U_{s(n)}$ (�
������~$s(n)\hm\in D$) ���~$n\hm\in K$ �~$s(n)\hm\notin U_{s(n)}$ (�
������~$s(n)\hm\notin D$) ���~$n\hm\notin K$. ����� �������,
$s$~������~$K$ �~$D$.
        %
\end{proof}

\begin{problem}
        %
��������, ��� ��������� ���� ��������, ����������������� ��
�����~$0$, �������� $m$\� ������. ��������, ��� ��������� ���� ��������,
����������������� ���� �� �� ����� �����, �������� $m$\� ������.
        %
\end{problem}

\begin{problem}
        %
����� $M$\� $m$\� ������ ������������ ���������. ��������,
��� ���������� ��������, ������� �� ������ ����� �����
������̣���� �������~$h$ ��������� ����� �����~$n$,
���~$(n\hm\in M)\hm\Leftrightarrow (h(n)\hm\in M)$.
(��������: ��� ����������� ���������� ���������� �������
� ����������� ����� ��� ���������� ��������� ���������������.)
        %
\end{problem}

\section[$m$\� ������� � ����������� ����������������]%
        {$m$\� ������� � �����������\\ ����������������}%
        \label{effective-non-enumerability}

������ ���������� ���������, ��� �������,
\�� ���\-��\-���\-��\-��\-��\-��\-����\��\
��������� �����������. � �������� ������� ����ͣ� �����������
������������ ���������. ��� ����� ����������� ���������? ���
���������, ������� �������� �� �����~$n$ ��������� ��� ������
������������~$n$. ������ ����� ������� ���: ��������� ����������
\�� ���������� �����������\��, ���� ���������� ��������, �������
�� ������~$n$ ���������~$n$~��������� ��������� ����� ���������.

\begin{problem}
        %
��������, ��� ������������ ���������~$A$ �������� ����������
����������� ����� � ������ �����, ����� ��� ��������
����������� ������������ ��������� (\�� �� �������� ��������\index{��������
���������}\index{���������!��������}, ��.~c.~\pageref{immune}).
        %
\end{problem}

������ ��� ����� ������������ ����������� ������� �������
����������������. ��� ������, ��� ���������~$A$ �������������?
��� �������� (������), ��� $A$~���������� �� ������
������������� ���������. ����������� �������� ���������~$A$
���������� ��������������, ���� �� ������ �������������
��������� ����� ������� �����, ��� ��� ���������� ��~$A$.

����� ���������, ����������� ��������� ������� �������������
������������ ���������~$W$ (� ��� ����� ��������� ������������
��������: �����~$n$ �� ������� ������� ���������~$W_{n}$). �����
��������, ��� ���������~$A$ �������� \emph{����������
��������������}\index{���������� �������������� ���������}%
\index{���������!���������� ��������������}, ���� ����������
����� ����� ������̣����
���������� �������~$f$, ���~$f(z) \hm\in A \hm\bigtriangleup W_z$ ���
����~$z$. (����� $\bigtriangleup$~�������� ��������������
��������; ������� �������, $f(z)$~�������� ������, ���
$A$~���������� ��~$W_z$.)

�������, ��� ��� �������� �� ������� �� ������ ��������
�������������� ���������, ��� ��� �� ������� ������������ ������
������ ��������� ����� ���������� ���������� � �������
������������ �������.

�������� ����������� ����������������
���������
������� �������������� � �������� $m$\� ����������. ���Σ�
� ������ �������� ����������.

\begin{theorem}
        \label{effective-no-enumerability-m-reducibility}%
����~$A\lem B$ � $A$~���������� �������������, �� �
$B$~���������� �������������.
        %
\end{theorem}

\begin{proof}
        %
��� ������� �������� \�� ����������� ���������\��\
�������~\ref{m-reducibility-lemma}, �����~(�). �� �� �����
����� ������� � � ţ ��������������.
����� �� ����� ����� �����, � ������� $B$~���������� �� ����������
������������� ���������~$X$. ���������� �������~$f$, ������� $m$\�
������~$A$ �~$B$. ��������~$f^{-1}(X)$ ������������� ���������~$X$ ���
���������� ����������� ����� ����������, ������� ����� �����
�����~$m$, � ������� �� ���������� ��~$A$. ����� $B$~���������� ��~$X$
� �����~$f(m)$.

����� ������� ��� ����������� ������, ��� ����� ���� ��������,
��� ����� ������������� ���������~$f^{-1}(X)$ ����� ����
���������� ������� �� ������ ������������� ���������~$X$. ���
����� �� ������ ��������������� ���, ��� ��������� ��������
�������\� ����� ��� �� ��, ��� � ��� ���������� ������
���������� ���� ���������� �������, �������� ������ ��������
(�������~\ref{number-of-composition}). �����ģ� ��� ����������� ��������.

���������� ������������ ���������
        $$
V = \{ \langle x,y\rangle \mid \langle x, f(y)\rangle \in W\}
        $$
(��� �����������, ��������� �������� ���������� �������������
���������~$W$ ��� ���������� �����������~$\langle x,y\rangle
\hm\mapsto \langle x, f(y)\rangle$). ����� ������, ���~$V_n \hm=
f^{-1}(W_n)$. ��� ��� ���������~$W$ �������� �������
������������� ����������, �� ���������� ���������� �����
������̣���� �������~$s$, ��� ������� $W_{s(n)}\hm=V_n\hm=f^{-1}(W_n)$
��� ����~$n$. ������� �������, �������~$s$ �� $W$\� ������ ������
������������� ��������� ���� $W$\� ����� ��� ��������� ���
�����������~$f$, ��� � �����������.
        %
\end{proof}

\begin{theorem}
        \label{coenumerable-effective-nonenumerable}%
���������� ������������ ��������� � ���������� ���������������
������������.
        %
\end{theorem}

\begin{proof}
        %
����� ���������� ������������ ���������~$D\hm=\{n\mid \langle n,n\rangle
\hm\in W\}$. ��� ���������� ����� ���������� ��������������. �
����� ����, ���������~$W_n$ �~$D$ ��������� ���� ����� �
�����~$n$, ������� $W_n$~���������� �� ���������� �~$D$ � ���� �����.
����� �������, ���������� �~$D$ ���������� �������������, ���ޣ�
� �������� �������~$f$ �� ����������� �����������
���������������� ����� ����� ������������� �������.
        %
\end{proof}

�� ���� ���������� ������ �������� ������� ����� �����������:

\begin{theorem}
        \label{m-complete-effective-non-coenumerable-1}%
������ $m$\� ������ ������������ ��������� ����� ����������
�������������� ����������.
        %
\end{theorem}

�� ����� ���� ����� � ��������. ����� ��������� � ����, �������
����� ����:

\begin{theorem}
       \label{m-complete-effective-non-coenumerable-2}%
����� $K$\� ������������ ���������, � $A$~����������
�������������. �����~$\bbN\setminus K \hm\lem A$ (���, ���
������������,~$K \hm\lem \bbN\setminus A$).
        %
\end{theorem}

\begin{proof}
        %
�� ����� ���� ��� ����� ������ ���������� ��������~$A$ ���� ��
���� ������������ ��������\� �� ������� � �� �����
������������ ����. ��������~$A$ �� ������� ��������� ��������
������� ������� �~$A$; �������� �� ����� ������������ ����
�������� ������� ������� ���~$A$. ������ ��� ��� ���� ������������
��� ��������. ����� ���������, ����������
���������~$V\hm=K\hm\times \bbN$. ��� �������~$V_n$ ���� �����
(���~$n\hm\notin K$), ���� ��������� �� ���� ����������� �����
(���~$n\hm\in K$). ��������� ���, ��� ���������~$W$ �������� �������, ��
������� ����� ������̣���� �������~$s$, ���
�������~$W_{s(n)}\hm=\varnothing$ ���~$n\hm\notin K$ �~$W_{s(n)}\hm=\bbN$
���~$n\hm\in K$. ����� $f$\� �������, �������������� �����������
���������������� ���������~$A$. �����~$f(s(n))\hm\in A$
���~$n\hm\notin K$ �~$f(s(n))\hm\notin A$ ���~$n\hm\in K$. ������� �������,
���������� �������~$f$ �~$s$ ������~$\bbN\setminus K$ �
���������~$A$, ��� � �����������.
        %
\end{proof}

������ �������� �������� ����� �����������:

\begin{theorem}
        \label{m-complete-effective-non-coenumerable-3}%
������������ ��������� �������� $m$\� ������ ����� � ������
�����, ����� ��� ���������� ���������� �������������.
        %
\end{theorem}

\begin{theorem}
        \label{m-complete-effective-non-coenumerable-4}%
��������� ���������� ������������� ����� � ������ �����, ����� �
���� $m$\� �������� ���������� ���������� (�������: ������)
$m$\� ������� ���������.
        %
\end{theorem}

�������, ��� �� ������ �������������� ��������� ����������
�������������. ��� �����, ��������, �� ������ �����:

\begin{theorem}
        \label{m-complete-effective-non-coenumerable-5}%
����� ���������� �������������� ��������� �������� �����������
������������ ������������ (\�� �� �������� ��������\index{��������
���������}\index{���������!��������}).
        %
\end{theorem}

\begin{proof}
        %
� ����� ����, ����� ���������~$A$ ���������� �������������.
����� ������� ��� �� ������� ���������\� �� ���� ���ģ�
� Σ� �������. ����� ����� ������� ��� �� ���������������
���������, ������� ������� �� ����� ��������\� � ���ģ�
������ �������. �������� ���, �� ����� ��������������
����� ����� ������ ����� ��������� ���������.

� ���� ����������� �� ������������ ����� ����: ��
��������� ���������, ��������� ������� ��� ���������, �����
�������� ��� ����� (������, ���� �� �������) � ������� ���������
������������ ��������. ������ ��� ���? ����� �����������
��������� ���������� ��������� �������� ��������. �����
���������� $n$\� �� �������� ��������� � ���� ���������
�����~$D_n$. ����� $D_n$~����� $n$\� �� �������� �������������
(� ���� �����������) ���������
        $$
D=\{ \langle n, x\rangle \mid x \in D_n\}.
        $$
�������� ��������������� ������������
������� ��������� ������������ ��������.
        %
\end{proof}

������� ���������, �������, ��� �� �����, ����������
(�������~\ref{simple-set}), �������� ��������� ������������ ��������, ��
���������� $m$\� �������\index{$m$\� ������ ���������}%
\index{���������!$m$\� ������}. ������ ��� � �������� ������� ��������
���������\index{������� ���������}\index{���������!�������}: ����
����� ������ ������������� �������������
���������, ������� �� ���� �� $m$\� ������.

\section{���������� $m$\� ������ ��������}\label{m-complete-isomorphism}

� ���� ������� �� �������,
��� ��� $m$\� ������ ��������� \�� �������� ���������\��\
� ���������� ���� �� ����� ������ ���������� �������������.
        \index{����������!$m$\� ������ ��������}%

\begin{theorem}
        \label{m-complete-isomorphism-theorem}%
����� $A$ �~$B$\� $m$\� ������\index{$m$\� ������ ���������} ������������
���������. �����
���������� ���������� ������������\index{���������� ������������}
(���������� �������
����������� ������������)~$f\colon \bbN\hm\to\bbN$, ���
������� $A$~��������� �~$B$, �� ����~$x\hm\in A \hm\Leftrightarrow
f(x)\hm\in B$ ��� ����~$x$.
        %
\end{theorem}

\begin{proof}
        %
�� ����� ������������ ��� �� ��ɣ�, ��� � � �����ģ���� ����
�������������� ������� �������� �� ����������� �������
��������� (��.~�.~\pageref{rogers-theorem}).
������, �� ��� ������ ������� ����� �����:

\lemma{�����.} ����� $A$\� $m$\� ������ ������������ ���������. �����
���������� ������ �� ������ ������������ �����~$n$
�������������� ������� ������� ������ ������ ����������� �����,
������� ����������� ��� �� �����������~$A$ ������������ �~$n$.

�������������� �����.
        %
��� � ������, � ��� ����� ��� ������� �������� ����� �����,
������� ����� ���� �� ��������� �~$A$ ��� ��, ��� � ��������.
���� �� ��� ����� �������������� ������ ����� �����, ����~$x\hm\in
A$, ������\� ����~$x\hm\notin A$. ��� ���� �� ����� ���������
���, �� ����, ����� �� ������� ����� ����� �� ����� ����
(� ����� ��� ����� � �� ������).

������ ������ ������� � ���������. ����� $P$\� ������������
������������ ���������. ���������� ������������ ���������
���~$A\hm\times P$. ��� �������� �~$A$, ��� ���
$A$~�������� $m$\� ������. (������\� �� � ����������� ���������� ���
���� � ���������� ����������� �����, � �� ���, ��,
��� ������, ��� �� ������ ����\� ���� ����� ���������
����������.) ������� �������, ����������
        ���������� ����� ������̣����
�������~$f$ ����
����������� ���������� � ����� ���������:
        $$
f(n,m) \in A \Leftrightarrow \text{$(n \in A)$ � $(m \in P)$}.
        $$
� ���������, ���~$m\in P$ �����~$n$ �~$f(n,m)$ ������������
����������� ��� �� �����������~$A$. �������, ����������~$P$
� ���������� ������������������~$p(0),p(1),\dots$, �� �����
��������� �����~$f(n,p(0)),f(n,p(1)),\dots$ � �������� �����
�����, ������� ����������� ��� �� �����������~$A$ ������������
�~$n$.

�����~$n\hm\in A$. �������, ��� ���������~$X$ ���������� �����
������� ����� (��� ��� � ���� ������ ���� �����������~$A$) �����
����������. � ����� ����,~$f(n,m)\hm\in X$ ���~$m\hm\in P$ (��
����������~$X$) �~$f(n,m)\hm\notin X$ ���~$m\hm\notin P$ (��������� �
���� ������~$f(n,m) \hm\notin A$, �~$X\hm\subset A$).
����� �������, �������~$m\hm\mapsto f(n,m)$ ������ ������������
���������~$P$ � ���������~$X$, ��� ���~$X$ ����������� � ������
����������.

������ ������ ������ ������, ������� ����������� �����,
����~$n\hm\notin A$. ����ͣ� ��� ������������ ����������� ���������~$P$
�~$Q$. ���������� ������������ ��������� ���~$(A\hm\times P)\hm\cup
(\bbN\hm\times Q)$. ����� �������~$f$ ������ ��� �~$A$.
��� ��������, ��� $f(n,m)\hm\in A$ ����� � ������ �����, �����
$(n\hm\in A\ \hbox{�}\ m\hm\in P)$ ��� $m\hm\in Q$.
��� �
������, ���~$m\in P$ �����~$n$ �~$f(n,m)$ ������������
����������� ��� �� �����������~$A$, ��� ��� �� ����� �����
����������� ������������������~$f(m,p(0)),f(n,p(1)),\dots$;
�������� ���� ��������, ��� (����~$n\hm\notin A$) � ����
������������������ ���������� ����� ��������� ������.

����� ��� �� ��� � ���������~$X$ ���� ������ ����
������������������ �������. �� ������ ������������� $X$~��
������������ �~$A$. �������, ���~$f(n,m)\hm\in X$ ���~$m\hm\in P$ (��
����������) �~$f(n,m)\hm\notin X$ ���~$m\hm\in Q$ (��� ��� � ����
������ $\langle n,m\rangle$~����������� ������ �������������
��������� ��� � $f(n,m)$~�����������~$A$). ����� �������,
�������� ���������~$X$ ��� �����������~$m\hm\mapsto f(n,m)$
��������~$P$ ��~$Q$. �� ���� �������� �������� ($X$~���������,
��� �������, � ��������� ����������� ����� ���������� �
���������). � �� ������ ������������� ���������~$P$ �~$Q$ ������
�������� ���������� ����������.

����, �� ������� ��� ������� �������� ����� ��������, �������
����������� ��� �� �����������~$A$ ������������ � ��������.
�������� �� �����������, �� ��������� ���أ��� ����������.
����� ��������.

����� ������~$A$ �~$B$\� ��� $m$\� ������ ������������ ���������.
�������, ��� ��� ���������� ���� ���������� �������������
������������ ����. ����� ������� ��� ������������ �� �����.
�� $k$\� �� ���� �� ����� ������� ����������� ������������
        $$
a_1 \leftrightarrow b_1,
a_2 \leftrightarrow b_2,\dots,
a_k \leftrightarrow b_k,
        $$
��� �������~$a_i\in
A\hm\Leftrightarrow b_i\hm\in B$ ��� ����~$i$. �� ޣ���� ����� ��
��ң� ����������� �����, �� �������� � ����� ����� �����
������������. ��������� ���� $m$\� ����������~$A$ �~$B$, ��
������� ��� ����������. ��� ���� ���������� ���� ����� ���������
������� ����������, �� �������������� ����� ��� ���������
������ ���������. �� ��ޣ���� ����� �� ������ �� �� �����,
������ ������ ������.

� ������� ���� ������� ���� ������� ���������� ������������,
�����������~$A$ �~$B$.
        %
\end{proof}

� ����� ������ ������ ���������� ��� ���������, ������������
���� ���������� �������������, �������� ����������� ����������.
������� ���������� ������� ����������, ��� �� �������� �������
���� ���� $m$\� ������ ������������ ��������� (���, ��� �� ��,
���� ���� ������������ ��������� � ���������� ��������������
�����������).

\section{������������ ���������}\label{chapt06-5}

� ���� ������� �� ���������� ������� � ����������� ����� ���
��������� ������ (������������ �� ������ ������) ����������:
����������� ����������� ���������������� ���������~$A$ ��
���������, ���� �� ����������� ���� (�������������) ��������������
���������~$A$.

����������� ��������� ������� ��������� ������������ �������� (���������
� �������~$n$ �� ����������~$W_n$).
�������, ��� ���������~$A$ �������� \emph{������������}\index{������������
���������}\index{���������!������������}, ����
���������� ���������� (�� ����������� ����� ������̣����)
�������~$f$ � ����� ���������: ��� ��������� � ������ ������~$n$
������ ������������~$W_n$ ���������~$A$ � ���� ������� � �� ��������:
        $$
W_n \subset A \Rightarrow f(n) \in A \setminus W_n.
        $$

\begin{problem}
        %
��������, ��� ������������ ��������� �� ����� ���� ��������.
        %
\end{problem}

����, ��� ���������� � ����������� ��������������\� ���� �����
���������� �� ����������� ���������� ��������������� ���������,
��� ��� ����� ���������� �������������� ��������� �����������.
������������ ������� �����������, ��� ����� � ��������.

\begin{theorem}
        \label{coproductive-m-complete}%
����� $A$\� ������������ ���������, $K$\� ������������
������������ ���������. ����� ���������� �~$K$ $m$\� �������� �~$A$.
        %
\end{theorem}

(�� ����� �������, ��� $A$~�������� ���������� ��������������,
��.~����.)

\begin{proof}
        %
����� $f$\� �������, ������� ����������
�� ����������� �������������� (� ���� ������� ��� ������������ �
��������� �������).

�� �������� ����� ������̣����
        ����������
���\-�\-���~$s$ � ������ ����������:
        \begin{itemize}
             \item
$x \notin K  \Rightarrow W_{s(x)}=\varnothing;$
             \item
$x \in K  \Rightarrow W_{s(x)}=\{f(s(x))\}.$
        \end{itemize}
(������ �������� �������������, ���
$f(s(x))$~���������� ���~$x\hm\in K$).
������ ��� ������ ��� � ������� ������� � ����������� �����,
�������, ��� � ������ ������ $f(s(x))$~���������� � �����������~$A$:
��������� ���������
� �������~$s(x)$ ����� � �������� �������������~$A$,
�����~$f(s(x))$ ������ ���� ���������~$A$. ��������, �� ������ ������
$f(s(x))$~�� �����������~$A$. � ����� ����, ���� �� ��� ���� ��
���, �� ���������~$W_{s(x)}$ ���� �� �������������~$A$, � ������
�����~$f(s(x))$ ������ ���� �� ���� ���������~$A$, �� �������� �
��� ������������\� � ��� ������.

������� ���� ��� ������� ��������� ����� �������~$s$, ��
�������~$x\hm\mapsto f(s(x))$ ����� $m$\� ������� ���������� ���������~$K$ �
���������~$A$, ��� �� � �������. ��� �� ţ �������?

���� �� �� ������ �������� (��� $x\hm\in K$) ������
��~$f(s(x))$,
�, ������, ������~$f(x)$, ������� �������� �� �� ����. ��� ������,
�� ����������� �� ������������ ��������� ���
        $$
V = \{ \langle x,y\rangle \mid \text{$x\in K$ � $y=f(x)$}\};
        $$
������� ����� ��������� ����� �� ��������� ��� � ��������
�� ������ ��������������� ���, ��� ���������\� �������. ��
� ����� ������, ����� � ������ ����� ������� ��������
�����~$f(s(x))$, ��� ������
��������� ������: ��� � ������� � ������ � ����, ��� ����������~$V$
��� ���� �����~$s(x)$, � ��� ����������~$s(x)$ ���� �����~$V$.

������ ������ ���� ��������� ��������� ������������ ������� �
����������� �����. �������� ����� ������̣����
        ����������
������� ����
����������~$h$ � ������ ����������:
        \begin{itemize}
        \item
$x \notin K  \Rightarrow W_{h(x,t)}=\varnothing;$
        \item
$x \in K  \Rightarrow W_{h(x,t)}=\{f(t)\}.$
        \end{itemize}
(�������� ���� �� ������ �����������\� ��������� ��� � ����������
������. �������, ��� $f(t)$~����� ���� � �� ����������, ����� ���~$\{f(t)\}$
�� �������� ������ ���������.) �� ������� � ����������� ����� (��� ������������ ��������)
��� ������~$x$ �������~$t\hm\mapsto h(x,t)$ ����� ����������� �����,
�, ��� �� �������� � ������� � ����������� ����� � ����������,
��� ����������� ����� ����� ������� ��������� ��������� ��~$x$.
����� �������, ���������� ����� ������̣���� ���������� �������~$s$,
��� �������
        $$
W_{s(x)}=W_{h(x,s(x))}
        $$
��� ����~$x$. ��� ��������� ����� ����������:
        $$
W_{s(x)}=W_{h(x,s(x))}=
        \left\{
            \begin{aligned}
                &\varnothing,  \text{ ���� $x\notin K$,}\\
                &\{f(s(x))\},  \text{ ���� $x\in K$}
            \end{aligned}
        \right.
        $$
--- ��� ����� ��, ���� �� � ������. �������, ��� ��������
$f(s(x))$~����������
��� ����~$x$ (����� $W_{s(x)}=\varnothing$, � $f(s(x))$~������
���� ����������). ��� �����, ������� � �����������
����� ��������� �������� ������� ������������� ���� � ������ �
��������� ��������������.
        %
\end{proof}

������������
���������, ���������� ������� �����������, ����������
\emph{�����������}\index{���������� ���������}\index{���������!����������}
(creative; ������ ��� ����� ��������� ��� \��
����������\��). �������� ����������� ���: ��� ��������� (������,
��� ����������) ����� ��������������, ��� ����� ���������������
�������: ���� ���\� �� ���������� ������ ��������� ���������
�������� �� ����������, �� � ����� ����� ������� �������
����������, ������� ������ �������� ����� ��������.

��� �� �����, ���������� ���������, ������������ ��������� �
���������� �������������� ����������� � $m$\� ������ ���������\�
���� � ��� �� �����, � ����� ��� ��������� �� ����� ������ �
��������� ������ ��������� (���������� ���� ����������
�������������).

���� ��������� �����������, �� ����� ��������� ��� �������� ���������
����������� ���������. �� ������ ���� ������� ������ ���������.
�������� � ���� ������������ ������� (\�� �������,
������������ �� ����������� ������������� ���������), �� �������
��������� �������. �� �������� �������������� ������������.
�������� � ����� ������������ ������������ �������, �������
������ �������. � ����������� ��������������� ������������ �����
����� ��������� ������������ ������� � ��� �����. ���������
����������� ���������� ������������������ ���������
������������� ���������. (��� �� ��� ������, ����� ����������,
��� ���������� �������������� ��������� �������� �����������
������������
������������.) �� ���� ����������� ������� ����� \��
������������\��\ ����������, �� ������� ���� �ݣ �������: ����
������������ ������������ ������ ������������� ���������
(��������� ������ ������������������), ����� ����� �ݣ ����
������� ������������� ��������� (��� �������, �������
�����~$\omega$). ������� ��� � ������������������, ����� ��������
������������ �������, ��������� $(\omega\hm+1)$\� �� ������� � ���
�����, ����� ��������� ����� ������������������, $(\omega2)$\� ��
�������, $(\omega3)$\� ��,\dots, $\omega^2$\� �������~\���

��, �������, �������� ����� ������� ��������, �������������
������������ (� ������ ��������������) ���������, �� �������.

% \begin{remark}
% (��������� �����? ������, ��� ����� ������ ��� ��������������
% ���������. �������, �� ��� ���� ���\� �� ��������, ���� ����������
% �������� ��� ����\� �� ��������. � �����, ��� ������������
% ����������� ���\� �� �������� ���� � ��������� � ����� �� ������
% �������� �����?)
% \end{remark}

\begin{problem}
        %
�� ��������� ������� � ����������� ����� (�
�������~\ref{coproductive-m-complete}), ��������, ��� ���
������� ������������� ���������~$A$ ���������� \textsl{����� ������̣����}
        ����������
�������~$f$, ��� ������� $W_n\hm\subset A$ ���ޣ� $f(n)\hm\in A\setminus W_n$.
(��������: ��������� $W_n$ � ������ ����������, ���  ��� �������� ���
�������������� ����� � �������~\ref{m-complete-isomorphism-theorem}.)
        %
\end{problem}

\section{���� ����������� ��������}
        \index{���������!�������������}%
        \index{����������� ���������}%

� ���� ������� �� ������������ ��������� ����������, ����������
��� ���������������� ������������ ��������. ��� ����������
����������� ������ ��� ���������� ���� �������� � $m$\� �������,
��������������, ����������� ���������������� � �� ����������� $m$\�
������ ��������.

�����~$A$ �~$B$\� ��� ���������������� ��������� (�����������
�����). ��������, ��� ��� ���������� ������������, ���� ��
���������� ����������� ���������, ����������� ���� �� ��� � ��
��������������� � ������.
��� ����������� ����� ����������������� ���: ���� $W_x$ �
$W_y$\� ��� ���������������� ������������ ���������,
����������~$A$ �~$B$ ��������������, �� ����������� $W_x\cup
W_y$ �������� �� ��� ����������� �����. (��� ����� ������
���������� ������������ ��������� �����~$W_x$ �~$W_y$, ������,
��� $W$\� ������� ������������� ���������.)

������ ����, ��� ����� �������������� ����������� ������� �����
�����������. ����� ��������, ��� ���������������� ���������~$A$
�~$B$ \emph{���������� ����������}, ���� ���������� ����������
        \index{���������!����������� �������������}%
        \index{���������� ����������� ���������}%
�������~$h$ � ����� ���������: ���� $A\hm\subset W_x$,
$B\hm\subset W_y$ � $W_x\hm\cap W_y\hm=\varnothing$, ��
$h(x,y)$ ���������� � $h(x,y)\hm\notin W_x \hm\cup W_y$.

����������� ������������� ����� �������������� ����\� ����
�����: �� ���������� ���������� �������
$\varphi_n$, ������� ���� �� ����� ������̣����,
�� ���� ������ ���������~$A$ ��������� ��
����, � �� ���� ������ ���������~$B$\� �������. (����� �������,
���~$\varphi$\� ������� ������������� �������.) ��������������
��������� � ����������� �������: ���������~$A$ �~$B$
\emph{������ ���������� ����������}, ���� ���������� �����
������̣���� ����������
�������~$h$, ������� �� ������~$n$ ���������
�����~$h(n)$, � ������� ������� $\varphi_n$ \�� ���������\��.
������ �������� �ң� �����: ���� $\varphi_n(h(n))$ ��
����������, ���� $h(n)\hm\in A$, �� $\varphi_n(h(n))$ �� �����
����, ���� $h(n)\hm\in B$, �� $\varphi_n(h(n))$ �� �����
�������.

\begin{problem}
        %
��������, ��� �� ������� �����������
������������� �������� ����������� ������������� (���
����������� ������������ ���� ������������).
        %
\end{problem}
        \index{���������!����������� �������������}%
        \index{���������� ����������� ���������}%

�������� ����������� ����� �����, �� ������������ ���������
�������, � �� � ���� �ݣ ���Σ���.

���������� �� ������ ���������� ����������� ������������ ���������?
����� ������, ��� ����������� ������������ ����������� ���� ����
����� ��������, � ������ ���������
$\{x\mid \varphi_x(x)\hm=1\}$ �
$\{x\mid \varphi_x(x)\hm=0\}$, ��� ������� � �������� �������~$h$
����� ����� ������������� �������.
        \index{������������ �������}%

\begin{problem}
        %
��������� ���.
        %
\end{problem}

��������� ���� �������� (����� ����������� � ������),
��������� ������� $m$\� ���������� ��� ���.
����� ���� ����� ��� ��������.
����� $\langle A,B\rangle$ � $\langle C,D\rangle$\� ��� ����
���������������� ������������ �������� ($A$ �� ������������
�~$B$, � $C$\� �~$D$). ����� ��������, ��� ���������� �����
        \index{$m$\� ����������!���}%
������̣���� ������� $f$ \emph{$m$\� ������~$\langle A, B\rangle$
�~$\langle C,D\rangle$}, ���� $f(A)\hm\subset C$ �
$f(B)\hm\subset D$.

\begin{problem}
        \index{���������!����������� �������������}%
        \index{���������� ����������� ���������}%
        (\textbf{�})~%
��������, ��� ����~$f$ ������~$\langle A,B\rangle$ �~$\langle
C,D\rangle$ �~$C$ �������� ��~$D$ ���������� ����������, ��
�~$A$ �������� ��~$B$ ���������� ����������.
        (\textbf{�})~%
��������, ��� ����~$f$ ������~$\langle A,B\rangle$ �~$\langle
C,D\rangle$ � ���� $\langle A,B\rangle$ ���������� ����������,
�� � ����~$\langle C,D\rangle$ ���������� ����������.
        (\textbf{�})~%
��������, ��� ����~$f$ ������~$\langle A,B\rangle$ �~$\langle
C,D\rangle$ � ���� $\langle A,B\rangle$ ������ ����������
����������, �� � ����~$\langle C,D\rangle$ ������ ����������
����������.
        %
\end{problem}

����������� ���������� ����� �������, ���������� �������������,
����� ��� $x\hm\notin A\hm\cup B$ ����������� $f(x)\hm\notin
C\hm\cup D$ (������� �������, $f$ ������ �������~$A$ �~$C$ �
������������~$B$ �~$D$). � ���� ������ �� ����� ��������, ���
$f$ \emph{������ ������} ����~$\langle A,B\rangle$ �
����~$\langle C,D\rangle$.

������ �� ����� ���������� \emph{$m$\� �������} � \emph{������� $m$\�
�������} ��� ���� ���������������� ������������ ��������,
        \index{$m$\� ������ ���������}%
        \index{$m$\� ����������}%
������ $m$\� ���������� (�������������� ������� $m$\�
����������) ����� ����� ���� � ������.

\begin{problem}
        %
��������, ��� ���� ���� �������� ������ ���������� �����������,
�� ��� �������� ������ $m$\� ������. (��������. �����
����~$\langle A,B\rangle$ ������ ���������� ����������,
�~$\langle K,L\rangle$\� ����� ���� ����������������
������������ ��������. �� ������ ������������ ����� $x$ �����
��������� ���������� ������� $\psi_x$ � ����� ���������: ����
$x\hm\in K$, �� $\psi_x$ ����� ���������� � ���������� �� �������
���� � �������� ����� �����, ���ޣ� ��� ��� ����� �����������~$A$;
���� $x\hm\in L$, ��
$\psi_x$ ����� ���������� � ���������� �� ���� ���� �
�������� ����� �����, ���ޣ� ��� ��� ����� �����������~$B$;
���� $x\hm\notin K\hm\cup L$, ��
$\psi_x$ ����� ���� ��~$A$ � ������� ��~$B$. ����� ���������
����� �������, ����������� $K$ � $L$; ���� $x$ �� ������������
� ����� �� ���� ��������, ��������� � ������ $\psi_x$ ����
���� $\langle a,0\rangle$ � $\langle b,1\rangle$; �����~$x$
��������������, ���������������. ����� �������� ���������������
���������� ������� ��������� $\varphi$ � ������� �����������
��������������~$A$ �~$B$.)
        %
\end{problem}

\begin{problem}
        \index{���������!����������� �������������}%
        \index{���������� ����������� ���������}%
        %
��������, ��� ������ $m$\� ������ ���� �������� ������
���������� �����������. (��������: ������ ���������� �����������
���� ���������� � � ��� ��������.)
        %
\end{problem}

�� ���������������� � �������� ����� ����������� ��������, ���
�������� �������, ������� $m$\� ������� � ������� �����������
������������� ������������. ����� ��������, ��� � ���������
����� ������ �������� ����������� ������������� ������������ ��.
����������� ��� ���� ���������� ��������������
�������~\ref{coproductive-m-complete} � ���, ��� ������ ����������
��������� �������� $m$\� ������. �������,
��� ������� ����� ����������� �������������� � �������
����������� �������������� �������� ����� ��, ��� �����
��������������� � ����������� �����������������.

\begin{problem}
        %
����� $\langle A,B\rangle$\� ���������� ����������� ����
���������������� ��������. ��������, ��� ��� �������� ������
$m$\� ������. (��������. �����~$K$ �~$L$\� ������������
���������������� ������������ ���������. ����� $h$\� ������� ��
����������� ����������� ������������� (��������~$A$ �~$B$). �
������� ������� � ����������� ����� ��������� ����� ������̣����
        ����������
������� $x(n)$ � $y(n)$ � ������ ����������: (1)~���� $n\hm\in
K$, �� $W_{x(n)}\hm=A$, $W_{y(n)}\hm= B\hm\cup\{h(x(n),y(n))\}$;
(2)~���� $n\hm\in L$, �� $W_{x(n)}\hm=A\hm\cup\{h(x(n),y(n))\}$,
$W_{y(n)}\hm=B$; (3)~���� $n\hm\notin K\hm\cup L$, ��
$W_{x(n)}\hm=A$, $W_{y(n)}\hm=B$. �������� ������, ��� ���
$n\hm\in K$ ��������~$h(x(n),y(n))$ ���������� �
�����������~$A$, ��� $n\hm\in L$ ��������~$h(x(n),y(n))$
���������� � �����������~$B$, � ��� $n\notin K\hm\cup L$
�������� $h(x(n),y(n))$ ���������� � ����� ��� $A\hm\cup B$.)
        %
\end{problem}

����, ��� ������ ���������������� �������� ������������.
��������� ���� ��������, ����� �������� ������������ ����� ����
��� ���������� ����������� ��������, ��� ���� ��������������
��������� �������� ����� ������ ����� �����, \��
�������������\��\ ������� � ����� ������ ���� ����������
����������� ��������.

����� �����, ����� ������� ���������������� ���������~$A$ �~$B$.
����ף� ��� ����� $\langle A,B\rangle$\� �������������� �
����� �� ���������
�ң� �������: ��� ��� �����������~$A$, ��� ���
�����������~$B$ ��� ��� ��� �� ����������� $A\hm\cup B$. (�����
�������, ���� ��� ������ ���������������\� ��������� $A$,
���������~$B$ � �������.)

\begin{problem}
        %
����� $\langle A,B\rangle$\� ������ $m$\� ������ ����
������������
��������. ��������, ��� �� ������ �����~$k$ �����
�������������� �������� ����� ������ ����� ��������� �����,
������� ����� $\langle A,B\rangle$\� ������������~$k$.
(��������: ���������� �� �������� � ����������������
�������~\ref{many-numbers} � ����� �
�������~\ref{m-complete-isomorphism-theorem}.)
        %
\end{problem}

\begin{problem}
        %
        \index{����������!$m$\� ������ ���}%
        \index{$m$\� ������ ���������}%
�����~$\langle A_1,B_1\rangle$ �~$\langle A_2,B_2\rangle$\� ���
������ $m$\� ������
���� ������������ ��������. ����� ���
��������� ��������� � ��������� ������: ���������� ����������
������������ (�������) $i\colon\bbN\hm\to\bbN$, ��� �������
$i(A_1)\hm=B_1$ � $i(A_2)\hm=B_2$.
            %
(��������: ���������� �� �������� � ����������������
������~\ref{rogers-theorem}
�~\ref{m-complete-isomorphism-theorem}.)
        %
\end{problem}
