This is an exercise on my study guide for my discrete applications class.
Prove by element argument: A × (B ∩ C) = (A × B) ∩ (A × C)
Now I know that this is the distributive law, but I'm not sure if this proof would work in the exact same way as a union problem would, because I know how to solve that one. Here is my thinking thus far:
Proof: Suppose A, B, and C are sets.
- A × (B ∩ C) = (A × B) ∩ (A × C)
- Case 1 (a is a member of A): if a belongs to A, then by the definition of the cartesian product, a is also a member of A x B and A x C. By definition of intersection, a belongs to (A × B) ∩ (A × C).
- Case 2 (a is a member of B ∩ C): a is a member of both B and C by intersection. a is a member of (A × B) ∩ (A × C) by the definition of intersection.
- By definition of a subset, (A × B) ∩ (A × C) is a subset of A × (B ∩ C).
- Therefore A × (B ∩ C) = (A × B) ∩ (A × C).
Is that at least a little right?
Thanks.
Best Answer
No, you're not doing it completely right, the cartesian product produces an element that is a pair of elements from both subsets.
The definition of the cartesian product.
Def. $X\times Y = \{ (x,y) : x \in X\text{ and }y \in Y \}$.
PROOF.
$Z = A \times (B \cap C) = \{ (a,y) : a \in A\text{ and }y \in B \cap C \}$
$W = (A \times B) \cap (A \times C) = \{ (a,b) : a \in A\text{ and }b \in B \} \cap \{ (a,c) : a \in A\text{ and }c \in C \}$
For all $a \in A$:
Case 1. $b \in C$. If $b \in C$ then $(a,b) \in Z$. Also $(a,b) \in W$.
Case 2. $b \notin C$. If $b \notin C$, then $b$ is not in $B \cap C$. Then $(a,b)$ is not in $Z$. $b$ is also not in $A \times C$, so it's not in $W$.
The rest follows by the symmetry of intersection. $C \cap B$ is equivalent to $B \cap C$. Relabel $B$ as $C$, and vice versa. Apply case 1 and case 2.
QED.