In mathematics, a binary relation R ⊆ A×B is total (or left total) if the source set A equals the domain {x : there is a y with xRy }. Conversely, R is called right total if B equals the range {y : there is an x with xRy }.
When f: A → B is a function, the domain of f is all of A, 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 A, 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
Total relations can be characterized algebraically by equalities and inequalities about relation compositions. If and are two binary relations, then their composition R ; S is defined as the relation
- If R is a total relation, then S ; R = ∅ implies S = ∅, for all sets W and relations S ⊆ W×X, where ∅ denotes the empty relation.[2][3]
- Let L be the universal relation: . A characterization[clarify] of a total relation R is .[4]
- Another algebraic characterization[clarify] of a total relation involves complements of relations: For any relation S, if R is total then , where denotes the complement of . This characterization follows from the distribution of composition over union.[2]: 57 [5]
- A total relation R stands in contrast to the empty relation ∅ in the sense that while [2]: 63
Other characterizations[clarify] use the identity relation and the converse relation of :
References
- ^ Functions from Carnegie Mellon University
- ^ a b c d Schmidt, Gunther; Ströhlein, Thomas (6 December 2012). Relations and Graphs: Discrete Mathematics for Computer Scientists. Springer Science & Business Media. p. 54. ISBN 978-3-642-77968-8.
- ^ If S ≠ ∅ and R is serial, then implies , hence , hence . The property follows by contraposition.
- ^ Since R is total, the formula in the set comprehension for P is true for each x and z, so .
- ^ If R is total, then , hence .
- ^ Gunther Schmidt (2011). Relational Mathematics. Cambridge University Press. doi:10.1017/CBO9780511778810. ISBN 9780511778810. Definition 5.8, page 57.
- 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] Relations and Graphs, p. 54, at Google Books
- Gunther Schmidt (2011) Relational Mathematics, p. 57, at Google Books