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

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