Login
Login

total relation

{{Short description|Type of logical relation}}

{{for|relations R where x=y or xRy or yRx for all x and y|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."[http://caae.phil.cmu.edu/projects/logicandproofs/alpha/htmltest/m15_functions/chapter15.html Functions] from Carnegie Mellon University

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.{{cite book|last1=Schmidt|first1=Gunther|last2=Ströhlein|first2=Thomas|title=Relations and Graphs: Discrete Mathematics for Computer Scientists|url={{google books |plainurl=y |id=ZgarCAAAQBAJ|paged=54}}|date=6 December 2012|publisher=Springer Science & Business Media|isbn=978-3-642-77968-8|author-link1=Gunther Schmidt}}{{rp|54}}
  • R is total iff I_X\subseteq RR^\top.{{rp|54}}
  • 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.{{rp|63}}
  • If R is total, then \overline R\subseteq R\overline{I_Y}. The converse is true if Y\ne\emptyset.{{rp|54}}{{cite book | doi=10.1017/CBO9780511778810 | isbn=9780511778810 | author=Gunther Schmidt | title=Relational Mathematics | publisher=Cambridge University Press | year=2011 }} Definition 5.8, page 57.
  • 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.{{rp|57}}

See also

Notes

{{reflist|group=note}}

References

{{reflist}}

  • 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] {{Google books|ZgarCAAAQBAJ|Relations and Graphs|page=54}}
  • Gunther Schmidt (2011) {{Google books|E4REBTs5WsC|Relational Mathematics|page=57}}

{{Order theory}}

Category:Properties of binary relations