# 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 (∀ 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 ${\displaystyle (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"[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]

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

## Algebraic characterization

Serial relations can be characterized algebraically by equalities and inequalities about relation compositions. If ${\displaystyle R\subseteq X\times Y}$  and ${\displaystyle S\subseteq Y\times Z}$  are two binary relations, then their composition ${\displaystyle S\circ R}$  is defined as the relation ${\displaystyle 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[clarify] the property that RS = ∅ implies S = ∅, for all sets W and relations SW×X, where ∅ denotes the empty relation.[4][5]
• Let L be the universal relation: ${\displaystyle \forall y\forall z.yLz}$ . Another characterization[clarify] of a total relation R is ${\displaystyle L\circ R=L}$ .[6]
• A third algebraic characterization[clarify] of a total relation involves complements of relations: For any relation S, if R is serial then ${\displaystyle {\overline {S\circ R}}\subseteq {\overline {S}}\circ R}$ , where ${\displaystyle {\overline {S}}}$  denotes the complement of ${\displaystyle S}$ . This characterization follows from the distribution of composition over union.[4]:57[7]
• A serial relation R stands in contrast to the empty relation ∅ in the sense that ${\displaystyle {\overline {L\circ \emptyset }}=L}$  while ${\displaystyle {\overline {L\circ R}}=\emptyset .}$ [4]:63

Other characterizations[clarify] use the identity relation ${\displaystyle I}$  and the converse relation ${\displaystyle R^{T}}$  of ${\displaystyle R}$ :

• ${\displaystyle I\subseteq R^{T}\circ R}$
• ${\displaystyle {\bar {R}}\subseteq {\bar {I}}\circ R.}$ [4]

## References

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. ^ James Garson (2013) Modal Logic for Philosophers, chapter 11: Relationships between modal logics, figure 11.1 page 220, Cambridge University Press doi:10.1017/CBO97811393421117.014
4. ^ 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.
5. ^ If S ≠ ∅ and R is total, then ${\displaystyle \exists w\exists x.wSx}$  implies ${\displaystyle \exists w\exists x\exists y.wSx\land xRy}$ , hence ${\displaystyle \exists w\exists y.w(S\circ R)y}$ , hence ${\displaystyle S\circ R\neq \emptyset }$ . The property follows by contraposition.
6. ^ ${\displaystyle P=L\circ R=\{(x,z):\exists y.xRy\land yLz\}}$  Since R is serial, the formula in the set comprehension for P is true for each x and z, so ${\displaystyle P=L}$ .
7. ^ If R is serial, then ${\displaystyle L=L\circ R=(S\cup {\bar {S}})\circ R=(S\circ R)\cup ({\bar {S}}\circ R)}$ , hence ${\displaystyle {\overline {S\circ R}}\subseteq {\bar {S}}\circ R}$ .