

\documentclass[11pt]{book}

\usepackage{amsmath, amssymb, amscd, russcorr, theorem, fancyhdr, epsfig}

\newcommand{\arrow}{{\:\longrightarrow\:}}
\newcommand{\restrict}[1]{{\left|_{{\phantom{|}\!\!}_{#1}}\right.}}
\def\endproof{\hbox{\vrule width 5pt height 5pt depth 0pt}}

\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\epsilon}{\varepsilon}
\renewcommand{\phi}{\varphi}
\renewcommand{\triangle}{\vartriangle}

\newcommand{\version}{version 1.1,\ \   24.03.2008}

\setlength{\headheight}{15pt}
\pagestyle{fancy} \lfoot{\tiny НМУ, весна 2008, первый
курс, лекция 0} 
\cfoot{-- \thepage \ -- } \rfoot{\tiny \sc\version}
\rhead{{\small  Миша Вербицкий}}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  equations                          %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\renewcommand{\theequation}{\thesection.\arabic{equation}}

\makeatletter
\@addtoreset{equation}{section}
\@addtoreset{footnote}{section}
\makeatother



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  listki-new.tex                     %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\def\1{\sqrt{-1}}
\def\rad{\operatorname{\sf rad}}
\def\Alt{\operatorname{\sf Alt}}
\def\Spec{\operatorname{\sf Spec}}
\def\Sym{\operatorname{\sf Sym}}
\def\Id{\operatorname{\sf Id}}
\def\Hom{\operatorname{Hom}}
\def\Vol{\operatorname{Vol}}
\def\Lie{\operatorname{Lie}}
\def\Map{\operatorname{Map}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\Mat}{\operatorname{Mat}}
\newcommand{\cchar}{\operatorname{\sf char}}

\def\Z{{\mathbb Z}}
\def\R{{\mathbb R}}
\def\C{{\mathbb C}}
\def\Q{{\mathbb Q}}
\def\N{{\mathbb N}}


\makeatletter
\begingroup
\gdef\th@upshape{\normalfont
  \def\@begintheorem##1##2{%
        \item[\hskip\labelsep \theorem@headerfont ##1\ ##2.]
%        \writevedomost{\string\mc{\thezadacha} \string & \string & \string 
%        \\ \string \hline}
   }%
\def\@opargbegintheorem##1##2##3{%
   \item[\hskip\labelsep \theorem@headerfont ##1\ ##2\ (##3).]
   \writevedomost{\string\mc{\thezadacha ##3}  \string & \string \grd \string & \string\grp
   \string \\ \string \hline}
    }}
\endgroup

\theoremstyle{upshape}

\newtheorem{zadacha}{Задача}[chapter]

\begingroup
\gdef\th@generic{\normalfont
  \def\@begintheorem##1##2{%
        \item[\hskip\labelsep \theorem@headerfont ##1\ ##2.]
     }%
\def\@opargbegintheorem##1##2##3{%
   \item[\hskip\labelsep \theorem@headerfont ##1\ ##2\ (##3).]
    }}
\endgroup

\theoremstyle{generic}

\newtheorem{opredelenie}[zadacha]{Определение}
\newtheorem{ukazanie}[zadacha]{Указание}
\newtheorem{zamechanie}[zadacha]{Замечание}

\renewcommand{\labelenumi}{\ralph{enumi}.}


\newcommand{\listok}[2]{%
\setcounter{page}{1}
\renewcommand{\@oddhead}{\hfil #2 \hfil}
\renewcommand{\@evenhead}{\hfil #2 \hfil}
\section*{#2}
\refstepcounter{section}
\setcounter{section}{#1}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% VEDOMOST GENERATION
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\newwrite\Vedomost
%\immediate\openout\Vedomost = \jobname.vdm
%\newcommand{\writevedomost}[1]{\immediate\write\Vedomost{ #1 }}
\newcommand{\writevedomost}[1]{}

\def\grd{\psboxit{box .7 setgray fill}{\phantom{\dtt}}\vphantom{666}}
\def\grp{\psboxit{box .7 setgray fill}{\phantom{\pdp}}\vphantom{666}}

\makeatother



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%   Chapter                         %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



  \renewcommand{\chapter}{%
     \secdef\ChapterNumbered\ChapterStarred}

  \def\ChapterNumbered[#1]#2{%
      \addcontentsline{toc}{chapter}{\thechapter. #1}
      \refstepcounter{chapter}
      {
\vspace{\baselineskip}
\chaptermark{#2}
          { {{\noindent\bf\huge \thechapter. \ #2\par}}}
      }
    \vspace{\baselineskip}
}

  \newcommand{\ChapterStarred}[1]{%
      \refstepcounter{chapter}
      \chaptermark{#1}%
      \vspace{\baselineskip}}

  \renewcommand{\chaptermark}[1]{\markboth{#1}{#1}}
                             



\newcommand{\пример}{%
     \refstepcounter{zadacha}
     {\noindent\bf Пример \thechapter.\arabic{zadacha}:\ }}
\newcommand{\лемма}{%
     \refstepcounter{zadacha}
     {\noindent\bf Лемма \thechapter.\arabic{zadacha}:\ }}
\newcommand{\теорема}{%
     \refstepcounter{zadacha}
     {\noindent\bf Теорема \thechapter.\arabic{zadacha}:\ }}
\newcommand{\утверждение}{%
     \refstepcounter{zadacha}
     {\noindent\bf Утверждение \thechapter.\arabic{zadacha}:\ }}

\def\хфилл{\hfill}
\def\ноиндент{\noindent}
\def\бф{\bf}
\def\ем{\em}
\def\ит{\it}
\def\задача{\begin{zadacha}}
\def\ез{\end{zadacha}}
\def\замечание{\begin{zamechanie}}
\def\еза{\end{zamechanie}}
\def\указание{\begin{ukazanie}}
\def\еу{\end{ukazanie}}
\def\eu{\end{ukazanie}}
\def\определение{\begin{opredelenie}}
\def\ео{\end{opredelenie}}
\def\eo{\end{opredelenie}}
\def\goth{\mathfrak}
\def\енум{\begin{enumerate}} 
\def\ее{\end{enumerate}}
\def\ee{\end{enumerate}}
\def\итем{\item $\bullet$ %
    \writevedomost{\string & \ralph{enumi} \string &\string & \string \\ \string \hline } }

\begin{document}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setcounter{chapter}{-1}
\lhead{{\scriptsize  Топология, лекция 0: применение аксиома выбора}}
\chapter{Топология, лекция 0: \\ Аксиома выбора и ее приложения}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Сечение отображения}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Пусть $\phi:\; A \arrow B$ сюрьективное отображение
множеств. {\бф Сечением} отображения $\phi$ называется
отображение $\psi:\; B \arrow A$, такое, что
$\psi\circ \phi=\Id$. 


\begin{figure}[ht]
\begin{center}\ \\
\epsfig{file=sechenie.eps,width=0.35\linewidth}\\
{\small \em Сечение сюрьективного отображения}
\end{center}
\end{figure}

Аксиома выбора утверждает, что 
каждое сюрьективное отображение имеет сечение.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Один из подходов к обоснованию математики 
называется {\бф формализмом}, и принадлежит он 
Давиду Гильберту. В начале XX-го века 
математика оказалась в кризисе, сотрясаемая
парадоксами, которые следовали
из ``наивной теории множеств'', придуманной Георгом
Кантором. Стало ясно, что обращение с произвольно
взятыми бесконечными множествами опасно и приводит
к противоречиям. В надежде избежать парадоксов, 
математики (Фреге, Гильберт, Цермело, Рассел-Уайтхед)
стали строить аксиоматическое обоснование
для теории множеств, надеясь, что аккуратное
следование логическим построениям поможет
избежать парадоксов. 

Система аксиом, предложенная Фреге, оказалось
противоречивой, основания математики по версии
Рассела-Уайтхеда -- слишком сложными, и к настоящему
времени канонической стала система аксиом, 
предложенная в 1908-м году Эрнстом Цермело,
и улучшенная в 1922 Адольфом Френкелем и 
(независимо от него) Торальфом Сколемом
(Adolf Fraenkel, Thoralf Skolem). 
В учебниках встречается немало 
версий системы Цермело-Френкеля,
но все они эквивалентны.

\begin{figure}[ht]
\begin{center}\ \\
\epsfig{file=Zermelo.eps,width=0.5\linewidth}\\
{Ernst Friedrich Ferdinand Zermelo\\
(1871 - 1953)}
\end{center}
\end{figure}


Цермело провел 3 года (1905-1908),
пытаясь доказать, что его система аксиом
непротиворечива (не приводит к противоречию).
Вплоть до 1930-х годов, Гильберт с коллегами были
уверены, что в скором времени удастся доказать
непротиворечивость системы аксиом Цермело-Френкеля,
и аксиоматическая теория множеств станет фундаментом
для всей математики. 

В 1931-м году, Курт Гёдель доказал, что 
непротиворечивость Цермело-Френкеля недоказуема.
Если точно, Гедель доказал, что 
невозможно доказать непротиворечивость 
любой системы аксиом в математическом языке,
достаточно сильном, чтобы сформулировать
на нем утверждения арифметики, если из этой системы
аксиом следуют аксиомы Пеано (существование 
натуральных чисел и принцип индукции).
Еще точнее -- Гедель доказал невозможность
доказательства средствами, допускающими 
формализацию в рамках того же самого 
математического языка.

Отмечу, что {\em опровергнуть} непротиворечивость
такой системы аксиом как раз весьма просто --
надо вывести из аксиом противоречие. Таким образом,
к примеру, была опровергнута система аксиом Готлоба Фреге.

Многие математики убеждены в 
непротиворечивости системы аксиом Цермело-Френкеля;
другие считают, что в случае противоречий
будет изобретена новая система аксиом,
и осмысленную часть математических утверждений
с легкостью переведут на новый язык 
(и так до бесконечности, по мере обнаружения
противоречий). Именно этой точке зрения
следовала группа Бурбаки.

Есть немало математиков, считающих, что
аксиоматический метод порочен сам по себе.
Эта точка зрения была выдвинута голландским математиком
Брауэром (Luitzen Egbertus Jan Brouwer), знаменитым
топологом, в 1908-м году, в статье, провокативно
озаглавленной ``De onbetrouwbaarheid der 
logische principes'' -- ``О сомнительности
основ логики''. Брауэр считал, что классическая
(аристотелева) логика не может быть применима
к бесконечным множествам, и все математические
исследования, которые основаны на таких
применениях -- неправильны.
Особенно Брауэру не нравился принцип исключенного
третьего, на котором основаны популярные
доказательства ``от противного''. На протяжении 1920-х
годов Брауэр был редактором журнала Mathematische Annalen,
и он принципиально возвращал авторам все статьи, где
использовались доказательство от противного.

Брауэр называл свою философию ``интуиционизмом''.
В середине XX-го века русские математики, близкие к 
Маркову и Колмогорову, развили свою версию философии 
интуиционизма, под названием ``конструктивизм'';
как и интуиционисты, конструктивные математики
отрицают классическую математику, точнее -- 
все неявные доказательства существования.

С точки зрения конструктивиста, любой математический
объект должен быть задан явно. Например, действительное
число в конструктивной математике это алгоритм его
вычисления с любой точностью, плюс оценка скорости 
сходимости этого алгоритма.

Исследования конструктивистов оказались очень
полезны в компьютерных науках, теории алгоритмов
и лингвистике.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Аксиома выбора и ее конкуренты}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Большой части математиков (даже не следующих
экзотическим философиям) свойственно недоверие
к неявным построениям. Действительно, явный
пример числа (в виде ряда, к примеру)
гораздо удобнее иметь, чем теорему вида
``существует такое число, что...''.

Тем не менее, аргументами ``от противного''
и неявными построениями по необходимости 
пользуются почти все математики, потому что 
если от них отказаться, придется отказываться
от большого числа полезных утверждений,
не имеющих явного доказательства.

Самым патологическим примером ``неявной
конструкции'' является аксиома выбора,
которая утверждает существование объектов,
которые заведомо не могут быть построены
никакой явной конструкцией.

Ближе к концу 1920-х годов, 
оказалось, что аксиома выбора позволяет доказывать
(наряду с верными и полезными) утверждения
чрезвычайно сомнительные и противоречащие
физической интуиции. Так, в 1924-м 
году Банах и Тарский обнаружили парадоксальное
разложение шара в $\R^3$ в счетное количество
частей, из которых можно сложить два таких
же шара. Сейчас известно, что шар можно
разложить в 5 частей, и сложить из них два таких
шара, изометрически передвигая эти части в  $\R^3$.

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

Впрочем, исключение аксиомы выбора не избавит
математику от противоречий: непротиворечивость
системы Цермело-Френкеля с аксиомой выбора\footnote{Эту систему
аксиом часто обозначают ZF+AC.} равносильна непротиворечивости
Цермело-Френкеля без нее.

Тем не менее, хорошим тоном считается
не пользоваться аксиомой выбора по возможности,
или пользоваться ею, всякий раз обозначая
факт неявности выбора.

В математике (кроме очень экзотических областей)
без аксиомы выбора довольно часто удается
обойтись. Основные утверждения, для которых
нужна аксиома выбора, такие.

1. Теорема о существовании максимальных идеалов
(см. лекцию 9).

2. Теорема о существовании базиса в любом бесконечномерном
векторном пространстве (``базиса Коши-Гамеля'').

3. Теорема Хана-Банаха о существовании замкнутой 
гиперплоскости, разделяющей два выпуклых, непересекающихся, замкнутых
подмножества в топологическом векторном пространстве.

4. Теорема Тихонова о компактности произведения
бесконечного количества компактов.

Аксиома выбора влечет
много утверждений, которые не нужны для доказательства
полезных теорем, и противоречат
интуиции -- наподобие парадокса Банаха-Тарского.
Основная проблема, которая следует из 
принятия аксиомы выбора -- существование
{\бф неизмеримых множеств}, множеств, для
которых не определена мера Лебега ({\bf мерой
Лебега} в математике называется 
понятие ``объема подмножества" в $\R^n$;
неизмеримые подмножетва -- подмножества,
для которых не определен объем).
Множества, которые фигурируют в парадоксе
Банаха-Тарского, очевидно неизмеримы: иначе
суммарный объем пяти частей, на которых
разбит шар, не мог бы равняться удвоенному
объему шара.

Существуют аксиомы теории множеств, которые
противоречат аксиоме выбора; самая известная
из них -- аксиома детерминированности
(axiom of determinacy),
из которой, среди прочего, следует,
что любое подмножество $\R^n$ измеримо.

Неизвестно, следует ли из непротиворечивости
ZF+AC непротиворечивость системы Цермело-Френкеля
с аксиомой детерминированности (ZF+AD). Другими
словами, ZF+AD может оказаться противоречива,
даже если ZF+AC непротиворечива. Поэтому
ZF+AD не нашла широкого употребления.

Другая причина, по которой аксиомы, отрицающие
аксиому выбора, не нашли употребления, такая.
Пусть $X$ и $Y$ -- два множества. Из аксиомы выбора
следует, что $X$ равномощно подмножеству $Y$, либо
$Y$ равномощно подмножеству $X$. Оказывается,
что это утверждение {\ем равносильно} аксиоме выбора.
Поэтому из любой аксиомы, отрицающей аксиому
выбора, следует существование таких множеств
$X$ и $Y$, что $X$ не равномощно подмножеству
$Y$, а $Y$ не равномощно подмножеству $X$.
Вместо изящной иерархии кардинальных
чисел,\footnote{{\bf Кардиналом}, или 
{\bf кардинальным
числом}, называется класс равномощных
множеств. Согласно теореме Кантора-Бернштейна, 
если одно множество равномощно подмножеству
другого, а другое -- подмножеству первого,
эти множества равномощны. Поэтому из двух
неравномощных множества, одно равномощно
подмножеству другого, но не наоборот.
Это задает отношение порядка на кардинальных
числах, которое и называется {\бф иерархия
кардиналов}.}
построенной Кантором, мы получаем огромное
количество множеств, которые никак не соизмеримы
по мощности. 

Вместо использования аксиомы выбора
можно пользоваться ее слабой формой,
которая называется {\бф аксиома зависимого выбора}
(dependent choice). Аксиома зависимого выбора
утверждает следующее. Пусть дано  множество $X$,
и в нем подмножество $V\subset X \times X$
такое, что $\pi_1(V)=X$, где $\pi_1$ -- проекция
на первый сомножитель. Тогда есть бесконечная
последовательность $\{x_i\}$
такая, что $(x_i, x_{i+1})\in V$, для любого $i$.

Система аксиом Цермело-Френкеля без аксиомы
выбора, но с зависимым выбором (ZF+DC)
достаточна для почти всех задач,
где необходим выбор, но недостаточна 
для утверждений 1-4, перечисленных выше. 
Также она следует из аксиомы детерминированности.

Любопытно, что непротиворечивость
Цермело-Френкеля равносильна
непротиворечивости системы аксиом,
состоящей из ZF+DC плюс аксиомы
"каждое подмножество $\R^n$
измеримо". Кроме того, DC следует 
из аксиомы детерминированности.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Вполне упорядоченные множества}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\определение
Пусть $X$ -- множество, а $R\subset X\times X$ -- бинарное
отношение на множестве $X$, обозначенное $x_1 \prec x_2$.
Это отношение называется {\бф отношением частичного
порядка} (partial order), если верны следующие утверждения
\begin{description}
\item[транзитивность:] из $x\prec y$ и $y\prec z$ следует
$x\prec z$.
\item[асимметричность:] если $x\prec y$, то невозможно
$y\prec x$.
\end{description}
Множество $(X, \prec)$ с отношением частичного
порядка называется {\bf частично упорядоченное множество}.
\ео

\определение
Пусть $(X, \prec)$ -- частично
упорядоченное множество. Если для каких-то $x, y\in X$ имеет
место  $x\prec y$ либо $y\prec x$, мы говорим,
что $x$ и $y$ {\бф сравнимы}.
Отношение $\prec$ называется {\бф отношением линейного
порядка} (total order), если любые два элемента сравнимы. Множество
$(X, \prec)$ с отношением линейного порядка
называется {\бф линейно упорядоченное множество}.

Линейно упорядоченные множества также называются
{\бф монотонно упорядоченными}, или просто {\бф упорядоченными}.
\ео

Если $x=y$ или $x\prec y$, мы пишем $x\preccurlyeq y$.


\определение
Пусть $(X, \prec)$ -- линейно
упорядоченное множество, а $Y \subset X$ -- его
подмножество. Элемент $y_0\in Y$ называется {\бф
минимальным}, если  для любого $y\in Y$, 
имеем $y_0\preccurlyeq y$. Линейно упорядоченное
множество называется {\бф вполне упорядоченным}
(well-ordered set),
если любое его подмножество имеет минимальный
элемент. Отношение порядка на таком множестве
называется {\бф отношение полного порядка}.
\ео


\определение
{\бф Начальным элементом} вполне упорядоченного
множества называется его минимальный элемент.
{\бф Отрезком} линейно упорядоченного
множества $(X, \prec)$ называется подмножество 
$Y\subset X$ такое, что для любых $x, z\in Y$,
и любого $y\in X$ такого, что $x\prec y\prec z$,
имеем $y\in Y$. {\бф Начальным отрезком}
вполне упорядоченного
множества называется отрезок, содержащий
минимальный элемент. 
\ео

\замечание
Пусть $X_0\subset X$ -- начальный отрезок 
вполне упорядоченного множества, $x_0$ его
начальный элемент, а $x$ -- минимальный
элемент в $X \backslash X_0$ (мы предполагаем,
что это множество непусто). 
Легко видеть, что $X_0$ -- множество всех
$y$ таких, что $x_0\preccurlyeq y\prec x$
(докажите это).
Мы обозначаем такой отрезок $[x_0, x[$.
\еза


Вполне упорядоченные множества изобрел Георг
Кантор, создатель теории множеств. Кантор
базировал свою теорию множеств на понятии
вполне упорядоченного множества и понятии ординала.


\begin{figure}[ht]
\begin{center}\ \\
\epsfig{file=Cantor.eps,width=0.45\linewidth}\\
{Georg Ferdinand Ludwig Philipp Cantor\\
(1845 - 1918)}
\end{center}
\end{figure}

\определение
Два вполне упорядоченных множества называются
{\бф изоморфными}, если между ними есть
биекция, сохраняющая порядок. Классы изоморфизма
вполне упорядоченных множеств называются
{\бф ординалами}, или же {\бф ординальными числами}.
\ео

\замечание
Ординалы можно складывать
(для этого надо взять объединение $X \coprod Y$ двух
непересекающихся вполне упорядоченных множеств,
и положить $X \prec Y$). Это сложение некоммутативно,
но ассоциативно. Кроме того, ординалы можно умножать.  
Полный порядок на произведении $X\times Y$ задается так:
\[ (x,y) \prec (x', y') \text{ \ если\ } x\prec x',
\text{\ либо\ } x=x', y\prec y'.
\]
\еза

\задача
Докажите, что эти определения задают
вполне упорядоченные множества. Докажите
ассоциативность и умножения и сложения
и дистрибутивность слева сложения относительно
умножения. Приведите примеры, когда
сложение и умножение ординалов
не коммутативно и не дистрибутивно
справа.\footnote{Дистрибутивность слева:
$x\cdot (y+z) = x\cdot y +x\cdot z$. Дистрибутивность
справа: $(y+z)\cdot x = y\cdot x + z\cdot x$.}
\ез


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\теорема\label{_vpolne_upo_vlo_Teorema_}
Пусть $X$, $Y$ -- вполне
упорядоченные множества. Тогда 
$X$ изоморфно начальному отрезку $Y$,
либо $Y$ изоморфно начальному отрезку $X$.
Более того, такой изоморфизм определен
однозначно.

\хфилл

\ноиндент
{\бф Доказательство:}
Пусть $Z$ -- множество пар $(X_1, Y_1)$ 
изоморфных начальных отрезков $X$ и $Y$.

\хфилл

\ноиндент
{\бф Шаг 1.}
Изоморфизм начальных отрезков
$(X_1, Y_1)$ определяется однозначно
множеством $X_1$. В самом деле,
пусть существует два различных вложения
$\phi:\; X_1\arrow Y$ и 
$\phi':\; X_1\arrow Y$,
задающие изоморфизм $X_1$ и начального
отрезка $Y$. Обозначим за $x$ минимальный
элемент $X_1$, такой, что $\phi(x) \neq \phi'(x)$.
Тогда $\phi\restrict{[x_0, x[}= \phi'\restrict{[x_0, x[}$.
Поскольку $\phi$ и $\phi'$ -- изоморфизм,
из этого следует, что $\phi(x) = \phi'(x)$.


\хфилл

\ноиндент
{\бф Шаг 2.}
Мы получили, что $Z$ упорядочено по включению
и это задает на $Z$ полный порядок (докажите). 
Пусть $x$ -- минимальный элемент
$X$, не принадлежащий $X_1$ для какого-то
$(X_1, Y_1)\in Z$. Если такого нет,
это значит, что $X$ изоморфен начальному
отрезку $Y$. Если $Y_1=Y$, мы все доказали.
В противном случае, начальный отрезок
$[x_0, x[$ изоморфен начальному отрезку
$[y_0, y[$, следовательно, отрезок
$[x_0, x]$ изоморфен $[y_0, y]$.
Мы пришли к противоречию. Это
доказывает Теорему \ref{_vpolne_upo_vlo_Teorema_}.
\endproof

\хфилл

Теоремой Цермело называется следующее утверждение,
доказанное  Эрнстом Цермело в 1904-м году.

\хфилл

\теорема
(Теорема Цермело, "well-ordering theorem")
Любое множество может быть вполне упорядочено.

\хфилл

Теорема Цермело равносильна аксиоме выбора;
мы докажем это немного погодя.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Лемма Цорна и теорема Цермело}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Другое утверждение, также равносильное аксиоме выбора -
лемма Цорна. 

Пусть $(S, \prec)$ -- частично упорядоченное
множество. Элемент $x\in S$ называется
{\бф максимальным}, если не существует $y\in S$ с $x\prec y$.
Для подмножества $S_1\subset S$ и $x\in S$, 
мы пишем $S_1 \preccurlyeq х$, если для каждого
$\xi \in S_1$ имеем $\xi \preccurlyeq x$.


\хфилл

\теорема
(лемма Цорна) Пусть $(S, \prec)$  -- частично упорядоченное
множество, причем для любого вполне упорядоченного 
подмножества $S_1\subset S$ найдется элемент $\xi\in S$
такой, что $S_1 \preccurlyeq \xi$. Тогда в $S$ найдется максимальный
элемент.

\хфилл


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\теорема\label{_AC_ZL_WOT_Teorema_}
Следующие утверждения равносильны:

\begin{description}
\item[ZL] Лемма Цорна.
\item[WOT] Теорема Цермело. 
\item[AC] Аксиома выбора.
\end{description}


\ноиндент
{\бф Доказательство:} 
Отметим, что полностью аккуратное доказательство
Теоремы \ref{_AC_ZL_WOT_Teorema_} требует
развития аксиоматической теории множеств.

\хфилл

\noindent
{\бф ZL $\Rightarrow$ WOT:}
Пусть $X$ -- любое множество, а $S$ -- множество
всех пар $(X_1, \prec)$, где $X_1\subset X$ -- подмножество,
а $\prec$ -- отношение полного порядка на $X_1$.

Рассмотрим отношение частичного порядка на $S$:
$(X_1, \prec) < (X_2, \prec)$, если $(X_1, \prec)$ это начальный
отрезок $(X_2, \prec)$. Легко видеть, что условие
леммы Цорна выполнено для $(S, <)$: если
$S_1\subset S$ вполне (и даже линейно) упорядочено, объединение 
$\Xi\subset X$ всех элементов $S_1$ с естественным отношением
порядка -- вполне упорядочено и удовлетворяет $S_1\leq\Xi$.
Поэтому в $S$ есть максимальный элемент
$(\Xi, \prec)$. Если $\Xi \neq X$, возьмем $\xi \in X \backslash \Xi$,
и определим отношение порядка на $\Xi_1:=\Xi \cup \{\xi\}$,
положив $\Xi \prec \xi$. Мы получим, что $\Xi_1$ -- вполне
упорядоченное множество, начальным
отрезком которого является $\Xi$,
а значит $\Xi$ не максимально. Мы пришли
к противоречию; следовательнo $\Xi=X$.
Поэтому $X$ вполне упорядочено.

\хфилл

\ноиндент
{\бф WOT $\Rightarrow$ AC:}
Пусть $X\stackrel\phi \arrow Y$ -- сюрьекция, а $X$ вполне
упорядочено. Определим отображение $Y \stackrel\psi\arrow X$,
взяв за $\psi(y)$ минимальный (в смысле полного порядка)
элемент $\phi^{-1}(y)$. Легко видеть, что это сечение.

\хфилл

\ноиндент
{\бф AC $\Rightarrow$ ZL.} 

\хфилл

\ноиндент
{\bf  Шаг 1:}
Пусть $(S, \prec)$ -- частично упорядоченное множество,
удовлетворяющее условиям леммы Цорна, и не содержащее
максимального элемента. Тогда для каждого вполне
упорядоченного подмножества $S_1\subset S$, 
найдется $\xi \succcurlyeq S_1$. Поскольку $\xi$
не максимален, найдется $\xi_1\in S$ такой, что
$\xi_1 \succ \xi$, а значит, $\xi \succ S_1$.

\хфилл

\ноиндент
{\bf  Шаг 2:}
Пусть ${\goth S}$ -- множество
вполне упорядоченных подмножеств $S$,
а $\gamma:\; {\goth S}\arrow S$ -- отображение,
переводящее $S_1 \subset S$ в элемент $\xi\in S$,
удовлетворяющий $\xi \succ S_1$. 
Такое отображение существует в силу аксиомы выбора.
Для доказательства этого, рассмотрим множество
всех пар 
\[ {\goth R}:= \{ (S_1 \in {\goth S}, \xi \in S) \ | \  \xi \succ S_1\}
\]
Естественная проекция ${\goth R}\arrow {\goth S}$
сюрьективна, что доказано на шаге 1. Сечение
${\goth R}\arrow {\goth S}$ в композиции с проекцией
${\goth R}\arrow S$ задаст искомое отображение $\gamma$.



\хфилл

\ноиндент
{\bf  Шаг 3:}
Пусть $\Theta$ -- множество вполне упорядоченных
подмножеств $P\subset S$ таких, что
для каждого $p\in P$, начальный отрезок
$[p_0, p[$ удовлетворяет $p = \gamma([p_0, p[)$.
Когда $p=p_0$, это значит, что
$p_0=\gamma(\emptyset)$.

Множество $\Theta$ вполне упорядочено по вложению.
В самом деле, возьмем $P, Q\in \Theta$,
и пусть $p$ -- минимальный элемент $P$
такой, что отрезок $[p_0,p[$ лежит в $Q$,
а $[p_0,p]$ уже не лежит в $Q$.
Поскольку $p=\gamma([p_0,p[)$, а
$[p_0,p[$ лежит в $Q$, из $p\notin Q$ следует,
что $Q=[p_0,p[$.

\хфилл

\ноиндент
{\bf  Шаг 4:}
Мы получили, что объединение
$P_\infty:=\bigcup_{P\in\Theta} P$ лежит в $\Theta$.
Это невозможно, потому что объединение
$P_\infty \cup \gamma(P_\infty)$ строго больше
$P_\infty$, и тоже лежит в $\Theta$.
Мы пришли к противоречию. Лемма Цорна доказана.
\endproof








\end{document}