Присоединяйтесь и знакомьтесь
-
Определения и свойства
- Объединение подмножества частично упорядоченного множества является высшей точкой (наименьшей верхней границей) подмножества.
- Встреча подмножества частично упорядоченного множества является нижней границей (наибольшей нижней границей).
- Объединение и встреча могут не существовать для всех пар элементов.
- Частично упорядоченное множество, в котором все пары имеют соединение, называется полурешеткой соединения.
- Частично упорядоченное множество, в котором все пары пересекаются, называется полурешеткой встречи.
- Частично упорядоченное множество, представляющее собой как соединяющую, так и встречающуюся полурешетку, является решеткой.
- Полная решетка — это решетка, в которой каждое подмножество имеет пересечение и соединение.
-
Подход с частичным упорядочением
- Соответствие (или наибольшая нижняя граница) между двумя элементами определяется как элемент, который больше или равен обоим элементам и больше или равен любой другой нижней границе.
- Соответствие может не существовать, но если оно существует, то уникально.
- Если все пары элементов имеют соответствие, то это бинарная операция, удовлетворяющая коммутативности, ассоциативности и идемпотентности.
-
Универсальный алгебраический подход
- Бинарная операция на множестве считается удовлетворительной, если удовлетворяет трем условиям.
- Эта пара (A, ∧) является встречающейся полурешеткой.
- Бинарное отношение ≤ на A определяется как x ≤ y тогда и только тогда, когда x ∧ y = x.
- Это отношение является частичным порядком на A.
-
Эквивалентность подходов
- Если (A, ≤) является частично упорядоченным множеством, то x ∧ y = x тогда и только тогда, когда x ≤ y.
- Если (A, ∧) является встречающейся полурешеткой, то z = x ∧ y является наибольшей нижней границей x и y в отношении ≤.
- Эти два подхода дают эквивалентные концепции.
-
Соответствие общим подмножествам
- Если (A, ∧) является встречающейся полурешеткой, то встреча может быть расширена до непустого конечного множества.
- Если соответствие определяет частичный порядок, то некоторые подмножества имеют нижнюю границу, которую можно рассматривать как соответствие подмножества.
-
Примеры
- В частично упорядоченном множестве ℘(X) соединения — это союзы, а встречи — это пересечения.
- В более общем случае, если F — это семейство подмножеств, частично упорядоченное ⊆, и F замкнуто при объединениях и пересечениях, то A, B, (Fi) ∈ F.
-
Основные операции над множествами
- A ∨ B = A ∪ B
- A ∧ B = A ∩ B
- ⋁ я ∈ I Fя = ⋃ я ∈ I Fя
- ⋀ я ∈ I Fя = ⋂ я ∈ I Fя
-
Условия существования A ∨ B
- A ∨ B существует в (F, ⊆) тогда и только тогда, когда существует уникальный J ∈ F такой, что A ∪ B ⊆ J
-
Примеры
- Если F = { {1}, {2}, {1, 2, 3}, R }, то {1} ∨ {2} = {1, 2, 3}
- Если F = { {1}, {2}, {1, 2, 3}, {0, 1, 2}, R }, то {1} ∨ {2} не существует, так как {0, 1, 2} и {1, 2, 3} являются единственными верхними границами {1} и {2}
- Если F = { {1}, {2}, {0, 2, 3}, {0, 1, 3} }, то {1} ∨ {2} не существует, так как нет верхней границы {1} и {2}