Присоединяйтесь и знакомьтесь - Join and meet

Этот Диаграмма Хассе изображает частично упорядоченный набор из четырех элементов - а, б, то максимальный элемент равно объединению а и б (а ∨ б) и минимальный элемент равно встрече а и б (а ∧ б). Соединение / соединение максимального / минимального элемента и другого элемента является максимальным / минимальным элементом, и, наоборот, соединение / соединение максимального / минимального элемента с другим элементом является другим элементом. Таким образом, каждая пара в этом poset имеет как пересечение, так и соединение, и poset может быть классифицирован как решетка (теория порядка).

В математика, конкретно теория порядка, то присоединиться из подмножество S из частично заказанный набор п это супремум (наименьшая верхняя граница) S, обозначается ⋁S, и аналогично встретить из S это инфимум (точная нижняя грань), обозначаемая ⋀S. В общем, объединение и встреча подмножества частично упорядоченного набора может не существовать. Присоединяйтесь и встречайтесь двойной друг к другу относительно инверсии порядка.

Частично упорядоченный набор, в котором все пары соединены, называется стыковочная полурешетка. Таким образом, частично упорядоченное множество, в котором все пары пересекаются, называется встречная полурешетка. Частично упорядоченное множество, которое одновременно является полурешеткой соединения и встречной полурешеткой, является решетка. Решетка, в которой каждое подмножество, а не только каждая пара, имеет пересечение, а соединение - это полная решетка. Также можно определить частичная решетка, в котором не все пары имеют пересечение или соединение, но операции (если они определены) удовлетворяют определенным аксиомам.[1]

Соединение / встреча подмножества полностью заказанный набор просто его максимальный / минимальный элемент, если такой элемент существует.

Если подмножество S частично упорядоченного набора п также (вверх) направленный набор, то его соединение (если оно существует) называется направленное присоединение или же направленный супремум. Вдвойне, если S направленное вниз множество, то его пересечение (если оно существует) есть направленная встреча или же направленный инфимум.

Подход частичного заказа

Позволять А быть набором с частичный заказ ≤, и пусть Икс и у быть двумя элементами в А. Элемент z из А является встречей (или наибольшей нижней границей или точной гранью) Икс и у, если выполнены следующие два условия:

  1. z ≤ Икс и z ≤ у (т.е. z это нижняя граница Икс и у).
  2. Для любого ш в А, так что ш ≤ Икс и ш ≤ у, у нас есть ш ≤ z (т.е. z больше или равно любой другой нижней границе Икс и у).

Если есть встреча Икс и у, то он уникален, так как если оба z и z′ - точные нижние границы Икс и у, тогда z ≤ z′ и z′ ≤ z, и поэтому z = z′. Если встреча существует, она обозначается Икс ∧ у.Некоторые пары элементов в А могут не иметь соответствия, либо потому, что у них вообще нет нижней границы, либо потому что ни одна из их нижней границы не превышает всех остальных. Если все пары элементов из А встретиться, тогда встреча - это бинарная операция на А, и легко видеть, что эта операция удовлетворяет следующим трем условиям: Для любых элементов Икс, у, и z в А,

а. Икс ∧ у = у ∧ Икс (коммутативность ),
б. Икс ∧ (у ∧ z) = (Икс ∧ у) ∧ z (ассоциативность ), и
c. Икс ∧ Икс = Икс (идемпотентность ).

Объединения определяются двойственно, а объединение Икс и у в А (если он существует) обозначается Икс ∨ у. Если не все пары элементов из А иметь встречу (соответственно, присоединиться), то встреча (соответственно, присоединение) все еще может рассматриваться как частичный бинарная операция на А.

Универсальный алгебраический подход

По определению бинарная операция ∧ на наборе А это встретить если он удовлетворяет трем условиям а, б, и c. Пара (А, ∧) тогда встречная полурешетка. Более того, тогда мы можем определить бинарное отношение ≤ на А, заявив, что Икс ≤ у если и только если Икс ∧ у = Икс. Фактически, это отношение есть частичный заказ на А. Действительно, для любых элементов Икс, у, и z в А,

  • Икс ≤ Икс, поскольку Икс ∧ Икс = Икс к c;
  • если Икс ≤ у и у ≤ Икс, тогда Икс = Икс ∧ у = у ∧ Икс = у к а; и
  • если Икс ≤ у и у ≤ z, тогда Икс ≤ z, с того времени Икс ∧ z = (Икс ∧ у) ∧ z = Икс ∧ (у ∧ z) = Икс ∧ у = Икс к б.

Обратите внимание, что и встречи, и соединения в равной степени удовлетворяют этому определению: пара связанных операций встречи и соединения дает частичные порядки, противоположные друг другу. Выбирая один из этих порядков в качестве основного, также фиксируется, какая операция считается встречей (та, которая дает такой же порядок), а какая - объединением (другая).

Эквивалентность подходов

Если (А, ≤) является частично заказанный набор, такие, что каждая пара элементов в А есть встреча, тогда действительно Икс ∧ у = Икс если и только если Икс ≤ у, поскольку в последнем случае действительно Икс это нижняя граница Икс и у, и поскольку ясно Икс это величайший нижняя граница тогда и только тогда, когда это нижняя граница. Таким образом, частичный порядок, определяемый встречей в подходе универсальной алгебры, совпадает с исходным частичным порядком.

Наоборот, если (А, ∧) является встречная полурешетка, а частичный порядок ≤ определяется как в подходе универсальной алгебры, и z = Икс ∧ у для некоторых элементов Икс и у в А, тогда z является точной нижней границей Икс и у относительно ≤, так как

z ∧ Икс = Икс ∧ z = Икс ∧ (Икс ∧ у) = (Икс ∧ Икс) ∧ у = Икс ∧ у = z

и поэтому z ≤ Икс. По аналогии, z ≤ у, и если ш это еще одна нижняя граница Икс и у, тогда ш ∧ Икс = ш ∧ у = wоткуда

ш ∧ z = ш ∧ (Икс ∧ у) = (ш ∧ Икс) ∧ у = ш ∧ у = ш.

Таким образом, существует встреча, определяемая частичным порядком, определенным исходной встречей, и две встречи совпадают.

Другими словами, эти два подхода дают по существу эквивалентные концепции, набор, снабженный как бинарным отношением, так и бинарной операцией, так что каждая из этих структур определяет другую и удовлетворяет условиям для частичных порядков или соответствия, соответственно.

Встречи общих подмножеств

Если (А, ∧) является полурешеткой, то встреча может быть продолжена до корректно определенной встречи любого непустой конечный набор, по методике, описанной в повторяющиеся двоичные операции. В качестве альтернативы, если встреча определяет или определяется частичным порядком, некоторые подмножества А действительно имеют инфимум по этому поводу, и разумно рассматривать такую ​​инфимум как встречу подмножества. Для непустых конечных подмножеств оба подхода дают один и тот же результат, и поэтому любой из них может использоваться как определение meet. В случае, когда каждый подмножество А есть встреча, на самом деле (А, ≤) является полная решетка; подробности см. полнота (теория порядка).

Примечания

  1. ^ Grätzer 1996, п.52.

Рекомендации

  • Davey, B.A .; Пристли, Х.А. (2002). Введение в решетки и порядок (2-е изд.). Кембридж: Издательство Кембриджского университета. ISBN  0-521-78451-4. Zbl  1002.06001.
  • Викерс, Стивен (1989). Топология через логику. Кембриджские тракты в теоретической информатике. 5. ISBN  0-521-36062-5. Zbl  0668.54001.