main.tex

\documentclass[12pt,a4paper]{article}
\usepackage{../.tex/mcs-notes}
\usepackage{stmaryrd}
\usepackage{todonotes}

\settitle
{Основы наивной теории множеств.}
{\href{https://users.math-cs.spbu.ru/~speranski}{Станислав Олегович Сперанский}}
{naive-set-theory/main.pdf}
\date{}

\newcommand{\subsets}{\ensuremath{\mathcal{P}}\xspace}
\newcommand{\finsubsets}{\ensuremath{\mathcal{P_{\mathrm{fin}}}}\xspace}
\DeclareMathOperator{\Ind}{Ind}
\DeclareMathOperator{\dom}{dom}
\DeclareMathOperator{\range}{range}
\DeclareMathOperator{\Min}{Min}
\DeclareMathOperator{\Seq}{Seq}
\DeclareMathOperator{\Left}{left}
\DeclareMathOperator{\Right}{right}
\DeclareMathOperator{\IS}{IS}
\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\Ord}{Ord}
\DeclareMathOperator{\card}{card}
\DeclareMathOperator{\Card}{Card}
\newcommand{\ZF}{\ensuremath{\mathrm{ZF}}\xspace}
\newcommand{\ZFC}{\ensuremath{\mathrm{ZFC}}\xspace}
\newcommand{\CH}{\ensuremath{\mathrm{CH}}\xspace}

\begin{document}
    \maketitle

    \listoftodos[TODOs]

    \tableofcontents

    \vspace{2em}
    Материалы лекций: \href{https://users.math-cs.spbu.ru/~speranski/courses/sets-2020-autumn/materials.html}{ссылка}
    \todo[color=green!40, inline]{Добавить конспекты теории из упражнений. Слить аккуратно воедино. Добавить ссылку на упражнения.}
    
    Литература:
    \begin{itemize}
        \item K. Hrbacek and T. Jech. Introduction to Set Theory. 3rd ed., revised and expanded. Marcel Dekker, Inc., 1999.
        \item T. Jech. Set Theory. 3rd ed., revised and expanded. Springer, 2002.
    \end{itemize}

    \section{Аксиоматика}

    Будем рассматривать как базовые выражения ``$x$ равен (совпадает с) $y$'' (``$x=y$'') ``$x$ лежит в $y$'' (``$x\in y$'').

    \begin{definition}[Наиваная схема аксиом выделения]
        Пусть $\Phi(x)$ --- произвольное условие на объекты. Тогда существует $X$, что $\forall u (\Phi(u) \leftrightarrow u \in X)$. В этом случае $X$ обозначается как $\{u \mid \Phi(u)\}$.
    \end{definition}

    \begin{statement}[парадокс Рассела]
        Пусть $R = \{u \mid u \notin u\}$. Тогда $R$ не может лежать в себе и не может не лежать в себе одновременно.
    \end{statement}

    \begin{statement}[парадокс Берри]
        Пусть $n$ --- наименьшее натуральное число, которое нельзя описать менее чем одиннадцатью словами. Тогда $n$ описывается 10 словами.
    \end{statement}

    Из-за данного парадокса будем рассматривать только условия, образованные переменными и $\in$, $=$, $\neg$, $\wedge$, $\vee$, $\leftarrow$, $\leftrightarrow$, $\forall$, $\exists$.

    \begin{definition}[аксиомы \ZFC (= \ZF (аксиомы Цермело-Френкеля) + C (аксиома выбора))]\ 
        \begin{description}
            \item[Ext)] ``Аксиома экстенциональности'':
                \[\forall X \forall Y (\forall u (u \in X \leftrightarrow u \in Y) \leftrightarrow X=Y)\]
            \item[Empty)] ``Аксиома пустого множества'':
                \[\exists \varnothing\; \forall u\, (u \notin \varnothing)\]
            \item[Pair)] ``Аксиома пары'':
                \[\forall X\, \forall Y\; \exists Z (\forall u\, (u \in Z \leftrightarrow (u = X \vee u = Y)))\]
                Обозначение: $Z = \{X, Y\}$.
            \item[Sep)] ``Схема аксиом выделения'':
                \[\forall \Phi(x)\quad \forall X\, \exists Y\; \forall u\, (u\in Y \leftrightarrow (u \in X \wedge \Phi(u)))\]
                Обозначение: $Y = \{u \in X \mid \Phi(u)\}$.

                \begin{corollary*}
                    Операторы
                    \begin{align*}
                        X \cap Y &:= \{u \mid u \in X \wedge u \in Y\}\\
                        X \setminus Y &:= \{u \in X \mid u \notin Y\}\\
                        \bigcap X &:= \{u \mid \forall v \in X \quad u \in v\}
                    \end{align*}
                    определены корректно.
                \end{corollary*}
            \item[Union)] ``Аксиома объединения'':
                \[\forall X\, \exists Y\; \forall u\, (u \in Y \leftrightarrow \exists v\, (v \in X \wedge u \in v))\]
                Обозначение: $Y=\bigcup X$.

                \begin{corollary*}
                    Оператор
                    \[
                        X \cup Y := \bigcup \{X, Y\} = \{u \mid u \in X \wedge u \in Y\}
                    \]
                    определён корректно.
                \end{corollary*}
            \item[Power)] Пусть $x \subseteq y := \forall v\, \{v \in x \rightarrow v \in y\}$. ``Аксиома степени'':
                \[
                    \forall X\, \exists Y\; \forall u\, (u \in Y \leftrightarrow u \subseteq X)
                \]
                Обозначение: $Y = \subsets(X) := \{u \mid u \subseteq X\}$.
                $\subsets(X)$ --- ``множество-степень X'' или ``булеан X''.

                \begin{definition}
                    Упорядоченная пара --- это объект от некоторых $X_1$ и $Y_1$, который равен другому такому объекту от $X_2$ и $Y_2$ тогда и только тогда, когда $X_1 = X_2 \wedge Y_1 = Y_2$.
                \end{definition}

                \begin{definition}
                    \emph{Декартово произведение} $X$ и $Y$ ($X \times Y$) --- $\{(x; y) \mid x \in X \wedge y \in Y\}$. 
                \end{definition}

                \begin{remark}
                    Можно несложно показать, что декартово произведение определено корректно.
                \end{remark}
            \item[Inf)] Пусть $\Ind(X) := \varnothing \in X \wedge \forall u\, (u \in X \wedge u \cup \{u\} \in X)$. Если $\Ind(X)$, то $X$ называется индуктивным. ``Аксиома бесконечности'': существует индуктивное множество.
            \item[Repl)] ``Схема аксиом подстановки'':
                \begin{align*}
                    \forall \Phi(x, y)\;&\\
                    &\forall x\, \forall y_1\, \forall y_2\, ((\Phi(x, y_1) \wedge \Phi(x, y_2)) \rightarrow y_1 = y_2) \rightarrow\\
                    &\forall X\, \exists Y\; \forall y\, (y \in Y \leftrightarrow \exists x (x \in X \wedge \Phi(x, y)))
                \end{align*}
            \item[Reg)] ``Аксиома регулярности'':
                \[
                    \forall X\, (X\neq \varnothing \rightarrow \exists u\, (u\in X \wedge X \cap u = \varnothing))
                \]
        \end{description}
    \end{definition}

    \section{Отношения}

    \begin{definition}
        \emph{Бинарное (или двухместное) отношение} $R$ между $X$ и $Y$ --- подмножество $X \times Y$. Если $Y = X$, $R$ называется \emph{бинарным (или двухместным) отношением} на $X$.\\
        Обозначение: $(x, y) \in R \Leftrightarrow xRy$.
    \end{definition}

    \begin{definition}
        \begin{align*}
            \dom(R) &:= \{u \in X \mid \exists v\quad uRv\}&& \text{``область определения $R$''}\\
            \range(R) &:= \{v \in Y \mid \exists u\quad uRv\}&& \text{``область значений $R$''}\\
            R[U] &:= \range(R \cap (U \times Y))\\
            R^{-1} &:= \{(y, x) \mid (x, y) \in R\}
        \end{align*}
    \end{definition}

    \begin{remark}
        \begin{align*}
            \range(R) = \dom&(R^{-1}) = R[X]\\
            \range(R^{-1}) = \dom&(R) = R^{-1}[Y]
        \end{align*}
    \end{remark}

    \begin{definition}
        Бинарные отношения можно естественным образом комбинировать: для любых отношений $R$ и $Q$ между $X$ и $Y$, $Y$ и $Z$ соответственно отношение
        \[
            S = R \circ Q := \{(x, z) \in X \times Z \mid \exists y: xRy \wedge yQz\}
        \]
        называется композицией $R$ и $Q$.
    \end{definition}

    \begin{definition}
        \emph{Тождественное отображение} на $X$ --- $id_X := \{(x, x) \mid x \in X\}$.
    \end{definition}

    \begin{remark}
        Тождественное отображение при композиции (не важно, правой или левой) с другим отношением не меняет его. 
    \end{remark}

    \begin{definition}
        Отношение $R$ между $X$ и $Y$ называется функциональным, если
        \[
            \forall x\; \forall y_1\, \forall y_2\, ((xRy_1 \wedge xRy_2) \rightarrow y_1 = y_2).
        \]
    \end{definition}

    \begin{definition}
        \emph{Функция} из $X$ в $Y$ --- функциональное отношение $R$ между $X$ и $Y$, в котором $\dom(R)=X$. Обозначение: $R: X \to Y$.
    \end{definition}

    \begin{definition}
        \emph{Ограничение} или \emph{сужение} функции $f: X \to Y$ на $U \subseteq X$ --- функция $f\upharpoonright_U := f \cap (U \times Y)$.
        
        Если $f: X \to Y$ и $g: U \to Y$, где $U \subseteq X$, таковы, что $f\upharpoonright_U = g$, то $f$ называется \emph{расширением} $g$, а $g$ --- \emph{ограничением} $f$.
    \end{definition}

    \begin{definition}
        $Y^X := \{f: X \to Y\}$.
    \end{definition}

    \begin{definition}
        Функция $f: X \to Y$ называется 
        \begin{itemize}
            \item \emph{сюръекцией},  если $range(f) = Y$;
            \item \emph{инъекцией}, если $f^{-1}$ функционально;
            \item \emph{биекцией}, если $f$ сюръективно и инъективно.
        \end{itemize}
    \end{definition}

    \begin{itemize}
        \item[C)] ``Аксиома выбора'':
            \[\forall X (\varnothing \notin X \to \exists f (f: X \to \bigcup X \wedge \forall u \in X (f(u) \in u)))\]
    \end{itemize}

    \section{Натуральные числа и индукция}

    Важным следствием Inf является
    \begin{align*}
        \exists X (\Ind(X) \wedge \forall Y (\Ind(Y) \to X \subseteq Y))&& \text{(Nat)}
    \end{align*}

    Nat описывает минимальное по включению индуктивное множество --- $\NN$, $\aleph_0$ или $\omega$.

    \begin{proof}[Вывод Nat из Inf]
        Пусть есть какое-то индуктивное $X_0$. Тогда рассмотрим
        \[\NN := \{x \in X_0 \mid \forall X (\Ind(X) \to x \in X)\}\]

        По построению $\Ind(X) \rightarrow \NN \subseteq X$. Также $\Ind(\NN)$.
    \end{proof}

    \begin{definition}
        Определим \emph{функцию последователя} $s: \NN \to NN$ как
        \[s := \{(n, m) \in \NN \times \NN \mid m = n \cup \{n\}\}\]
        Вместо $s(n)$ часто пишут $n+1$.
    \end{definition}

    \begin{definition}
        \emph{(Естественный) порядок} на $\NN$ --- $< := \{(n, m) \in \NN^2 \mid n \in m\}$.
    \end{definition}

    \begin{remark}
        Для всех $n, m \in \NN$ верно:
        \begin{enumerate}
            \item $\neg (n < 0)$;
            \item $n < m + 1 \leftrightarrow (n < m \vee n = m)$.
        \end{enumerate}
    \end{remark}

    \begin{theorem}[принцип индукции]
        Пусть $X$ удовлетворяет условию
        \[0 \in X \wedge \forall n \in \NN (n \in X \rightarrow n + 1 \in X).\]
        Тогда $\NN \subseteq X$.
    \end{theorem}

    \begin{proof}
        Из условия на $X$ следует, что $\NN \cap X$ индуктивно. Тогда из определения $\NN$ следует, что $\NN \subseteq \NN \cap X \subseteq X$, значит $\NN \subseteq X$.
    \end{proof}

    \begin{remark}
        В качестве $X$ могут быть $\{n \in \NN \mid \Phi(n)\}$.
    \end{remark}

    \begin{corollary}
        $\forall n \in \NN$ верно $n \subseteq \NN$.
    \end{corollary}

    \begin{theorem}[возвратная индукция]
        Пусть дан $X$, что $\forall n \in \NN (\forall m < n\; m \in X \rightarrow n \in X)$. Тогда $\NN \subseteq X$.
    \end{theorem}

    \begin{proof}
        Докажем, что $\forall n \in \NN n \subseteq X$, по индукции. База для $0$ очевидна. Шаг очевиден, так как $n \subseteq X$, значит $n \in X$, значит $n + 1 \subseteq X$.  
    \end{proof}

    \begin{definition}
        $\Min(X) := \{x \in X \mid \neg \exists u \in X u \in x\}$.
    \end{definition}

    \begin{theorem}[принцип минимального элемента]
        Если $X \subset \NN$ и $X \neq \varnothing$, то $\Min(X) \neq \varnothing$.
    \end{theorem}

    \begin{proof}
        Пусть $\Min(X) = \varnothing$. Возьмём $Y := \NN \setminus X$. Заметим, что
        \[\forall n \in \NN (\forall m < n\; m \in Y \rightarrow n \in Y)\]
        Тогда по принципу возвратной индукции $Y = \NN$, а тогда $X = \varnothing$ --- противоречие.
    \end{proof}

    \begin{theorem}[о рекурсии]
        Пусть есть $y_0 \in Y$ и $h: \NN \times Y \to Y$. Тогда существует и единственная $f: \NN \to Y$ такая, что для любого $n \in \NN$
        \[f(n) = \left\{\begin{aligned}
            &y_0&&\text{если }n = 0\\
            &h(m, f(m))&&\text{если }n = m + 1
        \end{aligned}\right.\]
    \end{theorem}

    \begin{proof}
        Пусть $k \in \NN$. Тогда будем называть функцию $f: k+1 \to Y$ \emph{правильной}, если условие в определении рекурсии верно для всех $n \in k + 1$. Также рассмотрим
        \[S := \{k \in \NN \mid \text{существует единственная правильная $f: k + 1 \to Y$}\}\]
        Будем обозначать для каждого $k \in S$ через $f_k$ соответствующую правильную функцию из $k+1$ в $Y$.

        Докажем по индукции, что $S = \NN$.

        \textbf{База.} Очевидно, $\{(0, y_0)\}$ --- единственная правильная функция из $0+1$ в $Y$. Поэтому $0 \in S$.

        \textbf{Шаг.} Легко заметить, что сужение любой правильной функции на $k+2$ на множество $k+1$ правильно. Поэтому все правильные функции на $k+2$ определены на $k+1$ как $f_k$. Тогда значение в $k+1$ определяется однозначно, значит правильная функция на $k+2$ существует и единственна. 
    \end{proof}

    \begin{theorem}[о рекурсии, параметризованная]
        Пусть $g_0 \in Y^X$ и $h: X \times \NN \times Y \to Y$. Тогда существует и единственна $f: X \times \NN \to Y$, что $\forall x \in X, n \in \NN$
        \[f(x, n) = \left\{\begin{aligned}
            &g_0(x)&&\text{если }n=0\\
            &h(x, m ,f(x, m))&&\text{если }n=m+1
        \end{aligned}\right.\]
    \end{theorem}

    \begin{proof}
        Рассмотрим для каждого $x \in X$ функцию $h_x: \NN \times Y \to Y, (n, y) \mapsto h(x, n, y)$. Тогда по теореме о рекурсии есть $f_x: \NN \to Y$, что
        \[f_x(n) = \left\{\begin{aligned}
            &g_0(x)&&\text{если $n=0$}\\
            &h_x(m, f_x(m))&&\text{если $n=m+1$}
        \end{aligned}\right.\]
        Тогда определим $f: X \times \NN \to Y, (x, n) \mapsto f_x(n)$. В этом случае
        \[f(x, n) = f_x(n) = \left\{\begin{aligned}
            &g_0(x)&&\text{если $n=0$}\\
            &h_x(m, f_x(m))&&\text{если $n=m+1$}
        \end{aligned}\right.=\left\{\begin{aligned}
            &g_0(x)&&\text{если $n=0$}\\
            &h(x, m, f(x, m))&&\text{если $n=m+1$}
        \end{aligned}\right.\]
    \end{proof}


    \begin{remark}
        Заметим, что с помощью теоремы о параметризованной рекурсии можно определить сложение, умножение и возведение в степень на натуральных числах.
    \end{remark}

    \begin{definition}
        Несложно заметить, что функциональные отношения $R \subseteq X \times Y$ --- функции из подмножества $X$ в $Y$. Поэтому будем называть их \emph{частичными функциями} и обозначать как $R: \subseteq X \to Y$.
    \end{definition}

    \begin{theorem}[о рекурсии, частичной]
        Пусть $y_0 \in Y$ и $h: \subseteq \NN \times Y \to Y$. Тогда существует и единственна $f: \subseteq \NN \to Y$, что
        \begin{itemize}
            \item для любого $n \in \dom(f)$,
                \[f(n) = \left\{\begin{aligned}
                    &y_0 && \text{если $n = 0$}\\
                    &h(m, f(m)) && \text{если $n = m + 1$}
                \end{aligned}\right.\]
            \item либо $\dom(f) = \NN$, либо $\dom(f) = k + 1$ для некоторого $k \in \NN$, что $(k, f(k)) \notin \dom(h)$.
        \end{itemize}
    \end{theorem}

    \begin{proof}
        Зафиксируем некоторое $\text{ы} \notin Y$ и положим $Y' := Y \cup \{\text{ы}\}$. Теперь расширим $h$ до $h': \NN \times Y' \to Y'$ следующим образом:
        \[h'(n, y') := \left\{\begin{aligned}
            &h(n, y') && \text{если $(n, y') \in \dom(h)$}\\
            &\text{ы} && \text{иначе}
        \end{aligned}\right.\]
        В силу теоремы о рекурсии существует и единственна $f': \NN \to Y'$ такая, что для любого $n \in \NN$,
        \[f'(n) = \left\{\begin{aligned}
            &y_0 && \text{если $n=0$}\\
            &h'(m, f'(m)) && \text{если $n=m+1$}
        \end{aligned}\right.\]
        Возьмём $f := f' \cup (\NN \times Y)$. Несложно убедиться, что $f$ будет искомой.
    \end{proof}

    \begin{definition}
        \emph{Конечными последовательностями элементов} $X$ называются элементы множества $X^* := \{f \mid \exists n \in \NN (f: n \to X)\}$.
    \end{definition}

    \begin{theorem}[о возвратной индукции]
        Пусть $h: \NN \times Y^* \to Y$. Тогда существует единственная $f: \NN \to Y$ такая, что для любого $n \in \NN$, $f(n) = h(n, f\upharpoonright_n)$.
    \end{theorem}

    \begin{proof}
        По аналогии с доказательством теоремы о рекурсии, однако вместо обычной индукции тут используется возвратная. [\dots]
    \end{proof}

    \begin{definition}
        Условие $\Phi(x, y)$ называется \emph{функциональным}, если
        \[\forall x \forall y_1 \forall y_2\; ((\Phi(x, y_1) \wedge \Phi(x, y_2)) \rightarrow y_1 = y_2)\]
        Если для некоторого $u$ нашёлся тот самый $y$, что $\Phi(u, y)$, тогда данный $y$ обозначается как $\llbracket \Phi \rrbracket (x)$.

        Функциональное условие $\Phi(x, y)$ называется \emph{тотальным}, если $\forall x \exists y\; \Phi(x, y)$.
    \end{definition}

    \begin{theorem}[о возвратной ``классовой рекурсии'']
        Пусть $\Phi(x, y)$ --- тотальное функциональное условие. Тогда существует единственная функция $f$ с $\dom(f) = \NN$, что $\forall n \in \NN$
        \[f(n) = \llbracket \Phi \rrbracket (f\upharpoonright_n)\]
    \end{theorem}

    \begin{proof}
        Идея здесь та же, хотя деталей побольше. В нашем модуле эта теорема не будет играть особой роли, однако именно ``классовая рекурсия'' является базовым инструментом в ТМ. [...]
    \end{proof}

    \section{Мощности}

    \begin{definition}
        $X$ и $Y$ \emph{равномощны}, если существует биекция $f: X \to Y$. Обозначение: $X \sim Y$.
    \end{definition}

    \begin{theorem}
        Для всех $X$, $Y$ и $Z$ верно следующее:
        \begin{enumerate}
            \item $X \sim X$;
            \item $X \sim Y \Leftrightarrow Y \sim X$;
            \item $X \sim Y \sim Z \Rightarrow X \sim Z$.
        \end{enumerate}
    \end{theorem}

    \begin{example}
        $\subsets(X) \sim 2^X$. Действительно, рассмотрим для каждого $Y \subseteq X$ функцию $\chi_Y: X \to 2$, что
        \[\chi_Y(x) := \left\{\begin{aligned}
            &1 && \text{если $x\in Y$}\\
            &0 && \text{если $x \in X \setminus Y$}
        \end{aligned}\right.\]
        Несложно заметить, что отображение, сопоставляющее $Y$ функцию $\chi_Y$ есть биекция из $\subsets(x)$ в $2^X$.
    \end{example}

    \begin{definition}
        Множество $X$ \emph{по мощности менее или равно} $Y$ ($X \preccurlyeq Y$), если существует инъекция из $X$ в $Y$.

        Множество $X$ \emph{по мощности (строго) менее} $Y$ ($X \prec Y$), если $X \preccurlyeq Y \wedge X \nsim Y$.
    \end{definition}

    \begin{remark}
        Тогда очевидно, что $X \preccurlyeq Y$ тогда и только тогда, когда $X$ равномощно некоторому подмножеству $Y$.
    \end{remark}

    \begin{theorem}\ 
        \begin{enumerate}
            \item $X \preccurlyeq X$.
            \item $X \sim Y \Rightarrow X \preccurlyeq Y$.
            \item $X \preccurlyeq Y \sim Z \Rightarrow X \preccurlyeq Z$.
            \item $X \sim Y \preccurlyeq Z \Rightarrow X \preccurlyeq Z$.
            \item $X \preccurlyeq Y \preccurlyeq Z \Rightarrow X \preccurlyeq Z$.
        \end{enumerate}
    \end{theorem}

    \begin{theorem}[Кантора, обобщённая]
        $X \prec \subsets(X)$.
    \end{theorem}

    \begin{proof}
        Очевидно, что $f: X \to \subsets(X), x \mapsto \{x\}$ есть инъекция, поэтому $X \preccurlyeq \subsets(X)$. Покажем, что между ними нет биекции.

        Предположим противное, т.е. есть биекция $f: X \to \subsets(X)$. Рассмотрим $Y := \{x \in X \mid x \notin f(x)\}$. Поскольку $f$ --- биекция, то $f(y) = Y$ для некоторого $y$. В итоге мы получаем
        \[
            y \in Y \qquad
            \Longleftrightarrow \qquad
            y \notin f(Y) \qquad
            \Longleftrightarrow \qquad
            y \notin Y
        \]
        Получаем противоречие.
    \end{proof}

    \begin{theorem}[Кантора-Шрёдера-Бернштейна]
        Если $X \preccurlyeq Y$ и $Y \preccurlyeq X$, то $X \sim Y$.
    \end{theorem}

    \begin{proof}
        \begin{thlemma}\label{CSB-th-lemma}
            Если $X \supseteq Y \supseteq X'$ и $X \sim X'$, то $X \sim Y \sim X'$.
        \end{thlemma}

        \begin{proof}
            Пусть $f: X \to X'$ --- биекция. Определим по рекурсии $\{X_i\}_{i=0}^\infty$ и $\{Y_i\}_{i=0}^\infty$:
            \begin{align*}
                X_n &:= \left\{\begin{aligned}
                    &X && \text{если $n = 0$}\\
                    &f[X_m] && \text{если $n=m+1$}
                \end{aligned}\right.&
                Y_n &:= \left\{\begin{aligned}
                    &Y && \text{если $n = 0$}\\
                    &f[Y_m] && \text{если $n=m+1$}
                \end{aligned}\right.
            \end{align*}

            По условию $X_0 = X \supseteq Y = Y_0$ и $Y_0 = Y \supseteq X' = f(X) = X_1$. Тогда несложно убедиться по индукции по $n$, что $X_n \supseteq Y_n \supseteq X_{n+1}$, так как $X_{n-1} \supseteq Y_{n-1} \supseteq X_n$, значит $f(X_{n-1}) \supseteq f(Y_{n-1}) \supseteq f(X_n)$, что буквально означает, что $X_n \supseteq Y_n \supseteq X_{n+1}$.

            Тогда для каждого $n \in \NN$ определим $U_n := X_n \setminus Y_n$. Пусть также $U := \bigcup_{n=0}^\infty U_n$, $Z := X \setminus U$.

            Несложно видеть, что
            \begin{align*}
                X &= \bigcup_{n=0}^\infty U_n \cup Z&
                Y &= \bigcup_{n=1}^\infty U_n \cup Z
            \end{align*}
            Также несложно видеть, что $f[U_n] = f[X_n \setminus Y_n] = f[X_n] \setminus f[Y_n] = X_{n+1} \setminus Y_{n+1} = U_{n+1}$, а потому $f[U] = U\setminus U_0$.

            Тогда определим $g: X \to X$ по правилу
            \[g(x) := \begin{cases}
                f(x) & \text{если $x \in U$}\\
                x & \text{если $x \in Z$}
            \end{cases}\]
            Несложно видеть, что это инъекция. Действительно, $g$ на $U$ равна $f$, а значит есть биекция из $U$ в $U\setminus U_0$, также является биекцией из $Z$ в себя, а поскольку $U$ и $Z$ дизъюнктны, то $g$ является биекцией из $U \cup Z$ в $U\setminus U_0 \cup Z$, т.е. из $X$ в $Y$. Значит $Y \sim X$.
        \end{proof}

        Пусть $f: X \to Y$ и $g: Y \to X$ --- инъекции. Несложно видеть, что $g[Y] \subseteq X$, а $f[X] \subseteq Y$, значит $g[f[X]] \subseteq g[Y]$. Т.е. $X \supseteq g[Y] \supseteq g[f[X]]$. При этом $X \sim f[X] \sim g[f[X]]$, поэтому применяя лемму \ref{CSB-th-lemma}, имеем, что $X \sim g[Y] \sim Y$, значит $X \sim Y$.
    \end{proof}

    \begin{definition}
        Будем говорить, что $X$ \emph{имеет $n$ элементов} (где $n \in \NN$), если $X \sim n$.

        $X$ \emph{конечно}, если для какого-то $n\in \NN$, что $X \sim n$.
    \end{definition}

    \begin{statement}
        $X$ бесконечно, значит $\forall n\in\NN\quad |X| \geqslant n$.
    \end{statement}

    \begin{proof}
        Докажем по индукции по $n$.

        \textbf{База:} $|X| \geqslant 0$ --- очевидно.

        \textbf{Шаг:} Пусть $|X| > n$, тогда существует инъекция $f: n \to X$. $f(n) \neq X$, поэтому есть $x \in X\setminus f(n)$, значит есть $f' = f \cup \{(n; x)\}$ --- инъекция из $n+1$ в $X$.
    \end{proof}

    \subsection{Основные свойства конечных множеств}

    \begin{statement}
        $X$ конечно, а $|Y| \leqslant |X|$, то $|Y|$ конечно.
    \end{statement}

    \begin{proof}
        Существует $n \in \NN$, что $|X| = n$. Тогда $Y$ кончено, так как иначе $n = |X| \geqslant |Y| \geqslant n+1$.
    \end{proof}

    \begin{statement}
        Пусть есть сюръекция из $X$ в $Y$, и $X$ конечно. Тогда $|Y| \leqslant |X|$.
    \end{statement}

    \begin{proof}
        WLOG $X=n$ для некоторого $n \in \NN$. Определим $g: Y \to n$ по правилу
        \[
            g(y) := \text{``минимальный элемент в $f^{-1}[\{y\}]$''}
        \]
        Легко понять, что $g: Y \to n$ --- инъекция. Стало быть, $|Y| \geqslant |n| = n$.
    \end{proof}

    \begin{statement}
        Пусть $X$ и $Y$ конечны, причём $X \cup Y = \varnothing$. Тогда $X \cap Y$ конечно и $|X \cup Y| = |X| + |Y|$.
    \end{statement}

    \begin{proof}
        Докажем утверждение индукцией по $|Y|$.

        \textbf{База.} Очевидно, если $|Y| = 0$, то $|Y| = \varnothing$, а потому $|X \cup Y| = |X| = |X| + 0 = |X| + |Y|$.

        \textbf{Шаг.} Пусть $|Y| = n+1$, т.е. существует биекция $f: n+1 \to Y$. Рассмотрим $y = f^{-1}(n)$ и $Z := Y \setminus \{y\}$. Очевидно, что $|Z| = n$. Тогда
        \begin{align*}
            |X \cup Y|
            &= |(X \cup Z) \cup \{y\}|&
            &= |X \cup Z| + 1&
            &= (|X| + |Z|) + 1\\
            &= |X| + (|Z| + 1)&
            &= |X| + |Y|
        \end{align*}
    \end{proof}

    \begin{statement}
        Пусть $X$ и $Y$ конечны. Тогда $X \times Y$ и $X^Y$ кончены и $|X\times Y| = |X|\cdot |Y|$, $|X^Y|=|X|^{|Y|}$.
    \end{statement}

    \subsection{Основные свойства (не более чем) счётных множеств}

    \begin{statement}[в \ZFC]
        Пусть $X$ бесконечно, тогда оно содержит счётное подмножество.
    \end{statement}

    \begin{proof}
        Пусть $\eta$ --- какая-нибудь функция выбора для $\subsets(X) \setminus \{\varnothing\}$. Используя рекурсию, определим $f: \NN \to X$ по правилу
        \[f(k) := \eta(X \setminus \range(f \upharpoonright_k))\]
        Как легко видеть, $f: \NN \to X$ --- инъекция. Поэтому $\range(f)$ будет счётным подмножеством $X$.
    \end{proof}

    \begin{definition}
        $\NN$ является кардиналом и обычно обозначается $\aleph_0$.
    \end{definition}

    \begin{corollary}[в \ZFC]
        $|X| >\aleph_0$ тогда и только тогда, когда $X$ бесконечно и несчётно.
    \end{corollary}

    \begin{statement}
        $|X| \leqslant \aleph_0$ тогда и только тогда, когда $X$ конечно или счётно.
    \end{statement}

    \begin{proof}
        Если $X$ конечно или счётно, то, очевидно, $|X| \leqslant \aleph_0$.

        Если $|X| \leqslant \aleph_0$, то WLOG $X \subseteq \NN$. Если $X$ бесконечно, то рекурсивно определим $f: \NN \to X$ по правилу
        \[f(k) := \text{``минимальный элемент в $X \setminus \range(f \upharpoonright_k)$''}\]
        Нетрудно проверить, что $f: \NN \to X$ --- биекция.
    \end{proof}

    \begin{corollary}[в \ZFC]
        $|X| \ngtr \aleph_0$ тогда и только тогда, когда $|X| \leqslant \aleph_0$.
    \end{corollary}

    \begin{statement}
        Есть сюръекция из $X$ в $Y$, причём $|X| \leqslant \aleph_0$. Тогда $|Y| \leqslant \aleph_0$.
    \end{statement}

    \begin{proof}
        WLOG $X \subseteq \NN$. Определим $g: Y \to X$ по правилу
        \[g(y) := \text{``минимальный элемент в $f^{-1}[\{y\}]$''}\]
        Легко понять, что $g: Y \to X$ --- инъекция. Стало быть, $|Y| \leqslant |X| \leqslant \aleph_0$.
    \end{proof}

    \begin{corollary}
        Непустое $X$ не более чем счётно тогда и только тогда, когда существует сюръекция из $\NN$ в $X$.
    \end{corollary}

    \begin{corollary}
        Пусть $R$ --- отношение эквивалентности на $X$, причём $X$ не более, чем счётно. Тогда $X/R$ не более чем счётно.
    \end{corollary}

    \begin{statement}
        Пусть $X$ и $Y$ не более чем счётны, тогда $X \times Y$ не более чем счётно.
    \end{statement}

    \begin{proof}
        WLOG $X, Y \subseteq \NN$. Тогда $X \times Y \subseteq \NN \times \NN$, а значит нужно показать, что счётность $\NN \times \NN$. Определим $\nu: \NN \times \NN \to \NN$ по правилу
        \[\nu(n, m) := \frac{(n+m)(n+m+1)}{2} + n\]
        Нетрудно проверить, что $\nu$ биективна.
    \end{proof}

    \begin{corollary} $\forall n \in \NN$
        \[\underbrace{\NN \times \dots \times \NN}_n\]
        счётно.
    \end{corollary}

    \begin{corollary}
        Пусть $X$ и $Y$ не более чем счётны, тогда $X \cup Y$ не более чем счётно.
    \end{corollary}

    \begin{proof}
        Поскольку $X$ и $Y\setminus X$ равномощны некоторым подмножествам $\NN \times \{0\}$ и $\NN \times \{1\}$, то $X \cup Y = X \cup (Y \setminus X)$ равномощно подмножеству $\NN \times \{0, 1\} \subseteq \NN \times \NN$, а потому не более чем счётно.
    \end{proof}

    \begin{statement}
        $X$ конечно, а элементы $X$ не более чем счётны. Тогда $\bigcup X$ не более чем счётно.
    \end{statement}

    \begin{proof}
        По индукции по $|X|$.
    \end{proof}

    \begin{definition} Условие ``быть (бесконечной) последовательностью'' ---
        $\Seq(F) := \exists Y:\quad F: \NN \to Y$.
        Если $\Seq(F)$, то для любого $n \in \NN$ вместо $F(n)$ нередко пишут $F_n$.
    \end{definition}

    \begin{statement}
        Если $F$ --- последовательность последовательностей, то тогда
        \[\bigcup \{\range(F_n)\mid n \in \NN\}\]
        не более чем счётно.
    \end{statement}

    \begin{proof}
        Определим $g: \NN \times \NN \to \bigcup \{\range(F_n)\mid n \in \NN\}$ по правилу
        \[g(n,m) := F_n(m) = F(n)(m)\]
        Легко понять, что $g$ сюръективна.
    \end{proof}

    \begin{corollary}[в \ZFC]
        Пусть $X$ не более чем счётно, и все его элементы не более чем счётны, тогда $\bigcup X$ не более чем счётно.
    \end{corollary}

    \begin{proof}
        WLOG $X \neq \varnothing$ и $\varnothing \notin X$. Пусть $g$ --- сюръекция из $\NN$ на $X$. Для каждого $n \in \NN$ положим
        \[S_n := \{f \mid f: \NN \to g(n) \text{ --- сюръекция}\}\]
        Очевидно, $S_n \neq \varnothing$ для всякого $n \in \NN$. Обозначим $\{S_n \mid n \in \NN\}$ через $\mathcal{J}$. Пусть $\eta$ --- какая-нибудь функция выбора для $\mathcal{J}$. Наконец, определим $F: \NN \to \bigcup \mathcal{J}$ по правилу
        \[F(n) := \eta(S_n)\]
        Ясно, что $\bigcup \{\range(F_n) \mid n \in \NN\} = \bigcup \{g(n) \mid n \in \NN\} = \bigcup X$.
    \end{proof}

    \begin{theorem}
        Пусть непустое $X$ не более чем счётно. Тогда $X^*$ счётно.
    \end{theorem}

    \begin{proof}
        Зафиксируем сюръекцию $g: \NN \to X$. Очевидно, $f \circ g \in X^*$ для всякого $f \in \NN^*$. Определим $G: \NN^* \to X^*$ по правилу
        \[G(f) := f \circ g\]
        Легко убедиться, что $G$ сюръективна. Поэтому достаточно показать, что $N^*$ не более чем счётно, а $X^*$ бесконечно.

        Пусть $\nu: \NN \times \NN \to \NN$ --- биекция. Разумеется, можно построить функции $\Left: \NN \to \NN$ и $\Right: \NN \to \NN$ такие, что для любых $n, m \in \NN$,
        \begin{align*}
            \Left(\nu(n,m)) &= n&
            &\text{ и }&
            \Right(\nu(n,m)) &= m
        \end{align*}
        Используя рекурсию, можно определить последовательность последовательностей $f$, удовлетворяющую следующим условиям:
        \begin{align*}
            f_0(i) &= \varnothing\\
            f_{n+1}(i) &= f_n(\Left(i)) \cup \{(n, \Right(i))\}
        \end{align*}
        Далее несложно доказать по индукции, что для каждого $n \in \NN$
        \[\range(f_n) = \{g \mid g: n \to \NN\}\]
        В таком случае $\bigcup \{\range(f_n) \mid n \in \NN\} = \NN^*$. Поэтому $\NN^*$ не более чем счётно.

        Осталось показать, что $X^*$ бесконечно. Для этого выберем какой-нибудь $x_0 \in X$ и определим $h: \NN \to X^*$ по правилу
        \[h(n) := n \times \{x_0\},\]
        т.е. $h(n)$ --- последовательность длины $n$ только из элемента $x_0$. Очевидно, что $h$ инъективна, а потому $X^*$ не может быть конечным.
    \end{proof}

    \begin{definition}
        Для произвольного множества $X$ обозначим
        \[\finsubsets(X) := \{Y \mid Y \subseteq X \text{ и $Y$ конечно}\}\]
        Говоря просто, $\finsubsets(X)$ --- семейство конечных подмножеств $X$.
    \end{definition}

    \begin{corollary}
        Пусть $X$ счётно. Тогда $\finsubsets(X)$ счётно.
    \end{corollary}

    \begin{proof}
        Рассмотрим $h: X^* \to \finsubsets(X)$, действующую по правилу
        \[h(f) := \range(f)\]
        Легко видеть, что $h$ сюръективна, значит $\finsubsets(X)$ не более чем счётно.

        С другой стороны пусть $\nu: \NN \to X$ --- инъекция. Тогда рассмотрим $g: \NN \to \finsubsets(X)$, что
        \[g(n) := \nu[n]\]
        Несложно проверить, что $|\nu[n]| = n$, поэтому $g$ инъективна, значит $\finsubsets(X)$ бесконечно, а значит счётно.
    \end{proof}

    \begin{corollary}
        В следствие теоремы Кантора $\subsets$ нельзя заменить на $\finsubsets$.
    \end{corollary}

    \begin{theorem}[в \ZFC]
        Пусть $X$ бесконечно, а $Y$ не более чем счётно. Тогда $|X \cup Y| = |X|$.
    \end{theorem}

    \begin{proof}
        Заменяя $Y$ на $Y\setminus X$, имеем, что WLOG $X \cap Y = \varnothing$. При этом у $X$ есть счётное подмножество $Z$. Тогда понятно, что $Z \cup Y$ счётно, а значит есть биекция $f: Z \cup Y \to Z$. Тогда определим $g: X \cup Y \to X$ так, что
        \[g(x) := \begin{cases}
            f(x)& \text{если $x \in Z \cup Y$}\\
            x& \text{если $x \in X \setminus Z$}
        \end{cases}\]
        Очевидно, что $g$ биективна.
    \end{proof}

    \begin{corollary}
        Пусть $X$ более чем счётно, а $Y$ не более чем счётно. Тогда $|X \setminus Y| = |X|$.
    \end{corollary}

    \begin{proof}
        Пусть $U := X \cap Y$, а $V := X \setminus U$. Ясно, что $U$ не более чем счётно, $V$ бесконечно. Значит, $|X| = |V \cup U| = |V| = |X \setminus Y|$. 
    \end{proof}

    \section{Упорядоченность}

    \begin{definition}
        \emph{Частично упорядоченное множество (ЧУМ)} --- пара из множества и частичного порядка на нём.

        \emph{Линейно упорядоченное множество (ЛУМ)} --- пара из множества и линейного порядка на нём.

        Обозначение: $\mathfrak{A} = \langle A, \leqslant \rangle$.
    \end{definition}

    \begin{definition}
        Пусть даны ЧУМ $\mathfrak{A} = \langle A, \leqslant \rangle$ и непустое $S \subseteq A$. Тогда $a \in A$ является
        \begin{itemize}
            \item \emph{максимальным элементом для $S$ в $\mathfrak{A}$}, если $a \in S \wedge \neg(\exists x \in S: a < x)$;
            \item \emph{минимальным элементом для $S$ в $\mathfrak{A}$}, если $a \in S \wedge \neg(\exists x \in S: x < a)$;
            \item \emph{наибольшим элементом для $S$ в $\mathfrak{A}$}, если $a \in S \wedge (\forall x \in S\quad x \leqslant a)$;
            \item \emph{наименьшим элементом для $S$ в $\mathfrak{A}$}, если $a \in S \wedge (\forall x \in S\quad a \leqslant x)$.
        \end{itemize}

        Если $S = A$, то уточнение ``для $S$'' опускают.

        Также $a$ является
        \begin{itemize}
            \item \emph{верхней гранью для $S$ в $\mathfrak{A}$}, если $\forall x \in S\quad x \leqslant a$;
            \item \emph{нижней гранью для $S$ в $\mathfrak{A}$}, если $\forall x \in S\quad x \geqslant a$;
            \item \emph{супремумом гранью для $S$ в $\mathfrak{A}$}, если $a$ --- наименьшая верхняя грань для $S$ в $\mathfrak{A}$;
            \item \emph{инфимумом гранью для $S$ в $\mathfrak{A}$}, если $a$ --- наибольшая нижняя грань для $S$ в $\mathfrak{A}$.
        \end{itemize}
    \end{definition}

    \begin{statement}
        В ЧУМ $\mathfrak{A}$
        \begin{itemize}
            \item не более одного наибольшего в $\mathfrak{A}$ элемента;
            \item всякий наибольший в $\mathfrak{A}$ максимален в $\mathfrak{A}$;
            \item любые два максимальных в $\mathfrak{A}$ несравнимы.
        \end{itemize}

        Аналогично для наименьших и минимальных элементов.
    \end{statement}

    \begin{statement}
        В ЛУМ все максимальные наибольшие и наоборот. Аналогично для минимальных и наименьших.
    \end{statement}

    \begin{definition}
        \emph{Гомоморфизм из $\langle A, \leqslant_A \rangle$ в $\langle B, \leqslant_B \rangle$} --- отображение $f: A \to B$, что
        \[
            a_1 \leqslant_A a_2 \Rightarrow f(a_1) \leqslant_B f(a_2)
        \]
        В таком случае ещё говорят, что $f$ сохраняет порядок.

        Если $f$ инъективно, а последнее условие усиливается до равносильности (а не остаётся следствием), то $f$ называется \emph{вложением из $\langle A, \leqslant_A \rangle$ в $\langle B, \leqslant_B \rangle$}.
    \end{definition}

    \begin{statement}
        Любой инъективный гомоморфизм из ЛУМ в ЧУМ является вложением.
    \end{statement}

    \begin{definition}
        \emph{Изоморфизм из $\mathfrak{A}$ в $\mathfrak{B}$} --- сюръективное вложение из $\mathfrak{A}$ в $\mathfrak{B}$. Обозначение: $\mathfrak{A} \simeq \mathfrak{B}$.
    \end{definition}

    \begin{statement}
        ``Изоморфность'' --- ``отношение эквивалентности'' на ЧУМах. Т.е. для любых $\mathfrak{A}$, $\mathfrak{B}$ и $\mathfrak{C}$ верно:
        \begin{enumerate}
            \item $\mathfrak{A} \simeq \mathfrak{A}$;
            \item $\mathfrak{A} \simeq \mathfrak{B} \Leftrightarrow \mathfrak{B} \simeq \mathfrak{A}$;
            \item $\mathfrak{A} \simeq \mathfrak{B} \simeq \mathfrak{C} \Rightarrow \mathfrak{A} \simeq \mathfrak{C}$.
        \end{enumerate}
    \end{statement}

    \begin{definition}
        Изоморфизм из $\mathfrak{A}$ на себя --- \emph{автоморфизм}.
    \end{definition}

    С ЧУМами можно делать базовые преобразования:
    \begin{enumerate}
        \item Пусть даны ЧУМ $\mathfrak{A} = \langle A, {\leqslant} \rangle$ и $S \subseteq A$. Возьмём
            \[ {\leqslant}_S := {\leqslant} \cap S \times S\]
            Тогда $\langle S, {\leqslant}_S \rangle$ --- ЧУМ. Оно называется \emph{индуцированным в $\mathfrak{A}$ по $S$}. При этом из ЛУМ получится ЛУМ.
        \item Пусть даны ЧУМ $\mathfrak{A} = \langle A, {\leqslant}_A \rangle$ и $\mathfrak{B} = \langle B, {\leqslant}_B \rangle$, причём $A$ и $B$ дизъюнктны. Возьмём
            \[{\leqslant} := {\leqslant}_A \cup A \times B \cup {\leqslant}_B\]
            Тогда $\langle A \cup B, {\leqslant} \rangle$ --- ЧУМ, которое обозначается $\mathfrak{A} \oplus \mathfrak{B}$. При этом из двух ЛУМ всегда получится ЛУМ.
        \item Пусть даны ЧУМ $\mathfrak{A} = \langle A, {\leqslant}_A \rangle$ и $\mathfrak{B} = \langle B, {\leqslant}_B \rangle$. Определим $\leqslant$ на $A \times B$ по правилу
            \[(a_1, b_1) \leqslant (a_2, b_2) :\Leftrightarrow a_1 \leqslant_A a_2 \wedge b_1 \leqslant \]
            Тогда $\langle A \times B, {\leqslant} \rangle$ --- ЧУМ, где $\leqslant$ традиционно называют \emph{покоординатным порядком}. Понятно, что $\leqslant$ мало когда бывает линейным.
        \item Модифицируем предыдущую конструкцию, сделав одну из координат главной. Например, первую:
            \[(a_1, b_1) \leqslant (a_2, b_2) :\Leftrightarrow a_1 < a_2 \vee (a_1 = a_2 \wedge b_1 \leqslant b_2)\]
            Тогда $\langle A \times B, {\leqslant} \rangle$ --- ЧУМ, которое обозначается $\mathfrak{A} \otimes \mathfrak{B}$. В таком случае из двух ЛУМ получается ЛУМ.
    \end{enumerate}

    \subsection{Трансфинитная индукция и фундированность}

    \begin{definition}
        Для ЧУМ $\mathfrak{A} = \langle A, {\leqslant} \rangle$ верен \emph{принцип трансфинитной индукции}, если для всякого $X \subseteq A$,
        \[\forall x \in A ((\forall y < x) y \in X \rightarrow x \in X) \rightarrow X = A\]
    \end{definition}

    \begin{definition}
        Для ЧУМ $\mathfrak{A} = \langle A, {\leqslant} \rangle$ верен \emph{принцип минимального элемента}, если для всякого $X \subseteq A$,
        \[X \neq \varnothing \rightarrow \exists x \in X ((\forall y \in X )\ y \nless x)\]
        Такие ЧУМ называются \emph{фундированными}.
    \end{definition}

    \begin{theorem}
        Для ЧУМ верен принцип трансфинитной индукции тогда и только тогда, когда оно фундировано.
    \end{theorem}

    \begin{proof}
        Пусть $X \subseteq A$. Обозначим $A \setminus X$ через $\overline{X}$. Тогда
        \begin{align*}
            \forall x \in A ((\forall y < x) y \in X \rightarrow x \in X) \rightarrow X = A &\Longleftrightarrow\\
            X \neq A \rightarrow \neg\forall x \in A ((\forall y < x) y \in X \rightarrow x \in X) &\Longleftrightarrow\\
            X \neq A \rightarrow \exists x \in A \neg((\forall y < x) y \in X \rightarrow x \in X) &\Longleftrightarrow\\
            X \neq A \rightarrow \exists x \in A ((\forall y < x) y \in X \wedge x \notin X) &\Longleftrightarrow\\
            X \neq A \rightarrow \exists x \in A ((\forall y \notin X) y \nless x \wedge x \notin X) &\Longleftrightarrow\\
            \overline{X} \neq \varnothing \rightarrow \exists x \in \overline{X} ((\forall y \in \overline{X}) y \nless x)&
        \end{align*}
    \end{proof}

    \begin{statement}\ 
        \begin{enumerate}
            \item Пусть даны фундированные ЧУМ $\mathfrak{A}$ и $\mathfrak{B}$, что $A \cap B = \varnothing$. Тогда $\mathfrak{A} \oplus \mathfrak{B}$ будет фундированным.
            \item Пусть даны фундированные ЧУМ $\mathfrak{A}$ и $\mathfrak{B}$. Тогда $\mathfrak{A} \otimes \mathfrak{B}$ будет фундированным.
        \end{enumerate}
    \end{statement}

    \begin{definition}
        \emph{Вполне упорядоченное множество (ВУМ)} --- фундированное ЛУМ. Порядки ВУМ называются \emph{полными порядками}.
    \end{definition}

    \begin{definition}
        Пусть дано ВУМ $\mathfrak{A} = \langle A, {\leqslant} \rangle$. \emph{Начальный сегмент} --- множество $S \subseteq A$, если для $\forall a_1, a_2 \in A$
        \[(a_1 \leqslant a_2 \wedge a_2 \in S) \Rightarrow a_1 \in S\]
    \end{definition}

    \begin{definition}
        Пусть дано ВУМ $\mathfrak{A} = \langle A, {\leqslant} \rangle$. Множество
        \[[0, a)_{\mathfrak{A}} := \{x \in A \mid x < a\}\]
        является начальным сегментом $\mathfrak{A}$. Когда ясно, о каком $\mathfrak{A}$ идёт речь, нижний индекс $\cdot_{\mathfrak{A}}$ обычно опускается.
    \end{definition}

    \begin{statement}
        Пусть $\mathfrak{A}$ --- ВУМ, а $S$ --- начальный сегмент $\mathfrak{A}$, отличный от $A$. Тогда существует единственный $a \in A$, что $S = [0, a)$.
    \end{statement}

    \begin{definition}
        $\IS_\mathfrak{A}$ --- множество всех начальных сегментов $\mathfrak{A}$, отличных от $A$, а
        \[{\subseteq}_{\IS_\mathfrak{A}} := \{(U, V) \in \IS_\mathfrak{A} \times \IS_\mathfrak{A} \mid U \subseteq V\}\]
    \end{definition}

    \begin{statement}
        Для любого ВУМ $\mathfrak{A}$ верно, что $\mathfrak{A} \simeq \langle \IS_\mathfrak{A}, {\subseteq}_{\IS_\mathfrak{A}} \rangle$.
    \end{statement}

    \begin{proof}
        Несложно видеть, что
        \[f: A \to \IS_\mathfrak{A}, a \mapsto [0, a)\]
        есть изоморфизм из $\mathfrak{A}$ в $\langle \IS_\mathfrak{A}, {\subseteq}_{\IS_\mathfrak{A}} \rangle$.
    \end{proof}

    \begin{statement}
        Пусть $\mathfrak{A}$ --- ВУМ, а $f$ --- вложение из $\mathfrak{A}$ в $\mathfrak{A}$. Тогда $f(a) \geqslant a$ для всех $a \in A$.
    \end{statement}

    \begin{proof}
        Рассмотрим
        \[X := \{a \in A \mid f(a) < a\}\]
        Предположим, что $X$ непусто. Пусть $a'$ --- наименьший элемент для $X$ в $\mathfrak{A}$. Тогда $f(a') < a'$, поэтому $f(f(a')) < f(a')$, что значит $f(a') \in X$. В таком случае $a' \leqslant f(a')$ --- противоречие.
    \end{proof}

    \begin{corollary}
        Для каждого ВУМ $\mathfrak{A}$ единственным автоморфизмом $\mathfrak{A}$ является $id_A$.
    \end{corollary}

    \begin{proof}
        Пусть $f$ --- автоморфизм $\mathfrak{A}$. Очевидно, что $f^{-1}$ также будет автоморфизмом $\mathfrak{A}$. Тогда для любого $a \in A$ имеем, что $f(a) \geqslant a$ и $f^{-1}(a) \geqslant a$, а значит $a \geqslant f(a) \geqslant a$, т.е. $f(a) = a$. Таким образом $f = id_A$.
    \end{proof}

    \begin{corollary}
        Для любых ВУМ $\mathfrak{A}$ и $\mathfrak{B}$ имеется не более одного изоморфизма из $\mathfrak{A}$ в $\mathfrak{B}$.
    \end{corollary}

    \begin{proof}
        Пусть $f$ и $g$ --- изоморфизмы из $\mathfrak{A}$ в $\mathfrak{B}$. Тогда несложно понять, что $f \circ g^{-1}$ есть автоморфизм, а значит $f \circ g^{-1} = id_A$. Следовательно $f = f \circ g^{-1} \circ g = id_A \circ g = g$.
    \end{proof}

    \begin{lemma}
        Никакой собственный начальный сегмент ВУМ $\mathfrak{A}$ не изоморфен самому $\mathfrak{A}$.
    \end{lemma}

    \begin{proof}
        Пусть $f$ --- изоморфизм из $\mathfrak{A}$ на некоторый собственный начальный сегмент $\mathfrak{A}$. Тогда $\range(f) = [0, a)$ для некоторого $a \in A$. Поэтому $f(a) < a$ --- противоречие.
    \end{proof}

    \begin{theorem}[о сравнении ВУМ]
        Для любых ВУМ $\mathfrak{A}$ и $\mathfrak{B}$ имеет место ровно один из трёх случаев:
        \begin{enumerate}
            \item \label{WOS_comparability_theorem_A=B} $\mathfrak{A}$ и $\mathfrak{B}$ изоморфны;
            \item \label{WOS_comparability_theorem_AtoB} $\mathfrak{A}$ изоморфно собственному начальному сегменту $\mathfrak{B}$;
            \item \label{WOS_comparability_theorem_BtoA} $\mathfrak{B}$ изоморфно собственному начальному сегменту $\mathfrak{A}$.
        \end{enumerate}

        При этом в пунктах (\ref{WOS_comparability_theorem_AtoB}) и (\ref{WOS_comparability_theorem_BtoA}) соответствующие собственные начальные сегменты определяются однозначно.
    \end{theorem}

    \begin{proof}
        Единственность сегментов в (\ref{WOS_comparability_theorem_AtoB}) и (\ref{WOS_comparability_theorem_BtoA}) и взаимная исключаемость пунктов (\ref{WOS_comparability_theorem_A=B}), (\ref{WOS_comparability_theorem_AtoB}) и (\ref{WOS_comparability_theorem_BtoA}) следуют из предыдущей леммы. Поэтому осталось показать, что один из трёх случаев точно будет иметь место.

        Рассмотрим
        \[\xi := \{(a, b) \in A \times B \mid [0, a)_\mathfrak{A} \simeq [0, b)_\mathfrak{B}\}\]
        По предыдущей лемме $\xi$ и $\xi^{-1}$ являются функциональными.

        Также несложно видеть, что если $f$ --- изоморфизм из $[0, a)_\mathfrak{A}$ на $[0, b)_\mathfrak{B}$, а $a' <_A a$ и $b' <_B b$, то
        \begin{itemize}
            \item $f\upharpoonright_{[0, a')_\mathfrak{A}}$ является изоморфизмом из $[0, a')_\mathfrak{A}$ на $[0, f(a'))_\mathfrak{B}$;
            \item $f^{-1}\upharpoonright_{[0, b')_\mathfrak{B}}$ является изоморфизмом из $[0, b')_\mathfrak{B}$ на $[0, f^{-1}(b'))_\mathfrak{A}$.
        \end{itemize}
        Следовательно, если $a \in \dom(\xi)$, то $[0, a)_\mathfrak{A} \subseteq \dom(\xi)$; если $b \in \range(\xi)$, то $[0, b)_\mathfrak{B} \subseteq \range(\xi)$. Поэтому $\xi$ --- биекция между начальными сегментами $\mathfrak{A}$ и $\mathfrak{B}$. Также следует и то, что $a_1 <_A a_2 \Leftrightarrow f(a_1) <_B f(a_2)$, что значит, что $\xi$ --- изоморфизм между начальными сегментами $\mathfrak{A}$ и $\mathfrak{B}$.

        Если $\dom(\xi) \neq A$, а $\range(\xi) \neq B$, то существуют $a \in A$ и $b \in B$, что $\dom(\xi) = [0, a)_\mathfrak{A}$, а $\range(\xi) = [0, b)_\mathfrak{B}$. Это значит, что $(a, b) \in \xi$ --- противоречие. Значит $\dom(\xi) = A$ или $\range(\xi) = B$, откуда следует желаемое.
    \end{proof}

    \section{Ординалы, кардиналы и важные теоремы \ZFC}

    \subsection{Ординалы}

    \begin{definition}
        $X$ называется \emph{транзитивным}, если $\bigcup X \subseteq X$ (или, что равносильно, $X \subseteq \subsets(X)$).
    \end{definition}

    \begin{definition}
        \[{\in}_X := \{(u, v) \in X \times X \mid u \in v\}\]
    \end{definition}

    \begin{definition}
        \emph{Ординал} или \emph{ординальное число} --- трансфинитное множество $X$, что $\in_X$ --- строгий полный порядок на $X$. Обозначение: $\alpha$, $\beta$, $\gamma$, \dots

        Поскольку $\NN$ (и все его элементы) являются ординалами, то когда речь идёт об ординалах, то пишут не $\NN$, а $\omega$.

        Также вместо $\alpha \in \beta$ можно писать $\alpha < \beta$.
    \end{definition}

    \begin{remark}
        Важно заметить, что для любого ординала $\alpha$ ЛУМ $\langle \alpha, {\in}_\alpha \rangle$ является ВУМ. Так как иначе есть некоторое $X\subseteq \alpha$, что у него нет минимального элемента, значит для любого $x \in X$ найдётся $x' \in X$, что $x' < x$, значит есть бесконечная убывающая последовательность (элементов $X$), но это противоречит аксиоме регулярности.
    \end{remark}

    \begin{statement}
        Пусть $\alpha$ --- ординал, а $X \in \alpha$. Тогда $X$ --- ординал.
    \end{statement}

    \begin{proof}
        \begin{enumerate}
            \item Проверим, что $X$ транзитивно. Пусть $E \in X$, тогда нужно показать, что $E \subseteq X$. Пусть $u \in E$. Тогда $E \in \alpha$, значит $u \in \alpha$. При этом $u \in_\alpha E \in_\alpha X$, значит $u \in_\alpha X$. Это и значит, что $E \subseteq X$.
            \item Заметим, что $X \subseteq \alpha$. Поэтому ${\in}_X = {\in}_\alpha \cap (X \times X)$, поэтому $\in_X$ --- строгий полный порядок.
        \end{enumerate}
    \end{proof}

    \begin{statement}
        Пусть $\alpha$ --- ординал, а $\beta \in \alpha$. Тогда $\beta = [0, \beta)$.
    \end{statement}

    \begin{proof}
        Очевидно следует из транзитивности $\in_\alpha$.
    \end{proof}

    \begin{statement}
        Для любых ординалов $\alpha$ и $\beta$
        \[\alpha \in \beta \quad \Longleftrightarrow \quad \alpha \subsetneq \beta\]
    \end{statement}

    \begin{proof}
        \begin{itemize}
            \item Пусть $\alpha \in \beta$. Тогда $\alpha \subseteq \beta$. Если $\alpha = \beta$, то $\beta \in \beta$, значит $\alpha \in_\beta \beta$, значит $\beta \in_\beta \beta$ --- противоречие со строгостью $\in_\beta$. Значит $\alpha \neq \beta$, значит $\alpha \subsetneq \beta$.
            \item Пусть $\alpha \subsetneq \beta$. Тогда $\beta \setminus \alpha \neq \varnothing$, а значит мы можем определить
                \[y := \text{``наименьший элемент $\beta \setminus \alpha$ в $\langle \beta, {\in}_\beta \rangle$''}\]
                Нетрудно убедиться, что $\alpha$ совпадает с $\{x \in \beta \mid x < \gamma\}$:
                \begin{itemize}
                    \item если $x \in \alpha$, то $\gamma \nleqslant x$ (так как иначе $\gamma \leqslant x \in \alpha$, а значит $\gamma \in \alpha$), а потому $x < \gamma$;
                    \item если $x \in \beta$ и $x < \gamma$, то $x \notin \beta \setminus \alpha$, т.е. $x \in \gamma$.
                \end{itemize}
                Таким образом $\alpha = [0, \gamma) = \gamma$.
        \end{itemize}
    \end{proof}

    \begin{theorem}
        Для любых ординалов $\alpha$, $\beta$ и $\gamma$:
        \begin{enumerate}
            \item $\alpha \nless \alpha$;
            \item $\alpha < \beta < \gamma \Rightarrow \alpha < \gamma$;
            \item либо $\alpha < \beta$, либо $\alpha = \beta$, либо $\alpha > \beta$;
        \end{enumerate}
        Более того для любого непустого множества ординалов $X$:
        \begin{enumerate}
            \setcounter{enumi}{3}
            \item $\bigcap X \in X$, причём $\bigcap$ --- наименьший элемент $X$ в $\langle X, \in_X \rangle$.
        \end{enumerate}
    \end{theorem}

    \begin{proof}
        \begin{enumerate}
            \item Иначе $\alpha \in \alpha$, значит $\alpha \in_\alpha \alpha$ --- противоречие.
            \item $\beta \subseteq \gamma$, следовательно $\alpha \in \gamma$.
            \setcounter{enumi}{3}
            \item Легко видеть, что $\bigcap X$ --- ординал. При этом для любого $\alpha \in X$ верно, что $\bigcap X \subseteq \alpha$, а значит $\bigcap X \leqslant \alpha$. Заметим, что $\bigcap X \nless \bigcap X$, значит есть $\alpha \in X$, что $\bigcap X \nless \alpha$, т.е. $\bigcap X = \alpha$, следовательно $\bigcap X \in X$.
            \setcounter{enumi}{2}
            \item В силу предыдущего пункта, в $\{\alpha, \beta\}$ есть наименьший элемент. Стало быть $\alpha$ и $\beta$ сравнимы по $\leqslant$.
        \end{enumerate}
    \end{proof}

    \begin{corollary}
        Пусть $X$ --- транзитивное множество ординалов. Тогда $X$ --- ординал.
    \end{corollary}

    \begin{proof}
        Действительно, $\in_X$ --- полный порядок на $X$ по только доказанной теореме, значит $X$ --- ординал.
    \end{proof}

    \begin{theorem}
        Пусть $X$ --- множество ординалов. Тогда $\bigcup X$ --- ординал, причём $\bigcup X$ является ``супремумом $X$'' в классе всех ординалов относительно $\in$.
    \end{theorem}

    \begin{proof}
        Очевидно, что $\bigcup X$ --- множество ординалов и что оно транзитивно. Поэтому $\bigcup X$ --- ординал.

        Разумеется, $\bigcup X$ является ``супремумом $X$'' в классе всех ординалов относительно $\subsetneq$, что на ординалах совпадает с $\in$.
    \end{proof}

    \begin{definition}
        Пусть $\alpha$ --- ординал. Тогда
        \[\alpha + 1 := \alpha \cup \{\alpha\}\]
        является ординалом.
    \end{definition}

    \begin{remark}
        Не сложно понять, что $\alpha \subsetneq \alpha + 1$ и нет такого $X$, что $\alpha \subsetneq X \subsetneq \alpha + 1$.
    \end{remark}

    \begin{definition}
        Ненулевой ординал $\alpha$ называется \emph{непредельным}, если есть ординал $\beta$, что $\alpha = \beta + 1$, и \emph{предельным иначе}.
    \end{definition}

    \begin{statement}\ 
        \begin{enumerate}
            \item $\alpha = \beta \Leftrightarrow \alpha + 1 = \beta + 1$. (Что значит, что у каждого непредельного ординала $\alpha$ есть единственный ``предшественник'' $\alpha - 1$.)
            \item \[\bigcup \alpha = \begin{cases}
                \alpha & \text{если $\alpha$ пределен}\\
                \alpha - 1 & \text{если $\alpha$ непределен}
            \end{cases}\]
        \end{enumerate}
    \end{statement}

    \begin{theorem}[о связи ординалов и ВУМ]
        Пусть $\mathfrak{A}$ --- строгий ВУМ. Тогда существует единственный ординал $\alpha$, что $\mathfrak{A} \simeq \langle \alpha, {\in}_\alpha \rangle$.
    \end{theorem}

    \begin{proof}
        Единственность очевидна: для любых ординалов $\alpha$ и $\beta$
        \[\langle \alpha, {\in}_\alpha \rangle \simeq \langle \beta, {\in}_\beta \rangle \quad \Longleftrightarrow \quad \alpha = \beta\]
        Осталось показать существование $\alpha$.

        Рассмотрим
        \[S := \{a \in A \mid \text{существует ординал $\alpha_a$, что $[0, a)_\mathfrak{A} \simeq \langle \alpha, {\in}_\alpha \rangle$}\}\]
        Само собой, для каждого $a \in S$ ординал $\alpha_a$ строго единственен. Поэтому есть
        \[X := \{\alpha_a \mid a \in S\}\]
        Поскольку изоморфизмы переводят начальные сегменты в начальные, то поэтому $X$ транзитивно, да и $\in_X$ является полным строгим порядком. Значит $X$ --- ординал. Рассматривая
        \[f: S \to X, a \mapsto \alpha_a\]
        имеем, что $f$ --- изоморфизм. Тогда если $A \setminus S \neq \varnothing$, то $S = [0, a)$, где $a$ --- наименьший элемент $A \setminus S$. Но тогда $[0, a)_\mathfrak{A} \simeq X$, а значит $a \in S$. Значит $S = A$.
    \end{proof}

    \begin{definition}
        Если $\mathfrak{A}$ --- ВУМ, то $\ord(\mathfrak{A})$ --- это такой ординал $\alpha$, что $\mathfrak{A} \simeq \langle \alpha, {\in}_\alpha \rangle$.
    \end{definition}

    \begin{definition}
        Пусть $\alpha$ и $\beta$ --- ординалы. Тогда определим операции
        \begin{gather*}
            \alpha + \beta := \ord(\langle \alpha, {\in}_\alpha \rangle \oplus \langle \beta, {\in}_\beta \rangle)\\
            \alpha \cdot \beta := \ord(\langle \alpha, {\in}_\alpha \rangle \otimes \langle \beta, {\in}_\beta \rangle)
        \end{gather*}
    \end{definition}

    \begin{remark}
        Важно заметить, что класс $\Ord$ всех ординалов не является множеством. Действительно, если $\Ord$ --- множество, то $\Ord$ --- само ординал, а значит $\Ord \in \Ord$, чего не может быть.
    \end{remark}

    \begin{definition}
        Пусть $X$ --- любое множество, а $\alpha$ --- ординал. Тогда определим
        \[X^{<\alpha} := \{f \mid (\exists \beta < \alpha) f: \beta \to X\} = \bigcup \{X^\beta \mid \beta < \alpha\}\]
    \end{definition}

    \begin{definition}
        Если $f: \beta \to X$, где $\beta$ --- ординал, то $f$ называют \emph{$\beta$-последовательностью}
    \end{definition}

    \begin{theorem}[о трансфинитной рекурсии]
        Фиксируем некоторый ординал $\alpha$. Пусть $h: X^{<\alpha} \to X$. Тогда существует единственная $f: \alpha \to X$, что для всякого $\beta \in \alpha$
        \[f(\beta) = h(f \upharpoonright_\beta)\]
    \end{theorem}

    \begin{proof}
        Пусть $\gamma \in \alpha$. Будем называть $t: \gamma + 1 \to X$ \emph{чудесной}, если для любого $\beta \in \gamma + 1$
        \[t(\beta) = h(t \upharpoonright_\beta)\]
        Рассмотрим
        \[S := \{\gamma \in \alpha \mid \text{существует единственная чудесная $t: \gamma + 1 \to X$}\}\]
        Тогда для каждого $\gamma \in S$ обозначим соответствующую (единственную) чудесную функцию из $\gamma + 1$ в $X$ как $f_\gamma$.

        Заметим, что если $t: \gamma + 1 \to X$ чудесна, то для каждого $\beta < \gamma$ функция $t \cap ((\beta + 1) \times X)$ тоже чудесна. Таким образом, если $\gamma, \beta \in S$, то $f_\beta = f_\gamma \cap ((\beta + 1) \times X)$ (и т.е. $f_\beta \subseteq f_\gamma$).

        Заметим также, что если для некоторого $\gamma \in \alpha$ все $\beta < \gamma$ лежат в $S$, то и $\gamma$ лежит в $S$. Действительно, можно рассмотреть
        \[t_0 := \bigcup \{f_\beta \mid \beta < \gamma\}\]
        Несложно видеть, что $t_0: \gamma \to X$. В таком случае рассмотрим
        \[t := t_0 \cup \{(\gamma, h(t_0))\}\]
        Несложно видеть, что ограничение $t$ на $\beta + 1$ для всех $\beta < \gamma$ есть $f_\beta$. Поэтому дял всех $\beta \in \gamma + 1$ либо $\beta = \gamma$, и тогда
        \[t(\beta) = t(\gamma) = h(t_0) = h(t \upharpoonright_\beta),\]
        либо $\beta < \gamma$, и тогда
        \[t(\beta) = t_0(\beta) = f_\beta(\beta) = h(f_\beta \upharpoonright_\beta) = h(t_0 \upharpoonright_\beta) = h(t \upharpoonright_\beta)\]
        Это значит, что $t$ чудесна. При этом если бы была отличная от $t$ чудесная функция $t': \gamma + 1 \to X$, то у неё должны быть такие же сужения на $\beta + 1$ для каждого $\beta < \gamma$, что и у $t$. Значит она может отличаться только в $\gamma$; но это тоже невозможно, так как
        \[t(\gamma) = h(t \upharpoonright_\gamma) = h(t' \upharpoonright_\gamma) = t'(\gamma)\]
        Поэтому $t$ является единственной чудесной функцией для $\gamma + 1$, что и значит, что $\gamma \in S$.

        Тогда по трансфинитной индукции имеем, что $S = \alpha$.

        Рассмотрим
        \[f := \bigcup \{f_\gamma \mid \gamma \in \alpha\}\]
        Несложно видеть, что $f: \alpha \to X$ и $f$ тоже окажется чудесной (что и требуется). Также если будет вдруг существовать ещё одна чудесная $f': \alpha \to X$, то у неё будут такие же сужения на $\beta + 1$ для каждого $\beta \in \alpha$, что и у $f$, значит $f'$ не будет ничем отличаться от $f$.
    \end{proof}

    \begin{remark*}
        Теорему о трансфинитной рекурсии можно обобщить до параметризованной, используя уже готовую рекурсию.
    \end{remark*}

    \begin{theorem}[о трансфинитной рекурсии, частичной]
        Фиксируем некоторый ординал $\alpha$. Пусть $h: \subseteq X^{<\alpha} \to X$. Тогда существует единственная $f: \subseteq \alpha \to X$, что
        \begin{enumerate}
            \item для всякого $\beta \in \dom(f)$
                \[f(\beta) = h(f \upharpoonright_\beta);\]
            \item либо $\dom(f) = \alpha$, либо $\dom(f) = \gamma$ для некоторого $\gamma < \alpha$, причём $f \notin \dom(h)$.
        \end{enumerate}
    \end{theorem}

    \begin{proof}
        Как обычно, рассмотрим $\text{ы} \notin X$ и положим $X' := X \cup \{\text{ы}\}$. Затем расширим $h$ до $h: (X')^{<\alpha} \to X'$ следующим образом:
        \[h'(g') := \begin{cases}
            h(g')& \text{если $g' \in \dom(h)$}\\
            \text{ы}& \text{иначе}
        \end{cases}\]
        В силу теоремы о трансфинитной рекурсии, найдётся единственная $f': \alpha \to X$, что для любого $\beta \in \alpha$
        \[f'(\beta) = h'(f' \upharpoonright_\beta)\]
        Возьмём
        \[f := f' \cap (\alpha \times X)\]
        Нетрудно убедиться, что $f$ является искомой.
    \end{proof}

    \begin{theorem}[о трансфинитной ``классовой рекурсии'']
        Фиксируем некоторый ординал $\alpha$. Пусть $\Phi(x, y)$ --- тотальное функциональное условие. Тогда существует единственная функция $f$ с $\dom(f) = \alpha$, что для всякого $\beta \in \alpha$
        \[f(\beta) = \llbracket \Phi \rrbracket(f \upharpoonright_\beta)\]
    \end{theorem}

    \begin{proof}
        Несложная модификация доказательства теоремы о трансфинитной рекурсии.
    \end{proof}

    \begin{theorem}[Цермело о полном упорядочении; в \ZFC]
        Для любого $A$ существует $\leqslant$, что $\langle A, \leqslant \rangle$ --- ВУМ.
    \end{theorem}

    \begin{proof}
        Пусть $\eta$ --- функция выбора на $\subsets(A) \setminus \{\varnothing\}$. Тогда для каждого ординала $\alpha$ существует единственная $f_\alpha: \subseteq \alpha \to A$, что
        \begin{enumerate}
            \item для любого $\beta \in \dom(f_\alpha)$
                \[f_\alpha(\beta) = \eta(A \setminus \range(f_\alpha \upharpoonright_\beta))\]
            \item либо $\dom(f_\alpha) = \alpha$, либо $\dom(f_\alpha) = \gamma \in \alpha$, причём $\range(f_\alpha) = A$.
        \end{enumerate}

        Несложно видеть, что $f_\alpha$ --- биекция между $\dom(f_\alpha)$ и $\range(f_\alpha)$, а значит с помощью неё можно построить на $\range(f_\alpha)$ ВУМ, изоморфный $\dom(f_\alpha)$. Поэтому если для некоторого ординала $\alpha$ окажется, что $\dom(f_\alpha) \neq \alpha$, то тогда $\range(\alpha) = A$, а значит мы сможем построить на $A$ ВУМ. Осталось показать, что такое $\alpha$ найдётся.

        Предположим противное: для каждого ординала $\alpha$ верно, что $\dom(f_\alpha) = \alpha$. Рассмотрим
        \[\Phi(x, y) := \text{``$y$ --- ординал''}\wedge x = f_{y+1}(y)\]
        Ясно, что если $\alpha < \beta$, то $f_\alpha \subseteq f_\beta$. Поэтому для любых $\alpha$ и $\beta$
        \[f_{\alpha + 1}(\alpha) = f_{\beta + 1}(\beta) \quad \Longrightarrow \quad \alpha = \beta\]
        Это значит, что $\Phi$ функционально. Поэтому по аксиоме подстановки можно выделить
        \[X := \{y \mid (\exists x \in A) \Phi(x, y)\}\]
        Однако $X$ должно совпадать с $\Ord$ --- противоречие.
    \end{proof}

    \subsection{Кардиналы}
    
    \begin{theorem}[о сравнимости по мощности; в \ZFC]
        Для любых $X$ и $Y$ верно, что $X \preccurlyeq Y$ или $X \succ Y$.
    \end{theorem}

    \begin{proof}
        Прямое следствие из теоремы Цермело и теоремы о сравнении ВУМ.
    \end{proof}

    \begin{definition}
        \emph{Кардинал} или \emph{кардинальное число} --- ординал, неравномощный никакому меньшему ординалу. Обозначение: $\kappa$, $\mu$, $\lambda$.
    \end{definition}

    \begin{statement}
        Для любых кардиналов $\kappa$ и $\mu$
        \[\kappa \sim \mu \quad \Longleftrightarrow \quad \kappa = \mu\]
    \end{statement}

    \begin{statement}
        Для любых кардиналов $\kappa$ и $\mu$
        \[\kappa \preccurlyeq \mu \quad \Longleftrightarrow \quad \kappa \leqslant \mu\]
    \end{statement}

    \begin{proof}
        \begin{enumerate}
            \item Если $\kappa \leqslant \mu$, то очевидно, что $\kappa \preccurlyeq \mu$.
            \item Пусть $\kappa \preccurlyeq \mu$. Предположим противное: $\kappa \nleqslant \mu$. Тогда $\kappa > \mu$, значит $\kappa \succcurlyeq \mu$. Ввиду теоремы Кантора-Шрёдера-Бернштейна, мы получаем, что $\kappa \sim \mu$, а значит $\kappa = \mu$ --- противоречие.
        \end{enumerate}
    \end{proof}

    \begin{theorem}[в \ZFC]
        Для любого множества есть единственный кардинал ему равномощный.
    \end{theorem}

    \begin{proof}
        По теореме Цермело есть ординал $\alpha$, равномощный $X$. Тогда можно определить
        \[\kappa := \bigcap \{\beta \in \alpha + 1 \mid \beta \sim X\}\]
        По уже доказанным утверждениям $\kappa \in \{\beta \in \alpha + 1 \mid \beta \sim X\}$, поэтому $\kappa \sim X$. При этом $\kappa$ является кардиналом, так как иначе есть $\gamma < \kappa$, что $\gamma \sim \kappa$, но тогда $\gamma \in \alpha + 1$ и $\gamma \sim X$, а тогда $\kappa \in \gamma$ --- противоречие. Поэтому у $X$ есть равномощный ему кардинал. А его единственность очевидна.
    \end{proof}

    \begin{definition}
        Кардинал, равномощный множеству обозначается как $\card(X)$ или $|X|$.
    \end{definition}

    \begin{statement}
        Для любых $X$ и $Y$
        \begin{enumerate}
            \item $X \sim Y$ тогда и только тогда, когда $\card(X) = \card(Y)$;
            \item $X \preccurlyeq Y$ тогда и только тогда, когда $\card(X) \leqslant \card(Y)$.
        \end{enumerate}
    \end{statement}

    \begin{definition}
        Для любых кардиналов $\kappa$ и $\mu$ определим
        \begin{gather}
            \kappa + \mu := \card(\kappa \times \{0\} \cup \mu \times \{1\})\\
            \kappa \cdot \mu := \card(\kappa \times \mu)
        \end{gather}
    \end{definition}

    \begin{remark*}
        Важно заметить, что $+$ и $\cdot$ отличаются между ординалами и кардиналами. Например, ординалы
        \[\omega, \qquad \omega + 1, \qquad \omega + \omega, \qquad \omega \cdot \omega\]
        являются попарно различными, а при этом кардиналы
        \[\aleph_0 = \aleph_0 + 1 = \aleph_0 + \aleph_0 = \aleph_0 \cdot \aleph_0\]
        совпадают.
    \end{remark*}

    \begin{statement}
        Для любого ординала существует больший кардинал.
    \end{statement}

    \begin{proof}
        Пусть $\kappa := \card(\subsets(\alpha))$. Если $\alpha \nless \kappa$, то $\kappa \leqslant \alpha$, а значит $\kappa \subseteq \alpha$, $\kappa \preccurlyeq \alpha$, т.е. $\subsets(\alpha) \preccurlyeq \alpha$ --- противоречие с теоремой Кантора. А поэтому $\alpha < \kappa$.
    \end{proof}

    \begin{remark}
        Как и $\Ord$, класс всех кардиналов $\Card$ также не является множеством. Действительно, если $\Card$ --- множество, то $\bigcup \Card = \Ord$ тоже является множеством, чего быть не может.
    \end{remark}
    
    \begin{definition}
        Когда речь идёт о кардиналах, будем говорить, что для всякого кардинала $\kappa$
        \[2^\kappa := \card(\subsets(\kappa))\]
    \end{definition}

    \begin{definition}
        Для каждого кардинала $\kappa$ обозначим
        \[\kappa^+ := \text{``наименьший кардинал, больший $\kappa$''}\]

        $\aleph_0^+$ обозначают $\aleph_1$, $\aleph_1^+$ --- $\aleph_2$, и т.д. На само деле, можно было бы определить $\aleph_\alpha$ для произвольного ординала $\alpha$.
    \end{definition}

    \begin{statement}[Континуум-гипотеза, \CH]
        \[2^{\aleph_0} = \aleph_1\]
    \end{statement}

    \begin{theorem}[Гёдель, 1940]
        Можно доказать, что $\neg \CH$ нельзя доказать в \ZFC.
    \end{theorem}

    \begin{theorem}[Коэн, 1963]
        Можно доказать, что \CH нельзя доказать в \ZFC.
    \end{theorem}

    \subsection{Важные теоремы в \ZFC}

    \begin{definition}
        Пусть $\mathfrak{A}$ --- ЧУМ. \emph{Цепь в $\mathfrak{A}$} --- непустое $S \subseteq A$, индуцирующее ЛУМ.
    \end{definition}

    \begin{theorem}[лемма Цорна; в \ZFC]
        Пусть $\mathfrak{A} = \langle A, \leqslant_A \rangle$ --- ЧУМ с непустым носителем, в которой у любой цепи имеется верхняя грань. Тогда в $\mathfrak{A}$ есть максимальный элемент.
    \end{theorem}

    \begin{proof}
        Пусть $\kappa$ --- какой-нибудь кардинал, больший $|A|$, например, $2^{|A|}$. Пусть также $\eta$ --- функция выбора для $\subsets(A) \setminus \varnothing$. Используя трансфинитную рекурсию, определим $f: \subseteq \kappa \to A$ по правилу
        \[f(\beta) = \eta(\{a' \in A \mid a' >_A a \quad \forall a \in \range(f \upharpoonright_\beta)\})\]
        Легко видеть, что для любых $\beta_1, \beta_2 \in \dom(f)$
        \[\beta_1 < \beta_2 \quad \Longrightarrow \quad f(\beta_1) <_A f(\beta_2)\]
        Из этого мы получаем, что
        \begin{enumerate}
            \item $f$ инъективна. Поэтому $\dom(f) \neq \kappa$, а значит $\dom(f) = \alpha < \kappa$. Причём в $A$ нет элементов, строго больших всех элементов из $\range(f)$.
            \item $\range(f)$ является цепью в $\mathfrak{A}$, значит у него есть верхняя грань $s$.
        \end{enumerate}
        Отсюда выходит, что $s \in \range(f)$, а значит нет элементов как внутри цепи $\range(f)$, так и вне неё больших $s$. Значит $s$ --- максимальный элемент в $\mathfrak{A}$.
    \end{proof}

    \begin{corollary}[в \ZFC]
        Пусть $\mathfrak{A} = \langle A, \leqslant_A \rangle$ --- ЧУМ, в котором у любой цепи имеется верхняя грань. Тогда для каждого $a \in A$ в $\mathfrak{A}$ есть максимальный элемент $a' \geqslant_A a$.
    \end{corollary}

    \begin{proof}
        Случай $A = \varnothing$ тривиален, поэтому будем считать, что $A \neq \varnothing$. Зафиксируем произвольное $a \in A$. Возьмём
        \[B := \{b \in A \mid a \leqslant_A b\} \qquad \text{и} \qquad {\leqslant}_B := {\leqslant}_A \cap B \times B\]
        Очевидно, что $\mathfrak{B} = \langle B, \leqslant_b \rangle$ будет ЧУМ, которое удовлетворяет условию леммы Цорна. Поэтому в $\mathfrak{B}$ есть максимальный элемент $a'$. Тогда несложно понять, что $a'$ будет максимальным и в $\mathfrak{A}$, а также $a' \geqslant_A a$.
    \end{proof}

    \begin{theorem}[в \ZFC]
        Пусть $X$ бесконечно. Тогда $|X \times X| = |X|$.
    \end{theorem}

    \begin{proof}
        Рассмотрим
        \[M := \{f \mid f: U \to U \times U \text{ -- биекция, где $U \subseteq X$ и $U$ бесконечно}\}\]
        Поскольку $X$ бесконечно, у него есть счётное подмножество, равномощное собственному декартовому квадрату, то $M$ непусто. Определим
        \[{\leqslant} := \{(f_1, f_2) \in M \times M \mid f_1 \subseteq f_2\}\]
        Далее будем рассматривать ЧУМ $\mathfrak{M} = \langle M, \leqslant \rangle$.

        Покажем, что условие леммы Цорна для $\mathfrak{M}$ выполнено. Пусть $S$ --- произвольная цепь в $\mathfrak{M}$. Возьмём
        \[f_S := \bigcup_{f \in S} f\]
        Понятно, что $f_S$ --- биекция из $\dom(f_S)$ в $\range(f_S)$, и при этом
        \begin{align*}
            \dom(f_S) &= \bigcup_{f \in S} \dom(f)&
            \range(f_S) &= \bigcup_{f \in S} \range(f)
        \end{align*}
        Очевидно, что $\range(f_S) \subseteq \dom(f_S) \times \dom(f_S)$. Также заметим, что для любых $a_1, a_2 \in \dom(f_S)$ существуют $f_1, f_2 \in S$, что $a_1 \in \dom(f_1)$ и $a_2 \in \dom(f_2)$, а значит $f = f_1 \cup f_2 \in S$ содержит в области определения $a_1$ и $a_2$, что значит, что $(a_1, a_2) \in \range(f) \subseteq \range(f_S)$. Это значит, что $\range(f_S) = \dom(f_S) \times \dom(f_S)$, а значит $f_S \in M$. Так мы имеем, что $f_S$ --- верхняя грань (и даже супремум) для $S$ в $\mathfrak{M}$.

        Тогда, применяя лемму Цорна, получаем максимальный элемент $f_\star$. Обозначим $\dom(f_\star)$ за $Y$.

        Предположим, что $|Y| < |X \setminus Y|$. Тогда $Y$ равномощно некоторому $Z \subseteq X \setminus Y$. Заметим, что
        \begin{align*}
            |Z|
            &\leqslant |Z \times Z|&
            &\leqslant 3 \cdot |Z \times Z|\\
            &= |Y \times Z| + |Z \times Y| + |Z \times Z|&
            &= |(Y \cup Z) \times (Y \cup Z) \setminus Y \times Y|\\
            &\leqslant |(2 \times Z) \times (2 \times Z)|&
            &= |4 \times Z \times Z| \leqslant |Z \times Z \times Z|\\
            &= |Z|
        \end{align*}
        Следовательно по теореме Кантора-Шрёдера-Бернштейна есть биекция $g$ из $Y \times Z \cup Z \times Y \cup Z \times Z$ в $Z$. Рассмотрим $h: (Y \cup Z) \to (Y \cup Z) \times (Y \cup Z)$, определённую по правилу
        \[h(x) := \begin{cases}
            f_\star(x)& x \in Y\\
            g(x)& x \in Z
        \end{cases}\]
        Следовательно $h \in M$ и $h > f_\star$ --- противоречие. Поэтому $|Y| \geqslant |X \setminus Y|$.

        В таком случае
        \[|Y| \leqslant |X| = |Y| + |X \setminus Y| \leqslant |Y| + |Y| = 2 \cdot |Y| \leqslant |Y| \cdot |Y| = |Y|\]
        а значит по теореме Кантора-Шрёдера-Бернштейна $|Y| = |X|$, а потому $|X| = |X \times X|$.
    \end{proof}

    \begin{corollary}[в \ZFC]
        Если $0 < |X| \leqslant |Y|$ и $Y$ бесконечно, то $|X \times Y| = |Y|$.
    \end{corollary}

    \begin{proof}
        Ясно, что
        \[|Y| = |1 \times Y| \leqslant |X \times Y| \leqslant |Y \times Y| = |Y|,\]
        откуда по теореме Кантора-Шрёдера-Бернштейна $|X \times Y| = |Y|$.
    \end{proof}

    \begin{corollary}
        Пусть $|X| \leqslant |Y|$ и $Y$ бесконечно. Тогда $|X \cup Y| = |Y|$.
    \end{corollary}

    \begin{proof}
        Легко видеть, что
        \[|Y| \leqslant |X \cup Y| \leqslant |X| + |Y| \leqslant 2 \cdot |Y| \leqslant |Y|^2 = |Y|,\]
        откуда по теореме Кантора-Шрёдера-Бернштейна $|X \cup Y| = |Y|$.
    \end{proof}

    \begin{corollary}
        Пусть $|X| < |Y|$ и $Y$ бесконечно. Тогда $|Y \setminus X| = |Y|$.
    \end{corollary}

    \begin{proof}
        Легко видеть, что
        \[|Y| = \max\{|X|, |Y|\} = |X \cup Y| = |X \cup (Y \setminus X)| = \max\{|X|, |Y \setminus X|\}\]
        Поскольку $|X| \neq |Y|$, то $|Y| = |Y \setminus X|$.
    \end{proof}

    \begin{corollary}
        Пусть $X$ бесконечно. Тогда $|X^*| = |X|$.
    \end{corollary}

    \begin{proof}
        По определению $|X^* = \bigcup_{n \in \NN} X^n|$. При этом очевидно по индукции, что $|X^n| = |X|$ для $n > 0$; $|X^0| = |\{\varnothing\}| = 1$. Поэтому
        \[|X^*| = |X^0| + \sum_{n \in \NN} |X^{n+1}| = 1 + \sum_{n \in \NN} |X| = 1 + |\NN| \cdot |X| = 1 + |X| = |X|\]
    \end{proof}
\end{document}