Serial relation

In set theory, a branch of mathematics, a serial relation, also called a total or more specifically left-total relation, is a binary relation R for which every element of the domain has a corresponding range element (∀ x ∃ y x R y).

Introduction

In $\mathbb {N}$ = 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.

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".[1] More commonly, an inverse serial relation is called a surjective relation, and is specified by a serial converse relation.[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 $R\subseteq X\times Y$ and $S\subseteq Y\times Z$ are two binary relations, then their composition R ; S is defined as the relation $R\ {;}\ S=\{(x,z)\in X\times Z\mid \exists y\in Y:(x,y)\in R\land (y,z)\in S\}.$

If R is a serial relation, then S ; R = ∅ implies S = ∅, for all sets W and relations S ⊆ W×X, where ∅ denotes the empty relation.[4][5]
Let L be the universal relation: $\forall y\forall z.yLz$ . A characterization of a serial relation R is $R;L=L$ .[6]
Another algebraic characterization of a serial relation involves complements of relations: For any relation S, if R is serial then ${\overline {R;S}}\subseteq R;{\bar {S}}$ , where ${\bar {S}}$ denotes the complement of $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 ${\overline {\emptyset ;L}}=L$ while ${\overline {R;L}}=\emptyset .$ [4]^: 63

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

$I\subseteq R;R^{T}$
${\bar {R}}\subseteq R;{\bar {I}}.$ [4][2]

Russell's series

Relations are used to develop series in The Principles of Mathematics. The prototype is Peano's successor function as a one-one relation on the natural numbers. Russell's series may be finite or generated by a relation giving cyclic order. In that case the point-pair separation relation is used for description. To define a progression, he requires the generating relation to be a connected relation. Then ordinal numbers are derived from progressions, the finite ones are finite ordinals. (Chapter 28: Progressions and ordinal numbers) Distinguishing open and closed series (p 234) results in four total orders: finite, one end, no end and open, and no end and closed. (p 202)

Contrary to other writers, Russell admits negative ordinals. For motivation consider the scales of measurement using scientific notation where a power of ten represents a decade of measure. Informally, this parameter corresponds to orders of magnitude used to quantify physical units. The parameter takes on negative as well as positive values.

Stretches

Russell adopted the term stretch from Alexius Meinong who had contributed to the theory of distance.[8] It refers to the intermediate terms between two points in a series, and the "number of terms measures the distance and divisibility of the whole." (p 181) To explain Meinong, Russell refers to the Cayley-Klein metric which uses stretch coordinates in anharmonic ratios which determine distance by using logarithm. (page 255)[9]

References

Yao, Y. (2004). "Semantics of Fuzzy Sets in Rough Set Theory". Transactions on Rough Sets II. Lecture Notes in Computer Science. Vol. 3135. p. 309. doi:10.1007/978-3-540-27778-1_15. ISBN 978-3-540-23990-1.
Gunther Schmidt (2011). Relational Mathematics. Cambridge University Press. doi:10.1017/CBO9780511778810. ISBN 9780511778810. Definition 5.8, page 57.
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
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 $\exists w\exists x.wSx$ implies $\exists w\exists x\exists y.wSx\land xRy$ , hence $\exists w\exists y.w(S;R)y$ , hence $S;R\neq \emptyset$ . The property follows by contraposition.
$P=R;L=\{(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 $P=L$ .
If R is serial, then $L=R;L=R;(S\cup {\bar {S}})=(R;S)\cup (R;{\bar {S}})$ , hence ${\overline {R;S}}\subseteq R;{\bar {S}}$ .
Alexius Meinong (1896) Uber die Bedeutung der Weberische Gesetze
Russell (1897) An Essay on the Foundations of Geometry

Jing Tao Yao and Davide Ciucci and Yan Zhang (2015). "Generalized Rough Sets". In Janusz Kacprzyk and Witold Pedrycz (ed.). Handbook of Computational Intelligence. Springer. pp. 413–424. ISBN 9783662435052. Here: page 416.
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..

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[Yao2005-1] Yao, Y. (2004). "Semantics of Fuzzy Sets in Rough Set Theory". Transactions on Rough Sets II. Lecture Notes in Computer Science. Vol. 3135. p. 309. doi:10.1007/978-3-540-27778-1_15. ISBN 978-3-540-23990-1.

[GS11-2] Gunther Schmidt (2011). Relational Mathematics. Cambridge University Press. doi:10.1017/CBO9780511778810. ISBN 9780511778810. Definition 5.8, page 57.

[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

[R&G-4] 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 serial, then $\exists w\exists x.wSx$ implies $\exists w\exists x\exists y.wSx\land xRy$ , hence $\exists w\exists y.w(S;R)y$ , hence $S;R\neq \emptyset$ . The property follows by contraposition.

[6] $P=R;L=\{(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 $P=L$ .

[7] If R is serial, then $L=R;L=R;(S\cup {\bar {S}})=(R;S)\cup (R;{\bar {S}})$ , hence ${\overline {R;S}}\subseteq R;{\bar {S}}$ .

[8] Alexius Meinong (1896) Uber die Bedeutung der Weberische Gesetze

[9] Russell (1897) An Essay on the Foundations of Geometry