Union of Relations Compatible with Operation is Compatible

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\left({S, \circ}\right)$ be a closed algebraic structure.

Let $\mathcal F$ be a family of relations on $S$.

Let each element of $\mathcal F$ be compatible with $\circ$.

Let $\mathcal Q = \bigcup \mathcal F$.


Then $Q$ is a relation compatible with $\circ$.


Proof

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

Let $x \mathop {\mathcal Q} y$.

Then for some $\mathcal R \in \mathcal F$:

$x \mathop{\mathcal R} y$.

Since $\mathcal R$ is a relation compatible with $\circ$:

$\left({x \circ z}\right) \mathop {\mathcal R} \left({y \circ z}\right)$

Since $\mathcal R \in \mathcal F$:

$\mathcal R \subseteq \bigcup \mathcal F = \mathcal Q$

Thus

$\left({x \circ z}\right) \mathop {\mathcal Q} \left({y \circ z}\right)$

We have shown that:

$\forall x, y, z \in S: x \mathop {\mathcal Q} y \implies \left({x \circ z}\right) \mathop {\mathcal Q} \left({y \circ z}\right)$

A similar argument shows that:

$\forall x, y, z \in S: x \mathop {\mathcal Q} y \implies \left({z \circ x}\right) \mathop {\mathcal Q} \left({z \circ y}\right)$

So $Q$ is a relation compatible with $\circ$.

$\blacksquare$