1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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]).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Question on Set Theory
  1. Set Theory Question (Replies: 2)

  2. Set theory question! (Replies: 1)

Loading...