Serial relation

From Wikipedia, the free encyclopedia
  (Redirected from Total relation)
Jump to navigation Jump to search

In set theory, a serial relation is a binary relation R for which every element of the domain has a corresponding range element (∀ xy  x R y). Serial relations are sometimes called total relations, but the term total relation has also been used to designate a connex relation, i.e., a homogeneous binary relation R for which either xRy or yRx holds for any pair (x,y).

For example, in ℕ = natural numbers, the "less than" relation (<) is serial. On its domain, a function is serial.

A reflexive relation is a serial relation but the converse is not true. However, a serial relation that is symmetric and transitive can be shown to be reflexive. In this case the relation is an equivalence relation.

If a strict order is serial, then it has no maximal element.

In Euclidean and affine geometry, the serial property of the relation of parallel lines is expressed by Playfair's axiom.

In Principia Mathematica, Bertrand Russell and A. N. Whitehead refer to "relations which generate a series"[1] as serial relations. Their notion differs from this article in that the relation may have a finite range.

For a relation R let {y: xRy } denote the "successor neighborhood" of x. A serial relation can be equivalently characterized as every element having a non-empty successor neighborhood. Similarly an inverse serial relation is a relation in which every element has non-empty "predecessor neighborhood".[2]

Algebraic characterization[edit]

Serial relations can be characterized algebraically by equalities and inequalities about relation compositions. If and are two binary relations, then their composition is defined as the relation

  • Total relations R are characterized by[clarify] the property that RS = ∅ implies S = ∅, for all sets W and relations SW×X, where ∅ denotes the empty relation.[3][4]
  • Let L be the universal relation: . Another characterization[clarify] of a total relation R is .[5]
  • A third algebraic characterization[clarify] of a total relation involves complements of relations: For any relation S, if R is serial then , where denotes the complement of . This characterization follows from the distribution of composition over union.[3]:57[6]
  • A serial relation R stands in contrast to the empty relation ∅ in the sense that while [3]:63

Other characterizations[clarify] use the identity relation and the converse relation of :

  • [3]


  1. ^ B. Russell & A. N. Whitehead (1910) Principia Mathematica, volume one, page 141 from University of Michigan Historical Mathematical Collection
  2. ^ Yao, Y. (2004). "Semantics of Fuzzy Sets in Rough Set Theory". Transactions on Rough Sets II. Lecture Notes in Computer Science. 3135. p. 309. doi:10.1007/978-3-540-27778-1_15. ISBN 978-3-540-23990-1.
  3. ^ 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.
  4. ^ If S ≠ ∅ and R is total, then implies , hence , hence . The property follows by contraposition.
  5. ^ Since R is serial, the formula in the set comprehension for P is true for each x and z, so .
  6. ^ If R is serial, then , hence .