% ���������� �������� 20.04.2000
\chapter{�������������� ��������}\label{chapt08}
        \index{�������������� ��������}%

\section{������~$\Sigma_n$ �~$\Pi_n$}\label{chapt08-1}
        \index{$\Sigma_n$}\index{$\Pi_n$}%

�� ��� ��������, ��� ������������ ��������� ����� ������������
        \index{������������ ���������}\index{���������!������������}%
���������� ��� �������� ���������� ��������:
        \index{���������� ���������}\index{���������!����������}%
���������~$A\hm\subset\bbN$ ����������� ����� � ������ �����, �����
���������� ���������� ���������~$B\hm\subset\bbN\hm\times\bbN$,
��������� �������� ���
��������. ���� ������������� ��������� �� ����������, �� �����
�������, ��� ��������~$A(x)$ ����������� ����� ����������� �����
� ������ �����, ����� ��� ����� ����������� � ����
        $$
A(x) \Leftrightarrow \exists y B(x,y),
        $$
��� $B(x,y)$\� ��������� ���������� ��������.

(� ���� �������
�� ������������ ���������� �������� � ����������� �����������
�������������: ������� $\exists x$ �������� ��� \�� ����������~$x$\��,
        \index{$\exists x$, $\forall x$}%
        \index{$\land$, $\lor$, $\lnot$}%
        \index{����������}%
        \index{����������}%
        \index{���������}%
        \index{��������}%
������� $\forall x$ �������� ��� \�� ��� ����~$x$\��, ���� $\land$
�������� ��� \�� �\��\ � ���������� �����������,
���� $\lor$ �������� ��� \�� ���\��\ � ���������� �����������,
���� $\lnot$ �������� ��� \�� �������, ���\��\ � ���������� ����������.
��� � ������, ���� $\Leftrightarrow$ �������� ��������������.)

��������� ������������ ������: ��� ����� ������� ��� ������
������ ���������? ��������, ����� �������� ����������� �
����
        $$
A(x) \Leftrightarrow \exists y \exists z C(x,y,z),
        $$
��� $C$\� ���������� �������� ����� ����������� �����? �����
����������, ��� ��� ��\� �������� ������������ ���������. � ����� ����,
��� ������ ������ �������� ������ ���� ����� �������� �����,
����������� ���������� ��������� ��� (������� �� ����������
����������� ��������): ��������~$C'$, ��� ��������~$C'(x,[y,z])
\hm\Leftrightarrow C(x,y,z)$, ����� ���������, �~$A(x)
\hm\Leftrightarrow \exists w C'(x,w)$.

������ ������: ����� �������� ����������� � ����
        $$
A(x) \Leftrightarrow \forall y B(x,y),
        $$
��� $B(x,y)$\� ��������� ���������� ��������? �����: ��,
��������� ������� ����������� (��� ������ �������,
\emph{��������������}). � ����� ����, �������� � ����������, �����
        \index{����������������}%
        $$
\lnot A(x) \Leftrightarrow \lnot \forall y B(x,y)
           \Leftrightarrow \exists y (\lnot B(x,y)),
        $$
� ���������� �������� �������� ����������� ��� �������� �
����������.

����� ����� �����������. ��������~$A$ \emph{����������� ������~$\Sigma_n$},
        \index{$\Sigma_n$}%
���� ��� ����� ����������� � ����
        $$
A(x)\Leftrightarrow
\exists y_1 \forall y_2 \exists y_3\dots B(x,y_1,y_2,\dots,y_n)
        $$
(� ������ ����� ����� $n$~������������ ���������) ��� ����������
����������� ��������~$B$. ���� � ������ ����� ���������
$n$~������������ ���������, ������� � �������� �����������
$\forall$, ��
        \index{$\Pi_n$}%
��������� ����������� \emph{������~$\Pi_n$}.

������� ��� ��������, ������� �� �� �������� ��� ��������:

\begin{theorem}
        \label{basic-arithmetic-hierarchy}%
(\textsf{�})~����������� ������~$\Sigma_n$~[$\Pi_n$] �� ���������, ���� �
������ ����� ��������� ������� ����� ��������� � ���������,
����� ������ ������� ��� ��������� ������������� [�����������] �
����� ����� ���������� ������� �����
��������� ���������~$n$.
        %
(\textsf{�})~��������� ������� �� ������~$\Sigma_n$ ����������� ������~$\Pi_n$ �
        \index{���������}%
��������.
        %
\end{theorem}

\begin{proof}
        %
��� �������������� ������� ����������� ���������� ���������
����� ������� ���������� �������� � ������� ��������� ���. ���
�������������� ������� ���� ��������� ��������� ������ (�����
��� ��������), ���� ��� �� �������� � ����������� �������� (���
��� ���� �� ������).
        %
\end{proof}

�� �������� � ���������; �� ����� �������� ����� ������� ���:
��������� ������~$\Sigma_n$ ���������� �� ���������� � �������
������������������ �������� \�� ��������\� ����������\� ��������\�
        \index{��������}%
        \index{����������}%
����������\� \dots\� ��������\��, � ������� ����� $n$~��������
��������. ������ �������� �������� ���������
����������� ��������� (����� ���������� � ��������) �� �������,
��� ��� �������� ���� � ���������� �����������~$\bbN^{n+1}$.

\begin{theorem}
        \label{arithmetic-union-intersection}%
        \index{$\Sigma_n$}%
        \index{$\Pi_n$}%
����������� � ����������� ���� �������� �� ������~$\Sigma_n$
�����������~$\Sigma_n$. ����������� � ����������� ����
�������� �� ������~$\Pi_n$ �����������~$\Pi_n$.
        %
\end{theorem}

\begin{proof}
        %
������ �������� ��� ����������� �� ���������� �����, ������, ���
���������� � ���������� ����� ���� ������� �� ������~$\Sigma_n$ �����
        \index{����������}%
        \index{����������}%
� ��� �� ������ (���������� ���~$\Pi_n$). �� ���� �� ����� ������
�������� � ��������������: ����, ������,
        \begin{align*}
A(x) & \Leftrightarrow \exists y \forall z B(x,y,z),\\
C(x) & \Leftrightarrow \exists u \forall v D(x,u,v),
        \end{align*}
��
        $$
A(x) \land C(x) \Leftrightarrow
   \exists y \exists u \forall z \forall v [B(x,y,z) \land D(x,u,v)],
        $$
���������� � ���������� ������� �������� ��������� � ��������
������ ��������� ���� ��������� � ����, ��� ����������� ����.
���������� ����� ����������� ��� �������~$\Sigma_n$ �~$\Pi_n$
��� ������������~$n$.
        %
\end{proof}

�� ���������� ������~$\Sigma_n$ �~$\Pi_n$ ��� ��������
����������� �����; ����������� ������� ��� ����� ������� � ���
�������� ��� ����������� �����, ����� � ������ ����� \��
�������������� ��������\��. �������, ���
�������� ��������� ���, �������������� ������~$\Sigma_n$,
����� �����������~$\Sigma_n$ (��������� ��� ��������
������������� � ������ ����� ���������� � ����).

�������� ��������� ��������, ����� ���������, ��� ������ �� ����
�������~$\Sigma_n$ �~$\Pi_n$ ���������� � ������ �� �������~$\Sigma_{n+1}$
�~$\Pi_{n+1}$. ����� �������� �ݣ ���:
        $$
\Sigma_n \cup \Pi_n \subset \Sigma_{n+1} \cap \Pi_{n+1}.
        $$

\begin{theorem}
        \label{arithmetic-m-reducibility}%
������~$\Sigma_n$ �~$\Pi_n$ \�� ������������� ����\��\
        \index{$m$\� ����������}%
        \index{$\Sigma_n$}%
        \index{$\Pi_n$}%
������������ $m$\� ����������:
����~$A\hm\lem B$ �~$B\hm\in \Sigma_n$~[$B\hm\in \Pi_n$],
�� �~$A\hm\in\Sigma_n$~[$A\hm\in\Pi_n$].
        %
\end{theorem}

\begin{proof}
        %
� ����� ����, ����� $A$~�������� �~$B$ � ������� �����
������̣���� ���������� �������~$f$, �� ����~$x\hm\in A
\hm\Leftrightarrow f(x)\hm\in B$. ����� $B$~�����������, ��������,
������~$\Sigma_3$, �� ����
        $$
x\in B \Leftrightarrow \exists y \forall z \exists u R(x,y,z,u),
        $$
��� $R$\� ��������� ���������� ��������. �����
        $$
x\in A \Leftrightarrow
f(x) \in B \Leftrightarrow \exists y \forall z \exists u R(f(x),y,z,u),
        $$
� �������� ��������, ��� $R(f(x),y,z,u)$ (��� ��������
���\-ף�\-��~$\langle x,y,z,u\rangle$) ���������.
        %
\end{proof}

\begin{problem}
        \label{arithmetic-product}%
��������, ��� ���� ���������~$A$ ����������� ������~$\Sigma_n$,
�� ���������~$A\hm\times A$ ����� ����������� ����� ������.
        %
\end{problem}

\begin{problem}
        %
��������, ��� ���� ���������~$A$ �~$B$ ����������� ������
$\Sigma_n$, �� �� �������� $A\setminus B$ �����������
������ $\Sigma_{n+1}\hm\cap\Pi_{n+1}$.
        %
\end{problem}

\section{������������� ��������� �~$\Sigma_n$ �~$\Pi_n$}\label{chapt08-2}
        \label{universal-sigma-pi}%
        \index{������������� � $\Sigma_n$/$\Pi_n$ ���������}%
        \index{���������!������������� � $\Sigma_n$/$\Pi_n$}%

�� ��� ��� �� �� ��������, ��� ������~$\Sigma_n$ �~$\Pi_n$
������������� ����������� ��� ������~$n$. ����� �������� ���,
��������, ��� � ������ �� ���� ������� ������� �������������
��������� (��� ���������������� ������) � ��� ��� �� �����������
������� �������.

\begin{theorem}
        \label{universal-sigma-pi-exist}%
��� ������~$n$ � ������~$\Sigma_n$ ���������� ���������,
������������� ��� ���� �������� ������~$\Sigma_n$. (���
���������� ����� ������������� � ������~$\Pi_n$.)
        %
\end{theorem}

������ �� ������������� ��������� �� ������~$\Sigma_n$, �� �����
� ���� ��������� ��� ����������� �����,
������� ����������� ������~$\Sigma_n$ �
����� ������� �������� ����������� ��� ��������� �����������
�����, ������������� ������~$\Sigma_n$.

\begin{proof}
        %
��� ������~$\Sigma_1$ (������������ ��������) �������������
        \index{������������� ������������ ���������}%
        \index{������������ ���������!�������������}%
�������������� ��������� �� ��� ���������. � ��� ������� �����
��������� ������������� ��������� � ��� ����� ������� �������
��������. (�������� ���� � ������� ������, ��� ��� �� \��
�������\��\ ������ �� ���������� �������������� �����������
���������.)

�� ����������� �������� ������~$\Pi_2$ ����� ���
        $
S(x) \hm\Leftrightarrow  \forall y \exists z R(x,y,z),
        $
��� $R$\� ��������� ���������� ��������. �� ��
����� ������������ ���������� � ��� �������� ����
        $
S(x) \hm\Leftrightarrow \forall y P(x,y),
        $
��� $P$\� ��������� ������������ ��������. ������ ��� �����,
��� ��������� ������������� ��������� ������~$\Pi_2$. ����ͣ�
������������� ������������ ��������~$U(n,x,y)$, �� ��������
��������� ���������~$n$ ���������� ��� ������������ �������� ���
����������� �����. ����� �� ��������~$T(n,x)\hm= \forall y
U(n,x,y)$ ��� ��������� �����������~$n$ ���������� ���
$\Pi_2$\� �������� ����������� �����. � ������ �������, ����
��������~$T$ �� ���������� ����������� ������~$\Pi_2$.

���������� � �������������� $\Pi_2$\� ��������� �����, ��������,
������������� $\Sigma_2$\� ����������.

���������� ����� ����������� � ��� $\Sigma_3$\�\ � $\Pi_3$\� ��������
(������� ������� ���������� � $\Sigma_3$\� ����������, ��� ��� �
��� ���������� ������� �������� ��������� ������������� � ������
������������ ���������), � ������ ���~$\Sigma_n$\�\ �
$\Pi_n$\� ��������.
        %
\end{proof}

\begin{theorem}
        \label{arithmetic-complement}%
������������� $\Sigma_n$\� ��������� �� ����������� ������~$\Pi_n$.
����������� �������, ������������� $\Pi_n$\� ��������� �� �����������
������ $\Sigma_n$.
        %
\end{theorem}

\begin{proof}
        %
���������� ������������� $\Sigma_n$\� ��������~$T(m,x)$. ��
����������� ��� ��������, ��� ����� ��� ������� (������������,
���� �������������~$m$) ���� ��� $\Sigma_n$\� ��������. �����
$T$~����������� ������~$\Pi_n$. ����� ��� ���������, ��������~$D(x)\hm=T(x,x)$,
����� ����������� ������~$\Pi_n$ (��������,
������, ���~$D \hm\lem T$), � ţ ���������, ��������~$\lnot D(x)$,
����������� ������~$\Sigma_n$. �� ����� �� ����� ����, ��� ���
$\lnot D$~������� �� ���� ������� ��������~$T$ (��� ����������
�� $m$\� �� ������� � �����~$m$), � $T$~������������.
        %
\end{proof}

�� ���� ������� �������, � ���������, ��� ����� ��
�������~$\Sigma_n$ �~$\Pi_n$ �������� ����������� ������������� ������
�� �������~$\Sigma_{n+1}$ �~$\Pi_{n+1}$. (�� ������ ������,
��� ���� �����������~$\Sigma_n \hm\cup \Pi_n$ �������� �����������
������������� �����������~$\Sigma_{n+1} \hm\cap \Pi_{n+1}$.)

\section{�������� ������}\label{chapt08-3}

�� ����� ��������, ���
        \index{�������� ������}%
�����~$\Sigma_n$ ��������� � ������� ���� $A$\� ������������
�������� ��� ���������� ���������~$A$ (���������� ��~$n$,
�����������). ����� ���������, ��� ��� �� ���������, ���
����������� ��� ���������� �������� ������.

����� $X$\� ������������ ���������. ����� $X$\� ������������
        \index{$A$\� ������������ ���������}%
        \index{���������!$A$\� ������������}%
�������� ���� �������������. ��� ��������� ����� $m$\� ������ �
        \index{$m$\� ������ ���������}%
        \index{���������!$m$\� ������}%
������ $X$\� ������������ �������� � ��� ������, ��� ��� ������
$X$\� ������������ ��������� � ���� $m$\� ��������. ��������
�������, ��� �� ������, ����� ���~$x\hm\mapsto [n,x]$ (� ���������
���� ������� �������, ��� ���� � ������� �����������
$m$\� ����������). ����� ���������� �����~$X'$ ����� $m$\� ������
��������� � ������ $X$\� ������������ ��������. ����� �������,
��� $X'$~���������� � ��������� �� $m$\� ���������������.

����� ���������, ����� ��������, ��� ���������~$P$ �~$Q$
        \index{���������!$m$\� �������������}%
        \index{$m$\� ������������� ���������}%
�������� $m$\� \emph{��������������}, ����~$P\hm\lem Q$ �~$Q\hm\lem P$.
(����� ������, ��� ��� ������������� ���������
���������������.) ����� ������������� �������� ��������
        \index{$m$\� �������}%
$m$\� \emph{��������}. ����� �������, ����� �������, ��� ��
��� ������� ���������~$X$ ���������� ��������� $m$\� �������~$X'$.

����������� ������� ���������� $T$\�\emph{�������} (������� �������� �����
        \index{$T$\� �������}%
        \index{���������� �������}%
        \index{������� ��������������}%
\emph{������������ ���������} ��� \emph{��������� ��������������})
��� ������ $T$\� �������������
��������; ���������~$P$ �~$Q$ ��������
        \index{���������!$�$\� �������������}%
        \index{$T$\� ������������� ���������}%
        \index{��������������� �� ��������}%
$T$\� \emph{��������������}, ��� \emph{�������������� ��
��������}, ����~$P\hm\leqT Q$ �~$Q\hm\leqT P$, �� ���� ���� ������ ��
        \index{$A$\� ���������� ���������}%
        \index{���������!$A$\� ����������}%
�������� ��������� ������������ �������. ���� ���������~$P$ �~$Q$
������������ �� ��������, �� ����� $P$\� ���������� �������
��������� � ������� $Q$\� ���������� ������� (� �����
$P$\� ������������ �������� ��������� � ������� $Q$\� ������������
        \index{$A$\� ������������ ���������}%
        \index{���������!$A$\� ������������}%
        \index{$A$\� ���������� �������}%
        \index{�������!$A$\� ����������}%
��������). ����� ������� $T$\� �������, ����� �������, ���
$m$\� �������~$X'$ ������������ $T$\� �������� ���������~$X$ � ���
����� ����������
����������� ��������� ���� $T$\� �������� � ���������
���� $m$\� ��������. ��� ����������� �������� \emph{���������
        \index{������}%
        \index{�������� ������}%
������}; ��������� (������, $m$\� �������)~$X'$ ��������
\emph{�������} ��������� (������, $T$\� �������)~$X$.

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

\begin{problem}
        %
��������, ��� ����� ��� $m$\� ������
� ������~$\Sigma_n$ ��������� ���������
��������� (���������� ���������� �������������).
        %
\end{problem}

\begin{problem}
        %
��������, ��� ��� ������ ������������� ���������~$A$ �����
������� ����� �������������� �����~$\alpha$, ��� ��������� ����
������������ �����, �������~$\alpha$, ����� ����������� �
������������ �� �������� ���������~$A$.
        %
\end{problem}



������, �������, �������� ������ ������������� �� $T$\� ��������,
������ ţ ����������� $T$\� �������, ����������~$X'$ (��� �������,
��� ��� $T$\� ������������� ����� ������).

        \index{$\bfnull, \bfnull',\dots,\bfnull^{(n)}$}%
��� ����������� ���������
$T$\� �������: $\bfnull$ (�������, ����������
��� ���������� ���������), $\bfnull'$ (ţ ������, �������
        \index{������������ ������������ ���������}%
        \index{���������!������������ ������������}%
$m$\� ������� ������������� ������������� ���������; �� ţ ���
�������������), �����~$\bfnull''$ (������ �������
$\bfnull'$), $\bfnull'''$ � ��� �����;
������~$\bfnull^{(n+1)}\hm= (\bfnull^{(n)})'$.

\begin{theorem}
        \label{arithmetic-jump}%
        \index{$\Sigma_n$}%
��� �����~$n\hm\ge 1$ �����~$\Sigma_n$ ��������� � ������� ����
$\bfnull^{(n-1)}$\� ������������ ��������.
        %
\end{theorem}

(���� ��� �� ����� ��� ���~$n\hm=1$.)

\begin{proof}
       %
������� �������, ��� ��� $\Sigma_n$\� ��������� �����������
������������~$\bfnull^{(n-1)}$. ��� �������� ��������� ��~$n$.
���~$n\hm=1$ ��� ��������. ���������� ������ ������������
���������~$X$ ��~$\Sigma_2$. �� �����������,
        $$
x \in X \Leftrightarrow \exists y \forall z R(x,y,z),
        $$
��� $R$\� ���������� ��������. ��������~$\forall z R(x,y,z)$
����� ������������ ���������. ��� ��������� ���������
������������~$\bfnull'$, ��� ��� $m$\� �������� � $m$\� �������
������������� ���������. ������, � ���� ��������~$\forall z
R(x,y,z)$ ��������� ������������~$\bfnull'$. ������� ���
��������, ���������~$X$, ����������� ������������~$\bfnull'$.

���������� ����� ���������� � ��� �\'������~$n$. ����
$X$~�����������~$\Sigma_3$, ��
        $$
x \in X \Leftrightarrow \exists y R(x,y),
        $$
��� $R$~�����������~$\Pi_2$. ���������~$R$ �����������~$\Sigma_2$
(�� �����������), ������� $\bfnull'$\� �����������,
������� $\bfnull''$\� ���������, ������� ����~$R$ ����
$\bfnull''$\� ���������, � ��� ��������
$\bfnull''$\� �����������.

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

��� �������������� ������ �������� ��� ����������� ���������
�������� �������~$\Sigma_n$ �~$\Pi_n$. ���������� �����\� ������
���������� ��������� ���� �������� �������� ����������� �����.
        \index{$D_x$}%
        \index{�������� ���������!�����}%
        \index{���������!�������� ��������}%
��������� �����~$D_x$ �������� ��������� �����~$x$. ���
������������� ���������~$A$ ���������� ���������~$\opSubset(A)$
   \index{$\opSubset(A)$}%
���� �������� �����������~$A$,
������, ��������� ���� �� �������:
        $$
x \in \opSubset(A) \Leftrightarrow D_x \subset A.
        $$

\lemma{����� 1.} ���� ���������~$A$ �����������
������~$\Sigma_n$ [��� $\Pi_n$], �� ���������~$\opSubset(A)$ �����
����������� ������~$\Sigma_n$~[��������������~$\Pi_n$].

(����������� ���� ����� �������� ���������������� �
������~\ref{arithmetic-product}
����������� � ��������� $A\hm\times A$: ������ ��
������������� �� ����, � ������������ �������.)

�������������� �����. ����� ���������~$A$ �����������,
��������, ������~$\Sigma_3$:
        $$
x \in A \Leftrightarrow \exists y \forall z \exists t R(x,y,z,t),
        $$
��� $R$\� ���������� ��������. ����� ����� ��������
��������~$\{x_1,\dots,x_n\} \hm\subset A$
��������� �������:
\begin{multline*}
 \exists \langle y_1,\dots,y_n \rangle
 \forall \langle z_1,\dots,z_n \rangle
 \exists \langle t_1,\dots,t_n \rangle
[R(x_1,y_1,z_1,t_1) \land \ldots \\
\ldots\land R(x_n,y_n,z_n,t_n)]
\end{multline*}
��� ������� ���������� �������� �� �������� ����������� �����
(���������� �����), �� �� ����� �������� �� ������
���� �������� � �����\� ������ ���������� ���������. ��� ����
������� ��� ���������� ������� (��� �������� ��������� �������:
������������� ���������� �� ����� ���� ����� ���������� �����)
�������� ���������� ��������� ������� ��������,
������� ��� ������ ����� �������� $\Sigma_n$\� ���������.

(�� ����� ���� �� ��������� �ݣ ���� ��������� ����: ������
����� �������� �� ��������� ��������� ���������~$\{x_1,\dots,x_n\}$, �
���������
������� (������������� ������������������)~$\langle
x_1,\dots,x_n\rangle$. �� ������� �� ������ ��������� � ������
������\� �� �������, ����������� ��� ��� ��������, ��������,
��� ��� �������� ��� ���.)

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

\begin{problem}
        %
��������, ���
���� $A$~����������� ������~$\Sigma_n$~[$\Pi_n$], �� �
���������~$\Intersect(A)$ ������� �������� ��������,
�������������� �~$A$, ����������� ������~$\Sigma_n$ [$\Pi_n$].
        %
\end{problem}

\begin{problem}
        %
����� �������� $R(x,y)$ ��� ����������� ����� ����������� ������
$\Sigma_n$. ��������, ��� ��������
        $$
S(x)= (\forall y \le x)\, R(x,y)
        $$
����������� $\Sigma_n$. (������������ ������� ${(\forall y\le x)}$
�������� ��� \�� ��� ����~$y$, �� �������������~$x$\��.)
        %
\end{problem}

�������� � �����������, �� ���������� �������� ����� �����������:

\lemma{����� 2.} ���� $A$~����������� ������~$\Sigma_n$~[$\Pi_n$],
��
   \index{$\Disjoint(A)$}%
���������~$\Disjoint(A)$, ��������� �� ������� ��������
��������, �� �������������� �~$A$, �����������~$\Pi_n$~[$\Sigma_n$].

�������������� �����. �� ������������ �~$A$ �������� ����
������������� ���������� �~$A$, � �������� ���������������
���������� ������ � ���, ��� ���������� � ��������� ��
������~$\Sigma_n$~[$\Pi_n$] ����� � ������~$\Pi_n$~[$\Sigma_n$].
����� ��������.

������ �� ����� ������� � �������������� ���� �����, ��� ���
���������, ������������ ������������~$\bfnull^{(n-1)}$,
����������� ������~$\Sigma_n$. ��� ����� ������������ ���������
��~$n$.

���Σ� � ������� �������������� ������: ������ ���������,
������������ ������������~$\bfnull'$, ����� �~$\Sigma_2$?
(����� ����� ���� �� ��������� ��������
$\bfnull'$\� ������������, �����ģ���� ����, �� �� ������������
����������� �� ����� �����, ������� ������� � ��� �\'������~$n$.)

����, ����� ��������� ���������~$A$ �����������
������������~$\bfnull'$. ����� ��� ����������� ������������ ����������
������������� ���������~$B$, �� ���� ����������� ������������
������������������ �������~$b$ ���������~$B$. �������� �����������
���� ���� ��������
(�������~\ref{alternative-definition-relative-computability},
�.~\pageref{alternative-definition-relative-computability}),
��� ��������, ��� ���������� ������������
���������~$Q$ ��� ����~$\langle x,t\rangle$, ��� $x$\� �����,
� $t$\� �������, ��� ��������
        $$
x \in A \Leftrightarrow
    \exists t [\text{($\langle x,t\rangle \in Q$)
                              � ($b$~����������~$t$)}].
        $$
�������~$t$ ������������ ����� �������, ������̣���� �� ��������
        \index{�������}%
��������� � ����������� ��������~$0$ �~$1$. (���� �~$t$ ����
�����\� �� ������ ��������, �� �� �� ����� ���� ������
������������������ ������� ���������~$B$ � ���� �� ������.)
������� \�� $b$~����������~$t$\��\ � �������� ���������~$B$
������ ���: $B$~�������� ��������� ��� ����������, �� �������
$t$~��������� ��������~$1$, � �� ������������ � ���������� ���
����������, �� ������� $t$~��������� ��������~$0$. ������� ������
�������� ����� �������� � ����� �������� ��������; �����
������~$Q$ ���� ����������� ������������ ���������~$P$ �����
����~$\langle x,u,v \rangle$ � �������� ���:
\begin{multline*}
x \in A \Leftrightarrow
    \exists u\exists v [\text{($\langle x,u,v\rangle \in P$)
                              � ($D_u$~���������� �~$B$)}\\
                              \text{� ($D_v$~�� ������������ �~$B$)}].
\end{multline*}
������ ������ \�� $D_u$~���������� �~$B$\��\ ������� \�� $u \hm\in
\opSubset(B)$\��, � ������ \�� $D_v$~��
������������ �~$B$\��\ ������� \�� $v \hm\in
\Disjoint(B)$\��. �������� ��������, ��� ��� ���
��������, �����Σ���� ������~\�� �\��\ � ������ �����,
����������� ������~$\Sigma_2$ � ���� ������� �������. ������,
������ ��� ����������� ������~$\Sigma_1$, ��� ��� $P$ �~$B$
����������� (��� ������� �������� ��������� �����~1). ������ ��
����������� ������~$\Pi_1$ �� �����~2. ������� �� ����������
����������� ������~$\Sigma_2$, � �������� ��������
(��������~$\exists u\exists v$) �� ������� �� ������� ����� ������.
������~$n\hm=2$ ��������.

�����, ���� �����\� �� ���������~$A$ �����������
������������~$\bfnull''$, �� �� ����������� ��� ��������, ��� ���
����������� ������������ ����������~$B$, ������� �����������
������������~$\bfnull'$ � ������ ����� �~$\Sigma_2$.
����� ����� ��� ����������� �������� ����� ��� �� �� �������
��~$1$. ���������� ����������� � ��� ��������� ��������~$n$.
        %
\end{proof}

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

\begin{theorem}
        \label{arithmetic-decidable}%
����������� �������~$\Sigma_n \hm\cap \Pi_n$ ��������� � �������
���������� ������������~$\bfnull^{(n-1)}$ ��������.
        %
\end{theorem}

\begin{proof}
        %
� ����� ����, ���������������� �������~�����
        \index{����� �������}%
        \index{�������!�����}%
(�������~\ref{post-theorem},
�.~\pageref{post-theorem})
        %
����������, ���
��������� ��������� �������� $X$\� ���������� ����� � ������
�����, ����� ��� � ��� ���������� $X$\� ����������� (����� $X$\�
������������ ������).
        %
\end{proof}

\begin{theorem}
        \label{arithmetic-hierarchy-strict}%
�����~$\Sigma_n \hm\cup \Pi_n$ �������� ����������� �������������
������~$\Sigma_{n+1} \hm\cap \Pi_{n+1}$.
        %
\end{theorem}

\begin{proof}
        %
��������, ��� �����~$\bfnull^{(n)}$. ���\� �������
���������~$X$, ����������� $m$\� ������ � ������
$\bfnull^{(n-1)}$\� ������������ ��������. ���������
$X$~�������� $m$\� ������ � ��������� ������, ��� ��
$\bfnull^{(n-1)}$\� ���������, �� ���� ��� ���������� ��
�������� $\bfnull^{(n-1)}$\� ������������.

������, �� ���������� ������ ��� ������� $X$~�����������
������~$\Sigma_n$, � ��� ����������\� ���. ��������, ���������� �~$X$
�����������~$\Pi_n$, �� ��~$\Sigma_n$. ���������� ������ \��
����������\��\ ���������~$X$ � ��� �����������, \�� ���������
        $$
\{2n \mid n \in X\} \cup \{2n+1 \mid n \notin X\}.
        $$
� ����� ��������� $m$\� �������� ���~$X$, ��� � ��� ����������,
������� ��� �� ����� ������������ ��~$\Sigma_n$, ��~$\Pi_n$. �
������ �������, ���, ��������, ��������� ������������~$X$,
������� �� ���������� ������� ����������� �~$\Sigma_{n+1}$, �~$\Pi_{n+1}$.
        %
\end{proof}

\section{������������� �������� � ��������}\label{chapt08-4}

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

�� ��� ��������, ��� ��������� ���� ������� ���� ������� � ��������
�������� ����������� �����������, �� ���� �����������
������~$\Sigma_1$. �������������, ��� ����������, ��������� ����
������� ����� �� ������̣���� �������, ����������� ������~$\Pi_1$.
(������~$\Sigma_1$ ��� ������������ �� �����, ��� ���
        \index{�������!����������\� �����}%
        \index{����������\� ����� �������}%
        \glossary{���������@\���������}%
        \glossary{����@\����}%
�����������, ��.~�������~\ref{uspensky-rice}, �.~\pageref{uspensky-rice}.)

\begin{problem}
        %
��������, ��� ��������� ������� ����� �� ������̣����
        \index{����� �� ������̣���� �������}%
        \index{�������!����� �� ������̣����}%
������� � ����� ������� ��������� �������� $m$\� ������
� ������~$\Pi_1$ ����������.
        %
\end{problem}

� ��� ����� ������� � ������� ������ �������? ��������, ���
        \index{�����!�������}%
        \index{��������� �������}%
����� ������� � ��������� ������� ������������ ������� �������?
�����������, ����� �������� � ��������� ������ ������ �����
�� ���� ������.

\begin{theorem}
        \label{number-set}%
(\textsf{�})~����� $U$\� ���������� ������������� ������� ��� ������ ����������
�������. ����� ��������� ���~$n$, ��� ������� $U_n$~����� ����������
� ������������ �����~$0$, ����������� ������~$\Pi_2$.
        \index{$\Pi_2$}%
        %
(\textsf{�})~����� $U$\� ������� ������������� �������. ����� ��������� ���������
�������� $m$\� ������ � ������~$\Pi_2$.
        %
\end{theorem}

�������, ��� ���������� ��������� � ������~(�) �����������: �
����������� ��������� (��.~�.~\pageref{friedberg-numbering}) ���
��������� ������� �� ������������� ������.

\begin{proof}
        %
������������ ��� �������� �����~$n$ ����� �������� ���: ���
������~$k$ ���ģ��� �����~$t$, ��� \textsl{�� $t$~�����
���������� ��������~$U(n,k)$ ���������� � ���� ���������~$0$}.
���������� ����� �������� ���������� ���������, � �����
��� ����� ��� �������� ��� ��� ������� ����. ����, �����~(�)
�������.

������� �����������~(�). ����� ������� ������������ ���������~$P$ ��
������~$\Pi_2$. ��� ����
        $$
x \in P \Leftrightarrow \forall y \exists z R(x,y,z),
        $$
��� $R$\� ��������� ���������� ��������. ���������� ������
�������~$S(x,y)$, ����������� ����� ����������: ��������� ���
�����, ���� �����~$z$, ��� ��������~$R(x,y,z)$; ��� ������ (�
����) ����� ����� �������, ������ �� �����~$0$. ����, ��� $x$\�
�� �������~$S_x$ �������~$S$ ����� ������������ ������� ��������
� ��� � ������ ��� ������, �����~$x\hm\in P$. �������� ��������
��������� � ������� �������~$s$, ��� �������~$U_{s(x)}\hm=S_x$.
��� � ����� �������~$P$ � ��������� ���� ������� ������������
������� �������.
        %
\end{proof}

��� ����� ������� ��� ������ �������? ��� ����� ����������
������������� �������~$U$ � ����� ���������� �������~$f$
��������� ���� $U$\� ������� �������~$f$ ��������
$\Pi_2$\� ����������. ����� ���� ����� ������� ����: ��������~$U_m\hm=U_n$
(�����~$m$ �~$n$ �������� �������� ����� � ��� ��
�������) �������� $\Pi_2$\� ��������� ����~$\langle m,n\rangle$,
������� ��� ����� ����� ��� ������� (\�� ��������� ����
������� ����� ���������� �������) �������� $\Pi_2$\� ����������. �
����� ����, ��������~$U_m\hm=U_n$ ����� �������������� ���: \�� ���
������~$x$ �~$t_1$ ���ģ��� �����~$t_2$, ��� \textsl{����
����������~$U(m,x)$ ����������� �� $t_1$~�����, �� ����������~$U(n,x)$
����������� �� $t_2$~����� � ��� �� �����������, �
��������}\��. ���������� ����� ���������, � �� �ţ
����� $\Pi_2$\� �������.

����� ���� ������, ��� ����� ������� ��������� ������� ��������
$\Pi_2$\� ������: ��� ������� � ����������� �������� �����������.
���� ������� ����������� ������� �������, �� ��������� ���� ţ
������� �������� $\bfnull'$\� ���������� (� ������ �� $\Pi_2$\� ������):
���� ������ ���
�������� ���������, ����� ���������, ��� ������� ����������
�����, ��� ��� ������ ���� ���������� (����� ���� ���������, ���
�������� ���������), � ����� ���������, ��� �� � ����� ��
���������� ����� ��� �� ���������� (������� ������ ����� ���
������� ��������� ���������, � ������� ������� ����������,
�������� ������������ ��������� � ������ ��� ���������� �����
���� ��������� � ������� $\bfnull'$\� �������).

���� �� ������� ����� ����������� ������� �����������, ��
���������� ����������� ���������� ���������, �� ���� ������
�������� ������� ����������
(������~\ref{infinite-recursive-subset},
�.~\pageref{infinite-recursive-subset}). ����� ����� ������������
�� �������� �� �� �����������, ��� � ��� ������� �������, ��
������ ������ ����� ������������ (�� ������ ��������� ��� ����).

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

\begin{problem}
        %
��������, ��� ��������� ���� ������� ���� �����
������̣���� ������� (� ������� ���������) ��������
$\Pi_2$\� ������.
        %
\end{problem}

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

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

� ����� �.\,�������� (\cite{rogers}, �������� 14.8) ���������
����� ����������� ��������� ���� ��� ������ ������ �������
���������� ������� � ������������ ��������. ��������, ��� ������
$m$\� ������� ��������� $K$ ��������� ���� ��� ������� ��������
$\Pi_2$\� ������. (����� � �����, ������ � �������, �� ����� �
���� ������� ��������� ������������ ��������.) ��������� �������
���� �������� �������� �������� $\Sigma_2$\� ������. ���������
������� ��������, ���������� ���� �� ����
����� ������������ ���������, �������� $\Sigma_3$\� ������.
��������� ������� ���� ���������� �������� ��������
$\Sigma_3$\� ������. ��������� ������� ���� �������� � ���������
������������ �������� $\Sigma_3$\� ������.

\begin{problem}
        %
�������� ������������� ����������� (��� �������� ��
�������������� � ����� ��������~\cite{rogers}).
        %
\end{problem}

\begin{problem}
        %
���������� ������� $\exists^{\infty} x$, ������� �������� ���
\�� ���������� ���������� �����~$x$, ��� �������\��. ��������,
��� ��� �������� �� ������ $\Pi_2$ (� ������ ���) ����������� �
����
       $$\exists^{\infty}x\,\text{(���������� ��������)}$$
� ��� ��� �������� �� ������ $\Sigma_3$ (� ������ ���)
����������� � ����
       $$\exists^{\infty}x\,\forall y\,\text{(���������� ��������)}.$$
        %
(����������� ����������� ����� � ��� ������� �������, ��.~�������~XVIII
� �������~14.8 �����~\cite{rogers}.)
\end{problem}
