HOME

TheInfoList



OR:

In mathematics, a
relation on a set In mathematics, a homogeneous relation (also called endorelation) on a set ''X'' is a binary relation between ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) relation ...
is called connected or complete or total if it relates (or "compares") all pairs of elements of the set in one direction or the other while it is called strongly connected if it relates pairs of elements. As described in the terminology section below, the terminology for these properties is not uniform. This notion of "total" 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 y (see
serial relation In set theory a serial relation is a homogeneous relation expressing the connection of an element of a sequence to the following element. The successor function used by Peano to define natural numbers is the prototype for a serial relation. Bertra ...
). Connectedness features prominently in the definition of
total order In mathematics, a total order or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( re ...
s: a total (or linear) order is a
partial order In mathematics, especially order theory, a partial order on a set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements needs to be comparable ...
in which any two elements are comparable; that is, the order relation is connected. Similarly, a
strict partial order In mathematics, especially order theory, a partial order on a set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements needs to be comparable; ...
that is connected is a strict total order. A relation is a total order
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
it is both a partial order and strongly connected. A relation is a
strict total order In mathematics, a total order or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( ref ...
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). Some authors do however use the term ''connected'' with a much looser meaning, which applies to precisely those orders whose
comparability graph In graph theory and order theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partial ...
s are
connected graph In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgrap ...
s. This applies for instance to the
fence A fence is a structure that encloses an area, typically outdoors, and is usually constructed from posts that are connected by boards, wire, rails or net (textile), netting. A fence differs from a wall in not having a solid foundation along its ...
s, of which none of the nontrivial examples are total orders.


Formal definition

A relation R on a set X is called when for all x, y \in X, \text x \neq y \text x \mathrel y \quad \text \quad y \mathrel x, or, equivalently, when for all x, y \in X, x \mathrel y \quad \text \quad y \mathrel x \quad \text \quad x = y. A relation with the property that for all x, y \in X, x \mathrel y \quad \text \quad y \mathrel x is called .


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. Thus, is used more generally for relations that are connected or strongly connected., p. 6 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 , although this, too, can lead to confusion: The
universal relation In mathematics, a homogeneous relation (also called endorelation) on a set ''X'' is a binary relation between ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) relation ...
is also called complete, and "
complete Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies t ...
" has several other meanings in
order theory Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intr ...
. Connected relations are also called or said to satisfy (although the more common definition of trichotomy is stronger in that of the three options x \mathrel y, y \mathrel x, x = y must hold). 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 and , and , and , and , or and , respectively, as alternative names for the notions of connected and strongly connected as defined above.


Characterizations

Let R be a
homogeneous relation In mathematics, a homogeneous relation (also called endorelation) on a set ''X'' is a binary relation between ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) relation ...
. The following are equivalent: * R is strongly connected; * U \subseteq R \cup R^\top; * \overline \subseteq R^\top; * \overline is asymmetric, where U is the
universal relation In mathematics, a homogeneous relation (also called endorelation) on a set ''X'' is a binary relation between ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) relation ...
and R^\top is the
converse relation In mathematics, the converse of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation 'child of' is the relation 'parent of'. In formal terms ...
of R. The following are equivalent: * R is connected; * \overline \subseteq R \cup R^\top; * \overline \subseteq R^\top \cup I; * \overline is antisymmetric, where \overline is the
complementary relation In set theory, the complement of a set , often denoted by A^c (or ), is the set of elements not in . When all elements in the universe, i.e. all elements under consideration, are considered to be members of a given set , the absolute complemen ...
of the
identity relation In mathematics, a homogeneous relation (also called endorelation) on a set ''X'' is a binary relation between ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) relation ...
I and R^\top is the
converse relation In mathematics, the converse of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation 'child of' is the relation 'parent of'. In formal terms ...
of R. Introducing progressions, Russell invoked the axiom of connection:


Properties

* The relationDefined formally by v E w if a graph edge leads from vertex v to vertex w E of a
tournament A tournament is a competition involving at least three competitors, all participating in a sport or game. More specifically, the term may be used in either of two overlapping senses: # One or more competitions held at a single venue and concen ...
graph G is always a connected relation on the set of Gs vertices. * If a strongly connected relation is
symmetric Symmetry () in everyday life refers to a sense of harmonious and beautiful proportion and balance. In mathematics, the term has a more precise definition and is usually used to refer to an object that is invariant under some transformations ...
, it is the
universal relation In mathematics, a homogeneous relation (also called endorelation) on a set ''X'' is a binary relation between ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) relation ...
. * A relation is strongly connected if, and only if, it is connected and reflexive.For the direction, both properties follow trivially. — For the direction: when x \neq y, then x\mathrely \lor y\mathrelx follows from connectedness; when x = y, x \mathrel y follows from reflexivity. * A connected relation on a set X cannot be
antitransitive In mathematics, intransitivity (sometimes called nontransitivity) is a property of binary relations that are not transitive relations. That is, we can find three values a, b, and c where the transitive condition does not hold. Antitransitivity ...
, provided X has at least 4 elements. Lemma 8.2, p.8. On a 3-element set \, for example, the relation \ has both properties. * If R is a connected relation on X, then all, or all but one, elements of X are in the
range Range may refer to: Geography * Range (geographic), a chain of hills or mountains; a somewhat linear, complex mountainous or hilly area (cordillera, sierra) ** Mountain range, a group of mountains bordered by lowlands * Range, a term used to i ...
of R.If x, y \in X \setminus \operatorname(R), then x \mathrel y and y \mathrel x are impossible, so x = y follows from connectedness. Similarly, all, or all but one, elements of X are in the domain of R.


Notes

;Proofs


References

{{Order theory Properties of binary relations