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

Множество М введённым на нём отношением порядка (т.е. пара {М, R}) называется (строго, нестрого, линейно ) упорядоченным множеством – в зависимости от вида отношения– строгого, нестрого или линейного.

Примеры: {множество чисел, неравенство}, {булеан, включение}.

Булеан произвольного множества есть частично упорядоченное множество - Доказать!

Матрица отношения нестрогого порядка имеет единицы на диагонали – рефлексивность.

Транзитивность приводит к ограничениям на вид матрицы: если a_ik=1 & a_kj=1 → a_ij=1.

Каждому отношению порядка ≤ на множестве М можно сопоставить следующие отношения.

1. Отношение <, которое получается из ≤ исключением элементов диагонали: < = ≤\ id_M. По определению, в этом случае получается отношение строгого порядка, т.е. иррефлексивное, антисимметричное и транзитивное.

2. Двойственный порядок ≥. Это отношение определяется как обратное по отношению к исходному: ≥ = ≤^-1. По аналогии с числами, мы будем говорить х меньше (больше) y, меньше (больше) или равен.

3. Отношение доминирования. Для двух элементов х и y y доминирует над z тогда, когда х строго больше y и не существует элемента «между ними». Иногда такие элементы называют «соседними». Из определения следует, что это отношение иррефлексивно, антисимметрично, но не транзитивно. Оно может быть и пусто. – Если отношение плотно, например.

Элементы (x, y) упорядоченного множества М называются сравнимыми по отношению порядка ≤, если x≤y или y≤x. В противном случае они называются несравнимыми. Аналогично определяется сравнимость для отношений строгого или двойственного порядков.

Линейный порядок.

Упорядоченное множество, все элементы которого попарно сравнимы, называется линейно упорядоченным, а соответствующее отношение – отношением линейного порядка. Заметим, что конечное множество можно перенумеровать натуральными числами – т.е. установить на нём линейный порядок. Можно также дополнить любое отношение порядка до линейного.

Лексикографический порядок.

Принцип построения словарей: Кант ≤ Кантор. Как быть с синонимами? — Есть кант – род песнопения и кант – край (обрамление, окантовка).