>>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.