Operating on Transitive Relationships Compatible with Operation

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\left({S, \circ}\right)$ be a magma.

Let $\mathcal R$ be a transitive relation on $S$ which is compatible with $\circ$.

Let $\mathcal R^=$ be the reflexive closure of $\mathcal R$.

Let $x, y, z, w \in S$.


Then the following implications hold:

$(1)\quad$ If $x \mathrel{\mathcal R} y$ and $z \mathrel{\mathcal R} w$, then $x \circ z \mathrel{\mathcal R} y \circ w$.

$(2)\quad$ If $x \mathrel{\mathcal R} y$ and $z \mathrel{\mathcal R^=} w$, then $x \circ z \mathrel{\mathcal R} y \circ w$.

$(3)\quad$ If $x \mathrel{\mathcal R^=} y$ and $z \mathrel{\mathcal R} w$, then $x \circ z \mathrel{\mathcal R} y \circ w$.

$(4)\quad$ If $x \mathrel{\mathcal R^=} y$ and $z \mathrel{\mathcal R^=} w$, then $x \circ z \mathrel{\mathcal R^=} y \circ w$.


Proof

We will prove $(1)$ and $(2)$. $(3)$ can be proven using precisely the same argument as $(2)$ and $(4)$ follows from $(1)$.

Suppose that $x \mathrel{\mathcal R} y$ and $z \mathrel{\mathcal R} w$.

By the definition of compatibility:

$x \mathrel{\mathcal R} y \implies x \circ z \mathrel{\mathcal R} y \circ z$
$z \mathrel{\mathcal R} w \implies y \circ z \mathrel{\mathcal R} y \circ w$

By transitivity:

$(1)\quad \left({x \mathrel{\mathcal R} y}\right) \land \left({z \mathrel{\mathcal R} w}\right) \implies x \circ z \mathrel{\mathcal R} y \circ w$

$\Box$


Suppose that $x \mathrel{\mathcal R} y$ and $z \mathrel{\mathcal R^=} w$.

By Reflexive Closure of Relation Compatible with Operation is Compatible, $\mathcal R^=$ is compatible with $\circ$.

By the definition of compatibility:

$x \mathrel{\mathcal R} y \implies x \circ z \mathrel{\mathcal R} y \circ z$
$z \mathrel{\mathcal R^=} w \implies y \circ z \mathrel{\mathcal R^=} y \circ w$

By Extended Transitivity:

$(2)\quad \left({x \mathrel{\mathcal R} y}\right) \land \left({z \mathrel{\mathcal R} w}\right) \implies x \circ z \mathrel{\mathcal R} y \circ w$

$\Box$


$(3)$ can be proven using precisely the same argument as $(2)$.

By Reflexive Closure of Relation Compatible with Operation is Compatible, $\mathcal R^=$ is compatible with $\circ$.

By Reflexive Closure of Transitive Relation is Transitive, $\mathcal R^=$ is transitive.

Thus $(4)$ follows from $(1)$.

$\blacksquare$