Total 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."<ref>Functions from Carnegie Mellon University</ref>

Algebraic characterization

Total relations can be characterized algebraically by equalities and inequalities involving compositions of relations. To this end, let <math>X,Y</math> be two sets, and let <math>R\subseteq X\times Y.</math> For any two sets <math>A,B,</math> let <math>L_{A,B}=A\times B</math> be the universal relation between <math>A</math> and <math>B,</math> and let <math>I_A=\{(a,a):a\in A\}</math> be the identity relation on <math>A.</math> We use the notation <math>R^\top</math> for the converse relation of <math>R.</math>

• <math>R</math> is total iff for any set <math>W</math> and any <math>S\subseteq W\times X,</math> <math>S\ne\emptyset</math> implies <math>SR\ne\emptyset.</math><ref name=R&G>Template:Cite book</ref>Template:Rp
• <math>R</math> is total iff <math>I_X\subseteq RR^\top.</math><ref name=R&G/>Template:Rp
• If <math>R</math> is total, then <math>L_{X,Y}=RL_{Y,Y}.</math> The converse is true if <math>Y\ne\emptyset.</math><ref group=note>If <math>Y=\emptyset\ne X,</math> then <math>R</math> will be not total.</ref>
• If <math>R</math> is total, then <math>\overline{RL_{Y,Y}}=\emptyset.</math> The converse is true if <math>Y\ne\emptyset.</math><ref group=note>Observe <math>\overline{RL_{Y,Y}}=\emptyset\Leftrightarrow RL_{Y,Y}=L_{X,Y},</math> and apply the previous bullet.</ref><ref name=R&G/>Template:Rp
• If <math>R</math> is total, then <math>\overline R\subseteq R\overline{I_Y}.</math> The converse is true if <math>Y\ne\emptyset.</math><ref name=R&G/>Template:Rp<ref name=GS11>Template:Cite book Definition 5.8, page 57.</ref>
• More generally, if <math>R</math> is total, then for any set <math>Z</math> and any <math>S\subseteq Y\times Z,</math> <math>\overline{RS}\subseteq R\overline S.</math> The converse is true if <math>Y\ne\emptyset.</math><ref group=note>Take <math>Z=Y,S=I_Y</math> and appeal to the previous bullet.</ref><ref name=R&G/>Template:Rp

See also

• Serial relation — a total homogeneous relation

References

• 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, Template:ISBN
• Gunther Schmidt & Thomas Strohlein (2012)[1987] Template:Google books
• Gunther Schmidt (2011) Template:Google books