Определение: Бинарное отношение δ⊆A*A определенное на множестве А есть отношение частичного порядка (обозначается a ≤ b), если оно удовлетворяет следующим аксиомам:

1) a ≤ a – рефлексивность
2) a ≤ b & b ≤ a → a = b — антисимметричность.
3) a ≤ b & b ≤ c → a ≤ c – транзитивность.

Пример:
1) обычное числовое отношение a ≤ b есть отношение частичного порядка.
2) Отношение включения A ⊆ B для координат в множестве U есть отношение частичного порядка.

Определение: Элементы a и b из А сравнимы, если a ≤ b или b ≤ a. В противном случае элементы a и b несравнимы.

Определение: Частично упорядоченное множество (ЧУМ) есть пара (А, ≤), где А – есть множество и a ≤ b есть отношение частичного порядка, определенное на А.

Замечание: Частично упорядоченное множество, особенно конечное, удобно изображать диаграммами (Хасса).
Введем отношение «≥», положив a ≥ b ↔ b ≤ a. Отношение «≥» есть отношение частичного порядка.

Утверждение:(принцип двойственности). Если в верном утверждении для частичного упорядоченного множества (А, ≤) знак «≤» заменить на «≥», то получим тоже верное отношение. Введем отношение строгого неравенства a < b ↔ a ≤ b & a ≠ b, a > b ↔ b < a. Из аксиом частичного порядка можно вывести справедливость следующих отношений для любых ∀a, b, c ∈ A. 1) a ≥ a 2) a < b & b < c ↔ a < c. Для отношений «<» и «>» справедлив принцип двойственности.

Определение: ЧУМ (А, <), для которого ∀a, b ∈ A (a ≤ b или b ≤ a), называется линейно упорядоченным. Замечание: линейно упорядочены, например, вещественные числа.

Определение: Элемент O принадлежащий A ЧУМа называется наименьшим, если ∀x ∈ A, x ≥ O, элемент I принадлежащий A называется наибольшим, если для ∀x ∈ A, x ≤ I.

Наибольший и наименьший элементы в ЧУМе называются универсальными границами.

Утверждение: Всякое ЧУМ (А, ≤) имеет не более одного наименьшего и не более одного наибольшего элемента.

Доказательство: пусть O и O’ есть два наименьших элемента в (А, ≤), тогда O ≤ O’ ибо O есть наименьший элемент в А. Аналогично с O’ ≤ O ибо О’ также наименьший элемент в А. отсюда следует, что O = O’ по аксиоме 2 ЧУМа. Для наибольшего элемента Доказательство аналогично.

Определение: Элемент L из А минимален в А, если не ∃ x ∈ A такого, что x < L. Элемент M из А максимален в А, если не существует x из A, что x > M.

Замечание: в ЧУМ возможно несколько максимальных и минимальных элементов. Наименьший элемент является минимальным. Наибольший элемент является максимальным.

Определение: В ЧУМе (А, ≤) элемент а’ непосредственно следует за а (обозначается а ‹ a’) если а < а’ (в обычном смысле) и ¬∃ существует x из A, a < x < a’. Утверждение: Если в конечном ЧУМе (A, ≤) имеет место a < b, то множество А содержит цепь a = x₁23<…n=b
Без доказательства.

Определение: Пусть (A, ≤) есть частично упорядоченное множество и множество B ⊆ A
1) элемент а ∈ А – есть верхняя грань для В, если для ∀b ∈ B: b ≤ a
2) совокупность B’ всех верхних граней для B называется верхний конус для B.
3) элемент b’ ∈ B’ — есть точная верхняя грань для B (обозначается sup B) если b’ — есть наименьший элемент в B’.
4) элемент a ∈ A есть нижняя грань в B, если для любого ∀b∈B a ≤ b.
5) совокупность В^♦ всех нижних граней для В называется нижним конусом для В.
6) элемент b^♦ ∈ B^♦ есть точная верхняя грань для В (inf B), если b^♦ есть наибольший элемент В^♦..

Лемма (Цорна): Если в ЧУМе (А, ≤) любая цепь имеет верхнюю(нижнюю) грань, то А имеет максимальный(минимальный) элемент.

Комментарии запрещены.