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

Со строгим порядком связана замечательная

2.1.2. Теорема Кантора. Для любого кардинала имеет место строгое неравенство .

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

2.2. С конечными множествами все более-менее понятно – их мощность это просто количество их элементов. Множество называется счетным, если оно равномощно множеству натуральных чисел. Обозначение для кардинала счетного множества . Георг Кантор доказал, что множество вещественных чисел из отрезка [0;1] не является счетным. Собственно, это следует из приведенной теоремы Кантора. Именно, отображение (здесь N – множество натуральных чисел), заданное правилом

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

Несколько примеров.

объединение счетных множеств счетно

объединение счетного числа счетных множеств счетно

с с с отрезок и квадрат на плоскости равномощны

сс бесконечномерный квадрат и отрезок равномощны.

3. Упорядоченные множества и их свойства

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

Рефлексивность: для любого имеем ; Антисимметричность: если и , то Транзитивность: если и , то .

Вместо обычно пишут и говорят «a не превосходит b». Отношение называют (частичным) порядком на множестве. Если и , то элементы и называются несравнимыми.

Примеры.

Числовая прямая с обычным отношением нестрогого порядка. Множество натуральных чисел с отношением делимости: если является делителем . Множество всех подмножеств произвольного множества A: если . Множество из трех элементов с порядками1 (элементы 1 и 2 несравнимы) и (элементы 0 и 2 несравнимы). Для любых двух (непересекающихся) частично упорядоченных множеств и на их объединении может быть задан следующий порядок. Пусть . Если , то между ними такое же отношение порядка, как во множестве А. Если , то между ними такое же отношение порядка, как во множестве В. Наконец, любой элемент множества А не больше любого элемента множества В (заметим, что в таком упорядочении важно какое множество первое, а какое второе). Для любых двух частично упорядоченных множеств и на их произведении  можно определить 1) покоординатный порядок: если и ; 2) лексикографический порядок – если либо , либо и (заметим, что в этом упорядочении также важно, какое множество первое, а какое второе).

3.2. Два упорядоченных множества и называются изоморфными (как упорядоченные множества), если существует биективное отображение , сохраняющее порядок:

тогда и только тогда, когда

Пример. 1. Проанализируем приведенный выше пример 4. Покажем, что трехэлементное множество с порядками (элементы 1 и 2 несравнимы) и (элементы 0 и 2 несравнимы) не изоморфны. Действительно, изоморфизм должен переводить пару сравнимых элементов в пару сравнимых. Элемент 0 сравним с двумя другими в первом упорядочении, а во втором с двумя другими сравним только элемент 1. Поэтому по необходимости . Но это невозможно, так как в этом случае и поэтому должно быть . Но 1 – строго больше любого элемента во втором упорядочивании.

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

Аналогично определим наименьший и минимальные элементы.

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

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

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

Примеры.

Множества N и {0,1} не изоморфны (здесь N –множество натуральных чисел с естественным порядком, а {0,1} – двухэлементное множество с порядком 0<1). Действительно, в первом множестве есть наименьший элемент, а во втором его нет. Заметим, что оба множества счетны. Множество рациональных чисел и множество целых чисел не изоморфны2. Действительно, пусть изоморфизм и , . В силу изоморфности  . Элемент должен быть целым числом между 0 и 1, что невозможно.

Интуитивно понятно, что неизоморфных счетных упорядоченных множеств бесконечно много.