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

3.3 Частично упорядоченное множество называют линейно упорядоченным, если для любых двух элементов либо , либо , то есть любые два элемента сравнимы. Заметим, что любое подмножество линейно упорядоченного множества с индуцированным порядком также является линейно упорядоченным множеством.

Докажем свойство конечных линейно упорядоченных множеств, упомянутое во введении.

3.3.1 Теорема. Два конечных линейно упорядоченных множества и изоморфны в том и только в том случае, если их мощности совпадают: .

Доказательство. Если множества изоморфны, то между ними имеется биекция, поэтому их мощности совпадают.

Обратно. Пусть . Заметим, что в любом конечном (частично) упорядоченном множестве всегда найдется какой-нибудь минимальный элемент. Более того, этот минимальный элемент должен быть наименьшим, так как любые два элемента строго больших его сравнимы (в силу линейности порядка). Пусть и . Но множества и также обладают наименьшими элементами и . Продолжая процедуру перебора наименьших элементов:

и для ,

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

Если число элементов множества бесконечно (хотя бы счетно), на нем можно ввести много различных линейных порядков. Например, если и –линейно упорядоченные множества, то множество с порядком, описанным в примере 5 п. 3.1 и множество с лексикографическим порядком (пример 6 п. 3.1) будут линейно упорядоченными.

Основное определение.

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

Теорема Шарковского. Пусть – линейный порядок на множестве натуральных чисел, заданный следующим правилом:

Если отображение имеет точку с периодом3 n и n<m, то f имеет и точку с периодом m.

Пояснение. Любое натуральное число k однозначно представляется в виде

.

Порядок в теореме Шарковского определяется правилом

Это – линейный порядок на множестве .

Принцип математической индукции может быть сформулирован так

Принцип индукции. Пусть – некоторое свойство, выполненное для  натурального числа . Если нам удалось доказать свойство в предположении, что верно для всех натуральных  , то имеет место для всех натуральных чисел .

Мы хотим обобщить этот принцип (сформулированный для множества натуральных чисел) на произвольное линейно упорядоченное множество. На вопрос «когда это можно сделать?» отвечает следующая

3.3.2 Теорема. Следующие три свойства частично упорядоченного множества эквивалентны:

Любое непустое подмножество имеет наименьший элемент:

В частности, само множество имеет наименьший элемент .

Любая убывающая бесконечная последовательность стабилизируется:

если для последовательности элементов выполнено , то начиная с некоторого номера всегда для всех . То есть не существует бесконечных строго убывающих последовательностей.

Выполняется принцип индукции. Пусть – некоторое свойство элементов данного множества. Если при всех из истинности для всех следует истинность , то данное свойство имеет место для всех элементов множества

Доказательство этого утверждения см. [1, стр. 52].

Множества, обладающие введенным только что свойством, называют фундированными.

Примеры.

Любое конечное множество фундировано. Множество натуральных чисел N с естественным порядком является фундированным. Прямое произведение с лексикографическим является фундированным. Более того, прямое произведение фундированных частично упорядоченных множеств с лексикографическим порядком (пример 6 п. 3.1) порядком является фундированным. Рассмотрим два частично упорядоченных множества и , причем фундировано. Пусть – множество отображений с «конечным носителем»:

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