А.Н. Колмогоров, С.В. Фомин - Элементы теории функции и функционального анализа, страница 9

Пусть а и Ь вЂ” элементы частично упорядоченного множества. Может оказаться, что ни одно из соотношений а < Ь и Ь < а не имеет места. В этом случае элементы а и Ь называются несраенижыжш Таким образом, отношение порядка определено лишь для некоторых пар элементов, поэтому мы и говорим о частичной упорядоченности.

Если же в частично упорядоченном множестве М несравнимых элементов нет, то множество М называется углорядоченглы,гн (линсйно упорядоченным, совершенно упорядоченным). Итак, множество М упорядочено„если опо частично упорядочено и если для любых двух различных элементов а, Ь б М обязательно либо а < Ь, либо Ь < а. Ясно, что всякое подмножество упорядоченного множества само упорядочено.

Множества, указанные в примерах 1-4 и. 1, являются лишь частично упорядоченными. Простейшими примерами линейно упорядоченных множеств могут служить натуральные числа, совокупность всех рациональных чисел, всех действительных чисел на отрезке (О, 1] и т. п. (с естественными отношениями «больше» и «меньше», которые в этих множествах имеются).

) Ыы воацерживаемся от понятий ироде «все частично упорядоченные множествав, так как они, подобно понятию «множество всех множества, по существу, внутренне противоречивы и не могут быть включены в четкие математические концепция. 1 4. Упвондоченные мнонеееевва зз Поскольку упорядоченность есть частный случай частичной упорядоченности, к упорядоченным множествам применимо понятие отображения, сохраняющего порядок, и, н частности, понятие изоморфизма. Поэтому можно говорить о гюрядковом типе упорядоченного множества. Ряд натуральных чисел 1,2,3,...

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

Лишь порядковый тип линейно упорядоченного конечного множества однозначно определяется числом и его элементов 1и обозначается также через и). Уже для счетного множества натуральных чисел возможен, например, наряду с его «естественным» типом ы, такой тип: 1,3,5,...,2,4,6.... т.е. такой, когда любое четное число следует за любым нечетным, а нечетные и четные числа между собой упорядочены по возрастанию.

Можно показать, что число различных порядковых типов, отвечающих мощности Ко, бесконечно и даже несчетно. 4. Упорядоченная сумма упорядоченных множеств. Пусть ЛХа и ЛХз — два непересекающихся упорядоченных множества с порядковыми типами В1 и Вз. В объединении М1 О ЛХэ множеств М, и Ма можно ввести порядок, считая, что два элемента из ЛХ1 упорядочены как в Мы два элемента из Мз упорядочены как в ЛХт и что всякий элемент из М1 предшествует всякому элементу из Мз.

(Проверьте, что это действительно линейная упорядоченность!) Такое упорядоченное множество мы будем называть упорядоченной суммой множеств М1 и ЛХз и обозначать ЛХа + Мз. Подчеркнем, что здесь важен порядок слагаемых: сумма Мэ + ЛХа не изоморфна, вообще говоря, сумме ЛХ1 + Мю Порядковый тип суммы Мг+ Мз мы будем называть упорядоченной суммой порядковых типов Ва и Вз и обозначать В~ + Вю Это определение легко распространяется на произвольное конечное число слагаемых Вы..., Вно Пример. Рассмотрим порядковые типы м и и.

Легко видеть, что п + ео = ы; действительно, если мы к натуральному ряду 40 Гл, Ь 9лгменою поорав многклств 1,2,3,..., к,... припишем слева конечное число членов, то мы получим тот же порядковый тип ы. В то же время порипковый тип и + и, т.е. порядковый тип множества 1,2,3,..., к,..., аы...,а„, не равен, очевидно,ы.

5, Вполне упорядоченные множества. Трансфинитные числа. Выше мы ввели понятия частичной упорядоченности и упорядоченности. Введем еще более узкое, но весьма важное понятие полной упорядоченности. Определение. Упорядоченное множество называется вполне упорядоченным, если каждое его непустое подмножество содержит наименьший (т.е, предшествующий всем элементам этого подмножества) элемент. Ксли упорядоченное множество конечно, то оно, очевидно, и вполне упорядочено. Примером упорядоченного, но не вполне упорядоченного множества может служить отрезок [О, 1]. Само это множество содержит наименьший элемент — число О, но его подмножество, состоящее из положительных чисел, наименьшего элемента не содержит.

Ясно, что всякое (непустое) подмнолсество вполне упорядоченного мнозкесгпва само вполне упорядочено. Порядковый тип вполне упорядоченного множества называют порядковым числом (трансфинитным порядковым числом или, короче трансфннитом, когда хотят подчеркнуть, что речь идет о бесконечном множестве). Натуральный ряд (с естественным отношением порядка) представляет собой множество не только упорядоченное, но и вполне упорядоченное. Таким образом, его порядковый тип ы есть порядковое число (трансфинит1).

Порядковым числом будет и ы+ 14, т.е. тип множества 1,..., и,..., аы..., аы Напротив, множество .,— и ...,— 3 — 2,-1 упорядочено, но не вполне упорядочено. Здесь в каждом непустом подмножестве есть наибольший элемент (т.е. следующий за всеми), но, вообще говоря, нет наименьшего (например, наименьшего элемента нет во всем множестве (1)). Порядковый тип (не являющийся порядковым числом!) множества (1) принято обозначать символом ы'.

1 4. Уиорвдачеиние миоягссвма Докажем следукнпий простой, но важный факт. Лемма 1. Упорядоченная сумма конечного чнсла вполне улорядочеиненх множеств есть вполне упорядоченное множегтво. В самогн деле, пусть М вЂ” лронзвольное подмножество упорядоченной суммы М~ + . + ЛХ„вполне упорядоченных множеств; рассмотрим первое из множеств Мы содержащее элементы нз ЛХ. Пересечение Лт П Мь является подмножеством вполне упорядоченного множества ЛХЬ и, значит, имеет первый элемент. Этот элемент будет первым элементом и всего М.

С л ел станс. Упорядоченная сулгма гщрядковых окал является порядковым числом. Мы можем, таким образом, отправлянсь от некоторого запаса порядковых чисел, строить новые порядковые числа. Например, отправляясь от натуральных чисел (т. е. конечных порядковых чпсел) и порядкового числа ю, можно получить порядковые числа ы+и, ю+ы, ш+ю+и, ы+ш+щ и тд. Читатель легко построит вполне упорядоченные множества, отвечающие этим трансфинитам. Наряду с упорядоченной суммой порядковых типов можно ввести уиорвдаченнае пра заедгниа Пусть ЛП и Лдр -- множества, упорядоченные по типам В~ н Вз. Возьмем много экземпляров множества М~ — ио однаму на каждый элемент Мз — - н заменим в множестве Мх его элементы этими экземплярами Мь Полученное множество называется упорядоченным произведением ЛП и Мз и обозначается символам ЛХг Мз.

Формально М~ Мз строятся как множество пар (а,Ь), где а б ЛП и Ь Е Мз, причем (ам 1н) < (ам 1м), если Ь~ < Ьз (при любых ам аз), н (ам Ь) < (ам Ь), если а~ <ам Аналогично определяется упорядоченное произведение любого конечного числа сомножителей Л4~ Мг ....Мю Порядковый тнп В произведения М~ Мз упорялоченных множеств называется произоедением порядковых тинов В~ и Вм в=в в . Как н упорядоченная сумма, упорядоченное произведение некоммутв- тивно. Лемма 2. Упорядоченное враизведениедвух вполне упорядоченных множеств есть вполне упорядоченное множество.

Да к аз а т ель с т в а. Пусть М вЂ” некоторое подмножество произведения М~ . Мм множество М есть множество пар (а,Ь). Рассмотрим все вторые элементы Ь нар, входящих в М. Они образуют некоторое подмножества в Лдз. В силу полной упорядоченности Мз это подмножество имеет первый элемент. Обозначим его Ьа и рассмотрим все пары вида (а. Ьо), еЛ. й Элементы и~европ мнооюеетв входящие в М. Их первые элементы а образуют некоторое подмиожесзво в Мь В силу полной упорядочешюсти М| среди них имеется первый элемент, Обозначим его ао. Тогда пара (ао,бо), как легко видетен и будет первым элементом М. Следствие. Упорядоченное произведение порядковых чисел является порядковым числом. Примеры. Легко видеть, что ы+ы = ы 2, ы+ы+ы = ы 3.