Представим, что у нас есть какая-то категория. Мы взяли три объекта этой категории: X1, X2, X3. Никаких стрелок между ними мы не брали. Просто три объекта. Пик1.

Любая конфигурация из некоторого объекта K и трёх стрелок: из K в X1, из K в X2, из K в X3 называется конусом над X1, X2, X3. Обозначается (K, f1,f2,f3). Объект K называется вершиной конуса. Пик2.

Конусов, вообще говоря, бывает много. На пик3 нарисованы два конуса. Один с вершиной в K, другой с вершиной в C.

Некоторые конусы являются универсальными. Конус с вершиной K называется универсальным, если для любого другого конуса с вершиной в некотором объекте C существует единственная стрелочка из C в K, делающая диаграмму коммутативной. Пик4.

Универсальных конусов может быть много. Но любые два универсальные конуса изоморфны. В самом деле, пусть конусы с вершинами в C и в K - универсальные. Тогда существует единственная универсальная стрелка h из C в K и единственная универсальная стрелка h' из K в C. Но это значит, что hh' = id K и h'h = id C, то есть h - изоморфизм. Ну и h' тоже изоморфизм, понятно.

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

Между объектами, над которыми строится конус, могут быть какие-то морфизмы. В нашем случае морфизмов нет, но так-то они могут быть. Диаграмма, над которой строится конус, может быть сколь угодно сложной. В нашем случае она простая, лишь три объекта и нуль стрелок между ними, - но это лишь в нашем случае.
По-другому универсальный конус называется "предел диаграммы".

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

Итак, пусть есть категория. Пусть I - какое-то множество индексов. Везде, где есть индексы, подразумевается, что они из I.

Утверждение, что объект X1×X2×X3... (возможно, правильнее было бы обозначить его ΠXi) с присовокуплённым к нему семейством морфизмов πi (они называются каноническими проекциями) есть произведение объектов Xi, означает, что для любого объекта Y и для любого семейства морфизмов
fi: Y→Xi
существует единственный морфизм
f: Y→X1×X2×X3...
, делающий каждую диаграмму пикрелейтед коммутативной, i пробегает I. Другими словами, любой морфизм в компоненту произведения есть проекция морфизма в произведение. X1×X2×X3... - это один цельный символ, обозначающий один-единственный объект. Его можно заменить буквой W или какой-нибудь другой буквой без потери смысла. Подчеркну, что произведение объектов - это не просто объект, а "объект + канонические проекции".

Вот частный случай произведения семейства объектов: произведение двух объектов. В трёх картинках сверху вниз.

На первой из картинок можно наблюдать три объекта и два морфизма.
A, B и A×B - три объекта.
p1 - это морфизм из A×B в A, p2 - это морфизм из A×B в B.

Пусть крестик в названии A×B вас не смущает. С тем же успехом можно было бы обозначить объект A×B буквой W или какой-нибудь другой буквой. Крестик не означает, что уже произошло применение какой-то операции. Это просто часть имени.

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

На второй картинке вы можете наблюдать появление новых действующих лиц: на сцену выходят объект X и два морфизма f1 и f2. Мы ничего особенного не знаем об объекте X; это просто какой-то объект. Морфизм f1 не обязан быть единственным морфизмом из X в A, равно как и кроме выбранного нами морфизма f2 из X в B может быть ещё много других морфизмов. Мы просто выбрали один произвольный объект с двумя произвольными морфизмами.

Теперь, пожалуйста, внимание на третью картинку. Если объект A×B с морфизмами p1 и p2 является произведением объектов A и B, то существует, и притом лишь один-единственный, морфизм f из X в A×B такой, что ``p1∘f = f1``, и ``p2∘f = f2``.

На прошлой диаграмме (в прошлом посте) был один-единственный треугольник. Диаграмма, прикрепленная к этому посту, составлена из двух треугольников с предыдущей диаграммы. На одной этой диаграмме совмещены и случай i=1, и случай i=2, один слева, другой справа. Вместо этой цельной диаграммы из двух треугольников можно - и от этого ничего не изменится - нарисовать два этих треугольника на двух разных картинках.

Вот у нас есть индексированные семейства. Семейство - это когда у нас есть множество индексов, множество элементов и функция, сопоставляющая каждому индексу какой-нибудь элемент. Аналогичную конструкцию можно сделать в категориях. Для этого просто представим, что у нас есть какая-то индексная категория, какая-то индексируемая категория и индексирующий функтор из первой во вторую. То есть мы заиндексировали не только объекты, но и морфизмы, причём не множеством, а категорией.

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

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

Пусть у нас нарисован конус с вершиной L. Если для любого другого конуса с вершиной N мы имеем право нарисовать одну и лишь одну стрелку из N в L, делающую всю картинку коммутативной, то этот особенный конус с вершиной L будем называть универсальным конусом. Или, иначе говоря, пределом той диаграммы, к которой мы взялись пририсовывать конусы.

Универсальный конус - это самый общий конус.

Вот, например, пример. На первой картинке диаграмма из двух объектов. Просто объекты, без всяких нетривиальных морфизмов (в каждом объекте болтается тождественный морфизм, но их мы не рисуем). Такая диаграмма называется дискретной диаграммой из двух объектов.

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

На третьей картинке изображён предел этой диаграммы - конус с вершиной L (что это предел, сообщаю я; по самой диаграмме это узнать нельзя, понятное дело). Из вершины любого другого конуса, - в частности, конуса с вершиной N, - в L опущена одна и только одна стрелка, делающая, по определению предела, диаграмму коммутативной.

По определению произведения, конус с вершиной L и исходящими из неё лучами - произведение объектов A и B. То есть произведение объектов - это предел диаграммы {A; B}. Тут я допускаю небольшую вольность речи, но суть не искажается.

Рассмотрим предел диаграммы первой картинки (два объекта с двумя морфизмами между ними, такая диаграмма называется "два параллельных морфизма"). Пределом будет конус с вершиной E (из конуса должны идти стрелки во все вершины, но так как диаграмма коммутативна и композиция морфизмов - морфизм, достаточно нарисовать одну стрелку в X). Из вершины любого другого конуса есть единственная стрелка в E, делающая диаграмму коммутативной. Этот предел называется эквалайзер, или уравнитель двух морфизмов.

У уравнителя есть теоретико-множественная интерпретация. Уравнитель двух функций f и g из X в Y - это наибольшее подмножество в X, на котором функции равны, с морфизмом вложения. Вершины других конусов - это другие подмножества X, на которых функции равны. То есть вершина уравнителя - это множество всех решений уравнения f(x)=g(x).

Вот картинка. Так не стоит рисовать (совмещены две разные картинки в одной), но я нарисую (мне лень рисовать две картинки и к тому же на одной имхо нагляднее).

Объект E со стрелкой eq из E в X называется эквалайзером стрелок f и g из X в Y, если f∘eq = g∘eq и если для любого объекта W и стрелки e из W в X такой, что f∘e = g∘e, существует и притом единственная стрелка u из W в E такая, что e = eq∘u.

Докажем, что любая стрелка эквалайзера - моник, т.е. на стрелку эквалайзера можно сокращать слева.
Допустим, что есть объект A и две стрелки p,q из A в E такие, что eq∘p = eq∘q.
Если мы докажем, что обязательно тогда будет p=q, то стрелка eq будет моником

Введем обозначение z для морфизма eq∘p, он же eq∘q.
То есть z = eq∘p = eq∘q.
z будет стрелкой из A в X. И причём
f∘z = f∘(eq∘p) = (f∘eq)∘p = (g∘eq)∘p = g∘(eq∘p)=g∘z;
f∘z =g∘z

По определению эквалайзера существует и притом единственная стрелка u из A в E такая, что z=eq∘u.
Сосредоточим наше внимание на словах "и притом единственная".
У нас есть две стрелки p и q из A в E такие, что z=eq∘p и z=eq∘q.
Слова "и притом единственная" означают, что эти стрелки равны.
Ибо если бы они не были равны, то у нас было бы две различные стрелки, пригодные на роль u, и поэтому eq не было бы эквалайзером.

Пусть A, A', B, B' - объекты категории C.
Пусть произведения A×A' и B×B' определены.
Проекции обозначим соответственно p1 и p2, и q1 и q2.

Пусть f - морфизм из A в B и f ' - морфизм из A' в B'.
Определим произведение морфизмов f и f' как единственную стрелку, делающую диаграмму пикрелейтед коммутативной.
Обозначим его f×f '.

По смыслу, мы тут просто образуем упорядоченные пары (A,A') и (B,B') и вводим морфизм между ними покомпонентно.

Напомним определение группы.
Группой называется пара (X,∘)
где X - множество,
∘ - функция из X×X в X такая, что верны три аксиомы:

1. Ассоциативность. Для любых a,b,c из X верно, что (a∘b)∘c = a∘(b∘c).

2. Существование левого нейтрального.
Существует такой элемент e из X, что для любого x из X верно что e∘x = x.

3. Существование левого обратного.
Для любого x из X существует такой элемент x' из X, что x'∘x = e, где e - левый нейтральный элемент.

Верны следующие два утверждения.
1. Левый нейтральный является правым нейтральным, т.е. для любого x из X верно, что x∘e = x.
2. Левый обратный является также правым обратным, т.е. для любого x из X верно, что x∘x' = e.
Доказательство. Пусть x' - левый обратный для x, пусть x'' - левый обратный для x'.
Тогда x∘e = e∘(x∘e) = (e∘x)∘e = ((x''∘x')∘x)∘e = (x''∘(x'∘x))∘e = (x''∘e)∘e = x''∘(e∘e) = x''∘e = x''∘(x'∘x) = (x''∘x')∘x = e∘x = x.
Кроме того, x∘x' = e∘(x∘x') = (e∘x)∘x' = ((x''∘x')∘x)∘x' = (x''∘(x'∘x))∘x' = (x''∘e)∘x' = x''∘x' = e.

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

Переформулируем определение группы чисто в терминах функций.

Групповой закон есть функция из X×X в X по определению. Переобозначим его буквой c, т.е. x∘y = c(x,y).
Тогда группа есть пара (X,c).

Обратим наше внимание на нейтральный элемент.
Пусть 1 - некоторое фиксированное нами одноэлементное множество.
О левом нейтральном элементе можно думать как о функции η из 1 в X.
Т.е. функция η указывает одну конкретную точку в X.
Скроем выбор множества 1 внутри некой функции, а именно введём функцию ε, которая отображает X в 1.
Теперь вместо функции η на постороннем множестве мы можем рассматривать функцию η∘ε, определённую на множестве X.
То есть теперь левый нейтральный элемент указывается функцией η∘ε.
Нам осталось сформулировать на языке функций, что такое "быть левым нейтральным".
Введём служебную функцию d, определив её так: d(x) = c(x,x). Напомню, что c - групповой закон.
Введём тождественную функцию id, определив её так: id(x) = x.
Образуем произведение функций η∘ε и id в категорном смысле.
Функция (η∘ε × id) определена на множестве X×X и действует покомпонентно, отображая пару (p,q) элементов X в пару (η∘ε(p), id(q)).
А функция c у нас определена как раз на парах элементов X.
Итак.
Пусть x - элемент X.
Функция d(x) переводит его в пару (x,x).
Функция (η∘ε × id) переводит эту пару в пару ((η∘ε)(x), x).
Наконец, функция c переводит эту пару в некий элемент y множества X.
Чтобы точка, которую указывает функция η∘ε, действительно была нейтральным элементом, нужно, чтобы вот это полученное нами в результате y было бы равно тому x, с которого мы начинали. Т.е. чтобы выполнялось равенство функций
c∘(η∘ε × id)∘d = id.
Конечно же, значок композиции ∘ тут обозначает композицию функций.

Обратим наше внимание на обратный элемент.
О левом обратном элементе можно думать как о функции α из X в X.
То есть функция α каждому элементу множества X сопоставляет другой элемент x' множества X.
Причём она делает это так, что если применить функцию c к паре (α(x),x), то получится нейтральный элемент.
Образуем категорное произведение функций α и id, а также воспользуемся обозначениями из предыдущего пункта.
Пусть x - элемент X.
Подействовав на него функцией d, образуем пару (x,x).
Подействовав на эту пару фунцией (α×id), получим пару (x',x).
Подействовав на эту пару функцией c, получим нейтральный элемент, т.е. (η∘ε)(x).
Итак, функция α доставляет нейтральные элементы - значит, верно равенство функций c∘(α × id)∘d = η∘ε.

Обратим наше внимание на ассоциативность.
Образуем произведение (c×id), которое отображает X×X ×X во множество X×X.
А именно, тройке (p,q,r) сопоставляет двойку (c(p,q), r).
Образуем произведение (id×c), которое отображает X ×X×X во множество X×X.
А именно, тройке (p,q,r) сопоставляет двойку (p, c(q,r)).
Ассоциативность означает равенство этих двоек.
Т.е. выполнение равенства функций c∘(c×id) = c∘(id×c).

Теперь дадим абстрактное определение группового закона композиции в категории C.

Пусть C - такая категория, что в ней определены конечные произведения, а также есть конечный объект 1, т.е. такой объект 1, что для любого объекта X существует один и только один морфизм из X в 1.
Произведение объектов и морфизмов обозначим с помощью ×.
Значок композиции ∘ обозначает композицию стрелок.

Магмовыми (ед.ч. магма) законами композиции на объекте X назовём всевозможные морфизмы из X×X в X.
Пусть c - магмовый закон на X. Назовём его ассоциативным, если для него диаграмма с подписью "ассоциативность" коммутативна.

Пусть c - ассоциативный закон на X. Пусть ε - морфизм из X в 1 (по условию, есть только один такой морфизм). Пусть d: X→X×X - диагональный морфизм. Назовём c групповым законом, если существуют такие морфизмы η:1→X и α:X→X, что диаграммы с подписями "левая единица" и "левый обратный" коммутативны.

Пусть c - групповой закон на X. Тогда пару (X,c) назовём C-группой.

Пусть категория С - это Set. Морфизмы в ней есть теоретико-множественные отображения. Если пара (X,c) из объекта X и морфизма c есть Set-группа, то X - множество, а c - отображение из X×X в X, являющееся обычной групповой операцией на X. То есть Set-группы - это обычные группы.

>>105187
На картинке "ассоциативность" опечатка, там id×c, конечно.

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

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

Внеязыковые сущности и их движение представляются, репрезентуются, манифестируются в языке с помощью языковых сущностей - словесных конструкций. Внеязыковая действительность и язык соотносятся так же, как местность и изображающая её карта. Языки - это карты внеязыковой действительности. Как известно, самой точной из всех возможных карт местности является сама эта местность; любая другая карта содержит меньше информации о местности. При этом карта местности всё-таки отражает местность, пусть и с потерей информации; собственно, этим-то и ценны карты - они позволяют отбрасывать ненужную, избыточную информацию о местности. Аналогичное имеет место и с языками.

Язык отражает внеязыковую действительность всегда с потерей информации; внеязыковая действительность всегда полнее языка. Как бумажная карта местности является всего лишь отражением самой местности, так и язык является всего лишь отражением внеязыковой действительности. Слова лишь символизируют действительность, но не являются ею. Нельзя свести всё сущее к какому-то языку. Мир не есть текст. Языки лишь отражают мир.

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

Как правило, наши фантазии не хаотичны. Мыслеобразы, живущие в нашем сознании, - это модели сущностей из данной в ощущениях реальности. Например, в моём сознании есть мыслеобраз кружки с чаем: как только я говорю слова "кружка с чаем", я ощущаю возникновение некоего образа. Этот мыслеобраз весьма размыт. Я не могу измерить температуру чая в воображённой мной кружке, не могу назвать цвет кружки. Но всё-таки он достаточно отчётлив, чтобы можно было отличить его от мыслеобраза, скажем, шляпы.

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

Поскольку человеческие сознания похожи друг на друга, люди часто создают похожие мыслеобразы. Это позволяет людям создавать мыслеобразы не в одиночку, а сообща. Люди ведут работу над мыслеобразами посредством языка. Один человек может передать свою фантазию другому человеку с помощью речи, с помощью текста. Но поскольку внеязыковая действительность отражается в языке с потерей информации, человек не может передать свою фантазию в точности так, как она была им воображена. Чем менее отчётлив мыслеобраз, тем хуже он отражается в речи, и тем больше слов приходится произносить. Тем не менее, обмен мыслеобразами между людьми всё-таки возможен. Для этого, однако, нужно прикладывать усилия: разговаривающие люди должны "синхронизироваться", приложить некоторые усилия, чтобы думать приблизительно об одном и том же.

Когда мы говорим друг с другом, мы всегда говорим о чём-то. Когда мы разговариваем, мы сосредоточены на какой-то теме; мы из всей внеязыковой действительности (из данной нам в ощущениях действительности и из наших фантазий) выделяем лишь какую-то небольшую часть внеязыковых сущностей. Эта выделенная часть внеязыковой действительности, населённая интересующими нас внеязыковыми сущностями, называется "домен дискурса". Чтобы люди могли обмениваться мыслеобразами, нужно, чтобы они думали об одном и том же домене дискурса. Один человек передаёт другому человеку мыслеобраз, связывая его с языковой сущностью. Сущность из домена дискурса связывается с языковой сущностью посредством определения. Определение сущности X - это то, что для любой произвольно взятой сущности позволяет выяснить наверняка, является ли она сущностью X или же не является. Не любой набор слов может являться определением; как минимум, определения должны быть отчётливее определяемого. Сущности, используемые в определении, должны быть гораздо яснее и понятнее сущности, которая определяется.

Когда мы занимаемся математикой, мы говорим о сущностях из особого, математического домена дискурса - о математических объектах. Математические объекты не даны нам в ощущениях, их нельзя облизнуть или взвесить. Они скорее порождения нашего разума, чем что-то, существующее само по себе; скорее фантазии, чем что-то материальное. Эти сущности, однако, обладают некоторой устойчивостью, они достаточно конкретны, чтобы их можно было изучать, чтобы в их домене дискурса были возможны анализ и синтез - разложение объектов на составляющие и создание из имеющихся объектов новых сущностей. Не любая фантазия может этим похвастаться. Математические объекты отчётливы настолько, что даже могут быть использованы как детали абстрактных машин, моделирующих реальность. Однако всё-таки математические объекты обладают некоторой туманностью, непрозрачностью. Разговор о них должен потому быть очень точным.

Русский язык плохо подходит для разговора о математических объектах, потому что он позволяет делать слишком расплывчатые утверждения. И не только русский; английский, французский, немецкий - никакой из естественных языков не позволит нам достичь того уровня отчётливости, который нам требуется, чтобы давать понятные определения математическим объектам. Поэтому нам нужен некий искусственный язык, позволяющий рассуждать строго. Цена строгости - отказ от художественных средств. Искусственный язык, который мы будем использовать для математических определений, строг настолько, что в нём нет не только ни метафор, ни иронии, - в нём нет даже фонетики, слова этого языка непроизносимы. Однако этот искусственный язык всё-таки обладает грамматикой. В общем-то, ничего кроме грамматики в нём и нет, поэтому наш искусственный язык называется формальной грамматикой.

Чтобы начать пользоваться этим искусственным языком, его нужно полностью описать. Описывать наш искусственный язык мы будем на русском языке. Чтобы не запутаться, создаваемый искусственный язык мы будем называть иногда объектным языком, а тот язык, с помощью которого мы создаём искусственный язык, будем называть метаязыком. Довольно часто мы будем использовать выражение "интуитивный смысл" - использование этого выражения означает, что мы разъясняем смысл слов объектного языка на метаязыке, то есть по-русски объясняем, о каких сущностях домена дискурса идёт речь.

>>105195
Чтобы создать формальную грамматику, мы должны сперва ввести алфавит. Как правило, в алфавит использующихся в математике искусственных языков входят буквы латинского алфавита, возможно, снабжённые штрихами (то есть x и x''' - это две буквы, причём две разные буквы). Далее мы должны рассмотреть все возможные строки символов этого алфавита и выделить средь них те, которые являются правильными словами. Наконец, мы должны описать законы построения текстов из наших слов. Отклонения от наших правил мы запретим.

На самом деле существует уже довольно много формальных грамматик, отличающихся друг от друга какими-то деталями. Формальные грамматики, использующиеся в математике для определений, - это, как правило, формальные системы. А точнее, особая разновидность формальных систем: формальные логики.

Формальная система - это формальная грамматика, имеющая две особенности.

Во-первых, в ней слова разделены на два класса: на термы и на формулы. Термы, или, как иначе говорят, выражения, - это примерно то же самое, что собственные и нарицательные имена в русском языке. Например "Джон Доу" или "ондатр" - термы. Формулы, или соотношения - это примерно то же самое, что в русском языке утвердительные либо отрицательные предложения. Например "Джон Доу не есть ондатр" - формула. Как правило, никто не даёт исчерпывающего перечня термов и формул. Явно перечисляется лишь небольшое количество строк, про которые говорят, что они "атомарные" термы (формулы), а затем даётся правило проверки, которое позволяет для любой строки символов однозначно выяснить, является ли она термом (формулой) или же не является.

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

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

Теперь нужно сказать, что такое формальная логика.

Формальная логика - это формальная система особого вида. Во-первых, в её алфавит входит значок →, причём если A и B - формулы, то строчка символов A→B тоже является формулой. Во-вторых, среди её правил вывода есть Modus Ponens. Modus Ponens - это правило вывода, которое формулируется следующим образом: "Если записан текст, в котором есть формулы ``A`` и ``A→B``, то к этому тексту можно приписать формулу ``B``". Как правило, формальная логика содержит средства для описания операций "НЕ", "И" и "ИЛИ" - символы для этих операций и значок-стрелочка называются пропозициональными связками.

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

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

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

Квантификация - это операция, которую можно применять к предикату. Она превращает одну из его переменных букв в обычную букву. Технически это выглядит как запись перед формулой, соответствующей предикату, особого символа, квантора, и указание переменной, которую этот квантор связывает, - получается новая формула. На место переменной, которая связана квантором, уже нельзя свободно подставлять термы. По сути, приписывание квантора к предикату даёт нам уже другой, новый предикат, причём уменьшенной арности. Есть два классических квантора, ∀ и ∃. Первый называется квантором всеобщности. Интуитивно он выражает понятие "для всех", "для каждого". Суждение ∀xP(x) означает, что какой бы терм мы ни подставили на место буквы x в формулу, соответствующую предикатному символу P, получится истинное высказывание о сущностях домена дискурса. Второй называется квантором существования. Интуитивно он выражает понятие "существует", "найдётся хотя бы один". Суждение ∃xP(x) означает, что найдётся хотя бы один терм такой, что предикат P, которому в качестве аргумента подан этот терм, будет истинным. В некоторых вариантах логики предикатов бывают и другие кванторы. Наиболее популярным является квантор ∃!, "существует единственный". Предикаты, в которых все переменные связаны кванторами, в логике называются предложениями. Переменные предиката, которые не связаны квантором, называются свободными переменными, или параметрами.

Отдельно следует упомянуть понятие равенства. Равенство, описываемое значком =, может присутствовать в формальной логике, а может отсутствовать. В формальных логиках с равенством некоторые слова, - равные слова, - отождествляются, то есть полагаются взаимозаменяемыми. Логики с равенством являются более сложными объектами, чем логики без равенства. Как правило, равенство присутствует в логике.

Разные логики предикатов могут отличаться друг от друга алфавитами, наборами кванторов, некоторыми аксиомами и другими техническими деталями. Но они похожи друг на друга настолько, что очень часто можно говорить просто о логике предикатов, не утруждая себя дополнительными уточнениями. Логика предикатов, исчисление предикатов, логика первого порядка, язык первого порядка - всё это синонимы. В логике предикатов кванторами могут быть связаны только переменные. Существуют также логика второго порядка, в которой кванторами могут связываться не только переменные, но и предикаты, и даже бесконечное число логик высшего порядка, в которых кванторами может связываться всё больший зоопарк сущностей. Но эти логики используются сравнительно редко. Есть также логика нулевого порядка, известная также как исчисление высказываний; в этой логике используются только предикаты нулевой арности (о которых даже не говорят явно, что они предикаты), а кванторы не встречаются вовсе (нет смысла вводить кванторы, если нет предикатов с переменными). Логика последующего порядка содержит в себе логики всех предыдущих порядков. В частности, логика предикатов - это расширение логики высказываний.

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

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

Остаётся вопрос о внеязыковой действительности - что же такое математические объекты, какие сущности населяют математический домен дискурса. По официальной позиции математического сообщества внеязыковые сущности математического домена дискурса попросту отождествляются с репрезентующими их языковыми сущностями, то есть математические объекты - это просто бессмысленные строки символов. Образно говоря, Джон Доу есть строчка символов 'Д', 'ж', 'о', 'н', ' ', 'Д', 'о', 'у', записанных рядом друг с другом в таком порядке слева направо. Неофициальных точек зрения есть довольно много, часть из них требует обращения за ответом к нейробиологии и психологии. Я не имею желания публично подвергать сомнению официальную позицию.

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

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

Строка символов s называется кавайной, если:
1. s есть строка из букв "ня"
2. Если s есть строка вида "A-B", где буквы A и B обозначают кавайные строки.
3. Всякая кавайная строка получается конечным количеством применений правил 1 и 2.

Самоссылаемость в этом определении есть во второй и третьей строке; именно за счёт этой самоссылаемости множество кавайных строк и порождается. Например, кавайная строка "ня-ня-ня" может быть порождена так. Сначала порождается строка "ня" на основании пункта 1. Затем порождается строка "ня-ня" с помощью применения пункта 2 к строкам A=B="ня". Затем порождается строка "ня-ня-ня" с помощью применения пункта 2 к строкам A="ня" и B="ня-ня". А вот строка "иа-иа" не является кавайной. Ни с помощью первого, ни с помощью второго пункта символ "и" в строке не может возникнуть, а на основании пункта 3 других кавайных строк нет. Доказательства, основанные на использовании рекурсивных определений, называются индуктивными доказательствами, или доказательствами по индукции.

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

>>105196
Теперь уже можно начать разговор о, собственно, математике.

Как правило, деятельность математика - это доказательство теорем. В доказательстве теорем есть несколько тактик. Первая и самая очевидная тактика - это непосредственный, прямой вывод одного утверждения из другого. Этот способ опирается на так называемый силлогизм: если истинна формула A→B и если истинна формула B→C, то формула A→C истинна тоже. Чтобы доказать теорему, нужно просто придумать цепочку силлогизмов. К сожалению, эта тактика столь же малоэффективна, сколь и очевидна. Доказательство этим способом напоминает поиск пути через лабиринт, где на каждом шаге имеется бесконечно много способов пройти дальше.

Несколько более эффективная тактика - это апагогические доказательства, то есть доказательства от противного. Этот приём опирается на закон исключённого третьего: истинно либо A, либо не-A, и третьего не дано. Если мы докажем, что не-A ложно, то мы обязаны будем признать, что A истинно. Чтобы доказать, что не-A ложно, мы должны доказать, что не-A противоречит чему-либо из ранее доказанного. Чтобы сделать это, мы говорим "Предположим, что не-A истинно", и пытаемся вывести хоть одно какое-нибудь противоречие. Как только мы находим противоречие, мы заключаем, что наше предположение было ошибочным, не-A ложно и потому A истинно. Здесь есть подводный камень: мы не знаем заранее, истинно ли A. Может случиться так, что не-A истинно, и тогда все наши поиски противоречия будут тщетными.

Эти две тактики общие и используются повсеместно. Кроме них есть несколько приёмов, которые применимы не везде, но уверенно занимают свою нишу. О них в своё время.

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

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

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

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

Теперь нужно поговорить о понятии совокупности (синоним: множества, коллекции) сущностей.

Мы легко можем говорить о совокупности всех звёзд на небе, или совокупности всех рыб в Индийском океане, или всех букв во всех написанных книгах. Для этого нам достаточно бросить пару слов. Однако эта лёгкость обманчива, и из-за неё легко впасть в самопротиворечие. Например, рассмотрим некую совокупность книг, и потребуем, чтобы у каждой книги было название, причём название книги должно печататься не в самой книге, а в особой Книге Названий. Мы лишь тогда поймём, что наше требование противоречиво, когда задумаемся: где должно быть напечатано название Книги Названий? Таким образом, рассуждения о совокупностях следует вести не на естественном языке, а на языке некоторой формальной теории, который бы сделал невозможными такие противоречия.

Первые попытки построения теории совокупностей были предприняты в конце XIX века, ещё до появления идеи формальной системы. Колоссальный вклад в создание языка, подходящего для разговоров о совокупностях, внёс профессор Георг Кантор, и его имя широко известно до сих пор. Первые же шаги в этой области были очень успешны, теоретико-множественный язык проник во все области математики практически мгновенно. К сожалению, довольно скоро выяснилось, что этот язык всё ещё позволяет впадать в самопротиворечия и потому нуждается в доработке. Потребовалось пятьдесят лет, чтобы довести теорию множеств до удовлетворительного состояния. Работа над ключевыми понятиями остановилась лишь после начала второй мировой, но, по-видимому, могла продолжаться и дольше; впрочем, и так получилось неплохо.

Главная идея теории множеств в том, что одна сущность может являться "элементом" другой, или "точкой" другой. Это записывается с помощью значка ∈ - стилизованная греческая буква эпсилон, первая буква слова "ἐστί", "есть". Если буквой X мы обозначим совокупность всех звёзд на небе, то утверждение x∈X будет означать, что x есть звезда. Если буквой M мы обозначим совокупность всех людей, то утверждение m∈M будет означать, что m есть человек. Множествам, конечно, не запрещается быть элементами других множеств.

Мы будем пользоваться и значком ∈, и тремя другими его вариантами. Значком ∉, "не есть"; например, m ∉ M означает, что m не человек. Значком ∋, нужным для изменения порядка чтения; запись X∋x означает, что x∈X. И, наконец, его отрицанием, значком ∌; запись X∌x означает, что x∉X. Мы не будем выяснять подробнее, что же это значит - быть элементом. Потребуем только, чтобы для любых двух сущностей x и X обязательно выполнялся один и лишь один из случаев: либо x∈X, либо x∉X.

Если у множества существует хотя бы один элемент, то оно называется непустым. Если же множество не имеет элементов, то оно называется пустым. Не следует думать, что пустое множество - это какое-то неполноценное множество. Отнюдь, пустое множество ничем не хуже любого другого множества. У него даже есть собственное имя: пустое множество обозначается значком ∅.

Для множеств вводятся понятия равенства и части. А именно: два множества A и B равны, если они состоят из одних и тех же элементов, то есть для любого x утверждение x∈A равносильно утверждению x∈B. Множество A является частью, или подмножеством, множества B, если каждый элемент A является также и элементом B; это записывается как A⊂B. Если A⊂B, то говорят ещё, что B является надмножеством A, и записывают это как B⊃A. Подчеркну, что быть частью и быть элементом - это разные вещи. Утверждения A∈B и A⊂B несут разный смысл.

Как нетрудно видеть из языка предикатов, отрицанием формулы "для любого x из того, что x является элементом A, следует, что x является элементом B" является формула "существует такой x, что x является элементом A и не является элементом B". Отсюда вытекает, что пустое множество является частью любого другого множества. В самом деле, если бы пустое множество не являлось подмножеством некоторого множества B, то пустое множество содержало бы хотя бы один элемент. Но оно пустое.

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

Со множествами можно совершать разные операции. Например, результатом применения операции объединения ко множествам A и B будет множество, состоящее из тех и только тех элементов, которые принадлежат или A, или B, или обоим множествам сразу; оно обознчается как A∪B. Результатом применения операции пересечения ко множествам A и B будет множество, состоящее из тех и только тех элементов, которые принадлежат и A, и B; оно обозначается как A⋂B. Результатом применения операции разности ко множествам A и B (в таком порядке) будет множество, состоящее из тех и только тех элементов, которые принадлежат A и не принадлежат B; оно обозначается как A\B. Эти и другие операции традиционно иллюстрируются с помощью диаграмм Эйлера-Венна.

Теперь перед нами встаёт вопрос: как же определять совокупности? Мы могли бы потребовать, чтобы для любого высказывания существовало равнообъёмное ему множество, то есть множество удовлетворяющих ему объектов. Точнее, если P(x) - одноместный предикат, то должно существовать множество M такое, что x∈M эквивалентно истинности P(x). К примеру, если P(x) означает, что x является звездой, то должно существовать множество, состоящее из всех звёзд и только из них. Такое требование, оказывается, приводит к проблемам.

В самом деле, пусть Rsl(x) - предикат, который означает x∉x. То есть Rsl(x) истинно тогда и только тогда, когда x не является элементом самого себя. Пусть существует множество, равнообъёмное этому предикату, - то есть множество M такое, что x∈M ↔ Rsl(x). Спросим, истинно ли или же ложно Rsl(M)? Если Rsl(M) истинно, то M по равнообъёмности является элементом M, что по определению предиката Rsl означает, что M не является элементом M; если же Rsl(M) ложно, то M, опять-таки по равнообъёмности, не является элементом M, что по определению нашего предиката означает, что M является элементом M. В любом случае мы имеем противоречие. Это рассуждение носит имя "парадокс Рассела".

Итак, перед нами проблема: предположение, что для любого предиката есть равнообъёмное ему множество, ведёт к неустранимым противоречиям. Известно два способа преодолеть эту проблему.

Первый способ - мы можем явно перечислить, у каких предикатов есть равнообъёмные им множества, а про другие предикаты отказаться что-либо выяснять. Этим путём, как наиболее очевидным, люди пошли сразу же после открытия противоречивости ранней теории множеств. Первую версию аксиом сформулировал профессор Цермело (Zermelo), позднее перечень аксиом был дополнен профессором Френкелем (Fraenkel) и некоторыми другими людьми. Теория, полученная этим путём, называется ZFC.

Второй способ - предположить, что множества делятся на обычные и большие (разница между ними в том, что большие множества не могут являться элементами других множеств), и сказать, что всё-таки каждому предикату соответствует множество, просто множества, которые соответствуют некоторым предикатам, - большие. На этом втором пути вместо "обычное множество" и "большое множество" принято говорить "несобственный класс" и "собственный класс". Этот способ - тот подход, которым пользовался сам Кантор; Кантор выделял среди множеств некие "поистине бесконечные", или "запредельные" совокупности. Сам Кантор эту свою идею до конца не довёл, заслуга создания теории классов принадлежит фон Нейману, Бернайсу и Гёделю, по их именам формальная теория классов называется NBG.

Эти два способа не взаимоисключающие. Теория NBG расширяет теорию ZFC. Язык NBG богаче и выразительнее языка ZFC, при этом язык ZFC является частью языка NBG. Теорема, использующая лишь терминологию ZFC, может быть доказана в NBG тогда и только тогда, когда она может быть доказана в ZFC. Однако вопрос, какой теорией пользоваться, - ZFC или NBG, - всё-таки возникает.

Действующим консенсусом математического сообщества является теория ZFC. Однако де-факто большинство рассуждений давно уже проводятся в NBG, и революционно настроенные люди давно уже считают, что о ZFC пора перестать говорить. Тем не менее, язык NBG недостаточно выразителен, чтобы описать некоторые математические сущности, открытые после работ Цермело и фон Неймана. Такие сущности появляются, например, в теории категорий; так, в NBG нет средств, чтобы описать совокупность всех естественных преобразований функторов F и G между двумя большими категориями, тогда как символ Hom(F;G) для этой совокупности уже очень широко используется. В 1990 году в одной книжке про кошек появилось предложение ввести в язык теории множеств, наряду со множествами и классами, третье понятие - конгломерат, conglomerate. Элементами конгломерата могут быть как множества, так и классы. Но конгломерат не может быть элементом конгломерата. Конечно, сразу же возникает проблема с формализацией категории всех конгломератов - такая категория не будет сама конгломератом, поэтому такой путь не особо удовлетворителен. Есть более глубокая идея, которую предложил Гротендик: иерархия универсумов, или, иначе говоря, вселенных. Универсумы - это очень большие множества, но ещё не классы. Каждый универсум содержит достаточный запас сущностей, чтобы для практических целей почти не отличаться от класса всех множеств. И каждый универсум является элементом ещё большего универсума (тоже множества, не класса). Это красивая и, по-видимому, правильная идея. Однако очень плохо поддающаяся изучению. Так, ещё Маклейн отмечал, что ни он сам, ни его знакомые не могут сказать ничего о том, как соотносятся между собой категории в двух разных универсумах - хотя бы хорошо изученные, вроде категории колец.

Я буду разговаривать в основном о ZFC, однако пару слов об NBG я тоже скажу. Термами ZFC являются буквы латинского алфавита со штрихами. В ZFC есть лишь два вида атомарных формул: x=y и x∈y. Все остальные формулы получаются из атомарных с помощью логических связок "и", "или", "не", "следует", "эквивалентно", а также с помощью кванторов всеобщности и существования. Слово "множество" означает в точности "терм ZFC", внеязыковая интерпретация не вводится. Каждый объект ZFC является множеством - никакие объекты, не являющиеся множествами, в ZFC не рассматриваются.

>>105198
Итак, аксиомы ZFC. Они таковы.

1. Два множества равны тогда и только тогда, когда первое является частью второго, а второе - частью первого.
2. Для любых двух множеств, не обязательно различных, существует неупорядоченная пара.
3. Всякий одноместный предикат выделяет во всяком множестве подмножество.
4. Каким бы ни было семейство множеств, существует множество, являющееся объединением этого семейства.
5. Для любого множества существует булеан.
6. Существует индуктивное множество.
7. Относительно всякой логической функции, заданной формулой, у любого множества существует образ.
8. Каждое непустое семейство множеств - фундированное.
9. Для каждого непустого семейства множеств существует множество, пересекающееся с каждым множеством семейства в точности по одному элементу.

Аксиома 1 называется аксиомой объёмности, или аксиомой экстенсиональности. Эта аксиома - единственная аксиома из оригинальной теории Кантора, дожившая до наших дней в неизменном виде. Если в логике, с помощью которой формализуется теория множеств, нет понятия равенства, то эту аксиому можно принять в качестве определения равенства двух множеств, с некоторыми оговорками.

Аксиома 2, аксиома неупорядоченной пары, утверждает существование неупорядоченной пары в том числе и для двух равных множеств. В случае, когда a=b, неупорядоченной парой множеств a и b будет просто одноэлементное множество {a} (которое с тем же успехом можно записать как {b}). То есть из аксиомы пары следует, что для каждого множества x существует множество {x}.

Аксиома 3 называется аксиомой спецификации, или же аксиомой выделения подмножеств. Множество, которое выделено из множества M предикатом P(x), с помощью нотации фигурных скобок записывается как {m∈M; P(m)}.

Аксиома 6 называется аксиомой бесконечности. Дело в том, что индуктивное множество, существование которого гарантируется этой аксиомой, будет бесконечным. Что такое бесконечное множество, я определю ниже.

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

Аксиома 8 называется аксиомой регулярности или же аксиомой фундирования. Аксиомы 7 и 8 отсутствовали в аксиоматике, изначально предложенной Цермело, и были добавлены Френкелем ради того, чтобы с помощью теории Цермело можно было развивать теорию ординалов.

Аксиома 9 называется аксиомой выбора. О ней я тоже напишу подробнее.

Нам следует явно различать определение множества и доказательство существования этого множества. Чтобы пользоваться некоторым множеством, нам недостаточно определить его, нам ещё нужно доказать, что оно существует. Аксиомы Цермело-Френкеля дают нам способ доказывать, что для некоторых одноместных предикатов существуют равнообъёмные им множества. Однако же, мы не можем утверждать, что кроме тех множеств, существование которых мы можем доказать с помощью ZFC, никаких множеств нет; мы не можем утверждать и обратного. ZFC оставляет за границей рассмотрения вопрос о существовании тех множеств, существование которых не может быть доказано с помощью аксиом 1-9.

В частности, нам нужно доказать, что для любых двух множеств действительно существуют пересечение, разность и другие операции. Эти доказательства, впрочем, будут довольно простыми. Например, докажем, что для любых двух множеств A и B существует разность. Для этого рассмотрим предикат P(x): "x∈A и x∉B". Этот предикат выделяет подмножество в A∪B. Оно и будет разностью. Существование пересечения доказывается аналогично.

Чтобы доказать существование декартова произведения, нам сперва нужно уточнить понятие упорядоченной пары. Итак, пусть a и b - множества. По определению, которое дал в 1921 году профессор Куратовский, их упорядоченной парой называется множество {{a}, {a,b}}. Существование этого множества доказывается просто - достаточно несколько раз применить аксиому пары. Сложнее доказать то, что это множество действительно является упорядоченной парой. Для этого нужно перевести на объектный язык понятия "являться первой компонентой" и "являться второй компонентой". Переводятся они так. Множество x является первой компонентой множества Z, если для каждого элемента z из Z верно, что x∈z. Множество x является второй компонентой множества Z, если существует такое z из Z, что x∈z, и причём для любых z1 и z2 из Z верно, что если z1 ≠ z2, то x∉z1 или x∉z2. Эти определения нужны лишь для логической корректности, в реальной жизни непосредственно к ним обращаются крайне редко и используют понятие упорядоченной пары без всяких уточнений. Тем не менее, эти определения показывают, что упорядоченная пара действительно может быть определена лишь с использованием равенства и принадлежности (атомарных понятий теории множеств) и логических операций. Кроме классического определения Куратовского, существуют и другие определения упорядоченной пары.

Нетрудно проследить, что две упорядоченные пары равны тогда и только тогда, когда равны их соответствующие компоненты: утверждение "(a1, b1) = (a2, b2)" эквивалентно утверждению "a1=a2 и b1=b2". Это свойство (пары равны титтк равны компоненты) является характеристическим, им должна обладать любая конструкция, претендующая на право называться упорядоченной парой.

Теперь, располагая понятием упорядоченной пары, мы можем строго доказать существование декартова произведения для любых двух множеств. Пусть A и B - произвольные множества. Тогда, по аксиоме 4, существует объединение этих множеств A∪B. Тогда, по аксиоме 5, существуют оба множества ℘(A∪B) и ℘(℘(A∪B)) - булеан A∪B и булеан булеана. Тогда с помощью предиката P(x): "существуют такие a из A и b из B, что x=(a,b)" мы можем выделить в ℘(℘(A∪B)) множество в точности всех тех множеств, которые являются упорядоченными парами с первой компонентой из A и второй компонентой из B, - то есть выделить декартово произведение A и B. Это и завершает доказательство.

Это рассуждение справедливо только для декартова произведения двух множеств. Декартово произведение больше чем двух множеств определяется способом, отличным от этого. Дело в том, что мы желаем, чтобы декартово произведение обладало ассоциативностью, чтобы множество (A×B)×C можно было бы отождествить со множеством A×(B×C). Ясно, что это не удастся сделать при использовании нашего понятия декартова произведения двух множеств, поскольку множество (A×B)×C - это подмножество в ℘(℘( ℘(℘(A∪B))∪С )), а множество A×(B×C) - это подмножество в ℘(℘( A∪℘(℘(B∪С)) )), и чтобы ассоциативность выполнялась, мы должны каким-то образом отождествить эти множества; но в формальной теории множеств у нас нет способа отождествлять произвольные множества. Нам нужно какое-то иное определение декартова произведения, если мы хотим, чтобы ассоциативность выполнялась.

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

Пусть у нас есть два множества A и B, не обязательно различные. Мы доказали, что у нас есть их декартово произведение A×B. Продолжим развивать нашу терминологию. Отношениями сигнатуры <A;B> мы будем называть части множества A×B. Одним из одношений, в частности, будет пустое множество. Элементами отношений будут упорядоченные пары, понятно. Когда M является отношением, мы довольно часто вместо "(a, b) ∈ M" будем писать "aMb". Например, aφb означает, что упорядоченная пара (a, b) является элементом множества φ. Когда A=B=X, мы будем говорить об отношении на множестве X. Когда A1⊂A и B1⊂B, мы можем рассмотреть сужение отношения φ на множество A1×B1, рассмотрев те и только те пары в φ, первая компонента которых принадлежит A1, вторая - B1.

О всяком отношении можно думать как о множестве, равнообъёмном некоторому двуместному предикату. В самом деле, пусть M - отношение. Тогда оно определяет двуместный предикат P(x,y): утверждение P(a,b) истинно тогда и только тогда, когда упорядоченная пара (a, b) является элементом множества M. Это довольно интересно, так как позволяет считать, что некоторые предикаты, - тексты, по сути, - соответствуют объектам, множествам. Получается, что действия в логике, манипуляции строками символов, соответствуют действиям в теории множеств, манипуляциям некоторыми множествами. Из этого сопоставления вытекает интересная идея о геометризации логики. Некоторые люди, например Джет Неструев, воспринимают сопоставление предикату равнообъёмного ему множества как сопоставление алгебраическим, словесным действиям некоторых геометрических действий; фигурами в этой геометрии оказываются множества. Отсюда можно сделать много далекоидущих заключений, но нам интересен лишь один аспект этой безусловно богатой философской идеи: она обосновывает, что утверждения о множествах на языке диаграмм Эйлера-Венна ничуть не хуже, чем утверждения о множествах на языке логики предикатов, даже если забыть, что по диаграмме Эйлера однозначно восстанавливается строка символов формальной теории. А поскольку диаграммы Эйлера часто более наглядны, чем строки символов, эта идея защищает право диаграмм Эйлера на существование и полезна в дискуссии с изредка встречающимися людьми, которые по каким-то неведомым причинам стремятся изгнать диаграммы Эйлера из теории множеств.

Отношение M на множествах A и B называется полным слева, если для всякого элемента a из A существует хотя бы один элемент b из B такой, что пара (a,b) является элементом M. Аналогично определяется полнота справа.

Отношение M на множествах A и B называется функциональным, если для всякого элемента a из A из того, что две пары (a, b1) и (a, b2) являются элементами M, следует, что b1 = b2. Это почти такое же свойство функциональности, которое использовалось в формулировке функционального предиката. Предикат, который соответствует функциональному отношению, будет функциональным. Функциональное отношение служит для выражения идеи, что элементам из A соответствуют элементы из B. Свойство функциональности означает, что элементам множества A соответствует не больше одного элемента из B.

Полное слева функциональное отношение f на множествах A и B называется отображением из A в B, или, синоним, функцией из A в B. Записывается как f: A→B. Именем функции является именно буква f; хотя довольно часто функции записывают также с помощью символа f(x). Обозначение стрелочкой вошло в моду где-то в 1940 году, до этого стандартной была менее удачная нотация. Мы очень часто будем рассматривать множество всех функций между двумя данными множествами. Множество всех функций из A в B обозначается как B^A (B, "возведённое в степень" A).

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

Множество A называется доменом функции f, обозначается как dom(A). Множество B называется кодоменом функции f, обозначается как cod(f). Если пара (x, y) является элементом функции f, то под символом "f(x)" мы будем понимать "y"; таким образом, y = f(x). Если f(x) = y, то мы будем говорить, что y является образом элемента x при отображении f; элемент x мы будем в таком случае называть прообразом элемента y. Образ всегда только один, это гарантируется свойством функциональности. А вот прообразов может быть много; множество всех прообразов элемента y называется полным прообразом y.

Если f - функция из X в Y, то множество всех тех y из Y, у которых есть хотя бы один прообраз, мы будем называть образом функции f и обозначать как Im(f) или же как f(X); вообще, если M - подмножество домена, то f(M) есть множество образов элементов из M. Образ функции вовсе не обязан совпадать с кодоменом функции. В кодомене вполне могут оказаться элементы, которые не имеют ни одного прообраза.

Функции, у которых образ равен кодомену, мы будем называть сюръективными функциями, или сюръекциями. То есть если f: X→Y является сюръекцией, то у каждого элемента y из Y есть хотя бы один прообраз. Сюръекция - это полное справа отношение.

Функции, у которых каждый элемент кодомена имеет не более одного прообраза, мы будем называть инъективными функциями, или инъекциями. То есть если f: X→Y является инъекцией, то она разные элементы домена переводит в разные элементы кодомена. При этом случай, когда элемент кодомена не имеет ни одного прообраза, не исключается.

Бывают функции, которые не являются ни сюръекциями, ни инъекциями. Бывают сюръекции, которые не являются инъекциями; бывают инъекции, которые не являются сюръекциями. У них нет специальных названий. Но вот функции, которые являются и инъективными, и сюръективными, особое название имеют: они называются биекциями, или взаимно-однозначными отображениями. Понятие биекции чрезвычайно важно в теории кардинальных чисел и вообще в любой теории, где можно говорить об изоморфизмах.

Пусть f: X→Y и g: X→Y - две функции. Мы говорим, что они совпадают в точке x, если f(x) = g(x). Ясно, что две функции с одинаковыми доменами и кодоменами равны (как множества) тогда и только тогда, когда они совпадают во всех точках домена. Именно о совпадении во всех точках мы будем думать, когда будем что-то говорить про равенство двух функций.

Пусть X, Y, Z - три множества. Рассмотрим функции f : X→Y и g : Y→Z. Функцию h из X в Z такую, что h(x) = g(f(x)) для любого x из X мы будем называть композицией функций f и g, и записывать как g∘f или просто gf (буквы идут именно в таком порядке). Ясно, что композиция функций не коммутативна: f∘g не равно g∘f, вообще говоря. Зато композиция функций ассоциативна: для любых трёх функций f, g, h с подходящими доменами верно, что h∘(g∘f) = (h∘g)∘f. Ясно, что композиция инъекций инъективна, композиция сюръекий сюръективна, композиция биекций биективна. Ясно также, что каждую инъекцию можно считать биекцией домена на образ.

Пусть X - множество. Функцию из f: X→X мы будем называть тождественной на X и обозначать символом idX, если для каждого x из X верно, что f(x) = x. То есть функция, тождественная на X, сопоставляет каждому элементу этот же самый элемент. Для каждого множества существует тождественная функция.

Пусть X и Y - два множества. Пусть f: X→Y и g: Y→X - две функции. Мы будем говорить, что функция g является обратной для функции f (называемой "прямой" функцией), если g∘f = idX. То есть функция f сопоставляет элементу множества X некий элемент множества Y, а функция g сопоставляет элементу Y некий элемент из X; тогда композиция g∘f сопоставляет каждому элементу из X какой-то элемент опять из X; если при этом последнем сопоставлении каждый элемент из X сопоставляется сам себе, то тогда-то функция g и будет обратной для f. Довольно часто об обратных функциях мы будем говорить лишь тогда, когда образ прямой функции совпадает с кодоменом; если же образ прямой функции - собственная часть кодомена, мы обычно будем называть обратную функцию термином "сечение". Иными словами, если прямая функция прообразу сопоставляет его образ, то обратная функция образу сопоставляет его прообраз.

Справедлив чрезвычайно широко используемый критерий биекции: функция f: X→Y является биективной тогда и только тогда, когда существует функция g: Y→X такая, что f есть обратная для g и g есть обратная для f. Этот критерий можно принять за альтернативное определение биекции. На практике главным образом используется часть "только тогда": установив, что некие отображения взаимно обратны, исследователь тут же может утверждать, что они биективны.

Пусть есть функция f: X→Y, и пусть X1⊂X. Мы можем рассмотреть функцию f1 из X1 в Y, во всех точках множества X1 совпадающую с f. Мы будем говорить, что f1 является сужением функции f на множество X1; функция f является продолжением функции f1.

Пусть X - множество. Функции вида X×X→X мы будем называть операциями на множестве X. Понятие операции очень важно в алгебре. Алгебраической структурой называется набор данных, состоящий из множества и нескольких заданных на нём операций (иногда понятие операции немного расширяют).

Пусть I - какое-то множество, S - какое-то семейство множеств. Сюръективную функцию f: I→S мы будем называть индексированным семейством множеств; при этом множество I мы будем называть множеством индексов. Индексированное семейство - это функция. Каждое неиндексированное семейство мы легко можем рассмотреть как индексированное, для этого достаточно взять тождественное отображение. Как правило, мы будем говорить об индексированных семействах лишь тогда, когда множеством индексов является ординал. Теория ординалов рассмотрена ниже.

Пусть S - непустое семейство непустых множеств. Функцию f: S→∪S мы будем называть функцией выбора на семействе S, если для каждого s из S верно, что f(s) ∈ s. То есть функция выбора - это такая функция, которая каждому множеству семейства сопоставляет элемент этого самого множества. Функция выбора как бы выбирает, отмечает в каждом множестве из семейства один конкретный элемент. Забегая вперёд, скажу, что аксиому 9, аксиому выбора, можно переформулировать так: для каждого непустого семейства непустых множеств существует хотя бы одна функция выбора. Функцией выбора на индексированном семействе S с индексами I мы будем называть функцию из I в ∪S такую, что f(i)∈si для каждого i.

Сформулируем теперь определение декартова произведения произвольного индексированного семейства множеств. Декартовым произведением семейства множеств S, индексированного множеством I, называется множество всех функций выбора на семействе S. То есть множество всех функций из I в ∪S таких, что для каждого i из I верно, что f(i)∈si. Оно обозначается как ПS. Ясно, что это определение отличается от определения произведения ×, которое мы дали для двух множеств.

Замечу ещё, что пустое множество является функцией. Она имеет специальное название: пустая функция.

Функция - это, пожалуй, самое важное понятие теории множеств после понятия "множество". Конечно, функции служат для того, чтобы функциональные предикаты можно было бы изучать теоретико-множественными методами; но функции сами по себе являются множествами, и с функциями связано очень большое количество содержательных определений и теорем самой теории множеств. В математике функции используются повсюду, но, как правило, внутренней структурой функций интересуются лишь в теории множеств. Очень часто то, что я называю функцией, называют функциональным графиком, а функцию определяют иначе: как набор данных, упорядоченную тройку, состоящий из множества A, множества B и функционального графика сигнатуры <A;B>. Такой подход более изящен, но он опирается на метаязыковое понятие "набор данных" и не позволяет легко говорить о, например, множестве всех функций между двумя множествами, он требует произнесения некоторого количества дополнительных слов. Изящность этого подхода, например, в том, что в нём каждая функция обязана нести в себе информацию о кодомене. Ведь по функциональному графику (он ведь всего лишь множество пар) мы не можем восстановить информацию о кодомене функции, функциональный график несёт информацию только об образе, информацию о кодомене мы должны хранить где-то ещё.

>>105199
Вернёмся теперь к обычным отношениям. Мы определили, что такое свойство функциональности. Кроме функциональности, отношения могут обладать и другими свойствами. Итак, пусть φ - отношение на множестве X.

φ рефлексивно, если для любого x из X верно, что xφx.
φ симметрично, если для любых x, y из X из того, что xφy, вытекает, что yφx.
φ транзитивно, если для любых x, y, z из X из того, что xφy и yφz, вытекает, что xφz.
φ тотально, если для любых x, y из X верно, что xφy или yφx.

φ антирефлексивно, если для любого x из X неверно, что xφx.
φ антисимметрично, если для любых x, y из X из того, что xφy и yφx, вытекает, что x=y.
φ асимметрично, если для любых x, y из X неверно, что "xφy и yφx".

Отношение φ называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Отношение эквивалентности - это что-то вроде абстрактного равенства элементов. Рефлексивность значит, что каждый элемент эквивалентен сам себе. Симметричность означает, что если первый элемент эквивалентен второму, то и второй элемент эквивалентен первому. Транзитивность означает, что если первое эквивалентно второму, а второе - третьему, то первое и третье эквивалентны. Эквивалентностей бывает довольно много. Например, отношение "параллельность" на множестве всех прямых в плоскости является отношением эквивалентности.

Всякому отношению эквивалентности на каком-то множестве можно сопоставить одно-единственное разбиение этого множества на непересекающиеся классы: эквивалентные друг другу элементы образуют класс. Обратно, всякому разбиению множества на непересекающиеся классы можно сопоставить одно-единственное отношение эквивалентности: два элемента будут эквивалентными тогда и только тогда, когда они лежат в одном классе. Идея о разбиении множества на классы эквивалентности - это очень глубокая идея, встречающаяся не в одной только теории множеств, но и много где ещё.

Отношение φ называется отношением нестрогого частичного порядка, если оно рефлексивно, антисимметрично и транзитивно. Таковы, например, известные отношения ≤ и ≥ на множестве вещественных чисел. Важный пример нестрогого частичного порядка - это когда у нас есть множество M, и элементы ℘(M) упорядочены по включению, то есть xφy тогда и только тогда, когда x⊂y. Если отношение вдобавок тотально, то оно называется отношением линейного порядка. Тотальность означает, что любые два элемента сравнимы, что из любых двух элементов один больше другого. Бывают частично упорядоченные множества, в которых имеются несравнимые элементы. Например, таков булеан множества {1,2,3}; множества {1,2} и {2,3} несравнимы, ни одно из них не является подмножеством другого. Частично упорядоченные множества обычно называются ЧУМ или poset.

Отношение φ называется отношением строгого частичного порядка, если оно антирефлексивно и транзитивно. Таковы, например, отношения < и > на множестве вещественных чисел. Антирефлексивность означает, что ни для какого x не может случиться так, что x < x. Если это отношение вдобавок тотально, то оно называется отношением линейного порядка. Отношения линейного порядка обладают важным свойством. Для любых x и y выполняется один и только один из трёх вариантов: либо xφy, либо x=y, либо yφx. Это свойство называется трихотомией. Из антирефлексивности и транзитивности следует асимметричность (если есть такие x и y, что xφy и yφx, то по транзитивности xφx, что противоречит антирефлексивности). Асимметричность означает, что не бывает таких x и y, что x<y и y<x.

Если у нас есть отношение строгого порядка <, то мы всегда можем ввести по нему отношение нестрогого порядка: "x≤y" тогда и только тогда, когда "x<y или x=y". Обратно, по отношению нестрогого порядка ≤ мы всегда можем построить строгий порядок: "x<y" тогда и только тогда, когда "x≤y и x≠y". Поэтому мы можем позволить себе говорить просто об упорядоченных множествах; символ < всегда означает строгий порядок, ≤ - нестрогий. Ясно, что подмножество упорядоченного множества является, в свою очередь, упорядоченным множеством.

Пусть X - множество, упорядоченное отношением φ; пусть Y - множество, упорядоченное отношением ψ; пусть f - функция из X в Y.
Мы говорим, что f сохраняет порядок, если из того, что a φ b, следует, что f(a) ψ f(b).
Сохраняющую порядок биекцию мы называем порядковым изоморфизмом; сами множества мы называем порядково изоморфными.
Порядковый изоморфизм множества в себя мы назовём порядковым автоморфизмом.
Если φ и ψ являются отношениями строгого линейного порядка, то мы говорим, что функция f - строго монотонно возрастающая.

Пусть у нас есть упорядоченное множество M.

Элемент m называется максимальным, если для любого x из M неверно, что m < x.
Элемент m называется минимальным, если для любого x из M неверно, что x < m.
Элемент m называется наибольшим (синоним: последним), если для любого x из M верно, что x ≤ m.
Элемент m называется наименьшим (синоним: первым), если для любого x из M верно, что m ≤ x.

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

Пусть X - подмножество M.
Элемент m из M называется верхней гранью (синоним: мажорантой) множества X, если для каждого x из X верно, что x ≤ m.
Элемент m из M называется нижней гранью (синоним: минорантой) множества X, если для каждого x из X верно, что m ≤ x.
Наименьший элемент множества всех мажорант X называется "супремум X".
Наибольший элемент множества всех минорант X называется "инфимум X".
X называется ограниченным сверху, если у него есть хотя бы одна мажоранта.
X называется ограниченным снизу, если у него есть хотя бы одна миноранта.

Множество может быть ограниченным сверху, но не иметь супремума; может быть ограниченным снизу, но не иметь инфимума.

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

Упорядоченное множество X называется направленным, если для любых x, y из X существует такой z из X, что x≤z, y≤z.
Подмножество Y в упорядоченном множество X называется кофинальным (или конфинальным) множеству X, если для любого x из X существует такой y из Y, что x≤y.

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

В 1638 году Галилей опубликовал свою книгу "Две науки". В ней содержалось несколько диалогов, излагающих взгляды Галилея; диалоги вели персонажи по имени Симплицио и Сальвати. Между всем прочим, эти персонажи обсуждали идею бесконечного. Сальвати предложил Симплицио рассмотреть целые положительные числа. Некоторые из них, как известно, являются квадратами: например, 4 является квадратом 2, а 9 является квадратом 3. Однако же некоторые числа, например 17, не являются квадратом никакого целого числа. Поскольку целое больше своей части, следует думать, что чисел, являющихся квадратами, меньше, чем всех положительных целых чисел; это с одной стороны. С другой стороны, каждое число можно возвести в квадрат, а это означает, что целых чисел ровно столько же, сколько и всех квадратов; каждому положительному целому числу соответствует один определённый квадрат. Таким образом, говорил Сальвати, мы имеем противоречие: часть и меньше целого, и равна ему.

Это рассуждение известно как парадокс Галилея. Галилей считал свой парадокс свидетельством, что бесконечные множества непознаваемы. Но на самом деле это лишь кажущийся парадокс, связанный с недостаточной продуманностью понятия "больше". Если уточнить, что же означает понятие "больше", то парадокс исчезает. На самом деле Галилей открыл вовсе не парадокс: он открыл, что совокупность целых чисел может быть биективно отображена на своё собственное подмножество (забегая вперёд, скажу, что если между неким множеством и совокупностью целых чисел есть хотя бы одна биекция, то это множество называется счётным). Галилей не был первым, кто размышлял над идеей взаимно-однозначного соответствия между бесконечными множествами. За тысячи лет до него Аристотель размышлял об ободе колеса, который демонстрировал, казалось бы, противоречивые свойства. Тем не менее, лишь в конце XIX века люди перестали рассматривать существование биекций между всей совокупностью и некоторой её частью как что-то противоречивое. Среди всех учёных, рамышлявших над биекциями такого рода, дальше всех продвинулись Дедекинд и особенно Кантор. Кантор практически единолично определил ключевые понятия теории множеств. Он всего в нескольких публикациях сумел ввести основные понятия теории множеств, классифицировать бесконечности, создать теорию кардиналов и теорию ординалов, а также мимоходом изобрести теоретико-множественную топологию.

Философские идеи Кантора казались его современникам довольно туманными. Они даже в наши дни выглядят несколько размыто. Вот предположим прежде всего, что нам даны совокупности предметов, причём они даны нам в каком-то порядке. Чтобы исследовать эти совокупности, нужно уметь выделять в них какие-то общие черты. Ради этого нужно абстрагироваться от частностей.

Нашим первым актом абстрагирования будет отказ от исследования природы данных нам предметов и изучение только лишь того порядка, в котором они нам даны. После этого первого абстрагирования у нас от конкретного множества останется лишь его порядковый тип. Порядковый тип - это то общее, что имеют между собой одинаково упорядоченные множества. Порядковые типы разных множеств довольно сильно различаются между собой. Например, во множестве положительных целых чисел есть первый элемент: число 1. А вот во множестве всех вещественных чисел первого элемента нет. Или вот во множестве всех вещественных чисел между любыми двумя не равными друг другу числами имеется ещё бесконечно много других чисел, а во множестве целых чисел между двумя числами имеется только лишь конечное количество точек. Порядковых типов очень много; всё ещё слишком много, чтобы устанавливать о них теоремы. Чтобы начать развивать теорию порядковых типов, нужно ещё немного сузить границы рассматриваемого. Ограничимся рассмотрением типов вполне упорядоченных множеств. Такие порядковые типы называются ординалами.

А что будет, если мы позволим себе переупорядочивать элементы? Что, если мы совершим второй акт абстрагирования: забудем даже и о том, в каком порядке даны нам элементы множества? В таком случае от множества останется лишь его мощность: количество элементов, которое это множество содержало. Два множества имеют одну и ту же мощность, если между ними можно установить хотя бы одно взаимно-однозначное соответствие. Например, в рассуждении Галилея устанавливается взаимно-однозначное соответствие между целыми положительными числами и их квадратами; это значит, что два этих множества равномощны. Мощность - это то общее, что есть у равномощных друг другу множеств. Мощность множества есть некое особое, новое число: кардинальное число. Введение кардинальных чисел оправдано тем, что, оказывается, существуют разные бесконечности: имеются такие бесконечные множества, что между ними не существует ни одной биекции.

Теперь мы сосредоточимся на том, чтобы, пользуясь всеми введёнными ранее понятиями, изложить, что же всё-таки такое ординалы и кардиналы. Можно было бы убедиться, что отношение "быть порядково изоморфным" и "быть равномощным" - это отношения эквивалентности, и попросту объявить ординалами и кардиналами классы эквивалентности по этим отношениям. Проблема в том, что даже один-единственный класс всех равномощных друг другу множеств уже слишком велик, чтобы быть множеством. То есть при таком подходе ординалы и кардиналы не будут множествами и, стало быть, не будут постижимы средствами ZFC, а мы всё-таки хотим, чтобы ординалы и кардиналы были объектами, которые мы можем изучать. Поэтому мы будем следовать другому подходу, который развивали Цермело, Френкель и фон Нейман: создадим в качестве ординалов и кардиналов некоторые особо хорошие, избранные множества, и затем укажем способ, с помощью которого можно сопоставлять эти ординалы и кардиналы произвольным множествам.

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

Множество всех элементов вполне упорядоченного множества, меньших элемента x, называется начальным отрезком этого множества, заданным концом x.
Никакое вполне упорядоченное множество не изоморфно своему начальному отрезку. В противном случае конец отрезка был бы больше своего образа.

Докажем теперь, что единственный порядковый автоморфизм вполне упорядоченного множества - тождественное отображение. В самом деле, автоморфизм - возрастающая функция. Мы выяснили, что в таком случае каждый элемент меньше или равен своему образу. По свойству автоморфизма это означает, что прообраз каждого элемента больше или равен самому элементу. Отсюда применением отображения получаем, что каждый элемент больше или равен своему образу. Таким образом, верны два факта: каждый элемент и больше или равен своему образу, и меньше или равен своему образу. Это возможно лишь в том случае, когда каждый элемент равен своему образу.

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

Этой теории достаточно, чтобы доказать теорему. Пусть есть два вполне упорядоченных множества, назовём их X и Y. Тогда выполняется один и только один случай: либо они изоморфны, либо первое изоморфно начальному отрезку второго, либо второе изоморфно начальному отрезку первого.

Доказательство.

Определим отображение f, отображающее некое подмножество первого множества (возможно, пустое) во второе множество. Положим f(x) = y, если начальный отрезок первого множества с концом в x с помощью какого-нибудь изоморфизма изоморфен начальному отрезку второго множества с концом в y. Это определение могло бы быть некорректным: если бы начальный отрезок с концом в x был бы изоморфен двум разным начальным отрезкам второго множества, то мы бы получили, что x может отображаться в два разных элемента второго множества, то есть символ f(x) был бы неоднозначным. Однако в таком случае, так как один из двух этих отрезков является начальным отрезком другого, мы бы получили изоморфизм вполне упорядоченного множества на его начальный отрезок, чего не может быть. Так что определение отображения f корректно.

Похожим образом можно доказать, что отображение f инъективно - разные точки переходят в разные. Ибо если бы оно не было инъективно, то некие две разные точки переходили бы в одну, и некий начальный отрезок первого множества был бы изоморфен своему начальному отрезку.

Докажем, что отображение f сохраняет порядок. Рассмотрим два элемента из домена f, первый меньше второго. Назовём их x1 и x2, x1 < x2. Нам нужно доказать, что f(x1) < f(x2). Для этого заметим, что, по определению f, имеются некие изоморфизмы g и h, которые переводят отрезки первого множества, заданные элементами x1 и x2, в отрезки второго множества, заданные соответственно элементами f(x1) и f(x2). От противного предположим, что f(x2) ≤ f(x1). Тогда h∘g' будет изоморфизмом вполне упорядоченного множества, - отрезка, заданного элементом f(x1), - на свой начальный отрезок, что невозможно. Поэтому предлположение неверно, и f(x1) < f(x2).

Отображение f инъективно и сохраняет порядок. Поэтому оно является биекцией (домена на образ, но не обязательно биекцией X и Y, так как образ f может отличаться от Y), и, следовательно, f является изоморфизмом. С помощью этого факта докажем саму теорему.

Если домен f совпадает с X, а образ f совпадает с Y, то X и Y изоморфны с помощью отображения f. Это даёт нам первый случай.

Если домен f не совпадает с X, то множество X\dom(f) непусто, поэтому в нём есть наименьший элемент, обозначим его x. Предположим, что образ f не совпадает с Y. Множество Y\im(f) тоже непусто, и в нём тоже есть наименьший элемент, обозначим его y. Элемент x задаёт начальный отрезок множества X. На нём функция f определена, ибо x - наименьший из элементов, на которых f не определена. Элемент y, в свою очередь, задаёт начальный отрезок множества Y, причём этот начальный отрезок совпадает с образом f. Получается, что отображение f есть изоморфизм начального отрезка, заданного элементом x, на начальный отрезок, заданный элементом y. Но в таком случае, по определению f, отображение f должно быть определено в точке x и причём f(x) = y. Противоречие означает, что образ f совпадает со множеством Y, что даёт нам второй случай.

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

Все случаи разобраны, теорема доказана.

>>105206
Теперь применим общую теорию порядка к интересующей нас частной ситуации.

Множество называется транзитивным, если каждый его элемент является его подмножеством.
Ординалом назовём транзитивное множество, которое вполне упорядочено отношением ∈; то есть как бы a меньше b, если a∈b.

Ясно, что никакой ординал не является своим элементом, ибо если ординал a является своим элементом, то это означает, что a < a, но это противоречит тому, что порядок, который мы рассматриваем, - строгий.

Пустое множество - ординал. Это проверяется прямо по определениям.

Если a - ординал и b - элемент a, то b является множеством всех тех элементов множества a, которые меньше b. Это тривиальное замечание, поскольку отношение порядка у нас совпадает с отношением принадлежности и ординал - транзитивное множество.

Более того, если a - ординал и b - элемент a, то b - ординал. В самом деле, b является подмножеством a и потому вполне упорядочено. Если c - элемент b, то c является множеством всех элементов, меньших c, и, так как c меньше b, по транзитивности порядка c является подмножеством b. Поэтому b, в свою очередь, транзитивно.

Если a и b - два неравных ординала и b - подмножество a, то b - элемент a. В самом деле, пусть c - наименьший элемент множества a\b. Тогда b есть множество всех элементов, меньших c. Так как и c есть множество всех элементов, меньших c, то b=c.

Пусть a и b - два ординала. Пусть c - их пересечение. Ясно, что c является подмножеством и a, и b. Если c не равно ни a, ни b, то c является элементом и a, и b. Это означает, что c входит в пересечение a и b и потому является своим элементом. Поэтому либо c=a, и тогда a есть подмножество b, либо c=b, и тогда b есть подмножество a.

Отсюда вытекает, что объединение любого множества ординалов - снова ординал, называющийся супремумом этого множества; супремум S обозначается как sup S. В частности, объединение a и {a} тоже будет ординалом; мы назовём этот ординал последователем a (синоним: преемником a). Он обозначается suc(a), a', или, чаще всего, a+1. Ординал a+1 не является элементом a, - в противном случае a оказалось бы своим элементом. Сам ординал a мы будем называть предшественником.

Если воспользоваться понятием класса, то можно сделать ещё несколько утверждений.

Класс Ord всех ординалов линейно упорядочен с помощью отношения ∈. Этот класс не является множеством: если бы он был множеством, то существовало бы его объединение, которое, как и объединение всякого множества ординалов, было бы ординалом и поэтому имело бы последователя. Этот последователь оказался бы ординалом, который не является элементом множества всех ординалов, - противоречие. Эта теорема, - о том, что класс ординалов не есть множество, - принадлежит профессору Чезаре Бурали-Форти.

Следовательно, если некий класс ординалов является множеством, то он не может быть равен классу всех ординалов; для любого множества ординалов имеется не являющийся его элементом ординал.

Пересечение любого непустого класса C ординалов - ординал. Этот ординал называется точной нижней гранью класса C и обозначается inf C. В частности, любое непустое множество ординалов имеет точную нижнюю грань. Ординал a+1 является точной нижней гранью всех ординалов, больших a.

Если ординал b таков, что существует ординал a, для которого b = a+1, — то есть b является последователем a, — то ординал b называется successor ordinal, по-русски непредельным ординалом. Ординалы, которые не являются непредельными, называются предельными. То есть ординал b предельный, если он не является последователем никакого ординала.

Пустое множество иногда считают предельным ординалом, иногда нет; я предпочитаю считать. Наименьший ненулевой предельный ординал обозначается ω, омега. Ординалы, меньше ω, называются конечными ординалами. Ординалы, не являющиеся конечными, называются бесконечными ординалами. Множество натуральных чисел определяется как множество всех конечных ординалов. Число 0 определяется как пустое множество. Число 1 определяется как ординал {0}. Число 2 определяется как ординал {0,1}. Число 3 определяется как ординал {0, 1, 2}. И т.д.

Множество натуральных чисел можно определить независимо от теории ординалов. Для этого достаточно сделать некоторые из теорем о натуральных чисел аксиомами. Исторически аксиоматическое определение натуральных чисел с помощью аксиом предшествовало теории ординалов. Вот как это выглядит:

Натуральные числа - это множество N, на котором задана одноместная операция suc(n) : N->N. Их свойства таковы:
a. Множество N непусто: существует элемент 0∈N
b. Для любых n∈N и m∈N если suc(n) = suc(m), то m=n.
c. Не существует элемента n∈N такого, что 0 = suc(n).
d. Для любого подмножества M в N, если 0∈M и если для каждого m∈M верно suc(m)∈M, то M=N.
Свойство d называется аксиомой индукции; подробнее о нём ниже.

Эти аксиомы называются аксиомами Пеано, но первым, кто их сформулировал, был Дедекинд. Идею, что натуральные числа вообще могут быть аксиоматизированы, предложил Грассман.

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

Теорема. Любое вполне упорядоченное множество изоморфно одному и только одному ординалу.
Доказательство. Пусть M - вполне упорядоченное множество. Определим класс-отображение F с помощью формулы следующим образом. F(x,a) истинно тогда и только тогда, когда a - ординал, x - начальный отрезок M, и a изоморфен начальному отрезку M, заданному x. Если такое a существует, то оно единственно. По аксиоме замены, образ F - множество.
Предположим, что домен F не совпадает с M. Пусть m - наименьший элемент среди всех элементов M, не принадлежащих домену F. Элемент m задаёт начальный отрезок множества M, для которого нет изоморфного ему ординала. Каждой точке этого отрезка F сопоставляет ординал. Рассмотрев объединение множества этих ординалов, получим ординал, который изоморфен нашему начальному отрезку, вопреки выбору m. Значит, отображение F определено на всём M.
Ясно, что F сохраняет порядок. Это можно доказать таким же рассуждением, как и в теореме о вполне упорядоченных множествах. Поэтому F является изоморфизмом своего домена на свой образ.
Образ F - множество ординалов. Рассмотрим объединение этого множества. Оно будет ординалом - как раз тем нужным нам ординалом, изоморфным M. Изоморфизм осуществляется построенным нами отображением F.

Ординал, которому изоморфно вполне упорядоченное множество, называется порядковым типом этого множества.

>>105207
Теперь мы попытаемся понять, что же лежит по ту сторону бесконечности.

Функцию, доменом которой является конечный ординал n, - натуральное число, - мы назовём конечной последовательностью длины n. Функцию, доменом которой является ординал ω, мы назовём бесконечной счётной последовательностью.

Пусть у нас есть упорядоченное множество X. Пусть > - отношение, обратное отношению <, то есть строчка символов "b>a" означает, что "a<b". Пусть x0, x1, x2, x3, ... - счётная последовательность элементов X. Мы назовём эту последовательность убывающей счётной цепью, если x0 > x1 > x2 > x3 > ... . Аналогично определяются конечные цепочки. Мы говорим, что X удовлетворяет условию обрыва убывающих цепочек, если в нём не существует ни одной убывающей счётной цепи (конечные убывающие цепи могут быть).

В частности, если множество X упорядочено отношением ∈, то оно будет удовлетворять условию обрыва убывающих цепей, если в нём нет ни одной последовательности вида x0 ∋ x1 ∋ x2 ∋ ... Образно говоря, такие цепочки напоминают фантастическую идею о бесконечной вложенности материи: вселенная состоит из галактик, галактики состоят из звёздных систем, в них содержатся планеты, планеты состоят из атомов, атомы из субатомных частиц, а где-то глубоко внутри них начинаются новые вселенные, и так далее. Обрыв убывающих цепочек означает неверность идеи бесконечной вложенности применительно ко множеству, в котором цепочки обрываются.

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

Первый факт в том, что не существует убывающей последовательности множеств. В самом деле, предположим, что такая последовательность есть. Рассмотрим образ этой последовательности, - т.е. множество X = {x0, x1, x2, x3, ... }; то, что такое множество существует, гарантирует нам аксиома преобразования. Во множестве X должен быть элемент xn, не пересекающийся с X. Но это невозможно, потому что элементом xn является множество x(n+1), которое также является элементом X, и потому пересечение xn и X содержит хотя бы один элемент.

Второй факт в том, что никакое множество не является элементом самого себя. то есть нет такого X, что X∈X. Ибо если бы такое множество X существовало, то существовала бы необрывающаяся убывающая цепочка X ∋ X ∋ X ∋ ...

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

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

Последовательность, доменом которой является ординал a, называется последовательностью длины a, или нумерацией длины a, или строкой длины a. Если s - строка длины a, то значком s⌢x, или просто sx, мы будем называть последовательность длины a+1, которая на a совпадает с s и значением которой на a+1 является x. Мы будем называть s⌢x приписыванием, или дописыванием, к строке s элемента x.

Последовательность s длины a мы будем обозначать или как {sn, n<a}, или как s0, s1, s2, ... , sn, ... , n<a. Мы часто будем опускать скобки и обозначать s(n) как sn, где n - ординал, меньший чем a. Мы будем называть последовательность ординалов неубывающей, если из того, что a<b, следует, что sa ≤ sb; возрастающей, если из того, что a<b, следует, что sa < sb.

Пусть s - последовательность ординалов, a - некий предельный ординал. Мы определим предел последовательности si при индексе, стремящемся к a, как супремум множества всех элементов sn, где n < a. Обозначать его мы будем как lim i→a si.

Иногда мы будем рассматривать очень большие "последовательности", которые являются функциями на классе всех ординалов. Такие "последовательности" мы будем называть большими. Большую последовательность ординалов sn мы будем называть непрерывной, если для всякого предельного ординала a верно, что lim i→a si = a. Возрастающую непрерывную большую последовательность мы будем называть нормальной.

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

Теорема (трансфинитная индукция).
Пусть C - какой-то класс ординалов, обладающий тремя свойствами.
1. Пустое множество является элементом C.
2. C вместе с каждым ординалом a содержит его последователя, ординал a+1.
3. Если a - предельный ординал и если каждый из ординалов, меньших a, является элементом C, то и ординал a является элементом класса C.
Тогда C есть класс всех ординалов.

Доказательство.
Предположим, что C не есть класс всех ординалов. Тогда рассмотрим наименьший ординал a, не входящий в C. Он либо является пустым множеством, либо является последователем некоторого ординала, либо является предельным ординалом. И потому входит в C либо на основании 1, либо на основании 2, либо, - так как он наименьший из не входящих ординалов, - на основании 3.

Эта теорема позволяет доказывать утверждения с помощью трансфинитной индукции. Чтобы доказать, что утверждение P(w) истинно для любого ординала, достаточно доказать три свойства: что P(0) истинно; что если P(a) истинно, то P(a+1) истинно; что если a - предельный ординал и для каждого b<a утверждение P(b) истинно, то и для a утверждение P(a) истинно.

Трансфинитная индукция - чрезвычайно мощный способ доказательства теорем. Например, с её помощью легко можно доказать непротиворечивость арифметики (что и сделал в 1936 году доктор Генцен). Есть, однако, менее мощный и, в некотором смысле, более простой способ доказательства теорем: математическая индукция. Формулируется она так. Если P(x) - высказывание о натуральных числах, если P(0) истинно, если из того, что P(n) истинно, следует, что P(n+1) истинно, - то тогда это высказывание истинно для любого натурального числа. Математическая индукция - частный случай трансфинитной индукции. Хотя её можно доказать и независимо, если каким-либо образом доказано, что в каждом непустом множестве натуральных чисел есть наименьшее число.

С трансфинитной индукцией тесно связана трансфинитная рекурсия, позволяющая как бы конструировать математические объекты из цепочек предыдущих объектов (возможно, трансфинитных). Для этого рассматривается функция G, генератор, определённая на классе последовательностей. Предполагается, что для каждого ординала b существует единственная такая последовательность {x0, x1, x2, ... , xn, ... }, где n<b, что для каждого ординала a, меньшего b, объект xa равен G({xn; n<a}). То есть функция G как бы генерирует последовательность; она принимает на вход последовательность ранее сгенерированных элементов и доставляет очередной элемент в генерируемой последовательности.

За пределами теории множеств активно используется вот такое утверждение: если X - множество и a - ординал, то для каждой функции G, которая отображает множество всех последовательностей элементов из X длины меньшей чем a во множество X, существует единственная последовательность s длины a такая, что sb = G({sn; n < b}) для каждого ординала b < a. То есть как только мы задали на множестве X функцию, каждое последующее значение которой однозначно определяется последовательностью ранее сгенерированных элементов, - задали генератор, мы задали одну конкретную последовательность элементов X.

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

>>105210
С помощью трансфинитной рекурсии можно дать определение арифметическим операциям на ординалах.

1. Сложение ординалов. Пусть a - ординал.
a + 0 = a
a + (b+1) = (a+b)+1 - здесь под x+1 понимается последователь ординала x
a + b = sup{ a+c ; c<b } - если b является предельным ординалом

2. Умножение ординалов.
a × 0 = 0
a × (b+1) = a×b + a
a × b = sup{ a×c ; c<b } - если b является предельным ординалом

3. Возведение в степень.
a^0 = 1
a^(b+1) = a^b × a
a^b = sup{ a^c ; c<b } - если b является предельным ординалом

По индукции (трансфинитной) можно доказать, что операции сложения и умножения ассоциативны, то есть для любых трёх ординалов a,b,c верны равенства (a+b)+c = a+(b+c) и (a×b)×c = a×(b×c). Однако сложение и умножение ординалов, вообще говоря, некоммутативны (то есть не для всех ординалов a и b верно, что a+b=b+a, a×b=b×a).
Например: 1+ω = sup{ 1+n ; n<ω } = ω, и, как мы знаем, ω не равно ω+1. Пример для умножения есть вот такой: 2×ω = ω, но ω×2 = ω+ω, а ординалы ω и ω+ω - разные ординалы. Однако сложение и умножение конечных ординалов всё-таки коммутативно.

Ординал x такой, что x = ω^x, называется эпсилон-ординалом. Бывают разные эпсилон-ординалы. Наименьший эпсилон-ординал называется эпсилон-нулевое, обозначается ε0. Ординал ε0 - это довольно большой ординал. Он является супремумом множества {ω, ω^ω, ω^ω^ω, ω^ω^ω^ω, ... , }. Об ε0 можно думать как об ординале ω, который возведён в степень ω ровно ω раз. Однако как множество, - всякий ординал ведь является множеством, - ε0 является счётным. Чисел эпсилон бесконечно много, и даже запредельно бесконечно много: для всякого ординала x есть соответствующее εx. При этом εx является счётным тогда и только тогда, когда x счётно. В частности, ε(ε0) - счётно. Порядок у этих ординалов приблизительно такой: 0, 1, 2, 3, ... , ω, ω+1, ω+2, ω+3, ... , ω+ω = ω×2, ... , ω×3, ... , ω×4, ... , ω×ω = ω^2, ... , ω^3, ... , ω^ω, ... , ω^ω^ω, ... , ω^ω^ω^ω, ... , ε0, ... , ε1, ... Довольно много букв.
Ординал ε0 часто используется в логике. Например, доктор Генцен доказал непротиворечивость арифметики натуральных чисел именно с помощью индукции до ε0.

У арифметических операций на ординалах есть, в некотором смысле, геометрическое толкование.

Пусть A и B - два линейно упорядоченных непересекающихся множества.
Суммой A и B мы назовём множество A∪B, упорядоченное так: если p - элемент A, q - элемент B, то p<q; если же оба элемента принадлежат либо A, либо B, то порядок между ними таков же, как в A или, соответственно, в B.

То есть мы как бы берём две упорядоченных строки и записываем одну из них правее другой. То есть пусть A - множество нечётных натуральных чисел, B - множество чётных. Тогда суммой A и B будет множество натуральных чисел, упорядоченное как 1 < 3 < 5 < 7 < ... < 2 < 4 < 6 < 8 < ... , то есть в таком порядке каждое чётное число больше любого нечётного.

Произведением A и B мы назовём множество A×B (декартово произведение), упорядоченное так: пара (p;q) меньше пары (r;s) если и только если либо p<r, либо p=r и q<s. Такой порядок называется лексикографическим, или алфавитным. То есть мы рассматриваем элементы множеств как буквы двух разных алфавитов, составляем множество всех двубуквенных строк и упорядочиваем его так же, как упорядочивают словари - так и получается произведение.

Это вот геометрическое толкование можно использовать в качестве альтернативного определения сложения и умножения ординалов. Сделать это позволяет следующий факт: для любых двух ординалов a и b сумма a+b в смысле суммы ординалов изоморфно сумме a и b как упорядоченных множеств; произведение a×b в смысле произведения ординалов изоморфно произведению a и b как упорядоченных множеств. Под изоморфизмом понимается изоморфизм упорядоченных множеств, ведь всякий ординал - это упорядоченное множество. Доказывается этот факт с помощью трансфинитной индукции.

Геометрическое толкование позволяет придумывать наглядные модели для ординалов. Например, об ординале ω можно думать как о множестве натуральных чисел с обычным порядком. Об ординале ω+1 можно думать как о множестве натуральных чисел, в которое добавили какой-то конечный элемент, который больше любого натурального числа. Об ординале ω+2 - как о множестве натуральных чисел, к которому добавили два последних элемента, то есть о множестве вида 1 < 2 < 3 < ... < a < b. Об ординале ω+ω можно думать как о множестве натуральных чисел, в котором любое чётное число больше любого нечётного, т.е. 1 < 3 < 5 < 7 < ... < 2 < 4 < 6 < 8 < ...

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

Например, порядок в классе ординалов согласован с арифметическими операциями:
Если a < b, то a+c < b+c.
Если b<c и a>0, то a×b < a×c.
Если b<c и a>0, то a^b < a^c.

Ещё в классе ординалов можно определить операции вычитания и деления с остатком:

Если a < b, то существует единственное c такое, что a+c = b. Это c называется разностью ординалов b и a и обозначается как b-a.

Если a - произвольный ординал и b > 0, то существуют единственные ординалы c и p такие, что a = bc + p и причём p<b. Ординал p называется остатком от деления ординала a на ординал b.

Кроме того, имеет место левая дистрибутивность, a(b+c) = ab+ac. А вот правой дистрибутивностью обладают только конечные ординалы, умножение бесконечных ординалов, вообще говоря, не дистрибутивно справа, то есть равенство (a+b)c = ac+bc в случае ординалов мы не всегда имеем право писать. Аналогично с сокращением. Мы можем сокращать слева, - если ab=ac и a>0, то b=c, - но сокращать справа в общем случае нельзя. Кроме того, 0+a = a+0 = a, 0×a = a×0 = 0 , 1×a = a×1 = a. Также в классе ординалов нет делителей нуля, то есть если a×b = 0, то либо a=0, либо b=0.

Главная теорема арифметики ординалов - это теорема Кантора о нормальной форме.
Теорема. Каждый ординал a > 0 может быть представлен, и притом единственным образом, в виде a = ω^(b1) × k1 + ω^(b2) × k2 + ... + ω^(bn) × kn, где n - некоторое положительное натуральное число, k1, k2, ... , kn - некоторые положительные натуральные числа и b1, ... , bn - такие ординалы, что a ≥ b1 > b2 > ... > bn.

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

С помощью теоремы о нормальной форме можно развить теорию делимости в классе ординалов (что и сделал Серпинский в 1958 году). Ключевое понятие этой теории - разложение на простые множители. Ординал a называется простым, если он больше ординала 1 и если он не представим как произведение двух меньших ординалов.

С помощью аксиомы выбора арифметика ординалов может быть обогащена дополнительными операциями.

>>105211
Оригинальная теория Цермело позволяла доказать существование ординала ω. Точнее, аксиома бесконечности в формулировке Цермело просто постулировала существование этого ординала (в современной формулировке доказательство существования ординала ω получается из аксиомы о существовании индуктивного множества с помощью, например, аксиомы выделения подмножеств). Однако существование какого-нибудь другого предельного ординала с помощью оригинальной теории Цермело доказать было уже невозможно. Теория ординалов оставалась неохваченной теорией множеств. Поэтому-то понадобилась аксиома, - точнее, схема аксиом, - замены. С помощью этой аксиомы мы легко можем доказать существование всё новых и новых предельных ординалов. Например, докажем существование ω+ω. Каждому элементу n из множества ω = {0, 1, 2, 3, ... } мы можем сопоставить ординал ω+n. Аксиома замены гарантирует, что существует множество {ω+0, ω+1, ω+2, ω+3, ... }, а существование объединения этого множества, - оно и будет ординалом ω×2, - гарантируется аксиомой объединения. С помощью аксиомы замены мы можем также доказать существование ω×ω, ω^ω, ε-энтого и вообще по уже построенному ординалов мы можем строить всё большие, и большие, и большие ординалы; чем больше ординалов мы построили раньше, тем больший скачок мы совершаем очередным применением аксиомы замены.

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

Пусть у нас есть семейство M непустых множеств. Функция выбора на M - это такая функция f, определённая на M, что для всякого m∈M верно f(m)∈m. То есть функция выбора сопоставляет каждому множеству из семейства элемент этого множества. То есть функция выбора выбирает, отмечает в каждом множестве семейства один элемент.

Аксиома выбора. Каждое семейство непустых множеств имеет функцию выбора.
В такой формулировке аксиома выбора легко следует из аксиомы выбора в версии ZFC. В самом деле, пусть для каждого семейства непустых множеств существует множество, пересекающееся с каждым множеством семейства в точности по одному элементу. Тогда просто сопоставим множеству этот элемент, вот и получится функция. Ещё легче из этой формулировки вывести формулировку ZFC: достаточно каждому множеству семейства сопоставить элемент, который в нём выбирает функция, тогда по аксиоме замены совокупность этих элементов будет множеством.

Аксиома выбора имеет и другие формулировки - например, каждая сюръекция имеет сечение. Условие обрыва убывающих цепочек тоже эквивалентно аксиоме выбора.
Сечение функции f - это любая функция из кодомена f в домен f, сужение которой на образ f является функцией, обратной для f.

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

Теорема Цермело: любое множество может быть вполне упорядочено.
Доказательство. Пусть аксиома выбора верна. Рассмотрим произвольное множество M. Пусть некая функция выбора отмечает в каждом непустом подмножестве M точку. Часть множества M назовём хорошей, если она вполне упорядочена с помощью какого-то порядка, причём так, что концом любого её начального отрезка является именно тот элемент, который функция выбора отмечает в дополнении этого отрезка до M Рассмотрим две произвольные хорошие части. У них есть общий начальный отрезок, возможно, пустое множество. Предположим, что общий начальный отрезок отличается от обеих этих частей. Тогда его концом в обеих частях является один и тот же элемент (тот, который функция выбора отмечает в дополнении отрезка до M), но тогда этот элемент должен входить в общий отрезок. Следовательно, общий отрезок совпадает по крайней мере с одной из двух рассматриваемых хороших частей. То есть из любых двух хороших частей одна является начальным отрезком другой. Рассмотрим теперь объединение всех хороших частей. Для любых двух элементов объединения существует хорошее множество, содержащее оба этих элемента. В этом хорошем множестве один из двух элементов меньше другого; положим, что такое же отношение между этими элементами и в объединении. Введённый нами порядок на объединении будет не только линейным, но и полным, поскольку любая убывающая цепочка элементов объединения содержится в некотором хорошем множестве и потому обрывается. Более того, объединение будет хорошим множеством, ибо начальный отрезок объединения является начальным отрезком какого-то хорошего множества и потому имеет тот же конец. Если объединение всех хороших частей M отличается от самого M, то мы могли бы взять в его дополнении отмеченный элемент и добавить его к объединению, положив его больше любого другого элемента объединения. Получилась бы хорошая часть, не входящая в объединение всех хороших частей. Это абсурдно, поэтому объединение хороших частей совпадает с M, - то есть M вполне упорядочено.

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

Из теоремы Цермело можно вывести теорему Хаусдорфа.

Теорема Хаусдорфа: любая цепь содержится в некоторой максимальной цепи.
Доказательство. Рассмотрим частично упорядоченное множество и цепь в нём. Рассмотрим дополнение этой цепи. Если оно пусто, то цепь уже максимальная, и доказывать нечего. Пусть оно непусто. Мы можем считать его вполне упорядоченным. С помощью трансфинитной рекурсии определим в нём множество хороших элементов. Наименьший элемент дополнения мы назовём хорошим, если он сравним с каждым элементом рассматриваемой нами цепи. Любой другой элемент дополнения мы назовём хорошим, если он сравним со всеми элементами цепи и со всеми предшествующими ему хорошими элементами. Получим множество всех хороших элементов. Объединение этого множества и рассматриваемой цепи будет максимальной цепью, ибо если эта цепь не максимальна, то в неё можно добавить некий элемент, который будет из-за этого хорошим; но все хорошие элементы уже добавлены.

Из теоремы Цермело можно вывести лемму Цорна в формулировке Куратовского.

Лемма Куратовского-Цорна: если в частично упорядоченном множестве любая цепь мажорируется, то в нём есть максимальный элемент.
Доказательство. Если множество пусто, то доказывать нечего, в противном случае возьмём какую-нибудь одноэлементную цепь. Эта цепь содержится в максимальной цепи. Максимальная цепь, как и всякая цепь, мажорируется каким-то элементом. Этот элемент входит в максимальную цепь (ибо цепь максимальна) и притом является максимальным - если бы у него была мажоранта, то цепь не была бы максимальной.

Из леммы Цорна можно вывести аксиому выбора.

Теорема: для каждого множества существует функция, сопоставляющая каждой непустой его части элемент этой части.
Доказательство. Рассмотрим произвольное непустое множество M. Рассмотрим множество функций выбора, определённых на каком-либо семействе частей M; обращу внимание, что домен функции выбора - не подмножество M, но некоторое множество подмножеств M. Упорядочим множество функций выбора: первая функция меньше второй, если домен первой - часть домена второй, и если сужение второй функции на домен первой совпадает с первой функцией. Возьмём какую-нибудь цепь во множестве функций в смысле этого порядка. Объединив домены функций из этой цепи, получим семейство частей M; на этом семействе определим функцию выбора, объединив графики функций из цепи. Эта функция выбора по своему построению будет мажорантой цепи. Таким образом, по лемме Куратовского-Цорна во множестве функций выбора существует максимальная функция f. Предположим, что домен этой функции отличается от множества всех непустых частей M. Тогда есть непустая часть M, не входящая в домен. Доопеределив функцию f на этой части, войдём в противоречие с максимальностью f. Значит, f является функцией выбора на семействе всех непустых частей M.

Вместо аксиомы выбора иногда используются её более слабые формы.
Аксиома счётного выбора: каждое счётное семейство непустых множеств имеет функцию выбора. Этой аксиомы, как правило, достаточно для использования в математическом анализе.
Аксиома зависимого выбора: если E - отношение на непустом множестве M, и если для каждого a из M существует b из M такое, что aEb, то существует счётная последовательность a0, a1, a2, ... элементов M такая, что an E a(n+1) для каждого натурального n.

Аксиома выбора чрезвычайно важна для приложений. Например, без неё нельзя доказать, что любое бесконечное множество содержит счётное подмножество; нельзя доказать, что декартово произведение семейства непустых множеств непусто. Кроме того, аксиома выбора нужна, чтобы доказать эквивалентность классического определения бесконечных множеств и множеств, бесконечных в смысле Дедекинда.

Два множества называются равномощными, если между ними есть хотя бы одна биекция.
Если множество равномощно некоторому конечному ординалу (то есть натуральному числу n), то мы говорим, что это множество конечно и содержит n элементов.
Мы говорим, что множество бесконечно, если оно не является конечным. То есть множество бесконечно, если оно не равномощно никакому натуральному числу n.

Мы говорим, что множество счётно, если оно равномощно множеству натуральных чисел. Счётные множества - это как бы такие множества, которые можно "расположить в виде строки". Например, множество натуральных чисел 0, 1, 2, 3, ... счётно, множество являющихся целыми квадратами натуральных чисел 1, 4, 9, 16, ... счётно, множество целых отрицательных чисел -1, -2, -3, ... счётно, множество всех целых чисел 0, 1, -1, 2, -2, 3, -3, ... счётно.

Бесконечный ординал и его последователь равномощны. В самом деле, пусть X - бесконечный ординал, и Y = X∪{X} - его последователь. Так как X бесконечно, ординал ω является подмножеством X. Рассмотрим функцию f: X→Y, определённую так. Ординалу 0 сопоставим X, любому другому конечному ординалу x сопоставим ординал x+1, а все остальные ординалы оставим неподвижными. Легко видеть, что f - биекция.

Мы говорим, что мощность множества M меньше или равна мощности множества N, если есть хотя бы одна инъекция M в N. Мы говорим, что мощность множества M строго меньше мощности множества N, если есть хотя бы одна инъекция M в N, но нет ни одной биекции между M и N.

Лемма Кантора. Между множеством и его булеаном нет биекции.
Доказательство. Пусть M - множество. Предположим, что между ним и его булеаном есть биекция. Эта биекция сопоставляет произвольному элементу множества M некоторое подмножество M. То есть образами элементов M являются подмножества M. Мы назовём элемент множества M обычным, если он является элементом своего образа, и необычным в противном случае; всякий элемент M является либо обычным, либо необычным. Рассмотрим множество всех необычных элементов M. Оно является элементом булеана M и потому является образом некоторого элемента x из M. Каким является элемент x, обычным или необычным? Если x является обычным, то он должен быть элементом множества всех необычных элементов, то есть быть необычным; это невозможно. Если же x является необычным, то он должен быть элементом множества всех обычных элементов, а потому должен быть обычным; это тоже невозможно. Значит, рассматриваемой биекции нет.

Теорема Кантора. Мощность множества строго меньше мощности булеана этого множества.
Доказательство. Чтобы инъективно отобразить множество X в ℘(X), достаточно каждому x из X сопоставить множество {x}. А биекции между X и ℘(X) нет по лемме.

Из теоремы Кантора следует, что бывают разные бесконечности. Например, мощность ω строго меньше мощности ℘(ω).

В общем случае довольно сложно понять, есть ли между двумя множествами хотя бы одна биекция. Имеется, однако, инструмент, который несколько упрощает дело.

Теорема Кантора-Бернштейна. Пусть есть два множества. Если мощность первого меньше или равна мощности второго, а мощность второго меньше или равна мощности первого, то эти два множества равномощны.

Доказательство. Пусть f: A→B и g:B→A две инъекции. Требуется доказать, что есть биекция h: A→B.
Для всякого a из A его предшественником назовём такой b из B, что g(b) = a. Поскольку g инъективно, у каждого a не больше одного предшественника. Аналогично, для всякого b из B его предшественником назовём такой a из A, что f(a) = b. У элемента либо вообще нет предшественника, либо есть ровно один предшественник.
Для каждого a из A построим максимально возможную цепочку предшественников: a, g(b), f(a'), g(b''), ...
здесь g(b) = a, f(a') = b, g(b'') = a' и т.д. Весом элемента a назовём длину максимальной цепочки минус 1 (минус стоит для удобства). Если цепочка предшественников конечна, то её вес равен натуральному числу n. Если цепочка бесконечна, то её вес есть ω.
Пусть A0 - множество элементов A веса 0, ... An - множество элементов веса n, ... , Aω - множество элементов, имеющих бесконечные цепочки предшественников.
Аналогично определяются веса элементов B и множества B0, B1, ... , Bω.

Заметим, что между A0 и B1 есть биекция: элементу a из A0 соответствует элемент f(a). Это биекция, потому что у неё есть обратное отображение: элементу b' из B1 соответствует его прообраз. Этот прообраз лежит в A0, потому что вес b' равен 1.
Аналогично, между A1 и B0 есть биекция: элементу a' из A1 соответствует элемент b из B0 такой, что g(b) = a'.

Так же устроены биекции между A2 и B3, A3 и B2, и т.д. Таким образом, получаем биекцию между множеством элементов конечного веса в A и множеством элементов конечного веса в B. Осталось получить биекцию между Aω и Bω. Для этого заметим, что каждому элементу a из Aω соответствует один-единственный элемент b=f(a) из Bω. И у этого соответствия есть обратное отображение: каждый элемент b из Bω имеет предшественника a в Aω такого, что f(a) = b.

Итак, теорема доказана. Пикрелейтед.

Кардинал - это ординал, который не равномощен никакому меньшему ординалу. Все конечные ординалы - кардиналы. Это можно доказать с помощью математической индукции. Они называются конечными кардиналами. Бесконечные кардиналы - это кардиналы, не являющиеся конечными. Бесконечные кардиналы называются алефами. ω - наименьший бесконечный кардинал. Все бесконечные кардиналы - это предельные ординалы (но не все предельные ординалы - бесконечные кардиналы). В самом деле, если некий кардинал не является предельным, то он имеет предшественника; но ведь он равномощен своему предшественнику, следовательно, не является кардиналом.

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

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

Для любого ординала a существует кардинал, больший a. Он обозначается символом a⁺ (a с плюсиком) и называется кардинал-последователь ординала a. Следовательно, для каждого кардинала есть больший кардинал.
Доказательство. Рассмотрим функцию Хартогса H(x), заданную на классе всех множеств. Если x - множество, то числом Хартогса H(x) для x называется наименьший ординал a, для которого нет инъекции из a в x. Если M - множество, то класс всех полных порядков на частях M является множеством. Следовательно, класс ординалов, инъективно отображающихся в M, тоже является множеством. Но поскольку класс всех ординалов не является множеством, существуют ординалы, не отображающиеся инъективно в M. Следовательно, существует наименьший такой ординал. То есть число Хартогса существует для каждого множества M. Нетрудно видеть, что число Хартогса - кардинал. Определим a⁺ для ординала a как H(a).

Если у нас есть какое-то множество кардиналов, то супремум этого множества - кардинал.

Бесконечные кардиналы обозначаются с помощью символа ℵ. Каждому ординалу с помощью нижеследующего определения по трансфинитной рекурсии соответствует кардинал.
Символом ℵ₀ (алеф-нуль) обозначается ω.
Символом ℵ(a+1) обозначается кардинал-последователь кардинала ℵa, где a+1 - ординал-последователь ординала a.
Пусть a - предельный ординал, и для каждого ординала b, меньшего a, определён кардинал ℵb. Тогда символом ℵa обозначается супремум множества всех кардиналов ℵb, где b<a.

Кардинал ℵ(a+1) называется преемником (successor) кардинала ℵa, или, иначе, последователем.
Кардинал ℵλ, где λ - предельный ординал, называется предельным кардиналом.

Вдобавок к алефам можно ввести символы ωa. Мы положим ωa = ℵa; например, ω₀ = ℵ₀ = ω. Нужно заметить, что ординалы ωa - это очень большие ординалы. Ординал ω₁ уже несчётен, он больше даже эпсилон-нулевого.

Пусть a - ненулевой предельный ординал. Пусть b - другой предельный ординал, и пусть {an, n<b} - возрастающая трансфинитная последовательность длины b. Мы будем говорить, что последовательность {an} кофинальна в a, если предел этой последовательности при n->b равен a.
Пусть a - ненулевой предельный ординал. Пусть A - подмножество a. Мы будем говорить, что A кофинально в a, если супремум A равен a.
Пусть a - бесконечный предельный ординал. Кофинальность a - наименьший предельный ординал b такой, что существует последовательность длины b, кофинальная a.
То есть кофинальность a - это наименьшая из мощностей всех тех множеств, которые кофинальны a.
По-русски почему-то принято говорить "конфинальная последовательность", "конфинальное множество", "конфинальность".

Кофинальность a - предельный ординал. Он обозначается cf(a). В случаях, когда это не ведёт к неточностям, скобки можно опускать и писать cf a. Ясно, что cf a меньше или равна a.
Можно доказать, что cf (cf a) = cf a.
Если a - ненулевой предельный ординал и A - подмножество a, кофинальное a, то порядковый тип A больше или равен cf A.
Если предел некоторой неубывающей c-последовательности элементов a равен a, то cf a = cf a.
Бесконечный кардинал ℵa называется регулярным, если он равен своей кофинальности. Он называется сингулярным, если больше своей кофинальности.
Кофинальность каждого предельного ординала - регулярный кардинал.

Прежде чем строить теорию кардиналов дальше, вернёмся ненадолго к классу всех ординалов. Класс Ord×Ord всех упорядоченных пар ординалов вполне упорядочен с помощью следующего порядка: (a,b) < (p,q) тогда и только тогда, когда или max{a,b} < max{p,q}, или max{a,b} = max{p,q} и a<p, или max{a,b} = max{p,q} и a=p и b<q.
Можно доказать, что это отношение (обобщение алфавитного порядка) действительно является полным порядком на Ord×Ord, достаточно погуглить по словам the canonical well-ordering on pairs of ordinals. Если мы обозначим как Г(x,y) порядковый тип множества всех пар (a,b), меньших чем (x,y) в смысле этого порядка, то установим биекцию из Ord×Ord в Ord. Более того, (a,b)<(p,q) тогда и только тогда, когда Г(a,b)<Г(p,q). Отсюда можно вывести, что Г(ω,ω) = ω и, более того, что для любого ординала a Г(ωa, ωa) = ωa.

В классе кардиналов можно ввести арифметические операции, с помощью геометрического определения.
Пусть m и n - два кардинала. Пусть A - какое-нибудь множество мощности m, B - какое-нибудь множество мощности n, и пусть A и B не пересекаются.

Положим, что
m+n = card(A∪B)
m×n = card(A×B)
m^n = card(A^B)
Здесь A×B - декартово произведение, A^B - множество всех функций из B в A.

Чтобы эти слова можно было бы принять в качестве корректного определения, нужно, чтобы определяемые объекты определялись однозначно - чтобы выбор A и B мог быть произвольным. Поэтому нужно доказать независимость определения от выбора A и B. Но это делается тривиальным повторением определений.

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

Лемма (о мощности булеана). Если card(A) = m, то card(P(A)) = 2^m.
Чтобы доказать эту лемму, построим биекцию между множеством P(A), - множеством всех подмножеств A, - и множеством всех функций из A в 2 = {0, 1}.
То есть нам нужно каждому подмножеству A сопоставить одну-единственную функцию из A в {0,1}.
Сделаем мы это так. Пусть M - произвольное подмножество A. Пусть χM - функция из A в {0,1} такая, что χM(a) равна 1 тогда и только тогда, когда a является элементом M. Такая функция называется характеристической функцией множества M, или, иначе говоря, индикатором множества M. Из определений ясно, что отображение, которое каждому множеству сопоставляет его индикатор, будет биекцией.

С помощью этой леммы теорема Кантора о том, что множество не равномощно своему подмножеству, быть переформулирована в терминах кардиналов следующим образом: для каждого кардинала m верно, что m < 2^m.

В классе кардиналов операции + и × не только ассоциативны, но ещё и коммутативны и дистрибутивны. Кроме того, верны следующие утверждения:
(a×b)^c = a^c × b^c ; a^(b+c) = a^b × a^c ; (a^b)^c = a^(b×c) ; если a≤b, то a^c ≤ b^c ; если 0 < a ≤ b, то c^a ≤ c^b ; a^0 = 1 ; 1^a = 1 ; 0^a = 0; для любых кардиналов a,b,c.

Теорема. Из вполне-упорядочивания на Ord×Ord следует, что ℵa + ℵb = ℵa × ℵb = max{ℵa, ℵb} для каждых ординалов a и b.

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

Главное замечание здесь - из того, что всякое множество может быть вполне упорядочено, следует, что мощность каждого бесконечного множества является алефом. Поэтому в присутствии аксиомы выбора (как это имеет место в ZFC) теория мощности сводится к теории алефов. Сложение и умножение кардиналов существенно упрощаются: пусть a и b два кардинала, тогда они являются алефами и потому a+b = a×b = max{a,b}. Зато интересные вещи происходят с возведением в степень.

Лемма. Пусть a и b - два кардинала, причём b - бесконечный. Если 2 ≤ a ≤ b, то a^b = 2^b.
Доказательство. Мы будем использовать утверждения об арифметике кардиналов.
2^b ≤ a^b ≤ (2^a)^b = 2^(a×b) = 2^b. Вот и всё.

Пусть {ai} - семейство кардиналов, индексированное множеством I. Пусть {Xi} - семейство попарно непересекающихся множеств, индексированное тем же самым множеством индексов, причём card(Xi) = ai.

Определим сумму семейства кардиналов {ai} как мощность объединения семейства {Xi}. Будем обозначать эту сумму как Σai.
Определим произведение семейства кардиналов {ai} как мощность декартова произведения ПX семейства {Xi}. Будем обозначать это произведение как Πai.

Теорема Кёнига. Пусть {ai} и {bi} - два семейства кардиналов, индексированные одним и тем же множеством, причём для каждого i верно, что ai < bi. Тогда Σai < Πbi.

Формулировка этой теоремы довольно проста, но из неё следует много любопытных следствий.

Следствие 1. a < 2^a для любого a.
Доказательство. По теореме Кёнига, 1+1+1+... (a раз) строго меньше чем 2×2×2×... (a раз).
Следствие 2. cf(2^ℵa) > ℵa.
Следствие 3. cf(ℵa ^ ℵb) > ℵb.
Следствие 4. a < a^cf(a) для каждого бесконечного кардинала a.

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

Теорема (Кантор). Множество Bin всех счётных последовательностей из нулей и единиц несчётно.
Доказательство. Приём доказательства, которым мы воспользуемся, называется диагональный метод Кантора. Для удобства речи будем считать, что натуральные числа начинаются с единицы.
Предположим, что мы установили биекцию f между множеством натуральных чисел и множеством всех последовательностей из 0 и 1, то есть каждой последовательности сопоставили её номер, и по каждому номеру нам известна последовательность. Определим последовательность x следующим образом. Если в последовательности номер 1 первым элементом является число 0, то первым элементом последовательности x положим число 1; если же первым элементом последовательности номер один является число 1, то первым элементом описываемой нами последовательности x положим число 0. Аналогично для каждого натурального n: если в последовательности номер n на n-м месте стоит 0, то в x на n-м месте поставим 1, а иначе поставим 0. Поскольку мы перенумеровали все последовательности, у последовательности x тоже есть какой-то номер m. Но последовательность x отличается от последовательности номер m, у них m-ые элементы не равны. Противоречие означает, что биекции нет.

Следствие 1. Множество всех подмножеств натуральных чисел несчётно. Иными словами, 2^ℵ₀ > ℵ₀
Доказательство. Рассмотрим множество натуральных чисел N. Каждому подмножеству сопоставим его характеристическую функцию, получим биекцию между 2^N и ℘(N). Применим нашу теорему.

Следствие 2. Множество R всех вещественных чисел несчётно.
Доказательство. Запишем каждое вещественное число в системе счисления по основанию 2, по теореме Кантора-Бернштейна-Шрёдера получим биекцию между R и Bin (теоремой К.-Б.-Ш. нужно пользоваться потому, что две разные последовательности нулей и единиц могут быть именами одного и того же вещественного числа, например 0.1111... = 1.0000... ). Применим нашу теорему.

В ходе доказательства следствий мы получили биекции между R и Bin и 2^ℵ0 и Bin. Поэтому R и 2^ℵ0 равномощны. Мощность множества всех вещественных чисел называется континуум и обозначается готической буквой c. Кардинал c - это какой-то кардинал. Но какой?

Ясно, что c больше или равен ℵ1. Логично предположить, что с - это и есть ℵ1, ведь откуда могут взяться бесконечные множества, лежащие между натуральными и вещественными числами? Предположение, что c = ℵ1, называется континуум-гипотезой, обозначается CH. Кантор выдвинул эту гипотезу в 1877 году. У Кантора, однако, не получилось ни доказать эту гипотезу, ни опровергнуть её. И не только у Кантора; континуум-гипотеза долгое время не поддавалась никому. В 1900 году Гильберт включил континуум-гипотезу в свой известный список самых интригующих открытых математических проблем. В 1940 году Курт Гёдель сумел доказать, что ни с помощью ZF, ни с помощью ZFC континуум-гипотезу нельзя опровергнуть; в 1963 году профессор Пол Коэн открыл, что континуум-гипотезу в ZFC нельзя и доказать. Континуум-гипотеза стала первой в череде гипотез, которые интересны и содержательны, но о которых в ZFC нельзя сказать ничего.

Континуум-гипотеза имеет более сильную версию: обобщённую континуум-гипотезу, GCH. Звучит она так: равенство 2^ℵa = ℵ(a+1) верно для каждого ординала a. GCH тоже независима от ZFC.

Континуум-гипотезу нельзя доказать в ZFC, однако идея, что последующий кардинал равен мощности предыдущего кардинала, всё-таки красивая. Если её нельзя выразить с помощью алефов, то почему бы не взять следующую букву еврейского алфавита? Давайте определим числа бет по рекурсии.
ℶ₀ = ℵ₀. ℶ(a+1) = 2^ℵa, если a непредельный ординал. ℶa = sup{ℶb; b<a}, если a - предельный ординал.
Обобщённая континуум-гипотеза переформулируется в этом случае так: для любого ординала a верно равенство алеф-a и бет-a.

Если принять GCH, то будут верны следующие равенства.
1. Если a ≤ b, то a^b = b⁺
2. Если cf a ≤ b < a, то a^b = a⁺.
3. Если b < cf a, то a^b = a.

Кроме того, мы можем рассмотреть функцию гимель: ℷ(x) = x^ cf x. Она пригодится для определения некоторых других объектов и гипотез.

Кардинал a называется сильным предельным кардиналом, если 2^b < a для каждого b < a. Алеф-нуль - сильный предельный, например.
Понятно, что сильный предельный кардинал - это предельный кардинал. Если GHC принята, то каждый предельный кардинал - сильный предельный.
Если a - сильный предельный кардинал, то 2^a = ℷ(a).

Кардинал называется слабо недостижимым, если он несчётный, регулярный и предельный. Кардинал называется сильно недостижимым, если он несчётный, регулярный и сильно предельный. Каждый сильно недостижимый кардинал является слабо недостижимым. Если GCH верна, то каждый слабо недостижимый кардинал - сильно недостижимый. Недостижимые кардиналы называются так потому, что их существование не может быть доказано с помощью обычных теоретико-множественных операций и даже с помощью аксиомы замены. Более того, утверждение о существовании хотя бы одного недостижимого кардинала равносильно утверждению о непротиворечивости ZFC. По сути, алеф-нулевой является недостижимым кардиналом для конечных кардиналов; недостижимые кардиналы относятся к обычным кардиналам так же, как алеф-нулевое относится к конечным кардиналам. Недостижимые кардиналы - это первый шаг в область, которая лежит дальше, чем запредельное. Наука об этой области бесконечного называется изучением больших кардиналов; кроме недостижимых кардиналов, есть и другие большие кардиналы. Недостижимые кардиналы появились в теории множеств довольно рано, о слабо недостижимых кардиналах размышлял ещё Хаусдорф в 1908 году. Тем не менее, в современной формулировке недостижимые кардиналы были введены Серпинским и Тарским в 1930-е.

Имеется связанная с большими кардиналами гипотеза сингулярных кардиналов, singular cardinal hypothesis.
SCH: для каждого сингулярного кардинала a если 2^cf a < a, то a^ cf a = a⁺.
SCH следует из GCH и независима от ZFC. Если большие кардиналы существуют, то SCH неверна.

Вернёмся, впрочем, в область маленьких бесконечностей.

С помощью арифметики кардиналов легко доказать, что множества всех последовательностей натуральных чисел и даже всех последовательностей вещественных чисел имеют мощность c. Ибо ℵ0^ℵ0 = (2^ℵ0)^ℵ0 = 2^(ℵ0×ℵ0) = 2^ℵ0. Кроме того, множество всех комплексных чисел, - которое равномощно множеству всех пар вещественных чисел, - тоже имеет мощность континуума, ибо 2^ℵ0 × 2^ℵ0 = 2^ℵ0. Множество рациональных чисел счётно, так как каждое рациональное число можно сопоставить единственной несократимой дроби с целым числителем и натуральным знаменателем, а мощность произведения множества целых чисел на множество натуральных чисел счётна.

Как известно, множество вещественных чисел упорядочено. Этот порядок является линейным, но не является полным: например, во множестве всех вещественных чисел нет наименьшего числа. Вообще, множество вещественных чисел неограничено: в нём нет ни наибольшего, ни наименьшего элемента. Порядок на R является плотным (между неравными числами можно вставить число, то есть если a<b, то существует такое c, что a<c<b). Более того, множество рациональных чисел плотно в R: между неравными вещественными можно вставить рациональное. А ещё порядок на R является непрерывным: непустая ограниченная сверху часть R имеет супремум, непустая ограниченная снизу часть R имеет инфимум. Непрерывный порядок по-русски иногда называют полным (по-английски он complete); не нужно путать это со вполне упорядоченным множеством (well-ordered set).

Есть пара известных теорем о плотных множествах; обе они принадлежат Кантору.

Теорема 1. Любые два счётные плотные неограниченные линейно упорядоченные множества изоморфны.
Теорема доказывается методом, который называется https://en.wikipedia.org/wiki/Back-and-forth_method

Теорема 2. R со стандартным порядком является единственным линейно непрерывно упорядоченным множеством, которое содержит плотное счётное подмножество, порядково изоморфное множеству рациональных чисел.
Доказательство. Возьмём два множества X и X', удовлетворяющих условию теоремы. Между их счётными плотными подмножествами P и P' есть изоморфизм f. Он может быть единственным образом продолжен до изоморфизма F между самими множествами: достаточно за образ точки из первого множества принять точную верхнюю грань образов точек плотного множества, которые меньше неё. То есть F(x) = sup{f(p); p≤x и p∈P}. Единственность проверяется элементарно.

Некоторую дополнительную информацию об упорядоченном множестве можно извлечь, рассмотрев множество сечений в нём. Сечение - это разбиение линейно упорядоченного множества на две части, нижний класс и верхний класс, так, чтобы любой элемент нижнего класса был меньше любого элемента верхнего класса; иногда налагают дополнительные требования. Иногда множество всех таких сечений может сказать что-то полезное и о самом множестве. Например, классическая конструкция множества вещественных чисел, предложенная Дедекиндом, - это множество всех сечений рациональных чисел. Каждое вещественное число отождествляется с некоторым сечением. Арифметические операции и предельный переход на R вводятся, опять-таки, с помощью сечений. Подробнее об этом написано почти в любом учебнике анализа.

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

В R открытым интервалом (a;b), где a<b, называется множество таких чисел x, что a < x < b. Поскольку Q плотно в R, каждый открытый интервал содержит хотя бы одно рациональное число. А поскольку Q счётно, любое семейство попарно не пересекающихся открытых интервалов R либо конечно, либо счётно.
Пусть теперь M - произвольное плотное линейно упорядоченное множество. Если любое семейство попарно не пересекающихся открытых интервалов в M не более чем счётно, то мы говорим, что M удовлетворяет условию счётности цепей, или условию Суслина.

Гипотеза Суслина, SH: пусть непрерывное плотное неограниченное линейно упорядоченное множество удовлетворяет счётности цепей, тогда оно порядково изоморфно R.
Контрпример к гипотезе Суслина - множество, обладающее такими свойствами, но не изоморфное R - называется суслинской линией, или континуумом Суслина. Гипотеза Суслина в том, что суслинских линий нет. Континуум Суслина обладает в некотором смысле пугающими свойствами, и, более того, даже порождает небольшой зоопарк из противоестественных объектов, поэтому вполне объяснимо желание доказать несуществование линий Суслина. Однако как показали в 1967-1971 годах Йех, Тенненбаум и Соловэй, гипотезу Суслина нельзя ни доказать, ни опровергнуть в ZFC. Для доказательства неопровержимости гипотезы эти учёные брали множество, подходящее под условия гипотезы Суслина, некоторым образом выращивали из него так называемое дерево Суслина и небольшой переделкой превращали дерево Суслина в континуум Суслина. Для доказательства недоказуемости гипотезы они изобрели способ убивать деревья Суслина; единожды убитое дерево становилось мёртвым. С помощью некоторой продвинутой версии коэновского метода форсинга, они в некотором запредельно-бесконечном процессе умертвили все деревья Суслина и показали таким образом, что суслинская линия не вырастет из множества.

На множестве вещественных чисел, как известно, можно ввести стандартную топологию. В ближайших нескольких абзацах мы будем работать с ней. Известно, что R является пространством сепарабельным (содержит счётное плотное подмножество, а именно рациональные числа) и полным (всякая последовательность Коши имеет предел). Подмножество M множества R называется открытым, если из того, что точка x является элементом M, следует, что имеются такие числа a и b, что a<x<b и интервал (a;b) есть часть M. Множество называется замкнутым, если его дополнение открыто. Объединение любого семейства открытых множеств открыто, пересечение конечного семейства открытых множеств открыто, всё R и пустое множество открыты. Пересечение любого семейства замкнутых множеств замкнуто, объединение конечного семейства замкнутых множеств замкнуто, всё R и пустое множество замкнуты. Открытое множество, элементом которого является точка x, называется окрестностью точки x.

Если M - какое-то множество, то точка m из M называется изолированной, если найдётся хотя бы одна окрестность U точки m такая, что пересечение U и M равно {m}. Множество называется совершенным, если оно не имеет изолированных точек. Можно доказать, что совершенное подмножество R имеет мощность континуума. Верна теорема Кантора-Бендиксона (1883 год): каждая несчётная замкнутая часть R есть объединение совершенной части и какой-то не более чем счётной части.

Замыканием множества M называется пересечение всех замкнутых множеств, содержащих M. Внутренностью множества M называется объединение всех открытых подмножеств M. Множество M называется нигде не плотным, если внутренность его замыкания есть пустое множество. Множество называется множеством первой категории Бэра, если оно является объединением счётного числа нигде не плотных множеств. Множества второй категории Бэра - множества, не являющиеся множествами первой категории. Множество R является множеством второй категории Бэра. Более того, верна теорема Бэра (1899): пересечение счётной последовательности плотных частей R является плотной частью R.

Пусть S - множество. Алгеброй подмножеств S мы будем называть такое семейство частей S, что S является элементом семейства, объединение и пересечение любых двух элементов семейства является элементом семейства, дополнение любого элемента семейства до S также является элементом семейства. Алгебра подмножеств называется сигма-алгеброй, если и объединение, и пересечение счётной последовательности её элементов снова её элемент. Не любая алгебра является сигма-алгеброй. Пересечение любого семейства алгебр является алгеброй; сигма-алгебр является сигма-алгеброй. Булеан S является алгеброй. Для любого семейства X подмножеств S существует наименьшая по включению алгебра, являющаяся надмножеством X; это пересечение всех алгебр, частью которых является x. Аналогично для сигма-алгебр. наименьшая сигма-алгебра на R, содержащая все открытые подмножества R, называется борелевской сигма-алгеброй. Её элементы называются борелевскими множествами. Борелевская алгебра содержит не только все открытые множества, но и все замкнутые множества, а также некоторые множества, не являющиеся ни открытыми, ни замкнутыми. Пересечения счётных семейств открытых множеств называются G-дельта множествами, объединения счётных семейств замкнутых множеств называются F-сигма множествами.

На множестве вещественных чисел задана дефолтная мера: мера Лебега. Измеримые по Лебегу множества образуют сигма-алгебру; каждый интервал измерим по Лебегу. Следовательно, борелевская сигма-алгебра является частью этой алгебры, и потому каждое борелевское множество измеримо по Лебегу.

Рассмотрим теперь множество всех счётных последовательностей натуральных чисел. Это множество можно сделать топологическим пространством, рассмотрев для этого множество всех конечных последовательностей натуральных чисел Seq. Каждой конечной последовательности натуральных чисел s сопоставим множество O(s) всех тех бесконечных последовательностей, начало которых совпадает с s. Если теперь взять множество всевозможных O(s) в качестве базы топологии, то и получим топологическое пространство. Оно называется пространством Бэра (Берівський простір). Пространство Бэра метризуемо; более того, оно будет сепарабельным и полным. Каждая последовательность натуральных чисел может быть рассмотрена как непрерывная дробь; непрерывные дроби задают иррациональные числа. Следовательно, пространство Бэра - это топологическое пространство иррациональных чисел. Часть T множества Seq называется деревом, если сужение каждого элемента T является элементом T. Для каждого дерева T мы можем рассмотреть множество [T] бесконечных путей вдоль T: таких счётных последовательностей f, что для каждого натурального числа n сужение f на n будет элементом T. Множества [T] замкнуты в пространстве Бэра. Обратно, если какое-то множество F замкнуто в пространстве Бэра, то множество всех конечных сужений элементов из F будет деревом, обозначим его TF, и притом [TF] будет равно F. Непустое дерево называется совершенным, если для каждого его элемента t существуют два элемента s1 и s2 дерева такие, что t является сужением и первого и второго, но ни s1 не является частью s2, ни s2 не является частью s1. Замкнутое множество F пространства Бэра является совершенным тогда и только тогда, когда дерево TF является совершенным. На пространстве Бэра можно ввести меру Лебега.

Польское пространство - это топологическое пространство, которое гомеоморфно сепарабельному отделимому метрическому пространству. Стандартная топология на R, пространство Бэра, интервал [0;1] в индуцированной с R топологии, а также канторово множество, гильбертов кирпич и многие другие пространства являются польскими. Можно доказать, что каждое польское пространство является непрерывным образом пространства Бэра.

Теперь вернёмся к общим теоретико-множественным вопросам. Классическая теория множеств приобрела свой окончательный облик в основном под влиянием фон Неймана. Фон Нейман предложил аксиому фундирования, согласно которой в каждом классе, упорядоченном с помощью ∈, есть наименьший элемент.

Одна из его ключевых идей - это кумулятивная иерархия множеств, или, как теперь говорят, иерархия фон Неймана. По трансфинитной рекурсии определим V0 как пустое множество, V(a+1) как булеан Va, если a предельный, положим Va равным объединению Vb для всех b<a. Va называется верум-a. Мы определили верумы так, что у нас, между всем прочим, имеется верум-омега, соответствующий первому бесконечному ординалу. Он является объединением всех верумов с конечными индексами. Каждый верум - транзитивное множество. Каждый предыдущий верум - часть последующего. Каждый ординал a есть подмножество верум-a. Объединение всех верумов обозначается как V. V не является множеством. В аксиоматике ZFC класс V равен классу всех множеств.

Количество элементов в верумах растёт очень быстро. Уже в пятом веруме содержится 65536 элементов, а в шестом веруме элементов будет 2^65536. В верум-омега содержится счётное количество элементов, а в омега плюс первом веруме элементов будет континуум.

Один из главных инструментов фон Неймана для работы с верумами - это "принцип коллекции". Звучит он так. Если нам дано "индексированное семейство классов", совокупностью индексов которого является множество, то существует множество, содержащее хотя бы один элемент из каждого класса.

Другим ключевым инструментом является ∈-индукция и ∈-рекурсия.
Пусть T - транзитивный класс, F - свойство. Предположим, что F(0) истинно. Предположим, что если x∈T и если F(z) истинно для каждого z∈x, то F(x) истинно.
Тогда для каждого x из T истинно F(x).
Доказательство элементарно. Рассмотрим класс всех тех x из T, для которых F(x) ложно. Если он непуст, то в нём есть ∈-наименьший элемент x. Применим одно из предположений.

Аналогично определяется ∈-рекурсия. Рассмотрим транзитивный класс, зададим на нём функцию, которая по последовательности предыдущих элементов порождает следующий элемент. Тогда определена последовательность элементов класса.

Аксиомы фон Неймана, Бернайса и Гёделя таковы.
A1. Аксиома экстенсиональности.
A2. Каждое множество - класс.
A3. Только множества могут быть элементами.
A4. Для любых двух множеств есть неупорядоченная пара.

B. Для каждого одноместного предиката существует равнообъёмный ему класс.

C1. Существует индуктивное множество.
C2. Каждое семейство множеств имеет объединение.
C3. Каждое множество имеет булеан.
C4. Аксиома замены.

D. Аксиома регулярности.
E. Аксиома выбора. Существует функция F такая, что F(x) является элементом x для каждого непустого множества x.

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

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

Фильтры и идеалы определеляются так. Пусть S - непустое множество.

Фильтр F на множестве S - это такая совокупность подмножеств S, что:
1. S - элемент F. Пустое множество - не элемент F.
2. Пересечение двух элементов F - элемент F.
3. Надмножество элемента F - элемент F.

Идеал I на множестве S - это такая совокупность подмножеств S, что:
1. Пустое множество - элемент I. S - не элемент I.
2. Объединение двух элементов I - элемент I.
3. Подмножество элемента I - элемент I.

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

Тривиальный фильтр на S - это множество {S}.
Пусть X - часть S. Множество всех надмножеств X называется главным фильтром на S, порождённым X.
Пусть S - бесконечное множество, пусть I - множество всех его конечных подмножеств. Оно будет идеалом. Дуальный ему фильтр называется фильтром Фреше.

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

Простые свойства фильтров таковы.
1. Пересечение непустого семейства фильтров на S - фильтр.
2. Объединение цепи по включению фильтров (каждый последующий элемент - надмножество предыдущего) - фильтр.
3. Если семейство частей S обладает свойством конечных пересечений, то оно является подмножеством хотя бы одного какого-то фильтра.

Фильтр на S называется ультрафильтром, если для каждой части X множества S элементом этого фильтра является либо X, либо дополнение X.
Идеал на S называется простым, если дуальный ему фильтр - ультрафильтр.
Фильтр называется максимальным, если он не является собственным подмножеством никакого другого фильтра. Фильтр является максимальным тогда и только тогда, когда он является ультрафильтром.

Теорема Тарского (1930). Каждый фильтр содержится в некотором ультрафильтре.

На множестве мощности a существует ровно 2^(2^a) ультрафильтров,

Рассмотрим теперь ультрафильтры на ω; они часто используются в теоретико-множественной топологии.
Пусть D - неглавный ультрафильтр на ω. Он называется слабо селективным (weakly selective, синоним p-point), если для каждого разбиения ω на счётное количество кусочков, не являющихся элементами D, в D существует элемент, пересечение которого с каждым из кусочков конечно. Существование слабо селективных ультрафильтров следует из континуум-гипотезы (Уолтер Рудин, тот самый, 1956 год). Несуществование слабо селективных ультрафильтров совместно с ZFC.

Пусть D - неглавный ультрафильтр на ω. Он называется ультрафильтром Рамсея, если его пересечение с каждым из кусочков состоит ровно из одного элемента. Ультрафильтр Рамсея является слабо селективным, понятно. Из континуум-гипотезы следует существование ультрафильтра Рамсея.

Фильтр называется сигма-полным, если пересечение счётного семейства элементов фильтра является элементом фильтра. Идеал называется сигма-полным, если объединение счётного семейства элементов идеала является элементом идеала. На счётном множестве каждый сигма-полный фильтр - главный. Вопрос, когда на множестве существует неглавный сигма-полный ультрафильтр, ведёт вглубь теории множеств. Если такие фильтры есть, то есть и большие кардиналы.

Пусть a - кардинал. Фильтр называется a-полным, если пересечение семейства мощности a элементов фильтра является элементом фильтра. Идеал называется a-полным, если объединение семейства мощности a элементов идеала является элементом идеала.

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

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

Пусть X - множество ординалов, пусть a - предельный ординал. a - предельная точка X, если супремум пересечения X и a равен a.
Пусть a - регулярный несчётный кардинал. Его подмножество называется замкнутым неограниченным, если оно неограничено и содержит все свои предельные точки кроме a. Подмножество a называется стационарным, если его пересечение с каждым замкнутым неограниченным подмножеством непусто. Пересечение двух замкнутых неограниченных множеств само является замкнутым неограниченным. Следовательно, замкнутые неограниченные множества обладают свойством конечных пересечений и потому мы можем говорить о некотором фильтре; он называется замкнутым неограниченным фильтром. Замкнутый неограниченный фильтр на a является a-полным.

Пожалуй, главный результат о стационарных множествах - это лемма, которую доказал профессор Фодор в 1956 году.
Теорема Фодора. Для каждой убывающей функции на стационарном множестве S в кардинале a, значениями которой являются кардиналы, существует стационарное подмножество S, на котором функция постоянна и равна некоторому кардиналу, меньшему a.

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

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

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

Стационарные множества можно организовать в иерархию Mahlo, или иерархию стационарных множеств. Иерархию Mahlo ввёл в начале XX века, собственно, Paul Mahlo с помощью Mahlo operation.

Запишу пример интересного неотделимого пространства, чтобы не забыть. Рассмотрим множество целых чисел Z. Возьмём его разбиение на классы вычетов по модулю, ну например, 5, то есть всего будет пять классов:
[0]={... , 0, 5, 10, 15, ... },
[1]={... , 1, 6, 11, 16, ... },
[2]={... , 2, 7, 12, 17, ... },
[3]={... , 3, 8, 13, 18, ... },
[4]={... , 4, 9, 14, 19, ... }.

Введём топологию на Z, взяв эти множества в качестве базы топологии. То есть подмножество Z является открытым тогда и только тогда, когда оно является объединением какого-то семейства множеств из базы. Это действительно топология. Пустое множество открыто, так как является объединением пустого семейства элементов базы. Всё Z открыто, так как Z = [0]∪[1]∪[2]∪[3]∪[4]. Объединение любого семейства открытых множеств открыто по определению. Наконец, пересечение конечного семейства открытых множеств открыто: в самом деле, базу можно считать индексированной, и всякому открытому множеству можно сопоставить множество индексов тех элементов базы, объединением которых оно является. Возьмём пересечение этих множеств индексов, получим новое множество индексов. Объединив элементы базы с этими индексами, получим открытое множество, которое в точности является пересечением семейства.

Таким образом, открытыми множествами будут всевозможные объединения множеств [0]...[4]. Таких объединений 2^5 = 32 штуки, то есть в Z открыто 32 множества. Пространство Z с такой топологией демонстрирует занятные свойства, например, оно не является хаусдорфовым. Вот скажем точки 0 и 5 не имеют непересекающихся окрестностей. Вообще, оно даже не удовлетворяет аксиоме T0. По смыслу, открытые множества в этой топологии - множества чисел, которые при делении на 5 дают один из интересующих нас остатков. Например, [1]∪[3] - множество тех целых чисел, которые при делении на 5 дают в остатке либо 1, либо 3.

Топологическое пространство.
Пусть M - множество. Пусть T - некоторое множество подмножеств M. Если:
1. Пустое множество есть элемент T, M есть элемент T
2. Объединение любого семейства элементов T есть элемент T
3. Пересечение любого конечного семейства элементов T есть элемент T
то T называется топологией на M. Элементы T называются открытыми множествами.
Обычно рассматриваются только такие топологии, которые обладают свойством Хаусдорфа:
4. Если x и y - две разные точки T, то существуют два непересекающихся открытых множества U и V такие, что x элемент U, y элемент V.
Открытые множества, содержащие точку x, называются окрестностями точки x. Свойство Хаусдорфа можно переформулировать:
4. Две разные точки имеют непересекающиеся окрестности.
Окрестности x, из которых выброшена сама точка x, называются проколотыми.

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

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

Фильтр.
Пусть M - множество. Пусть F - некоторое множество подмножеств M. Если:
1. Пустое множество не есть элемент F
2. F не пусто
3. Пересечение любого конечного семейства элементов F есть элемент F
4. Надмножество элемента F есть элемент F
то F называется фильтром на M.

База топологии.
Пусть T - топология на M. Пусть B - некоторое множество открытых множеств.
Если множество T равно множеству объединений всевозможных семейств элементов B,
то B называется базой топологии T. Элементы B называются окончаниями базы, или, синоним, базовыми элементами.

Это означает, что любое открытое множество является объединением некоторого, возможно бесконечного, семейства элементов базы. Поэтому когда в пространстве выбрана база, мы можем утверждать, что если x - точка открытого множества U, то существует окончание b этой базы такое, что x∈b⊂U.
База задаёт топологию однозначно. Но у одной и той же топологии может быть много разных баз. Ясно, что сама топология T является своей базой. Таким образом, хотя бы одна база существует всегда. У баз пространства могут быть разные мощности. Наименьшая из мощностей баз называется весом топологического пространства.

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

У базы топологии есть очень полезный критерий.
Пусть B - множество подмножеств M. Оно является базой некоторой топологии на M тогда и только тогда, когда:
1. Объединение B равно M
2. Для любых U,V из B для любой точки x из U⋂V существует такое W из B, что x∈W ⊂ U⋂V.
Условие 2 означает, что любая точка пересечения двух окончаний базы входит в него вместе с некоторым содержащим её окончанием.
В частности, условие 2 выполняется, если пересечение конечного семейства элементов базы снова элемент базы - в качестве W можно взять тогда само U⋂V.

Этот критерий позволяет легко и изящно задавать топологии, указав в качестве базы множество, обладающее свойствами 1 и 2 - это задание корректно, поскольку база определяет топологию однозначно. Например, ясно, что, хотя непустое пересечение двух шаров в R^n не является шаром, оно содержит как подмножество хотя бы один шар. Таким образом, взяв в качестве базы всевозможные n-мерные шары, мы однозначно зададим топологию в R^n (она называется стандартной). Напомню, что в R^1 шаром является интервал, в R^2 шаром является круг.

Вообще, в качестве базы можно взять любое множество стандартных геометрических тел, если пересечение двух из них вместе с каждой точкой содержит объёмлющее её тело того же типа (речь об открытых телах, граница не включается). Например, в пересечении двух треугольников на плоскости каждая точка содержится вместе с маленьким треугольничком, поэтому топологию плоскости можно задавать с помощью треугольников. Так как в каждый треугольник точка входит вместе с некоторым кругом, а в каждый круг - с треугольником, база на треугольниках будет эквивалентна базе на кругах и задаст ту же топологию. Вместо треугольников можно взять квадраты, ромбы или, например, снежинки с хитрыми дырками - все они будут задавать одну и ту же топологию. В R^3 в качестве базы можно взять параллелепипеды или даже произвольную аниме-фигурку (сплошную, пустотелые не годятся). Таким образом, любое открытое в R^3 множество можно представлять себе как объединение некоторого семейства фигурок Хоро.

Предбаза топологии.
Пусть T - топология на M. Пусть B - база топологии T. Пусть P - некоторое множество открытых множеств.
Если множество B равно множеству пересечений всевозможных конечных семейств элементов P,
то P называется предбазой топологии T, порождающей базу B.

То есть множество всех конечных пересечений элементов предбазы образует некоторую базу.

Пусть M - какое-то множество. Пусть P - произвольное семейство подмножеств M. Пусть B - семейство подмножеств M, элементами которого являются пустое множество, всё множество M, все элементы P и всевозможные пересечения конечных семейств элементов P. Пусть T - всевозможные объединения всяческих, конечных и бесконечных, подсемейств B. Тогда T есть топология на M, B есть база этой топологии, P есть предбаза этой базы. Таким образом, чтобы ввести топологию на произвольном множестве, достаточно взять произвольное семейство его подмножеств и рассмотреть в качестве предбазы.

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

База фильтра.
Пусть F - фильтр на M. Пусть B - некоторое множество элементов этого фильтра.
Если любой элемент фильтра является надмножеством хотя бы одного элемента из B,
то B называется базой фильтра F. Элементы B называются окончаниями базы, или, синоним, базовыми элементами.

У базы фильтра есть аналогичный базе топологии критерий.
Пусть B - множество подмножеств M. Оно является базой некоторого фильтра на M тогда и только тогда, когда:
1. B не пусто
2. Пустое множество не есть элемент B
3. Для любых двух элементов из B существует элемент из B, являющийся подмножеством их пересечения.

Всякая база является базой только одного фильтра. Поэтому если мы укажем для произвольного множества M семейство частей, обладающее свойствами 1-3, то мы укажем один конкретный фильтр на этом множестве. У одного фильтра может быть много разных баз.

Две базы фильтра называются эквивалентными, если каждое окончание одной базы содержит как подмножество некоторое окончание другой базы. То есть базы B1 и B2 эквивалентны, если для каждого элемента из B1 существует являющийся его частью элемент из B2, и для каждого элемента из B2 существует являющийся его частью элемент из B1. Эквивалентные базы задают один и тот же фильтр.

Для базы фильтра, как и для базы множеств, можно ввести понятие предбазы. Предбазой фильтра в M называется семейство попарно пересекающихся подмножеств M. Если добавить к предбазе всевозможные конечные пересечения её элементов, то получится база фильтра.

Фильтры придумал Анри Картан в тридцатых годах, они были нужны ему для топологических исследований, которыми он занимался на своём семинаре. Фильтр задумывался как локальная конструкция - то есть в топологическом пространстве выделялась точка и рассматривался фильтр как бы в этой точке. Фильтр должен был быть множеством всех окрестностей точки, но возникла проблема: произвольное надмножество открытого множества не является, вообще говоря, открытым множеством. Поэтому Картан пошёл на усложнение понятия окрестности. То, что выше названо окрестностью (открытое множество, содержащее точку), Картан переименовал в открытую окрестность. Окрестностью точки x он стал называть любое множество M, которое содержит открытое подмножество U такое, что x - элемент U. То есть окрестностями точки стали не всевозможные открытые множества, содержащие эту точку, но всевозможные надмножества открытых множеств, содержащих эту точку. В таком, расширенном, смысле множество всех окрестностей точки действительно является фильтром. Однако если локально рассматривать не фильтр, а базу, то этой проблемы не возникнет. Семейство всех окрестностей (окрестностей в обычном смысле, то есть открытых окрестностей) точки x является базой. Оказывается, что рассмотрения только баз, без упоминания фильтров, достаточно, чтобы развить довольно богатый анализ. Поэтому обычно окрестности понимают в узком смысле, а не в смысле Картана. Терминология Картана, однако, весьма популярна.

Пусть M - кардинал, и пусть X - его подмножество (т.е. X - множество каких-то ординалов). X называется неограниченным в M, если ∪X = M. Напомню, что объединение множества ординалов - снова ординал, поэтому ∪X - ординал.
Если M - кардинал, то кофинальностью M называется наименьший кардинал k такой, что существует неограниченное множество X ⊂ M такое, что мощность X равна k. То есть кофинальность кардинала - наименьшая из мощностей неограниченных в нём множеств.
Кардинал называется регулярным, если он равен своей кофинальности. То есть если в нём нет неограниченных подмножеств мощности меньшей, чем он сам.
Кардинал k называется сингулярным, если в нём есть неограниченное подмножество мощностью меньше k.
Возможно, это лучше объяснит, почему кофинальность интересна.

Алеф-нуль, алеф-один и вообще алеф-n, где n натуральное, - все они регулярны. Кофинальность алеф-100500 есть 100500.
Первый сингулярный кардинал - это алеф-омега. Дело в том, что этот кардинал есть объединение всех алеф-n, где n натуральное. Но таких алефов ровно счётность - столько же, сколько натуральных чисел. То есть кофинальность алеф-омеги (хтонически гигантского кардинала) - всего лишь алеф-нуль.

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

Пусть дано топологическое пространство, A и B - два его непустых подмножества. A отделимо от B, если существует открытое множество, содержащее A, но не содержащее B. A и B отделимы, если есть два непересекающихся открытых множества, содержащие соответственно A и B. Может быть так, что A отделимо от B и B отделимо от A, но A и B не отделимы. A и B функционально отделимы, если есть непрерывная функция из пространства в отрезок [0;1], равная 0 на A и 1 на B.

Слово "точка" часто обозначает одноэлементное множество, содержащее эту точку. В определениях ниже точки считаются неравными, а замкнутые множества не содержат точку и не пересекаются. T0 - аксиома Колмогорова, T1 - Фреше, T2 - Хаусдорфа, T3 1/2 - Тихонова.

Топологическое пространство называется:
T0, если для любых двух точек верно, что хотя бы одна из них отделима от другой;
T1, если -//- что любая из них отделима от другой;
T2, если любые две точки отделимы;
T3, если точка и замкнутое множество отделимы;
регулярным, если оно T3 и T1;
T3 1/2, если точка и замкнутое множество функционально отделимы;
T4, если любые два замкнутых множества отделимы;
нормальным, если оно T4 и T1;
T5, если любое его подмножество нормально;
T6, если оно T1 и любые два замкнутых множества функционально отделимы.

Очевидно, что в T1-пространствах точки замкнуты.
T2 влечёт T1, T1 влечёт T0.
Регулярность влечёт T2.
Нормальность влечёт регулярность.
T5 влечёт нормальность.
T6 влечёт T5.

Пространство является T6 титтк оно нормально и любое его замкнутое подмножество типа G-дельта. Все метрические пространства - T6. Все T2-компакты нормальны.

---

Пусть T - топологическое пространство, A и B - два его замкнутых подмножества.
Пусть f - непрерывная функция из T в [0;1].
Пусть f(A) = 0, f(B) = 1.

Функция непрерывна тогда и только тогда, когда прообраз открытого множества открыт.
Возьмём вот такие открытые в отрезке множества: [0;0.5) и (0.5;1].
Их f-прообразы не пересекаются.
Вдобавок, эти прообразы как подмножества T открыты, ибо f непрерывна.
Первый из них содержит A.
Второй из них содержит B.
Таким образом, у A и B есть непересекающиеся окрестности.

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