\chapter{�������� ������� ���������}\label{chapt04}

\section{��������� �������}\label{chapt04-1}

���Σ� � ������ �������. ���������� ��������� ������� ����� ��
������̣���� �������\index{��������� �������!����� ��
������̣���� �������} ��� �����\� ���� ������� ���������. ����� ��
��� ���������? ������� �������, ����� �� �� ������ ������� �
������� ��������� ����������, �������� �� ��� ������� ����� ��
������̣����?

������ ��� �������� �� ���� ������, �������, ��� ����� ��
������� �� ����, ����� ������� ���������\index{������� (ǣ������) ���������}
    \index{���������!������� (ǣ������)}%
�������. � ����� ����,
���� ���� ��� ������ ������� ���������, �� ���, ��� �������, \��
��������\index{���������� ���������}\��\ ���� � �����: �� ������ �������
� ����� ��������� �����
�������������� �������� ����� ��� �� ������� � ������ ���������.
���� �� � ����� ��������� ����� ���� �� ���������
\�� �����\� ��\� ������̣������\��\ �������, ��
��� ����� ���� �� ������ � �
������ (�������� \�� ������� ��������\��).

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

\begin{theorem}
        %
����� $U$\� ������������ ������� ������������� �������.
����� ��������� ���~$n$, ��� ������� �������~$U_n$ ��������
����� �� ������̣����, �����������.
        %
\end{theorem}

\begin{proof}
        %
���������� �����, ���������� \�� ����\'�����\index{����\'����}\��\� �������,
��� ���� �� ��� ��������� ���� ����������, �� � ������ �����
������������ ��������� ���� �� ����������. (���, ��� �� �����,
�������.)

����� $K$\� ������������ ������������ ������������
���������. ���������� �����
        ����������
�������~$V$ ���� ����������:
        $$
V(n,x)= \left\{
           \begin{aligned}
             &\text{$0$, ���� $n\in K$,}\\
             &\text{�� ����������, ���� $n\notin K$.}
           \end{aligned}
        \right.
        $$
��� �����, ������ �������� ���� ������� ��������, � ��� ��
�������� ��������� � ���������������������� ��������
���������~$K$ �� ������� ���������. ��������, ��� ������� ����� �������
���� �����: ���~$n\hm\in K$ �������~$V_n$ �������� �������
��������, ���~$n\hm\notin K$\� ����� �� ������̣���� ��������.

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

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

����� ����, ����� ��������, ��� ��������� ������� ����� ��
������̣���� ������� �� ������ �� ���������, �� � ��
�����������. � ����� ����, ��� ����������\� ��������� ����
������� ���� ������� � �������� �������� �����������\�
�����������. (���
����� ��� ����� ���������� ���������, � �� ������ ��� �������:
����������� ��������~$U(n,x)$ ��� ����~$n$ �~$x$, �� �����
�������� ��~$n$, ��� ������� ������������~$x$, ��� �������
$U(n,x)$~����������.) � ���� ���������� ������������� ���������
�����������, �� ���� ��������� ������������� (�� ������� �����%
\index{�������!�����}, �.~\pageref{post-theorem}).

����������� � ����� ����� �����������, ���������� ������
�������� ����������\�  �����\index{�������!����������\� �����}%
\index{����������\� ����� �������}.
��������� ����� ���� ����������
������� (������ ���������) �����~$\calF$.

\begin{theorem}
        \label{uspensky-rice}%
����� $\calA\hm\subset\calF$\� ������������
������������� �������� ���������� ������� (���������������
��������, ��� ���� ��� �������, ��� ���������������, ��� �
�������, ��� �� ���������������, �� ���� ��� ���������
$\calA$~������� � �� ��������� �� ����~$\calF$). ����� $U$\�
������� ������������� �������. ����� �� ���������� ���������,
������� �� $U$\� ������ ���������� ������� �������� ��, ��������
�� ��� ���������~$\calA$. ������� �������, ��������� $\{ n
\mid U_{n}\hm\in \calA\}$ �����������.
        %
\end{theorem}

\begin{proof}
        %
���������, ����������� �� ����� �� ������̣���� �������
(��������� ţ~$\zeta$) ������~$\calA$, � ����ͣ�
������������ �������~$\xi$ \�� � ������ �������\��\
(����~$\zeta\hm\in\calA$, ��~$\xi\hm\notin\calA$ � ��������).

����� ��������� ��� ������, �� ������ ������ ������� �������
����ͣ� �������~$\xi$: �������
        $$
V(n,x)= \left\{
           \begin{aligned}
             &\text{$\xi(x)$, ���� $n\in K$,}\\
             &\text{�� ����������, ���� $n\notin K$.}
           \end{aligned}
        \right.
        $$
��� � ������, �������~$V$ ����� ���������� (��� ������~$n$ �~$x$
�� ������� ���������~$n$ � ���������~$K$, �����
���� ���������~$\xi(x)$). ���~$n\in K$ �������~$V_n$
��������� �~$\xi$, ���~$n\hm\notin K$\� �~$\zeta$. �����
�������, �������� ��������~$V_{n}\hm\in\calA$ (���� �� ��� �����
���� ������� ������� ����������� �������), ����� ���� �� ������,
����������� �� �����~$n$ ���������~$K$ ��� ���.
        %
\end{proof}

��������� ����������� ����� �������������� �������� ���
���������������� (� ����� ������� ��~$\calA$ �� ��ң�
����� �� ������̣���� �������, � ������ �������\� �����). ���
����� ������������ �������. �������, ��� ����
��������~$\calA$ ����� ������������ �� $U$\� �������, �� ����� ���
����������������
������������ ���������~$P$ �~$Q$ ��������
���������� ����������.
������� �����\� ������ ��� �������~$\xi$ �~$\eta$, �����������
\�� �� ������ �������\��\ ��~$\calA$. ���������� �������
        $$
V(n,x)= \left\{
           \begin{aligned}
             &\text{$\xi(x)$, ���� $n\in P$,}\\
             &\text{$\eta(x)$, ���� $n\in Q$,}\\
             &\text{�� ����������, ���� $n\notin P\cup Q$.}
           \end{aligned}
        \right.
        $$
��� ������� ���������: ��� ��������~$n$ �~$x$ �������,
����~$n$ �������� ���� �~$P$, ���� �~$Q$, ����� ���� ���������
���������� ��������������~$\xi(x)$ ���~$\eta(x)$.

����~$n\hm\in P$, �� $V_n$~��������� �~$\xi$; ����~$n\hm\in Q$, ��
$V_n$~��������� �~$\eta$. �������, ��������, ����������� ��~$V_n$
������~$\calA$, �� ����� �� ��������� ��������~$P$
��~$Q$. �������� ������������, ������� � ��������� ���� �����
������������ ������� ��������������.

������ ������� �������������� ����������, ��� ����� ���������
�������� ���� �������: ��� ����� ��������� ����������
�������~$\varphi$ �~$\psi$ � ����� ������� ������������� �������~$U$
��������� ���� $U$\� ������� �������~$\varphi$ � �������~$\psi$ ��
�������� ���������� ����������. (�������, ��� ��� ��������� ��
�����������, ��� �� ������������ ������.)

������ ����� ������� ������ ���������� ������������� �������, ��
���������� �������\index{������������� �������!���������}.
���������� ������� ���, ����� ����� ��
������̣���� ������� ����� ������������ �����. ��� ��������.
����� $U(n,x)$\� ������������
        ����������
������������� �������.
���������� ���������~$D$ ���� $U$\� ������� ���� �������
� �������� �������� �����������.
��� �� ��� ��������, ��� ���������
�����������. ���������� ����� ������̣����
        ����������
�������~$d$, ���
�������������: $D \hm=\{d(0),d(1),\dots\}$.
������ ���������� �������~$V(i,x)$, ��� ������� $V(0,x)$~��
���������� �� ��� �����~$x$, � $V(i+1,x)\hm=U(d(i),x)$. �������
�������, �������~$V_0$ ����� �� ����������, � �������~$V_{i+1}$
��������� �~$U_{d(i)}$. ����� ������, ��� �������~$V$ ���������;
��� ������������ �� ����������, � ������������ $V$\� ������� �����
�� ������̣���� ������� �������� �����~$0$.

�� ����� ���� ���������� � ����� ������������ ���������: ���
������� ��������, ����� ��������� ������������� ����������
�������, ���
������� ������ ���������� ������� ����� ����� ����� ���� �����.
        \label{friedberg-numbering}%
��������������� ��������� �������� \emph{������������};
        \index{���������!�����������}%
        \index{����������� ���������}%
��������, ��� �� ����� ���� ��������.
��������
����������������: ����� ����������� ����� ���� ����������������,
� ������� ������ ��������������� ������ ����� ������
������������ �������. (�������������� ���� ������� ������ �
�� ����������, �� ������� ����� ��� ���� � ������ �.\,�.\,��������
\�� ��������� � ����������� �������\��~\cite{maltsev}.)
        %
%����� ��� �� ������� ����� � ������ ������ ����� ���...
        %
����������� ����������� ����� � ��� ���������
������������ ��������.

\section{����� ������ ������ �������}\label{chapt04-2}

������� ����������\� ����� ����������, ��� � ������� ���������
��������� �������\index{��������� �������} ����� ���������� �������
����������� � ������ ����������. ������ �� �������
����� ������� ����:
�� ������ ����� ������� � ������� ��������� ����� ��������������
�������� ������� ������ ������ ������� ��� �� �������. ���������
��� ����� ��������, ��������, ���:

\begin{theorem}
        \label{many-numbers}%
����� $U$\� ������� ������������� �������. ����� ����������
����� ������̣���� �������~$g$ ���� ����������
� ����� ���������:
��� ������~$i$ ����� $g(i,0),g(i,1),\dots$ ��������
���������� $U$\� �������� �������~$U_i$.
        %
\end{theorem}

%\begin{proof}
$\lhd$\
        %
���� �����: �� �������� ������ ������� ����������������, �
������� �������� �������~$U_i$ ����� ���������� ����� ��������.
�����, ��������� ���, ��� ������� $U$\� �������, ����� \��
�������������\��\ ��� ��������� � �������� $U$\� ������
������������ ��� �������. ��� ���� �� ������ ����������� ����, �����
�������������, ��� ��������� ���������� ����� ������ �������
(������ ������, ������ ��������� ����� ���������� ����� �������).
�������� ��� ����� ��������. ����� $h$\� ������������
�������. �������, ��� ���������� ��������,
������������ ���������� ����� ��������� $U$\� ������� �������~$h$.
(� ������� ������������, ��� ��� ����� ������� �� ������ ���
���������� �������~$h$, �� � ��� ���� �������~$U_i$, ���
�������, \�� ���������� ��~$i$\��, �� �������� ������� ��� ���.)

����� $P$\� ������������ ������������ ���������.
����������
        ����������
�������
        $$
V(n,x)= \left\{
           \begin{aligned}
             & h(x), \text{ ���� $n\in P$,}\\
             &\text{�� ����������, ���� $n\notin P$.}
           \end{aligned}
        \right.
        $$
����� �������~$V_n$ ����������� ����� ���: ����~$n\hm\in P$,
��~$V_n\hm=h$; ����~$n\hm\notin P$, ��~$V_n$\� ����� �� ������̣����
�������, ������� �� ��������� �����~$\zeta$. ����� ���� �������,
���~$h\hm\ne\zeta$ (���~$h\hm=\zeta$ ��� ����������� �� ��������
� ��� ����������� ���� ����� �������).

��� ��� $U$\� ������� ������������� �������, ��
���������� ����������~$s$, ����������� $V$\� ������ � $U$\� ������.
��� ����
        %
\vspace*{-0.5ex}
        %
{
\begin{itemize}
\addtolength{\itemsep}{-0.7ex}
       \item
$n\hm\in P \hm\Rightarrow U_{s(n)}\hm=V_n\hm=h$;
       \item
$n\hm\notin P \hm\Rightarrow U_{s(n)}\hm=V_n\hm=\zeta$.
        %
\end{itemize}
}
        %
\vspace*{-0.5ex}
        %
����� �������, ���� $p(0),p(1),\dots$\� ����������
������������ ���������~$P$, �� ��� ����� $s(p(0)),s(p(1)),\dots$
����� $U$\� �������� �������~$h$. �������, ��� ����� ���� �����
���������� ����� ��������� (� ������ ����� ��������� �� ���� ��
������, ���� �� ����������� �����, �ݣ �� ��������������, �����
�������~$h$).

����� ��� �� ���, � ���������~$X\hm=\{s(n)\mid n\hm\in P\}$ �������.
����� $X$~���������.
����~$n\hm\in P$, ��~$s(n)\hm\in X$ �� ����������; ����~$n\hm\notin P$,
�� $s(n)$\� ����� �������~$\zeta$ � ������ �� �����
������������~$X$ (��������, ���~$h\hm\ne\zeta$).
�������������, $n\hm\in P$ ����������� $s(n)\hm\in X$, � ������
�� ������������ $X$ ������� ������������ $P$, ��� ������������
�������������.

��� �����������, ������, �� ��������, ���� �������~$h$
����� �� ����������. ���� �����
$s(p(0)),s(p(1)),\dots$ ��\� �������� ����� ��������~$h$,
����� �� ����������� ���, ��� ����� ��� ���������� �����
���������.
� ���� ������
�������� ���� ������ � ���������� ����� ����������
�������~$\xi$, �������� ��~$\zeta$ (��������, ������������
�������). ���������� ��� ������������ �����������\index{������������
����������� ���������} ���������~$P$ �~$Q$ �
���������� �������
        %
\vspace*{-0.4ex}
        %
        $$
V(n,x)= \left\{
           \begin{aligned}
            &\text{$h(x)$, ���� $n\in P$,}\\
            &\text{$\xi(x)$, ���� $n\in Q$,}\\
            &\text{�� ����������, ���� $n\notin P\cup Q$.}
           \end{aligned}
        \right.
        $$
����� $s$\� ����������, ����������� $V$\� ������ � $U$\� ������.
�����
        %
\vspace{-0.4ex}
        %
{
\begin{itemize}
\addtolength{\itemsep}{-0.7ex}
       \item
$n\hm\in P \hm\Rightarrow U_{s(n)}\hm=h$;\hfil
       \item
$n\hm\in Q \hm\Rightarrow U_{s(n)}\hm=\xi$;\hfil
       \item
$n\hm\notin P \hm\cup Q \hm\Rightarrow U_{s(n)}\hm=\zeta$.
        %
\end{itemize}
}
        %
        %
\vspace{-0.4ex}
        %
��� � ������, ����� $s(p(0)),s(p(1)),\dots$ ����� ��������
�������~$h$. �������, ��� ����~$h\hm\ne \xi$, �� ���������~$X$ ����� �����
����������� (� ������ ����������). � ����� ����, ����
$X$~���������, �� �� ����� ��������~$P$ ��~$Q$ ����������
����������. ������, ��������� $\{n\mid s(n)\hm\in X\}$ ��������~$P$
(�� ����������) � �� ������������ �~$Q$ (��������� ���~$n\hm\in Q$
�����~$s(n)$ ����� ������� �������~$\xi$ � ������ �� �����
������ �~$X$).

����� �������, � ��� ���� ��� �����������, ����������� ��������
������ ������ �������� �������~$h$. ������ �� ��� ��������
������� (���� ���������� ����� ����� �������), ���� $h$~���� ��
���\� �� ����������; ������ �������� ��������� ��� ����� ��
������̣����~$h$. ����� ��� ������ ���� �������~$h$ � ������� ��
��������, �������� �� ��� ����� �� ������̣���� ��� ���. ���
�����? ����� ����� ��������� ����������� ��� �����������, ����
���� �� ��� �� ���� ��� ��������� ����� �����\� �� �����, ��� ��
������� ���� ���� �� ����������� ������� ���������, ���� � ��
�����, �����.

��� ��������� ��� �������� ����������� ���������� ��~$i$.
��������� ������, ���� ����������� ���. ���������� ���
        ����������
�������~$V_1$ �~$V_2$ ���� ����������, ������̣���� �������������
\begin{align*}
        V_1([i,n],x) & =
           \left\{
              \begin{aligned}
                {}&\text{$U(i,x)$}, \text{ ���� $n\in P$,}\\
                {}&\text{�� ����������}, \text{ ���� $n\notin P$,}\\
              \end{aligned}
           \right.\\[1ex]
        V_2([i,n],x) & =
           \left\{
              \begin{aligned}
                {}&\text{$U(i,x)$}, \text{ ���� $n\in P$,}\\
                {}&\text{$0$}, \text{ ���� $n\in Q$,}\\
                {}&\text{�� ����������},\text{ ���� $n\notin P\cup Q$}\\
              \end{aligned}
           \right.
\end{align*}
($P$ � $Q$\� ������������� ������������ ����������� ���������,
$[u,v]$\� ����� ����~$\langle u,v\rangle$ � ������������� ����������
��������� ���). ��������� $U$\� ������� ������������� �������, �����
����� �����
        ���������� ����� ������̣����
�������~$s_1$ �~$s_2$, ���
    $V_1([i,n],x)\hm=U(s_1([i,n]),x)$
�
    $V_2([i,n],x)\hm=U(s_2([i,n]),x)$.
����� $p$\� ����� ������̣���� ������� ������ ���������, ��� �������
$P\hm=\{p(0),p(1),\dots\}$. ������� �������~$g$ ����� ���������� ���:
$g(i,k)$~���� $k$\� �� (��� �ޣ�� ����������) ����� � ������������������
        %
\begin{multline*}
s_1([i,p(0)]),
s_2([i,p(0)]),
s_1([i,p(1)]),\\
s_2([i,p(1)]),
s_1([i,p(2)]),
s_2([i,p(2)]),\ldots\ \rhd
\end{multline*}
        %
%\end{proof}

\section{���������� ������� ���������}\label{chapt03-4}%
        \index{����������!������� ���������}

���������� ������ ��� ����������� � ��������� ����� �������
������������ ��� �������������� ������� ��������\index{�������!��������}%
        \index{�������� �������}%
\glossary{�������@\�������} �� ����������� ������� (ǣ�������) ���������.
��� ţ ������������:

\begin{theorem}
        \label{rogers-theorem}%
����� $U_1$ �~$U_2$\� ��� ������� ������������� ������� ���
������ ���������� ������� ������ ���������. ����� ���������� ���
����� ������̣���� ������� �������� ����������
�������~$s_{12}$ �~$s_{21}$, ��� �������
        $$
U_1(n,x)=U_2(s_{12}(n),x) \quad \text{�} \quad
U_2(n,x)=U_1(s_{21}(n),x)
        $$
��� �����~$n$ �~$x$.
        %
\end{theorem}

��� ������� ����������, ��� �����������, �������� ���� �������
��������� � ������ � ��������, ����� ������� ������� ���������,
��� ��� ����� ��� ������� ��������� ���������� ���� ����������
������������� �������. (�������, ��� ����������� ����������
�������~\ref{many-numbers}
�������� ���������� ������� �� ����������� �������
���������. � ����� ����, ��� ��������� ������� ���������\� ��������,
��� ���������, ������������ �� ������ ����������������,\� ����
������� �������� ������� ������ ����� ������� ��� �� �������,
������� � ���� ����������� ����� ������ ���� � ��� ����� ������
������� ���������.)

\begin{proof}
        %
�� ����� ����������� �������� ��� ��, ��� � ��� ��������������
����������� �ޣ���� ������� ����� ������������� �������� ���
������� � ���������� ���������. ���������� ������� �������
���������� �� �����. �� $k$\� � ���� �������� ���������
������� ����������� ������������
        $$
a_1 \leftrightarrow b_1,
a_2 \leftrightarrow b_2, \dots,
a_k \leftrightarrow b_k
        $$
����� ����� ��������� $k$\� ����������� ��������������
������������ ����. ��� ���� ��� �������~$i$ �����~$a_i$ �~$b_i$
�������� �������� ����� � ��� �� �������, ������ � ������
���������� ($a_i$\� ������������~$U_1$, � $b_i$\�
������������~$U_2$).

�� ������ ���� ���������� �� ��������� ����� ����~$a_k
\hm\leftrightarrow b_k$ � ����������� ���������� ��������. ��� ����
���������� � ����� ������ �� ������� ��� ����������� �����. ���
����� �� ������� ������� ������� ����������� ������������, � ���
����� ����������, ��� ���� ����������� ���������.

����, ��� �� ��������� ����� ����? �� ޣ���� ����� �� ��ң�
���������� ����������� �����~$u$, �� �������� � ����� �������
������������ (�� ������������� �����~$a_i$). ��� ��������
$U_1$\� ������� ��������� �������. ��������� ���������~$U_2$
�������, �� ����� �������� ��������� $U_2$\� ����� ��� �� �������.
��������� ���~$v$. ���� $v$~�� ����������� �����~$b_i$, ����
�������: �� ��������� ���� $u \hm\leftrightarrow v$ � ������
������������. ���� �����������, �� ����������
��������~\ref{many-numbers} � �������� ������ $U_2$\� ������
��� �� ������� �� ���
���, ���� ����� ��� �� �������� ������, �ݣ �� ��������������
�����~$b_i$.

�� ��ޣ���� ����� �� ��������� ����������� �������, ��
�������� � ����������� �����, �� �������������� �����~$b_i$.
        %
\end{proof}

��������� ���
�������������
(������� �� ������� ������������ ���أ���):
���������, ������, �������\index{�������} � ��\index{��} ����� �������
�������� �����������, �� �� ���������� ������� ���������� ��
������ �����������\index{����������} �� ������� � �� � ��������, � �������
��������. (�������, �������� ����� �������������� ��� ���� ��
������������, ��������� � ������� � �� � ��������� �����
��������� �����������, ������� ������� ������ �������������
��������.)

����������� ������� ����� � ��� ������� ��������� ������������
��������: ����� ��� ����� ��������� ��������� (���������� ����������
������������� �������). �������������� ����� ����������
����������; ������� ����� ��������, ��� � ������� ��������� ��
������ ������ ����� �������������� �������� ������� ������ �������
���� �� ���������. ��� ���� ����������� ��� �������\� ����
������� ��� ���� ��������, ����� �������, ������ ��� �������.

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

\section{������������ �������� �������}\label{chapt03-5}%
        \index{������������ �������� �������}

�� ��� ������ (�������~\ref{uspensky-rice}), ��� �������
(�������������) �������� ������� �� �������� �����������. ��
��������� �������� ������������� (� ��� ������, ��� ���������
���� ������� ���� �������, ���������� ���� ���������,
�����������). ��������, ������ �������� ������� \�� ���� ���\� ��
������̣����\��\ (��.~����). ������ ������:
�������� \�� $f(19)$~���������� � �����~$98$\��.

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

����� �������� \emph{��������}\index{�������} ������� � ������������
����������� � ����������, ������� �������� ������� �����������.
������� �������, ������� ���� �������� ������ ���
$\langle\text{��������},\text{��������}\rangle$; ������� �����
������������� ��� �������������� ������� (���������� ���������
�������, ������������ ������� \���). ��� ��������� �������� �
���������� ��������� ��������, ������������ ��������� �������� \���

������� �������~$t$ ������������� �������� ������� \��
���������� ���� �������\index{����������� �������}\��,
�� ���� ���������~$\Gamma(t)$\index{$\Gamma(t)$} ����
(����������) �������, ������� �������� �������������~$t$.
(������� � �������, ��� ���������~$\Gamma(t)$ �������� ����
��������� �� ��������� ���� ���������� �������.) �����
���������, ��� ��� ������~$t$ � ��� ����� ����������
���������~$U$ ��������� ���� ������� ���� ������� ��~$\Gamma(t)$ �����������.
� ����� ����, ���� ����������� ��������� ��������~$U_n(x)$ ���
����~$n$ �~$x$; ��� ������ ����������� ������ ���������
����������, ���~$U_n\hm\in \Gamma(t)$, ���� ��������~$n$. (����
$U_n\hm\in \Gamma(t)$, �� ��� ����������� �� �������� ����, ��� ���
������� ����������� �������~$t$ �������.)

����� $T$\� ������������ ��������� ��������. �����~$\Gamma(T)$%
\index{$\Gamma(T)$}
��������� ��������� ���� ���������� �������, ������� ����������
���� �� ���� ������� ��~$T$, �� ���� ����������� ��������~$\Gamma(t)$
�� ����~$t\hm\in T$. ������ �� ����� ��������������
��������� ���������:

\begin{theorem}
        \label{enumerable-families}%
(\textsf{�})~����� $T$\� ������������ ������������ ��������� ��������,
� $U$\� ���������� ������������� ������� ��� ������
���������� ������� ������ ���������. ����� ��������� ����
$U$\� ������� ���� ������� ��~$\Gamma(T)$ �����������.
        %
(\textsf{�})~����� $U$\� ������� ������������� ������� (��� ������
���������� ������� ������ ���������). ����� $\calG$\�
��������� ������������ ����� ������. ���� ��������� $\{ n \mid
U_n \hm\in \calG\}$ ���� $U$\� ������� ���� ������� �� ������
$\calG$ �����������, ��~$\calG\hm=\Gamma(T)$ ���
���������� ������������� ��������� ��������~$T$.
        %
\end{theorem}

��������, ������������� ���� ����� ���\� �� ��\-��\-��\-̣�\-��� �������
������������� ��������� ���� �������� �������� (� �����, ������,
��������� ���� �������� � �������������� �������� �����������).

\begin{proof}
        %
�����~(�) ����������� ������������ �����: ���� ����������� ���������
��� ��������~$U(n,x)$ � ����������� ��� ������� ��~$T$; ���
������ ��������������, ��� �����\� �� �� �������~$U_n$ ��������
������������ ������\� �� ������� ��~$T$, ������� ��������~$n$.

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

\lemma{����� 1.} ���� ���������� �������~$h$ �������� ������������
���������� �������~$g$, ������������� ������~$\calG$, �� �
�������~$h$ ����������� ������~$\calG$.

\lemma{����� 2.} ���� ���������� �������~$g$ �����������
������~$\calG$, �� ���������� �������~$h$ � �������� ��������
����������� (�������), ������������� ������~$\calG$,
������������ ������� $g$~��������.

(��������� � �������. � ������������ ��� ��� ����� ����������,
��� ����� ������������ ��������~$\calG$ ��������
�������� �
��������� ���� ���������.)

�������, ��� �� ���� ���� �������� ��������� ��\-����\-��\-���.
�������, ��� ���������~$T$ ���� ��������, �������������
������~$\calG$, �����������. � ����� ����, ��
������� ��� ��������������� ������� (\�� �� ������ ���
$\langle\text{��������},\text{��������}\rangle$) ����� ��������
��� $U$\� �����, ��������� �������~$U$ �������� �������.
(���������: ���������� ������� $\langle
t,x\rangle\hm\mapsto\text{(��������}$ �������~$t$ � �����~$x)$ �
�������� ����������� ������� ������������� �������.) �������
���������~$T$ �������� ������������ ��� �������� �������������
��������� ���� $U$\� ������� ���� ������� �� ������~$\calG$.

�����~1 �~2 �����������, ���~$\calG\hm=\Gamma(T)$. � �����
����, �� �����~1 ����� ������� ��~$\Gamma(T)$ �����������
������~$\calG$, ��� ��� ��������� ţ �����
�����������~$\calG$. � ������ �������, �����~2
�����������, ��� ������ �������~$g$ ��~$\calG$ �����
�������� �����, �������������~$\calG$ (��� ����� �~$T$) �
������~$g\hm\in\Gamma(T)$.

�������� �������� �����~1 �~2. �����, � ������������ � ������~1,
��������� �������~$g$ ����������� ������~$\calG$, � ţ
�����������~$h$\� ���. ����ͣ� ������������ ������������
���������~$K$ � ���������� ����� ������� ���� ����������:
        $$
V(n,x)= \left\{
           \begin{aligned}
            &\text{$h(x)$, ���� $n\in K$,}\\
            &\text{$g(x)$, ���� $n\notin K$.}
           \end{aligned}
        \right.
        $$
��� ������� ���������. � ����� ����, ţ ������, ��� �����
���������, ���������� ��� ����������� �������~$g$, �����������
��~$\bbN$, � �������~$h$, ����������� ��~$K$. �������
�������, ����� ���������~$V(n,x)$, �� ��������� �������
������������~$K$, � ����� (����������� � ���� ���������)
����������~$g(x)$ �~$h(x)$. ���������
��������, ���� ����������� ����������~$g(x)$ (� ���� ������ ���
�������, ����� ��~$n$ �~$K$, ��� ���~$h$ ���� �����������~$g$)
��� ���� ����������� ����������~$h(x)$ � � ���� ��~$n$
������������ �~$K$.

��������� �������~$U$ �������� �������, ���������� ����� ������̣����
�������~$s$ � ����� ���������:
        %
\begin{itemize}
       \item
$n\in K \Rightarrow U_{s(n)}=h \Rightarrow U_{s(n)} \notin \calG$;
       \item
$n\notin K \Rightarrow U_{s(n)}=g \Rightarrow U_{s(n)} \in \calG$.
        %
\end{itemize}
        %
��� ����� ���������� �~$K$ �������� ���������� �������������
��������� ������� ������� ��~$\calG$ ��� ����������
�����������~$s$ � ������ (�������~\ref{image-preimage}) �����������.
���������� ������������
��������� �������������� �����~1.

�����~2 ������������ �����������
������������. ����� (������� ����������� �����) �������~$g$
����������� ������~$\calG$, �� ������� ţ �������� �����
�� ����������� ����� ������. ���������� �������
        $$
V(n,x)= \left\{
           \begin{aligned}
            &\text{$g(x)$, } &\text{���� �����~$x$ ����� ������������~$K$}\\
            &                &\text{����� $n$ �ݣ �� ���������,}\\
            &\hbox to 0pt{\text{�� ����������, ���� ���������.}\hss}
           \end{aligned}
        \right.
        $$
����� ������, ��� ���~$n\hm\notin K$ �������~$V_n$ ��������� �~$g$,
� ������ �����������~$\calG$, � ���~$n\hm\in K$ �������~$V_n$
�������� �������� ������ �������~$g$ � ������ ��
�����������~$\calG$. ����� ���������� ��� � �����~1.
        %
\end{proof}
