Связанное отношение

Переходные бинарные отношения

	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.

В математике соотношение на наборе называется подключенным или полным или общим, если оно связано (или «сравнивает») все отдельные пары элементов набора в одном направлении или другое, в то время как оно называется тесно связано, если оно связано все пары элементы. Как описано в разделе терминологии ниже , терминология для этих свойств не является единой. Это понятие «полного» не следует путать с понятием полной связи в том смысле, что для всех $x\in X$ есть $y\in X$ так что $x\mathrel {R} y$ (См. Серийное отношение ).

Особенности связанности заметно в определении общих порядков : общий (или линейный) порядок - это частичный порядок , в котором любые два элемента сопоставимы; то есть отношение порядка связано. Точно так же строгий частичный порядок , который подключен, является строгим общим порядком. Отношение - это полный порядок, если и только тогда, когда это и частичный порядок, так и тесно. Отношение - это строгий полный порядок , если и только если, это строгий частичный порядок и просто подключен. Строгий общий порядок никогда не может быть сильно подключен (за исключением пустого домена).

Формальное определение

Отношение $R$ на съемочной площадке $X$ называется подключен, когда для всех $x,y\in X,$ ${\text{ if }}x\neq y{\text{ then }}x\mathrel {R} y\quad {\text{or}}\quad y\mathrel {R} x,$ или, эквивалентно, когда для всех $x,y\in X,$ $x\mathrel {R} y\quad {\text{or}}\quad y\mathrel {R} x\quad {\text{or}}\quad x=y.$

Отношение к собственности, которое для всех $x,y\in X,$ $x\mathrel {R} y\quad {\text{or}}\quad y\mathrel {R} x$ называется сильно связан . ^{[ 1 ]}^{[ 2 ]}^{[ 3 ]}

Терминология

Основное использование понятия связанного отношения заключается в контексте порядков, где оно используется для определения общего или линейного порядка. В этом контексте свойство часто не называется конкретно. Скорее, общие заказы определяются как частичные заказы, в которых каких -либо двух элементов сопоставимы. ^{[ 4 ]}^{[ 5 ]} Таким образом, Всего используется в более общем плане для отношений, которые связаны или сильно связаны. ^{[ 6 ]} Тем не менее, это понятие «полного отношения» следует отличить от свойства серийного , которое также называется общим. Точно так же иногда вызываются связанные отношения полный , ^{[ 7 ]} Хотя это также может привести к путанице: универсальное отношение также называется полной, ^{[ 8 ]} и « полное » имеет несколько других значений в теории порядка . Связанные отношения также называются Connex ^{[ 9 ]}^{[ 10 ]} или сказал, чтобы удовлетворить трихотомию ^{[ 11 ]} (Хотя более распространенное определение трихотомии сильнее в том, что именно один из трех вариантов $x\mathrel {R} y,y\mathrel {R} x,x=y$ должен держать).

Когда рассматриваемые отношения не являются порядками, быть связанным и тесным подключением - это важно различные свойства. Источники, которые определяют оба, затем используют пары терминов, таких как слабо связанный и связанный , ^{[ 12 ]} Полное и сильно завершено , ^{[ 13 ]} общее и полное , ^{[ 6 ]} полуконсекс и Connex , ^{[ 14 ]} или Connex и строго связан , ^{[ 15 ]} соответственно, как альтернативные имена для понятий подключенных и сильно связанных, как определено выше.

Характеристики

Позволять $R$ быть однородным отношением . Следующие эквивалентные: ^{[ 14 ]}

$R$ сильно связан;
$U\subseteq R\cup R^{\top }$ ;
${\overline {R}}\subseteq R^{\top }$ ;
${\overline {R}}$ асимметрично ,

где $U$ это универсальное отношение и $R^{\top }$ это обратное отношение $R.$

Следующие эквивалентные: ^{[ 14 ]}

$R$ связан;
${\overline {I}}\subseteq R\cup R^{\top }$ ;
${\overline {R}}\subseteq R^{\top }\cup I$ ;
${\overline {R}}$ является антисимметричным ,

где ${\overline {I}}$ является дополнительным отношением идентичности отношения к $I$ и $R^{\top }$ это обратное отношение $R.$

Представляя прогрессии, Рассел обратил на себя аксиому соединения:

Всякий раз, когда серия первоначально дается с помощью транзитивного асимметричного отношения, мы можем выразить связь с условием, что любые два термина нашей серии должны иметь генерирующее соотношение .
- Бертран Рассел , Принципы математики , стр. 239

Характеристики

Отношение края ^{[ Примечание 1 ]} $E$ турнирного графика $G$ всегда связано с набором $G$ Вершины .
Если тесно связанное отношение является симметричным , это универсальное отношение .
Отношение тесно связано, если и только если, оно связано и рефлексивное. ^{[ Доказательство 1 ]}
Связанное соотношение на наборе $X$ не может быть антитракансивным , предоставленным $X$ имеет не менее 4 элементов. ^{[ 16 ]} На 3-элементном наборе $\{a,b,c\},$ Например, отношение $\{(a,b),(b,c),(c,a)\}$ имеет оба свойства.
Если $R$ является связанным отношением на $X,$ тогда все или все, кроме одного, элементы $X$ в диапазоне находятся $R.$ ^{[ Доказательство 2 ]} Точно так же все или все, кроме одного, элементы $X$ находятся в домене $R.$

Примечания

^ Определено формально $vEw$ Если край графа ведет из вершины $v$ в вершину $w$

Доказательства

^ Для единственного направления, оба свойства тривиально следуют. - Для направления IF : когда $x\neq y,$ затем $x\mathrel {R} y\lor y\mathrel {R} x$ следует из связи; когда $x=y,$ $x\mathrel {R} y$ следует от рефлексивности.
^ Если $x,y\in X\setminus \operatorname {ran} (R),$ затем $x\mathrel {R} y$ и $y\mathrel {R} x$ невозможно, так $x=y$ следует из связности.

Ссылки

^ Клэпхэм, Кристофер; Николсон, Джеймс (2014-09-18). "Подключен". Краткий Оксфордский словарь математики . Издательство Оксфордского университета. ISBN 978-0-19-967959-1 Полем Получено 2021-04-12 .
^ Nievergelt, Yves (2015-10-13). Логика, математика и информатика: современные основы с практическими приложениями . Спрингер. п. 182. ISBN 978-1-4939-3223-8 .
^ Causey, Robert L. (1994). Логика, наборы и рекурсия . Jones & Bartlett Learning. ISBN 0-86720-463-х Полем , с. 135
^ Пол Р. Халмос (1968). Наивная теория наборов . Принстон: Ностроранд. Здесь: гл.14. Халмос дает названия рефлексивности, антисимметрии и транзитивности, но не связанности.
^ Патрик Кузен (1990). «Методы и логика для проверки программ». В Ян Ван Леувен (ред.). Формальные модели и семантика . Справочник по теоретической информатике. Тол. Б. Elsevier. С. 841–993. ISBN 0-444-88074-7 Полем Здесь: секта.6.3, с.878
^ Jump up to: ^а ^{беременный} Aliprantis, Charalambos D.; Border, Kim C. (2007-05-02). Бесконечный размерный анализ: руководство автостопщика . Спрингер. ISBN 978-3-540-32696-0 Полем , с. 6
^ Макинсон, Дэвид (2012-02-27). Наборы, логика и математика для вычислений . Спрингер. ISBN 978-1-4471-2500-6 Полем , с. 50
^ Уайтхед, Альфред Норт ; Рассел, Бертран (1910). Принципия Mathematica . Кембридж: издательство Кембриджского университета. {{cite book}}: Cs1 Maint: дата и год ( ссылка )
^ Уолл, Роберт Э. (1974). Введение в математическую лингвистику . Прентис-Холл. Страница 114.
^ Карл Поллард. «Отношения и функции» (PDF) . Университет штата Огайо . Получено 2018-05-28 . Страница 7.
^ Кунен, Кеннет (2009). Основы математики . Публикации колледжа. ISBN 978-1-904987-14-7 Полем п. 24
^ Фишберн, Питер С. (2015-03-08). Теория социального выбора . ПРИЗНАЯ УНИВЕРСИТЕТА ПРИСЕТА. п. 72. ISBN 978-1-4008-6833-9 .
^ Робертс, Фред С. (2009-03-12). Теория измерений: том 7: с приложениями к принятию решений, полезности и социальных наук . Издательство Кембриджского университета. ISBN 978-0-521-10243-8 Полем Страница 29
^ Jump up to: ^а ^{беременный} ^в Шмидт, Гюнтер ; Стрехляйн, Томас (1993). Отношения и графики: дискретная математика для компьютерных ученых . Берлин: Спрингер. ISBN 978-3-642-77970-1 .
^ Гантер, Бернхард; Вилле, Рудольф (2012-12-06). Формальный концептуальный анализ: математические основы . Springer Science & Business Media. ISBN 978-3-642-59830-2 Полем п. 86
^ Jochen Burghardt (Jun 2018). Простые законы о необычных свойствах бинарных отношений (технический отчет). Arxiv : 1806.05036 . BIBCODE : 2018ARXIV180605036B . Лемма 8.2, с.8.

[16] Определено формально $vEw$ Если край графа ведет из вершины $v$ в вершину $w$

[17] Для единственного направления, оба свойства тривиально следуют. - Для направления IF : когда $x\neq y,$ затем $x\mathrel {R} y\lor y\mathrel {R} x$ следует из связи; когда $x=y,$ $x\mathrel {R} y$ следует от рефлексивности.

[19] Если $x,y\in X\setminus \operatorname {ran} (R),$ затем $x\mathrel {R} y$ и $y\mathrel {R} x$ невозможно, так $x=y$ следует из связности.

[1] Клэпхэм, Кристофер; Николсон, Джеймс (2014-09-18). "Подключен". Краткий Оксфордский словарь математики . Издательство Оксфордского университета. ISBN 978-0-19-967959-1 Полем Получено 2021-04-12 .

[2] Nievergelt, Yves (2015-10-13). Логика, математика и информатика: современные основы с практическими приложениями . Спрингер. п. 182. ISBN 978-1-4939-3223-8 .

[3] Causey, Robert L. (1994). Логика, наборы и рекурсия . Jones & Bartlett Learning. ISBN 0-86720-463-х Полем , с. 135

[4] Пол Р. Халмос (1968). Наивная теория наборов . Принстон: Ностроранд. Здесь: гл.14. Халмос дает названия рефлексивности, антисимметрии и транзитивности, но не связанности.

[5] Патрик Кузен (1990). «Методы и логика для проверки программ». В Ян Ван Леувен (ред.). Формальные модели и семантика . Справочник по теоретической информатике. Тол. Б. Elsevier. С. 841–993. ISBN 0-444-88074-7 Полем Здесь: секта.6.3, с.878

[Aliprantis-6] Jump up to: ^а ^{беременный} Aliprantis, Charalambos D.; Border, Kim C. (2007-05-02). Бесконечный размерный анализ: руководство автостопщика . Спрингер. ISBN 978-3-540-32696-0 Полем , с. 6

[7] Макинсон, Дэвид (2012-02-27). Наборы, логика и математика для вычислений . Спрингер. ISBN 978-1-4471-2500-6 Полем , с. 50

[8] Уайтхед, Альфред Норт ; Рассел, Бертран (1910). Принципия Mathematica . Кембридж: издательство Кембриджского университета. {{cite book}}: Cs1 Maint: дата и год ( ссылка )

[9] Уолл, Роберт Э. (1974). Введение в математическую лингвистику . Прентис-Холл. Страница 114.

[10] Карл Поллард. «Отношения и функции» (PDF) . Университет штата Огайо . Получено 2018-05-28 . Страница 7.

[11] Кунен, Кеннет (2009). Основы математики . Публикации колледжа. ISBN 978-1-904987-14-7 Полем п. 24

[12] Фишберн, Питер С. (2015-03-08). Теория социального выбора . ПРИЗНАЯ УНИВЕРСИТЕТА ПРИСЕТА. п. 72. ISBN 978-1-4008-6833-9 .

[13] Робертс, Фред С. (2009-03-12). Теория измерений: том 7: с приложениями к принятию решений, полезности и социальных наук . Издательство Кембриджского университета. ISBN 978-0-521-10243-8 Полем Страница 29

[Schmidt-14] Jump up to: ^а ^{беременный} ^в Шмидт, Гюнтер ; Стрехляйн, Томас (1993). Отношения и графики: дискретная математика для компьютерных ученых . Берлин: Спрингер. ISBN 978-3-642-77970-1 .

[15] Гантер, Бернхард; Вилле, Рудольф (2012-12-06). Формальный концептуальный анализ: математические основы . Springer Science & Business Media. ISBN 978-3-642-59830-2 Полем п. 86

[18] Jochen Burghardt (Jun 2018). Простые законы о необычных свойствах бинарных отношений (технический отчет). Arxiv : 1806.05036 . BIBCODE : 2018ARXIV180605036B . Лемма 8.2, с.8.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

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

[ Доказательство 1 ]

[ 16 ]

[ Доказательство 2 ]

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