П. 4. Мощность и порядковый тип

1. Эквивалентность. Два множества U и V эквивалентны, если между ними можно построить биекцию. Обозначение: U ~ V.

Два множества, эквивалентные третьему, эквивалентны.

" бесконечное множество эквивалентно некоему своему собственному подмножеству! Это еще одно определение бесконечного множества.

Пример. Натуральные числа N эквивалентны:: 1) квадратам натуральных чисел: x «x ²; 2) натуральным степеням числа 2: x «2 ^x.

Упр. 6. Выписать биекции для чисел от 1 до 10 в этих примерах.

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

Для конечного множества мощность — это просто число элементов. Для булеана конечного множества |M(U)| = 2^{| U |},— число элементов.

Множество, эквивалентное множеству натуральных чисел N, называется счетным. Его мощность обозначается! ₀ (читается «алеф нуль»), т.е. | U | º! ₀.

Свойства счетных множеств: 1) любое натуральное число меньше, чем! ₀; 2) таким образом,! ₀ — наименьшая бесконечная мощность.

Множество несчетно, если его мощность больше, чем счетна.

Множество имеет мощность континуума, если оно эквивалентно множеству всех вещественных чисел отрезка [0, 1]. Обозначение мощности континуума:!.! — наименьшая несчетная мощность.

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

3. Изоморфизм. Бинарное отношение j называется антисимметричным, если из (a, b) Î j и (b, a) Î j следует, что a = b.

Частичная упорядоченность — бинарное отношение на множестве, одновременно антисимметричное, транзитивное и рефлексивное. Множество с таким отношением частично упорядочено. Если два элемента множества упорядочены, т.е. (a, b) Î j, то они сравнимы: a ˆ b.

Упр. 7. Определим на множестве слов отношение : a  b, если слово a — часть b. Например, <да>  <еда>, <еда>  <беда>. Привести по четыре других примера сравнимых и несравнимых слов.

Функция f: U ® V является изоморфизмом частично упорядоченных множеств U и V, если: 1) функция f — биекция; 2) образы f (a) и f (b) сравнимы тогда и только тогда, когда сравнимы a и b. Множества U и V изоморфны, если можно построить изоморфизм между ними.

Пример. Русский алфавит изоморфен первым 33 натуральным числам.

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

Множество упорядочено, или линейно упорядочено, если сравнимы любые два его элемента. Любое множество можно упорядочить!

Упорядоченное множество вполне упорядочено, если каждое его непустое подмножество содержит наименьший элемент.

Порядковое число (трансфинитное число, ординальное число, ординал, — это порядковый тип вполне упорядоченного множества.