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

Транзитивные бинарные отношения

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

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

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.

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

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

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

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

Определения [ править ]

Частичный подход [ править ]

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

$m\leq x{\text{ and }}m\leq y$ (то есть, $m$ является нижней границей $x{\text{ and }}y$ ).
Для любого $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 }.$ ^[2] Если не все пары элементов из $A$ встретимся, то встречу все равно можно рассматривать как частичную бинарную операцию над $A.$ ^[1]

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

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

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

$x\leq j{\text{ and }}y\leq j$ (то есть, $j$ является верхней границей $x{\text{ and }}y$ ).
Для любого $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 \,$ обозначает встречу / минимум ^{[примечание 1]}).

В более общем плане предположим, что ${\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 ).

См. также [ править ]

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

Примечания [ править ]

^ Перейти обратно: ^а ^б Гретцер, Джордж (21 ноября 2002 г.). Общая теория решеток: Второе издание . Springer Science & Business Media. п. 52. ИСБН 978-3-7643-6996-5 .
^ Хачтел, Гэри Д.; Соменци, Фабио (1996). Алгоритмы логического синтеза и проверки . Академическое издательство Клювер. п. 88. ИСБН 0792397460 .

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

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

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

[Grätzer-1] Перейти обратно: ^а ^б Гретцер, Джордж (21 ноября 2002 г.). Общая теория решеток: Второе издание . Springer Science & Business Media. п. 52. ИСБН 978-3-7643-6996-5 .

[2] Хачтел, Гэри Д.; Соменци, Фабио (1996). Алгоритмы логического синтеза и проверки . Академическое издательство Клювер. п. 88. ИСБН 0792397460 .

[3] Сразу можно определить, что супремумы и инфимумы в этом каноническом простом примере $(\wp (X),\subseteq )$ являются $\,\cup \,{\text{ and }}\,\cap \,,$ соответственно. Сходство символа $\,\vee \,$ к $\,\cup \,$ и из $\,\wedge \,$ к $\,\cap \,$ таким образом, может использоваться как мнемоника для запоминания того, что в наиболее общих условиях $\,\vee \,$ обозначает супремум (потому что супремум — это граница сверху, как и $A\cup B$ находится «выше» $A$ и $B$ ) пока $\,\wedge \,$ обозначает нижнюю границу (поскольку нижняя граница является границей снизу, как и $A\cap B$ ниже" $A$ и $B$ ). Это также можно использовать, чтобы запомнить, обозначаются ли встречи/соединения $\,\vee \,$ или через $\,\wedge .\,$ Интуиция подсказывает, что « соединение » двух множеств должно привести к их объединению. $A\cup B,$ который похож на $A\vee B,$ поэтому «объединиться» должно обозначаться $\,\vee .\,$ Аналогично, два множества должны « встретиться » на пересечении. $A\cap B,$ который похож на $A\wedge B,$ поэтому «встретиться» должно обозначаться $\,\wedge .\,$

[1]

[2]

[примечание 1]

v т Это Теория порядка
Topics Glossary Category
Key concepts	Binary relation Boolean algebra Cyclic order Lattice Partial order Preorder Total order Weak ordering
Results	Boolean prime ideal theorem Cantor–Bernstein theorem Cantor's isomorphism theorem Dilworth's theorem Dushnik–Miller theorem Hausdorff maximal principle Knaster–Tarski theorem Kruskal's tree theorem Laver's theorem Mirsky's theorem Szpilrajn extension theorem Zorn's lemma
Properties & Types (list)	Antisymmetric Asymmetric Boolean algebra topics Completeness Connected Covering Dense Directed (Partial) Equivalence Foundational Heyting algebra Homogeneous Idempotent Lattice Bounded Complemented Complete Distributive Join and meet Reflexive Partial order Chain-complete Graded Eulerian Strict Prefix order Preorder Total Semilattice Semiorder Symmetric Total Tolerance Transitive Well-founded Well-quasi-ordering (Better) (Pre) Well-order
Constructions	Composition Converse/Transpose Lexicographic order Linear extension Product order Reflexive closure Series-parallel partial order Star product Symmetric closure Transitive closure
Topology & Orders	Alexandrov topology & Specialization preorder Ordered topological vector space Normal cone Order topology Order topology Topological vector lattice Banach Fréchet Locally convex Normed
Related	Antichain Cofinal Cofinality Comparability Graph Duality Filter Hasse diagram Ideal Net Subnet Order morphism Embedding Isomorphism Order type Ordered field Positive cone of an ordered field Ordered vector space Partially ordered Positive cone of an ordered vector space Riesz space Partially ordered group Positive cone of a partially ordered group Upper set Young's lattice

Определения [ править ]

Частичный подход [ править ]

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

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

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

Примеры [ править ]

См. также [ править ]

Примечания [ править ]

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

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