Математическая культура. Мациевский С.В. - 33 стр.

                п. 4. Мощность и порядковый тип
     1. Эквивалентность. Два множества U и V эквивалентны, если между
ними можно построить биекцию. Обозначение: U ~ V.
     Два множества, эквивалентные третьему, эквивалентны.
     ∀ бесконечное множество эквивалентно некоему своему собственному
подмножеству! Это еще одно определение бесконечного множества.
     Пример. Натуральные числа N эквивалентны:: 1) квадратам натураль-
ных чисел: x ↔ x2; 2) натуральным степеням числа 2: x ↔ 2x.
     Упр. 6. Выписать биекции для чисел от 1 до 10 в этих примерах.
     2. Мощность. Мощность множества (кардинальное число, карди-
нал) — это то общее, что есть у любых двух эквивалентных множеств, то,
что остается после абстрагирования как от качества элементов, так и от их
порядка. Обозначение мощности множества U: |U|.
     Для конечного множества мощность —| это    |
                                                    просто число элементов.
Для булеана конечного множества |N (U)| = 2 U ,— число элементов.
     Множество, эквивалентное множеству натуральных чисел N, называется
счетным. Его мощность обозначается " 0 (читается «алеф нуль»), т.е.
|U| ≡ " 0.
     Свойства счетных множеств: 1) любое натуральное число меньше, чем
" 0; 2) таким образом, " 0 — наименьшая бесконечная мощность.
     Множество несчетно, если его мощность больше, чем счетна.
     Множество имеет мощность континуума, если оно эквивалентно
множеству всех вещественных чисел отрезка [0, 1]. Обозначение мощности
континуума: " . " — наименьшая несчетная мощность.
     Примеры. Натуральные, целые, рациональные и алгебраические числа
— счетные множества, тогда как трансцендентные, иррациональные, дей-
ствительные и комплексные числа имеют мощность континуума.
     3. Изоморфизм. Бинарное отношение ϕ называется антисимметрич-
ным, если из (a, b) ∈ ϕ и (b, a) ∈ ϕ следует, что a = b.
     Частичная упорядоченность — бинарное отношение на множестве,
одновременно антисимметричное, транзитивное и рефлексивное. Множе-
ство с таким отношением частично упорядочено. Если два элемента мно-
жества упорядочены, т.е. (a, b) ∈ ϕ, то они сравнимы: 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. Порядковый тип — это то общее, что присуще любым двум изо-
морфным между собой частично упорядоченным множествам.
     Множество упорядочено, или линейно упорядочено, если сравнимы
любые два его элемента. Любое множество можно упорядочить!
     Упорядоченное множество вполне упорядочено, если каждое его не-
пустое подмножество содержит наименьший элемент.

                                    32