Присоединяйтесь и знакомьтесь
Транзитивные бинарные отношения |
---|
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Join_and_meet.svg/220px-Join_and_meet.svg.png)
В математике , особенно теории порядка , соединение подмножества в множества частично упорядоченного является супремумом (наименьшая верхняя граница) обозначенный , встреча и аналогично - нижняя грань (наибольшая нижняя граница), обозначаемая В общем случае соединение и встреча подмножества частично упорядоченного множества не обязательно должны существовать. Соединение и встреча двойственны друг другу в отношении инверсии порядка.
Частично упорядоченный набор, в котором все пары имеют соединение, — это соединение-полурешетка . Двойственным образом частично упорядоченное множество, в котором все пары имеют пересечение, является пересечением-полурешеткой . Частично упорядоченное множество, которое является одновременно соединяющейся полурешеткой и встречной полурешеткой, представляет собой решетку . Решетка, в которой каждое подмножество, а не только каждая пара, имеет пересечение и соединение, является полной решеткой . Также возможно определить частичную решетку , в которой не все пары встречаются или соединяются, но операции (если они определены) удовлетворяют определенным аксиомам. [1]
Соединение/встреча подмножества полностью упорядоченного множества — это просто максимальный/минимальный элемент этого подмножества, если такой элемент существует.
Если подмножество частично упорядоченного множества также является направленным (вверх) множеством , то его соединение (если оно существует) называется направленным соединением или направленным супремумом . Двойственно, если является направленным вниз множеством, то его встреча (если она существует) является направленной встречей или направленной нижней границей .
Определения [ править ]
Частичный подход [ править ]
Позволять быть множеством с частичным порядком и разреши Элемент из называется встретиться (или наибольшая нижняя граница или самый низкий ) из и обозначается если выполняются следующие два условия:
- (то есть, является нижней границей ).
- Для любого если затем (то есть, больше или равно любой другой нижней границе ).
Соревнование не обязательно должно существовать, либо потому, что у пары вообще нет нижней границы, либо потому, что ни одна из нижних границ не превосходит все остальные. Однако, если произойдет встреча то оно единственное, так как если оба являются максимальными нижними границами затем и поэтому [2] Если не все пары элементов из встретимся, то встречу все равно можно рассматривать как частичную бинарную операцию над [1]
Если встреча существует, то она обозначается Если все пары элементов из встретиться, то встреча — это бинарная операция над и легко видеть, что эта операция удовлетворяет следующим трем условиям: Для любых элементов
- ( коммутативность ),
- ( ассоциативность ) и
- ( идемпотентность ).
Объединения определяются двойственно : объединение если он существует, обозначается Элемент из это присоединяйтесь (или наименьшая верхняя граница или высший ) из в если выполняются следующие два условия:
- (то есть, является верхней границей ).
- Для любого если затем (то есть, меньше или равно любой другой верхней границе ).
алгебраический подход Универсальный
По определению, бинарная операция на съемочной площадке является соревнованием , если оно удовлетворяет трем условиям a , b и c . Пара тогда это встреча-полурешетка . Более того, тогда мы можем определить бинарное отношение на A , заявив, что если и только если Фактически это отношение представляет собой частичный порядок на Действительно, для любых элементов
- с по с ;
- если затем по ; и
- если затем с того времени по б .
И встречи, и соединения в равной степени удовлетворяют этому определению: пара связанных операций встречи и соединения дает частичные заказы, которые являются обратными друг другу. При выборе одного из этих ордеров в качестве основного также фиксируется, какая операция считается встречей (тот, что дает тот же заказ), а какая — объединением (другой).
Эквивалентность подходов [ править ]
Если — частично упорядоченное множество , такое, что каждая пара элементов в встретится, тогда действительно если и только если поскольку в последнем случае действительно является нижней границей и с тех пор является максимальной нижней границей тогда и только тогда, когда она является нижней границей. Таким образом, частичный порядок, определяемый встречей в подходе универсальной алгебры, совпадает с исходным частичным порядком.
И наоборот, если представляет собой встречу-полурешетку , а частичный порядок определяется как в подходе универсальной алгебры, и для некоторых элементов затем является наибольшей нижней границей относительно с и поэтому Сходным образом, и если это еще одна нижняя граница затем откуда Таким образом, существует встреча, определяемая частичным порядком, заданным исходной встречей, и эти две встречи совпадают.
Другими словами, два подхода дают по существу эквивалентные концепции, набор, оснащенный как бинарным отношением, так и бинарной операцией, так что каждая из этих структур определяет другую и удовлетворяет условиям частичного порядка или соответствия соответственно.
Встречается с общими подмножествами [ править ]
Если является встречей-полурешеткой, то встречу можно расширить до четко определенной встречи любого непустого конечного множества с помощью метода, описанного в итеративных бинарных операциях . Альтернативно, если собрание определяет или определяется частичным порядком, некоторые подмножества действительно имеют инфимум относительно этого, и разумно рассматривать такой инфимум как часть подмножества. Для непустых конечных подмножеств оба подхода дают один и тот же результат, поэтому любой из них можно использовать в качестве определения соответствия. В случае, когда каждое подмножество на самом деле встречается представляет собой полную решетку ; подробнее см. полнота (теория порядка) .
Примеры [ править ]
Если какой-то набор мощности частично упорядочивается обычным способом (по ) тогда соединения являются объединениями, а встречи — пересечениями; в символах, (где сходство этих символов может быть использовано как мнемоника для запоминания того, что обозначает соединение/супремум и обозначает встречу / минимум [примечание 1] ).
В более общем плане предположим, что это семейство подмножеств некоторого множества который частично упорядочен Если замкнуто относительно произвольных объединений и произвольных пересечений и если принадлежать затем Но если тогда не закрыто под союзами существует в тогда и только тогда, когда существует единственное -самый маленький такой, что Например, если затем тогда как если затем не существует, поскольку множества являются единственными верхними границами в это может быть наименьшая верхняя граница но и Если затем не существует, поскольку нет верхней границы в
См. также [ править ]
Примечания [ править ]
- ^ Перейти обратно: а б Гретцер, Джордж (21 ноября 2002 г.). Общая теория решеток: Второе издание . Springer Science & Business Media. п. 52. ИСБН 978-3-7643-6996-5 .
- ^ Хачтел, Гэри Д.; Соменци, Фабио (1996). Алгоритмы логического синтеза и проверки . Академическое издательство Клювер. п. 88. ИСБН 0792397460 .
- ^ Сразу можно определить, что супремумы и инфимумы в этом каноническом простом примере являются соответственно. Сходство символа к и из к таким образом, может использоваться как мнемоника для запоминания того, что в наиболее общих условиях обозначает супремум (потому что супремум — это граница сверху, как и находится «выше» и ) пока обозначает нижнюю границу (поскольку нижняя граница является границей снизу, как и ниже" и ). Это также можно использовать, чтобы запомнить, обозначаются ли встречи/соединения или через Интуиция подсказывает, что « соединение » двух множеств должно привести к их объединению. который похож на поэтому «объединиться» должно обозначаться Аналогично, два множества должны « встретиться » на пересечении. который похож на поэтому «встретиться» должно обозначаться
Ссылки [ править ]
- Дэйви, бакалавр; Пристли, ХА (2002). Введение в решетки и порядок (2-е изд.). Кембридж: Издательство Кембриджского университета . ISBN 0-521-78451-4 . Збл 1002.06001 .
- Викерс, Стивен (1989). Топология через логику . Кембриджские трактаты по теоретической информатике. Том. 5. ISBN 0-521-36062-5 . Збл 0668.54001 .