# Total relation

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Total_relation
> Markdown URL: https://mediated.wiki/source/Total_relation.md
> Source: https://en.wikipedia.org/wiki/Total_relation
> Source revision: 1204646531
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Type of logical relation

For relations *R* where *x=y* or *xRy* or *yRx* for all *x* and *y*, see [connected relation](/source/Connected_relation).

In [mathematics](/source/Mathematics), a [binary relation](/source/Binary_relation) *R* ⊆ *X*×*Y* between two sets *X* and *Y* is **total** (or **left total**) if the source set *X* equals the domain {*x* : there is a *y* with *xRy* }. Conversely, *R* is called **right total** if *Y* equals the range {*y* : there is an *x* with *xRy* }.

When *f*: *X* → *Y* is a [function](/source/Function_(mathematics)), the domain of *f* is all of *X*, hence *f* is a total relation. On the other hand, if *f* is a [partial function](/source/Partial_function), then the domain may be a proper subset of *X*, in which case *f* is not a total relation.

"A binary relation is said to be total with respect to a universe of discourse just in case everything in that universe of discourse stands in that relation to something else."[1]

## Algebraic characterization

Total relations can be characterized algebraically by equalities and inequalities involving [compositions of relations](/source/Composition_of_relations). To this end, let X , Y {\displaystyle X,Y} be two sets, and let R ⊆ X × Y . {\displaystyle R\subseteq X\times Y.} For any two sets A , B , {\displaystyle A,B,} let L A , B = A × B {\displaystyle L_{A,B}=A\times B} be the [universal relation](/source/Universal_relation) between A {\displaystyle A} and B , {\displaystyle B,} and let I A = { ( a , a ) : a ∈ A } {\displaystyle I_{A}=\{(a,a):a\in A\}} be the [identity relation](/source/Identity_relation) on A . {\displaystyle A.} We use the notation R ⊤ {\displaystyle R^{\top }} for the [converse relation](/source/Converse_relation) of R . {\displaystyle R.}

- R {\displaystyle R} is total iff for any set W {\displaystyle W} and any S ⊆ W × X , {\displaystyle S\subseteq W\times X,} S ≠ ∅ {\displaystyle S\neq \emptyset } implies S R ≠ ∅ . {\displaystyle SR\neq \emptyset .} [2]: 54

- R {\displaystyle R} is total iff I X ⊆ R R ⊤ . {\displaystyle I_{X}\subseteq RR^{\top }.} [2]: 54

- If R {\displaystyle R} is total, then L X , Y = R L Y , Y . {\displaystyle L_{X,Y}=RL_{Y,Y}.} The converse is true if Y ≠ ∅ . {\displaystyle Y\neq \emptyset .} [note 1]

- If R {\displaystyle R} is total, then R L Y , Y ¯ = ∅ . {\displaystyle {\overline {RL_{Y,Y}}}=\emptyset .} The converse is true if Y ≠ ∅ . {\displaystyle Y\neq \emptyset .} [note 2][2]: 63

- If R {\displaystyle R} is total, then R ¯ ⊆ R I Y ¯ . {\displaystyle {\overline {R}}\subseteq R{\overline {I_{Y}}}.} The converse is true if Y ≠ ∅ . {\displaystyle Y\neq \emptyset .} [2]: 54[3]

- More generally, if R {\displaystyle R} is total, then for any set Z {\displaystyle Z} and any S ⊆ Y × Z , {\displaystyle S\subseteq Y\times Z,} R S ¯ ⊆ R S ¯ . {\displaystyle {\overline {RS}}\subseteq R{\overline {S}}.} The converse is true if Y ≠ ∅ . {\displaystyle Y\neq \emptyset .} [note 3][2]: 57

## See also

- [Serial relation](/source/Serial_relation) — a total homogeneous relation

## Notes

1. **[^](#cite_ref-3)** If Y = ∅ ≠ X , {\displaystyle Y=\emptyset \neq X,} then R {\displaystyle R} will be not total.

1. **[^](#cite_ref-4)** Observe R L Y , Y ¯ = ∅ ⇔ R L Y , Y = L X , Y , {\displaystyle {\overline {RL_{Y,Y}}}=\emptyset \Leftrightarrow RL_{Y,Y}=L_{X,Y},} and apply the previous bullet.

1. **[^](#cite_ref-6)** Take Z = Y , S = I Y {\displaystyle Z=Y,S=I_{Y}} and appeal to the previous bullet.

## References

1. **[^](#cite_ref-1)** [Functions](http://caae.phil.cmu.edu/projects/logicandproofs/alpha/htmltest/m15_functions/chapter15.html) from [Carnegie Mellon University](/source/Carnegie_Mellon_University)

1. ^ [***a***](#cite_ref-R&G_2-0) [***b***](#cite_ref-R&G_2-1) [***c***](#cite_ref-R&G_2-2) [***d***](#cite_ref-R&G_2-3) [***e***](#cite_ref-R&G_2-4) [Schmidt, Gunther](/source/Gunther_Schmidt); Ströhlein, Thomas (6 December 2012). [*Relations and Graphs: Discrete Mathematics for Computer Scientists*](https://books.google.com/books?id=ZgarCAAAQBAJ). [Springer Science & Business Media](/source/Springer_Science_%26_Business_Media). [ISBN](/source/ISBN_(identifier)) [978-3-642-77968-8](https://en.wikipedia.org/wiki/Special:BookSources/978-3-642-77968-8).

1. **[^](#cite_ref-GS11_5-0)** Gunther Schmidt (2011). *Relational Mathematics*. [Cambridge University Press](/source/Cambridge_University_Press). [doi](/source/Doi_(identifier)):[10.1017/CBO9780511778810](https://doi.org/10.1017%2FCBO9780511778810). [ISBN](/source/ISBN_(identifier)) [9780511778810](https://en.wikipedia.org/wiki/Special:BookSources/9780511778810). Definition 5.8, page 57.

- [Gunther Schmidt](/source/Gunther_Schmidt) & Michael Winter (2018) *Relational Topology*

- C. Brink, W. Kahl, and G. Schmidt (1997) *Relational Methods in Computer Science*, Advances in Computer Science, page 5, [ISBN](/source/ISBN_(identifier)) [3-211-82971-7](https://en.wikipedia.org/wiki/Special:BookSources/3-211-82971-7)

- Gunther Schmidt & Thomas Strohlein (2012)[1987] *[Relations and Graphs](https://books.google.com/books?id=ZgarCAAAQBAJ&pg=PA54)*, p. 54, at [Google Books](/source/Google_Books)

- Gunther Schmidt (2011) *[Relational Mathematics](https://books.google.com/books?id=E4REBTs5WsC&pg=PA57)*, p. 57, at [Google Books](/source/Google_Books)

v t e Order theory Topics Glossary Category Key concepts Binary relation Boolean algebra Cyclic order Lattice Partially ordered set 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 Partially ordered set Chain-complete Eulerian Graded Locally finite Strict Prefix order Preorder Total Reflexive Semilattice Semiorder Symmetric Tolerance Total 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

---
Adapted from the Wikipedia article [Total relation](https://en.wikipedia.org/wiki/Total_relation) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Total_relation?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.