Element Argument Proofs - Set theory

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.

1. A × (B ∩ C) = (A × B) ∩ (A × C)
2. 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).
3. 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.
4. By definition of a subset, (A × B) ∩ (A × C) is a subset of A × (B ∩ C).
5. Therefore A × (B ∩ C) = (A × B) ∩ (A × C).

Is that at least a little right? Thanks.

-
This doesn't seem to belong here. This site is about programming, not pure math. –  murgatroid99 Dec 6 '12 at 3:42

migrated from stackoverflow.comDec 6 '12 at 12:16

This question came from our site for professional and enthusiast programmers.

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.

-