Subset Relation is Compatible with Subset Product

From ProofWiki
Jump to: navigation, search

Theorem

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

Let $\mathcal P \left({S}\right)$ be the power set of $S$.

Let $\circ_\mathcal P$ be the operation induced on $\mathcal P \left({S}\right)$ by $\circ$.


Then the subset relation $\subseteq$ is compatible with $\circ_\mathcal P$.


Corollary 1

Let $A, B, C, D \in \mathcal P \left({S}\right)$.

Let $A \subseteq B$ and $C \subseteq D$.


Then:

$A \circ_\mathcal P C \subseteq B \circ_\mathcal P D$


Corollary 2

Let $A,B \in \mathcal P \left({S}\right)$, the power set of $S$.

Let $A \subseteq B$.

Let $x \in S$.


Then:

$x \circ A \subseteq x \circ B$
$A \circ x \subseteq B \circ x$


Proof

Let $A, B, C \in \mathcal P \left({S}\right)$.

Let $A \subseteq B$.

Let $x \in A \circ_\mathcal P C$.

Then for some $a \in A$ and some $c \in C$:

$x = a \circ c$

Since $A \subseteq B$, $a \in B$.

Thus $x \in B \circ_\mathcal P C$.

Since this holds for all $x \in A \circ_\mathcal P C$:

$A \circ_\mathcal P C \subseteq B \circ_\mathcal P C$

The same argument shows that:

$C \circ_\mathcal P A \subseteq C \circ_\mathcal P B$

$\blacksquare$