1610912324-d6d302fddade0a032e1066381713268c (824704), страница 9
Текст из файла (страница 9)
Может оказаться, что ни одно из соотношений а < Ь и Ь < а не имеет места. В этом случае элементы а и 6 называются несравнимыми. Таким образом, отношение порядка, определено лишь для некоторых пар э,пементов, поэтому мы и говорим о частичной упорядоченности. Если же в частично упорядоченном множестве ЛХ несравнимых элемоитов нет, то множество ЛХ называется упорядоченным (линейно утзорядоченнь!м, совершенно упорядочении!м). Итак, множество ЛХ упорядочено, если оно частично упорядочено и если для любых двух различных элементов а, Ь е ЛХ обязательно либо а < Ь, либо Ь < а.
Ясно, что всякое подмножество унорядочепного множества само упорядочено. Множества, указанные н примерах 1 — 4 п. 1, являются лишь частично упорядоченными. Простейшими примерами линейно упорядоченных множеств могут служить натуральные числа, совокупность всех рациональных чисел, всех действительных чисел на отрезке [О, 1] и т.
и. (с естественными отношениями «больше» и «меньше>), которые В этих мно>кествах имеются). )Ыы воздерживаемся от понятий вроде «все частично упорядоченные множествав. так как они, подобно понятию «множество всех множеств>, по существу, внутренне противоречивы и не могут быть включены в четкис математические концепции. 1 4. Упорядоченные множества Поскольку упорядоченносп есть частный случай частичной упорядоченности, к упорядоченным множествам применимо понятие отображения, сохраняющего порядок, и, в частности, понятие изоморфизма.
Поэтому можно говорить о порядковом типе упорядоченного множества. Ряд натуральных чисел 1,2,3,... с естественным отношением порядка между его элементами представляет собой простейший пример бесконечного упорядоченного множества. Его порядковый тип принято обозначать символом ы. Если два частично упорядоченных множества изоморфны между собой, то они, конечно, имеют одинаковую мощность (изоморфизм это биекция), поэтому можно говорить о мощности, отвечающей данному порядковому типу (например, типу ы отвечает мощность Ко).
Однако обратное неверно; множество данной мощности может быть упорядочено, вообще говоря, многими разными способами. Лишь порядковый тип линейно упорядоченного к о н е ч н о г о множества однозначно определяется числом п его элементов (и обозначается также через и). Уже для счетного множества натуральных чисел возможен, например, наряду с его «естественным» типом ы, такой тип: 1,3,5,...,2,4,6, т.е. такой, когда любое четное число следует за любым нечетным, а нечетные и четные числа между собой упорядочены по возрастанию.
Можно показать, что число различных порядковых типов, отвечающих мощности Ко, бесконечно и даже несчетно. 4. Упорядоченная сумма упорядоченных множеств. Пусть ЛХ1 и ЪХз два непересекающихся упорядоченных множества с порядковыми типами 01 и 0з, В объединении ЛХ1 О ЛХз множеств ЛХс и ЛХв можно ввести порядок, считая, что два элемента из ЛХ1 упорядочены как в ЛХы два элемента из ЛХз упорядочены как в Мз и что всякий элемент из ЛХ» предшествует всякому элементу из ЛХ .
(Проверьте,что это действительно линейная упорядоченность!) Такое упорядоченное множество мы будем называть упоряуочснной суммой множсглв М, и Ме и обозначать ЛХ1 + ЛХз. Подчеркнем, что здесь важен порядок слагаемых: сумма ЛХз + ЛХ1 не изоморфна, вообще говоря, сумме ЛХ1+ ЛХм Порядковый тип суммы М, + ЛХв мы будем называть упорядоченной суммой порядковых типов 01 и 0з и обознача"и 01 4-04. Это определение легко распространяется на произвольное конечное число слагаемых 0ы..., 0 Пример. Рассмотрим порядковые типы ш и и.
Легко видеть, что и + со = со; действительно, если мы к натуральному ряду рл. П Элементы теории множеств 40 1,2,3,..., й,... припишем слева конечное число членов, то мы получим тот же порядковый тип ев. В то же время порядковый тип ш + и, т.е. порядковый тип множества 1,2,3,..., й,..., аы...,а„, не равен, очевидно,ш. 5.
Вполне упорядоченные множества. Трансфинитные числа. Выше мы ввели понятия частичной упорядоченности и упорядоченности. Введем еше более узкое, но весьма важное понятие полной упорядоченности. Определение. Упорядоченное множество называется вгюлне упврядвченн м, если каждое его непустое подмножество содержит наименыпий (т. е, предшествующий всем элементам этого подмножества) элемент. Если упорядоченное множество конечно, то оно, очевидно, и вполне упорядочено. Примером упорядоченного,но не вполне упорядоченного множества может служить отрезок [О, 1]. Само это множество содержит наименьший элемент число О, .но его подмножество, состоящее из положительных чисел, наименыпего элемента не содержит. Ясно, что всякое (непустве) подмножество вполне упорядоченного мноаюесепва само вполне упорядочено.
Порядковый тип вполне упорядоченного множества называют порядкввьем числом (трансфинитным порядковым числом или, короче трансфинитвм, когда хотят подчеркнуть, что речь идет о бесконечном множестве). Натуральный ряд (с естественным отношением порядка) представляет собой множество не только упорядоченное,. но и вполне упорядоченное. Таким образом, его порядковый тип ео есть порядковое число (трансфинит!). Порядковым числом будет и ы + й, т.е. тип множества 1,...,и,...,аы...,ак.
Напротив, множество .,— и,... — 3 — 2 — 1 упорядочено, но не вполне упорядочено. Здесь в каждом непустом подмножестве есть наибольший элемент (т. е, следующий за всеми), но, вообще говоря, пет наименьшего (например, наименьшего элемента нет во всем множестве (1)). Порядковый тип (не являющийся порядковым числом!) множества (1) принято обозначать символом ы'. Ь 4. Упорядоченные мнсокества 41 Докажем следующий простой, но важный факт. Лемма К Упорядоченная сумма конечного числа вполне упорядоченных множеств есть нполпе упорядоченное множество. В самом деле, пусть ЛХ произвольное подмножество упорядоченной суммы ЛХ1 + . + М„вполне упорядоченных множеств; рассмотрим первое из множеств ЛХЬ, содержащее элементы нз ЛХ.
Пересечение М О ЛХь является подмножеством вполно упорядоченного множества ЛХЬ н, значит, имеет первый элемент. Этот элемент будет первым элементом и всего М. С лед с та не. Упорядоченная сумма порядковьгх чисел является порядковым числом. Мы можем, таким образом, отправляясь от некоторого запаса порядковых чисел, строить новые порядковые числа. Например, отправляясь от натуральных чисел (т. е. конечных порядковых чисел) и порядкового числа щ, можно получить порядковые числа ю+и, ог+зй ы+ы+гг, ог4-ог4-ог и т.д.
Читатель легко построит вполне упорядоченные множества, отвечающие этим трансфинитам. Наряду с упорядоченной суммой порядковых типов можно ввести упорядоченное произведение. Пусть ЛХг и Мг множества, упорядоченные по типам Вг и Вг. Возьмем много экземпляров множества ЛХг -- по одному на каждый элемент ЛХг — и заменим в множестве Мг его элементы этими экземплярамн Мь Полученное множество называется упорядоченным произведением ЛХ~ и Мг и обозначается символом ЛХг Мг.
Формально ЛХг . ЛХг строится как множество пар 1о, Ь), где о Е Иг н Ь Е ЛХг, причем (ач., Ьг) < (аг, Ьг), если Ьг < 6г (прн любых аы ог), и (оы 6) < (аз, Ь)., если ап < аг. Аналогично определяется упорядоченное произведение любого конечного числа сомножителей М, ЛХг ... ЛХр. Порядковый тнп В произведения М~ Мг упорядоченных ътожеств называется проозеедевием порядковых гпипое Вг и Вг: В = ВгВг. Как н упорядоченная сумлга, упорядоченное произведение некоммута- тивпо. П е и и а 2.
Упорялоченное произведение двух вполне упорядоченных множеств есть вполне. упорядоченное множество. Доказательство. Пусть М некоторое подмножество произведения ЛХг ЛХМ множество М есть множество пар 1а,Ь). Рассмотрим все вторые элементы Ь пар, входящих в ЛХ. Они образуют некоторое подмножество в Мг В силу полной упорядоченности ЛХг это подмножество имеет первый элемент. Обозначим ого Ьо и рассмотрим все пары вида (о, Ьо), Гл. П Элементы теории множеств 42 входящие в ЛХ. Их первые элементы а, образуют некоторое подмножество в ЛХь В силу полной упорядоченности ЛХе среди них имеется первый элемент. Обозначим его ао.
Тогда пара (ао,Ьо), как легко видеть, и будет первым элементом ЛХ. С л е д с т в и е. Упорядоченное произведение порядковых чисел является порядковым числом. Примеры. Легко видеть, что ы+~~ = ы 2, ь~+ы+ы = ~н 3. Легко также построить множества, упорядоченные по типам ео п, ы, ы п, ы, ..., о ',... Все этв множества будут иметь счетную мощность. Лйожно определить и другие действия над порядковыми типами, например, возведение в степень, и ввести в рассмотрение такие порядковые числа, как., скажем, ео, ы" и т.
д. б. Сравнение порядковых чисел. Если пе и па - два конечных порядковых числа, то они или совпадают, или одно из них больше другого. Распространим это отношение порядка на трансфинитные порядковые числа. Введем для этого следуюъпие понятия. Всякий элемент а линейно упорядоченного множества ЛХ определяет начальный отрезок Р (совокупность элеъ1ентов < а) и остаепок О (совокупность элементов > а). Пусть а и )Х вЂ” двв порядковых числа, а ЛХ и 1У множества, типа а и )1 соответственно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
