Total relation

For relations R where xRy or yRx for all x and y, see connected relation.

In mathematics, a 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, the domain of f is all of X, hence f is a total relation. On the other hand, if f is a 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. To this end, let ${\displaystyle X,Y}$  be two sets, and let ${\displaystyle R\subseteq X\times Y.}$  For any two sets ${\displaystyle A,B,}$  let ${\displaystyle L_{A,B}=A\times B}$  be the universal relation between ${\displaystyle A}$  and ${\displaystyle B,}$  and let ${\displaystyle I_{A}=\{(a,a):a\in A\}}$  be the identity relation on ${\displaystyle A.}$  We use the notation ${\displaystyle R^{\top }}$  for the converse relation of ${\displaystyle R.}$ 

• ${\displaystyle R}$  is total iff for any set ${\displaystyle W}$  and any ${\displaystyle S\subseteq W\times X,}$  ${\displaystyle S\neq \emptyset }$  implies ${\displaystyle SR\neq \emptyset .}$ ^[2]: 54
• ${\displaystyle R}$  is total iff ${\displaystyle I_{X}\subseteq RR^{\top }.}$ ^[2]: 54
• If ${\displaystyle R}$  is total, then ${\displaystyle L_{X,Y}=RL_{Y,Y}.}$  The converse is true if ${\displaystyle Y\neq \emptyset .}$ ^{[note 1]}
• If ${\displaystyle R}$  is total, then ${\displaystyle {\overline {RL_{Y,Y}}}=\emptyset .}$  The converse is true if ${\displaystyle Y\neq \emptyset .}$ ^{[note 2][2]: 63}
• If ${\displaystyle R}$  is total, then ${\displaystyle {\overline {R}}\subseteq R{\overline {I_{Y}}}.}$  The converse is true if ${\displaystyle Y\neq \emptyset .}$ ^{[2]: 54 [3]}
• More generally, if ${\displaystyle R}$  is total, then for any set ${\displaystyle Z}$  and any ${\displaystyle S\subseteq Y\times Z,}$  ${\displaystyle {\overline {RS}}\subseteq R{\overline {S}}.}$  The converse is true if ${\displaystyle Y\neq \emptyset .}$ ^{[note 3][2]: 57}

Notes

1. If ${\displaystyle Y=\emptyset \neq X,}$  then ${\displaystyle R}$  will be not total.
2. Observe ${\displaystyle {\overline {RL_{Y,Y}}}=\emptyset \Leftrightarrow RL_{Y,Y}=L_{X,Y},}$  and apply the previous bullet.
3. Take ${\displaystyle Z=Y,S=I_{Y}}$  and appeal to the previous bullet.

References

1. Functions from Carnegie Mellon University
2. Schmidt, Gunther; Ströhlein, Thomas (6 December 2012). Relations and Graphs: Discrete Mathematics for Computer Scientists. Springer Science & Business Media. ISBN 978-3-642-77968-8.
3. Gunther Schmidt (2011). Relational Mathematics. Cambridge University Press. doi:10.1017/CBO9780511778810. ISBN 9780511778810. Definition 5.8, page 57.

• 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 3-211-82971-7
• Gunther Schmidt & Thomas Strohlein (2012)[1987] Relations and Graphs, p. 54, at Google Books
• Gunther Schmidt (2011) Relational Mathematics, p. 57, at Google Books