Частично упорядоченные множества

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

Рассмотрим отношения G, L из 1.2.4, отношение Q из 1.2.2 и отношение включения V на множестве всех подмножеств целых чисел (B(Z) – булеан множества Z): B(Z) .

Таблица 1.4

Свойства отношений

Отношение	Р	АР	С	АС	НС	Т
G	-	+	-	-	+	+
L	+	-	-	+	-	+
Q	+	-	-	+	-	+
V	+	-	-	+	-	+

Мы видим, что по свойствам эти отношения разделились на два типа.

Определение. Отношение R на множестве Х, обладающее свойствами рефлексивности, антисимметричности, транзитивности, называется отношением порядка на множестве Х (обозначается “ p ”).

Определение. Отношение R на множестве Х, обладающее свойствами антирефлексивности, несимметричности, транзитивности, называется отношением строгого порядка.

Таким образом, отношения L, Q, V являются отношениями порядка на соответствующих множествах, а отношение G – отношением строгого порядка.

Если на множестве X введено отношение порядка p, то получен новый объект p) – частично упорядоченное множество. Так, различные частично упорядоченные множества (N, £) и (N, ½) можно получить, рассматривая на множестве N натуральных чисел отношения сравнения “ £ ” ( - x меньше или равно y и делимости “ ½ ” ( - x является делителем y). Слово “частично” используется потому, что не все элементы множества могут быть сравнимы между собой. Для частично упорядоченного множества (N, ½) несравнимы элементы N и N, так как ни один из них не является делителем другого.

Если все элементы множества сравнимы между собой, мы имеем линейный порядок, например, (N, £) – линейно упорядоченное множество.

Дата добавления: 2014-12-07