Serial relation

In set theory, a serial relation is a binary relation R for which every element of the domain has a corresponding range element (∀ x ∃ y  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 $(m\parallel n)$ is expressed by Playfair's axiom.

In Principia Mathematica, Bertrand Russell and A. N. Whitehead refer to "relations which generate a series" 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".

In normal modal logic, the extension of fundamental axiom set K by the serial property results in axiom set D.

Algebraic characterization

Serial relations can be characterized algebraically by equalities and inequalities about relation compositions. If $R\subseteq X\times Y$ and $S\subseteq Y\times Z$ are two binary relations, then their composition $S\circ R$ is defined as the relation $S\circ R=\{(x,z)\in X\times Z\mid \exists y\in Y:(x,y)\in R\land (y,z)\in S\}.$

• Total relations R are characterized by the property that R∘S = ∅ implies S = ∅, for all sets W and relations S ⊆ W×X, where ∅ denotes the empty relation.

• Let L be the universal relation: $\forall y\forall z.yLz$. Another characterization of a total relation R is $L\circ R=L$.

• A third algebraic characterization of a total relation involves complements of relations: For any relation S, if R is serial then ${\overline {S\circ R}}\subseteq {\overline {S}}\circ R$, where ${\overline {S}}$ denotes the complement of $S$. This characterization follows from the distribution of composition over union.

• A serial relation R stands in contrast to the empty relation ∅ in the sense that ${\overline {L\circ \emptyset }}=L$ while ${\overline {L\circ R}}=\emptyset .$

Other characterizations use the identity relation $I$ and the converse relation $R^{T}$ of $R$:

• $I\subseteq R^{T}\circ R$
• ${\bar {R}}\subseteq {\bar {I}}\circ R.$

References

• Jing Tao Yao and Davide Ciucci and Yan Zhang (2015). "Generalized Rough Sets". In Janusz Kacprzyk and Witold Pedrycz. Handbook of Computational Intelligence. Springer. pp. 413–424. ISBN 9783662435052. Here: page 416.
• Gunther Schmidt (2013). Relational Mathematics. Cambridge University Press. doi:10.1017/CBO9780511778810. ISBN 9780511778810. Here: definition 5.8, page 57.
• Yao, Y.Y.; Wong, S.K.M. (1995). "Generalization of rough sets using relationships between attribute values" (PDF). Proceedings of the 2nd Annual Joint Conference on Information Sciences: 30–33..