Total relation

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

• 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