User:Rzach/sandbox

This is the user sandbox of Rzach. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here.

Other sandboxes: Main sandbox | Template sandbox

Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Wikipedia? Submit your draft for review!

Transitive binary relations

	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 for 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.

In mathematics, a homogeneous relation is called connected or total if it relates all distinct pairs of elements in one direction or the other, i.e., if any two elements can be compared. More formally, the homogeneous relation $R$ on a set $X$ is connected when for all $x,y\in X,$ where $x\neq y$ ,

x\mathrel {R} y\quad {\text{or}}\quad y\mathrel {R} x,

or, equivalently, when for all $x,y\in X$ ,

x\mathrel {R} y\quad {\text{or}}\quad y\mathrel {R} x\quad {\text{or}}\quad x=y.

A relation with the property that for all $x,y\in X$ ,

x\mathrel {R} y\quad {\text{or}}\quad y\mathrel {R} x

is called strongly connected.^[1]^[2]^[3]

Terminology for these properties is not uniform, see below. The notion should not be confused with that of a total relation in the sense that for all $x\in X$ there is a $y\in X$ so that $x\mathrel {R} y$ (see serial relation).

Connectedness and total orders

Connectedness features prominently in the definition of total orders: a total (or linear) order is a partial order in which any two elements are comparable, i.e., the order relation is connected. Similarly, a strict partial order that is connected is a strict total order.

A relation is a total order if, and only if, it is both a partial order and strongly connected. A relation is a strict total order if, and only if, it is a strict partial order and just connected. A strict total order can never be strongly connected (except on an empty domain).

Terminology

The main use of the notion of connected relation is in the context of orders, where it is used to define total, or linear, orders. In this context, the property is often not specifically named. Rather, total orders are defined as partial orders in which any two elements are comparable.^[4]^[5] Thus, total is used more generally for relations that are connected or strongly connected.^{[citation needed]} However, this notion of "total relation" must be distinguished from the property of being serial, which is also called total. Similarly, connected relations are sometimes called complete,^[6] although this, too, can lead to confusion: The universal relation is also called complete,^{[citation needed]} and "complete" has several other meanings in order theory. Connected relations are also called connex^[7]^[8] or trichotomous^[clarify].^[9]

When the relations considered are not orders, being connected and being strongly connected are importantly different properties. Sources which define both then use pairs of terms such as weakly connected and connected,^[10] complete and strongly complete,^[11] semiconnex and connex,^[12] or connex and strictly connex,^[13] respectively, as alternative names for the notions of connected and strongly connected as defined above.

Characterizations

Let $R$ be a homogeneous relation. The following are equivalent:^[12]

$R$ is strongly connected;
$U\subseteq R\cup R^{\top }$ ;
${\overline {R}}\subseteq R^{\top }$ ;
${\overline {R}}$ is asymmetric,

where $U$ is the universal relation and $R^{\top }$ is the converse relation of $R$ .

The following are equivalent:^[12]

$R$ is connected;
${\overline {I}}\subseteq R\cup R^{\top }$ ;
${\overline {R}}\subseteq R^{\top }\cup I$ ;
${\overline {R}}$ is antisymmetric,

where ${\overline {I}}$ is the complementary relation of the identity relation $I$ and $R^{\top }$ is the converse relation of $R$ .

Properties

The edge relation^[14] $E$ of a tournament graph $G$ is always a connected relation on the set of $G$ 's vertices.
If a strongly connected is symmetric, it is the universal relation.
A relation is strongly connected if, and only if, it is connected and reflexive.^[15]
A connected relation on a set $X$ cannot be antitransitive, provided $X$ has at least 4 elements.^[16] On a 3-element set ${a, b, c}$ , e.g. the relation ${(a, b), (b, c), (c, a)}$ has both properties.
If $R$ is a connected relation on $X$ , then all, or all but one, elements of $X$ are in the range of $R$ .^[17] Similarly, all, or all but one, elements of $X$ are in the domain of $R$ .

References

^ Clapham, Christopher; Nicholson, James (2014-09-18). "connected". The Concise Oxford Dictionary of Mathematics. Oxford University Press. ISBN 978-0-19-967959-1. Retrieved 2021-04-12.
^ Nievergelt, Yves (2015-10-13). Logic, Mathematics, and Computer Science: Modern Foundations with Practical Applications. Springer. p. 182. ISBN 978-1-4939-3223-8.
^ Causey, Robert L. (1994). Logic, Sets, and Recursion. Jones & Bartlett Learning. ISBN 0-86720-463-X., p. 135
^ Paul R. Halmos (1968). Naive Set Theory. Princeton: Nostrand. Here: Ch.14. Halmos gives the names of reflexivity, anti-symmetry, and transitivity, but not of connectedness.
^ Patrick Cousot (1990). "Methods and Logics for Proving Programs". In Jan van Leeuwen (ed.). Formal Models and Semantics. Handbook of Theoretical Computer Science. Vol. B. Elsevier. pp. 841–993. ISBN 0-444-88074-7. Here: Sect.6.3, p.878
^ Makinson, David (2012-02-27). Sets, Logic and Maths for Computing. Springer. ISBN 978-1-4471-2500-6., p. 50
^ Wall, Robert E. (1974). Introduction to Mathematical Linguistics. Prentice-Hall. page 114.
^ Carl Pollard. "Relations and Functions" (PDF). Ohio State University. Retrieved 2018-05-28. Page 7.
^ Kunen, Kenneth (2009). The Foundations of Mathematics. College Publications. ISBN 978-1-904987-14-7., p. 24
^ Fishburn, Peter C. (2015-03-08). The Theory of Social Choice. Princeton University Press. p. 72. ISBN 978-1-4008-6833-9.
^ Roberts, Fred S. (2009-03-12). Measurement Theory: Volume 7: With Applications to Decisionmaking, Utility, and the Social Sciences. Cambridge University Press. ISBN 978-0-521-10243-8. page 29
^ ^a ^b ^c Schmidt, Gunther; Ströhlein, Thomas (1993). Relations and Graphs: Discrete Mathematics for Computer Scientists. Berlin: Springer. ISBN 978-3-642-77970-1.
^ Ganter, Bernhard; Wille, Rudolf (2012-12-06). Formal Concept Analysis: Mathematical Foundations. Springer Science & Business Media. ISBN 978-3-642-59830-2. p. 86
^ defined formally by $vEw$ if a graph edge leads from vertex $v$ to vertex $w$
^ For the only if direction, both properties follow trivially. — For the if direction: when $x\neq y,$ then $x\mathrel {R} y\lor y\mathrel {R} x$ follows from connectedness; when $x=y$ , $x\mathrel {R} y$ follows from reflexivity.
^ Jochen Burghardt (Jun 2018). Simple Laws about Nonprominent Properties of Binary Relations (Technical Report). arXiv:1806.05036. Bibcode:2018arXiv180605036B. Lemma 8.2, p.8.
^ If x, y∈X\ran(R), then $x\mathrel {R} y$ and $y\mathrel {R} x$ are impossible, so $x=y$ follows from connectedness.

Category:Binary relations

[1] Clapham, Christopher; Nicholson, James (2014-09-18). "connected". The Concise Oxford Dictionary of Mathematics. Oxford University Press. ISBN 978-0-19-967959-1. Retrieved 2021-04-12.

[2] Nievergelt, Yves (2015-10-13). Logic, Mathematics, and Computer Science: Modern Foundations with Practical Applications. Springer. p. 182. ISBN 978-1-4939-3223-8.

[3] Causey, Robert L. (1994). Logic, Sets, and Recursion. Jones & Bartlett Learning. ISBN 0-86720-463-X., p. 135

[4] Paul R. Halmos (1968). Naive Set Theory. Princeton: Nostrand. Here: Ch.14. Halmos gives the names of reflexivity, anti-symmetry, and transitivity, but not of connectedness.

[5] Patrick Cousot (1990). "Methods and Logics for Proving Programs". In Jan van Leeuwen (ed.). Formal Models and Semantics. Handbook of Theoretical Computer Science. Vol. B. Elsevier. pp. 841–993. ISBN 0-444-88074-7. Here: Sect.6.3, p.878

[6] Makinson, David (2012-02-27). Sets, Logic and Maths for Computing. Springer. ISBN 978-1-4471-2500-6., p. 50

[7] Wall, Robert E. (1974). Introduction to Mathematical Linguistics. Prentice-Hall. page 114.

[8] Carl Pollard. "Relations and Functions" (PDF). Ohio State University. Retrieved 2018-05-28. Page 7.

[9] Kunen, Kenneth (2009). The Foundations of Mathematics. College Publications. ISBN 978-1-904987-14-7., p. 24

[10] Fishburn, Peter C. (2015-03-08). The Theory of Social Choice. Princeton University Press. p. 72. ISBN 978-1-4008-6833-9.

[11] Roberts, Fred S. (2009-03-12). Measurement Theory: Volume 7: With Applications to Decisionmaking, Utility, and the Social Sciences. Cambridge University Press. ISBN 978-0-521-10243-8. page 29

[Schmidt-12] Schmidt, Gunther; Ströhlein, Thomas (1993). Relations and Graphs: Discrete Mathematics for Computer Scientists. Berlin: Springer. ISBN 978-3-642-77970-1.

[13] Ganter, Bernhard; Wille, Rudolf (2012-12-06). Formal Concept Analysis: Mathematical Foundations. Springer Science & Business Media. ISBN 978-3-642-59830-2. p. 86

[14] rmally by $vEw$ if a graph edge leads from vertex $v$ to vertex $w$

[15] For the only if direction, both properties follow trivially. — For the if direction: when $x\neq y,$ then $x\mathrel {R} y\lor y\mathrel {R} x$ follows from connectedness; when $x=y$ , $x\mathrel {R} y$ follows from reflexivity.

[16] Jochen Burghardt (Jun 2018). Simple Laws about Nonprominent Properties of Binary Relations (Technical Report). arXiv:1806.05036. Bibcode:2018arXiv180605036B. Lemma 8.2, p.8.

[17] If x, y∈X\ran(R), then $x\mathrel {R} y$ and $y\mathrel {R} x$ are impossible, so $x=y$ follows from connectedness.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]