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!

Set theory proof

  1. Feb 3, 2009 #1
    1. The problem statement, all variables and given/known data
    A,B and C are sets.
    Prove (A∩B)C = AC∩BC is FALSE
    That is, I have to give a counterargument for this statement.

    2. Relevant equations
    I can't find a counterargument directly. My professor suggest trying to prove the statement to find a problem and come up with the counterargument.
    To prove this is false, first must prove that
    AC∩BC[tex]\subseteq[/tex](A∩B)C is false, OR
    (A∩B)C[tex]\subseteq[/tex]AC∩BC is false.

    3. The attempt at a solution
    I have proven (A∩B)C[tex]\subseteq[/tex]AC∩BC is true by:
    • w is a string
    • Let w[tex]\in[/tex](A∩B)C then [tex]\exists[/tex]u[tex]\in[/tex](A∩B)and [tex]\exists[/tex]v[tex]\in[/tex]C where w=uv
    • If [tex]\exists[/tex]u[tex]\in[/tex]A then w=uv[tex]\in[/tex]AC and [tex]\exists[/tex]u[tex]\in[/tex]B and w=uv[tex]\in[/tex]BC
    • Hence (A∩B)C[tex]\subseteq[/tex]AC∩BC

    However, I wasn't able to prove AC∩BC[tex]\subseteq[/tex](A∩B)C is false.

    • w is a string
    • Let w[tex]\in[/tex]AC and w[tex]\in[/tex]BC
    • Then [tex]\exists[/tex]u[tex]\in[/tex]A and [tex]\exists[/tex]v[tex]\in[/tex]C where w=uv
    • Also [tex]\exists[/tex]u[tex]\in[/tex]B and [tex]\exists[/tex]v[tex]\in[/tex]C where w=uv
    • Then [tex]\exists[/tex]u[tex]\in[/tex]A∩B and [tex]\exists[/tex]v[tex]\in[/tex]C
    • Hence AC∩BC[tex]\subseteq[/tex](A∩B)C ?

    My professor said that the second part is wrong, but I have already tried over an hour but still can not make the second part false nor just come up with a counterargument.

    I'm really not good with logic, can anyone help me?
    I still have a lot of programming assignment waiting for me to do.
  2. jcsd
  3. Feb 7, 2009 #2
    you don't really need to prove anything..
    you just have to come up with a counterexample

    If you draw a Venn diagram of the 3 sets you can construct your counter example

    Good luck!
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Set theory proof
  1. Set theory hash-tables (Replies: 0)