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

Концепция в теории порядка

Эта диаграмма Хассе изображает частично упорядоченное множество с четырьмя элементами: a , b , максимальный элемент a b , равный объединению a и b , и минимальный элемент a b , равный пересечению a и b . Объединение/пересечение максимального/минимального элемента и другого элемента является максимальным/минимальным элементом, и наоборот, объединение/пересечение максимального/минимального элемента с другим элементом является другим элементом. Таким образом, каждая пара в этом частично упорядоченном множестве имеет как объединение, так и объединение, и частично упорядоченное множество может быть классифицировано как решетка . ${\displaystyle \vee }$ ${\displaystyle \wedge }$

В математике , в частности, в теории порядка , объединение подмножества частично упорядоченного множества является супремумом ( наименьшим верхним пределом) обозначенного и аналогично, встреча является инфимумом (наибольшей нижней границей), обозначенного В общем случае объединение и встреча подмножества частично упорядоченного множества не обязаны существовать. Объединение и встреча являются двойственными друг другу относительно инверсии порядка. ${\displaystyle S}$ ${\displaystyle P}$ ${\displaystyle S,}$ ${\textstyle \bigvee S,}$ ${\displaystyle S}$ ${\textstyle \bigwedge S.}$

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

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

Если подмножество частично упорядоченного множества также является (вверх) направленным множеством , то его соединение (если оно существует) называется направленным соединением или направленным супремумом . Двойственно, если — направленное вниз множество, то его встреча (если оно существует) называется направленным встречей или направленным инфимумом . ${\displaystyle S}$ ${\displaystyle P}$ ${\displaystyle S}$

Определения

Частичный подход

Пусть будет множеством с частичным порядком и пусть элемент называется ${\displaystyle A}$ ${\displaystyle \,\leq ,\,}$ ${\displaystyle x,y\in A.}$ ${\displaystyle m}$ ${\displaystyle A}$встретиться (илинаибольшая нижняя граница илиинфимум )и обозначается ,если выполняются следующие два условия: ${\displaystyle x{\text{ and }}y}$ ${\displaystyle x\wedge y,}$

1. ${\displaystyle m\leq x{\text{ and }}m\leq y}$(то есть является нижней границей ) . ${\displaystyle m}$ ${\displaystyle x{\text{ and }}y}$
2. Для любого , если то (то есть больше или равно любой другой нижней границе ). ${\displaystyle w\in A,}$ ${\displaystyle w\leq x{\text{ and }}w\leq y,}$ ${\displaystyle w\leq m}$ ${\displaystyle m}$ ${\displaystyle x{\text{ and }}y}$

Встреча не обязательно должна существовать, либо поскольку пара вообще не имеет нижней границы, либо поскольку ни одна из нижних границ не больше всех остальных. Однако, если есть встреча, то она уникальна, поскольку если оба являются наибольшими нижними границами, то и, таким образом, ^[2] Если не все пары элементов из имеют встречу, то встреча все еще может рассматриваться как частичная бинарная операция над ^[1] ${\displaystyle x{\text{ and }}y,}$ ${\displaystyle m{\text{ and }}m^{\prime }}$ ${\displaystyle x{\text{ and }}y,}$ ${\displaystyle m\leq m^{\prime }{\text{ and }}m^{\prime }\leq m,}$ ${\displaystyle m=m^{\prime }.}$ ${\displaystyle A}$ ${\displaystyle A.}$

Если встреча существует, то это обозначается Если все пары элементов из имеют встречу, то встреча является бинарной операцией над и легко видеть, что эта операция удовлетворяет следующим трем условиям: Для любых элементов ${\displaystyle x\wedge y.}$ ${\displaystyle A}$ ${\displaystyle A,}$ ${\displaystyle x,y,z\in A,}$

1. ${\displaystyle x\wedge y=y\wedge x}$( коммутативность ),
2. ${\displaystyle x\wedge (y\wedge z)=(x\wedge y)\wedge z}$( ассоциативность ) и
3. ${\displaystyle x\wedge x=x}$( идемпотентность ).

Соединения определяются двойственно с соединением, если оно существует, обозначаемым как Элемент - это ${\displaystyle x{\text{ and }}y,}$ ${\displaystyle x\vee y.}$ ${\displaystyle j}$ ${\displaystyle A}$присоединиться (илинаименьшая верхняя граница илисупремум ) изв ,если выполняются следующие два условия: ${\displaystyle x{\text{ and }}y}$ ${\displaystyle A}$

1. ${\displaystyle x\leq j{\text{ and }}y\leq j}$(то есть является верхней границей ) . ${\displaystyle j}$ ${\displaystyle x{\text{ and }}y}$
2. Для любого , если то (то есть меньше или равно любой другой верхней границе ). ${\displaystyle w\in A,}$ ${\displaystyle x\leq w{\text{ and }}y\leq w,}$ ${\displaystyle j\leq w}$ ${\displaystyle j}$ ${\displaystyle x{\text{ and }}y}$

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

По определению, бинарная операция на множестве является встречей , если она удовлетворяет трем условиям a , b , и c . Тогда пара является встречей-полурешеткой . Более того, мы можем определить бинарное отношение на A , заявив, что тогда и только тогда, когда На самом деле, это отношение является частичным порядком на Действительно, для любых элементов ${\displaystyle \,\wedge \,}$ ${\displaystyle A}$ ${\displaystyle (A,\wedge )}$ ${\displaystyle \,\leq \,}$ ${\displaystyle x\leq y}$ ${\displaystyle x\wedge y=x.}$ ${\displaystyle A.}$ ${\displaystyle x,y,z\in A,}$

• ${\displaystyle x\leq x,}$так как через c ; ${\displaystyle x\wedge x=x}$
• если то через а ; и ${\displaystyle x\leq y{\text{ and }}y\leq x}$ ${\displaystyle x=x\wedge y=y\wedge x=y}$
• если то с тех пор то по б . ${\displaystyle x\leq y{\text{ and }}y\leq z}$ ${\displaystyle x\leq z}$ ${\displaystyle x\wedge z=(x\wedge y)\wedge z=x\wedge (y\wedge z)=x\wedge y=x}$

И meets, и joins в равной степени удовлетворяют этому определению: пара связанных операций meet и join дают частичные порядки, которые являются обратными друг другу. При выборе одного из этих порядков в качестве основного также фиксируется, какая операция считается meet (та, которая дает тот же порядок), а какая — join (другая).

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

Если — частично упорядоченное множество , такое, что каждая пара элементов в имеет meet, то действительно тогда и только тогда, когда так как в последнем случае действительно является нижней границей и так как является точной нижней границей тогда и только тогда, когда это нижняя граница. Таким образом, частичный порядок, определяемый meet в подходе универсальной алгебры, совпадает с исходным частичным порядком. ${\displaystyle (A,\leq )}$ ${\displaystyle A}$ ${\displaystyle x\wedge y=x}$ ${\displaystyle x\leq y,}$ ${\displaystyle x}$ ${\displaystyle x{\text{ and }}y,}$ ${\displaystyle x}$

Наоборот, если есть встреча-полурешетка , а частичный порядок определяется как в подходе универсальной алгебры, и для некоторых элементов то есть точная нижняя граница относительно так как и поэтому Аналогично, и если есть другая нижняя граница то откуда Таким образом, существует встреча, определяемая частичным порядком, определяемым исходной встречей, и эти две встречи совпадают. ${\displaystyle (A,\wedge )}$ ${\displaystyle \,\leq \,}$ ${\displaystyle z=x\wedge y}$ ${\displaystyle x,y\in A,}$ ${\displaystyle z}$ ${\displaystyle x{\text{ and }}y}$ ${\displaystyle \,\leq ,\,}$ $${\displaystyle z\wedge x=x\wedge z=x\wedge (x\wedge y)=(x\wedge x)\wedge y=x\wedge y=z}$$ ${\displaystyle z\leq x.}$ ${\displaystyle z\leq y,}$ ${\displaystyle w}$ ${\displaystyle x{\text{ and }}y,}$ ${\displaystyle w\wedge x=w\wedge y=w,}$ $${\displaystyle w\wedge z=w\wedge (x\wedge y)=(w\wedge x)\wedge y=w\wedge y=w.}$$

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

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

Если является meet-полурешеткой, то meet может быть расширен до вполне определенного meet любого непустого конечного множества с помощью техники, описанной в итерированных бинарных операциях . В качестве альтернативы, если meet определяет или определяется частичным порядком, некоторые подмножества из действительно имеют инфиму относительно этого, и разумно рассматривать такой инфимум как meet подмножества. Для непустых конечных подмножеств оба подхода дают одинаковый результат, и поэтому любой из них может быть взят в качестве определения meet. В случае, когда каждое подмножество из имеет meet, фактически является полной решеткой ; подробности см. в полноте (теория порядка) . ${\displaystyle (A,\wedge )}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle (A,\leq )}$

Примеры

Если некоторое множество степеней частично упорядочено обычным образом (по ), то объединения являются объединениями, а встречи — пересечениями; в символах (где сходство этих символов может использоваться в качестве мнемонического приема для запоминания, который обозначает объединение/супремум и обозначает встречу/инфимум ^{[примечание 1]} ). ${\displaystyle \wp (X)}$ ${\displaystyle \,\subseteq }$ ${\displaystyle \,\vee \,=\,\cup \,{\text{ and }}\,\wedge \,=\,\cap \,}$ ${\displaystyle \,\vee \,}$ ${\displaystyle \,\wedge \,}$

В более общем случае предположим, что — семейство подмножеств некоторого множества , которое частично упорядочено по Если замкнуто относительно произвольных объединений и произвольных пересечений, и если принадлежит, то Но если не замкнуто относительно объединений, то существует в тогда и только тогда, когда существует уникальный -наименьший такой, что Например, если то тогда как если то не существует, потому что множества являются единственными верхними границами в , которые могли бы быть наименьшей верхней границей , но и Если то не существует, потому что нет верхней границы в ${\displaystyle {\mathcal {F}}\neq \varnothing }$ ${\displaystyle X}$ ${\displaystyle \,\subseteq .\,}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle A,B,\left(F_{i}\right)_{i\in I}}$ ${\displaystyle {\mathcal {F}}}$ $${\displaystyle A\vee B=A\cup B,\quad A\wedge B=A\cap B,\quad \bigvee _{i\in I}F_{i}=\bigcup _{i\in I}F_{i},\quad {\text{ and }}\quad \bigwedge _{i\in I}F_{i}=\bigcap _{i\in I}F_{i}.}$$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle A\vee B}$ ${\displaystyle ({\mathcal {F}},\subseteq )}$ ${\displaystyle \,\subseteq }$ ${\displaystyle J\in {\mathcal {F}}}$ ${\displaystyle A\cup B\subseteq J.}$ ${\displaystyle {\mathcal {F}}=\{\{1\},\{2\},\{1,2,3\},\mathbb {R} \}}$ ${\displaystyle \{1\}\vee \{2\}=\{1,2,3\}}$ ${\displaystyle {\mathcal {F}}=\{\{1\},\{2\},\{1,2,3\},\{0,1,2\},\mathbb {R} \}}$ ${\displaystyle \{1\}\vee \{2\}}$ ${\displaystyle \{0,1,2\}{\text{ and }}\{1,2,3\}}$ ${\displaystyle \{1\}{\text{ and }}\{2\}}$ ${\displaystyle ({\mathcal {F}},\subseteq )}$ ${\displaystyle \{1\}\vee \{2\}}$ ${\displaystyle \{0,1,2\}\not \subseteq \{1,2,3\}}$ ${\displaystyle \{1,2,3\}\not \subseteq \{0,1,2\}.}$ ${\displaystyle {\mathcal {F}}=\{\{1\},\{2\},\{0,2,3\},\{0,1,3\}\}}$ ${\displaystyle \{1\}\vee \{2\}}$ ${\displaystyle \{1\}{\text{ and }}\{2\}}$ ${\displaystyle ({\mathcal {F}},\subseteq ).}$

Смотрите также

• Локально выпуклая векторная решетка

Примечания

1. Grätzer, George (21 ноября 2002 г.). Общая теория решеток: Второе издание. Springer Science & Business Media. стр. 52. ISBN 978-3-7643-6996-5.
2. Hachtel, Gary D.; Somenzi, Fabio (1996). Логический синтез и алгоритмы проверки . Kluwer Academic Publishers. стр. 88. ISBN 0792397460.

1. Можно сразу определить, что супремумы и инфимумы в этом каноническом простом примере являются соответственно. Сходство символов с и с можно использовать в качестве мнемонического знака для запоминания того, что в наиболее общей ситуации обозначает супремум (потому что супремум — это граница сверху, как и «выше» и ), а обозначает инфимум (потому что инфимум — это граница снизу, как и «ниже» и ). Это также можно использовать для запоминания того, обозначаются ли meets/joins с помощью или с помощью Интуиция подсказывает, что « joining »ing two sets together должно производить их объединение , которое выглядит похожим на , поэтому «join» должно обозначаться с помощью Аналогично, два множества должны « встретиться » на своем пересечении , которое выглядит похожим на , поэтому «meet» должно обозначаться с помощью ${\displaystyle (\wp (X),\subseteq )}$ ${\displaystyle \,\cup \,{\text{ and }}\,\cap \,,}$ ${\displaystyle \,\vee \,}$ ${\displaystyle \,\cup \,}$ ${\displaystyle \,\wedge \,}$ ${\displaystyle \,\cap \,}$ ${\displaystyle \,\vee \,}$ ${\displaystyle A\cup B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \,\wedge \,}$ ${\displaystyle A\cap B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \,\vee \,}$ ${\displaystyle \,\wedge .\,}$ ${\displaystyle A\cup B,}$ ${\displaystyle A\vee B,}$ ${\displaystyle \,\vee .\,}$ ${\displaystyle A\cap B,}$ ${\displaystyle A\wedge B,}$ ${\displaystyle \,\wedge .\,}$

Ссылки

• Davey, BA; Priestley, HA (2002). Введение в решетки и порядок (2-е изд.). Кембридж: Cambridge University Press . ISBN 0-521-78451-4. Збл  1002.06001.
• Викерс, Стивен (1989). Топология через логику . Кембриджские трактаты по теоретической информатике. Том 5. ISBN 0-521-36062-5. Збл  0668.54001.