Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
This doesn't seem to belong here. This site is about programming, not pure math. –  murgatroid99 Dec 6 '12 at 3:42
add comment

migrated from stackoverflow.com Dec 6 '12 at 12:16

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

1 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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.