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

showТранзитивные   бинарные отношения
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Total, Semiconnex Anti- reflexive Equivalence relation Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Preorder (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Partial order ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Total preorder ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Total order ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Prewellordering ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Well-quasi-ordering ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Well-ordering ✗ Y Y Y ✗ ✗ Y ✗ ✗ Lattice ✗ Y ✗ ✗ Y Y Y ✗ ✗ Join-semilattice ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Meet-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Strict partial order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict weak order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict total order ✗ Y Y ✗ ✗ ✗ ✗ Y Y Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Definitions, for all $a,b$ and $S\neq \varnothing :$ ${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$ ${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$ ${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}$ ${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$ $aRa$ ${\text{not }}aRa$ ${\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}$
Y indicates that the column's property is always true the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively. All definitions tacitly require the homogeneous relation $R$ be transitive: for all $a,b,c,$ if $aRb$ and $bRc$ then $aRc.$ A term's definition may require additional properties that are not listed in this table.

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

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

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

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

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

Определения

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

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

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

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

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

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

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

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

алгебраический

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

• $x\leq x,$ с $x\wedge x=x$ по с ;
• если $x\leq y{\text{ and }}y\leq x$ затем $x=x\wedge y=y\wedge x=y$ по ; ​и
• если $x\leq y{\text{ and }}y\leq z$ затем $x\leq z$ с того времени $x\wedge z=(x\wedge y)\wedge z=x\wedge (y\wedge z)=x\wedge y=x$ по б .

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

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

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

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

$$z\wedge x=x\wedge z=x\wedge (x\wedge y)=(x\wedge x)\wedge y=x\wedge y=z$$

и поэтому $z\leq x.$ Сходным образом, $z\leq y,$ и если $w$ это еще одна нижняя граница $x{\text{ and }}y,$ затем $w\wedge x=w\wedge y=w,$ откуда

$$w\wedge z=w\wedge (x\wedge y)=(w\wedge x)\wedge y=w\wedge y=w.$$

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

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

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

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

Примеры

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

В более общем плане предположим, что ${\mathcal {F}}\neq \varnothing$ это семейство подмножеств некоторого множества $X$ который частично упорядочен $\,\subseteq .\,$ Если ${\mathcal {F}}$ замкнуто относительно произвольных объединений и произвольных пересечений и если $A,B,\left(F_{i}\right)_{i\in I}$ принадлежать ${\mathcal {F}}$ затем

$$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}.$$

Но если ${\mathcal {F}}$ тогда не закрыто под союзами $A\vee B$ существует в $({\mathcal {F}},\subseteq )$ тогда и только тогда, когда существует единственное $\,\subseteq$-самый маленький $J\in {\mathcal {F}}$ такой, что $A\cup B\subseteq J.$ Например, если ${\mathcal {F}}=\{\{1\},\{2\},\{1,2,3\},\mathbb {R} \}$ затем $\{1\}\vee \{2\}=\{1,2,3\}$ тогда как если ${\mathcal {F}}=\{\{1\},\{2\},\{1,2,3\},\{0,1,2\},\mathbb {R} \}$ затем $\{1\}\vee \{2\}$ не существует, поскольку множества $\{0,1,2\}{\text{ and }}\{1,2,3\}$ являются единственными верхними границами $\{1\}{\text{ and }}\{2\}$ в $({\mathcal {F}},\subseteq )$ это может быть наименьшая верхняя граница $\{1\}\vee \{2\}$ но $\{0,1,2\}\not \subseteq \{1,2,3\}$ и $\{1,2,3\}\not \subseteq \{0,1,2\}.$ Если ${\mathcal {F}}=\{\{1\},\{2\},\{0,2,3\},\{0,1,3\}\}$ затем $\{1\}\vee \{2\}$ не существует, поскольку нет верхней границы $\{1\}{\text{ and }}\{2\}$ в $({\mathcal {F}},\subseteq ).$

См. также

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

Ссылки

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