Demonic composition

From HandWiki
Revision as of 19:08, 6 March 2023 by Smart bot editor (talk | contribs) (linkage)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

In mathematics, demonic composition is an operation on binary relations that is similar to the ordinary composition of relations but is robust to refinement of the relations into (partial) functions or injective relations. Unlike ordinary composition of relations, demonic composition is not associative.

Definition

Suppose [math]\displaystyle{ R }[/math] is a binary relation between [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] and [math]\displaystyle{ S }[/math] is a relation between [math]\displaystyle{ Y }[/math] and [math]\displaystyle{ Z. }[/math] Their right demonic composition [math]\displaystyle{ R \textbf{;}^{\to} S }[/math] is a relation between [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Z. }[/math] Its graph is defined as [math]\displaystyle{ \{(x, z) \ : \ x \mathrel{(S \circ R)} z \text{ and for all } y \in Y \ (x \mathrel{R} y \text{ implies } y \mathrel{S} z)\}. }[/math]

Conversely, their left demonic composition [math]\displaystyle{ R \textbf{;}^{\leftarrow} S }[/math] is defined by [math]\displaystyle{ \{(x, z) \  : \ x \mathrel{(S \circ R)} z \text{ and for all } y \in Y \ (y \mathrel{S} z \text{ implies } x \mathrel{R} y)\}. }[/math]

References

  • Backhouse, Roland; van der Woude, Jaap (1993), "Demonic operators and monotype factors", Mathematical Structures in Computer Science 3 (4): 417–433, doi:10.1017/S096012950000030X .