logo search
Diskretnaya_matematika_1_semestr

Отношение порядка. Изоморфизм упорядоченных множеств.

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

Пусть р-произвольное отображение декартового произведения

(a1,a2,...,an)(A1,A2,...An) (возможноА1=А2=...An) на множестве, состоящее из 2 элементов {1,0}. Такое отображение называется предикатом.

Совокупность тех наборов (a1,a2,...,an) которые р отображает в истину задает n-арное отношение R. RA1*A2*...*An которые однозначно определяет р.

Два упорядоченных множества называются изоморфными (одинаковыми с точки зрения структуры) если существует также биективное отображение :A1→А2 такое что если a1b=>(a)2(b)

Для изображения конечных упорядоченных множеств используется диаграмма Хассе. Идея диаграмм Хассе состоит в том, что мы не рисуем того, что мы можем установить по рефлексивности и транзитивности. Два элемента называются сравнимыми, если ab или ba. Упорядоченное множество, любые два элементы которого сравнимы, называется линейно-упорядоченным.

2^А нельзя линейно упорядочить отношением включения.

Линейно упорядоченое множество называют цепью.