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

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

В математике , в частности , порядок теории , то присоединиться из подмножества S о наличии частично упорядоченного множества P является гранью ( не менее верхняя граница) из S , обозначаемый ⋁ S , и , аналогично, встречаются из S является нижняя грань (точная нижняя граница), обозначаемое ⋀ S . В общем, соединение и встреча подмножества частично упорядоченного набора может не существовать. Join и meet двойственны друг другу относительно инверсии порядка.

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

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

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

Подход частичного заказа [ править ]

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

1. z ≤ x и z ≤ y (т. е. z является нижней границей x и y ).
2. Для любого 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 , y иz в 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 , ≤) является полной решеткой ; подробности см.полнота (теория порядка) .

Заметки [ править ]

Ссылки [ править ]