Total relation

Algebraic characterization

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

• R is total iff for any set W and any S\subseteq W\times X, S\ne\emptyset implies SR\ne\emptyset.
• R is total iff I_X\subseteq RR^\top.
• If R is total, then L_{X,Y}=RL_{Y,Y}. The converse is true if Y\ne\emptyset.If Y=\emptyset\ne X, then R will be not total.
• If R is total, then \overline{RL_{Y,Y}}=\emptyset. The converse is true if Y\ne\emptyset.Observe \overline{RL_{Y,Y}}=\emptyset\Leftrightarrow RL_{Y,Y}=L_{X,Y}, and apply the previous bullet.
• If R is total, then \overline R\subseteq R\overline{I_Y}. The converse is true if Y\ne\emptyset.
• More generally, if R is total, then for any set Z and any S\subseteq Y\times Z, \overline{RS}\subseteq R\overline S. The converse is true if Y\ne\emptyset.Take Z=Y,S=I_Y and appeal to the previous bullet.

Notes

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

References

1. [http://caae.phil.cmu.edu/projects/logicandproofs/alpha/htmltest/m15_functions/chapter15.html Functions] from [[Carnegie Mellon University]]
2. (6 December 2012). ["Relations and Graphs: Discrete Mathematics for Computer Scientists"]({{google books). [[Springer Science & Business Media]].
3. Gunther Schmidt. (2011). "Relational Mathematics". [[Cambridge University Press]].