Бинарные отношения | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
« ✓ » указывает, что свойство столбца требуется в определении строки. Например, определение отношения эквивалентности требует, чтобы оно было симметричным. Все определения молчаливо требуют транзитивности и рефлексивности . |
В математике , в частности , порядок теории , то присоединиться из подмножества S о наличии частично упорядоченного множества P является гранью ( не менее верхняя граница) из S , обозначаемый ⋁ S , и , аналогично, встречаются из S является нижняя грань (точная нижняя граница), обозначаемое ⋀ S . В общем, соединение и встреча подмножества частично упорядоченного набора может не существовать. Join и meet двойственны друг другу относительно инверсии порядка.
Частично упорядоченное множество, в котором все пары соединены, является полурешёткой соединения . Двойственно частично упорядоченное множество, в котором все пары пересекаются, является полурешёткой встреч . Частично упорядоченное множество, которое одновременно является полурешеткой соединения и полурешеткой пересечения, является решеткой . Решетка, в которой каждое подмножество, а не только каждая пара, имеет пересечение, а соединение является полной решеткой . Также возможно определить частичную решетку , в которой не все пары имеют пересечение или соединение, но операции (если они определены) удовлетворяют определенным аксиомам. [1]
Соединение / встреча подмножества полностью упорядоченного множества - это просто его максимальный / минимальный элемент, если такой элемент существует.
Если подмножество S частично упорядоченного множества P также является (восходящим) направленным набором , то его соединение (если оно существует) называется направленным соединением или направленной супремумом . Двойственно, если S - направленное вниз множество, то его встреча (если она существует) - это направленная встреча или направленная нижняя грань .
Подход частичного заказа
Пусть быть набор с частичным порядком ≤, и пусть х и у - два элемента в A . Элемент z из A является пересечением (или точной нижней границей, или точной гранью) x и y , если выполняются следующие два условия:
- z ≤ x и z ≤ y (то есть z является нижней границей x и y ).
- Для любого w в A , такого что w ≤ x и w ≤ y , мы имеем w ≤ z (то есть z больше или равно любой другой нижней границе x и y ).
Если существует пересечение x и y , то оно уникально, поскольку если и z, и z ′ являются точными нижними границами x и y , то z ≤ z ′ и z ′ ≤ z , и, следовательно, z = z ′ . Если встреча действительно существует, она обозначается x ∧ y . Некоторым парам элементов в A может не хватать пересечения либо потому, что у них вообще нет нижней границы, либо потому, что ни одна из их нижних границ не превосходит все остальные. Если все пары элементов из A имеют пересечение, то встреча является бинарной операцией на A , и легко видеть, что эта операция удовлетворяет следующим трем условиям: для любых элементов x , y и z в A ,
- а. x ∧ y = y ∧ x ( коммутативность ),
- б. x ∧ ( y ∧ z ) = ( x ∧ y ) ∧ z ( ассоциативность ) и
- c. x ∧ x = x ( идемпотентность ).
Соединения определяются двойственно, и соединение x и y в A (если оно существует) обозначается x ∨ y . Если не все пары элементов из A имеют концов (соответственно, присоединиться к ), то встречается (соответственно, присоединиться) все еще могут рассматриваться в качестве частичной бинарной операции на A .
Универсальный алгебраический подход
По определению, бинарная операция ∧ на множестве A является встречей, если она удовлетворяет трем условиям a , b и c . Тогда пара ( A , ∧) является встречно-полурешеткой . Более того, затем мы можем определить бинарное отношение ≤ на A , указав, что x ≤ y тогда и только тогда, когда x ∧ y = x . На самом деле, это отношение является частичным порядком на A . Действительно, для любых элементов х , у и г в А ,
- x ≤ x , поскольку x ∧ x = x по c ;
- если x ≤ y и y ≤ x , то x = x ∧ y = y ∧ x = y по a ; а также
- если x ≤ y и y ≤ z , то x ≤ z , поскольку тогда x ∧ z = ( x ∧ y ) ∧ z = x ∧ ( y ∧ z ) = x ∧ y = x по b .
Обратите внимание, что и встречи, и соединения в равной степени удовлетворяют этому определению: пара связанных операций встречи и соединения дает частичные порядки, противоположные друг другу. Выбирая один из этих порядков в качестве основного, также фиксируется, какая операция считается встречей (та, которая дает такой же порядок), а какая - объединением (другая).
Эквивалентность подходов
Если ( A , ≤) - частично упорядоченное множество , такое, что каждая пара элементов в A имеет пересечение, тогда действительно x ∧ y = x тогда и только тогда, когда x ≤ y , поскольку в последнем случае действительно x является нижней границей из й и у , а так как очевидно , х является наибольшим нижней границей , если и только если она является нижней границей. Таким образом, частичный порядок, определяемый встречей в подходе универсальной алгебры, совпадает с исходным частичным порядком.
Наоборот, если ( A , ∧) является встречно-полурешеткой , а частичный порядок ≤ определяется, как в подходе универсальной алгебры, и z = x ∧ y для некоторых элементов x и y в A , то z является точной нижней границей из х и у по отношению к ≤, так как
- z ∧ x = x ∧ z = x ∧ ( x ∧ y ) = ( x ∧ x ) ∧ y = x ∧ y = z
и поэтому z ≤ x . Аналогично, z ≤ y , и если w - еще одна нижняя граница x и y , то w ∧ x = w ∧ y = w , откуда
- ж ∧ г = ш ∧ ( х ∧ у ) = ( ш ∧ х ) ∧ у = ш ∧ у = ш .
Таким образом, существует встреча, определяемая частичным порядком, определенным исходной встречей, и эти две встречи совпадают.
Другими словами, эти два подхода дают по существу эквивалентные концепции, набор, снабженный как бинарным отношением, так и бинарной операцией, так что каждая из этих структур определяет другую и удовлетворяет условиям для частичных порядков или соответствия, соответственно.
Встречи общих подмножеств
Если ( A , ∧) является полурешеткой встречи, то встреча может быть расширена до точно определенной встречи любого непустого конечного множества с помощью техники, описанной в повторяющихся бинарных операциях . В качестве альтернативы, если meet определяет или определяется частичным порядком, некоторые подмножества A действительно имеют нижнюю границу в отношении этого, и разумно рассматривать такую нижнюю грань как встречу подмножества. Для непустых конечных подмножеств оба подхода дают один и тот же результат, и поэтому любой из них может использоваться как определение meet. В случае, когда каждое подмножество A имеет пересечение, фактически ( A , ≤) является полной решеткой ; подробнее см. полнота (теория порядка) .
Заметки
- ^ Grätzer 1996 , стр. 52 .
Рекомендации
- Дэйви, BA; Пристли, HA (2002). Введение в решетки и порядок (2-е изд.). Кембридж: Издательство Кембриджского университета . ISBN 0-521-78451-4. Zbl 1002.06001 .
- Викерс, Стивен (1989). Топология через логику . Кембриджские тракты в теоретической информатике. 5 . ISBN 0-521-36062-5. Zbl 0668.54001 .