

\documentclass[11pt]{book}

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

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


\makeatletter

\@ifundefined{Bbb}
     {\newcommand{\Bbb}[1]{{\mathbb #1}}}%
{}%     {\edef\Bbb#1{{\Bbb #1}}}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%       Pagestyle                                %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 
\newcommand{\ps@verbit}{%
  \renewcommand{\@oddhead}{%
          \scriptsize
          {Геометрия и алгебра}
          \hfil\tiny {М. Вербицкий, \@date}}
  \renewcommand{\@evenhead}{\@oddhead}
  \renewcommand{\@oddfoot}{\hfil\thepage\hfil}
  \renewcommand{\@evenfoot}{\@oddfoot}}
 
\pagestyle{verbit}


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

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

\@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\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{\subs}[1]{{\bigskip \bf\large {\centerline #1}\bigskip}}
\newcommand{\sttr}{{\bf(*)}}
\newcommand{\shrk}{{\bf(!)}}
\newcommand{\doublesttr}{{\bf(**)}}

\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\бф{\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}

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

{
\small
\renewcommand{\contentsname}{Содержание}
\tableofcontents
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

\chapter{Введение}
\label{_Intro_Section_}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Краткое описание}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

Можно читать ее по частям или целиком;
например, решать задачи, пропуская текст лекций.
"Геометрическая" часть задач и лекций не очень
связана с алгебраической, а лекции дополняют
листки с задачами. Задачи разбиты на две группы
(простые задачи без звездочки и сложные - со звездочкой),
можно решать либо все простые задачи, либо все сложные,
либо и те и другие.

В задачах (и в лекциях) излагается курс алгебры и
геометрии, в таком примерно объеме.

\хфилл

Алгебра:

\begin{itemize}

\item 0. Группы, кольца, поля. Действительные и
комплексные числа. Теорема Евклида-Гаусса
об однозначности разложения на простые множители.
Решение простейших диофантовых уравнений.

\item 1. Конечномерные векторные пространства.
 Базис, размерность. Билинейные, полилинейные формы,
двойственные пространства. Определение тензорного 
произведения векторных пространств.
Симплектические и квадратичные формы. 

\item 2. Грассманова алгебра и определители.

\item 3.  Линейные операторы. Полупростота,
нильпотентность. Теорема Кэли-Гамильтона.
Жорданова нормальная форма.

\item 3. Алгебраические расширения полей. Артиновы
коммутативные алгебры. Расширения Галуа.

\item 4. Представления конечных групп.

\item 5. Основная теорема теории Галуа.

\end{itemize}



Геометрия:

\begin{itemize}
\item 0. Метрические пространства. 
Последовательности Коши, пределы, пополнение
метрических пространств. Теорема Хопфа-Ринова.
Геодезические в полных метрических пространствах.
Векторные пространства с нормой.

\item 1. Теоретико-множественная топология
(определение непрерывных отображений, компактность,
отделимость, счетная база).

\item 2. Лемма Урысона и теорема о метризации
нормального топологического пространства со счетной базой.

\item 3.  Теорема Тихонова о компактности, равномерная
сходимость, теорема Арцела-Асколи. 
Конструкция кривой Пеано.

\item 4. Фундаментальная группа, свободные группы,
гомотопическая эквивалентность, накрытия Галуа,
конструкция универсального накрытия.
\end{itemize}

Последние 3-4 листка по геометрии и по алгебре
повторяют друг друга, местами дословно. Дело в том,
что группа Галуа устроена аналогично фундаментальной
группе, а накрытие топологического пространства -
конечному расширению полей. Пользуясь этой аналогией,
Гротендик построил фундаментальную группу,
пользуясь только алгебраическими методами
(этот раздел математики называется {\ем этальной
геометрией}). 

В. И. Арнольд прочел основанный на этой аналогии
курс теории Галуа в физико-математическом интернате 18;
впоследствии его лекции были записаны В. М. Алексеевым
("Теорема Абеля в задачах и решениях"). 

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

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

Кроме этого, первокурсник должен знать основы анализа;
их можно подчерпнуть в учебнике В. А. Зорича
"Математический анализ" и в учебнике Лорана
Шварца "Анализ".

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

Соавтором и редактором листочков с задачами
был Дима Каледин, которому автор безмерно благодарен.
Спасибо Марине Прохоровой за редакторскую работу над
задачами и А. Х. Шеню за ряд ценных замечаний. 
Структура книги отражает программу, составленную
А. Х. Шенем,  В. А. Гинзбургом и другими 
преподавателями маткласса 57 школы, где учился 
автор. Другим источником идей и вдохновения были
блестящие учебники "Теорема Абеля в задачах 
и решениях" Алексеева и "Теоремы и задачи 
функционального анализа" Кириллова и Гвишиани.




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

\section{Матклассы: обучение по листочкам}

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

В 1970-е в московских матшколах кристаллизовалась
необычная форма обучения математике. Ее возникновение
часто приписывают Н. Н. Константинову, который работал
в 57, 91 и 179 школах. По этой
системе выучились сотни матклассов, и каждый вносил
преподаватель нечто свое в программу и в подход к
обучению. Самым известным на настоящим момент практиком
матшкольного обучения по листочком является
Б. М. Давидович, завуч московской школы 57;
автора этой книги учили А. Х. Шень, В. А. Гинзбург,
Б. П. Гейдман и А. Ю. Вайнтроб, и он благодарен им сверх 
всякой меры.

Здесь был бы уместен исторический очерк матшкольного
образования, но пока придется ограничиться этим куцым сообщением.
Автор заранее приносит извинения всем, кого он не упомянул.

ПОРТРЕТ КОНСТАНТИНОВА - ???

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

На уроках ``специальной математики''
никто не стоит у доски с указкой и мелом;
все (или почти все) общение школьника с преподавателями
ведется за партой и тет-а-тет, либо в походах.
Школьникам выдается листок с задачами, обыкновенно -
по одному или два в неделю; через какое-то время
после выдачи листочка, студенты должны ``сдать
задачи'', то есть рассказать их преподавателям 
на уроке. При такой системе преподавателей на
класс из 30 человек требуется где-то 5-10.

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

Преподаватели подбираются из числа энтузиастов 
подобного обучения, профессиональных математиков
и студентов; в основном это - выпускники матклассов. 
Они разъясняют школьникам непонятные места.
Также школьникам не возбраняется находить
решение задач в книжках либо (когда совсем припрет)
спрашивать у товарищей. Принято считать, что эта часть
обучения не менее важная, чем собственно
решение задач. Действительно, свободное 
обращение с литературой и способность рассказать
либо выслушать нечто математическое не менее важна,
чем решение задач.

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

На протяжении 1980-х программа матклассов сложилась
окончательно, и с тех пор остается практически неизменной.
В общих чертах идеализированная программа 
матшколы устроена примерно так. 

\begin{itemize}
\item Обучение ведется 
3 или 4 года. На первый год, школьники приучаются
обращению с множествами (элементарной теории множеств,
классам эквивалентности, отображениям, наложениям, вложениям 
и биекции, равномощности, счетным и континуальным множествам). 
Излагаются начала аксиоматического подхода.
Определяются понятия элементарной алгебры: группы, кольца 
и поля. Вводится алгоритм Евклида, его используют
для доказательства однозначности разложения на
множители в кольце целых чисел.

\item На второй год, школьники
изучают основы анализа (пределы, ряды, непрерывность
и дифференцируемость функций на прямой),
свойства логарифма и экспоненты. Излагается аксиоматическое
определение вещественных чисел (обыкновенно, через 
последовательности Коши). Проходят комплексные числа
и их геометрическую интерпретацию. Выводят из свойств
комплексных чисел тождества для тригонометрических 
функций, как обычные (формула косинусов и синусов),
так и необычные (формула для $\sin^n(x)$ и т.д.).
 Также изучают
начала линейной алгебры (конечномерные пространства,
базис, размерность).

\item На третий год, школьники изучают основы 
теории метрических пространств (компактность,
пополнение) и топологии (аксиоматическое определение
топологического пространства, топологические
свойства метрических пространств, аксиомы
отделимости). В курсе алгебры школьники
усваивают определение p-адических чисел, 
классификацию конечных полей и элементы 
теории Галуа.
\end{itemize}


\section{Зачем это}

Матшкольники, которые попадают на Мехмат МГУ,
первые 2 или 3 года ничего не делают, потому
что они все знают. В принципе, практически
все полезное, что дается математику в 
современной университетской программе,
содержится в вышеприведенном куррикулуме.
В университетской программе содержится
крайне много вещей неполезных, и их
приходится учить старшекурсникам;
так сложилось исторически.

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

Можно прочесть этот материал в виде цикла лекций,
но проще, наверное дать его первокурсникам в
привычной форме цикла задач, и реализовать обучение
по аналогии с матклассом.

Есть ситуация, когда иначе поступить просто нельзя.

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

Для такой ситуации и написана эта книга.

Независимый Московский Университет ежегодно сталкивается
с этой проблемой - большая часть студентов матшкольники.
Обыкновенно лекции читаются, исходя из того, что базовые
понятия и большая часть матшкольной программы 
студентам хорошо известны; это
приводит к отсеву нематшкольной части студентов. При этом
и матшкольники (как показывает опыт) по большей части 
не знают базовых понятий, и отсеиваются немного погодя.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Как читать эту книгу}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Основное содержание этой книги - два цикла
листочков с задачами, приведенные во второй
части книги.

Программа матшколы состоит из двух циклов,
практически независимых - геометрия, топология 
и анализ используют свойства вещественных чисел и
понятия предела и открытого множества, алгебра 
и теория чисел занимается свойствами групп, 
колец и полей. Эти две группы листочков
(``геометрию'' и "алгебру") можно решать 
независимо. Для листочков по "геометрии"
необходимо знакомство с понятиями
поля, кольца и группы; для листочков
по "алгебре" - свойства вещественных
и комплексных чисел. 

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

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

Формально говоря,
для понимания листочков достаточно школьной
программы и знания основных определений
теории множеств (вложение, наложение,
ограничение отображения, классы эквивалентности).
Многие школьные учебники (например, учебник
Колмогорова) уже содержат все нужные
определения. Этот материал излагается
в главе \ref???.

Для решения некоторых задач со звездочкой
(особенно в конце курса геометрии) и хорошего 
понимания остального материала, необходимо
немного подробнее ознакомиться с теорией множеств,
в частности, научиться пользоваться 
леммой Цорна. Об этом см. главу \ref???.

Остальные главы этой книги читать
не обязательно. С другой стороны, пытаться
решать задачи подряд и в изоляции от преподавателей
и студентов тоже не очень полезно - всегда есть
риск застопориться на какой-то тривиальной 
вещи и застрять надолго. В нормальной учебной
обстановке, такая проблема решается просто:
надо спросить другого студента или преподавателя.
Если их нет, надо походить, подумать, почитать
книжку, попробовать изучить контекст непонятной
вещи, подумать о том, как исторически возникли
такие штуки в математике. Проще всего выяснить
это (если знать английский), сделав поиск
на нужные ключевые слова в Интернете.
Но на случай, если Интернет не работает,
или если это слишком трудно, или просто
чтоб отдохнула голова - можно посмотреть
главы из первой части книги, 
сопутствующие этому листочку. Они адресованы
студенту, которому задач недостаточно, но
читать их можно и независимо. В принципе,
каждая такая глава является записью
лекции, прочитанной студентам, которым
выдан листок.

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Важное замечание}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


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

Никакого вреда в этом нет: чтение книги
должно быть занятием творческим; в идеале -
совместным творчеством автора и читателя.
Для этого некоторые авторы специально добавляют
в свои книги опечатки, чтобы студентам было
о чем задуматься. 

Вторая проблема, тоже весьма неприятная - люди
любят читать книги подряд. При этом дойдя до места,
где непонятно, люди читают это место снова и снова,
до полного отупения. Это неправильно! Надо открыть
книжку на другом месте и читать там, а непонятное
место перечитать потом.

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

\chapter{Основания математики}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{О математической строгости}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

"Точные науки" отличаются от "социо-гуманитарных"
тем, что в точных науках утверждение можно проверить
воспроизводимым экспериментом либо наблюдением.
Роль воспроизводимого наблюдения в математике 
играет {\em доказательство}.

Идея доказательства восходит к древним грекам,
и дошла до наших дней практически без изменений.
Математическая теория строится {\bf аксиоматически}.
В основе лежат несколько постулатов - аксиом, принятых 
как нечто абсолютно верное; все же остальное выводится 
из аксиом посредством формальной логики. 

При таком подходе, доказательству подлежат зачастую 
вещи, интуитивно очевидные. Именно это и называется 
{\em математической строгостью}.

На протяжении истории, стандарты математической
строгости менялись довольно часто. Отказ от строгости
в пользу {\em интуиции}, {\em мышления по аналогии} и 
{\em эвристических
аргументов} - дело не всегда вредное.
Многие современные математики считают, что 
принятые в конце XX века стандарты математической
строгости (восходящие к Гильберту и к французской группе 
Бурбаки) излишни. Немало об отрицательном
влиянии Гильберта и Бурбаки говорил 
В. И. Арнольд.

Отчасти он прав - большинство эвристических
аргументов можно довести до математически
строгих доказательств посредством рутинной
(и не всегда полезной) работы. Эту точку зрения
лучше всего высказали сами Бурбаки ("Теория Множеств"). 

\begin{quote}
{\it ...Математик, желающий убедиться в полной правильности,
или, как говорят, ``строгости", доказательства или теории,
отнюдь не прибегает к одной из тех полных формализаций,
которыми мы сейчас располагаем, и даже большей частью
не пользуется частичными и неполными формализациями,
доставляемыми алгебраическим и другими подобными
исчислениями. Обыкновенно он довольствуется тем, что
приводит изложение к такому состоянию, когда его опыт
и чутье математика  говорят ему, что перевод на
формализованный язык был бы теперь лишь упражнением в
терпении. Если возникают сомнения, то, в конечном счете
они относятся именно к возможности прийти без
двусмысленности к такой формализации  употреблялось ли
одно и то же слово в разных смыслах в зависимости от
контекста, нарушались ли правила синтаксиса
бессознательным употреблением способов рассуждения, не
разрешаемых явно этими правилами, была ли, наконец,
совершена фактическая ошибка. Текст редактируется, все
больше и больше приближаясь к формализованному тексту,
пока, по мнению специалистов, дальнейшее продолжение этой
работы не станет излишним.}
\end{quote}


Излишняя увлеченность формальными методами, 
возможно, действительно вредна, но
в обучении студентов без математической строгости не
обойтись. Профессиональный математик способен легко
определить, когда эвристический аргумент можно
{\ем формализовать}, то есть довести до любой требуемой степени
математической строгости; но эту способность можно
приобрести, только упражняясь в получении 
формально строгих доказательств.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{О формальном методе}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Формальный метод восходит к Гильберту,
который надеялся, что с его помощью удастся обосновать
математику. Его надежды не оправдались, благодаря теоремам
Геделя о неполноте. Но и сейчас формальный метод остается простейшим
(и лучше всего развитым) методом построения оснований
математики.

ПОРТРЕТ ГИЛЬБЕРТА!!!


Формальная версия математики устроена так. 
Математическая теория описывает свойства
определенных объектов, с помощью аксиом
и правил вывода. Сущность этих объектов
с формальной точки зрения неинтересна -
по замечанию Гильберта, {\ем "следует добиться 
того, чтобы вместо точек, прямых и плоскостей с
равным успехом можно было говорить о столах, 
стульях и пивных кружках"}. Правила вывода
суть формальные операции над утверждениями;
верным (доказанным) называется такое 
утверждение, которое можно вывести из аксиом. 

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

Также нужно доказать, что любое утверждение
можно доказать либо опровергнуть, исходя из аксиом.
Это свойство теории называется {\бф полнота}. 
В противном случае формальное описание математических
объектов неадекватно их сущности, хотя это не так
просто видеть.

Дело в том, что математическим объектам можно 
приписать реальность безотносительно к аксиомам,
которые ими описываются. Скажем, аксиомы арифметики
описывают теорию чисел, науку о решении диофантовых
уравнений (уравнений в целых числах). 
Утверждение {\ем "уравнение $P(t_1, t_2, ... t_n)=0$ 
не имеет целочисленных решений $t_1, ... t_n$"} 
может выводиться из аксиом арифметики (аксиом
Пеано), а может и не выводиться. Во втором случае,
может случиться, что уравнение имеет решения.
Может случиться и так, что
из аксиом арифметики невозможно  вывести ни
наличия, ни отсутствия решений.

Когда в какой-то теории есть утверждение $Q$,
которое нельзя вывести из аксиом, и при этом 
нельзя вывести из аксиом его отрицание "не $Q$" - эта
система аксиом называется {\bf неполной}.

"Математической реальности" такая система
аксиом, очевидно, неадекватна. Действительно, предположим,
что исходя из аксиом Пеано, нельзя ни доказать,
ни опровергнуть утверждение $Q$ "уравнение $P(t_1, t_2, ... t_n)=0$ 
не имеет целочисленных решений $t_1, ... t_n$".
В этой ситуации уравнение $P(t_1, t_2, ... t_n)=0$ 
таки не имеет решений, ибо, если бы такое решение
было, мы бы могли его подставить в уравнение,
и получить теорему "$Q$ ложно".

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

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

Этого не случилось.

К концу 1920-х годов, формальная программа
Гильберта близилась к завершению. В 1930-м
году польский математик Альфред Тарский развил систему
аксиом для элементарной геометрии, более формальную
и строгую, чем у Гильберта, и доказал, что эта система
аксиом полна и непротиворечива.

Но в самом начале 1930-х, совершенно неожиданно,
Курт Гедель доказал две теоремы о неполноте,
которые не оставили камня на камне от программы
Гильберта. 

Гедель доказал, что ни одна достаточно
богатая формальная теория не может быть полна; также
он доказал, что доказательство ее непротиворечивости
получить {\em невозможно.}

 ПОРТРЕТ ГЕДЕЛЯ!!!

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Теория множеств и ее аксиоматизация}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


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

"Наивная теория множеств" имеет дело с 
{\em множествами} - любыми совокупностями
объектов, которые называются "элементами множества". 
Утверждение "$x$ является элементом $X$" записывается
$x\in X$. Отрицание его записывается
$x\notin X$.

Можно говорить о "множестве всех последовательностей",
"множестве всех букв алфавита", "множестве
всех слов", и проделывать над такими множествами
естественные операции (пересечения, объединения
и т. п.). {\bf Подмножеством} множества
$X$ называется любое множество $X'$ такое,
что все элементы $X'$ являются элементами
$X$. Отношение "$X'$ является подмножеством $X$"
записывается $X'\subset X$. 

"Пустое множество" (обозначается $\emptyset$) 
не имеет элементов вовсе. 

Кантор не добивался абсолютной строгости
в теории множеств. Первая попытка построить
теорию множеств строго и аксиоматически
принадлежала Готтлобу Фреге, который 
предполагал, что получится логически вывести всю математику
из самоочевидных постулатов теории множеств (этот подход
к основаниям математики называется "логицизмом"). 
Построенную Фреге теорию называют "наивной теорией 
множеств". Она неверна (содержит противоречия).

Самое простое из противоречий наивной
теории множеств было обнаружено
Бертраном Расселом в 1901 году. 
Рассмотрим множество $A$ всех множеств
$X$ таких, что $X$ не является элементом $X$.
Будет ли $A$ принадлежать $A$? 
Если $A$ не принадлежит $A$, то $A$ должно
быть своим элементом. То есть формальным следствием
$A\notin A$ является $A\in A$. 

Этот парадокс - форма хорошо известного
"парадокса цирюльника". В одном селе живет цирюльник X.,
который бреет всех жителей, кроме тех, которые бреют себя сами.
Бреет ли цирюльник X. сам себя? 

Со времен Рассела получено множество парадоксов
наивной теории множеств. Они все сводятся, грубо говоря,
к тому, что строится "слишком большое" множество,
которое и приводит к парадоксам.

Рассел и Уайтхед построили версию теории множеств, свободную
от известных парадоксов, но она оказалась неудобна.
Более удобная версия
аксиоматической теории множеств была разработана
Э. Цермело в 1908. В 1922 А. Френкель
дополнил эту систему аксиом; современная версия
аксиоматической теории множеств называется
{\ем система аксиом Цермело-Френкеля} (ZF).
Отличие этой версии теории множеств от
наивной было в том, что "излишне больших"
множеств Цермело-Френкель не допускали.
Их теория оперировала не "всеми" множествами,
а только теми, чье существование можно
доказать (вывести из аксиом). Такие множества
конструируются из других множеств посредством
набора четко определенных операций. И парадоксальные
объекты, такие, как "множество всех множеств",
в системе аксиом Цермело-Френкеля просто
{\em не существуют}.

Довольно долго
(вплоть до Геделя) математики надеялись, 
что теория множеств Цермело-Френкеля полна и непротиворечива.
Сейчас ясно, что она неполна, и, возможно,
противоречива (во всяком случае, непротиворечивость
этой системы аксиом доказать невозможно, и это факт). 
Тем не менее, в большинстве версий "оснований математики"
математика базируется на теории множеств.

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

Бурбаки комментируют возможность противоречий в основаниях
математики таким образом ("Теория множеств"). 

\begin{quote}
{\it За 40 лет с тех пор, как сформулировали с достаточной
точностью аксиомы Теории множеств и стали извлекать из них
следствия в самых разнообразных областях математики, еще
ни разу не встретилось противоречие, и можно с основанием
надеяться, что оно и не появится никогда.

Если бы дело и сложилось иначе, то, конечно, замеченное
противоречие было бы внутренне присуще самим принципам,
положенным в основание Теории множеств, а потому нужно
было бы видоизменить эти принципы, стараясь по возможности
не ставить под угрозу те части математики, которыми более
других дорожат. И ясно, достичь этого тем более легко, что
применение аксиоматического метода и формализованного
языка позволит формулировать эти принципы более четко и
отделять от них следствия более определенно. Впрочем,
приблизительно это и произошло недавно, когда устранили
парадоксы Теории множеств принятием формализованного
языка. Подобную ревизию следует предпринять и в случае,
когда этот язык окажется в свою очередь противоречивым.}
\end{quote}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Терминология и библиография}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

По английски, теория множеств называется 
set theory, Цер\-ме\-ло-\-Френ\-кель - Zermelo-Fraenkel.
В английской версии Википедии основания
математики изложены весьма подробно, особенно
экзотические и альтернативные версии.
Популярное изложение формального метода и
его истории есть в "Теории множеств" Бурбаки.
Прекрасный учебник теории множеств -
"Теория множеств" Куратовского и Мостовского.
Биография Гильберта - "Гильберт",
Констанс Рид. 

Натурфилософские аспекты
теорем Геделя подробно обсуждаются
в книгах Р. Пенроуза "Новый разум 
императора" ("The Emperor's New Mind") 
и "Тени разума" ("The Shadows 
of the Mind").

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

\chapter[Основные понятия теории 
множеств]{Основные понятия \\теории множеств}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Обозначения теории множеств}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Г. Кантор определял множество так:
"Множество есть многое, мыслимое нами как единое".
Говоря чуть более строго, "Множество это
единое имя для совокупности всех объектов, 
обладающих данным свойством" (тоже Кантор).

В наивной теории множеств,
множество есть "любая совокупность объектов, называемых
элементами множества". Во избежание противоречий,
которыми славится наивная теория множеств, это
определение придется несколько изменить, отбросив
"излишне большие" классы множеств - об этом см. ниже.
Множества {\bf равны}, если они составлены из одинаковых элементов.

ПОРТРЕТ КАНТОРА!!!

Множество $S$ следует понимать как своего рода черный ящик -
для каждого объекта $x$, этот черный ящик умеет отвечать
на вопрос - "принадлежит ли $x$ множеству $S$"? 
Больше ничего $S$ делать не умеет. Два множества
{\бф равны}, или же {\бф совпадают},
если они отвечают на этот вопрос одинаково.

Если $x$ принадлежит $S$, это обозначается $x\in S$,
или $S\ni x$, если не принадлежит, это обозначается $x\notin S$.
Это обозначение (как и большинство других обозначений
для логических операторов: $\exists$, $\cap$,
$\cup$ и так далее) придумал Джузеппе Пеано в конце XIX
века. В этих обозначениях, равенство множеств можно записать
так:
\[
S_1 = S_2 \Leftrightarrow 
\left (\forall x \ \ | \ \ x\in S_1 \Leftrightarrow x\in S_2 \right)
\]
"Множества $S_1$ и $S_2$ равны тогда и только тогда, когда для
любого $x$, $x\in S_1$ равносильно $x\in S_2$".
Значок $\forall$ обозначает "для каждого",
а $\Leftrightarrow$ - эквивалентность 
утверждений ("тогда и только тогда",
"равносильно"). 

{\бф Подмножеством} множества $S$ называется 
множество $S_1$, целиком содержащееся в $S$.
Это обозначается $S_1\subset S$ (обозначение введено
Эрнстом Шредером в 1890). В логических обозначениях,
можно записать
\[
S_1 = S \Leftrightarrow 
\left (\forall x \ \ | \ \ x\in S_1 \Rightarrow x\in S \right)
\]
В этой формуле
стрелка $\Rightarrow$ обозначает импликацию ("следовательно").
Иногда это же самое записывают $S\supset S_1$.
Если $S_2\subset S_1$ и $S_1\subset S_2$, множества
$S_1$ и $S_2$ равны. 

Подмножество $S_1\subset S$, не совпадающее с $S$,
называется {\бф собственным подмножеством}.
Это обозначается $S_1\subsetneq S$.

Пустое множество обозначают $\emptyset$;
это обозначение впервые появилось у Бурбаки, и 
принадлежит Андре Вейлю.

Множество всех подмножеств $S$ обозначается $2^S$.



\задача
Пусть $S$ - конечное множество из $s$ элементов.
Докажите, что $2^S$ - конечное множество из $2^s$
элементов
\ез


Если $S_1$ и $S_2$ - два множества, можно говорить
об их {\бф объединении} $S_1\cup S_2$ (множестве всех элементов,
принадлежащих $S_1$ или $S_2$) и {\бф пересечении}
$S_1\cap S_2$
(множестве всех элементов,
принадлежащих $S_1$ и $S_2$).
Формально объединение определяется так:
\begin{equation}\label{_cup_formally_def_Equation_}
S_1\cup S_2= \{ x \ \  | \ \ (x\in S_1) \vee (x\in S_2)
\end{equation}
В этой формуле $\{ x \ \  | \ \  P(x) \}$
обозначает "множество всех $x$, удовлетворяющих $P(x)$
(это обозначение принадлежит Кантору). 
Символы $\vee$ и $\wedge$ означают "или" и "и"
(использовать $\vee$ для обозначения дизъюнкции
первым стал Б. Рассел; вместо "и" Рассел 
использовал точку).


\задача
Запишите $S_1\cap S_2$ формулой, аналогичной 
\eqref{_cup_formally_def_Equation_}.
\ез

Если заданы множества $S_1$ и $S_2$, можно определить 
{\бф произведение} $S_1\times S_2$ - множество всех
пар $(x, y)$, где $x\in S_1$, $y\in S_2$.

\hfill

{\бф Дополнение} множества $A$ до подмножества $B\subset A$ -
множество всех $a\in A$, которые не лежат в $B$.
Дополнение обозначается $AQ\backslash B$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Соответствия и отображения}
\label{_Sootve_Otobra_Subsection_}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Пусть $S_1$, $S_2$ - множество. {\бф Соответствием},
называется любое подмножество $P\subset S_1 \times S_2$.
Если пара $(x, y)$ принадлежит $P$, говорят 
"соответствие $P$ выполнено для пары $(x,y)$".
Это обозначается $P(x,y)$.

Соответствие обыкновенно задается 
какой-либо формулой: например, если 
$S_1$ и $S_2$ это множества вещественных чисел,
формулы $x< y$, $x> y$, $x\neq y$ 
задают соответствия. 

{\бф Отображением}, или {\бф функцией}
$f:\; S_1 \arrow S_2$ называется такое 
соответствие $\Gamma_f\subset S_1 \times S_2$, 
что для каждого $x\in S_1$ существует единственный
элемент $y\in S_2$ такой, что $(x, y) \in \Gamma_f$.
Множество $\Gamma_f$ в этой ситуации называется
{\бф графиком функции}. {\бф Значением} функции
$f$ на элементе $x\in S_1$ называется
тот единственный $y\in S_2$, для
которого $(x, y) \in \Gamma_f$.
Это обозначается так: $y = f(x)$.

Функцию часто задают формулами: если 
$S_1$ и $S_2$ это множества вещественных чисел,
то формулы $x\arrow x^2$, $x\arrow |x|$,
$x\arrow x+2$ задают отображения.

Следует думать про функции как про набор
правил, ставящих в соответствие каждому 
$x\in S_1$ некоторый элемент $S_2$.

Отображение из множества в себя называется
{\бф преобразованием} множества. {\бф Тождественное
преобразование} множества $S$ переводит
каждый $x\in S$ в себя. Его график называется
{\бф диагональю}. Тождественное преобразование
$S$ обозначается $\Id_S:\; S \arrow S$.

Если $f:\; S_1 \arrow S_2$, $g:\; S_2 \arrow S_3$
две функции, можно определить их {\бф композицию}
$f\circ g$, ставящую в соответствие $x \in S_1$
$g(f(x))\in S_3$. 

\задача
Пусть $f:\; S_1 \arrow S_2$, $g:\; S_2 \arrow S_3$,
$х:\; S_3 \arrow S_4$ - три функции. Докажите,
что композиция удовлетворяет {\бф свойству ассоциативности}
\[ f\circ (g\circ h) = (f\circ g)\circ h
\]
\ез

\замечание
Иногда значок $\circ$ обозначает
композицию отображений, примененную в другом порядке:
не $g(f(x))$, а $g(f(x))$.
\еза

Если $f(x)=y$, $y$ называется {\бф образом}
$x$, а $x$ - {\бф прообразом} $y$. 

{\бф Образом $S_1$} (обозначается $f(S_1)$)
при отображении $f:\; S_1 \arrow S_2$ 
называется множество всех $y\in S_2$,
которые являются образами каких-то $x\in S_1$.

{\bf Прообраз} подмножества $R_2\subset S_2$ -
множество всех элементов $x\in S_1$, переходящих
в элементы $R_2$; {\бф образ подмножества} $R_1\subset S_1$ -
совокупность всех элементов, полученных как образы
элементов $R_1$. Образ подмножества обозначается
$f(R_1)$, прообраз - $f^{-1}(R_2)$.

{\бф Ограничением} функции $f:\; S_1 \arrow S_2$ 
на подмножество $R_1\subset S_1$ называется
функция $f\restrict {R_1}:\; R \arrow S_2$, которая
на каждом $x\in R_1$ принимает значение
$f(x)$.

Функция $f:\; S_1 \arrow S_2$ 
называется {\бф вложением}, или {\бф инъекцией}.
или {\бф инъективным отображением}, если для 
разных $x, x' \in S_1$, их образы
не равны: $f(x) \neq f(x')$.

Функция $f:\; S_1 \arrow S_2$ 
называется {\бф наложением}, или {\бф сюръекцией}.
или {\бф сюръективным отображением}, если $f(S_1)= S_2$;
иначе говоря, каждый $y\in S_2$ является
образом какого-то элемента $S_1$.

{\бф сечение} наложения 
$\phi\; X\arrow Y$ это отображение
$\psi\; Y\arrow X$, удовлетворяющее $\phi\circ \psi =
\Id_X$. Иначе говоря, $\psi$ ставит каждому элементу
$Y$ в соответствие некий элемент из прообраза $\phi^{-1}(y)$.

ИЛЛЮСТРАЦИЮ - СЕЧЕНИЕ !!!

Если функция $f:\; S_1 \arrow S_2$ - одновременно
наложение и вложение, она называется
{\бф биекцией}, или {\бф биективным отображением},
или {\бф взаимно однозначным отображением},
или {\бф обратимой}.

\задача 
Пусть $f:\; S_1 \arrow S_2$ - биекция.
Докажите, что существует отображение
$g:\; S_2 \arrow S_1$ такое, что композиция
$f\circ g$ - тождественное преобразование $S_1$,
а $g\circ f$ - тождественное преобразование $S_2$.
\ез


Определение функций через подмножества произведения
принято в версии оснований математики, которая
базируется на теории множеств. В других версиях
оснований математики основным является понятие
функции, заданной формулой либо каким-то алгоритмом,
а множества определяются в терминах
функций. Даже в аксиоматической теории множеств
приведенное выше определение функции используется
наряду с формально-логическим "функция, заданная
формулой на языке Цермело-Френкеля" (высказывательная 
функция). Получить из "высказывательной функции"
функцию в смысле вышеприведенного определения
можно, воспользовавшись одной из аксиом 
("схемой подстановки").


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

\определение
Пусть на множестве $S$ задано соотношение $\sim$,
удовлетворяющее следующим условиям.

\begin{description}
\item[Рефлексивность] Для любого $x\in S$, $x\sim x$.
\item[Симметричность] Для любого $x, y\in S$, 
\[ 
 (x\sim y) \Leftrightarrow (y\sim x)
\]
\item[Транзитивность] Для любых $x, y, z\in S$, 
\[ 
 (x\sim y) \text{\ \ и \ \ } (y\sim z)\Rightarrow (x\sim z).
\]
\end{description}

Такое соотношение называется {\бф отношением
эквивалентности}.
\ео 

\задача
Придумайте примеры соотношений, которые
\итем являются рефлексивными и симметричными, но не
транзитивными
\итем являются рефлексивными и транзитивными, но не
симметричными
\итем являются транзитивными и симметричными,
но не рефлексивными
\ез

\определение
Пусть $X, \sim$ - множество, снабженное отношением
эквивалентности. {\бф Классом эквивалентности}
элемента $x\in X$ называется множество всех $y\in X$
таких, что $x\in y$. {\бф Представителем класса} $S$
называется любой элемент $x\in X$, который лежит в этом классе.
\ео

\задача
Докажите, что в такой ситуации $X$ разбито в объединение
непересекающихся классов эквивалентности
\ез

В силу этой задачи, на $X$ задано сюрьективное
отображение $\pi:\; X \arrow Y$ в множество $Y$ классов эквивалентности,
которое переводит элемент в его класс эквивалентности.
Легко видеть, что любое сюрьективное отображение
$\pi:\; X \arrow Y$ получается таким образом.




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

Наивная теория множеств приводит к парадоксам.
Источником этих парадоксов принято считать
несуществование "слишком больших множеств".
Аксиоматическая теория множеств имеет дело не
со "всеми" множествами, а только с теми, чье
существование может быть получено из аксиом.

Аксиоматическая  теория множеств требует продвинутого
логического аппарата. Большинство математиков
не помнят этих аксиом и ими не пользуются.
Вместо этого используется принцип "применением
естественных операций над множествами  получается множество".
Под "естественными операциями" понимаются
операции, описанные выше:
взятие пересечения, объединения, произведения,
подмножества и множества всех подмножеств. 

В канонической форме, система аксиом Цермело-Френкеля
(ZFC) состоит из 9 аксиом.

\begin{description}
\item[1. Аксиома объемности (экстенсиональности).]
Два множества $A$ и $B$ равны тогда и 
только тогда, когда они имеют одни и те же элементы:
\[
(\forall x (x\in A \Leftrightarrow x\in B)) \Rightarrow A=B
\]

\item[2. Аксиома пары.] Для любых множеств $А$ и $B$ существует
множество $C$ такое, что $A$ и $B$ являются его единственными
элементами. Множество $C$ обозначается $\{A,B\}$ и называется
{\bf неупорядоченной парой} $A$ и $B$. Если $A=B$, то $C$ состоит из
одного элемента.

\item[3. Аксиома подмножества.] 
Пусть $\phi(p)$ - свойство, которым может обладать
множество $p$. Для каждого множества $X$ существует
подмножество $X_\phi\subset X$, составленное из всех
$x\in S$, удовлетворяющих свойству $\phi$.

\item[4. Аксиома объединения.] 
 Для любых множеств $A$ и $B$ существует объединение $A\cup B$:
\[ 
A\cup B:= \{ x \ \  | \ \  (x\in A)\vee (x\in B) \}
\]

\end{description}

\замечание
Отметим, что пересечение $A\cap B$ существует в силу
Аксиомы Подмножества.
\еза


\begin{description}
\item[5. Аксиома степени.] 
Для любого множества $S$ существует множество его подмножеств
$2^S$.

\end{description}

\замечание \label{_indukti_mno_Zamechanie_}
Конечные множества в аксиоматической теории
множеств строятся следующим образом. 
Множество из нуля элементов - $\emptyset$.
Множество из одного элемента - это $\{\emptyset\}$,
множество из двух элементов - это
\[
\{ \{\emptyset\}, \emptyset\},
\]
множество из трех элементов -
\[
\{ \{ \{\emptyset\},\emptyset\}, \{\emptyset\}, \emptyset\},
\]
и так далее. На каждом шаге, к множеству $S$ добавляется
новый элемент, полученный из одного из элементов
$x\in S$ как $x\cup \{x\}$. Аналогичным образом
можно построить и бесконечное множество.
Множество $S$ называется {\бф индуктивным},
если оно содержит $\emptyset$, и для любого
элемента $x\in S$, $S$ содержит $x\cup \{x\}$.
\еза
\begin{description}
\item[6. Аксиома бесконечного множества.]
\  \\ Существует индуктивное множество.
\end{description}

\замечание
Из этой аксиомы следует существование пустого множества,
а также существование конечных множеств из $i$ элементов,
описанных в Замечании \ref{_indukti_mno_Zamechanie_}.
\еза

\определение
Пусть на языке Цермело-Френкеля задано свойство $\Phi(x, y)$, которым
может обладать пара множеств $x, y$. Предположим,
что для каждого $x$ есть не больше одного $y$ такого,
что $\Phi(x,y)$ выполняется. В такой ситуации,
$\Phi$ задает "функцию" из класса множеств $x$, 
для которых $y$ существует,
переводящую $x$ в этот (единственным
образом определенный) $y$.
Такая "функция" называется {\бф высказывательной
функцией}, а множества, где она определена -
ее {\бф областью определения}. 

Отметим, что "высказывательные функции"
не являются функциями в обычном смысле этого слова
(см. раздел \ref{_Sootve_Otobra_Subsection_}).

Область определения
 высказывательной функции - не обязательно множество.
Скажем, область определения тождественной
высказывательной функции
\[
\Phi(x,y) \Leftrightarrow (x=y)
\]
это все множества, но совокупность всех множеств
не образует множества (см. \ref???).
\ео

\begin{description}
\item[7. Схема подстановки для высказывательной функции $\Phi$.]
Пусть $\Phi(x,y)$ - высказывательная функция, а $X$ -
множество, все элементы которого лежат в области
определения $\Phi$. Тогда существует множество
$Y$, составленное из всех $y$, для которых
верно $\Phi(x,y)$, с каким-то $x\in X$.
\end{description}

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

\begin{description}
\item[8. Аксиома регулярности.]
Любое непустое множество $S$ содержит элемент $x\in S$
такой, что $x\cap S=\emptyset$.

\item[9. Аксиома выбора.]
Пусть $\phi:\; X \arrow Y$ сюрьективное отображение
множеств. Тогда у $\phi $ есть {\бф сечение}
$\psi\; Y\arrow X$, то есть отображение
$\psi\; Y\arrow X$, удовлетворяющее $\phi\circ \psi =
\Id_X$. Иначе говоря, $\psi$ ставит каждому элементу
$Y$ в соответствие некий элемент из прообраза $\phi^{-1}(y)$.
\end{description}

Аксиома выбора влечет ряд парадоксальных следствий.
Например, из нее следует, что единичный шар в $\R^3$
можно разбить на 4 конгруэнтные (одинаковые) 
части $S_1$, $S_2$, $S_3$, $S_4$, а затем сложить
из них два шара такого же размера
(парадокс Банаха-Тарского). Аксиома выбора
независима от остальных аксиом Цермело-Френкеля:
ее нельзя ни доказать, ни опровергнуть
в этой системе аксиом (это доказал Пол Коэн,
используя {\бф метод форсинга}).
Если система Цермело-Френкеля
непротиворечива, то она непротиворечива
в предположении, что аксиома выбора верна,
как и в предположении, что аксиома выбора неверна
(это доказал Гедель).
Большинство альтернативных версий оснований математики
(конструктивизм, интуиционизмя, ультрафинитизм) не
признает аксиому выбора и ее следствий. В большинстве
разделов математики без аксиомы выбора можно обойтись,
используя вместа аксиомы выбора какую-то ослабленную 
версию (см. \ref???), не влекущую парадоксов.
Поэтому многие ученые стараются избежать
аксиомы выбора и ее следствий, или, по крайней мере,
отмечают все случаи ее употребления. 

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

Аксиомы Цермело-Френкеля приводятся 
в этой главе для ознакомления.
Для большинства разделов математики наивной теории множеств
вполне достаточно, хотя необходимо помнить и избегать
возможности парадоксов. К счастью, для того, чтобы избежать
известных парадоксов, вполне достаточно ограничения множеств
по мощности (см. \ref???). 



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Терминология и библиография}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


По-английски, отображение называется map, mapping, function,
образ и прообраз - image, preimage.
Соотношение - relation, соотношение эквивалентности -
equivalence relation. Биекция, инъекция и сюрьекция - bijection,
injection, surjection (эти слова изобретены группой Бурбаки).
Произведение множеств - Cartesian product (в честь Декарта,
имя которого которого в латинских текстах писали Cartesius).
Аксиома выбора называется Axiom of choice (сокращается до AC). 
Система Цермело-Френкеля (ZFC) подробно освещается
в англоязычной Википедии. Большая коллекция
ссылок на страницы, посвященные аксиоме выбора, лежит тут\\
http://www.math.vanderbilt.edu/$\tilde\ $schectex/ccc/choice.html\\

Книга И. В. Ященко "Парадоксы теории множеств" -\\
http://www.mccme.ru/mmmf-lectures/books/books/books.php?book=20


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

\chapter{Кардиналы и теорема Кантора}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Теорема Кантора-Бернштейна-Шредера}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Два множества $A$ и $B$ называются {\бф равномощными},
если между $A$ и $B$ существует взаимно-однозначное
соответствие. {\бф Счетное множество} есть множество,
равномощное множеству натуральных чисел.

Если множество $A$ равномощно подмножеству $B$,
говорится, что {\бф мощность $A$ не больше мощности $B$}.

\hfill

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{\бф Теорема Кантора-Бернштейна-Шредера.}
Пусть $A$, $B$ такие множества, что $A$ равномощно
подмножеству $B$, а $B$ равномощно подмножеству $A$.
Тогда $A$ и $B$ равномощны.

\hfill

{\bf Доказательство:} 
Пусть $f:\; A \hookrightarrow B$ вложение
из $A$ в $B$, а $g :\; B \hookrightarrow A$
вложение из $B$ в $A$. Рассмотрим 
отображение $f\circ g:\; A \arrow A$
и $g\circ f:\; B \arrow B$. Обозначим
за $A_0$ дополнение $A\backslash g(B)$.
Определим индуктивно $A_i$
по формуле
$A_{i+1}= f\circ g(A_0)$.
Определим $A_\infty$ как пересечение
образов отображений $(f\circ g)^i$ для всех $i$
(за $(f\circ g)^i$ обозначается композиция $f\circ g$ с
собой $i$ раз). Легко видеть, что $A$ разбивается
в объединение непересекающихся подмножеств,
$A= A_0 \cap A_1 \cap ... \cap A_\infty$.

Применим аналогичную процедуру к $B$, получив
разбиение $B$ в объединение непересекающихся подмножеств,
$B= B_0 \cap B_1 \cap ... \cap B_\infty$.

Легко видеть, что $f$ задает биекцию из $A_\infty$ в
$B_\infty$. Также $f$ задает биективное отображение
из $A_0 \cap A_2 \cap A_4 \cap ...$ в $B_1 \cap B_3 \cap B_5 \cap ...$,
а $g$ задает биективное отображение из $B_0 \cap B_2 \cap B_4 \cap ...$ 
в $A_1 \cap A_3 \cap A_5 \cap ...$ (см. иллюстрацию). 


ИЛЛЮСТРАЦИЯ !!!


Мы разбили $A$ и $B$ на непересекающиеся 
подмножества, которые попарно биективны.
\endproof

\замечание
В математике, значком \endproof \ \ или похожим
значком обозначается конец доказательства.
Этот знак называется "халмош" или "tombstone".
Его изобрел Пол Халмош, известный американский математик.
\еза

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Мощность множества}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\определение
Пусть на множестве $S$ задано соотношение $\succeq$.
Это соотношение называется {\бф отношением 
частичного порядка}, если выполнены следующие
аксиомы
\begin{description}
\item[(i)] (Рефлексивность) Для любого $a$, имеет место
$a\succeq a$
\item[(ii)] (Транзитивность) $a \succeq b$ и $b\succeq c$ влечет
$a \succeq c$
\item[(iii)] (Асимметричность) Если $a\succeq b$ и $b
\succeq a$, то $a=b$.
\end{description}
Если, в дополнение к тому, для любых двух $a, b$ имеет место
$a\succeq b$ либо $b
\succeq a$, то $\succeq$ называется {\бф отношением
полного порядка}.
\ео

В качестве примера "отношения частичного порядка" 
рассмотрим соотношение "быть подмножеством" на множестве
всех подмножеств $X$. Ясно, что $A_1\subset A_2$ -
соотношение частичного порядка. Отношение
полного порядка имеется на множестве
вещественных чисел ("меньше": $a\leq b$).

\hfill

\определение
Два множества называются {\бф равномощными},
если между ними есть биективная эквивалентность.
Если множество $A$ допускает вложение в $B$,
говорится, что {\бф мощность $A$ меньше или равна
мощности $B$}. 
\ео

Легко видеть, что равномощность - это отношение
эквивалентности. {\бф Кардинал}, или
{\бф кардинальное число} множества $A$ это
его мощность. На языке наивной теории множеств,
отношение равномощности разбивает все множества
на классы эквивалентности, пронумерованные 
{\бф кардиналами}. Иначе говоря, кардинал
$X$ - это класс эквивалентности множеств, 
равномощных $X$.

С точки зрения аксиоматической теории
множеств, "класс эквивалентности множеств, 
равномощных $X$" множеством не является,
и говорить про него нельзя. Тем не менее,
"множество кардиналов меньших данного"
определить можно. Это делается так.
Возьмем множество $X$. Рассмотрим
множество $2^X$ всех подмножеств $X$.
Равномощность задает на $2^X$
соотношение эквивалентности.
Множество классов эквивалентности
называется {\бф множеством кардиналов
меньших или равных $X$}. В дальнейшем
мы будем называть это множество 
"множеством кардиналов", предполагая,
что $X$ - чрезвычайно большое множество,
мощность которого может быть при необходимости
увеличена настолько, насколько нужно.

\задача Выведите
из теоремы Кантора-Бернштейна-Шредера,
что "мощность $A$ меньше или равна
мощности $B$" задает на множестве
кардиналов отношение частичного порядка.
\ез

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

Используя аксиому выбора, легко доказать,
что множество кардиналов на самом деле
{\бф упорядочено}: для любых
множеств $X$ и $Y$, либо
$X$ вкладывается в $Y$, либо $Y$
вкладывается в $X$ (см. \ref???). 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Счетные множества}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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


\задача
Докажите, что следующие множества счетны
\итем Множество $\Z$ целых чисел
\итем Множество $\Q$ рациональных чисел
\итем Множество $\Z[t]$ полиномов с целыми коэффициентами.
\ез

Естественные операции с конечными множествами
(взятие произведения, взятие объединения
непересекающихся множеств и так далее)
как правило увеличивают мощность множества.
С бесконечными (например, счетными) множествами
все совершенно иначе - естественные операции
не меняют их мощности.


\задача
Пусть $X$ - счетное множество
Докажите, что $X\times X$ счетное. 
\ез

\задача
Пусть $X$, $Y$ - непересекающиеся счетные
множества. Докажите, что $X\cup Y$ счетно.
\ез

Из аксиомы выбора легко вывести, 
что любое бесконечное множество содержит
счетное множество (см. \ref???). 
Из таких множеств можно выкинуть
конечное подмножество, не меняя мощности.

\задача
Пусть $X$ - бесконечное множество, которое
содержит счетное подмножество.
Рассмотрим конечное подмножество $Z\subset X$.
Докажите, что дополнение $X\backslash Z$
равномощно $X$. 
\ез



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Диагональный метод Кантора}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Из известных нам операций над множествами,
операция "взятия множества подмножеств" $X\arrow 2^X$ стоит
особняком: как доказал Кантор, она всегда
увеличивает мощность множества.

\hfill

{\бф Теорема Кантора:}
Пусть $X$ непустое множество.
Тогда $X$ и $2^X$ неравномощны.

\hfill

{\бф Доказательство:}
Пусть $\phi:\; X \arrow 2^X$ биекция.
Рассмотрим множество $S$ всех $x\in X$, которые
не содержатся в $\phi(x)$. Пусть $\phi(x_0)=S$.
Зададимся вопросом - лежит ли $x_0$ в $S$?
Если не лежит, то по определению $S$,
$x_0 \notin \phi(x_0)$ влечет $x_0\in S$ -
противоречие. Точно также, если 
$x_0$ лежит в $S$, имеем $x_0 \in \phi(x_0)$,
что влечет $x_0\notin S$. Следовательно,
биекция $\phi:\; X \arrow 2^X$ невозможна.
\endproof

\hfill

Континуум (обозначается $\aleph_0$)
это кардинальное число $2^\N$,
где $\N$ это множество натуральных чисел.
Множество, равномощное континууму, называется
{\бф континуальным}. 

Согласно теореме Кантора, мощность
континуума строго больше мощности $\N$.
Доказательство теоремы Кантора для
случая $X=\N$ можно наглядно изложить
следующим образом. 

Пусть $S\subset \N$ некоторое подможество.
Рассмотрим последовательность $\{x_i\}$, $i=0,1,2, ...$,
где $x_i$ равен $1$ если $i\in S$ и 0 если
$i\notin S$. Это позволяет записывать
элементы $2^\N$ как последовательности
нулей и единиц. Ясно, что полученное
соответствие между элементами $2^\N$
и последовательностями взаимно однозначно.

Предположим, что задано взаимно однозначное
соответствие между $\N$ и $2^\N$. Это значит,
что есть последовательность последовательностей,
в которой найдется любая последовательность:
\[
\begin{array}{ccccc}
\lambda^0_0 & \lambda_1^0 & \lambda_2^0 & \lambda_3^0 & ...\\
\lambda^1_0 &\lambda_1^1 & \lambda_2^1 & \lambda_3^1 & ...\\
\lambda^2_0 &\lambda_1^2 & \lambda_2^2 & \lambda_3^2 & ...\\
\lambda^3_0 &\lambda_1^3 & \lambda_2^3 & \lambda_3^3 & ...
\end{array}
\]
Диагональ этой диаграммы -
это последовательность $\{\lambda^i_i\}$.

Рассмотрим последовательность $a_0, a_1, a_2, ...$
полученную таким образом: если $\lambda^i_i$ равно 1,
то $a_i$ равно 0, в противном случае $a_i=1$.
Такая последовательность отличается
от каждой из $\{\lambda^i_*\}$ в $i$-м члене, 
а значит не совпадает ни с одной из последовательностей
$\{\lambda^i_*\}$. Поэтому отображение
$\N \arrow 2^\N$, относящее $i$ 
последовательность $\{\lambda^i_*\}$,
не может быть сюрьективно.

Этот аргумент 
называется "диагональным методом Кантора";
он изобретен Кантором в 1891-м году. Несчетность
вещественных чисел Кантор доказал впервые 
в 1873-м, но совершенно другим способом.

Один из парадоксов наивной теории множеств 
немедленно следует из теоремы Кантора. Действительно,
множество всех множеств тождественно множеству
всех своих подможеств, а значит равномощно ему.
На языке аксиоматической теории множеств
этот парадокс превращается в теорему -
"множества всех множеств не существует".

Вещественное число от 0 до 1 можно
записать в двоичной системе счисления,
получив последовательность из нулей и единиц.
Некоторые последовательности соответствуют 
одним и тем же числам; например,
0.0011111111... и 0.01000000...

\задача
Докажите, что следующие множества равномощны континууму
\итем Множество $\R$ вещественных чисел
\итем Множество последовательностей из чисел 0,1,2,3
\итем Множество последовательностей целых чисел
\итем Множество функций $\phi:\; \Q \arrow \Q$
\ез

\указание
Воспользуйтесь теоремой Кантора-Бернштейна-Шредера.
\еу

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Континуум-гипотеза}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Последние годы жизни Кантор провел, пытаясь доказать
{\ем гипотезу континуума}, которая утверждает, что
любое подмножество $\R$ либо континуально, либо счетно.
Обобщенная континуум-гипотеза утверждает, что
для любого бесконечного множество $X$,
любое множество $Z$ мощности меньше $2^X$ и больше $X$
равномощно $X$ или $2^X$.

В 1940-м году Гедель доказал, что гипотезу континуума
(и обобщенную гипотезу континуума) 
невозможно опровергнуть, пользуясь аксиомами
Цермело-Френкеля; иначе говоря, гипотеза континуума
может быть опровергнута только в том случае,
если эта система аксиом сама по себе противоречива.
Аргумент Геделя весьма прост - Гедель
определил "конструктивный универсум",
набор множеств, полученных из пустого множества
естественными теоретико-множественными операциями,
и доказал, что в конструктивном универсуме
выполняются аксиомы Цермело-Френкеля. 
Мощность множества, полученного конструктивно, 
довольно легко вычислить явно, и проверить,
что кардиналов, промежуточных между $X$ и $2^X$
не бывает.

В 1963-м году Пол Коэн доказал, что гипотезу
континуума (и обобщенную гипотезу континуума) 
невозможно вывести из этих аксиом,
то есть она {\ем недоказуема}.

КОЭН - ПОРТРЕТ !!!!

Есть математики, считающие, что теория множеств
описывает "реально существующие объекты"; другие
математики считают, что теория множеств состоит
из формальных манипуляций, не имеющих основания
в "реальном мире". Эти два взгляда часто называют
"платоновским" и "формальным". Платон в книге 
"Государство" уподобил людей узникам, а 
материальный мир теням на стенах темного
узилища-пещеры. Светом, с точки зрения
Платона, является мудрость, доступная
лишь избранным. Материальный мир - 
несовершенный отпечаток истинного мира
символов, идей и знания.

Для формалиста вопрос о "верности континуум-гипотезы"
после результатов Геделя и Коэна не имеет смысла; 
для реалиста этот вопрос все еще осмысленный.

Гедель был сторонником платоновской точки зрения
на математику; он считал, что континуум-гипотеза
неверна, и невозможность опровергнуть ее иллюстрирует
несовершенство системы аксиом Цермело-Френкеля.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Замечания}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Теорема Кантора-Бернштейна-Шредера была
получена Кантором с помощью аксиомы выбора
и трансфинитной индукции. Доказательство,
приведенное выше, принадлежит Эрнсту 
Шредеру, одному из основателей математической
логики и изобретателю исчисления предикатов, 
и  Феликсу Бернштейну, ученику Кантора.
Поэтому эту теорему также называют теорема
Шредера-Бернштейна. Иногда ее называют
теорема Кантора-Бернштейна (доказательство
Шредера содержало ошибку, исправленную
Бернштейном в его диссертации). 


Счетные множества по-английски называются
countable, или denumerable, соотношения 
частичного порядка - partial order relations.

Чтобы избежать парадоксов наивной теории
множеств, нужно оперировать с множествами
"мощности не больше заданной", то есть
с множествами, которые допускают вложение
в заданное (очень большое) множество.
Это множество часто называется 
{\бф универсумом}. В 1920-х 
Джон фон Нойман (John von Neumann) 
сформулировал систему аксиом теории множеств,
основанную на понятии классов ("очень
больших множеств") и множеств 
("множеств небольшой мощности,
которыми можно оперировать в соответствии
с наивным представлением о множествах").
Эта система аксиом была упрощена и улучшена 
Паулем Бернайсом (Paul Bernays) в конце 1930-х,
и Геделем в 1940-м. Она эквивалентна 
системе аксиом Цермело-Френкеля.

Для большинства
разделов современной математики
основанием является не теория множеств,
а теория категорий (см \ref???).
Строгое построение теории 
категорий обыкновенно осуществляется 
на основе аксиоматики фон 
Ноймана-Бернайса-Геделя
(NBG).

Аксиоматика NBG и описание ее применений
хорошо излагаются в англоязычной Википедии;
там же можно прочитать биографию
фон Ноймана с подробным очерком его 
работ по логике. 

Великолепный учебник (а по совместительству
и задачник) наивной теории множеств - первая часть книги
Н. К. Верещагина и А. Шеня "Лекции по математической 
логике и теории алгоритмов," доступная на сайте 
Независимого Университета: \\
http://www.mccme.ru/free-books/

Доказательство Коэна недоказуемости континуум-гипотезы
можно найти в книжке "Теория множеств и
континуум-гипотеза", П. Дж. Коэн.




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

\chapter[Группы, кольца, поля (Алгебра 1)]%
{Группы, кольца, поля \\(Алгебра 1)}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Алгебраические структуры. Группы.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Пусть $A$ - произвольное множество.
{\бф  $n$-арная операция} на $A$ - это отображение
$\underbrace{A\times A \times ... A}_{n\text{\ \ раз}}\arrow A$.
1-арные операции называются унарными, 2-арные - бинарными,
3-арные - тернарными. Под 0-арными операциями мы будем
понимать отображение из одноэлементного множества в $A$.
Другими словами, 0-арная операция на $A$ - это задание
элемента $A$.

Наука, изучающая алгебраические операции на множествах,
называется {\ем абстрактной алгеброй}. 

{\бф Алгебраическая структура} - это набор алгебраических
операций, удовлетворяющих набору аксиом.

\hfill

{\bf Пример:}
{\ем Структура полугруппы} на множестве $G$ - это
бинарная операция "умножения" $G\times G\arrow G$,
$x, y \arrow xy$, удовлетворяющая {\бф условию ассоциативности}
$(xy)z = x(yz)$.


\hfill


{\бф Структура группы на множестве $G$}
задается следующими операциями:

\begin{itemize}
\item Бинарная операция "умножения" $G\times G\arrow G$,
$x, y \arrow xy$
\item Унарная операция "взятия обратного элемента",
$x\arrow x^{-1}$
\item Задание "единицы группы" $e$ - это 0-арная операция.
\end{itemize}

Эти операции удовлетворяют следующим аксиомам
(для любых $x, y, z\in G$

\begin{description}
\item[Ассоциативность:] $(xy)z = x(yz)$ 
\item[Существование единицы:] $ex=xe=x$
\item[Существование обратного элемента:]
$xx^{-1}=x^{-1}x=e$.
\end{description}

Это определение кажется произвольным,
но оно имеет глубокий математический смысл.
Дело в том, что композиция отображений обладает
свойством ассоциативности. Пусть $G_S$ это множество
биективных (взаимно однозначных) 
отображений из $S$ в себя. Умножение
элементов из $G_S$ - это композиция, взятие обратного 
элемента - взятие обратного отображения,
единица - тождественное отображение из $S$ в себя.
Нетрудно проверить (проверьте), что $G_S$ с этими
операциями является группой. Эта группа называется
{\бф группа подстановок из $S$ в себя},
или же {\бф группой биективных отображений},
или еще {\бф группой перестановок}. 
Если $S$ - конечное множество из $n$ элементов,
$G_S$ называется {\бф симметрической группой},
и обозначается $S_n$. 

Пусть $G$ - любая группа. Множество $G'\subset G$
называется {\бф подгруппой}, если оно содержит единицу $e$
и для любых $x, y\in G'$, $xy$ и $x^{-1}$ принадлежат $G'$.
В этом случае также говорится, что $G'$ 
{\бф сохраняется групповыми операциями}
взятия произведения и взятия обратного.

Понятно, что подгруппа $G'\subset G$ тоже является
группой. 

Отображение $\phi:\; G_1 \arrow G_2$ групп называется {\бф гомоморфизмом},
если оно переводит единицу $G_1$ в единицу $G_2$,
удовлетворяет $\phi(x^{-1}) = \phi(x)^{-1}$,
$\phi(xy) = \phi(x)\phi(y)$, для любых $x,y\in G_1$.
В этом случае также говорится, что $\phi$
{\бф сохраняет групповые операции}
взятия произведения и взятия обратного.
{\бф Изоморфизм групп} - это биективный гомоморфизм.

Из определения ясно, что отображение $G' \arrow G$ из подгруппы
в группу является гомоморфизмом.

Если задан гомоморфизм $G_0 \stackrel \phi \arrow G_S$ из группы
$G_0$ в группу перестановок $S$, говорится,
что $G_0$ {\бф действует на $S$}. Это значит,
что для любого элемента $x\in G_0$ задана 
перестановка $\phi(x):\; S\arrow S$, причем
для любых $x, y\in G_0$, композиция
перестановок $\phi(x)\circ\phi(y)$
 равна перестановке $\phi(xy)$.
Следует думать о группе $G_0$ как о 
группе преобразований из $S$ в себя, а об 
элементах $x\in G_0$ - как о преобразованиях.

В большинстве случаев в математике группы 
возникают как группы
преобразований какого-нибудь пространства.
Например, группа движений плоскости, группа
подстановок множества, или группа
преобразований пространства, переводящих прямые
в прямые (такие преобразования называются
{\ем аффинными}). 

Пусть $A$ - любая группа, $x\in A$ любой элемент. 
Рассмотрим подстановку $a \arrow ax$, $a\in A$
Это задает отображение из $A$ в множество $S_A$
подстановок из $A$ в себя. Нетрудно видеть, что
это отображение - инъективный гомоморфизм. 

Мы получили следующую теорему.

\hfill

{\bf Теорема Кэли:} Любая группа изоморфна
подгруппе группы подстановок. 

\endproof

\hfill

В принципе,
эту теорему можно считать определением группы.
Исторически, группы появились как подгруппы группы
подстановок. Определение группы в терминах алгебраических
операций принадлежит Артуру Кэли (1854).

\задача
Пусть $A$ - любая группа. Докажите, что следующие
отображения задают гомоморфизм $A \arrow G_A$
\итем $x\in A$ переводится в подстановку $a\arrow x^{-1} a$.
\итем $x\in A$ переводится в подстановку $a\arrow x^{-1} ax$

Всегда ли такие гомоморфизмы инъективны?
\ез

\hfill

Произведение $G_1\times G_2$ групп $G_1$, $G_2$
наделено групповой структурой: произведение в $G_1\times
G_2$ задается как $(g_1, g_2) (g_1', g_2') = (g_1g_1', g_2, g_2')$,
обратный элемент - как $(g_1, g_2)^{-1} = (g_1^{-1}, g_2^{-1})$,
и единица - как $(e_1, e_2)$. Проверьте, что это группа.

\hfill

Если $H\subset G$ подгруппа, можно определить 
{\бф правые классы смежности} $G$ по $H$ как классы эквивалентности
по такому  соотношению эквивалентности: $g\sim g'$, если
$hg=h'g'$, для каких-то $h, h'\in H$. Проверьте, что
это соотношение эквивалентности. Аналогичным образом
определяются {\бф левые классы смежности}:
 $g\sim g'$, если $gh=g'h'$.

Это определение принадлежит Галуа.


\hfill

Два элемента группы $x, y\in G$ называются
{\бф коммутирующими}, если $xy=yx$. 

\hfill

Элемент $x\in G$, умноженный на себя $n$ раз,
обозначается $x^n$; это обозначение читается
"$n$-я степень $x$". Так же определяются 
отрицательные степени: $x^{-n}= (x^{-1})^n$.

\hfill


Среди групп особенно важны {\бф абелевы}, они же
{\бф коммутативные} группы. Это группы, в которых
выполняется {\бф закон коммутативности} $xy=yx$.

Групповой закон в абелевых группах обыкновенно записывается
значком плюса $+$, единичный элемент - нулем $0$, а обратный
элемент - минусом $-$. 

Группа целых чисел $\Z$ с операцией сложения, очевидно,
абелева. Другой пример абелевой группы - группа $\Z/n \Z$
остатков по модулю $n$, с операцией сложения. 
Группа $\Z$ наряду с группой $\Z/n \Z$
"порождена одним элементом": все элементы
$\Z$ и $\Z/n \Z$ получаются как степени
образующей. Поэтому $\Z$ и $\Z/n \Z$
называются {\бф циклическими группами}.

\определение
Группа $G$, содержащая элемент $t$, называется
{\бф циклической}, если любой элемент $G$ равен $t^m$,
для какого-то $m\in \Z$.
\ео

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Конечные группы порядка 6}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

Классификация конечных абелевых групп излагается в листке
\ref???. Оказывается, что любая конечная группа
изоморфна произведению нескольких групп вида $\Z/n\Z$.

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

\hfill

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\теорема
 Пусть $W$ - группа порядка 6 (из 6
элементов). Тогда $W$ изоморфна $\Z/6\Z$, либо
группе $S_3$ подстановок множества из трех элементов.

\хфилл

{\бф Доказательство.}\\
По определению,
{\бф порядок элемента $t$ группы $G$} - это порядок 
подгруппы $\langle t \rangle$, состоящей из всех степеней
$t^i$, $i \in \Z$. 
Такая подгруппа называется {\бф подгруппой,
порожденной $t$}. \footnote{Вообще же
{\бф подгруппа, порожденная элементами $t_1, ... t_n\in G$}
это наименьшая подгруппа $G$, содержащая $t_1, ... t_n$.}

Теорема Лагранжа утверждает, что
порядок элемента $t\in G$ делит порядок $G$
(порядок группы обозначается $|G|$).
Действительно, частное $\frac{|G|}{|\langle t \rangle|}$
равно числу смежных классов $G$ над $\langle t \rangle$.
Поэтому порядок любого элемента $W$ является делителем 6.

Можно доказать, что любая группа $G$ четного порядка содержит
элемент порядка 2. Разобьем $G$ на классы 
вида $\{ t, t^{-1}\}$. В каждом из таких классов
есть один элемент (если $t$ порядка 2 или равен 1)
или два (если $t$ порядка больше 2). Если
элементов порядка 2 нет, в каждом из таких
классов, кроме $\{e\}$, есть по два элемента,
а этого не может быть, потому что порядок
$G$ четный. Из этого рассуждения также
следует, что число элементов
порядка 2 в $G$ нечетно.

Если $W$ абелева, то это $\Z/6\Z$.
Это легко видеть из следующего. Если в $W$ есть два
неравных коммутирующих 
элемента $t_1$, $t_2$ порядка 2, они порождают подгруппу
$\langle t_1, t_2\rangle=\{e, t_1, t_2, t_1t_2\}$ порядка 4. 
Поскольку $|G|$ делит $|\langle t_1, t_2\rangle|$,
такого быть не может. Поэтому в $W$ есть элемент $w$ порядка
3 и элемент $v$ порядка 2. Поскольку они коммутируют,
их произведение $t:=uv$ имеет порядок 6 (проверьте!), 
и $W= \{e, t, t^2, t^3, t^4, t^5\}$ изоморфно
$\Z/6\Z$ (изоморфизм переводит $t$ в образующую $\Z/6\Z$).

Предположим теперь, что $W$ неабелева.
Нам осталось доказать, что в этом случае
$W$ изоморфно $S_3$.
Чтобы построить изоморфизм из $W$ в $S_3$,
надо определить действие $W$ на множестве
$S$ из трех элементов, таким образом, чтобы 
каждый неединичный элемент $w\in W$ действовал
на $S$ нетривиально.

Если в $W$ есть элемент порядка 6, то 
$W$ изоморфна $\Z/6\Z$, как показано выше.
Поэтому порядок любого элемента $W$ равен 2 или 3.
Пусть $u\in W$ - элемент второго порядка.
Если он коммутирует со всеми элементами $W$,
то в $W$ найдется элемент $t$ порядка 3 (иначе мы
бы имели подгруппу четвертого порядка
$\langle u, t\rangle=\{e, u, t, ut\}$ в $W$, что
невозможно). Тогда $ut$ имеет порядок 6, 
и $W$ абелева. Следовательно, в $W$ есть
элемент порядка 2, не коммутирующий со 
всеми элементами $W$.

Множество элементов $g\in G$, коммутирующих
со всеми элементами $G$, называется {\бф центром $G$}.
Легко видеть, это это подгруппа. На этом языке,
вышеприведенное заключение переговаривается так.

Пусть $W$ - неабелева группа порядка 6. Тогда в $W$ есть
элемент $u$ порядка 2, не лежащий в центре $W$.
Кроме того, порядок любого элемента $W$ равен 2 или 3.

Пусть $u$, $v\in W$ - два элемента порядка 2.
Их произведение $uv$ удовлетворяет 
\[
(uv)^{-1} = v^{-1} u^{-1} =vu
\]
Поскольку $u$ и $v$ не могут коммутировать
(иначе мы получим подгруппу порядка 4), 
из этого следует, что $(uv)^{-1} \neq uv$,
и $uv$ имеет порядок (как минимум) 3. Поэтому в $W$
есть элементы порядка 3 (возьмем любой
$v\neq u$; либо он порядка 3, и тогда 
все доказано, либо порядка 2, и тогда
$uv$ порядка 3). 

Пусть $S\subset W$ - множество всех элементов $W$
порядка 2. Число таких элементов нечетно, как мы
уже видели. Поскольку $u$ не лежит в центре $W$,
$uv\neq vu$, то есть $u \neq v^{-1} u v$.
Но элемент $v^{-1} u v$ тоже порядка 2.
Значит в $S$, как минимум, 3 элемента.
В $S$ также не может быть 5 элементов,
потому что в $W$ есть элементы порядка 3.
Поэтому в $S$ есть в точности 3 элемента.

Для каждого $v\in W$ рассмотрим подстановку
$s_v:\; S \arrow S$, переводящую $u\in S$ в $v^{-1} u v$.
Легко видеть, что это отображение задает гомоморфизм
из $W$ в $S_3$. Как мы уже видели,
элемент $u$ порядка 2 коммутируют только с единицей и 
$u$. Поэтому подстановка $s_v$ нетривиальна
для любого $v$. Мы получили инъективный
гомоморфизм из $W$ в группу $S_3$.
Поскольку обе эти группы имеют по 6 элементов,
это изоморфизм. \endproof

\хфилл

Можно доказать эту теорему, явно
написав таблицу умножения в группе из 6 элементов.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Алгебраические структуры. Кольца, поля.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

Наряду с группой, весьма важно понятие {\бф кольца}.
Структура кольца на множестве $R$ задается бинарными
операциями {\бф сложения} (обозначается $+$)
и {\бф умножения} (обозначается $x, y \arrow xy$),
и унарной операцией {\бф взятия противоположного} (обозначается 
$x \arrow -x$),  и выделенным элементом $0$. Все эти операции удовлетворяют
следующим аксиомам, верным для любых $x, y , z\in R$. 

\begin{description}

\item[Групповой закон сложения:] Рассмотрим
кольцо $R$ с бинарной операцией $+$, унарной
операцией $-$  и выделенным элементом $0$.
Множество $R$ с этими алгебраическими 
операциями образует абелеву группу.
Это свойство часто формулируют так: 
{\бф кольцо образует абелеву группу по сложению}.
Структура группы по сложению на $R$
называется {\бф аддитивной групповой
структурой} (addition - сложение).

\item[Ассоциативность умножения:] $(xy)z = x(yz)$ 

\item[Существование единицы:] 
Задан выделенный элемент $1$ такой, что $1x=x1=x$

\item[Дистрибутивность:] $x(y+z)=xy+xz$

\item[Коммутативность умножения:] $xy=yx$.

\end{description}

В определении кольца, коммутативность умножения
и существование единицы не всегда предполагаются.
Структура, определенная выше, в таком 
случае будет не просто кольцо, а 
"коммутативное кольцо с единицей".

Операции умножения и сложения хорошо известны
из младших классов школы; также в младших классах
известно, что вышеприведенные законы выполняются 
на множестве целых чисел. Иначе говоря, целые
числа образуют кольцо. Также кольцо образуют
вещественные числа (бесконечные десятичные дроби)
и рациональные числа (дроби вида $\frac p q$, где
$p$ и $q$ целые, а $q$ ненулевое). Но в кольце
вещественных и рациональных чисел задана еще
одна алгебраическая операция - деление. 
"Кольцо с делением" называется {\бф поле}.
Оно определяется так.


Структура поля на множестве $R$ задается бинарными
операциями {\it сложения} (обозначается $+$)
и {\it умножения} (обозначается $x, y \arrow xy$),
унарными операциями {\it взятия противоположного} (обозначается 
$x \arrow -x$), и {\it взятия обратного} $x\arrow x^{-1}$
и выделенными элементами $1$ и $0$. Эти операции
должны удовлетворять аксиомам кольца,
а множество $R\backslash 0$ с операциями
умножения, взятия обратного и единицей 1
должно удовлетворять аксиомам группы.

Кратко (хоть и не совсем точно)
это формулируют так: "поле - это кольцо,
образующее группу по умножению".

Обратимый элемент кольца - это такой $x$,
что найдется $y$, удовлетворяющий $xy=1$.

\задача
Пусть $R$ кольцо, где все ненулевые элементы обратимы.
Докажите, что $R$ это поле.
\ез

В этой задаче мы допускаем обычную в алгебре 
вольность речи: структура поля задается дополнительной
операцией взятия обратного. Правильно было бы сказать 
"Докажите, что на $R$ найдется структура
поля, совместимая с операциями умножения и сложения".

\задача
Пусть $R$ кольцо, где все ненулевые элементы обратимы.
Докажите, что на $R$ существует единственная
структура поля, совместимая с с операциями умножения и
сложения.
\ез


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Алгебраические структуры. Гомоморфизмы.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Зафиксируем какую-нибудь алгебраическую структуру
$\goth S$ - скажем, группы, кольца или поля. 
Пусть $A$ и $B$ - множества, наделенные такой алгебраической
структурой (то есть группы, кольца, поля и т.п.).
Рассмотрим $n$-арные операции
\[ 
  \mu_n:\; \underbrace{A\times A \times ... A}_{n\text{\ \
  раз}}\arrow A\ \ \    \mu_n:\; \underbrace{B\times B \times ... B}_{n\text{\ \
  раз}}\arrow B
\]
задающие $\goth S$. Отображение
$\phi:\; A \arrow B$ {\бф сохраняет операцию $\mu_n$}
если оно перестановочно с $\mu_n$. Иначе говоря, 
$\phi$ сохраняет $\mu_n$, если
имеет место соотношение
\[
\phi(\mu_n(a_1, a_2, ... a_n)) = \mu_n(\phi(a_1), \phi(a_2), ...\phi(a_n))
\]

{\bf Морфизм} (или же {\бф гомоморфизм}) из 
$A$ в $B$ это отображение, {\ит сохраняющее
все алгебраические операции структуры $\goth S$}.

Гомоморфизм групп - отображение, сохраняющее
умножение, взятие обратного элемента и единицу.

Гомоморфизм колец - отображение, сохраняющее
умножение, сложение, вычитание, и переводящее
1 в 1 и 0 в 0.

Гомоморфизм можно определить для любой
алгебраической структуры. Также можно определить
следующие понятия.

{\бф Эпиморфизм} - сюръективный гомоморфизм.

{\бф Мономорфизм} - инъективный гомоморфизм.

{\бф Изоморфизм} - биективный гомоморфизм.

{\бф Эндоморфизм} - гомоморфизм из множества,
снабженного алгебраической структурой, в себя.

{\бф Автоморфизм} - биективный эндоморфизм.

\задача Пусть $A$, $B$ - группы. Рассмотрим
структуру полугруппы, заданную на $A$, $B$
операцией умножения, и пусть $\phi:\; A \arrow B$
гомоморфизм полугрупп. Докажите, что $\phi$
гомоморфизм групп.
\ез

\задача Пусть $A$, $B$ - поля. Рассмотрим
структуру кольца, заданную на $A$, $B$
операцией умножения, сложения и взятия противоположного
элемента, и пусть $\phi:\; A \arrow B$
гомоморфизм колец. Докажите, что $\phi$
гомоморфизм полей.
\ез

\задача
Пусть $\phi:\; A \arrow B$ - эпиморфизм полей.
Докажите, что $\phi$ - изоморфизм.
\ез

\задача
Пусть $\goth S$ произвольная алгебраическая
структура, а $A$ - множество, наделенное
$\goth S$. Докажите, что композиция эндоморфизмов
$A$ - эндоморфизм. Докажите, что автоморфизмы
$A$, с групповой операцией композиции,
 образуют группу.
\ез


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Комплексные числа}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Рассмотрим множество $A=\R^2$ пар вещественных чисел 
вида $(x,y)$. Определим сложение на таких парах почленно:
$(x, y) + (x', y')= (x+x', y+y')$. Мы хотим определить
умножение на $\R^2$ таким образом, чтобы выполнялись
аксиомы кольца. 

Предположим, что единичный элемент в $A$ задан парой
$(1,0)$. Из дистрибутивности следует, что
$(m,0)(x,y)= (mx, my)$, для любого целого $m$ 
(проверьте!). Поэтому естественно задать умножение
на элементы вида $(\lambda, 0)$, для 
любого вещественного $\lambda$, так же:
\[
(\lambda,0)(x,y)= (\lambda x, \lambda y)
\]
Запишем элементы $A$ в виде $a1 + b i$,
где $a, b \in \R$, $1= (1,0)$ и $i=(0,1)$.
Упрощая обозначения, мы можем обозначать
элементы $A$ как $a + b i$.

В силу дистрибутивности, имеем
\begin{equation}\label{_mult_hyperco_Equation_}
(a+bi) (a' + b'i) = aa' + (ab'+a'b) i + bb' i^2
\end{equation}
Поэтому в наших предположениях
умножение в $A$ целиком определяется значением
$i^2$.

Зафиксируем вещественные числа $\lambda, \mu$, и пусть
$i^2=\lambda+\mu i$, а умножение в $A$ задано формулой
\eqref{_mult_hyperco_Equation_}.

Аксиомы кольца в такой ситуации выполнены, и это
нетрудно проверить. Аддитивная структура на $A$
(структура сложения) задана с самого начала, и
довольно понятно, что $A$ образует группу по сложению
(как группа, $A$ изоморфно произведению $\R\times \R$). 
Коммутативность, дистрибутивность умножения и наличие единицы 
очевидны по построению. Чтобы проверить ассоциативность,
мы воспользуемся дистрибутивностью умножения.

Пусть $a_1, a_2, a_3$ - любые элементы $A$,
$a_k = x_k + y_k i$. В силу дистрибутивности, имеем
\begin{align*}
(а_1 а_2) а_3 = & x_1 x_2 x_3 + (x_1 x_2 y_3  +
x_1 y_2 x_3  + y_1 x_2 x_3)i \\ + &(y_1 x_2 y_3  +
y_1 x_2 y_3  + y_1 y_2 x_3)i^2 + y_1 y_2 y_3 i^3.
\end{align*}
Очевидно, $a_1 (a_2 a_3)$ равно тому же самому.

Для каждой пары вещественных чисел $\lambda, \mu$,
мы получили структуру кольца на $A$, определяемую
(как в формуле \eqref{_mult_hyperco_Equation_})
дистрибутивностью умножения и законом
$i^2=\lambda+\mu i$.

В последних листках по алгебре такие кольца
("конечномерные коммутативные алгебры над полем",
или же "артиновы кольца") обсуждаются довольно подробно.
Сейчас нас интересует исключительно случай $i^2=-1$, потому
что полученное таким образом кольцо - это поле
({\бф поле комплексных чисел}). Кольцо с таким 
законом умножения обозначается $\C$, а его
элементы называются {\бф комплексными числами}.
Элемент $i$ удобно обозначать $\1$.

Итак, мы имеем следующее.

1. Кольцо $\C= \R^2$ со сложением, заданным почленно,
и умножением, заданным законом 
\begin{equation}\label{_comple_Equation_}
(a+b\1) (a' + b'\1) = aa' + (ab'+a'b) \1 + bb' \1^2
\end{equation}
где $a+b \1$ записывает пару вида $(a, b) \in \R^2$

2. Соотношение $\1^2=-1$.

Рассмотрим отображение $z\arrow \bar z$,
переводящее элемент $a+b\1\in \C$ в 
$a-b\1$ (оно называется {\бф комплексным сопряжением}).
Комплексное сопряжение в композиции
с собой равно тождественному отображению
(такие отображения называются {\ит инволюциями}.

Легко видеть, что комплексное сопряжение -
автоморфизм кольца $A$, а неподвижные
точки комплексного сопряжения -
комплексные числа вида $a+ 0\1$
(такие комплексные числа называются 
{\бф вещественными}). 
{\бф Отображение нормы} переводит
$z\in \C$ в $z\bar z$; это отображение
мультипликативно (сохраняет умножение)
поскольку комплексное сопряжение
мультипликативно. 

Поскольку $z\bar z$ удовлетворяет
$\overline {z\bar z}= \bar z z = z\bar z$,
оно вещественное; явное вычисление дает
$z\bar z= x^2 + y ^2$ для $z= x+ y\1$.
Если $z\neq 0$, то $z\bar z$ --
ненулевое вещественное число;
следовательно, $z\bar z$ обратимо.

Всякий ненулевой элемент $z\in \C$ обратим:
\[ 
  z^{-1}= \bar z (z\bar z)^{-1}.
\]
Поэтому $\C$ - поле. Это поле называется
{\бф полем комплексных чисел}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Замечания, терминология, библиография}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Определение группы (как подгруппы группы подстановок,
замкнутой относительно групповых операций)
принадлежит итальянскому врачу и математику
Паоло Руффини (Paolo Ruffini, 1765 - 1822).
Руффини в 1799-м году опубликовал доказательство
неразрешимости уравнения 5-й степени в радикалах,
впоследствии переоткрытое Абелем. Руффини называл
свои группы permutazione. Термин группа (le groupe)
принадлежит Эваристу Галуа, немало сделавшему в 
теории групп (ему принадлежит открытие
классов смежности и  нормальных подгрупп). 
Абстрактное 
определение группы в терминах умножения
элементов принадлежит Артуру Кэли (Cayley).
Современное аксиоматическое определение
группы появилось в учебнике Хайнриха Вебера
в 1895-м году.


Теорию колец и полей
разработал Дедекинд; он же изобрел термин
"поле". Термин "кольцо" принадлежит Гильберту,
аксиоматическое определение кольца - Эмми Нетер
(Emmy Noether) и Вольфгангу Круллю (Wolfgang Krull).

Работы Нетер не были опубликованы по политическим
причинам, и ее идеи известны из книги Ван дер
Вардена "Современная алгебра". Эта книга до сих пор
остается великолепным учебником по теории колец и по алгебре 
вообще. Многие вещи понятно изложены в другом стандартном
учебнике - "Алгебре" Сержа Ленга. 

Одна из лучших книг по элементарной алгебре
(и вообще математике) - пятитомная 
"Энциклопедия элементарной математики",
под редакцией П. С. Александрова, А. И. Маркушевича, 
А. Я. Хинчина. Другая полезная школьнику книга -
И. Р. Шафаревич, "Основные понятия алгебры".
Великолепный учебник-задачник по теории групп
и полей, с началами теории Галуа - "Теорема
Абеля в задачах и решениях" В. Б. Алексеева,
составленная по материалам лекций В. И. Арнольда 
в физико-математической школе-интернате 18.

Обозначения $\N$, $\Z$, $\Q$, $\R$, $\C$
для натуральных, целых, рациональных, вещественных
и комплексных числах принадлежат Бурбаки.

По-аглийски, группа будет group, кольцо
ring, поле field, морфизм, гомоморфизм, мономорфизм,
эпиморфизм, изоморфизм, эндоморфизм автоморфизм - morphism, homomorphism,
monomorphism, epimorphism, isomorphism, endomorphism,
automorphism.

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

\chapter[Делимость в кольцах (Алгебра 2)]{Делимость в кольцах \\(Алгебра 2)}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Идеалы в кольцах}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


Пусть $\phi:\; R_1 \arrow R_2$ - эпиморфизм
(сюрьективный гомоморфизм) колец. По определению,
$\phi$ это гомоморфизм аддитивных групп $R_1$
в $R_2$, сохраняющий единицу и умножение.

Если задан гомоморфизм групп $\psi:\; G_1\arrow G_2$,
{\бф ядром $\psi$} называется множество всех элементов
$G_1$, переходящих в единицу $e_2\in G_2$. Легко
видеть, что ядро гомоморфизма групп - это
подгруппа (проверьте!).

{\бф Ядро гомоморфизма колец} $\phi:\; R_1 \arrow R_2$ -
это множество всех элементов $R_1$, которые
переходят в ноль под действием $\phi$.
Ядро $\phi$ никогда не содержит единицы,
а значит, не является подкольцом.

Ядро гомоморфизма колец является {\бф идеалом}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\определение
Пусть $R$ - кольцо, $I\subset R$ - подгруппа 
аддитивной группы $R$, не содержащая 1, и такая,
что для любого $x\in I$, $y\in R$,
$xy\in I$. Тогда $I$ называется 
{\бф идеалом кольца $R$}.
\ео

\задача
Пусть $\phi:\; R_1 \arrow R_2$ -
гомоморфизм колец. Проверьте, что его ядро является
идеалом $R_1$.
\ез

\определение
Элемент $x$ кольца $R$ называется
{\бф обратимым}, или {\бф единицей кольца},
если найдется $x'\in R$ такой, что $xx'=1$.
\ео

\замечание
Не надо путать "единицу" (обратимый элемент)
и единичный элемент 1.
\еза

Пусть $t\in R$ элемент кольца, который не обратим.
Ясно, что совокупность элементов вида $xt$, $x\in R$
образует идеал. Такой идеал называется {\бф главным}.
Не все идеалы - главные.

\задача
Рассмотрим кольцо $k[x,y]$ многочленов вида
$\sum_{i, j} a_{ij} x^i y^j$, где $a_{ij}$ - коэффициенты
из поля $k$ (такое кольцо называется {\бф кольцом
полиномов от двух переменных над $k$}. Докажите, что
многочлены с нулевым свободным членом 
\[ \left\{ \sum_{i, j} a_{i,j} x^i y^j \ \ | \ \ a_{0,0}=0\right\}
\]
образуют идеал. Докажите, что этот идеал - не главный.
\ез

Ядро гомоморфизма колец - это всегда идеал.
Обратное тоже верно: любой идеал можно получить
как ядро гомоморфизма колец. Пусть $I\subset R$ - идеал в 
кольце $R$. Рассмотрим множество $R/I$
классов эквивалентности элементов $R$ по модулю $I$:
\[
   x\sim y \Leftrightarrow x= y+n, \ \  n\in I.
\]
Можно думать про $R/I$ как про множество "остатков по
модулю $I$". Как и в случае с обычным кольцом остатков по 
модулю $n$, на $R/I$ задано умножение и сложение:
если $x\sim x'$, $y\sim y'$, то $x+y\sim y+y'$ и
$xy\sim yy'$. Нетрудно проверить, что определенные
таким образом операции задают на $R/I$ структуру
кольца (проверьте!). Это кольцо называется
{\бф факторкольцом по идеалу}. Естественное
отображение $R\arrow R/I$ является гомоморфизмом
колец (оно называется {\бф отображением проекции}).
Ядро этого гомоморфизма совпадает с $I$.


Таким образом можно получить структуру кольца
на множестве $\Z/n\Z$ остатков по модулю $n$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Основная теорема арифметики}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Пусть $a, b\in R$ элементы кольца $R$.
Мы говорим, что {\бф $a$ делит $b$},
если $b=ac$, для какого-то $c\in R$.
В этом случае также говорится, что
{\бф $b$ делится на $a$}.

Элементы $a, b\in R$, если для любого
$d\in R$, делящего $a$ и $b$, $d$ обратим.

Элемент $p\in R$ кольца называется
{\бф простым}, если для любого разложения
$p=nm$ на множители, $n$ либо $m$ - обратимы.
Хорошо известно, что любое целое число
$n\in \Z$ разлагается на простые множители 
в $\Z$, и это разложение единственно с точностью
до перестановки множителей. На самом деле
этот факт в высшей степени нетривиальный:
в большинстве колец разложение на простые
множители не единственно.

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

Первым шагом в этом направлении было доказательство
Эйлером неразрешимости уравнения $x^3=y^2+2$.
Ферма утверждал, что это уравнение не имеет 
целочисленных решений,
кроме $(x,y)=(3,\pm 5)$. Эйлер вывел это
из единственности разложения на простые множители
в кольце $\Z[\sqrt{-2}]$ чисел вида
$a+b\sqrt{-2}$, $a, b\in \Z$ (см. задача \ref???), 
которое он не доказывал. Вероятно, Эйлер считал
единственность разложения на простые множители
не требующей доказательства.

Эйлер пользовался следующим аргументом.
Запишем уравнение  $x^3=y^2+2$ так:
\[
x^3 = (y+ \sqrt{-2})(y-\sqrt{-2}).
\]
Если $y$ четен, то число $y^2+2$ четно и не делится
на 4. Но в этом случае оно не может быть третьей степенью
целого числа $x$. Поэтому $y$ нечетен.
 
В кольце $\Z[\sqrt{-2}]$ число $\sqrt{-2}$ просто
(проверьте!).

Числа $y+ \sqrt{-2}$ и $y-\sqrt{-2}$ взаимно просты.
Действительно, их сумма равна $-2\sqrt{-2}= (\sqrt{-2})^3$,
поэтому у них не может быть общих простых делителей, кроме
$\sqrt{-2}$. Но $\sqrt{-2}$ не может делить $y+ \sqrt{-2}$,
потому что $y$ нечетно. Произведение взаимно простых
чисел $y+ \sqrt{-2}$ и $y-\sqrt{-2}$ равно третьей степени;
из этого следует, что все простые сомножители $y+\sqrt{-2}$
 и $y-\sqrt{-2}$ 
входят туда в третьей степени. Поэтому имеем
$y+ \sqrt{-2}=\mu^3$, где $\mu=a+b\sqrt{-2}$ - 
какой-то элемент $\Z[\sqrt{-2}]$.

Имеем
\begin{equation}\label{_mu^3_Equation_}
\begin{aligned}
y+ \sqrt{-2}= &\mu^3=
(a+b\sqrt{-2})^3 = a^3+ 3\sqrt{-2}a^2 b - 6 ab^2 -2\sqrt{-2} b^3\\
=& a^3-6ab^2 + (3a^2 b-2b^3)\sqrt{-2}.
\end{aligned}
\end{equation}
Поэтому $3a^2 b-2b^3=1$. Поскольку $b$ делит $3a^2 b-2b^3$,
$b$ равно $\pm1$. Получаем $\pm(3a^2-2)=1$, из чего сразу
следует $b=1, a=\pm 1$. Снова применяя \eqref{_mu^3_Equation_},
получаем $y=\pm5$, $x=3$.

\hfill

Похожий аргумент Эйлер использовал для 
доказательства "последней теоремы Ферма":  несуществования ненулевых 
целочисленных решений уравнения $a^n+b^n=c^n$,
для $n=3$. Эйлер пользовался единственностью
разложения на простые множители в кольце $\Z[\xi]$,
где $\xi$ - комплексный корень 3-й степени из 1
(см. задачу \ref???).

На протяжении XIX века(и особенно во Франции) "теорема Ферма" 
была одним из главных вопросов теории чисел
Жозеф Лиувилль понял, что аргумент Эйлера
можно обобщить для любого простого $n$, если в кольце
чисел вида $\Z[\xi_n]$, где $\xi_n$ - 
 комплексный корень $n$-й степени из 1, 
разложение на простые множители единственно.
Габриель Ламэ воспользовался идеей Лиувилля,
и 1 марта 1847-м года на заседании французской
Академии объявил, что закончил 
доказательство теоремы Ферма для любого $n$.
После доклада Ламэ выступил Лиувилль, который
указал ему, что единственность разложения
на простые множители в кольце $\Z[\xi_n]$
нуждается в доказательстве, и он сомневается,
что она верна для любых $n$. 

Единственность разложения на простые множители,
как оказалось - утверждение весьма нетривиальное.
Она называется Основная Теорема Арифметики; для целых
чисел и для некоторых колец вида $\Z[\sqrt{-i}]$
ее можно доказать с помощью алгоритма Евклида
(см. раздел \ref???). Интересно, что Евклид
(в отличие от Эйлера, Коши, Ламэ и других
математиков XVIII и XIX века) понимал,
что этот факт нуждается в доказательстве.

В 1801-м году Гаусс опубликовал учебник
теории чисел "Disquisitiones Arithmeticae",
где воспроизвел классические результаты
теории чисел, в том числе и основную
теорему арифметики. Для доказательства
этого результата Гаусс воспользовался
аргументом Евклида, тем же самым, что 
и мы. Для Гаусса необходимость этого
доказательства была не просто данью традиции.
В 1831-м году Гаусс определил
"целые комплексные числа" вида $a+b\1$, 
$a, b\in \Z$ (сейчас их называют 
{\ем гауссовыми}) и доказал, посредством
алгоритма Евклида, что основная теорема
арифметики выполнена и в этом кольце.

В споре с Ламэ и Коши о единственности разложения
на простые множители в $\Z[\xi_n]$,
Лиувилль был целиком прав - разложение на простые множители
в кольце $\Z[\xi_n]$ не единственно, например, для $n=23$; это
было доказано Эрнстом Куммером еще в 1843-м году.
По сообщению Гензеля,
Куммер задолго до Ламэ понял, что доказательство
теоремы Ферма вытекает из единственности 
разложения на простые множители в $\Z[\xi_n]$;
но Дирихле указал ему, что единственность
разложения нуждается в доказательстве.

Обнаружив неоднозначность разложения на множители,
Куммер изобрел теорию идеалов. С помощью идеалов
ему удалось доказать теорему Ферма для некоторых 
$n$ таких, что в $\Z[\xi_n]$  единственности 
разложения на простые множители нет. 

Единственности
разложения на простые множители
нет, например, в кольце $\Z[\sqrt{-3}]$
чисел вида $a+b\sqrt{-3}$, $a, b\in \Z$.
Действительно, $z\bar z=|z|^2$ для $z\in \Z[\sqrt{-3}]$
всегда целое, и равно единице
только если $z$ обратимо в $\Z[\sqrt{-3}]$
(проверьте!). К тому же, $|z|^2$ делится на 4,
если он четен (проверьте!). Поскольку $|2|^2=4$, 
$2$ просто в $\Z[\sqrt{-3}]$. По той же самой
причине, $1+ \sqrt{-3}$ и $1-\sqrt{-3}$
тоже просты. Следовательно, у числа 4 есть
два разных разложения на простые множители:
\[
4=2^2 = (1+ \sqrt{-3})(1-\sqrt{-3}).
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Деление с остатком в кольце}
\label{_Euclidean_Section_}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Предположим, что в кольце $R$ задана функция
$\nu:\; R \arrow \Z^{\geq 0}$, бьющая 
в неотрицательные целые числа и принимающая
значение 0 только в нуле. Предположим также,
что для любых ненулевых $x, x'\in R$, $\nu(x)\geq \nu(x')$,
имеет место "деление с остатком $x$ на $x'$", то
есть существует $a$ такое, что
\[
\nu(x-ax') < \nu(x').
\]
В этом случае, $x-ax'$ называется "остатком от деления
$x$ на $x'$". Кольцо, где задано деление с остатком,
называется {\бф евклидовым}.

Примером такого кольца является $\Z$, где в качестве
функции $\nu$ можно взять $z\arrow |z|$, а в качестве
"деления с остатком" - обычное деление с остатком.

Предположим, что $R$ это кольцо, где задано деление с
остатком.

"Шаг Алгоритма Евклида" это функция 
\[
 \Psi:\; (R\backslash 0)\times (R\backslash 0)\arrow
 R\times R.
\]
Он берет пару ненулевых чисел $v, w\in R$,
$\nu(v) \geq \nu(w)$, и делит
$v$ на $w$ с остатком, получая остаток
$y$. На выходе шага алгоритма Евклида - 
пара $w, y$.

"Алгоритм Евклида" получает пару ненулевых
чисел $v_0, w_0\in R$, $\nu(v) \geq \nu(w)$,
и применяет к ним шаг алгоритма Евклида, получая пару 
$(v_1, w_1)=(w_0, y)$, как описано выше. Если $y=0$
(то есть  $v_0$ делится нацело на $w_0$),
алгоритм Евклида заканчивает работу. 
Если же $v_0$ не делится нацело на $w_0$,
алгоритм Евклида применяет шаг алгоритма Евклида
к $(v_1, w_1)=(w_0, y)$ и так далее.
Если алгоритм Евклида заканчивается парой $(v_n, w_n)=(w, 0)$,
$w$ объявляется его {\бф результатом}.

Возьмем какую-то пару $a, b\in R$, и применим
к ней алгоритм Евклида.
Поскольку на каждом шаге алгоритма Евклида $\nu(w_i)$ 
уменьшается, он рано или поздно остановится.
С другой стороны, на каждом шаге алгоритма элементы
$(v_i, w_i)$ получаются как линейные комбинации
$a$ и $b$:
\[
v_i = a\lambda+ b\mu, \ \ 
 w_i = a\lambda'+ b\mu', \ \ \ \lambda, \lambda', \mu, \mu' \in R.
\]
Поэтому на выходе алгоритма Евклида мы имеем
линейную комбинацию $d=a\lambda+ b\mu$. Это число 
делит $v_n$ и $w_n$. Поэтому оно делит
$w_{n-1}=v_n$, $v_{n-1}=w_n + k v_n$.
Воспользовавшись индукцией, мы получаем,
что $d$ делит $v_0$ и $w_0$.

Мы получили такое утверждение.

\хфилл

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\утверждение
 Предположим, что $R$ - кольцо,
где задано деление с остатком.
Тогда для любых ненулевых $a, b\in \R $
найдется их линейная комбинация  $d=a\lambda+ b\mu$,
$\lambda, \mu \in R$, которая делит $a$ и $b$. 

\endproof

\хфилл

Из этого утверждения следует, что $d$ это
"наибольший общий делитель" (НОД) $a$ и $b$.
По определению, {\бф наибольший общий делитель} $a$ и $b$
это такое $c$, которое делит $a$ и $b$,
причем любой другой делитель $a$ и $b$ делит
$c$. Ясно, что любой делитель $a$ и $b$
делит и их линейную комбинацию $d=a\lambda+ b\mu$,
поэтому $d$ это НОД.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Кольца главных идеалов}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Пусть $R$ кольцо, $a_1, ... a_n\in R$ - его элементы.
Обозначим за $a_1R+ a_2 R + ... a_n R\subset R$ множество,
состоящее из всех линейных комбинаций вида
$\sum a_i \lambda_i$, где $\lambda_i$ - произвольные
элементы $R$. Предположим, что $I:=a_1R+ a_2 R + ... a_n R$
не содержит единицы $R$. Ясно, что в таком случае $I$
это идеал в $R$. Такой идеал называется 
{\бф идеалом, порожденным элементами $a_1, ... a_n$,}
а элементы $a_i$ - генераторами или порождающими элементами.

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

\определение
Кольцо $R$ называется {\бф кольцом главных идеалов},
если любой идеал $a_1R+ a_2 R + ... a_n R$, порожденный
конечным множеством $a_1, ... a_n\in R$,
является главным.
\ео

Пусть в кольце $R$ есть НОД $d$ двух элементов $x$ и $y$
и он является их линейной комбинацией. Тогда
$d$ принадлежит идеалу $xR+yR$, порожденному
$x$ и $y$. Более того, любой элемент $xR+yR$
делится на $d$, поскольку $d$ - делитель $x$ и $y$.
Поэтому идеал $xR+yR$ состоит из элементов,
делящихся на $d$. Мы получили, что
этот идеал главный. Воспользовавшись
индукцией по числу образующих, это
рассуждение легко обобщить на идеалы
$a_1R+ a_2 R + ... a_n R$ с любым числом
генераторов.

\задача
Пусть в кольце $R$ есть НОД любых двух элементов,
и он является их линейной комбинацией.
Докажите, что $R$ - кольцо главных идеалов.
\ез

Из рассуждений раздела \ref{_Euclidean_Section_}
ясно, что любое евклидово кольцо является кольцом
главных идеалов.

\определение
{\bf Делители нуля} в кольце $R$ это такие ненулевые элементы
$x$, $y$, что $xy=0$. 
\ео


\определение
Идеал $I\subset R$ в кольце называется {\бф простым},
если выполнено любое из следующих условий
\begin{description}

\item[(i)] Для любых $x, y\notin I$, верно также
$xy\notin I$.

\item[(ii)] Факторкольцо $R/I$ не имеет делителей нуля.

\end{description}
\ео

\задача Докажите, что эти условия равносильны.
\ез

\определение
Идеал $I\subset R$ в кольце называется {\бф максимальным},
если $R/I$ - это поле.
\ео

\замечание
Ясно, что любой максимальный идеал является простым.
\еза

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\утверждение
Если $p\in R$ - простой элемент в кольце главных идеалов,
то порожденный им идеал $I=pR$ - максимальный.

\хфилл

{\бф Доказательство:}
Возьмем ненулевой элемент $x\in R/I$, и докажем,
что он обратим. Предположим, что он необратим,
а следовательно, порождает идеал $J\subset R/I$.
Рассмотрим идеал $\pi^{-1}(J)\subset R$, где
$\pi:\; R \arrow R/I$ - естественная проекция.
Этот идеал главный, поскольку порожден
$p$ и каким-то представителем класса $x\in R/I$.
Пусть $d$ - образующая идеала $\pi^{-1}(J)$.
Поскольку $\pi^{-1}(J)$ содержит $p$,
$d$ является делителем $p$, а значит,
пропорционален $p$ (тут мы используем
то, что $p$ просто). Но в этом случае
$\pi^{-1}(J)$ совпадает с $I$, а следовательно,
$x=0$. \endproof

\hfill

Из простоты идеала $pR$ сразу следует 
лемма Евклида, которая была ключевым местом
в доказательстве Евклида (и Гаусса) основной
теоремы арифметики.

\hfill

{\бф Лемма Евклида:} Пусть $p\in R$ простое, $a$ и $b\in R$ 
взаимно просты, и $ab$ делится на $p$. Предположим, что одно из
следующих условий верно.
\begin{description}

\item[(i)] $R$ - евклидово кольцо

\item[(ii)] $R$ - кольцо главных идеалов

\item[(iii)] Идеал $pR$ прост

\end{description}
Тогда $a$ либо $b$ делится на $p$.

\хфилл

{\бф Доказательство:} Как доказано выше, 
если $R$ евклидово, то это кольцо
главных идеалов, а в этом случае $pR$ максимальный, а
следовательно - простой. Поэтому достаточно вывести,
что $a$ либо $b$ делится на $p$, из простоты идеала
$pR$. Но если $ab$ делится на $p$, то $ab\in pR$,
и в этом случае $a$ либо $b$ лежит в $pR$
по определению простого идеала.
\endproof

\хфилл

Из леммы Евклида единственность разложения
на простые множители следует сразу. Действительно,
пусть у $a\in R$ есть два разложения на простые
множители, которые не получаются одно из другого
перестановкой. Разделив $a$ на все сомножители,
общие в этих разложениях, мы можем предположить,
что в этих разложениях нет общих простых
сомножителей. Но это значит, что $a=p_1p_2... p_n$
делится на некоторое простое $p$, причем каждый
из простых сомножителей $p_1, ... p_n$ не делится
на $p$. Это противоречит лемме Евклида.
Поэтому разложение на простые множители
единственно в любом кольце главных идеалов.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Мультипликативная группа $(\Z/p\Z)^*$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Пусть $p\in \Z$ - простое число.
Поскольку $\Z$ - кольцо главных идеалов,
кольцо остатков $\Z/p\Z$ - поле. 
Рассмотрим "мультипликативную группу" поля
$\Z/p\Z$ (группу всех ненулевых элементов
с операцией умножения). Эта группа 
обозначается $(\Z/p\Z)^*$.

В дальнейшем, нам потребуется следующая
теорема.

\hfill

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\теорема
Пусть $p\in \Z$ - простое число. Тогда 
мультипликативная группа
$(\Z/p\Z)^*$ - циклическая.

\hfill

{\bf Доказательство:}
Пусть $a\in G$ элемент абелевой группы
порядка $p_1^{\alpha_1} p_2^{\alpha_2}... p_n^{\alpha_n}$.
Взяв соответствующую степень $a$, можно получить
элемент порядка $p_i^{\alpha_i}$.
Если порядки $m, n$ элементов $x, y\in G$
взаимно просты, их произведение имеет порядок $mn$ 
(проверьте!). Из этого легко вывести следующее
утверждение

\задача
Пусть
$x, y\in G$ - элементы абелевой группы порядков 
$n$ и $m$. Тогда в $G$ найдется
элемент порядка НОК$(n,m)$, где НОК$(n,m)$
обозначает наименьшее общее кратное
$n$ и $m$ (наименьшее число, которое
делит $n$ и $m$). 
\ез

Применим эту теорему к группе $(\Z/p\Z)^*$.
Пусть $n$ - наименьшее общее кратное
порядков всех элементов $(\Z/p\Z)^*$.
Применив предыдущую задачу и воспользовавшись
индукцией, мы получим, что в $(\Z/p\Z)^*$
найдется элемент $\zeta$ порядка $n$. По теореме
Лагранжа, $n$ делит порядок $(\Z/p\Z)^*$, который
равен $p-1$.

Все элементы $(\Z/p\Z)^*$ (а их $p-1$)
являются решениями уравнения $t^n =1$.
Легко видеть, что в поле у полиномиального
уравнения вида степени $n$ может быть
не больше $n$ решений (см. задачу \ref???).
Поэтому $n\geq p-1$. Как указано выше,
$n$ делит $p-1$, и следовательно $n=p-1$.
Поэтому все элементы $(\Z/p\Z)^*$
могут быть представлены в виде степеней 
$\zeta \in (\Z/p\Z)^*$. Следовательно,
группа $(\Z/p\Z)^*$ циклическая.
\endproof

\hfill

Из этой теоремы можно получить разные полезные
следствия об арифметике поля $\Z/p\Z$, например такое.

\hfill

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\лемма\label{_sqrt-1_in_z_p_z_Lemma_}
Пусть $p\in \Z$ простое число больше 2.
Уравнение $t^2=-1$ имеет решения
в $\Z/p\Z$ тогда и только тогда, когда
$p$ имеет вид $4k+1$.

\хфилл

{\бф Доказательство:}
Порядок группы $(\Z/p\Z)^*$
делится на 4 для $p=4k+1$,
а поскольку эта группа циклическая,
там есть элемент порядка 4. Элемент
порядка 2 в $(\Z/p\Z)^*$ всего один, поскольку
у уравнения $t^2=1$ не может быть больше
двух решений. Следовательно, квадрат элемента
порядка 4 равен -1.

Если же $p=4k+3$, элементов порядка 4 не может
быть в $(\Z/p\Z)^*$ по теореме Лагранжа.
Но любое решение уравнения $t^2=-1$
удовлетворяет $t^4=1$, следовательно,
имеет порядок 4. \endproof




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Простые элементы в кольце целых гауссовых
чисел}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Кольцо целых гауссовых чисел $\Z[\1]$ 
(чисел вида $a+b\1$) евклидово (см. задачу \ref???).
Это доказал Гаусс в 1831-м году. 
Дедекинд использовал этот факт, чтобы
получить теорему Ферма о представимости
простых чисел в виде суммы двух квадратов.

\хфилл

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\теорема\label{_Fermat_sum_squares_Theorem_}
 Пусть $p\in \Z$ - простое число больше 2.
Тогда $p$ представимо в виде $p = x^2 + y^2$, $x, y\in \Z$
тогда и только тогда, когда $p=4k+1$.

\хфилл

Мы докажем Теорему \ref{_Fermat_sum_squares_Theorem_} 
в конце этого раздела.

\замечание
Простое число больше 2 нечетно, то есть имеет вид 
$p=4k+1$ либо $p=4k+3$. Во втором случае $p$ не
может быть представлено в виде $p = x^2 + y^2$. 
Действительно, раз $p$ нечетно, то $x$ должен
быть нечетен, а $y$ четен, или наоборот.
Но четное число делится на 4, а квадрат
нечетного числа дает остаток 1 при делении на 4
(проверьте!). Поэтому число вида $p=4k+3$
не может быть представлено в виде суммы 
двух квадратов.
\еза

\хфилл

Дедекинд использовал следующий аргумент.
Если целое число $a\in \Z$ просто в  $\Z[\1]$,
то оно просто и в $\Z$. Обратное не всегда верно -
некоторые простые в $\Z$ числа оказываются составными
в $\Z[\1]$. Простые сомножители таких чисел
не могут быть вещественными: в геометрическом
представлении комплексных чисел, они располагаются
либо кверху, либо книзу от оси абсцисс. 
Разобьем эти сомножители на две группы, первая
кверху от горизонтали, вторая книзу:
\[
p= q_1 q_2... q_n p_1 p_2... p_n
\]
Комплексное сопряжение действует
на $\Z[\1]$ автоморфизмом, переводя $p$ в себя.
Из единственности разложения на простые множители
ясно, что оно переводит группу сомножителей
$q_1 q_2... q_n$, лежащую кверху от абссцисс,
в группу сомножителей $p_1 p_2... p_n$,
лежащую книзу, и наоборот. Группируя их
попарно, получаем
\[
p = q_1\bar q_1 q_2 \bar q_2 ... q_n \bar q_n.
\]
Каждый из сомножителей вида $q_i \bar q_i$ лежит в $\Z$,
а раз $p$ просто в $\Z$, такой сомножитель всего один.
Мы получаем, что
$p= q\bar q$, где $q$ и $\bar q$ просты в $\Z[\1]$.
Записав $q= x+ y\1$, мы получим $p = x^2 + y^2$.
Мы получили такую теорему.

\хфилл

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\теорема
 Пусть $p\in \Z$ положительное простое число.
Если $p$ не представимо в виде суммы квадратов целых чисел,
то оно просто в $\Z[-1]$. Если же $p$
представимо в виде суммы квадратов, $p= x^2 + y^2$, 
то $p$ разлагается в   $\Z[-1]$ в произведение
\[
p = (x+ y\1)(x-y\1),
\]
причем сомножители $x+y\1$, $x-y\1$ просты в $\Z[-1]$.
В этом случае разложение $p$ в сумму квадратов
единственно.

\endproof

\хфилл

Пусть $a\in \Z[\1]$ - простое. Сомножителей
у $a$ столько же, сколько у $\bar a$, потому что
отображение $a\arrow \bar a$ задает автоморфизм 
кольца $\Z[\1]$. Поэтому $a \bar a=|a|^2$
имеет не больше двух простых сомножителей в $\Z[\1]$,
а следовательно и в $\Z$.

Если $|a|^2$ просто, то $a$ тоже просто, как мы только что доказали.

Если же $|a|^2$ не просто в $\Z$, то у $a \bar a$
в $\Z$ есть два сомножителя, как и в $\Z[\1]$,
а значит $a$ и $\bar a$ вещественны. 
В этом случае $a$ - простое число в $\Z$,
не разложимое в сумму квадратов. Мы получили
такую классификацию простых элементов в $\Z[\1]$.

\хфилл

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\теорема
Пусть $a\in \Z[\1]$ - простой элемент в $\Z[\1]$.
Тогда, с точностью до обратимого множителя, $a$ может быть
записано так.
\begin{itemize}
\item Либо $a$ - простое целое число, не разложимое
в сумму квадратов

\item либо $a=x\pm y\1$,
где $x^2 + y^2=p$ просто в $\Z$.

\end{itemize}

\endproof

\хфилл

Поскольку $\Z[\1]$ евклидово, это кольцо
главных идеалов. Поэтому $p\in \Z$ просто в $\Z[\1]$
тогда и только тогда, когда $p\Z[\1]$ - максимальный идеал.
Для доказательства Теоремы \ref{_Fermat_sum_squares_Theorem_},
нам нужно показать, что $p\Z[\1]$ - не максимальный идеал
для простого числа $p=4k+1$. Рассмотрим факторкольцо
$\Z/p\Z[\1]$. Докажем, что это не поле.

Согласно Лемме \ref{_sqrt-1_in_z_p_z_Lemma_},
доказанной в предыдущем разделе,
в $\Z/p\Z$ найдется $\xi$ такое, что
$\xi^2=-1$. Рассмотрим элемент 
$\xi\pm\1\in Z/p\Z[\1]$. Этот элемент,
очевидно, ненулевой. С другой стороны,
\[
(\xi-\1)(\xi+\1) = \xi^2-\1^2 = -1 +1 =0,
\]
а значит, в $\Z/p\Z[\1]$ найдутся делители нуля.
Поэтому это не поле, и, следовательно, $p=4k+1$
не просто в $\Z[\1]$. Мы доказали теорему
Ферма о разложении простых чисел в сумму квадратов
(Теорема \ref{_Fermat_sum_squares_Theorem_}).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Замечания, терминология, библиография}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Теория уравнений в целых числах ("диофантовых
уравнений") восходит к древним грекам, но систематически
заниматься решением подобных уравнений стал Пьер Ферма,
положив начало современной теории чисел. Эти
исследования были весьма плодотворными.
Многие понятия, возникшие в теории чисел 
(кольца, идеалы, группы) стали центральными
в других областях математики.

Идеалы ("идеальные числа") были изобретением Куммера,
который пытался таким образом преодолеть проблему
неоднозначности разложения на множители в кольцах вида
$\Z[\xi]$, где $\xi$ - комплексный корень из единицы.
Идеи Куммера развил Дедекинд, предложивший современную
версию этого понятия.

ПОРТРЕТ КУММЕРА!!!

Теория идеалов в коммутативных кольцах лежит в фундаменте
алгебраической геометрии, одного из самых важных разделов
математики. Основы этой науки изложены в "Алгебре"
Ван Дер Вардена. Дальнейший материал можно найти в
великолепном учебнике Атьи и Макдональда "Коммутативная
алгебра". Приложения коммутативной алгебры 
к алгебраической геометрии рассказываются
в учебнике Шафаревича "Алгебраическая геометрия".
Стандартным руководством по алгебраической
геометрии с точки зрения коммутативной алгебры
является "Алгебраическая геометрия" Р. Хартсхорна.

Прекрасное введение в теорию чисел для 
студентов и школьников - книга Ж.-П. Серра 
"Курс арифметики". Алгебраическая теория чисел 
(с упором на исторически важные попытки доказательства
теоремы Ферма) излагается в книге Постникова
"Алгебраическая теория чисел". Тот же самый
материал, в большей подробности и аккуратнее,
есть в книжке Г. Эдвардса "Последняя теорема
Ферма. Генетическое введение в алгебраическую 
теорию чисел".

Идеальное руководство по алгебраической теории
чисел - "Алгебраическая теория чисел", 
Дж. Касселс, А. Фрелих (ред.). Также весьма
полезна монография Боревича-Шафаревича 
"Теория чисел".

Терминология: идеал, простой идеал, 
максимальный идеал, главный идеал - ideal,
prime ideal, maximal ideal, principal ideal.
Гауссовы числа - Gaussian integers.
Кольцо, где выполнена Основная Теорема
Арифметики - unique factorization domain,
UFD, factorial ring (последний термин
изобретен Бурбаки). По-русски такое
кольцо часто называют {\бф факториальным}.


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

\chapter[Алгебраические числа
(Алгебра 3)]{Алгебраические числа\\
(Алгебра 3)}

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Симметрические многочлены}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\бф Характеристикой} поля $k$ называется
порядок элемента $1$ в аддитивной группе $k$,
если он конечен. Если этот порядок бесконечен,
говорится, что $k$ - поле характеристики 0.

Поле $\Z/p\Z$ имеет характеристику $p$,
а поле $\Q$ - характеристику 0. 
Характеристика поле $k$ обозначается $\cchar k$.
На протяжении
этого раздела, мы будем предполагать, что
задано поле $k$, $\cchar k=0$.

Рассмотрим кольцо $k[x_1, ... x_n]$ многочленов
от $n$ переменных. Многочлен $P(x_1, ..., x_n) \in k[x_1, ... x_n]$
называется {\бф симметрическим}, если для любой
перестановки
\[
\sigma=\begin{pmatrix}
1& 2& 3 & ... &n\\
\sigma_1 & \sigma_2& \sigma_3& ...&\sigma_n
\end{pmatrix}
\]
многочлен 
\begin{equation}\label{_sigma(P)_Equation_}
\sigma(P)= P(x_{\sigma_1}, x_{\sigma_2}, ... x_{\sigma_n})
\end{equation}
равен $P$.

Научно выражаясь, симметрическая группа $S_n$ (группа
подстановок) действует на кольце многочленов
автоморфизмами по формуле \eqref{_sigma(P)_Equation_},
а симметрические многочлены - это в точности
многочлены, которые любая подстановка 
переводит в себя (такие элементы называются
"инвариантными при действии группы").

\хфилл

\пример
Симметрическими многочленами от двух переменных являются
$x_1+x_2$ и $x_1x_2$ и еще, например, $x_1^2+x_2^2$.
Многочлен $x_1^2 +x_2$ симметрическим не является,
потому что перестановка 
\[
\sigma=\begin{pmatrix}
1& 2\\
2&1
\end{pmatrix}
\]
переводит $x_1^2 +x_2$ в $x_2^2 +x_1$.

\хфилл

Легко видеть, что сумма и произведение
симметрических многочленов - тоже симметрический
многочлен. Следовательно, 
симметрические многочлены образуют кольцо
$k[x_1, .... x_n]^{S_n}\subset k[x_1, .... x_n]$.




\хфилл

Рассмотрим полином $\chi(t)\in R[t]$ с коэффициентами в кольце
$R=k[x_1, ... x_n]$, 
\[
\chi(t) = (t+x_1)(t+x_2) ... (t+x_n).
\]
Раскрыв скобки, получим
\[
\chi(t) = t^n + (x_1+x_2+... +x_n) t^{n-1} +
\left(\sum_{i<j} x_i x_j\right) t^{n-2} + ... + x_1 x_2 ... x_n
\]
Коэффициенты этого полинома - элементы кольца
$k[x_1, ... x_n]$. Обозначим их за $\goth{s}_i$.
Старший коэффициент $\goth{s}_0=1$, следующий 
по старшинству $\goth{s}_1=x_1+x_2+... +x_n$, и так далее,
а свободный член $\goth{s}_n$ - произведение всех $x_i$.

Поскольку полином $P(t)$ инвариантен относительно
действия группы $S_n$, то же самое верно для всех полиномов
$\goth{s}_i$. Следовательно, эти полиномы симметрические.

\определение
Полиномы $\goth{s}_i$, $i=1, ... n$ называются 
{\бф элементарными симметрическими полиномами}.
\ео

Мы говорим, что полином $Q(x_1, ... x_n) \in k[x_1, ... x_n]$
{\bf выражается через $\goth{s}_i$, $i=1, ... n$},
если можно выразить $Q$ как линейную комбинацию
произведений каких-то $\goth{s}_i$: к примеру,
\[
Q= \goth{s}_1 + \goth{s}_2^2 + 
\goth{s}_1 \goth{s}_3 \goth{s}_5 + \goth{s}_8^9 \goth{s}_1.
\]
Основная теорема о симметрических полиномах
(известная, вероятно, еще Ньютону) утверждает,
что любой симметрический полином выражается
через элементарные.

\хфилл

\теорема
Пусть $Q(x_1, ... x_n) \in k[x_1, ... x_n]$ -
симметрический полином. Тогда $Q$ выражается через
элементарные симметрические полиномы $\goth{s}_i$, $i=1, ... n$:
\[
Q(x_1, ... x_n) = 
Q'(\goth{s}_1(x_1, ... x_n), \goth{s}_2(x_1, ... x_n),
... \goth{s}_n(x_1, ... x_n)),
\]
где $Q'$ - какой-то многочлен он $n$ переменных.


\хфилл

{\бф Доказательство:}
Докажем эту теорему, пользуясь индукцией по $n$.
Для $n=1$ все очевидно. Подставляя в $Q$ 
$x_n=0$ (т.е. отбрасывая все мономы, которые
делятся на $x_n$), получаем симметрический
полином $Q_1(x_1, ... x_{n-1})$, который,
по предположению индукции, выражается через
элементарные симметрические полиномы
от $n-1$ переменных. 





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Замечания, терминология, библиография}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Полезное руководство по началам алгебры -
записки лекций А. Г. Кузнецова, досупные на сайте 
Независимого Университета:\\
http://www.mccme.ru/ium/s03/alg1.html \\
http://www.mccme.ru/ium/f02/alg1.html



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

\chapter{Следствия аксиомы выбора}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Счетная аксиома выбора}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Теорема Цермело}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Следствие: любые два множества либо равномощны,
либо одно больше другого, либо наоборот

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Континуум-гипотеза}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Лемма Цорна}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Существование базиса.



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

\chapter[Векторные пространства и категории
(Алгебра 4)]{Векторные пространства и категории\\
(Алгебра 4)}

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



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

\chapter[Векторные пространства с нормой
(Геометрия 3)]{Векторные пространства с нормой\\
(Геометрия 3)}

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



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

\chapter[Тензорная алгебра
(Алгебра 5)]{Тензорная алгебра\\
(Алгебра 5)}

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




\end{document}




%Первым шагом в этом направлении было доказательство
%Эйлером неразрешимости в целых числах
%нескольких уравнений, в том числе 
%"теоремы Ферма" (неразрешимости
%в целых числах уравнения $a^n + b^n = c^n$, $n\geq 2$)
%для $n=3$. Эйлер рассмотрел кольцо $\Z[\xi]$
%чисел вида $a+b\xi$, где $a, b \in Z$ целые,
%а $\xi^3=1$ - комплексный корень 3-й степени из 1. 
%Предположив, что в этом кольце разложение
%на простые множители единственно (см. задачу \ref???),
%Эйлер заключил, что уравнение
%$a^3 + b^3 = c^3$ решений в целых числах не имеет.
%
%ПОРТРЕТ ЭЙЛЕРА!!!
%
%Первоначальный
%аргумент Эйлера был довольно сложен, но суть его можно
%передать весьма просто. Пусть $a, b, c$ - решения 
%уравнения $a^3 + b^3 = c^3$. Сократив общие множители,
%можно считать, что $a, b, c$ взаимно просты. 
%
%Пусть $(a, b,c)$ - попарно взаимно простые
%решения уравнения $a^3 + b^3 = c^3$.
%Из всех троек такого вида выберем такую,
%в которой максимум $\max(a, b,c)$ наименьший.
%Перепишем это уравнение как
%\[
%(a+b)(a+\xi b) (a+\xi^2b)=c^3
%\]
%(тут требуется раскрыть скобки и проверить, что
%$(a+b)(a+\xi b) (a+\xi^2b)= a^3+b^3$.
%
%Поскольку $a$ и $b$ взаимно просты, числа
%$(a+b)$, $(a+\xi b)$,  $(a+\xi^2b)$ 
%попарно взаимно просты (проверьте!).
%А поскольку их произведение является
%третьей степенью, каждое из них, с точностью 
%до обратимого элемента $\Z[\xi]$  - 
%третья степень (это следует из единственности 
%разложения на простые множители).
%Имеем
%\begin{equation}\label{^3_Equation_}
%a+b = t^3, \ \ a+\xi b = \lambda u^3,
%\end{equation}
%где $\lambda$ - обратимый элемент $\Z[\xi]$.
%
%Полезно отметить, что $\xi+\xi^2+1=0$ (в геометрической
%интерпретации комплексных чисел, $\xi+\xi^2+1$ это сумма
%векторов от $(0,0)$ к вершинам равностороннего
%треугольника). 
%Также, как легко видеть,  
%$\bar \xi = \frac{|\xi|^2}{\xi}=\xi^{-1}=\xi^2$.


Про гиперкомплексные числа:
http://64.233.183.104/search?q=cache:UTK6-BfdK4oJ:www.ems-ph.org/journals/show_pdf.php%3Fissn%3D0013-6018%26vol%3D53%26iss%3D1%26rank%3D2+%22gaussian+integers%22+unique+factorization+history&hl=ru&ct=clnk&cd=12


