Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Question on Set Theory

  1. Sep 9, 2011 #1
    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, [itex]A=B\cup C[/itex] and [itex]B\cap C = \emptyset [/itex]

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

    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 [itex] B_1 \cap C_1 \neq \emptyset [/itex] and [itex]B_2 \cap C_2 \neq \emptyset [/itex]

    then [itex] 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) [/itex]

    which implies that [itex]B \cap C \neq \emptyset [/itex] since [itex]B_1 \cap C_1 \neq \emptyset [/itex] and [itex]B_2 \cap C_2 \neq \emptyset [/itex]

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

    it seems like this can be easily extended for any n

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

    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. jcsd
  3. Sep 9, 2011 #2
    You need to prove two things:

    [tex]B_i\subseteq A_i~\text{and}~A_i\subseteq B_i[/tex]

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

    The second is more difficult. Pick [itex]x_i\in A_i[/itex]. Assume that it is not in [itex]B_i[/itex]. Try to extend [itex]x_i[/itex] to an element you know is not in [itex]B\cup C[/itex]. This will be a contradiction. (hint: pick a [itex]x_k\in C_k[/itex]).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook