\chapter[������������, ������������ � ��������������]%
{���������� �������, ���������� � ������������ ���������}\label{chapt01}%
\index{���������� �������}\index{�������!����������}

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

�������~$f$ � ������������ ����������� � ���������� ����������
\emph{����������}%
\index{���������� �������}\index{�������!����������}, ���� ����������
��������, ţ �����������, �� ���� ����� ��������~$A$, ���
        %
\begin{itemize}
        \item
���� $f(n)$~���������� ��� ���������� ������������~$n$, ��
��������~$A$ ��������������� �� �����~$n$ � ��������~$f(n)$;
        \item
���� $f(n)$~�� ����������, ��
��������~$A$ �� ��������������� �� �����~$n$.
        %
\end{itemize}

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

\textsf{1}. ������� ������������ ������������ ����� ��� ��������� �������
(�������� ����������� ������� �������� ��������� ������������
������������ ����). ��������, ����� �� ������̣���� �������
��������� (� ��������~$A$ ���� ����� ���������, ������� ������
�������������).

\textsf{2}. ����� ���� �� �������� �����������, ������ ���: \�� ����
$f(n)$~�� ����������, �� ���� ��������~$A$ �� ���������������,
���� ���������������, �� ������ �� ��������\��. �� ����� ���� ��
����� ������ �� �� ���������� (������ ����, �����
���������������, ������ �� ���������, �������� �����
�������������).

\textsf{3}. ������� � �������� ���������� ����� ���� �� ������
����������� �����, �� � �������� ������ (����� � ��������~$\{0,1\}$),
���� ����������� �����, �������� ������������������
���� � ������ �����, ��� �������, \�� �������������� �������%
\index{�������������� ������}\��.
������� ����������� ������� ����� ���������� �������, ������,
���������� ������� � ����� ������������ �����������, ����������
������� �������� ������������ �����.

��� �������, ������, �
��������������� ����������� � ���������� �������
������������ ������� ������������ �����������. ����� ��������
�������, ����������� ����� ���� �������, � �� � ������������
����� ������� �������� �� �����. ������� ������, ���, ��������,
����� (��� �������� ����������� ������������) ��������, �
�������~$\sign(x)$, ������ $-1$, $0$ �~$1$ ���
$x\hm<0$, $x\hm=0$ �~$x\hm>0$ ��������������\� ���. ����� ��� ��
������� ������������ ����������� ������������ �������,
����������� ������� �������� ����������� ������������������
����� � ������ \���

\textsf{4}. ��������� ����������� ����� ������� ��������� ���������
������������ �����������. ������ (\�� ������������
�����������\��?) ����� ���������� �ӣ ����� ����� ������ ��
�����, ��������� � ��� ����, ��� ����� ��������. �� �ӣ �� ����
��������� ������������, ����� �� ������� �� �������� ��, ��� ��
�� ��������. ��� ������ ��������� �����������:

\�� �������\��, ��� ������ ���������� �������~$f$ � ������������
����������� � ���������� ����� ���� ���������� �� �����
������̣���� ���������� ������� $g\colon \bbN\hm\to\bbN$. �
����� ����, ���� $f$~����������� ����������~$A$, ��
��������� ��������~$B$ ��������� �������~$g$, ������������~$f$:
\�� ���� $A$~���������������
��~$n$, �� $B$~���� ��� �� ���������, ��� �~$A$; ���� $A$~��
��������������� ��~$n$, �� $B$~���� ��������� (������)~$0$\��. (�
ޣ� ������ � ���� �����������?)

\section{���������� ���������}\label{chapt01-2}%
\index{���������� ���������}\index{���������!����������}

��������� ����������� �����~$X$ ���������� \emph{����������}%
\index{���������� ���������}\index{���������!����������},
���� ���������� ��������, ������� �� ������ ������������~$n$
����������, ����������� �� ��� ���������~$X$.

������� �������, $X$~���������, ���� ���
\emph{������������������ �������}\index{������������������ �������}%
\index{�������!������������������} $\chi(n) \hm= (\text{\textbf{if}
$n\hm\in X$ \textbf{then} $1$ \textbf{else} 0 \textbf{fi}})$
���������.

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

���������� ���������� ������������ �������� ���
����������� �����, �������� ������������ �����~\���

\begin{problem}
        %
��������, ��� ��������� ���� ������������ �����, ������� �����~$e$\index{$e$}
(��������� ����������� ����������), ���������.
        %
\end{problem}

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

������� ������ ������: ����� �������� ������������ ���������
���������������, �� ���������� ���������. ��� ������������
������: ��������� ���~$n$, ��� ������� � �����~$\pi$\index{$\pi$} ���� ��
�����~$n$ ������� ������, ���������. � ����� ����, ���
��������� �������� ����
��� ����������� �����, ���� ��� �����������
����� ������ �� ����������. � ����� ������� ��� ���������. ���
�� ����� �� ��� � �� ���������� ���������, ������� ��~$n$
������� ��, ���� �� �~$\pi$ �� �����~$n$ ������� ������.

\begin{problem}
        %
������������ �� � ���� ����������� �����\� �� �������� �����~$\pi$?
��� ���������, ���� �������� ����� \�� �� �����~$n$
�������\��\ �� \�� �����~$n$ ������� (��\-��\-֣�\-���
��\� ���������)\��?
        %
\end{problem}

���������� �� ������������ ���������\index{������������ ���������}%
\index{���������!������������}? ��\-����\-��\-��\� ������
������, ��� ���������� (� ������� ���������� �����������
������������ ����) �ޣ���� �����, � ���� �����������
������������ ���� ���ޣ���� �����. ����� ���������� �������
�� �ݣ ��������.

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

��������� ����������� ����� ���������� \emph{������������}\index{������������
���������}\index{���������!������������}, ����
��� ������������� ��������� ����������, �� ���� ���� ����������
��������, ������� �������� (� ������������ ������� � �
������������� ������������ �������) ��� �������� ����� ���������
� ������~��.

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

���������� ����� ������������� ����������� �������������
���������. ��� ��������� �� ���:
        %
\begin{enumerate}
        \item\label{enum-1}
��������� �����������, ���� ��� ���� ������� �����������\index{�������
�����������} ���������� �������\index{���������� �������}%
\index{�������!����������}.
        \item\label{enum-2}
��������� �����������, ���� ��� ���� ������� ��������\index{������� ��������}
���������� �������\index{���������� �������}\index{�������!����������}.
        \item\label{enum-3}
���������~$X$ �����������, ���� ��� (��� ������ �������) \��
����������������������\index{���������������������� �������}%
\index{�������!����������������������}\��\ �������, ������~$0$ ��
���������~$X$ � �� ������̣���� ���~$X$, ���������.
        %
\end{enumerate}

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

����� $X$~������������� ��������� ����������~$A$. �������, ���
���������������������� ������� ���������~$X$ ���������. � �����
����, �������� ţ ���������� �����: ������� �� ���� �����~$n$,
�������� ��������� ��������~$A$, ������, ���� �� ����������
�����~$n$. ��� ������ �� ��� �������, ������ �� �����~$0$ �
��������� ������.

��������, ����� $X$~���� ������� �����������
(����������) �������~$f$, ����������� ��������� ����������~$B$.
����� $X$~������������� ����� ����������~$A$:
        %
\quot{%
        %
����������� ���������~$B$ �� ������ $0,1,2,\dots$,
����� �ӣ ������ ����� ������ ���������~$B$ \textnormal{(}�������
���� ��� ������ �� ������~$0$ �~$1$; ����� �� ��� ���� ������ ��
������ $0,1,2$, ����� �� ��� �� ������ $0,1,2,3$ � ��� �����\textnormal{)}.
��� ���������, �� ������� ��������~$B$ ����������� ������,
�������� �� ���� �����������.
        %
}

����, �� ���������� ��������������� ��������� ��\-��\-��\-��\-���
������������~\ref{enum-1} �~\ref{enum-3}. ���� � ������ ���
�����ģ���� �������� ���������~$A$ �������� �� ���������, ��
������� $B$~����������� ������, � ���������� ���� ������, ��
���������� ��������, ������������� ������� �������� �������~$f$.
�������� �ݣ ���������, ��� ������ ������������ ��������� ����
������� �������� ���������� �������. ��� ����� �������,
��������, ���: ����� $X$~���� ������� ����������� ����������
�������, ����������� ��������� ����������~$A$. ����� $X$~����
������� �������� �������
        $$
b(x)=\left\{
        \begin{aligned}
           & x,\ \text{���� $A$ ����������� ������ �� $x$},\\
           & \text{�� ���������� � ��������� ������}.
        \end{aligned}
     \right.
        $$
����������� ��� ������� �������� ��������� ��� ��, ��� �~$A$, ��
������ ������ ���������� ������ ���������~$A$ ������ �����
�����.

�ݣ ���� ������������� ����������� ������������� ���������:
��������� ����������� ����� �����������, ���� ��� ���� �����,
���� ���� ��������� �������� ����� ������̣���� ����������
������� (������� �������, ��� �������� ����� ����������� �
���������� ������������������).

� ����� ����, ����� ������������ ���������~$X$, �������������
����������~$A$, �������. ����ͣ� � Σ� �����\� �� �������~$x_0$.
������ ���������� ����� ����� ������̣���� �������~$a$: ���� ��
$n$\� � ���� ������ ���������~$A$ ���������� �����~$t$, �� �������
$a(n)\hm=t$; ���� �� ������ �� ����������, �� ������� $a(n)\hm=x_0$.
(�� ������������, ��� �� ������ ���� ������ ��������� �����
��������� ������ ���� �����\� � ��������� ������ ������ ����
������� �� ����� ������ ����.)

�������, ��� ��� ����������� ���������������\� ����
��������~$A$, �� ����� �� �����, ����� �� ������������� ��
��������� ��� ���.

\begin{theorem}
        \label{enumerable-union-intersection}%
�����������\index{����������� ��������} � �����������\index{�����������
��������} ������������ ��������\index{������������ ���������}%
\index{���������!������������} �����������.
        %
\end{theorem}

\begin{proof}
        %
���� $X$ �~$Y$ ������������� ����������� $A$ �~$B$, �� ��
����������� ������������� ����������, ������� �����������
��������� �� ����� $A$ �~$B$ � �������� �ӣ, ��� �������� $A$ �~$B$.
� ������������ ������� �������\� ���������� ������ $A$ �~$B$
���� ����������� � ������� ���� � ������; ��� ��������
������\� ��������.
        %
\end{proof}

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

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

\begin{problem}
        %
������ ������� � ��� ����������
\�� ������������������� ����������\index{�������������������
��������}\��\
(���������, �� ����������Σ����)\� ����� �������� �������� �
���� ������� ����
        \begin{center}
 \texttt{n := }������������ ����������� �����
        \end{center}
(����������, �������, ������� \��\texttt{n := }$0$ ��� $1$\��,
��� ��� ������������ ����� ����� ����������� �� �����).
������������������� �������� (��� ����� � ��� �� �����) �����
����������� ��\� �������, � ����������� �� ����, ����� \��
������������\��\ ����� ����� �������. ��������, ��� ������������
��������� ����� ������������ ���������� ��� ��������� �����,
������� ����� ��������� �� ������ �������������������� ���������
(��� ������������� �����).
        %
\end{problem}

\begin{problem}
        %
��������, ��� ���� ��������� $A\hm\subset\bbN$ �~$B\hm\subset\bbN$
�����������, �� �� ���������
������������\index{��������� ������������
��������}~$A\hm\times B\hm\subset\bbN\hm\times\bbN$
����� �����������.
        %
\end{problem}

\section{������������ � ���������� ���������}\label{chapt01-4}
\index{������������ ���������}\index{���������!������������}%
\index{���������� ���������}\index{���������!����������}
\begin{theorem}
        \label{post-theorem}%
������ ���������� ��������� ����������� ����� �����������.
���� ���������~$A$ � ��� ���������� (�� ��������� ����
����������� �����) �����������, �� $A$~���������.
        %
\end{theorem}

\begin{proof}
        %
���� �������������� ����� � ���������~$A$ ����� ���������
��������� ����������, ��~$A$ � ��� ���������� �����������: ����
�� ������� ��������� �������������� ����� $0,1,2,\dots$ �
�������� �� �� ���, ������� �����������~$A$ (��� ��, ������� ��
�����������~$A$).

� ������ �������: ���� � ��� ���� ��������, �������������~$A$,
� ����� ������ ��������, ������������� ���������� �~$A$, ��
��� ��������� �������������� ��������� �����~$n$ �~$A$ ����
��������� ��� ��� ��������� � �����, ���� ���� �� ���
����������~$n$ (�� �����, ��� ���� ��� ������ ����� ���� ��
��� ��� �������). ���������, ����� �������� ��� ������,
�� ������, ����� ��~$n$ �~$A$.
        %
\end{proof}

���� ���� �������� \emph{�������� �\'����}\index{�������!�����}%
\glossary{����@\����}.

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

\begin{theorem}
        %
���������~$P$ ����������� ����� ����������� ����� � ������
�����, ����� ��� �������� ���������\index{��������} ���������� �����������
���������~$Q$ ��� ����������� �����. (�������� ����������,
���� �� ��� �������� �� ������ ����������:
$x\hm\in P \hm\Leftrightarrow \exists y (\langle x,y\rangle \hm\in
Q)$.)
        %
\end{theorem}

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

��������, ���� $P$\� ������������ ���������, �������������
����������~$A$, �� ��� ���� �������� ����������� ���������~$Q$,
���������� �� ���� ����� ��� $\langle x,n\rangle$, ���~$x$
���������� � ������� ������~$n$ ����� ������ ���������~$A$.
(��� ��������, ��������, ���������.)
        %
\end{proof}

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

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

\begin{theorem}
        %
�������~$f$ � ������������ ����������� � ���������� ���������
����� � ������ �����, ����� ţ ������\index{������ �������}
    $$
F=\{\langle x, y\rangle \mid \text{$f(x)$ ���������� � ����� $y$}\}
    $$
��������
������������ ���������� ��� ����������� �����.
        %
\end{theorem}

\begin{proof}
        %
����� $f$~���������. ����� ���������� ��������, ������������� ţ
������� �����������, �� ���� ���������� ���~$x$, �� �������
$f$~����������. ���� ������ ��� ������� �� �����~$x$ ��������� �ݣ �
��������~$f(x)$, ������� ��������, ������������� ���������~$F$.

��������, ���� ������� ��������, �������������~$F$, �� �������~$f$
����������� ����� ����������: ���� �� �����~$n$, �ģ�
��������� �~$F$ ����, ������ ���� ������� �����~$n$; ���
������ ����� ���� ���������, �������� ţ ������ ���� �
������� ������.
        %
\end{proof}

����� $f$\� ��������� ������� � ������������
����������� � ����������. \emph{�����}\index{����� ���������}
���������~$A$ ���~$f$
������������ ��� ��������� ���� �����~$f(n)$, ��� �������~$n\in
A$ � $f(n)$~����������. \emph{��������}\index{��������}
���������~$A$ ���~$f$
������������ ��� ��������� ���� ���~$n$, ��� �������
$f(n)$~���������� � �����������~$A$.

\begin{theorem}
        \label{image-preimage}%
�������� � ����� ������������� ��������� ��� ���������� �������
�����������.
        %
\end{theorem}

\begin{proof}
        %
� ����� ����, �������� ������������� ���������~$A$ ��� ����������
�������~$f$ ����� �������� ���: ����� ������~$f$, �������� ���
� ������������ ���������� $\bbN\hm\times A$ � ��������������
�� ������ ����������. ����������� ��� ������� ����������,
������ ���������� �������� �������.
        %
\end{proof}

\begin{problem}
        %
����� $F$\� ������������ ��������� ��� ����������� �����.
��������. ��� ���������� ���������� �������~$f$, ������̣���� ��
��� � ������ ���~$x$, ��� ������� ���ģ���~$y$, ��� �������
$\langle x,y\rangle\hm\in F$, ���ޣ� ��������~$f(x)$ ��������
����� �� �����~$y$. (��� ����������� �������� ������
\emph{�������� �� �������������}\index{�������!�� �������������}.)
        %
\end{problem}

\begin{problem}
        %
���� ��� �������������� ������������ ��������� $X$ �~$Y$.
��������, ��� �������� ���������������� ������������ ���������
$X' \hm\subset X$ � $Y'\hm\subset Y$, ��� ������� $X'\hm\cup Y' \hm=
X \hm\cup Y$.
        %
\end{problem}

\begin{problem}
        %
\emph{�����������}\index{���������� ���������} ���������� ���������,
�������
���
$P(x_1,\dots,x_n)\hm=0$, ��� $P$\� ��������� � ������
��������������. ��������, ��� ��������� ����������� ���������,
������� ����� �������, �����������. (��� �����������: � ����
������� ��������� ��������� �.\,�.\,�����������, ���������
        \glossary{����������@\����������}%
�������� ���������� \�� 10\� � ��������~���������\��.)
        %
\end{problem}

\begin{problem}
        %
�� �������� �� �������������� �������~�����\glossary{�����@\�����},
��������, ���
��������� ���� �����������~$n$, ��� ������� ���������� �������
��������� $x^n\hm+y^n\hm=z^n$ � ����� ������������� ������,
�����������. (��� ������ ��������, ��� ��������� �������� ����
����� $1$ �~$2$.)
        %
\end{problem}

\begin{problem}
        %
��������, ��� ������ ����������� ������������ ���������
����� �������� � ���� $\{a(0), a(1), a(2),\dots\}$, ���
$a$\� ���������� �������, ��� �������� ������� ��������.
(��������: � ���� ������������ ������� ����������.)
        %
\end{problem}

\begin{problem}
        \label{infinite-recursive-subset}%
��������, ��� ������ ����������� ������������ ���������\index{������������
���������}\index{���������!������������}
�������� ����������� ���������� ������������\index{���������� ���������}%
\index{���������!����������}.
(��������: ������������� ���������� ������� � ������� ������������
���������������������.)
        %
\end{problem}

\begin{problem}
        %
��������, ��� ��� ������ ���������� �������~$f$ ���������� ����������
�������, ���������� \�� ��������������\index{�������������� �������}\��\ �~$f$
� ��������� ������: ������� �����������~$g$ ��������� � �������� ��������~$f$,
� ��� ����
        $
f(g(f(x)))\hm=f(x)
        $
��� ����~$x$, ��� ������� $f(x)$~����������.
        %
\end{problem}

\begin{problem}
        \label{computable-real}%
�������������� ����� $\alpha$ ���������� \emph{����������},
        \index{���������� �������������� �����}%
        \index{�����!����������}%
���� ���������� ���������� ������� $a$, ������� �� ������ �������������
$\varepsilon\hm>0$ ���� ������������ ����������� �~$\alpha$
� ������� �� �����~$\varepsilon$, \��
        $
|\alpha - a(\varepsilon)| \le \varepsilon
        $
��� ������ ������������� $\varepsilon\hm>0$. (������������ �����
�������� �������������� ��������, ��� ��� ������� ������������
�� ������� ������������ ���������.)

        (\textbf{�})~%
��������, ��� ����� $\alpha$ ��������� ����� � ������ �����,
����� ��������� ������������ �����, ������� $\alpha$, ���������.

        (\textbf{�})~%
��������, ��� ����� $\alpha$ ��������� ����� � ������ �����,
����� ������������������ ������ �������������� ��� ����������
(��� ��������) ����� ���������.

        (\textbf{�})~%
��������, ��� �����~$\alpha$ ��������� ����� � ������ �����,
����� ���������� ���������� ������������������ ������������
�����, ��������� ���������� � $\alpha$ (��������� ��������,
��� ����� �������������� �������~$N$ ��~$\varepsilon$ �
����������� $\varepsilon$-$N$\� ����������� ����������.)

        (\textbf{�})~%
��������, ��� �����, ������������, �������� � ������� ����������
�������������� ����� ���������. ��������, ��� ������ ����������
� ����������� �������������� ��������.

        (\textbf{�})~%
������������� � �������� ����������� � ���, ��� ������
��������� ���������� ������������������ ���������� ��������������
����� ��������.

        (\textbf{�})~%
�������������� �����~$\alpha$ �������� \emph{������������ �����},
        \index{�����!������������ �����/������}%
        \index{������������ �����/������ �����}%
���� ��������� ���� ������������ �����, �������~$\alpha$,
�����������. (�������������� ������ ������������ ����������.)
��������, ��� ����� $\alpha$ ����������� ����� ����� � ������
�����, ����� ��� �������� �������� ��������� ����������
������������ ������������������ ������������ �����.

        (\textbf{�})~%
��������, ��� �������������� ����� ��������� ����� � ������
�����, ����� ��� ����������� ����� � ������.
        %
\end{problem}

���������� �������� ���������� �������������� ����� ��.~�
������~\ref{computable-real-2}.


