Quire

Total relation

From Quire, the open reference·Type of logical relation·1 min read

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]
  • {\displaystyle R} is total iff {\displaystyle I_{X}\subseteq RR^{\top }.}[2]
  • If {\displaystyle R} is total, then {\displaystyle L_{X,Y}=RL_{Y,Y}.} The converse is true if {\displaystyle Y\neq \emptyset .}[3]
  • If {\displaystyle R} is total, then {\displaystyle {\overline {RL_{Y,Y=\emptyset .} The converse is true if {\displaystyle Y\neq \emptyset .}[4][2]
  • If {\displaystyle R} is total, then {\displaystyle {\overline {R\subseteq R{\overline {I_{Y.} The converse is true if {\displaystyle Y\neq \emptyset .}[2][5]
  • 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 .}[6][2]

See also#edit

Notes#edit

  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. ^ If {\displaystyle Y=\emptyset \neq X,} then {\displaystyle R} will be not total.
  4. ^ Observe {\displaystyle {\overline {RL_{Y,Y=\emptyset \Leftrightarrow RL_{Y,Y}=L_{X,Y},} and apply the previous bullet.
  5. ^ Gunther Schmidt (2011). Relational Mathematics. Cambridge University Press. doi:10.1017/CBO9780511778810. ISBN 9780511778810. Definition 5.8, page 57.
  6. ^ Take {\displaystyle Z=Y,S=I_{Y and appeal to the previous bullet.

References#edit

Categories Properties of binary relations

This article is mirrored from “Total relation” on English Wikipedia, revision 1204646531, written by Wikipedia's contributors and licensed CC BY-SA 4.0. Editing it here creates a Quire copy with its own history.

Synced with Wikipedia revision 1204646531 · just now