Serial relation: Difference between revisions

Content deleted Content added

Inline

Revision as of 21:01, 21 July 2018

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"^[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

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 R∘S = ∅ implies S = ∅, for all sets W and relations S ⊆ W×X, where ∅ denotes the empty relation.^[3]^[4]

Let L be the universal relation: $\forall y\forall z.yLz$ . Another characterization^[clarify] of a total relation R is $L\circ R=L$ .^[5]

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.^[3]^: 57^[6]

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 .$ ^[3]^: 63

Other characterizations^[clarify] use the identity relation $I$ and the converse relation $R^{-1}$ of $R$ :

$I\subseteq R^{-1}\circ R$
${\overline {R}}\subseteq {\overline {I}}\circ R.$ ^[3]

References

^ B. Russell & A. N. Whitehead (1910) Principia Mathematica, volume one, page 141 from University of Michigan Historical Mathematical Collection
^ 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.
^ ^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.
^ If S ≠ ∅ and R is total, then $\exists w\exists x.wSx$ implies $\exists w\exists x\exists y.wSx\land xRy$ , hence $\exists w\exists y.w(S\circ R)y$ , hence $S\circ R\neq \emptyset$ . The property follows by contraposition.
^ $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 $P=L$ .
^ If R is serial, then $L=L\circ R=(S\cup {\overline {S}})\circ R=(S\circ R)\cup ({\overline {S}}\circ R)$ , hence ${\overline {S\circ R}}\subseteq {\overline {S}}\circ R$ .

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. {{cite book}}: Cite has empty unknown parameter: |month= (help); External link in |chapterurl= (help); Unknown parameter |chapterurl= ignored (|chapter-url= suggested) (help) Here: page 416.
Gunther Schmidt (2013). Relational Mathematics. Cambridge University Press. doi:10.1017/CBO9780511778810. ISBN 9780511778810. {{cite book}}: Cite has empty unknown parameter: |month= (help) 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..

[1] B. Russell & A. N. Whitehead (1910) Principia Mathematica, volume one, page 141 from University of Michigan Historical Mathematical Collection

[Yao2005-2] 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.

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

[5] $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 $P=L$ .

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

[1]

[2]

[3]

[4]

[5]

[6]

@@ Line 10: / Line 10: @@
 In ''[[Principia Mathematica]]'', [[Bertrand Russell]] and [[A. N. Whitehead]] refer to "relations which generate a series"<ref>B. Russell & A. N. Whitehead (1910) [https://quod.lib.umich.edu/u/umhistmath/AAT3201.0001.001/283?rgn=full+text;view=pdf;q1=serial+relation Principia Mathematica, volume one, page 141] from [[University of Michigan]] Historical Mathematical Collection</ref> 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".<ref name="Yao2005">{{Cite book | doi = 10.1007/978-3-540-27778-1_15| chapter = Semantics of Fuzzy Sets in Rough Set Theory| title = Transactions on Rough Sets II| volume = 3135| pages = 309| series = [[Lecture Notes in Computer Science]]| year = 2004| last1 = Yao | first1 = Y. | isbn = 978-3-540-23990-1}}</ref>
 ==Algebraic characterization==