Jump to content
Search

Total relation

Add links
From Wikipedia, the free encyclopedia

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

[edit]

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 

See also

[edit]

Notes

[edit]
  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

[edit]
  1. ↑ Functions from Carnegie Mellon University
  2. 1 2 3 4 5 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.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Total_relation&oldid=1204646531"
Total relation
Add topic
Morty Proxy This is a proxified and sanitized view of the page, visit original site.