Виды бинарных отношений

Рисунок 3.4 – Разбиение множества

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

Определение. Разбиением (или расслоением) множества А называется система S непустых подмножеств множества А таких, что каждый элемент из А принадлежит одному и только одному подмножеству из системы S.

Подмножества из S называются смежными классами (или слоями) разбиения S.

Рассмотрим связи между отношениями эквивалентности некоторого множества и его разбиениями.

Теорема 3.4. Если σ – отношение эквивалентности на множестве А, то совокупность всех различных смежных классов множества А по эквивалентности σ является разбиением множества А.

Теорема 3.5. Пусть S – разбиение множества А, а σ — бинарное отношение на множестве А такое, что, по определению, х σ у () истинно тогда и только тогда, когда в S есть подмножество М, для которого , . Тогда σ – отношение эквивалентности на множестве А. Эта эквивалентность σ называется эквивалентностью, отвечающей разбиению S.

Теорема 3.6. Для любого множества А существует взаимно однозначное соответствие между множеством разбиений множества А и множеством отношений эквивалентности на А.

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

Примеры отношений порядка:

- отношение «меньше» на множестве натуральных чисел;

- отношение «короче» на множестве отрезков.

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

1) х ρ х для любого   (рефлексивность);

2) из х ρ у и y ρ z следует x ρ z для любых  (транзитивность);

3) из х ρ у и у ρ х следует х=у для любых   (антисимметричность).

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

Примерами отношения частичного порядка являются: отношение  включения на множестве подмножеств не­которого множества; отношение ≤ на множестве действительных чисел; отношение «х делит у» на множестве натуральных чисел.

Частичный порядок на множестве А будем обозначать символом ≤, и если a ≤ b для некоторых элементов , то будем говорить, что а меньше или равно b, а также, что а содержится в b или равно b. Если a ≤ b и а ≠ b, то будем писать а < b и говорить, что а строго меньше b или а строго содержится в b.

Определение. Элементы а, b множества А называются сравнимыми относительно частичного порядка ≤ на этом множестве, если a ≤ b или b ≤ a.

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

Частично упорядоченное множество может обладать или не обладать наименьшим или наибольшим элементом. Однако если частично упорядоченное множество обладает наибольшим (наименьшим) элементом, то он единственный.

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

Определение. Минимальным элементом частично упорядоченного множества А называется такой элемент , что каждый элемент x из А либо не сравним с b, либо b ≤ х, т.е. если А не содержит элементов, строго меньших b.

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

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

Определение. Пусть а, b – элементы частично упорядоченного множества А. Элемент а называется непосредственно меньшим (непосредственно предшествующим) для элемента b, а b – непосредственно большим (непосредственно следующим) за а, если a < b и не существует элемента , который удовлетворял бы отношению a < х < b.

Определение. Частичный порядок на множестве А называется линейным порядком, если любые два элемента из А сравнимы относительно ≤.

Определение. Множество А, на котором задан какой-либо линейный порядок, называется линейно упорядоченным множеством, или цепью.

Примером линейно упорядоченного множества может служить множество всех действительных чисел с обычным отношением ≤.

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

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

1) (условие минимальности). Всякое непустое подмножество множества А является частично упорядоченным множеством, содержащим минимальные элементы;

2) (условие индуктивности). Если все минимальные элементы множества А обладают некоторым свойством Р и из того, что все элементы х из А, удовлетворяющие условию х < а, обладают свойством Р, вытекает, что элемент а также обладает свойством Р, то свойством Р обладают все элементы

Определение. Линейно упорядоченное множество, удовлетворяющее условию минимальности (а, следовательно, и остальным условиям теоремы), называется вполне упорядоченным множеством.

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

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