# Homework Help: Question on Set Theory

1. Sep 9, 2011

### CornMuffin

1. The problem statement, all variables and given/known data
Let A = A1 x ... x An
B = B1 x ... x Bn
C = C1 x ... x Cn
Such that A,B,C are non empty, $A=B\cup C$ and $B\cap C = \emptyset$

prove that there exists a k in {1,...,n} such that $B_k\cap C_k = \emptyset$
and for $i\neq k$, $A_i = B_i = C_i$

2. Relevant equations

3. The attempt at a solution
I figure the best way to prove this is by induction.

for n=1, there is nothing to show, so I will start with n=2

Assume $B_1 \cap C_1 \neq \emptyset$ and $B_2 \cap C_2 \neq \emptyset$

then $B \cap C = (B_1 \times B_2 )\cap (C_1 \times C_2) = (B_1 \cap C_1) \times (B_2 \cap C_2)$

which implies that $B \cap C \neq \emptyset$ since $B_1 \cap C_1 \neq \emptyset$ and $B_2 \cap C_2 \neq \emptyset$

but this is a contradiction to our conditions, therefore, there exists a k in {1,...,n} such that $B_k\cap C_k = \emptyset$

it seems like this can be easily extended for any n

but i am having trouble proving the second part of the problem:
for $i\neq k$, $A_i = B_i = C_i$

I tried using proof by contradiction for n=2, but i couldn't get anywhere with that

Any hints on what I should try?

2. Sep 9, 2011

### micromass

You need to prove two things:

$$B_i\subseteq A_i~\text{and}~A_i\subseteq B_i$$

The first is not so hard: pick $x_i\in B_i$, extend it to an element of B. And use that $B\cup C=A$.

The second is more difficult. Pick $x_i\in A_i$. Assume that it is not in $B_i$. Try to extend $x_i$ to an element you know is not in $B\cup C$. This will be a contradiction. (hint: pick a $x_k\in C_k$).