% ---------------------------- �������� 49 ----------------------------------
\chapter{������������� ���������}

\section[��������������� � �������]%
{��������� ��������������� � �������}\index{���������!���������������}%
\index{���������!�������}
        \label{equivalence-order}

��������, ��� �������� ���������� �� ���\-����\-��~$X$ ����������
������������ $R\hm\subset X\hm\times X$; ������ $\langle
x_1,x_2\rangle \hm\in R$ ����� �����~$x_1 R x_2$.

�������� ���������~$R$ �� ���������~$X$
���������� \emph{���������� ���������������}\index{���������!���������������},
���� ��������� ��������� ��������:
        %
\begin{itemize}
        %
\item (��������������)\index{��������������} $xRx$ ��� ����~$x\hm\in X$;
        %
\item (��������������)\index{��������������} $xRy \hm\Rightarrow yRx$
��� ����~$x,y\hm\in X$;
        %
\item (��������������)\index{��������������} $xRy \text{ � } yRz \hm\Rightarrow
        xRz$ ��� ����� ���������~$x,y,z\hm \in X$.
\end{itemize}
         %
����� ����� ��������� ���������, �� ����� ������������
�����������:

\begin{theorem}
        \label{equivalence-classes}%
(\textsf{�})
        %
���� ��������� $X$ ������� � ����������� ����������������
�����������, �� ��������� \�� ������ � ����� ������������\��\
�������� ���������� ���������������.

(\textsf{�})
        %
������ ��������� ��������������� ���������� ��������� ��������
�� ���������� ���������.
        %
\end{theorem}

\begin{proof}
        %
������ ����������� ������ ��������; �� �����ģ� ��������������
�������, ����� ���� �����, ��� ������������ ��� ������
����������� ���������������. ����, ����� $R$\� ���������
���������������. ��� ������� ��������~$x\hm\in X$ ���������� ���
\emph{����� ���������������}\index{����� ���������������}\� ���������
����~$y\in X$, ��� ������� �����~$xRy$.

�������, ��� ��� ���� ��������� $x_1$, $x_2$ ����� ��������� ����
�� ������������, ���� ���������. ����� ��� ������������, �� ����
����� ����� �������~$z$. ����� $x_1 R z$ �~$x_2 R z$, ������
$z R x_2$ (��������������) � $x_1 R x_2$ (��������������), � �����
$x_2 R x_1$ (��������������). ������� ��� ������~$z$
��~$x_1 R z$ �������~$x_2 R z$ (��������������) � ��������.

% ---------------------------- �������� 50 ----------------------------------
�������� ��������, ��� � ���� �������������� ������ �������~$x$
����������� ����������� �� ������, �� ���� �������������
�ӣ ���������~$X$ ������� �� ���������������� ������.
        %
\end{proof}

\begin{problem}
        %
��������, ��� ���������� �������������� � �������������� �����
�������� �����: $\text{$xRz$ � $yRz$} \Rightarrow xRy$
(��� ���������� ���������� ��������������).
        %
\end{problem}

\begin{problem}
        %
������� ��������� ��������� ��������������� ���������� �� ���������
$\{1,2,3,4,5\}$?
        %
\end{problem}

\begin{problem}
        %
�� ���������~$M$ ������ ��� ��������� ���������������,
������������ $\sim_1$ � $\sim_2$, ������� $n_1$ � $n_2$ �������
��������������� ��������������.
����� �� �� �����������
$x\sim y \hm\Leftrightarrow [(x\sim_1 y)\text{ � }(x\sim_2 y)]$
���������� ���������������? ������� � ���� ����� ���� �������?
��� ����� ������� ��� ����������� ���������?
        %
\end{problem}

\begin{problem}
        %
(������� ������\index{�������!������}\glossary{������@\������})
��������� ���� $k$\� ���������� �����������
������������ ���������~$A$ ������� �� $l$~������� ($k$, $l$\�
����������� �����). ��������, ��� ���ģ��� ����������� ���������
$B\hm\subset A$, ��� $k$\� ���������� ������������ ��������
����������� ������ ������.

(���~$k\hm=1$ ��� ��������: ���� ����������� ��������� �������
�� �������� ����� �������, �� ���� �� ������� ����������. ���~$k=2$
�~$l=2$ ����������� ����� �������������� ���:
�� ������������ ��������� ����� ����� ������� ����
���������� ����� ������� ��������, ���� ���������� �����
������� ����������. �������� ������� ����� �����������\� � ���,
��� ����� ����� ����� ����� ���� ���� ��� ������� ��������,
���� ��� ������� ����������,\� ��������� ������ ��� ����������.)
        %
\end{problem}

��������� ������� ��������������� �������� \emph{������\�
����������}\index{������\� ���������}
���������~$X$ �� ��������� ���������������~$R$.
(���� ��������� ����������� � ��������������� �����������
��~$X$, ���������� ������\� ������, ������\� ������ \���)

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

�������� ���������~$\le$ �� ���������~$X$ ���������� \emph{����������
���������� �������},
    \index{���������!���������� �������}%
    \index{��������� �������}%
���� ��������� ����� ��������:
        %
\begin{itemize}
        %
\item (��������������)\index{��������������} $x\le x$ ��� ����~$x\hm\in X$;
        %
% ---------------------------- �������� 51 ----------------------------------
\item (������������������)\index{������������������}
         $x\le y \text{ � } y\le x \hm\Rightarrow x\hm=y$
         ��� ���� $x,y\hm\in X$;
       %
\item (��������������)\index{��������������}
         $x\le y\text{ � }y\le z \hm\Rightarrow
        x\hm\le z$ ��� ���� $x,y,z\hm \in X$.
\end{itemize}
        %
(������ ��������, �� ���������� ������~$\le$ (� �� �����) ��� ����
��������� �������.) ��������� � �������� �� Σ� ���������� ����������
������� �������� \emph{�������� �������������}.%
        \index{���������!�������� �������������}%

�������, ��� ��� �������� $x,y$ �������� ��������������
��������� \emph{��������}\index{�����������},
���� $x\le y$ ��� $y\le x$. �������,
��� ����������� ���������� ������� �� �������, ����� ����� ���
�������� ��������� ���� ��������. ������� ��� ����������, �� �������
����������� \emph{��������� �������} (\emph{������� ��������������
���������}).
        \index{�������� �������}%
        \index{���������!��������� �������}%
        \index{���������!������� �������������}%

�����ģ� ��������� �������� ��������� ��������:
        %
\begin{itemize}
        %
\item
�������� ��������� � ������� ���������� ������� (�����
������� ����� ��������).
        %
\item
�� ��������� $\mathbb{R}\hm\times\mathbb{R}$ ���� ��� ��������������
����� ����� ������ ��������� �������, ������, ��� $\langle
x_1,x_2\rangle \hm\le \langle y_1,y_2\rangle$, ���� $x_1\hm\le x_2$
�~$y_1\hm\le y_2$. ���� ������� ��� �� ����� ��������: ����
$\langle 0,1\rangle$ �~$\langle 1,0\rangle$ �� ��������.
        %
\item
�� ��������� ������� � ��������������� ����������� � ����������
����� ������ ��������� �������, ������, ��� $f\hm\le g$, ����
$f(x)\hm\le g(x)$ ��� ���� $x\in\bbR$. ���� ������� �� �����
��������.
        %
\item
�� ��������� ����� ������������� ����� ����� ���������� �������,
������, ��� $x\hm\le y$, ���� $x$ �����~$y$. ���� �������
���� �� ����� ��������.
        %
\item
��������� \�� ����� ������� �������� �����~$x$ �������� ����� � ���������
�����~$y$\��\ �� ����� ���������� ������� �� ��������� �����
������������� ����� (��� ����������� � �����������, �� ��
���������������).
        %
% ---------------------------- �������� 52 ----------------------------------
\item
����� $U$\� ������������ ���������. ����� �� ���������~$P(U)$ ����
����������� ���������~$U$ ��������� ��������� $\subset$ �����
��������� ��������.
        %
\item
\label{lexicographic-ordering}%
�� ������ �������� �������� �������� ���������� ���������
�������
($\text{�}\hm\le\text{�}\hm\le\text{�}\hm\le\ldots\hm\le\text{�}$).
���� ������� ������\� ��� ����� ��� ����� ����� �������, ����� ��
��� ������ (��� ������������� �������� � �������).
        %
\item
�� ������ �������� �������� ������̣� \emph{������������������}%
       \index{������������������ �������}
������� (��� � �������). ��������� ���������� ��� ����� ���:
���� �����~$x$ �������� ������� �����~$y$, �� $x\hm\le y$
(��������, $\text{����}\hm\le\text{������}$). ���� �� ���� �� ����
�� �������� ������� �������, ��������� �� ������ �� �������
�����, � ������� ����� ����������: �� �����, ��� ��� �����
������ � ���������� �������, � ����� ������. ���� ������� �����
������ (����� ��� �� ������ ����������� ��������?).
        %
\item
��������� ��������� ($(x\hm\le y)\hm\Leftrightarrow (x\hm=y)$)
����� �������� ���������� ���������� �������, ��� ��������
������� ��� ��������� �������� �� ��������.
        %
\item
�����ģ� ������ ������� ������. ����� ���� ���������~$X$
���������
�������. ���ģ� �� Σ� �������, ������, ���
$x\hm\le
y$, ���� �������~$x$ ������� ���������� ������ �������~$y$ (���
���� $x$~�~$y$\� ���� � �� �� �������). � ����������� �� ������
������� ���� ������� ����� ���� ��� �� ���� ��������.
        %
\end{itemize}

����� $x,y$\� �������� �������� �������������� ���������~$X$.
�������, ��� $x<y$\index{$a<b$}, ���� $x\le y$ � $x\ne y$. ��� ����� ���������
��������� �����
��������:
        \begin{gather*}
 x \not< x;\\
(x < y) \text{ � } (y < z)\ \Rightarrow\ x < z.
        \end{gather*}
% ---------------------------- �������� 53 ----------------------------------
(������ ��������, �������� ������: ���� $x\hm<y$ �~$y\hm<z$, �� ����
$x\hm\le y$, $x\hm\ne y$, $y\hm\le z$, $y\hm\ne z$, ��~$x\hm\le z$ ��
��������������; ���� �� ���������, ���~$x\hm=z$, �� �� �� �����
$x\hm\le y\hm\le x$ � ������~$x\hm=y$ �� ������������������, ���
������������ �������������.)

����������������� ���������: �� ������ ����~$\le$ ��� \�� ������
��� �����\��, � ����~$<$\� ��� \�� ������\��, ������
�����������, ��� $x\hm\le y$ ����� � ������ �����, ����� $x\hm<y$ ���~$x\hm=y$.
� �������, ��� ������������� ���. �ݣ ���� ���������: ��������� $x\hm>y$
(\�� $x$ ������~$y$\��) ��������, ���~$y\hm<x$,
� ��������� $x\ge y$ (\�� $x$ ������ ��� �����~$y$\��) ��������,
���~$y\hm\le x$.

\begin{problem}
        %
���������, ������ �� ����� ������ $x\hm\le y$ ��� \�� $x$ �� ������~$y$\��.
        %
\end{problem}

� ��������� ������� ��������� ���������� ������� ������������
��� ���������~$<$, ��������������� ���� ��������� ���������. �
���� ������ ��������� $x\hm\le y \hm\Leftrightarrow [(x\hm<y)
\text{ ��� } (x\hm=y)]$ �������� ���������� ���������� ������� �
������ ������ �����������.

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

�� ��������� �������� ��������� $<$ ������ �������� ����������
\emph{�������� �������}, � ��������� $\le$\� ����������
\emph{���������� �������}. ���� � �� �� �������� �������������
��������� ����� �������� ��\� �������: ����� ������� ����������
��������� ���������� �������~$\le$ (������������,
���������������� � ������������) � ����� �� ���� ��������
��������� �������� �������~$<$, � ����� ����������� � ��������.

\begin{problem}
        %
������� ���������� ������������������ � ����������� ���������� �������,
�������� ����������� \emph{�����������}\index{�����������}.
��������, ��� �����
����������� ������� ���: ��������� ������� �� ����������������
������, ��� ���� $x\hm\le y$ ��� ����� ���� ���������
$x$, $y$ �� ������ ������, � �� ������\� ��������� ����� ���������
�������, ������� � ���������� ��������� ��������� ���� ���������
�� ������ �������.
        %
\end{problem}

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

\begin{itemize}
        %
\item
����� $Y$\� ������������ �������� �������������� ���������~$(X,\le)$.
����� �� ���������~$Y$ ��������� ������������ ��������� �������,
\emph{��������������}\index{�������������� �������} ��~$X$. ��������� ������,
        $$
(\le _Y) = (\le) \cap (Y\times Y).
        $$
���� ������� ��~$X$ ��� ��������, �� � �������������� ������� ��~$Y$,
��������, ����� ��������.
        %
% ---------------------------- �������� 54 ----------------------------------
\item
����� $X$ � $Y$\� ��� ���������������� ��������
������������� ���������. ����� �� �� ����������� �����
���������� ��������� ������� ���: ������ ������� ���������
�������� ������������ ��� ������, � ����� �������
���������~$X$ �� ����������� ������ ������ ��������~$Y$. ���
��������� ����������� ����������~$X+Y$\index{$A+B$}. (������� �����
��������, ���� �� ��� ������� �� ������ �� ��������.)

��� �� ����������� ��������� � ��� �������������� (� ����
����������� ��������). ��������, ������ �� �������������
 ���������
$\mathbb{N}+\mathbb{N}$, �� ��ң� ���
���������������� ����� ������������ ���� $\{0,1,2,\dots\}$ �
$\{\overline 0,\overline 1,\overline 2\dots\}$ � ������������� ���������
$\{0,1,2,\dots,\overline 0, \overline1, \overline2,\dots\}$, ���ޣ� $k\le \overline l$
��� ���� $k$~�~$l$, � ������ ������ ����� ������� �������.
        %
\item
����� $(X, \le_{X})$ � $(Y,\le_Y)$\� ��� �������������
���������. ����� ���������� ������� �� ������������~$X\hm\times Y$ �����������
���������. ����� �������, ��� $\langle x_1,y_1\rangle \hm\le
\langle x_2,y_2\rangle$, ���� $x_1 \le_X x_2$ �~$y_1\le_Y y_2$
(�������������� ���������). ���� �������, ������, �� �����
��������, ���� ���� �������� ������� � ���� ���������: ����
������ ���������� ������ � ����� ����, � ������ � ������, ��� ��
��������? ����� �������� ��������
        \label{linear-cartesian-product}%
�������, �����������, ����� ���������� ����� \�� �������\��\ �
����� ������� ���������� �� ���, � ����� (� ������ ���������)\�
�� ������. ���� ������� ������� $X$\� ����������, �� $\langle
x_1,y_1\rangle \hm\le\langle x_2,y_2\rangle$, ���� $x_1 <_X x_2$
��� ���� $x_1=x_2$, � $y_1 \le_Y y_2$. ������ �� �����������
�������� ������ ������� ������� ������ ����������. ������ �
������������ ���� ������� ������������� �������� ��� � �������
������������� ���������, �� � ���������� ������������� ������
����� ������� (������� ���������� �� ������ ����������).{\looseness=-1\par}
        %
\end{itemize}

\begin{problem}
        %
��������, ��� � �������� �������������
���������~$\mathbb{N}\hm\times\mathbb{N}$ (������� ��������������)
��� ������������
% ---------------------------- �������� 55 ----------------------------------
������������, ����� ��� ��������
�������� ���� �� ����������. ����� �� �����������
����������� ���~$\mathbb{Z}\hm\times\mathbb{Z}$?
        %
\end{problem}

\begin{problem}
        %
�������� ����������� ����������� ���~$\mathbb{N}^k$ (�������
��������������).
        %
\end{problem}

\begin{problem}
        %
����� $U$\� �������� ��������� ��~$n$ ���������. ����������
���������~$P(U)$ ���� ����������� ���������~$U$, �������������
�� ���������. ������ �����������
��������� �������� ��������� $S\subset P(U)$, ����
�������������� ��~$S$ ������� ������? ���� ������� ���
��������~$S$ �� ��������? (��������: ��.~������~\ref{noncomparable-subsets}.)
        %
\end{problem}

\begin{problem}
        %
������� ���������� ��������� �������� �������� ��
��������� ��~$n$ ���������?
        %
\end{problem}

\begin{problem}
        %
��������, ��� ������ ��������� ������� �� �������� ���������
����� ���������� �� ��������� (\�� ����������\��\ ��������, ���
���� $x\hm\le y$ � �������� �������, �� � � ����� ��� ���������
���).
        %
\end{problem}

\begin{problem}
        %
���� ����������� �������� ������������� ���������~$X$. ��������,
��� � Σ� ������ ���ģ��� ���� ����������� ������������ �������
����������� ���������, ���� ����������� ������������, �� �������
�������������� ������� ������.
        %
\end{problem}

\begin{problem}
        %
(�������� ������� ���������� ������.) ���� ����� ������������� �����
$m$~�~$n$. ��������, ��� �� ������ �������� ������������� ���������
��������~$mn+1$ ����� ������� ���� $m+1$~������� �����������
���������, ���� $n+1$~������� ���������.
        %
\end{problem}

\begin{problem}
        %
� ������� �������� $mn+1$~��������� �����. ��������, ��� �����
����� �� ��� ���������� ���, ����� �������� ���� ������������
������������������ �����~$m+1$, ���� ���������
������������������ �����~$n+1$. (��������: ����� ���������������
���������� �������.)
        %
\end{problem}

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

������� �������� �������������� ��������� �������� \emph{����������}%
\index{���������� �������},
���� �� ������ ������ ������� ��������, � \emph{������������}%
\index{������������ �������},
���� �� ���������� �������� ��������. ���� ��������� ��
�������� ������� �������������, �� ��� �� ���� � �� ��:
���������� �������
% ---------------------------- �������� 56 ----------------------------------
������������� �������� ������������,
�� �� ��������. (���� ���� �������, � ������� ����������
����� ������, ������\� �������, ������� ������ ������
�� ����������.)

����������� ������� ������������ \emph{����������}\index{���������� �������}
 � \emph{�����������}\index{����������� �������} ��������.

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

\begin{problem}
        %
��������, ��� ����� ��� ������������ ��������
�� ��������. ��������, ��� � �������� ��������
������������� ���������~$X$ ��� ������ ��������~$x$
���ģ��� ������������ �������~$y$, ������� ��� ������~$x$.
        %
\end{problem}

\section{�����������}\index{����������}
        \label{isomorphisms}%

��� �������� ������������� ��������� ����������
\emph{�����������}\index{���������!����������}, ���� ����� ���� ����������
\emph{����������}\index{����������}, �� ���� ������� ����������� ������������,
����������� �������. (�����������, ��� � ���� ������
��� ���������� ��� ���������.) ����� ������� ���:
������� $f\colon A\hm\to B$ ���������� ������������ ��������
������������� ��������~$A$ �~$B$, ����
        $$
 a_1 \le a_2 \ \Leftrightarrow \ f(a_1) \le f(a_2)
        $$
��� ����� ��������� $a_1,a_2\hm\in A$ (����� ����~$\le$ ����������
������� � ���������~$A$, ������\� � ���������~$B$).

��������, ��� ��������� ������������ ����������� (������ ���������
��������� ������ ����), ����������� (���� $X$~���������~$Y$, ��
� ��������) � ����������� (��� ���������, ���������� ��������,
��������� ����� �����). ����� �������, ��� ��������
������������� ��������� ����������� �� ������ ����������,
������� �������� \emph{����������� ������}\index{���������� ���}.
(������, ��� � �
����������, ��� ���������� ������������\� ���������� ��������
������� �����, � ������ �������� � ���������� ����� ���
���������� ������.)

% ---------------------------- �������� 57 ----------------------------------
\begin{theorem}\label{finite-linear-order}
        %
�������� ������� ������������� ��������� �� �����������
����� ��������� ���������.
        %
\end{theorem}

\begin{proof}
        %
�������� ������� ������������� ��������� ������ ����� ����������
������� (����ͣ� ����� �������; ���� �� �� ����������, ����ͣ� �������,
���� � �� �� ����������, �ݣ �������\� � ��� �����; �������
��������� ������������������ $x\hm>y\hm>z\hm>\ldots$, ������� ���� ���
������ ������ ����������). �������� ����������� �������� �����~$1$.
�� ���������� ����� ������� ����������
������� � �������� ��� �����~$2$ � ��� �����. ����� ������,
��� ������� ����� ���������� ������������� ������� �����
��������, �� ���� ��� ���� ��������� ��������� ���������
$\{1,2,\dots,n\}$.
        %
\end{proof}

\problskip

\begin{problem}
        %
��������, ��� ��������� ���� ����� ������������� ���������
�����~$30$ � ���������� \�� ���� ���������\��\ � ��������
��������� ������� ��������� ��������� ���� �����������
���������~$\{a,b,c\}$, �������������� �� ���������.
        %
\end{problem}

\begin{problem}
        %
����� ������������� �������� ������������������%
\index{�������� ������������������} �����������
�����, �� ���� ������������������, � ������� ��� �����, �����
��������� �����, �����~$0$. �� ��������� �����
������������������� ���ģ� �������������� �������:
$(a_0,a_1,\dots) \hm\le (b_0,b_1,\dots)$, ���� $a_i\hm\le b_i$
��� ����~$i$. ��������, ��� ��� ��������� ��������� ���������
���� ������������� ����� ����� � ���������� \�� ����
���������\��\ � �������� �������.
        %
\end{problem}

\problskip

������� ����������� ����������� �������� ��������������
���������~$A$ � ����, ���������� ������������,
��������
\emph{�������������}\index{�����������} ��������
�������������� ���������~$A$.
������������� ����������� ������ �������� �������������, ��
��� ��������� �������� ���������� � ������ ������������. ��������,
����������� ����������� ������� ($x\mapsto x+1$) ��������
������������� �������� �������������� ���������~$\bbZ$
����� ����� (� ������������ ��������). ��� ���������
����������� ����� �� �� ������� �� ���� ������������
(��� �������� �������������).

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

% ---------------------------- �������� 58 ----------------------------------
\begin{problem}
        %
���������� ��������� $P(A)$ ���� ����������� ����������
$k$\� ����������� ���������~$A$, �������� �������������
�� ���������. ������� ����� ������������� ����� ���������.
        %
\end{problem}

\begin{problem}
        %
��������, ��� ��������� ����� ������������� �����, ��������
������������� ���������� \�� $x$~�����~$y$\��, ����� ���������
��������� �������������.
        %
\end{problem}

��� ��������� �������� �����������, �� �� ����������
������� ������������� �������� (�
���� �������~\ref{finite-linear-order} ��� ������ ���� ������������).

\begin{itemize}
        %
\item
�������~$[0,1]$ (� ������� ���������� �������)
�� ��������� ���������~$\bbR$, ��� ��� � �������
���� ���������� �������, � � ������� ���. (��� �����������
���������� �������, �����������, ������ ���������������
�����������.)
        %
\item
���������~$\bbZ$ (����� ����� � ������� ��������)
�� ��������� ���������~$\bbQ$ (������������ �����).
� ����� ����, ����� $\alpha\colon\bbZ\hm\to\bbQ$ �������� ������������.
����ͣ� ��� �������� �����
�����, ������, $2$ �~$3$.
��� �����������~$\alpha$ �� ������ ��������������� �����\� �� ���
������������ ����� $\alpha(2)$ �~$\alpha(3)$, ���ޣ�
$\alpha(2)\hm<\alpha(3)$, ��� ���~$2\hm<3$. �� ����� ������������
������ �����~$\alpha(2)$ �~$\alpha(3)$ ������ ���������������
����� ����� �����~$2$ �~$3$, ������� ���.{\looseness=-1\par}
        %
\item
����� ������� ������\� ���������~$\bbZ$ �~$\bbZ\hm+\bbZ$.
����ͣ� �~$\bbZ\hm+\bbZ$ ���
����� ���� (�� ��� � ������ ����������); �� ���������� ��~$0$ �~$\overline 0$.
��� ����~$0\hm<\overline 0$. ��� ����������� �� ������
��������������� ��� ����� ����� $a$ �~$b$, ���
�������~$a\hm<b$. ����� ���� ��������� ����� $0$ �~$\overline 0$ (�� ����������
�����: $1$, $2$, $3$, $\dots$, $-\overline3$, $-\overline2$, $-\overline1$)
������ ��������������� ����� ����� $a$ �~$b$\� �� �� ���� ��������
�����.{\looseness=-1\par}

���� ������ ������������� ���������� �� ���������� ���, ���
����� ������� ����� ���������� �������� ������ ��������
��������. ��� �������,
% ---------------------------- �������� 59 ----------------------------------
������������� ���������~$\bbZ$
�~$\bbZ\hm+\bbZ$ \�� ����������� ������������\��\index{������������
���������������}.
        %
\end{itemize}

\begin{problem}
        %
��������, ��� ������� �������������
���������~$\bbZ\hm\times\bbN$ �~$\bbZ\hm\times\bbZ$ (�
��������� ���� �� �.~\pageref{linear-cartesian-product} ��������) ��
���������.
        %
\end{problem}

\begin{problem}
        %
����� �� ��������� ������� �������������
���������~$\bbN\hm\times\bbZ$ �~$\bbZ\hm\times\bbZ$?
        %
\end{problem}

\begin{problem}
        %
����� �� ��������� ������� �������������
���������~$\bbQ\hm\times\bbZ$ �~$\bbQ\hm\times\bbN$?
        %
\end{problem}

�����������~$x\hm\mapsto \sqrt{2}x$ ������������ ���������� �����
�����������~$(0,1)$ �~$(0,\sqrt{2})$.
�� ��� �� ��� ������ ��������� ���������� �����
����������� ������������ ����� ���� ���������� (�� ����
�����~$\bbQ\hm\cap(0,1)$ �~$\bbQ\hm\cap(0,\sqrt{2})$), ���������
��������� ��~$\sqrt{2}$ ��������� ������������ ����� �
��������������. ��� �� ����� ���������� ��������� �����. ���
����� ���� ����� ������������ ������������������ ������������ �����
$0\hm<x_1\hm<x_2\hm<\dots$ � $0\hm< y_1\hm<y_2\hm<\dots$, ����������
�������������� �~$1$ �~$\sqrt{2}$ � ��������� �������\� ��������
�������~$f$, ������� ���������~$x_i$ �~$y_i$ � ������� �� ������
�� ��������~$[x_i,x_{i+1}]$ (���.~\ref{iso-1}).
����� ������, ��� ��� ����� �������
������������.
        %
\begin{figure}[ht]
$$
\epsffile{iso1.1}
$$
\caption{������� ������������ ����������.}
\label{iso-1}
\end{figure}
        %

\begin{problem}
        %
��������, ��� ��������� ������������ ����� ���������~$(0,1)$ �
���������~$\mathbb{Q}$ ���������. (��������: ����� ����
% ---------------------------- �������� 60 ----------------------------------
����� ��������� �������; �������, � ���� ������ ���� � ������ �������,
������� ���������� � ����, ��� �������~$x\hm\mapsto 1/x$ ���������
������������ ����� � ������������.)
        %
\end{problem}

\problskip
����� ������� ����������� ��������� � ���������
������ (������, ������ �����, ��� ��������� �� �����
�������~\ref{dense-countable-sets}, ��� �� ����������).


\begin{problem}
        %
��������, ��� ��������� �������\� ������������ �����%
\index{�����!�������\� ������������} ���������~$(0,1)$
��������� ���������~$\bbQ$. (����� ���������
\emph{�������\� ������������}, ���� ��� ����� ���~$m/2^n$, ���
$m$\� ����� �����, � $n$\� �����������.)
        %
\end{problem}

\problskip
��� �������� $x$, $y$ ������� �������������� ��������� ��������
\emph{���������}\index{�������� ��������}, ����~$x\hm<y$ � ��
���������� �������� �����
����, �� ���� ������~$z$, ���~$x\hm<z\hm<y$. ������� �������������
��������� �������� \emph{�������}\index{���������!�������},
���� � Σ� ��� ��������
��������� (�� ���� ����� ������ ����� ���� ������).

\begin{theorem}\label{dense-countable-sets}
        %
����� ��� �ޣ���� ������� ������� ������������� ��������� ���
����������� � ����������� ��������� ���������.
        %
\end{theorem}

\begin{proof}
        %
����� $X$ �~$Y$\� ������ ��� ���������. ��������� ����������
����� ���� �������� �� �����. ����� $n$~����� � ��� ���� ���
$n$\� ���������� ������������ $X_n\hm\subset X$ �~$Y_n\hm\subset Y$,
�������� ������� �� ����� �������� \�� �����������\��, �
������� ����������� ������������ ����� ����, �����������
�������. �� ��������� ���� �� ��ң� �����\� �� ������������
������� ������ ��
�������� (������, ���������~$X$) � ���������� ��� �� ����� �����������
����������~$X$. �� ����� ��������� ���� ������ ����,
���� ������, ���� ������� ����� ������\� �� �����. �
������ �� ������� �� ����� ����� ������������ ������� �~$Y$,
����������� � ��� �� ��������� (������ ����,
����� ������ � ������
���������� ������,
����� ������ � �������
���������� ������ \���).
��� ���� �� ���������� ���, ���
�~$Y$ ��� ����������� ��������, ��� ����������� � ��� ��������
���������,\� � ����������� �� ����, ����� �� �ң� ������� �����
�����. ����� ����� �� ��������� ��������� �������� � $X_n$ �~$Y_n$,
������ �� ���������������� ���� �����.

% ---------------------------- �������� 61 ----------------------------------
����� � �������
�������� ���������� ����� ����������� $X$ �~$Y$, �� ������
������������ � ���, ����� ��� �������� ����� �������� ���� ����
��� ������ ��������. ��� ����� ������� ���: ��������� ������
�� �������� �ޣ���, ����������� ��� �������� � ����� ��������
������������ ������� � ���������� ������� (�� ��ޣ���� �����\�
��~$X$, �� ޣ����\� ��~$Y$). ��� ����������� ���������
��������������.
        %
\end{proof}

\begin{problem}
        %
������� ���������� ������������ �ޣ�\-��� �������
������� ������������� �������� (��� ���������� � ����������
�������� ������ �� ��������). (�����:~$4$.)
        %
\end{problem}

\begin{problem}
        %
��������� ������ ���� ������� ������� ������������� ��������
�������� ��������� ��� ����������� � ����������� ���������,
�� ���������� �����������.
(��������: �������� ���������
$\mathbb{Q}\hm+\mathbb{R}$ �~$\mathbb{R}\hm+\mathbb{Q}$.)
        %
\end{problem}

\begin{theorem}
        \label{Q-universal}
������ �ޣ���� ������� ������������� ���������
��������� ���������� ������������ ���������~$\mathbb{Q}$.
        %
\end{theorem}

\begin{proof}
        %
������� ����� ��, ��� ������ ���������~$\mathbb{Q}$ ����� ���� �����
����� ������� �ޣ���� ����� ������� ��������� ��� �������
� ���������� ���������, ��� ��� ��� ��� ���������.

�������������� ����� ����������� ���������� ��� ��, ��� � �
�������~\ref{dense-countable-sets}\� � ��� ��������, ���
����� �������������� �������� ������� ������ � ����� �������
(�� ������� ��� ���������), � ���� � ��� ����������� �
��������� ������������ �����.
        %
\end{proof}

\begin{problem}
        %
����� ������ �������������� �������~\ref{Q-universal}, �������,
��� ����� ��������� $X$ ��������� ������������ ���������
$\bbQ\times X$.
        %
\end{problem}

\section{������������� ���������}\index{���������!�������������}
        \label{well-founded-sets}
        \index{������������� ���������}%

������� �������������� ��������\index{��������}
� ����� �� ��������� ���� ������ ���:
        %
\quot{%
        %
����� $A(n)$\� ��������� �������� ������������ �����~$n$. �����
��� ������� ��������~$A(n)$ � �������������, ��� $A(m)$ ����� ���
����~$m$, �������~$n$. ����� ��������~$A(n)$ ����� ���
���� ����������� �����~$n$.
        }

(�������, ��� �� ������� ��������������~$A(0)$ �������� ��� ������
�������������, ��������� ������� ��\-���~���.)

% ---------------------------- �������� 62 ----------------------------------
��� ����� �������� ������������� �������� ����� �����������
�������? ����� ������ ��������� ������� ��������:

\begin{theorem}
        \label{well-founded-induction}%
��������� ��� �������� �������� �������������� ���������~$X$
�����������:

(\textsf{�}) ����� �������� ������������~$X$ ����� �����������
�������;

(\textsf{�}) �� ���������� ����������� ������ ���������
������������������ $x_0\hm>x_1\hm>x_2\hm>\dots$ ��������� ���������~$X$;

(\textsf{�}) ��� ���������~$X$ ����� ������� �������� � ���������
�����: ���� (��� ������~$x\hm\in X$)
�� ����������~$A(y)$ ��� ����~$y\hm<x$ ������� ����������~$A(x)$,
�� ��������~$A(x)$ ����� ��� ����~$x$.
��������� ��� ���������� ���:
        $$
\forall x\, (\forall y \, ((y<x)\Rightarrow A(y))\Rightarrow A(x))
\Rightarrow
\forall x\, A(x).
        $$
\end{theorem}

\begin{proof}
        %
������� ������� ��������������� ������ ���� �������. ����
$x_0\hm>x_1\hm>x_2>\dots$\� ����������� ��������� ������������������,
��, ��������, ��������� ţ �������� �� ����� ������������
�������� (��� ������� �������� ��������� �ݣ ������).
������� ��~(�) �������~(�). ��������, ���� $B$\� ��������
���������, �� ������� ������������ ��������, �� �����������
��������� ������������������ ����� ��������� ���. ����ͣ�
������������ �������~$b_0\hm\in B$. �� �������������
�� �� �������� �����������, ��� ��� ����� �����~$b_1\hm\in B$,
��� ��������~$b_0\hm>b_1$. �� ��� �� �������� ����� ����� $b_2\hm\in B$,
��� ��������~$b_1\hm>b_2$ \��� ���������� ����������� ���������
������������������.

������ ������� ������� �������� �� ������������� ������������
�������� � ����� ������������. ����� $A(x)$\� ������������
�������� ��������� ���������~$X$, ������ �� ��� ���� ���������~$x$.
���������� �������� ���������~$B$ ��� ���������, ���
������� ��������~$A$ �������. ����� $x$\� ����������� �������
���������~$B$.
% ---------------------------- �������� 63 ----------------------------------
�� ������� ������� ��������� � ���������~$B$ ���,
������� ��� ����~$y\hm<x$ ��������~$A(y)$ ���������. �� ����� ��
������������� ������ ���� ��������� �~$A(x)$\�
������������.

�������� �������� ������������� ������������ �������� � �����
�������� ������������, ������ �� �������� ��������. ����� $B$\�
������������ ��� ����������� ���������. ������� ��
��������, ��� $B$~�����; ������� �������, � ��������~$A(x)$
����ͣ� ��������~$x\hm\notin B$. � ����� ����, ���� $A(y)$~�����
��� ����~$y\hm<x$, �� ������� �������, �������~$x$, ��
����� �~$B$. ���� �� $x$~����� �~$B$, �� ��
��� �� ��� �����������, � ����� ���.
        %
\end{proof}

���������, ���������� ���������� (�)\�(�), ����������
\emph{��������������}.
        \index{���������!�������������}%
        \index{������������� ���������}%
����� ���� ������� ������������� ��������? ������ �����,
��� �������� ������\� ��������� ����������� �����.

������ ������\� ���������~$\bbN\hm\times\bbN$
��� ����������� ����� (������ �� ����, � ������� ������
���� ������; � ������ ��������� ���������� ������).
� ����� ����, �������� �������~(�). ��� ����� ������
�������������� ��� ���: ������ ������������������
        $
u_0\hm\ge u_1\hm\ge u_2 \ge\ldots
        $
��������� ���������
���� ��� ������ ��������������� (��� �����, ������� �
����������, �����); ��������, ��� ��� �������������
������������.

����� ���� ������������ ������������������ ���
        $$
\langle x_0, y_0 \rangle \ge
\langle x_1, y_1 \rangle \ge
\langle x_2, y_2 \rangle \ge \dots
        $$
�� ����������� ������� (������� ������������ ������ �����)
$y_0\hm\ge y_1\hm\ge y_2\ge\ldots$ � ������ ������������������
����������� �����~$y_i$
� ������\� �� ����� �� ��������. ����� ����� ��� $x_i$~������
�������\� � ���� ���������������. ��� � �����������.

�� �� ����� ����������� �������� � � ����� ����� ��������.
        %
\begin{theorem}
        %
����� $A$ �~$B$\� ��� ������������� �������� �������������
���������. ����� �� ������������~$A\hm\times B$, � �������
        $$
\langle a_1, b_1 \rangle \le
\langle a_2, b_2 \rangle \Leftrightarrow
[(b_1 < b_2) \text{ ��� } (b_1=b_2 \text{ � } a_1\le a_2)],
        $$
% ---------------------------- �������� 64 ----------------------------------
�������� �������������.
        %
\end{theorem}

\begin{proof}
        %
� ������������������
$\langle a_0,b_0 \rangle \hm\ge
 \langle a_1,b_1 \rangle \ge\ldots$ ��������������� �������
������, � ����� � ������ �����.
        %
\end{proof}

������ �������� ����������� �����������
���~$\mathbb{N}\hm\times\mathbb{N}\times\mathbb{N}$, ���~$\mathbb{N}^k$
��� ������ ��� ������������ ��������� ����� �������������
��������.

�ݣ ����� ��������, ��� �����~$A+B$ ���� ������������� ��������
$A$ �~$B$ �����������: ������������������ $x_0\le x_1\le
x_2\le\dots$ ���� ������� ���������� �~$B$ (� �� ��������� ��
���������������~$B$), ���� �������� ������� ��~$A$. � ���������
������ ��� ��������� �������� ����� �����������~$A$, � ��
���������� ���������������~$A$.

\smallskip

����� � ���������������� (��� � ����������� �������) ��� �����
��������, ��� ��������� ������� �� ����� ������������ ����������
�����. ��������, ������� ����, �� ������ ���������, ��� ���� ���
������ �� ���� ������. ��� ����� ������� ���: ������ �����\� ��
����������� �������� � ���������, ��� �� ������ ���� ����� ����
�������� �����������. �����, ���� ������ ���� �������� �����~$N$,
�� ����� �������������, ��� �� ����� ��� ����� $N$~�����
���� ����������.

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

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

��������� �������� � ޣ���� ������: ������ ���� �� ����
ޣ��� ���� ������, � � ����� �������� ����� ����� ����� ��
������ ������, �� ��� ��� ������ �������� ����������� (�����
����� �������� �����). ������ (��� ��������) ������ � ������
����� ��������� �� �����. ����� ����� ������ �� ���������,
��������� �����������.
    %   ޣ��� ����   (if any)
��������, ��� ���� ��� ������ ޣ�� ��������, ����� �� �� ���
��������� ����� ����� � ����������.

% ---------------------------- �������� 65 ----------------------------------
�������: ����� ������� $k$~����� �����. ������� ��������
��������� ���: ���������, ������� ����� ������� ���� ���� �
���������� ($n_1$\� ����� ����� ������������ �����������,
$n_2$\� ����� ���������, � ��� ����� ��~$n_k$). �������, ��� �
���������� ������� � ޣ���� ����� $\langle n_1,\dots,n_k\rangle$
����������� (� ������ ���ģ����� ���� �������, ����� ��
���������� ������� ��������� �����, ����� ������������� \���).
��������� ���������~$\bbN^k$ �����������, ���� ������� ������
����������.

\problskip
\begin{problem}
        %
������� �������� ������������������ ����� � ������. �� ����
��� ����������� ������� ����� ��������: ����� � ��� ������ $01$
� �������� �� $100{\dots}00$ (��� ���� ����� �������� �������
������ �����). ��������, ��� ����� ���� ������ ��������� ����������
����� ���.
        %
\end{problem}

\begin{problem}
        %
���������� ��������� ���� ���� �������� �������� (������, ����
�������� ������������������� ������� ����, ���������� �� ������)
� ������������������ ��������
        \index{������������������ �������}%
(��.~�.~\pageref{lexicographic-ordering}). ����� �� ��� ���������
�����������?
        %
\end{problem}

\begin{problem}
        %
���������� ��������� �������������� �������������������
����������� �����, � �������
��� �����, ������� � ����������, ����� ����. ���ģ�
� Σ� ������� ���: ������� ���������� ������ �����,
��� ��������� ������ ������ \��� ��������, ���
��� (�������) ������������� ��������� �����������.
        %
\end{problem}

\begin{problem}
        %
���������� ��������� ���� ����������� �� ����� ����������~$x$,
������������ �������\� ����������� �����. ���������� ��� ���:
���������~$P$ ������ ����������~$Q$, ���� $P(x)\hm>Q(x)$ ���
���� ���������� �������~$x$. ��������, ��� ��� �����������
������ �������� ������� � ��� ������������ �������������
��������� �����������.
        %
\end{problem}
