Отношение частичного порядка (№11)

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

Работу выполнила:

Никифорова Татьяна

Группа КБ-11

Определение и примеры

Порядком, или частичным порядком, на множестве M называется бинарное отношение на M (определяемое некоторым множеством ), удовлетворяющее следующим условиям:

• Рефлексивность:

• Транзитивность:

• Антисимметричность:

Множество M, на котором задано отношение частичного порядка, называется частично упорядоченным. Если быть совсем точным, то частично упорядоченным множеством называется пара , где M — множество, а — отношение частичного порядка на M.

Терминология и обозначения

Отношение частичного порядка обычно обозначают символом , по аналогии с отношением «меньше либо равно» на множестве действительных чисел. При этом, если , то говорят, что элемент a не превосходит b, или что a подчинен b.

Если и , то пишут a < b, и говорят, что a меньше b, или что a строго подчинен b.

Иногда, чтобы отличить произвольный порядок на некотором множестве от известного отношения «меньше либо равно» на множестве действительных чисел, вместо и < используют специальные символы и соответственно.

Строгий и нестрогий порядок

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

то получим определение строгого, или антирефлексивного порядка.

Если — нестрогий порядок на множестве M, то отношение < , определяемое как:

является строгим порядком на M. Обратно, если < — строгий порядок, то отношение , определенное как

является нестрогим порядком.

Поэтому все равно — задать на множестве нестрогий порядок, или строгий порядок. В результате получится одна и та же структура. Разница только в терминологии и обозначениях.

Примеры

Подмножества {x, y, z}, упорядоченные отношением включения

• Как уже указывалось выше, множество действительных чисел частично упорядочено по отношению «меньше либо равно» .

• Пусть M — множество всех действительнозначных функций, определенных на отрезке [a,b], то есть функций вида

Введем отношение порядка на M следующим образом. Мы скажем, что , если для всех выполнено неравенство . Очевидно, введенное отношение в самом деле является отношение частичного порядка.

• Пусть M — некоторое множество. Множество всех подмножеств M (так называемый булеан), частично упорядочено по включению .

• Множество всех натуральных чисел частично упорядочено по отношению делимости .

Связанные определения

Несравнимые элементы

Если a и b — действительные числа, то имеет место одно и только из соотношений:

В случае, если a и b — элементы произвольного частично упорядоченного множества, то существует четвёртая логическая возможность: не выполнено ни одно из указанных трех соотношений. В этом случае элементы a и b называются несравнимыми. Например, если M — множество действительнозначных функций на отрезке [0,1], то элементы f(x) = x и g(x) = 1 − x будут несравнимы. Возможность существования несравнимых элементов объясняет смысл термина «частично упорядоченное множество».

Минимальный/максимальный и наименьший/наибольший элементы

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

Элемент называется минимальным, если не существует элемента b < a. Другими словами, a — минимальный элемент, если для любого элемента либо b > a, либо b = a, либо b и a несравнимы. Элемент a называется наименьшим, если для любого элемента имеет место неравенство . Очевидно, всякий наименьший элемент является также минимальным, но обратное в общем случае неверно: минимальный элемент a может и не быть наименьшим, если существуют элементы b, не сравнимые с a.

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

Аналогично вводятся понятия максимального и наибольшего элементов.

Верхние и нижние грани

Пусть A — подмножество частично упорядоченного множества . Элемент называется верхней гранью A, если любой элемент не превосходит u. Аналогично вводится понятие нижней грани множества A.

Любой элемент, больший, чем некоторая верхняя грань A, также будет верхней гранью A. А любой элемент, меньший, чем некоторая нижняя грань A, также будет нижней гранью A. Эти соображения ведут к введению понятий наименьшей верхней грани и наибольшей нижней грани.

Специальные типы частично упорядоченных множеств

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

Пусть — частично упорядоченное множество. Если в M любые два элемента сравнимы, то множество M называется линейно упорядоченным. Линейно упорядоченное множество также называют совершенно упорядоченным, или просто, упорядоченным множеством. Таким образом, в линейно упорядоченном множество для любых двух элементов a и b имеет место одно и только одно из соотношений: либо a < b, либо a = b, либо b < a.

Также всякое линейно упорядоченное подмножество частично упорядоченного множества называют цепью, то есть цепь в частично упорядоченном множестве — такое его подмножество, в котором любые два элемента сравнимы.

Из приведенных выше примеров частично упорядоченных множеств только множество действительных чисел является линейно упорядоченным. Множество действительнозначных функций на отрезке [a,b] (при условии a < b), булеан (при ), натуральные числа с отношением делимости — не являются линейно упорядоченными.

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

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

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

Классический пример вполне упорядоченного множества — множество натуральных чисел . Утверждение о том, что любое непустое подмножество содержит наименьший элемент, равносильно принципу математической индукции. В качестве примера линейно упорядоченного, но не вполне упорядоченного множества можно привести множество неотрицательных чисел, упорядоченное естественным образом . Действительно, его подмножество {x:x > 1} не имеет наименьшего элемента.

Вполне упорядоченные множества играют исключительно важную роль в общей теории множеств.

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

К числу фундаментальных теорем о частично упорядоченных множествах относятся принцип максимума Хаусдорфа и лемма Куратовского-Цорна. Эти утверждения эквивалентны между собой и существенно опираются на так называемую аксиому выбора (в действительности, эквивалентны аксиоме выбора).

Типовая задача:

Является ли отношение, заданное на вершинах единичного куба в Rⁿ как aRb, если в координатах вершины a не больше единиц, чем в координатах вершины b, отношением частичного порядка? Решение: Отношение R является отношением частичного порядка, если оно: - рефлексивно, т.е. aRa; - антисиметрично, т.е. ; - транзитивно, т.е. . Для иллюстрации возьмём трёхмерный единичный куб с проставленными координатами вершин. Тогда, очевидно, для куба в пространстве Rⁿ вершину определяются набором из n символов . В n-мерном кубе всего К=2ⁿ вершин. На множестве вершин введём функцию , равную числу единиц в её n-наборе. Очевидно, что 0 ≤ N(Aj) ≤ n. Тогда отношение R можно определить как . Проверяем свойства: - рефлексивность: A_iRA_j достаточно очевидно, что этим свойством R обладает, т.к. ; - антисимметричность: Однако соотношение возможно не только при Ai = Aj (рисунок); - транзитивность: ? Действительно, если Таким образом, отношение не является отношением частичного порядка, так как оно не является антисимметричным.

Список использованных Интернет-ресурсов:

1. http://ru.wikipedia.org/wiki/Частично_упорядоченное_множество

2. http://bankzadach.ru/teoriya-mnozhestv-/otnoshenie-chastichnogo-poryadka-000136.html