set-theory.tex

\section{Наивная теория множеств}

\subsection{Множества}

\literature{[K1], гл. 1, \S~5, п. 1; [vdW], гл. 1, \S~1.}

Мы не будем давать точных определений основным понятиям теории
множеств, этим занимается аксиоматическая теория множеств. Наш подход
к теории множеств совершенно наивен; под множеством мы будем понимать
некоторый {\it набор} ({\it совокупность}, {\it семейство})
объектов~--- {\it элементов}. Природа этих объектов для нас не очень
важна: это могут
быть, скажем, натуральные числа, а могут быть другие
множества. Множество полностью определяется своими элементами. Иными
словами, два множества $A$ и $B$ равны тогда и только тогда, когда они
состоят из одних и тех же элементов: $x\in A$ тогда и только тогда,
когда $x\in B$.

Как задать множество? Самый простой способ~--- перечислить его
элементы следующим образом: $A=\{1,2,3\}$.
Сразу отметим, что каждый
объект $x$ может либо являться элементом данного множества $A$ (это
записывается так: $x\in A$), либо не
являться его элементом ($x\not\in A$); он не может быть элементом
множества $A$ <<два раза>>. Поэтому запись $\{1,2,1,3,3,2\}$ задает то
же самое множество, что и запись $\{1,2,3\}$, и запись $\{2,3,1\}$.

Прямое перечисление может задать только конечное множество. Для
задания бесконечных множеств можно использовать неформальную запись с
многоточием, например, $\mb N=\{0,1,2,3,\dots\}$~--- множество натуральных
чисел.

\begin{remark}
Мы будем считать, что $0$ является натуральным числом.
\end{remark}

В такой записи с многоточием мы предполагаем, что читатель понимает,
какие именно элементы имеются в виду. Многоточие может стоять и
справа, и слева: например, запись $\{\dots,-4,-2,0,2,4,\dots\}$ призвана
обозначать множество четных чисел.

Мы предполагаем также, что нам известны такие множества, изучающиеся в
школе, как множество вещественных чисел $\mb R$, множество
рациональных чисел $\mb Q$, множество целых чисел $\mb Z$.

Очень важный пример множества~--- пустое множество $\emptyset$. Это
такое множество, что высказывание $x\in\emptyset$ ложно для любого
объекта $x$.

Чуть более строгий способ задания множества: $A=\{s\in S\mid s\text{
  удовлетворяет свойству }P\}$; здесь вертикальная черта $\mid$
читается как <<таких, что>>, а $P$~--- то, что в математической
логике называется {\it предикатом}, то есть, высказыванием, которое
может для каждого объекта $s$ быть истинным или ложным. Для записи
предикатов (и вообще высказываний) полезны значки $\forall$ (<<для
любого>>), $\exists$ (<<существует>>) и $\exists!$ (<<существует
единственный>>). Эти значки называются {\it кванторами} и также имеют
строгий смысл, но для нас они будут служить просто сокращениями
интуитивно понятных фраз <<для любого>>, <<существует>> и <<существует
единственный>>. Например, $\forall x\in\mathbb N, x>-5$ и $\exists!
x\in\mathbb N, 3x=15$~--- истинные
высказывания, а $\forall x\in\mathbb N, x<20$~--- ложное.

Теперь мы можем более точным образом описать множество всех четных
чисел: $\{x\in\mb Z\mid \exists y\in\mb Z: x=2y\}$. Еще одно полезное
сокращение позволяет записать множество четных чисел так: $\{2x\mid
x\in\mb Z\}$. Множество четных чисел мы будем обозначать через $2\mb
Z$.

Обратите внимание, что порядок, в котором идут кванторы в
высказывании, чрезвычайно важен: высказывание $\forall x\in\mb Z\exists
y\in\mb Z:x=y+1$, очевидно, истинно (из любого целого числа можно
вычесть $1$). А вот высказывание $\exists y\in\mb Z\forall x\in\mb
Z:x=y+1$ означает существование такого загадочного целого числа $y$,
которое на единицу меньше любого целого числа. Понятно, что это
высказывание ложно.

На самом деле, запись  $\{s\in S\mid s\text{
  удовлетворяет свойству }P\}$ задает не просто множество, а
{\it подмножество} множества $S$. Если множество $T$ таково, что любой
элемент множества $T$ является и элементом множества $S$, то говорят,
что $T$ является подмножеством $S$ и пишут $T\subseteq S$. Более
строго, $T\subseteq S$ тогда и только тогда, когда из $x\in T$ следует
$x\in S$. Конструкцию <<из \dots следует \dots>> можно записывать
значком $\Rightarrow$; в определении подмножества тогда можно писать
$x\in T\Rightarrow x\in S$. Заметим, что стрелочка идет только в одну
сторону; если бы было верно и $x\in S\Rightarrow x\in T$, то множества
$S$ и $T$ совпадали бы. Таким образом, если $T\subseteq S$ и
$S\subseteq T$, то $S=T$, поскольку в этом случае $x\in
S\Leftrightarrow X\in T$; множества $S$ и $T$ состоят из
одних и тех же элементов.

Примеры: $\mb N\subseteq\mb Z\subseteq\mb Q\subseteq\mb R$. Кроме
того, $2\mb Z\subseteq\mb Z$. Более того, $\emptyset\subseteq X$ для
любого множества $X$: пустое множество является подмножеством любого
множества. В частности, $\emptyset\subseteq\emptyset$. Не следует
путать значки $\subseteq$ и $\in$: так, $\emptyset\not\in\emptyset$. К
тому же, слева от значка $\in$ может стоять объект любой природы, а
слева от значка $\subseteq$~--- только множество.

Следующее важное понятие~--- {\it мощность} множества. Неформально
говоря, это количество элементов в множестве. Мощность множества $X$
обозначается через $|X|$. Четко различаются два
случая: когда мощность множества конечна и когда она
бесконечна. Если мощность множества конечна, то она измеряется
натуральным числом (вообще говоря, это практически является
определением натурального числа). Например, $|\emptyset|=0$,
$|\{1,2,3\}|=|\{2,1,3,2,2,1\}|=3$. Когда мощность множества $X$ не является
натуральным числом, говорят, что $X$ бесконечно: $|X|=\infty$.
Если множество $X$ конечно, то любое его подмножество $Y$ также
конечно, и $|Y|\leq |X|$. Более того, если $Y$~--- подмножество
конечного множества $X$,
то $|Y|=|X|$ тогда и только тогда,
когда $Y=X$. Если же $Y\subseteq X$ и $Y\neq X$ (в этом случае
говорят, что $Y$~--- {\it собственное подмножество} $X$), то $|Y|<|X|$.

\subsection{Операции над множествами}

\literature{[K1], гл. 1, \S~5, п. 1; [vdW], гл. 1, \S~1.}

Операции над множествами предоставляют массу способов получать новые
множества из уже имеющихся. Мы обсудим по крайней мере следующие
операции:

\begin{itemize}
\item объединение $\cup$,
\item пересечение $\cap$,
\item разность $\setminus$,
\item симметрическая разность $\Delta$,
\item (декартово)  произведение $\times$,
\item несвязное объединение (копроизведение) $\coprod$,
\item факторизация $/$.
\end{itemize}

Пересечение $A\cap B$ множеств $A$ и $B$ состоит из всех элементов, лежащих и в
$A$, и в $B$. Более формально, $x\in A\cap B$ тогда и только тогда,
когда $x\in A$ и $x\in B$.

Объединение $A\cup B$ множеств $A$ и $B$ состоит из всех элементов,
лежащих в $A$ или в $B$ (возможно, и в $A$, и в $B$). Иначе говоря,
$x\in A\cup B$ тогда и только тогда, когда $x\in A$ или $x\in B$.

Разность $A\setminus B$ состоит из элементов $A$, не лежащих в $B$:
$A\setminus B=\{x\in A\mid x\not\in B\}$. Иначе говоря, $x\in
A\setminus B$ тогда и только тогда, когда $x\in A$ и $x\not\in B$.

Симметрическая разность $A$ и $B$ состоит из элементов, лежащих ровно
в одном из этих множеств. Это можно записать, например, так: $A\Delta
B=(A\cup B)\setminus(A\cap B)$.

Несвязное объединение $A\coprod B$ предназначено для того, чтобы
объединить два
множества $A$ и $B$ (которые, возможно, имеют непустое пересечение)
так, чтобы в результате элементы из $A$ и из $B$ <<не
перемешались>>: все элементы из $A$ оказались отличными от всех
элементов из $B$. Представьте, что элементы множества $A$ выкрашены в
красный цвет, а элементы $B$~--- в синий цвет. После этого они стали
все различны (их пересечение стало пустым), и мы рассмотрели их
объединение. Если множества $A$ и $B$ конечны, то $|A\coprod
B|=|A|+|B|$.

Произведение множества $A$ и $B$~--- это множество всех упорядоченных
пар $(a,b)$, где $a\in A$, $b\in B$. Запись $(a,b)$ означает, что мы
заботимся о порядке элементов $a,b$ (в отличие от записи
$\{a,b\}$): пара $(a,b)$, вообще говоря, не равна паре $(b,a)$, если
$a\neq b$. Более строго, $(a,b)=(a',b')$ тогда и только тогда, когда
$a=a'$ и $b=b'$.

Итак, $A\times B=\{(a,b)\mid a\in A,b\in B\}$. Например,
$$
\{1,2,3\}\times\{x,y\}=\{(1,x),(2,x),(3,x),(1,y),(2,y),(3,y)\}.
$$
В
школе изучают декартову плоскость, которая фактически представляет
собой квадрат вещественной прямой: $\mb R^2=\mb R\times\mb
R$. Заметим, что $|A\times B|=|A|\times |B|$ для конечных множеств
$A$, $B$.

Несложно обобщить понятия пересечения и объединения на несколько
множеств: $A_1\cap A_2\cap\dots\cap A_n$, $A_1\cup A_2\cup\dots\cup
A_n$. Например, $A_1\cap A_2\cap A_3\cap A_4=((A_1\cap A_2)\cap
A_3)\cap A_4$; и на самом деле порядок расстановки скобок в таком
выражении не имеет значения. Более интересно попробовать обобщить
понятие произведения; заметим, что $A_1\times (A_2\times A_3)$ не
равно $(A_1\times A_2)\times A_3$. Действительно, первое множество
состоит из упорядоченных пар, первый элемент которых лежит в $A_1$, а
второй является упорядоченной парой элементов из $A_2$ и $A_3$. В то
же время второе множество состоит из совершенно других упорядоченных
пар: первый их элемент является упорядоченной парой элементов из $A_1$
и $A_2$, а второй элемент лежит в множестве $A_3$. Но по аналогии с
упорядоченной парой можно определить {\it упорядоченную тройку} и
получить множество $A_1\times A_2\times A_3=\{(a_1,a_2,a_3)\mid a_1\in
A_1,a_2\in A_2,a_3\in A_3\}$ (не совпадающее ни с $A_1\times(A_2\times
A_3)$, ни с $(A_1\times A_2)\times A_3$!). Совершенно аналогично
определяется {\it упорядоченная $n$-ка} или {\it кортеж} из $n$
элементов $(a_1,\dots,a_n)$, что позволяет определить произведение
$A_1\times A_2\times\dots\times A_n$.

Несложно определить пересечение и объединение для произвольного (не
обязательно конечного) набора множеств: если $(A_i)_{i\in I}$~---
семейство множеств, проиндексированное некоторым индексным множеством
$I$, то $\bigcap_{i\in I}A_i$~--- пересечение множеств $A_i$~---
состоит из элементов, которые лежат в каждом $A_i$, а $\bigcup_{i\in
  I}A_i$~--- объединение множеств $A_i$~--- состоит из элементов,
которые лежат хотя бы в одном из $A_i$.

С помощью упорядоченных пар
мы можем более строго определить несвязное объединение множеств
$A$ и $B$: рассмотрим множества $\{0\}\times A$ и $\{1\}\times B$
(состоящие из <<покрашенных элементов>> $(0,a)$ для $a\in A$ и $(1,b)$
для $b\in B$). Теперь все элементы $(0,a)$ и $(1,b)$ уж точно
различны, и можно положить $A\coprod B=(\{0\}\times A)\cup(\{1\}\times
B)$.

\subsection{Отображения}

\literature{[K1], гл. 1, \S~5, п. 2, [vdW], гл. 1, \S~2.}

{\em Наивное определение}: \dfn{отображение}\index{отображение}
$f\colon X\to Y$
сопоставляет
каждому элементу $x\in X$ некоторый элемент $y\in Y$. При этом пишут
$y=f(x)$ или $x\mapsto y$ и $y$ называют \dfn{образом}\index{образ}
элемента $x$ при отображении
$f$. Вместе с каждым отображением нужно помнить его
\dfn{область определения}\index{область определения} $X$ и
\dfn{область значений}\index{область значений} $Y$; например,
отображения
$\mathbb N\to\mathbb N$, $x\mapsto x^2$ и $\mb R\to\mb R$, $x\mapsto
x^2$~--- два совершенно разных отображения.

Для каждого множества $X$ можно рассмотреть \dfn{тождественное
  отображение}\index{тождественное отображение} $\id_X\colon X\to X$,
переводящее каждый элемент $x\in X$ в $x$.

С каждым декартовым произведением $X\times Y$ множеств $X$ и $Y$
связаны отображения $\pi_1\colon X\times Y\to X$ и $\pi_2\colon
X\times Y\to Y$, определенные следующим образом: отображение $\pi_1$
сопоставляет паре $(x,y)$ элементов $x\in X$, $y\in Y$ элемент $x$, а
отображение $\pi_2$ сопоставляет этой паре элемент $y$. Эти
отображения называются \dfn{каноническими
  проекциями}\index{каноническая проекция}.

Пусть $f\colon X\to Y$~--- отображение, и $A\subseteq X$;
\dfn{образом}\index{образ} подмножества $A$ называется
множество образов всех элементов из $A$: $f(A)=\{y\in Y\mid \exists
x\in A\colon f(x)=y\}=\{f(x)\mid x\in A\}$. Если же $B\subseteq Y$,
можно посмотреть на все элементы $X$, образы которых лежат в
$B$. Получаем \dfn{(полный) прообраз}\index{прообраз} подмножества $B$:
$f^{-1}(B)=\{x\in X\mid f(x)\in B\}$. Вообще, говорят, что $x$
является прообразом элемента $y\in Y$, если $f(x)=y$; таким образом,
полный прообраз подмножества составлен из всех прообразов всех его
элементов.

%17.09.2014

Если $f\colon X\to Y$~--- отображение множеств и $A\subseteq X$, можно
определить \dfn{ограничение}\index{ограничение} отображения $f$ на
$A$. Это отображение,
которое мы будем обозначать через $f|_A$, из $A$ в $Y$, задаваемое,
неформально говоря, тем же правилом, что и $f$. Более точно,
$f|_A(x)=f(x)$ для всех $x\in A$.

Пусть теперь даны два отображения, $f\colon X\to Y$, $g\colon Y\to
Z$. Их \dfn{композиция}\index{композиция} $g\circ f$~--- это новое
отображение из $X$ в
$Z$, переводящее элемент $x\in X$ в $g(f(x))\in Z$. То есть, $(g\circ
f)(x)=g(f(x))$ для всех $x\in X$. Обратите внимание, что мы записываем
композицию справа налево: в записи $g\circ f$ сначала применяется $f$,
а потом $g$.

\begin{theorem}[Ассоциативность композиции]\label{thm_composition_associative}
Пусть $X,Y,Z,T$~--- множества, $f\colon X\to Y$, $g\colon Y\to Z$,
$h\colon Z\to T$. Тогда отображения $(h\circ g)\circ f$ и $h\circ
(g\circ f)$ из $X$ в $T$ совпадают.
\end{theorem}
\begin{proof}
Что значит, что два отображения совпадают? Во-первых, должны совпадать
их области определения и значений; и действительно, $(h\circ g)\circ
f$ и $h\circ (g\circ f)$ действуют из $X$ в $T$. Во-вторых, они должны
совпадать в каждой точке. Возьмем любой элемент $x\in X$ и проверим,
что $((h\circ g)\circ f)(x)=(h\circ (g\circ f))(x)$. Действительно,
$$((h\circ g)\circ f)(x)=(h\circ g)(f(x))=h(g(f(x)))$$
и
$$(h\circ(g\circ f))(x)=h((g\circ f)(x))=h(g(f(x))).$$
\end{proof}

Еще одно полезное свойство композиции: пусть $f\colon X\to Y$~---
отображение. Тогда $f\circ\id_X=\id_Y\circ f=f$. Действительно,
$(f\circ\id_X)(x)=f(\id_X(x))=f(x)$ и $(\id_Y\circ
f)(x)=\id_Y(f(x))=f(x)$.

Все отображения из множества $X$ в множество $Y$ образуют множество,
которое мы будем обозначать через $\Map(X,Y)$ или через
$Y^X$. Последнее обозначение связано с тем, что для конечных $X$, $Y$
имеет место равенство $|Y^X|=|Y|^{|X|}$. В частности, если
$X=\emptyset$, то существует ровно одно отображение из $X$ в $Y$:
$|Y^\emptyset|=1$. Если же, наоборот, $Y=\emptyset$, то для непустого
$X$ отображений из $X$ в $\emptyset$ вообще нет: точке из $X$ нечего
сопоставить. Таким образом, $\emptyset^X=\emptyset$ для непустого
$X$. Наконец, для пустого $Y$, как и для любого другого,
существует ровно одно отображение из $\emptyset$ в $Y$
(тождественное), поэтому $|\emptyset^\emptyset|=1$.

\begin{definition}
Пусть $f\colon X\to Y$~--- отображение.
\begin{enumerate}
\item
$f$ называется \dfn{инъективным отображением}, или
\dfn{инъекцией}\index{инъекция}, если из
$x_1\neq x_2$ следует, что $f(x_1)\neq f(x_2)$ для $x_1,x_2\in
X$. Иными словами, у каждого элемента $Y$ не более одного прообраза.
\item
$f$ называется \dfn{сюръективным отображением}, или
\dfn{сюръекцией}\index{сюръекция}, если
для каждого $y\in Y$ найдется $x\in X$ такой, что $f(x)=y$. Иными
словами, у каждого элеента $Y$ не менее одного прообраза.
\item
$f$ называется \dfn{биективным отображением}, или
\dfn{биекцией}\index{биекция}, если
оно инъективно и сюръективно.
\end{enumerate}
\end{definition}

\begin{example}
Обозначим через $\mb R_{\geq 0}$ множество неотрицательных
вещественных чисел: $\mb R_{\geq 0}=\{x\in\mb R\mid x\geq
0\}$. Рассмотрим четыре отображения
\begin{eqnarray*}
&&f_1\colon\mb R\to\mb R, x\mapsto x^2;\\
&&f_2\colon\mb R\to\mb R_{\geq 0}, x\mapsto x^2;\\
&&f_3\colon\mb R_{\geq 0}\to\mb R, x\mapsto x^2;\\
&&f_4\colon\mb R_{\geq 0}\to\mb R_{\geq 0}, x\mapsto x^2.
\end{eqnarray*}
\end{example}
Хотя эти отображения задаются одной и той же формулой (возведение в
квадрат), их свойства совершенно различны: $f_4$ биективно; $f_3$
инъективно, но не сюръективно; $f_2$ сюръективно, но не инъективно;
$f_1$ не инъективно и не сюръективно.

\begin{definition}\label{dfn:inverse-map}
Пусть $f\colon X\to Y$~--- отображение. Отображение $g\colon Y\to X$
называется \dfn{левым обратным}\index{обратное отображение!левое} к
$f$, если $g\circ f = \id_X$. Отображение $g\colon Y\to X$ называется
\dfn{правым обратным}\index{обратное отображение!правое} к $f$, если
$f\circ g = \id_Y$. Наконец, $g$ называется
\dfn{[двусторонним] обратным}\index{обратное отображение} к $f$, если
оно одновременно является левым обратным и правым обратным к $f$.
Отображение $f$ называется
\dfn{обратимым слева}\index{обратимое отображение!слева},
если у него есть левое обратное,
\dfn{обратимым справа}\index{обратимое отображение!справа}, если у
него есть правое  обратное, и просто
\dfn{обратимым}\index{обратимое отображение} (или
\dfn{двусторонне обратимым}\index{обратимое отображение!двусторонне}),
если у него есть обратное.
\end{definition}

\begin{lemma}\label{lemma:invertible_left_and_right}
Если у отображения $f\colon X\to Y$ есть левое обратное и правое
обратное, то они совпадают. Таким образом, отображение обратимо тогда
и только тогда, когда оно обратимо слева и обратимо справа.
\end{lemma}
\begin{proof}
Пусть у $f$ есть левое обратное $g_L$ и правое обратное $g_R$. По
определению это означает, что
$g_L\circ f=\id_X$ и $f\circ g_R = \id_Y$.
Рассмотрим отображение $(g_L\circ f)\circ g_R$. По теореме об
ассоциативности композиции~\ref{thm_composition_associative} оно равно
$g_L\circ (f\circ g_R)$. С другой стороны,
$(g_L\circ f)\circ g_R = \id_X\circ g_R = g_R$ и
$g_L\circ (f\circ g_R) = g_L\circ\id_Y = g_L$. Поэтому $g_L = g_R$.
\end{proof}

Покажем, что мы на самом деле уже встречали понятия левой, правой и
двусторонней обратимости под другими названиями.

\begin{theorem}\label{thm:sur-inj-reformulations}
Пусть $f\colon X\to Y$~--- отображение.
\begin{enumerate}
\item Пусть $X$ непусто. $f$ обратимо слева тогда и только тогда,
  когда $f$ инъективно.
\item $f$ обратимо справа тогда и только тогда, когда $f$ сюръективно.
\item $f$ обратимо тогда и только тогда, когда $f$ биективно.
\end{enumerate}
\end{theorem}
\begin{proof}
\begin{enumerate}
\item
Предположим, что $f$ обратимо слева, то есть, $g\circ f = \id_X$ для
некоторого $g\colon Y\to X$. Покажем инъективность $f$: пусть
$x_1,x_2\in X$ таковы, что $f(x_1) = f(x_2)$. Применяя $g$, получаем,
что $g(f(x_1)) = g(f(x_2))$. Но $g(f(x)) = (g\circ f)(x) = \id_X(x) =
x$ для всех $x\in X$, поэтому $x_1 = x_2$.

Обратно, предположим, что $f$ инъективно, построим к $f$ левое
обратное отображение $g\colon Y\to X$. В силу непустоты $X$ можно
выбрать некоторый элемент $c\in X$. Для определения отображения $g$
нам нужно задать его значение для каждого $y\in Y$. Возьмем $y\in Y$;
в силу инъективности найдется не более одного элемента $x\in X$
такого, что $f(x) = y$. Если такой элемент (ровно один) есть, положим
$g(y) = x$. Если же его нет, положим $g(y) = c$.
Проверим, что так определенное отображение $g$ действительно является
левым обратным к $f$. Действительно, для всякого $x_0\in X$ элемент
$f(x_0)$ лежит в $Y$, и есть ровно один элемент $x\in X$ такой, что
$f(x) = f(x_0)$~--- это сам $x_0$. Поэтому в силу нашего определения
$g(f(x_0)) = x_0 = \id_X(x_0)$. Мы получили, что для произвольного
$x_0\in X$ справедливо $(g\circ f)(x_0) = \id_X(x_0)$. Поэтому
$g\circ f = \id_X$.
\item
Предположим, что $f$ обратимо справа, то есть, $f\circ g = \id_Y$ для
некоторого $g\colon Y\to X$. Покажем сюръективность $f$; нужно
проверить, что для каждого $y\in Y$ найдется элемент $x\in X$ такой,
что $f(x) = y$. Действительно, положим $x = g(y)$. Тогда
$f(x) = f(g(y)) = (f\circ g)(y) = \id_Y(y) = y$.

Обратно, предположим, что $f$ сюръективно. Построим отображение
$g\colon Y\to X$ такое, что $f\circ g = \id_Y$. Для этого мы должны
определить $g(y)$ для каждого $y\in Y$. В силу сюръективности найдется
хотя бы один элемент $x\in X$ такой, что $f(x) = y$. Тогда положим
$g(y) = x$. Очевидно, что $f(g(y)) = y$ для всех $y\in Y$.

{\small
\begin{remark}\label{remark:axiom-of-choice}
На самом деле тот факт, что мы можем {\it одновременно} для каждого
$y\in Y$ выбрать один какой-нибудь элемент $x\in X$ со свойством
$f(x)=y$, и получится корректно заданное отображение, является одной
из аксиом теории множеств (она
называется~\dfn{аксиомой выбора}\index{аксиома выбора}). Фактически,
она равносильна как раз тому, что мы доказываем: обратимости справа
любого сюръективного отображения. Заметим, что при доказательстве
первого пункта теоремы такой проблемы не возникает: там при построении
левого обратного отображения мы либо выбираем единственный прообраз,
либо (в случае пустого прообраза) отправляем наш элемент в
фиксированный элемент $c$. Здесь же прообраз может быть огромным, и
возможность одновременно в огромном количестве прообразов выбрать по
одному элементу как раз и гарантируется аксиомой выбора. Мы не
обсуждаем строгую формализацию понятия множества, поэтому игнорируем
все проблемы, связанные с аксиомой выбора.
\end{remark}
}
\item Пусть $f$ обратимо. Тогда, очевидно, оно обратимо слева и
  обратимо справа. По доказанному выше, из этого следует, что $f$
  инъективно и сюръективно (заметим, что в доказательстве того, что из
  обратимости слева следует инъективность, мы не использовали
  предположение о непустоте $X$). Значит, $f$ биективно.

  Обратно, пусть $f$ биективно, то есть, инъективно и
  сюръективно. Предположим сначала, что $X$ непусто. Тогда, по
  доказанному выше, $f$ обратимо слева и обратимо справа. По
  лемме~\ref{lemma:invertible_left_and_right} из этого следует, что
  $f$ обратимо. Осталось рассмотреть случай, когда $X =
  \emptyset$. Покажем, что в этом случае и $Y = \emptyset$. Для этого
  вспомним, что $f$ сюръективно. По определению это означает, что для
  каждого $y\in Y$ найдется $x\in X$ такой, что $f(x) = y$. Если $Y$
  непусто, то для какого-нибудь элемента $y\in Y$ должен найтись
  элемент $x\in X$, а это невозможно, поскольку $X$ пусто. Мы
  показали, что $X = Y = \emptyset$; но в этом случае есть
  единственное отображение $f\colon X\to Y$ (тождественное), и
  единственное отображение $g\colon Y\to X$ будет обратным к нему.
\end{enumerate}
\end{proof}

Если $f\colon X\to Y$~--- некоторое отображение, можно рассмотреть его
\dfn{график}\index{график}
$$
\Gamma_f=\{(x,f(x))\mid x\in X\}\subseteq X\times Y.
$$
Это понятие помогает нам дать точное определение понятию
отображения. Нетрудно видеть, что график отображения $f$ однозначно
определяет само $f$. С другой стороны, какие подмножества $X\times Y$
могут быть графиками отображений из $X$ в $Y$? Нетрудно понять, что
над каждой точкой $x\in X$ должна находиться ровно одна точка $(x,y)$
из графика (у каждой точки $x$ есть ровно один образ). Это приводит
нас к следующему определению.

\begin{definition}
Упорядоченная тройка $(X,Y,\Gamma)$, где $X,Y$~--- множества и
$\Gamma\subseteq X\times Y$, называется
\dfn{отображением}\index{отображение} из $X$ в
$Y$, если
\begin{enumerate}
\item для любого $x\in X$ из того, что $(x,y_1)\in\Gamma$ и
$(x,y_2)\in\Gamma$, следует, что $y_1=y_2$;
\item для любого $x\in X$ существует $y\in Y$ такое, что
  $(x,y)\in\Gamma$.
\end{enumerate}
\end{definition}

\subsection{Бинарные отношения}

\literature{[K1], гл. 1, \S~6, п. 1.}

\begin{definition}
\dfn{Бинарным отношением}\index{отношение!бинарное} на множестве $S$
называется подмножество
$R\subseteq S\times S$. Если $(x,y)\in S$, говорят, что
\dfn{$x$ находится в отношении $R$ с $y$}\index{отношение}, и пишут
$xRy$.
\end{definition}

%24.09.2014

\begin{examples}\label{examples:relations}
Отношение $\geq$ на множестве $\mb R$: $\geq=\{(x,y)\in\mb R\times\mb
R\mid x\geq y\}$. Аналогично~--- на множестве $\mb Z$, или
на множестве $\mb N$. Отношения $\leq$, $>$, $<$ на тех же
множествах. Отношение равенства на $\mb R$: $\{(x,x)\mid x\in\mb
R\}$~--- аналогично на любом множестве.
Отношение делимости на целых числах (точное определение будет
дано во второй главе).
На множестве всех прямых на декартовой плоскости можно ввести
отношение параллельности и отношение перпендикулярности.
\end{examples}

Для визуализации отношений полезно рисовать их графики~---
изображать множества точек, координаты которых лежат в данном
отношении.

\subsection{Отношения эквивалентности}

\literature{[K1], гл. 1, \S~6, п. 2; [vdW], гл. 1, \S~5.}

Определение отношения достаточно общее; на практике встречаются
отношения,
удовлетворяющие некоторым из следующих свойств.

\begin{definition}
Пусть $R\subseteq X\times X$~--- бинарное отношение на множестве $X$.
\begin{enumerate}
\item $R$ называется \dfn{рефлексивным}\index{отношение!рефлексивное},
  если для любого $x\in X$
  выполнено $xRx$.
\item $R$ называется \dfn{симметричным}\index{отношение!симметричное},
  если для любых $x,y\in X$ из
  $xRy$ следует $yRx$.
\item $R$ называется \dfn{транзитивным}\index{отношение!транзитивное},
  если для любых $x,y,z\in X$
  из $xRy$ и $yRz$ следует $xRz$.
\item $R$ называется \dfn{отношением
    эквивалентности}\index{отношение!эквивалентности}, если оно
  рефлексивно, симметрично и транзитивно.
\end{enumerate}
\end{definition}

\begin{examples}
Посмотрим на примеры~\ref{examples:relations}.
Нетрудно видеть, что отношения $\geq$, $\leq$, $>$, $<$ на множестве
$\mb R$ транзитивны, но не симметричны. При этом отношения $\geq$ и
$\leq$ рефлексивны. Отношение равенства на любом множестве является
отношением эквивалентности. Отношение делимости рефлексивно и
транзитивно. Отношение параллельности прямых на плоскости (если
учесть, что прямая параллельна самой себе) является отношением
эквивалентности. Отношение перпендикулярности симметрично, но не
рефлексивно и не транзитивно.
\end{examples}

\begin{definition}\label{def_equiv_class}
Пусть $\sim$~--- отношение эквивалентности на множестве $X$. Для
элемента $x\in X$ рассмотрим множество $\{y\in X\mid y\sim x\}$. Мы
будем обозначать его через $\overline{x}$ или $[x]$ и называть
\dfn{классом эквивалентности}\index{класс эквивалентности} элемента $x$.
\end{definition}

\begin{theorem}[О разбиении на классы эквивалентности]\label{thm_quotient_set}
Пусть $\sim$~--- отношение эквивалентности на множестве $X$.
Тогда $X$ разбивается на классы эквивалентности, то есть, каждый
элемент множества $X$ лежит в каком-то классе, и любые два класса либо
не пересекаются, либо совпадают.
\end{theorem}
\begin{proof}
Из рефлексивности следует, что $x\in\overline{x}$, поэтому каждый
элемент лежит в каком-то классе. Пусть $\overline{x}$ и
$\overline{y}$~--- два класса эквивалентности и
$\overline{x}\cap\overline{y}\neq\emptyset$. Выберем
$z\in\overline{x}\cap\overline{y}$; тогда $z\sim x$ и $z\sim
y$. Докажем, что на самом деле $\overline{x}=\overline{y}$, проверив
включения в обе стороны. Возьмем $t\in\overline{x}$; тогда $t\sim
x$, $x\sim z$, $z\sim y$, откуда $t\sim y$, то есть,
$t\in\overline{y}$. Поэтому
$\overline{x}\subseteq\overline{y}$. Аналогично,
$\overline{y}\subseteq\overline{x}$.
\end{proof}

\begin{definition}\label{def_quotient_set}
Пусть $\sim$~--- отношение эквивалентности на множестве $X$.
Множество всех классов эквивалентности элементов $X$ называется
\dfn{фактор-множеством}\index{фактор-множество} множества $X$ по
отношению $\sim$ и
обозначается через $X/\sim$. Отображение $\pi\colon X\to X/\sim$,
сопоставляющее каждому элементу $x\in X$ его класс эквивалентности
$\overline{x}$, называется
\dfn{канонической проекцией}\index{каноническая проекция} множества
$X$ на фактор-множество $X/\sim$. Нетрудно видеть, что это отображение
сюръективно.
\end{definition}

\subsection{Метод математической индукции}

\literature{[K1], гл. 1, \S~7; [vdW], гл. 1, \S~3; [B], гл. 1, п. 2.}

Пусть $P(n)$~--- набор высказываний, зависящий от натурального
параметра $n$. \dfn{Принцип математической индукции}\index{принцип
  математической индукции} гласит, что если
$P(0)$
истинно (\dfn{база индукции}\index{база индукции}) и для любого
натурального $k$ из истинности $P(k)$ следует истинность
$P(k+1)$ (\dfn{индукционный переход}\index{индукционный переход}), то
$P(n)$
истинно для всех натуральных $n$.

Эквивалентная переформулировка принципа математической индукции
гласит, что в любом непустом множестве натуральных чисел есть
минимальный элемент. Этот принцип (или какой-то равносильный ему), как
правило, принимается за аксиому в современных аксиоматиках натуральных
чисел.

Покажем, что если в любом непустом множестве натуральных чисел есть
минимальный элемент, то принцип математической индукции
выполняется. Будем действовать от противного: предположим, что $P(0)$
истинно, и для любого $k\in\mb N$ из истинности $P(k)$ следует
истинность $P(k+1)$, но, в то же время, $P(n)$ истинно не для всех
$n$. Пусть $A\subseteq\mb N$~--- множество натуральных чисел $n$, для
которых $P(n)$ ложно; оно непусто по нашему предположению.
Тогда в $A$ есть минимальный элемент $a$. Если $a=0$, то $P(0)$ ложно
(поскольку $a\in A$), что противоречит базе индукции. Если же $a>0$,
то $a-1$ также является натуральным числом, и $a-1\notin A$ в силу
минимальности. Поэтому $P(a-1)$ истинно. Но тогда из индукционного
перехода следует, что и $P(a) = P((a-1)+1)$ истинно~--- противоречие.

Принципа математической индукции равносилен следующему
принципу полной индукции: пусть
$P(n)$~--- набор высказываний, зависящий от натурального параметра
$n$. Если $P(0)$ истинно и из истинности $P(0), P(1),\dots,P(k)$
следует истинность $P(k+1)$, то $P(n)$ истинно для всех натуральных $n$.

\subsection{Операции}

\literature{[K1], гл. 4, \S~1, п. 1.}

\begin{definition}
Пусть $X$~--- множество. \dfn{Бинарной
  операцией}\index{операция!бинарная} на множестве $X$
называется отображение $X\times X\to X$.
\end{definition}

\begin{examples}
Отображения $\mb R\times\mb R\to\mb R$, задаваемые формулами
$(a,b)\mapsto a+b$, $(a,b)\mapsto ab$, $(a,b)\mapsto a-b$, являются
бинарными операциями. Отображение $(a,b)\mapsto a^b$ является бинарной
операцией на множестве $\mb N$.
\end{examples}

\begin{definition}
Пусть $\ph\colon X\times X\to X$~--- бинарная операция на множестве $X$.
\begin{enumerate}
\item Операция $\ph$ называется
\dfn{ассоциативной}\index{операция!ассоциативная}\index{ассоциативность}, если
$\ph(\ph(a,b),c)=\ph(a,\ph(b,c))$ выполняется для всех
$a,b,c\in X$.
\item Операция $\ph$ называется
  \dfn{коммутативной}\index{операция!коммутативная}\index{коммутативность},
  если
  $\ph(a,b)=\ph(b,a)$ выполняется для всех $a,b\in X$.
\end{enumerate} 
\end{definition}
Нетрудно видеть, что операции сложения и умножения на множестве
вещественных чисел являются ассоциативными и коммутативными, а вот
возведение в степень
натуральных чисел не является ни
ассоциативной, ни коммутативной операцией.

\begin{definition}
Пусть $\bullet$~--- бинарная операция на множестве $X$. 
Элемент $e\in X$ называется
\dfn{левым нейтральным}\index{нейтральный элемент!левый}
(или \dfn{левой единицей}\index{единица!левая}) по отношению к операции
$\bullet$, если $e\bullet x = x$ для любого $x\in X$. Элемент $e\in X$
называется
\dfn{правым нейтральным}\index{нейтральный элемент!правый} (или
\dfn{правой единицей}\index{единица!правая}) по
отношению к $\bullet$, если
$x\bullet e = x$ для любого $x\in X$. Элемент $e\in X$ называется
\dfn{нейтральным}\index{нейтральный элемент} (или
\dfn{единицей}\index{единица}), если он одновременно является
левым и правым нейтральным.
\end{definition}

Отметим, что бинарная операция возведения в степень на множестве
$\mb R$ обладает правой единицей (это $1$: действительно, $a^1 = a$),
но не обладает левой единицей.

\begin{lemma}
Если $\bullet\colon X\times X\to X$~--- бинарная операция,
и в $X$ есть правая единица и левая единица относительно
$\bullet$, то они совпадают.
\end{lemma}
\begin{proof}
Действительно, если $e_L\in X$~--- левая единица, а $e_R\in X$~---
правая единица, то по определению левой единицы выполнено $e_L\bullet
e_R = e_R$, а по определению правой единицы выполнено $e_L\bullet e_R
= e_L$. Поэтому
$e_L = e_L\bullet e_R = e_R$.
\end{proof}

\begin{definition}
Пусть $\bullet$~--- бинарная операция на множестве $X$, и в $X$ есть
нейтральный элемент $e$ относительно этой операции.
Пусть $x\in X$. Элемент $y\in X$ называется
\dfn{левым обратным}\index{обратный элемент!левый}
(относительно операции $\bullet$) к $x$, если $yx = e$.
Элемент $y\in X$ называется
\dfn{правым обратным}\index{обратный элемент!правый} (относительно
операции $\bullet$) к $x$, если $xy = e$.
Если $y\in X$ одновременно является левым и правым обратным к
$x$, то он называется просто \dfn{обратным}\index{обратный элемент} к
$x$. Элемент $x$ называется
\dfn{обратимым слева}\index{обратимый элемент!слева},
если у него есть левый
обратный, \dfn{обратимым справа}\index{обратимый элемент!справа},
если у него есть правый обратный, и
\dfn{обратимым}\index{обратимый элемент}, если у него есть обратный.
\end{definition}

\begin{lemma}
Пусть $\bullet$~--- бинарная операция на множестве $X$, и в $X$ есть
нейтральный элемент $e$ относительно это операции. Предположим, что
операция $\bullet$ ассоциативна. Пусть элемент $x$ обратим слева и
обратим справа. Тогда он обратим. Иными словами, если у элемента есть
левый и правый обратный относительно ассоциативной операции, то они
совпадают.
\end{lemma}
\begin{proof}
Пусть $y_L$~--- левый обратный к $x$, а $y_R$~--- правый обратный к
$x$. По определению это означает, что $y_L\bullet x = e$
и $x\bullet y_R = e$. Но тогда
$$
y_R = e\bullet y_R = (y_L\bullet x)\bullet y_R = y_L\bullet (x\bullet y_R) =
y_L\bullet e = y_L
$$
(обратите внимание, что в середине мы воспользовались ассоциативностью
операции $\bullet$).
\end{proof}

Пусть на $X$ задана бинарная операция $\bullet$, и $a,b,c\in
X$. Выражение $a\bullet b\bullet c$ не определено: для его однозначной
интерпретации необходимо расставить скобки, и получится либо
$(a\bullet b)\bullet c$, либо $a\bullet (b\bullet c)$. Если операция
$\bullet$ ассоциативна, то результат вычисления этих двух выражений
одинаков. Пусть теперь $a,b,c,d\in X$. Скобки в выражении $a\bullet
b\bullet c\bullet d$ можно расставить уже пятью вариантами:
$$
((a\bullet b)\bullet c)\bullet d,\quad
(a\bullet (b\bullet c))\bullet d,\quad
(a\bullet b)\bullet (c\bullet d),\quad
a\bullet((b\bullet c)\bullet d),\quad
a\bullet (b\bullet (c\bullet d)).
$$
Оказывается, что если операция $\bullet$ ассоциативна, то результат
вычисления всех этих выражений одинаков.
Аналогично, в выаржении любой длины для указания порядка, в котором
выполняются операции, необходимо расставить скобки. Оказывается, для
ассоциативной операции результат выполнения
не зависит от порядка расстановки скобок. Это
свойство называется \dfn{обобщенной
  ассоциативностью}\index{ассоциативность!обобщенная}. Поэтому для
ассоциативных операций ставить скобки в подобных выражениях не
обязательно.

\begin{theorem}
Если на множестве $X$ задана ассоциативная операция $\bullet$, то она
обладает обобщенной ассоциативностью: результат вычисления выражения
$x_1\bullet x_2\bullet\dots\bullet x_n$ не зависит от расстановки в
нем скобок.
\end{theorem}
\begin{proof}
Будем доказывать индукцией по $n$. База $n=3$ является определением
ассоциативности. Пусть теперь $n>3$, и для всех меньших $n$ теорема
уже доказана.
Достаточно показать, что результат при любой расстановке скобок
совпадает с результатом при следующей расстановке, в которой все скобки
<<сдвинуты влево>>
$$
(\dots ((x_1\bullet x_2)\bullet x_3)\bullet\dots\bullet x_n).
$$
Возьмем произвольную расстановку и посмотрим на действие, которое
выполняется последним: оно состоит в перемножении некоторого выражения
от $x_1,\dots,x_k$ и некоторого выражения от $x_{k+1},\dots,x_n$:
$$
(\dots x_1\bullet\dots\bullet x_k\dots) \bullet
(\dots x_{k+1}\bullet\dots\bullet x_n\dots).
$$
При этом $1 \leq k < n$.

Предположим сначала, что $k = n-1$. Тогда последняя операция состоит в
перемножении скобки, в которой стоят $x_1,\dots,x_{n-1}$, на $x_n$. В
выражении от $x_1,\dots,x_{n-1}$ мы можем, по предположению индукции,
сдвинуть все скобки влево, не меняя результата. Приписывая справа
$x_n$, получаем как раз выражение нужного вида уже от
$x_1,\dots,x_n$, и доказательство закончено.

Пусть теперь $k<n-1$. Заметим, что во второй скобке стоят
$x_{k+1},\dots,x_n$~--- здесь хотя бы два элемента, и меньше, чем
$n$. По предположению индукции мы можем расставить в этом выражении
скобки нашим выбранным способом, не меняя результата:
$$
\underbrace{\left(\dots x_1\bullet\dots\bullet x_k\dots\right)}_{A} \bullet
(\underbrace{(\dots (x_{k+1}\bullet x_{k+2})\bullet\dots\bullet x_{n-1})}_B\bullet\underbrace{x_n}_C)
$$
(тут нужно отметить, что рассуждение работает и при $k=n-2$; в этом
случае во второй скобке стоит лишь два элемента, и формально мы не
можем применить предположение индукции, но в этом нет ничего страшного).
Применим теперь ассоциативность к полученному выражению вида
$A\bullet (B\bullet C)$ и заменим его на $(A\bullet B)\bullet C$:
$$
(\underbrace{\dots x_1\bullet\dots\bullet x_k\dots}_{A} \bullet
\underbrace{\dots (x_{k+1}\bullet x_{k+2})\bullet\dots\bullet x_{n-1}}_B)\bullet\underbrace{x_n}_C)
$$
Заметим, что теперь последняя выполняемая операция~--- умножения
некоторого выражения от переменных $x_1,\dots,x_{n-1}$ на $x_n$. Это
означает,
что мы свели задачу к уже разобранному случаю $k=n-1$; теперь можно,
как и выше, воспользоваться предположением индукции, расставить скобки
в выражении от $x_1,\dots,x_{n-1}$ нужным образом, и мы сразу получим
необходимую расстановку.
\end{proof}