Product of Subset with Intersection

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {G, \circ}$ be an algebraic structure.

Let $X, Y, Z \subseteq G$.

Then:

$X \circ \paren {Y \cap Z} \subseteq \paren {X \circ Y} \cap \paren {X \circ Z}$
$\paren {Y \cap Z} \circ X \subseteq \paren {Y \circ X} \cap \paren {Z \circ X}$

where $X \circ Y$ denotes the subset product of $X$ and $Y$.


Corollary

Let $\struct {G, \circ}$ be a group.

Let $X, Y, Z \subseteq G$ such that $X$ is a singleton.


Then:

$X \circ \paren {Y \cap Z} = \paren {X \circ Y} \cap \paren {X \circ Z}$
$\paren {Y \cap Z} \circ X = \paren {Y \circ X} \cap \paren {Z \circ X}$

where $X \circ Y$ denotes the subset product of $X$ and $Y$.


Proof 1

Let $x \in X, t \in Y \cap Z$.

By the definition of intersection, $t \in Y$ and $t \in Z$.


Consider $X \circ \paren {Y \cap Z}$.

We have $x \circ t \in X \circ \paren {Y \cap Z}$ by definition of subset product.

As $t \in Y$ and $t \in Z$, we also have $x \circ t \in X \circ Y$ and $x \circ t \in X \circ Z$.

The result follows.


Similarly, consider $\paren {Y \cap Z} \circ X$.

Then we have $t \circ x \in \paren {Y \cap Z} \circ X$ by definition of subset product.

As $t \in Y$ and $t \in Z$, we also have $t \circ x \in Y \circ X$ and $t \circ x \in Z \circ X$.

Again, the result follows.

$\blacksquare$


Proof 2

Consider the relation $\mathcal R \subseteq G \times G$ defined as:

$\forall g, h \in G: \left({g, h}\right) \in \mathcal R \iff \exists g \in X$

Then:

$\forall S \subseteq G: X \circ S = \mathcal R \left({S}\right)$

Then:

\(\displaystyle X \circ \left({Y \cap Z}\right)\) \(=\) \(\displaystyle \mathcal R \left({Y \cap Z}\right)\)
\(\displaystyle \) \(\subseteq\) \(\displaystyle \mathcal R \left({Y}\right) \cap \mathcal R \left({Z}\right)\) Image of Intersection under Relation
\(\displaystyle \) \(=\) \(\displaystyle \left({X \circ Y}\right) \cap \left({X \circ Z}\right)\)


Next, consider the relation $\mathcal R \subseteq G \times G$ defined as:

$\forall g, h \in G: \left({g, h}\right) \in \mathcal R \iff \exists h \in X$

Then:

$\forall S \subseteq G: S \circ X = \mathcal R \left({S}\right)$

Then:

\(\displaystyle \left({Y \cap Z}\right) \circ X\) \(=\) \(\displaystyle \mathcal R \left({Y \cap Z}\right)\)
\(\displaystyle \) \(\subseteq\) \(\displaystyle \mathcal R \left({Y}\right) \cap \mathcal R \left({Z}\right)\) Image of Intersection under Relation
\(\displaystyle \) \(=\) \(\displaystyle \left({Y \circ X}\right) \cap \left({Z \circ X}\right)\)

$\blacksquare$


Equality does not Hold

While it is the case that:

$X \circ \paren {Y \cap Z} \subseteq \paren {X \circ Y} \cap \paren {X \circ Z}$

it is not necessarily the case that:

$X \circ \paren {Y \cap Z} = \paren {X \circ Y} \cap \paren {X \circ Z}$


Sources