§8. Арифметика кардинальных чисел. Ординалы. Трансфинитная индукция.

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

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

Определение 1: Если мощность некоторого множества равна, мощность множестваравна, причёмине пересекаются, то мощность множествабудет равна.

Замечание: Для сложения мощностей можно использовать следующие арифметические свойства:

-коммутативность,

-ассоциативность.

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

Для дальнейших рассуждений введём следующие стандартные обозначения мощностей множеств. Мощность счетного континуума обычно обозначают первой буквой древнееврейского алфавита , называемой «алеф». Мощность конечного множества -. Мощность множествавсех подмножеств множестваобозначают -, где- множество мощности континуум (например, множество точек отрезка).

Для введенных в рассмотрение кардинальных чисел имеют место следующие равенства:

1) ,

2) ,

3) ,

4) ,

5) .

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

Если мощность множества равна, а мощность множестваравна, то мощность множестваобозначается.

Для умножения мощностей (кардинальных чисел) имеют место следующие законы:

-коммутативность;

-ассоциативность;

-дистрибутивность;

;

;

.

Например, последнее из этих равенств может означать, что множество точек отрезка равномощно множеству точек квадрата.

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

В частности, число всех подмножеств множества , как показано выше, равно(т.е. числу всех функций со значениями 0 и 1).

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

Определение 2: Пусть множество имеет мощность, множествоимеет мощность, тогдаесть мощность множества всевозможных функций из множестваво множество, т.е..

Ниже даётся понятие порядковых типов для произвольных множеств.

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

Определение 3: Если два линейно упорядоченных множества изоморфны, то их называют подобными множествами.

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

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

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

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

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

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

Замечание: Можно заметить, что каждое конечное линейно упорядоченное множество удовлетворяет условию минимальности, и потому, вполне упорядочено, т.е. является отрезком натурального ряда чисел.

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

Георг Кантор в своё время из множества всех множеств выделил вполне упорядоченные множества, ряд свойств которых напоминает свойства множества натуральных чисел.

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

Определение 5: Порядковый тип вполне упорядоченного множества называется порядковым числом. Если порядковое число имеет бесконечную мощность, то оно называется трансфинитным числом.

Число 0 и все натуральные числа есть конечные порядковые числа.

Определение 6:Порядковые числа называют ординалами.

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

Покажем, как можно представлять себе некоторые счётные ординалы. На рисунке показано, как можно луч взаимно однозначно отобразить на отрезоктак, чтобы при этом сохраняется порядок указания точек. Точкамна луче будут взаимно однозначно соответствовать точкина отрезке. Рассмотрим точку 1 на отрезке. Эту точку уже невозможно занумеровать натуральным числом, для её нумерации нужен новый символ, например.Так принято обозначать трансфинитное число, идущее сразу за всеми натуральными числами. Слово «трансфинитное» происходит от латинских слов:trans-через, finite-конечный.

Перенесем теперь полученные точки на отрезок бесконечного луча. Множество полученных точектакже является вполне упорядоченным.

Множество теперь сдвинет полученное множество точек на 1 влево, при этом точки отобразится следующим образом:,,...,,и т.д.

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

Таким образом, даже счётные ординалы могут быть устроены достаточно сложно. Из теоремы Цериело следует, что существуют ординалы любой мощности.

Рассмотрим некоторые практические приложения вышеизложенного материала.

Известно, какую важную роль играет в математике метод полной математической индукции. Этот метод можно использовать для доказательства различных математических предложений (равенств, неравенств и т. д.). Метод математической индукции можно применять, если предложение рассматривается во множестве натуральных чисел. Он основан на следующей теореме.

Теорема 1 (принцип математической индукции): Пусть предложение, определённое на множестве натуральных чисел. Если предложениебудет таким, что высказывание- истинно, и из истинности высказыванияследует истинность высказываниядля любого, то предложениевыполняется для любого натурального числа.

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

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

1) База индукции: Проверка истинности высказывания . Есливыполняется, то переходим к следующему пункту.

2) Индуктивное допущение: Делается предположение об истинности высказывания для произвольного числа.

3) Индуктивное доказательство: Исходя из условий задачи, нужно показать, что из истинности высказывания следует истинность высказывания.

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

Замечание: Иногда база индукции начинается не с 1, а с некоторого натурального числа .

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

Теорема 2 (о трансфинитной индукции): Пусть предложение, определённое на множестве порядковых чисел, т. е.- порядковое число. Если высказываниеистинно, и из истинностивытекает истинность, где, тогдаистинно для всех порядковых чисел.

Доказательство теоремы 2 аналогично доказательству теоремы 1.

Множество натуральных чисел - первый числовой класс.

Определение 7: Вторым числовым классом назовем множество всех порядковых чисел, являющихся наименьшим числом второго класса и наименьшим трансфинитным числом. Можно доказать, что если - число второго класса, тотакже число второго класса; если- счетное множество чисел второго класса и- наименьшее число, большее всех чисел из множества, то и- число второго класса.

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

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

Определение 8: Мощность вполне упорядоченного множества называется алефом.

Множество алефов есть вполне упорядоченное множество.

Заметим, что арифметика ординалов отличается от арифметики кардинальных чисел. В частности, если иординалы, то и, и. (например,и, но) и значит,.