Грани множеств

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

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

Аналогично определяются наименьший и минимальный элементы, а именно: наименьший элемент а ´ х для "хÎА, а минимальный элемент – это такой, что либо а ´ х для "хÎА, либо а и х несравнимы.

Покажем, что наибольший (и наименьший) элемент, если он существует, единственен. Предположим, что существуют два наибольших элемента: а₁ и а₂. Тогда должны выполняться два условия: а₁ ´ а₂ и обратное: а₂ ´ а₁. Тогда, в силу антисимметричности, имеем а₁=а₂.

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

NB Поскольку на одном и том же множестве могут быть определены разные отношения порядка – например, на множестве натуральных чисел естественный числовой порядок и отношение делимости, то всегда следует уточнять, о каком порядке говорится, когда используются наибольшие, наименьшие, минимальные и максимальные элементы. Пример: лексикографический порядок 1<10<100<2<… 001<002<010<100…

Пусть (A, ´) – упорядоченное множество и ВÍА. Элемент аÎА называется верхней гранью(мажорантой) множества В, если для всех х из В имеет место х ´ а.

Нижней гранью (минорантой) называется элемент а, если для всех х имеет место а ´ х.

Наименьший элемент из множества всех верхних граней называется supremum (точная верхнея грань), а наибольший элемент из множества нижних граней – infinum (точная нижняя грань). Обозначения: Sup B, Inf B.

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

D infDÎD

А максимальные А В=supDÎD A E = supFÏF

элементы G

наименьший F

элемент линейный порядок

O В О С O = infFÏF C

Пример.

Рассмотрим множество точек плоскости с заданной фиксированной декартовой системой координат. Отношение порядка на множестве точек плоскости определим следующим образом: (a, b) ´ (c, d), если и только если a≤c & b≤d. Очевидно, введённое отношение является отношением нестрогого частичного порядка. (Примечание: на прямых линиях данное отношение индуцирует линейный порядок.)

а) Треугольник на рисунке – точка (0,0) является наименьшим элементом. Наибольшего нет. Максимальные элементы – прямая АВ.

б) (0,0) – inf D, B=sup D, обе точки принадлежат множеству.

в) (0,0) и Е – точные грани, но они в данном примере не принадлежат множеству.

Упорядоченное множество (М, ´) называют вполне упорядоченным, если любое его непустое подмножество имеет минимальный элемент.

Множество натуральных чисел – вполне упорядочено, а целых – нет.

Для упорядоченных множеств справедлив принцип двойственности. Он заключается в том, что любое утверждение, справедливое для порядка ´, останется справедливым и для двойственного порядка µ, если в нём (утверждении) а) порядок заменить на двойственный б) наименьший (минимальный) элемент заменить на наибольший (максимальный) и наоборот в) инфинум заменить на супремум и наоборот.

Говорят также и о взаимно-двойственных определениях – если в любом определении, связанном с упорядоченным множеством, произвести взаимные замены согласно приведённым правилам, то получится новое определение, называемое двойственным к исходному. Так, определение наибольшего элемента двойственно к определению наименьшего. Таким образом можно уменьшить число доказываемых теорем.