§ 5. УПОРЯДОЧЕННЫЕ МНОЖЕСТВА И АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ

5.1. Упорядоченные множества

Определение 51.1. Пусть во множестве М задано бинарное отношение («выше» или «следует за»). Это отношение называют отношением порядка, а систему — упорядоченным множеством, если это отношение:

1) транзитивно, т. е.

и

2) антисимметрично, т. е.

Вместо того чтобы сказать «а выше мы говорим также «b предшествует а». Если и если для любого элемента отличного от а и от b,

мы говорим непосредственно следует за 6».

Отношение порядка во множестве М называют отношением нестрогого порядка, а систему — нестрого упорядоченным множеством, если это отношение

3) рефлексивно, т. е.

Отношение порядка во множестве М называют отношением строгого порядка, а систему — строго упорядоченным множеством, если это отношение

4) антирефлексивно, т. е.

Отношение порядка во множестве М называют отношением линейного (или совершенного) порядка, а систему — линейно (совершенно) упорядоченным множеством, если это отношение

5) связно, т. е.

Если отношение порядка во множестве М не является отношением линейного порядка, то это отношение называют отношением частичного порядка, а систему — частично упорядоченным множеством.

Следующие термины, мы думаем, понятны без объяснений: «линейно и нестрого упорядоченное множество», «линейно и строго упорядоченное множество», «частично и нестрого упорядоченное множество», «частично и строго упорядоченное множество».

Если — упорядоченное множество, а М — подмножество то бинарное отношение является отношением порядка При этом система — строго упорядоченное множество, если система М — строго упорядоченное множество; JVT — линейно упорядоченное множество, если система М — линейно упорядоченное множество. В дальнейшем термин «подмножество» упорядоченного множества используется и для обозначения подмножества множества и для обозначения системы , где .

Пусть — упорядоченное множество; с — его элементы. Если то говорят, что элемент b лежит между элементами а и с. Если система — линейно упорядоченное множество, то хотя бы один из любой тройки элементов множества М лежит между двумя другими.

Пусть — упорядоченное множество, В — подмножество множества А. Элемент — множества А называют нижней гранью множества В, если

в частности наименьшим элементом множества если к тому же .

Определение 5.1.2. Пусть В — подмножество упорядоченного множества Элемент множества В называют минимальным элементом множества В, если

Аналогично определяется верхняя грань, наибольший и максимальный элементы подмножества упорядоченного множества. Множество всех верхних и нижних граней множества В мы обозначаем соответственно символами U(В) и L(В). В частности, — множество всех элементов множества А, следующих за элементами а и b; — множество всех элементов , следующих за элементом а.

Упорядоченное множество называют решеткой (структурой) если выполняются следующие условия:

Примеры: 5.1.1. Отношение (делится на) делимости в N — отношение частичного и нестрогого порядка.

5.1.2. Отношение с — включения во множестве всех подмножеств данного множества — отношение частичного и нестрогого порядка.

5.1.3. Отношение делимости во множестве всех степеней данного натурального числа — отношение линейного и нестрогого порядка.

5.1.4. Пусть М — множество, РМ — множество всех его подмножеств. Тогда система — решетка.

5.1.5. Система — решетка. Если а и b — натуральные числа, то множество общих кратных и множество общих делителей чисел а и b соответственно.

Вопросы 5.1.1. Какими являются отношения (больше) и (больше или равно) во множестве натуральных чисел?

5.1.2. Доказать, что

если — строго упорядоченное множество.

5.1.3. Пусть — линейно упорядоченное множество. Доказать, что бинарное отношение , определяемое условием

есть отношение линейного и строгого порядка.

5.1.4. Пусть — линейно упорядоченное множество. Доказать, что бинарное отношение определяемое условием

есть отношение линейного, нестрогого порядка.

Определение 5.1.3. Если в линейно упорядоченном множестве каждое непустое подмножество имеет наименьший элемент, то систему называют вполне упорядоченным множеством, а отношение отношением полного порядка.

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

Пример 5.1.4. Порядок (больше) во множестве натуральных чисел является полным.

Пусть система — вполне упорядоченное множество; . Множество

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

Если а — минимальный элемент множества А, то Теорема 5.1.1. (принцип трансфинитной индукции). Пусть система — вполне упорядоченное множество. Любое подмножество М множества А содержит А, если

(5.1.1)

другими словами, если для каждого элемента а множества А из принадлежности к множеству М всех элементов интервала следует, что и элемент а принадлежит М.

Доказательство. Пусть , т. е. теоретико-множественная разность множеств . Если пусто, то доказывать нечего. Если , то, так как А — вполне упорядоченное множество, множество содержит наименьший элемент .

В таком случае, все элементы, предшествующие и отличные от , не принадлежат М и, значит, принадлежат М. Таким образом, . Поэтому в силу (5.1.1) , и, следовательно, противоречие с предположением.

В 1904 г. итальянский математик Цермело доказал следующую теорему.

Теорема 5.1.2. Во всяком множестве можно ввести полный порядок.

Следует заметить, что доказательство Цермело неэффективно в.. том смысле, что позволяет установить существование полного порядка в данном множестве, но не дает указания, как узнать для какой- нибудь пары элементов данного множества, какой из этих элементов предшествует второму в этом порядке.

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

Различные типы строго (нестрого) упорядоченных четырехэлементных множеств изображаются следующими графами:

Граф 1 отвечает линейному порядку, остальные — частичному.

Вопросы: 5.1.5. Сколькими способами можно определить линейный порядокна множестве из трех элементов? линейный и строгий? линейный и нестрогий?

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

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

5.1.8. Пусть — вполне упорядоченное множество; . Доказать, что система — вполне упорядоченное множество.

5.1.9. Пусть — вполне упорядоченное множество; — интервал системы А. Доказать, что любой интервал системы является интервалом системы А.

5.1.10. Доказать, что любой интервал вполне упорядоченного множества есть его собственное подмножество.

5.1.11. Пусть — вполне упорядоченное множество; . Доказать, что

в случае, если порядок нестрогий.

5.1.12. Пусть — вполне упорядоченное множество; . Доказать, что или или или .

5.1.13. Пусть — вполне упорядоченное множество; . Доказать, что В — интервал системы А тогда и только тогда, если

5.1.14. Пусть изоморфное отображение вполне упорядоченного множества на его подмножество Доказать, что

5.1.15. Пусть А -вполне упорядоченное множество; — интервал системы А. Доказать, что системы А и неизоморфны.

5.1.16. Пусть — вполне упорядоченные множества такие, что . Во множестве определим бинарное отношение следующими условиями:

1) если , то

2) если то

3) если , то

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

5.1.17. Пусть — вполне упорядоченные множества. Во множестве определим бинарное отношение следующим условием:

Доказать, что система () — вполне упорядоченное множество.

Для каждого вполне упорядоченного множества символом А обозначаем новый объект, называемый порядковым числом вполне упорядоченного множества, и такой, что для любых вполне упорядоченных множеств А и В

в том и только том случае, если системы А и В изоморфны. Пусть ; Тогда:

а) говорят, что (а меньше ), если система А изоморфно отображается на некоторый интервал системы В; говорят, что

б) под суммой понимают порядковое число системы (), если и отношение определено, как в условии вопроса 5.1.16;

в) под произведением понимают порядковое число системы ( если отношение определено, как в условии вопроса 5.1.17.

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

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

Для любого порядкового чжла а А символом условимся обозначать кардинальное число множества А.

Вопросы: 5.1.18. Пусть у порядковые числа. Доказать, что:

Пусть a — порядковое число; символом мы обозначаем множество всех порядковых чисел, строго меньших числа а. Таким образом, если a — порядковое число, то

5.1.19. Доказать, что система — вполне упорядоченное множество, а его порядковое число равно а.

5.1.20. Доказать, что для любых порядковых чисел

5.1.21. Доказать, для для любых порядковых чисел

5.1.22. Из теоремы Цермело вывести, что для любых кардинальных чисел а и b

5.1.23. Пусть а — кардинальное число, — множество всех кардинальных чисел, строго меньших кардинального числа а.

Доказать, что система — вполне упорядоченное множество.

5.1.24. Пусть а — порядковое число; — множество всех предельных чисел множества S. Доказать, что:

1) любое порядковое число а из множества S можно представить и только одним способом в виде

(5.1.2)

где — предельное число множества — конечное порядковое число;

2) любое порядковое число, представимое в виде (5.1.2), принадлежит

5.1.25. Пусть — кардинальные числа такие, что . Доказать, что

5.1.26. Пусть a, z и 7 — порядковые числа

Доказать, что:

5.1.27. Пусть а и b — кардинальные числа такие, что . Доказать, что