Упражнения

3.1. Выяснить, какими свойствами обладают следующие бинарные отношения:

а) ρ={(1, 30), (5, 6), (6, 5), (30, 2), (1, 2), (5, 5)} на А={1, 2, 5, 6, 30};

б) ρ={(1, 1)} на А={1};

в) ρ={(1, 1), (2, 2), (3, 3)} на А={1, 2, 3};

г) ρ={(х, у) | х, уR и xy};

д) ρ={(х, у) | х, уZ₊ и x, y – четные};

е) ρ={(х, у) | х, уR и х делится на у};

ж) отношение подобия на множестве всех многоугольников плоскости;

з) ρ={(х, у) | х и у имеют одинаковое имя} на множестве всех жителей г.Абакана.

3.2. Множество Х={4, 6, -2, 0, 3} разбито следующим образом:

а) {4, 6}, {–2, 0}, {3};

б) {4}, {6, –2, 0}, {3};

в) {4, 6, –2, 0}, {3};

г) задать какое-нибудь другое разбиение.

Записать отношение эквивалентности, соответствующее каждому разбиению.

3.3. На множестве Х={2, 4, 6, 8} заданы отношения эквивалентности:

а) ρ₁={(2, 2), (4, 4), (6, 6), (8, 8)};

б) ρ₂={(2, 2), (2, 4), (4, 2), (4.4), (6, 6), (8, 8)};

в) ρ₃={(2, 2), (2, 4), (4, 2), (4, 4), (6, 6), (8, 8), (6, 8), (8, 6)}.

Записать для каждого отношения классы эквивалентности, порожденные элементами множества Х, и соответствующее отношению фактор-множество множества Х.

3.4. Доказать, что объединение ρ₁ρ₂ двух отношений эквивалентности ρ₁ и ρ₂, заданных на множестве Х, является отношением эквивалентности тогда и только тогда, когда ρ₁ρ₂₌ρ₁◦ρ₂.

3.5. Доказать, что если ρ – есть транзитивное и симметричное отношение на множестве А и Д_ρR_ρ=А, то ρ – есть отношение эквивалентности на множестве А.

§ 4. Отношения порядка

Определение: Бинарное отношение называется предпорядком (квазипорядком) на множестве А, если оно рефлексивно и транзитивно на множестве А.

Определение: Бинарное отношение называется отношением частичного порядка на множестве А, если оно рефлексивно, транзитивно и антисимметрично на множестве А. Обозначение: .

Определение: Бинарное отношение называется отношением строгого порядка на множестве А, если антирефлексивно, антисимметрично и транзитивно на множестве А. Обозначение: .

Определение: Отношение порядка на множестве А, для которого любые два элемента сравнимы, т.е. : или , называется отношением линейного порядка.

Определение: Множество А с заданным на нём частичным порядком называется частично упорядоченным множеством. Обозначение: .

Определение: Множество А с заданным на нём строгим порядком называется строго упорядоченным множеством. Обозначение: .

Определение: Элемент частично упорядоченного множества называется максимальным, если .

Определение: Элемент частично упорядоченного множества называется наибольшим, если . Обозначение: .

Определение: Элемент частично упорядоченного множества называется минимальным, если .

Определение: Элемент частично упорядоченного множества называется наименьшим, если . Обозначение: .

Всякое конечное частично упорядоченное множество содержит как максимальные, так и минимальные элементы (причём может не единственные). Наибольший и наименьший элементы частично упорядоченного множества (если они существуют) единственны.

Заметим, что всякий наибольший элемент является максимальным, а всякий наименьший элемент является минимальным. Обратные утверждения, вообще говоря, неверны.

Рассмотрим упорядоченное множество А с введённым на нём отношением порядка . Говорят, что элемент y покрывает элемент x, если и не существует такого элемента , что и .

Если множество А конечно, то упорядоченное множество можно представить в виде схемы, в которой каждый элемент изображается точкой на плоскости, и если y покрывает x, то точки x и y соединяют отрезком, причём точку, соответствующую x, располагают ниже. Такие схемы называют диаграммами Хассе.