Total relation

In mathematics, a binary relation RX×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: XY 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 characterizationEdit

Total relations can be characterized algebraically by equalities and inequalities involving compositions of relations. To this end, let   be two sets, and let   For any two sets   let   be the universal relation between   and   and let   be the identity relation on   We use the notation   for the converse relation of  

  •   is total iff for any set   and any     implies  [2]: 54 
  •   is total iff  [2]: 54 
  • If   is total, then   The converse is true if  [note 1]
  • If   is total, then   The converse is true if  [note 2][2]: 63 
  • If   is total, then   The converse is true if  [2]: 54 [3]
  • More generally, if   is total, then for any set   and any     The converse is true if  [note 3][2]: 57 

NotesEdit

  1. ^ If   then   will be not total.
  2. ^ Observe   and apply the previous bullet.
  3. ^ Take   and appeal to the previous bullet.

ReferencesEdit

  1. ^ Functions from Carnegie Mellon University
  2. ^ a b c d e 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.