Операции на множестве ординальных чисел (стр. 1 )

ОПЕРАЦИИ НА МНОЖЕСТВЕ ОРДИНАЛЬНЫХ ЧИСЕЛ

Введение О теории множеств. Операции над множествами, мощности. Упорядоченные множества и их свойства. Линейно упорядоченные множества. Фундированные множества. Определение ординалов. Их свойства. Арифметика ординалов. Одно приложение

Литература

1. Введение

Предмет данной работы – операции над ординалами, или порядковыми типами. Эти объекты, обобщающие понятие числа, были определены Георгом Кантором в 1883 году.

Натуральные числа (в данном контексте включающие в себя и 0) могут быть использованы для двух целей: чтобы описать размер множества – количество его элементов, или чтобы описать положение (порядок) элемента в последовательности. Если мы ограничиваемся рассмотрением конечных множеств эти два понятия – порядкового и количественного, совпадают (см. 3.3). Именно, есть только один, с точностью до изоморфизма, способ упорядочить конечное множество в линейную последовательность: два конечных линейно упорядоченных множества изоморфны, если и только если они содержат одинаковое количество элементов. Когда мы имеем дело с бесконечными множествами, нужно различать понятия размера, приводящее к кардинальным числам, и позиции, следования, приводящей к обобщенным порядковым номерам – ординалам. Любое бесконечное множество можно упорядочить бесконечным числом способов. Можно сказать, что ординалы – классы порядковых типов – и есть эти способы. Ниже вводятся операции с такими типами, которые можно назвать «арифметикой ординалов».

2. О теории множеств. Операции над множествами. Мощности,

арифметика мощностей.

2.1 В теории множеств, если понимать ее узко, объектами являются просто множества, безо всякой дополнительной структуры. Множеством, с «наивной» точки зрения называется набор элементов произвольной природы. Иногда говорят, что «множество определяется своими элементами». При этом постулируется существование пустого множества ш – множества, не содержащего элементов.

Говорят, что два множества изоморфны, если между их элементами можно установить взаимно-однозначное соответствие, то есть множество изоморфно множеству , если существует взаимно-однозначное отображение .

Ясно, что:

любое множество изоморфно самому себе; Если множество изоморфно множеству , то и множество изоморфно множеству ; Если множество изоморфно множеству и множество изоморфно множеству , то множество изоморфно множеству .

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

Мощность множества обозначается символом . Мощности множеств называют кардинальными числами.

Одной из базовых в теории множеств является

Теорема 2.1.1 (Кантора-Бернштейна). Пусть и некоторые множества. Если существуют инъективные отображения и (не обязательно взаимно-однозначные), то данные множества равномощны.

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

Над множествами определены естественные операции объединения, произведения и возведения в степень. А именно, назовем объединением множеств и такое множество , которое содержит как элементы первого множества, так и элементы второго:

.

Назовем декартовым произведением множеств и множество упорядоченных пар :

Наконец, если и множества, то степенью называется множество всех отображений

.

Пример. С возведением в степень связан один интересный пример. Именно, пусть – произвольное множество. С каждым его подмножеством связана функция со значениями в двухэлементном множестве:

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

Описанные операции на множествах продолжаются до операций над мощностями – кардинальными числами. А именно, если , , то

, где – множество, равномощное множеству , которое не пересекается с множеством , а также , .

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

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