# Serial 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 $(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[clarify] the property that RS = ∅ implies S = ∅, for all sets W and relations SW×X, where ∅ denotes the empty relation.
• Let L be the universal relation: $\forall y\forall z.yLz$ . Another characterization[clarify] of a total relation R is $L\circ R=L$ .
• A third algebraic characterization[clarify] 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.:57
• 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 .$ :63

Other characterizations[clarify] 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.$ 