Hubbry Logo
Connected relationConnected relationMain
Open search
Connected relation
Community hub
Connected relation
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Connected relation
Connected relation
Connected relation
View on Wikipedia
from Wikipedia
"Connexity" redirects here. For the comparison shopping company, see Connexity Inc.
Transitive binary relations
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric
Total,
Semiconnex		 Anti-
reflexive
Equivalence relation Green tickY ✗ ✗ ✗ ✗ ✗ Green tickY ✗ ✗
Preorder (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Green tickY ✗ ✗
Partial order ✗ Green tickY ✗ ✗ ✗ ✗ Green tickY ✗ ✗
Total preorder ✗ ✗ Green tickY ✗ ✗ ✗ Green tickY ✗ ✗
Total order ✗ Green tickY Green tickY ✗ ✗ ✗ Green tickY ✗ ✗
Prewellordering ✗ ✗ Green tickY Green tickY ✗ ✗ Green tickY ✗ ✗
Well-quasi-ordering ✗ ✗ ✗ Green tickY ✗ ✗ Green tickY ✗ ✗
Well-ordering ✗ Green tickY Green tickY Green tickY ✗ ✗ Green tickY ✗ ✗
Lattice ✗ Green tickY ✗ ✗ Green tickY Green tickY Green tickY ✗ ✗
Join-semilattice ✗ Green tickY ✗ ✗ Green tickY ✗ Green tickY ✗ ✗
Meet-semilattice ✗ Green tickY ✗ ✗ ✗ Green tickY Green tickY ✗ ✗
Strict partial order ✗ Green tickY ✗ ✗ ✗ ✗ ✗ Green tickY Green tickY
Strict weak order ✗ Green tickY ✗ ✗ ✗ ✗ ✗ Green tickY Green tickY
Strict total order ✗ Green tickY Green tickY ✗ ✗ ✗ ✗ Green tickY Green tickY
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric
Definitions,
for all and
Green tickY 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 Green tickY in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively.

All definitions tacitly require the homogeneous relation be transitive: for all if and then
A term's definition may require additional properties that are not listed in this table.

In mathematics, a relation on a set is called connected or complete or total if it relates (or "compares") all distinct pairs of elements of the set in one direction or the other while it is called strongly connected if it relates all 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 there is a so that (see serial relation).

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; that is, 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).

Some authors do however use the term connected with a much looser meaning, which applies to precisely those orders whose comparability graphs are connected graphs. This applies for instance to the fences, of which none of the nontrivial examples are total orders.

Formal definition

[edit]

A relation on a set is called connected when for all or, equivalently, when for all

A relation with the property that for all is called strongly connected.[1][2][3]

Terminology

[edit]

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.[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 complete,[7] although this, too, can lead to confusion: The universal relation is also called complete,[8] and "complete" has several other meanings in order theory. Connected relations are also called connex[9][10] or said to satisfy trichotomy[11] (although the more common definition of trichotomy is stronger in that exactly one of the three options 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 weakly connected and connected,[12] complete and strongly complete,[13] total and complete,[6] semiconnex and connex,[14] or connex and strictly connex,[15] respectively, as alternative names for the notions of connected and strongly connected as defined above.

Characterizations

[edit]

Let be a homogeneous relation. The following are equivalent:[14]

  • is strongly connected;
  • ;
  • ;
  • is asymmetric,

where is the universal relation and is the converse relation of

The following are equivalent:[14]

  • is connected;
  • ;
  • ;
  • is antisymmetric,

where is the complementary relation of , is the identity relation and is the converse relation of .

Introducing progressions, Russell invoked the axiom of connection:

Whenever a series is originally given by a transitive asymmetrical relation, we can express connection by the condition that any two terms of our series are to have the generating relation.

— Bertrand Russell, The Principles of Mathematics, page 239

Properties

[edit]
  • The edge relation[note 1] of a tournament graph is always a connected relation on the set of 's vertices.
  • If a strongly connected relation is symmetric, it is the universal relation.
  • A relation is strongly connected if, and only if, it is connected and reflexive.[proof 1]
  • A connected relation on a set cannot be antitransitive, provided has at least 4 elements.[16] On a 3-element set for example, the relation has both properties.
  • If is a connected relation on then all, or all but one, elements of are in the range of [proof 2] Similarly, all, or all but one, elements of are in the domain of

Notes

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Connected relation

View on Grokipedia
from Grokipedia
In mathematics, a connected relation is a binary relation on a set EE such that for every pair of distinct elements x,y∈Ex, y \in E, at least one of the ordered pairs (x,y)(x, y) or (y,x)(y, x) belongs to the relation. This property ensures that all distinct elements in the set are comparable under the relation, distinguishing it from partial relations where some pairs may lack any directed connection. Connected relations are fundamental in order theory, where they provide the totality condition for more structured relations; specifically, a reflexive and transitive connected relation constitutes a total preorder (or weak order), allowing for a complete linear arrangement of elements up to equivalence classes. Connectedness applies strictly to off-diagonal pairs and is independent of reflexivity, which is a separate property often added for preorders. If additionally antisymmetric, a total preorder becomes a , enabling unique numerical representations like utility functions in . Examples abound in familiar contexts: the "less than or equal to" relation ≤\leq on the real numbers R\mathbb{R} is connected, as is the "greater than" relation on the real numbers (assuming distinct values), whereas "is the same age as" on people fails connectedness due to incomparable pairs.

Definition and terminology

Formal definition

A RR on a set XX is a R⊆X×XR \subseteq X \times X. The relation RR is connected if, for all distinct x,y∈Xx, y \in X, either x R yx\, R\, y or y R xy\, R\, x holds. This condition is equivalent to requiring that for all x,y∈Xx, y \in X, x R yx\, R\, y, y R xy\, R\, x, or x=yx = y. A variant called a strongly connected relation strengthens the condition to hold for all x,y∈Xx, y \in X (including when x=yx = y), so that x R yx\, R\, y or y R xy\, R\, x is true without exception. The universal relation U=X×XU = X \times X satisfies the connected condition, as every belongs to UU. Total orders represent connected partial orders.

Terminology

In mathematical literature on binary relations and , a connected relation is also known by several synonyms, including complete relation, total relation (particularly when emphasizing pairwise comparability in the context of preorders or orders), and connex relation. These terms are used interchangeably to denote a relation where every pair of distinct elements is related in at least one direction, though "total relation" can sometimes refer more broadly to left-total (serial) relations in set-theoretic contexts, requiring clarification based on the specific framework. The property of trichotomy, often associated with connected relations in strict forms, requires that for any elements xx and yy in the domain, exactly one of x<yx < y, y<xy < x, or x=yx = y holds, ensuring mutual exclusivity alongside comparability; this strengthens the connected property for irreflexive relations, as seen in strict total orders. Unlike serial relations, which guarantee that every element relates to at least one other element (i.e., ∀x∃y (x,y)∈R\forall x \exists y \, (x, y) \in R), connected relations demand pairwise comparability for all distinct pairs, preventing isolated incomparabilities while seriality allows for elements incomparable to most others as long as each has some relation. The term "connex" derives from French mathematical traditions, where it describes relations akin to linear connectivity, and was adopted into English usage by to highlight exhaustive comparability, drawing an analogy to the interconnectedness in graph theory's connected components but applied to relational structures. "Connected" similarly evokes this graph-theoretic intuition for comparability in orders. Connected relations underpin total preorders, which combine reflexivity and transitivity with this comparability.

Characterizations

Algebraic characterizations

A binary relation RR on a set XX is connected if and only if R∪R⊤⊇(X×X)∖ΔR \cup R^\top \supseteq (X \times X) \setminus \Delta, where R⊤R^\top denotes the converse of RR, defined by (y,x)∈R⊤(y, x) \in R^\top if and only if (x,y)∈R(x, y) \in R, and Δ={(x,x)∣x∈X}\Delta = \{(x, x) \mid x \in X\} is the diagonal relation. This condition ensures that for every pair of distinct elements in XX, at least one of the ordered pairs belongs to RR or its converse, capturing the requirement that RR or R⊤R^\top holds between any two distinct elements of XX. The equivalence follows directly from the definition of a connected relation, which states that for all distinct x,y∈Xx, y \in X, either x R yx\, R\, y or y R xy\, R\, x. The off-diagonal pairs are covered by the connectedness condition. For the diagonal elements (x,x)(x, x), they belong to R∪R⊤R \cup R^\top if and only if x R xx\, R\, x, so equality R∪R⊤=X×XR \cup R^\top = X \times X holds precisely when RR is reflexive (i.e., strongly connected). Thus, the union covers at least the off-diagonal part for connected relations, and the full X×XX \times X if reflexive. For strict (irreflexive) relations, the characterization is that a strict relation RR on XX is (strictly) connected if and only if R∪R⊤=(X×X)∖ΔR \cup R^\top = (X \times X) \setminus \Delta. Here, the proof sketch mirrors the non-strict case but excludes the diagonal, as strict connectedness requires that for all distinct x,y∈Xx, y \in X, either x R yx\, R\, y or y R xy\, R\, x, with no elements on the diagonal. This algebraic view using unions and converses provides an equivalent formulation to complement-based characterizations, where the complement of RR is contained in R⊤R^\top off the diagonal.

Complement-based characterizations

A connected binary relation RR on a set XX can be characterized in terms of its complement R‾\overline{R}, defined as the set of all ordered pairs (x,y)(x, y) such that xR̸yx \not R y. Specifically, RR is connected if and only if R‾\overline{R} is antisymmetric, meaning that for all distinct x,y∈Xx, y \in X, it is not the case that both xR‾yx \overline{R} y and yR‾xy \overline{R} x. To see this equivalence, suppose RR is connected: for all distinct x,y∈Xx, y \in X, either xRyx R y or yRxy R x (or both). Then, for distinct x,yx, y, if xR‾yx \overline{R} y, it means xR̸yx \not R y, so yRxy R x must hold by connectedness, implying y̸R‾xy \not \overline{R} x. Thus, R‾\overline{R} cannot hold in both directions for distinct elements, so R‾\overline{R} is antisymmetric. Conversely, if R‾\overline{R} is antisymmetric, then for distinct x,yx, y, it cannot be that both xR‾yx \overline{R} y and yR‾xy \overline{R} x, i.e., not both xR̸yx \not R y and yR̸xy \not R x, so either xRyx R y or yRxy R x, meaning RR is connected. Equivalently, the antisymmetry of R‾\overline{R} implies that R‾\overline{R} has no symmetric pairs off the diagonal, as any such pair would violate the antisymmetry condition for distinct elements. This formulation highlights how the absence of "undirected" non-relations in RR corresponds to the lack of bidirectional non-relations in the complement. For the stronger notion of a strongly connected relation, which is a connected relation that is also reflexive, the complement R‾\overline{R} is asymmetric. A relation is asymmetric if it is both irreflexive (no xR‾xx \overline{R} x for any x∈Xx \in X) and antisymmetric. Since reflexivity of RR ensures xRxx R x for all xx, R‾\overline{R} excludes the diagonal and is thus irreflexive; combined with the antisymmetry from connectedness, R‾\overline{R} is asymmetric. The proof follows similarly: reflexivity guarantees irreflexivity of R‾\overline{R}, and the connected case already establishes antisymmetry of R‾\overline{R}. Conversely, if R‾\overline{R} is asymmetric, it is antisymmetric (yielding connectedness of RR) and irreflexive (yielding reflexivity of RR). This parallel to the algebraic characterization via unions with the converse provides a complementary perspective on totality.

Properties

Fundamental properties

A connected relation RR on a set AA with ∣A∣>1|A| > 1 cannot be empty, as the definition requires that for every pair of distinct elements x,y∈Ax, y \in A, either xRyx R y or yRxy R x. If a connected relation is reflexive, then for all x,y∈Ax, y \in A, xRyx R y or yRxy R x. Strongly connected relations coincide with total preorders when transitivity is also present. The collection of connected relations on a fixed set is closed under arbitrary unions: if {Ri}i∈I\{R_i\}_{i \in I} is a of connected relations on AA, then ⋃i∈IRi\bigcup_{i \in I} R_i is connected, since for any distinct x,y∈Ax, y \in A, there exists some ii such that xRiyx R_i y or yRixy R_i x. However, connected relations are not closed under s: the intersection of two connected relations on AA need not be connected, as a pair may be related in opposite directions in each relation, resulting in neither direction in the intersection. Connectedness requires that the relation covers every pair of distinct elements in at least , ensuring no pairs exist.

Interactions with other relations

A connected relation combined with results in a relation that includes both directions for every pair of distinct elements; if also reflexive, this is relation UU, which relates every pair including the diagonal. When a connected relation is also asymmetric, it forms a relation, where exactly one directed relation holds between every pair of distinct elements. If this is additionally transitive, it constitutes a strict . The combination of a connected relation with transitivity and reflexivity yields a total preorder, also known as a linear preorder or weak order, in which every pair of elements is comparable under the reflexive and transitive structure. A reflexive connected relation that is antisymmetric is a ; the antisymmetry ensures no mutual relations between distinct elements, while connectedness guarantees totality across all pairs. Connectedness does not interact with reflexivity in a mandatory way, as non-reflexive connected relations exist; for instance, the strict less-than relation << on the real numbers connects every distinct pair but excludes self-relations.

Examples

Illustrative examples

One illustrative example of a connected relation is the standard ordering ≤ on the real numbers R\mathbb{R}. For any two real numbers xx and yy, either x≤yx \leq y or y≤xy \leq x, satisfying the connectedness condition, and this relation forms a on R\mathbb{R}. In , a on a of vertices defines a connected relation via its directed edges. A is an orientation of a complete undirected graph, ensuring that for every pair of distinct vertices uu and vv, there is exactly one directed edge between them, either u→vu \to v or v→uv \to u, making the edge relation connected (though typically asymmetric). The universal relation UU on any nonempty set AA, defined by U=A×AU = A \times A, is trivially connected, as every pair (x,y)(x, y) with x,y∈Ax, y \in A satisfies x U yx \, U \, y and y U xy \, U \, x; this relation is also symmetric and reflexive. The lexicographic order on the set of finite words over an ordered , such as strings over {a,b}\{a, b\} with a<ba < b, provides another example. For any two distinct words w1w_1 and w2w_2, they are comparable by scanning from the left until the first position where they differ, and relating based on the order of those symbols, ensuring connectedness. A non-strict connected relation can be constructed by unioning the equality relation with a strict total order. For instance, on the integers Z\mathbb{Z}, the relation == union << yields the standard ≤\leq, where for distinct m,n∈Zm, n \in \mathbb{Z}, either m<nm < n or n<mn < m, and equals hold for identical elements, maintaining connectedness.

Counterexamples

The empty relation on a nonempty set AA with ∣A∣≥2|A| \geq 2 provides a simple counterexample to connectedness. This relation R=∅⊆A×AR = \emptyset \subseteq A \times A contains no ordered pairs, so for any distinct x,y∈Ax, y \in A, neither x R yx \, R \, y nor y R xy \, R \, x holds. The equality relation on a set AA with ∣A∣≥2|A| \geq 2 is another . Defined by x R yx \, R \, y x=yx = y, this relation is reflexive, antisymmetric, and transitive, making it a partial order, but it fails connectedness because for any distinct x,y∈Ax, y \in A, neither x R yx \, R \, y nor y R xy \, R \, x is true. The divisibility relation on the set of positive integers exemplifies a partial order that is not connected. Here, m R nm \, R \, n mm divides nn (i.e., n=kmn = k m for some k≥1k \geq 1); this relation is reflexive, antisymmetric, and transitive. However, for m=2m = 2 and n=3n = 3, neither 2 R 32 \, R \, 3 (since 3 is not a multiple of 2) nor 3 R 23 \, R \, 2 (since 2 is not a multiple of 3) holds. An asymmetric strict partial order also illustrates failure of connectedness. Consider the proper subset relation ⊂\subset on the power set of {1,2}\{1, 2\}, where S R TS \, R \, T if and only if SS is a proper subset of TT; this is irreflexive, transitive, and asymmetric. Yet, for S={1}S = \{1\} and T={2}T = \{2\}, neither {1} R {2}\{1\} \, R \, \{2\} nor {2} R {1}\{2\} \, R \, \{1\} holds, as neither is a proper subset of the other.

Applications

In order theory

In order theory, connected relations play a central role in defining total preorders and total orders, which extend partial orders by ensuring comparability between all elements. A total preorder is a reflexive and transitive relation that is also connected, meaning that for any two elements xx and yy in the set, either x≤yx \leq y or y≤xy \leq x. When this relation is additionally antisymmetric—implying that if x≤yx \leq y and y≤xy \leq x, then x=yx = y—it becomes a , providing a linear arrangement of the elements without incomparabilities. This structure is fundamental for linear extensions, where a connected refinement of a partial order is constructed by embedding the original antisymmetric, reflexive, and into a that preserves all existing comparisons. Szpilrajn's theorem guarantees the existence of such linear extensions for any partial order, enabling the transformation of partial structures into fully comparable ones. The Dedekind-MacNeille completion further illustrates the preservation of connectedness in lattice theory. For a poset that is already a (a connected partial order), this completion embeds the original structure into the smallest containing it, using cuts to fill gaps while maintaining the linear arrangement and all existing suprema and infima. This process generalizes Dedekind's from , ensuring that the completed lattice remains a complete —a totally ordered complete lattice—thus preserving the connected nature of the relation. Connected relations underpin practical applications in , particularly in algorithms that require full comparability. Sorting algorithms, such as comparison-based sorts, fundamentally rely on total orders, which combine connectedness with transitivity to ensure that pairwise comparisons can unambiguously arrange elements into a sequence where each precedes or succeeds the next without cycles or gaps. This reliance on total orders allows efficient of data while respecting the underlying relation. Historically, connected relations were pivotal in Georg Cantor's development of well-orderings, which extend total orders by adding well-foundedness—every nonempty has a least element. Cantor's work in the late used well-orderings to explore transfinite cardinalities and the structure of infinite sets, establishing foundational principles for by assuming every set admits such a connected, well-founded extension, later formalized via the .

In

In , a connected on a corresponds to a , which is a obtained by orienting the edges of a complete undirected graph such that exactly one directed edge exists between every pair of distinct vertices. This orientation models the relation where, for distinct elements uu and vv, either uu relates to vv (edge u→vu \to v) or vv to uu (edge v→uv \to u), but not both, ensuring and totality. A key property in tournaments is strong connectivity, defined as the existence of a directed path from every vertex to every other vertex. Strongly connected tournaments exhibit rich structural features, such as containing directed cycles of lengths from 3 up to the number of vertices, and by Camion's theorem, they possess a Hamiltonian cycle visiting each vertex exactly once. Since the underlying undirected graph of any tournament is complete, every tournament is weakly connected—meaning the graph remains connected when ignoring edge directions—but strong connectivity imposes the additional requirement of directed accessibility. In random tournaments, where each edge orientation is chosen uniformly at random, the structure guarantees weak connectivity for all realizations due to the complete underlying graph. Tournaments frequently model round-robin competitions in sports scheduling, where vertices represent teams or players, and a directed edge from uu to vv indicates that uu defeats vv in their matchup. This application captures the exhaustive pairwise comparisons inherent in connected relations, allowing analysis of outcomes like dominance hierarchies or systems. A special case is the transitive tournament, where the relation is not only connected and asymmetric but also transitive, equivalent to a on the vertices such that edges point from higher to lower ranked elements. Such tournaments are acyclic and form a linear , briefly referencing order-theoretic total orders as their foundational counterpart.

References

  1. https://lexique.netmath.ca/en/connected-relation/
  2. https://arxiv.org/pdf/2306.06471
  3. https://www.math.cmu.edu/~wgunther/127m12/notes/day11.pdf
  4. https://www.sciencedirect.com/science/article/abs/pii/S0304406802000034
  5. https://ncatlab.org/nlab/show/connected+relation
  6. https://semantics.uchicago.edu/kennedy/classes/w06/readings/ptw3.pdf
  7. https://ncatlab.org/nlab/show/trichotomous
  8. https://ncatlab.org/nlab/show/connected%2Brelation
  9. https://ncatlab.org/nlab/show/total%2Brelation
  10. https://people.umass.edu/klement/imp/imp-iphone.pdf
  11. https://ncatlab.org/nlab/show/total+relation
  12. https://web.stanford.edu/class/archive/cs/cs103/cs103.1142/lectures/07/Small07.pdf
  13. https://principlesofcryptography.com/set-theory-primer/
  14. https://philarchive.org/archive/EASATU
  15. https://web.ma.utexas.edu/users/allcock/research/tournaments.pdf
  16. https://www.cs.cornell.edu/home/halpern/papers/prec.pdf
  17. https://ics.uci.edu/~alspaugh/cls/shr/relation.html
  18. https://www.cs.cornell.edu/courses/cs280/2001sp/handouts/h28.pdf
  19. https://dspace.mit.edu/bitstream/handle/1721.1/104426/6-042j-spring-2010/contents/readings/MIT6_042JS10_chap07.pdf
  20. http://acme.able.cs.cmu.edu/pubs/uploads/pdf/CMU-ISR-17-119.pdf
  21. https://mfleck.cs.illinois.edu/building-blocks/version-1.3/relations.pdf
  22. https://people.math.wisc.edu/~slempp/papers/linext.pdf
  23. https://math.berkeley.edu/~wodzicki/H104/OrderedSets.pdf
  24. https://www.cs.tufts.edu/~nr/cs257/archive/fritz-henglein/what-is-a-sorting-function.pdf
  25. https://arxiv.org/abs/2304.00055
  26. https://facultyweb.kennesaw.edu/mlavrov/courses/graph-theory/lecture19.pdf
  27. https://www.jstor.org/stable/2315334
Add your contribution
Related Hubs
User Avatar
No comments yet.