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!

Proof involving basic set theory

  1. Apr 22, 2014 #1
    1. Suppose A \ B[itex]\subseteq[/itex]C[itex]\cap[/itex]D and x[itex]\in[/itex]A. Prove that if x [itex]\notin[/itex]D then x[itex]\in[/itex]B



    2. None



    3. Proof: Suppose A \ B[itex]\subseteq[/itex]C[itex]\cap[/itex]D, x[itex]\in[/itex]A, and x[itex]\notin[/itex]D. It follows that our first assumption is equivalent to A due to our third assumption. Thus, B[itex]\subseteq[/itex]C[itex]\cap[/itex]D is disjoint and either x[itex]\notin[/itex]B[itex]\subseteq[/itex]C or x[itex]\notin[/itex]D. Let us temporarily assume that it is the case that x[itex]\notin[/itex]B[itex]\subseteq[/itex]C, then this may be expressed equivalently as x[itex]\in[/itex]B and x[itex]\notin[/itex]C, a contradiction with the definition of subsets, thus x must be an element of B and C provided x[itex]\notin[/itex]D


    I'm not entirely sure if all of my reasoning is correct.
     
    Last edited by a moderator: Apr 22, 2014
  2. jcsd
  3. Apr 22, 2014 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes, the reasoning is rubbish and it's not even very grammatical. I think the easiest way to prove this is to assume that given x is in A and x is NOT in D, assume that x is NOT in B. Can you show that leads to a contradiction? That's something like what you were doing, but could you express it more clearly?
     
    Last edited by a moderator: Apr 22, 2014
  4. Apr 23, 2014 #3
    Thank you for your response, I thought that would be the case. The set of exercises this problem comes from are specifically of the form, "If P, then Q. Assume P then prove Q." so I'd prefer to stick to that method of attack. Could you point out some of the things that are incorrect about my reasoning? That would be extremely helpful. I'll attempt to express the proof more clearly after I get a bit of sleep.
     
  5. Apr 23, 2014 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Let's start with the first sentence. "It follows that our first assumption is equivalent to A due to our third assumption." What does that mean?

    And let's stick with the indirect proof for just a bit. Can you show that if you assume that given x is in A and x is NOT in D and x is NOT in B, then x is in A\B and x is not in C∩D?
     
    Last edited: Apr 23, 2014
  6. Apr 23, 2014 #5

    Mark44

    Staff: Mentor

    Is there a mistake in the problem statement? It seems to me that the last statement should be ##x \in C##, not ##x \in B##.
     
  7. Apr 23, 2014 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    That wouldn't be true. Pick A={1,2,3}, B={2,3}, C={1,2}, D={1}. Now pick x=3.
     
    Last edited: Apr 23, 2014
  8. Apr 24, 2014 #7
    I believe that first sentence is a result of my confusion between free and bound variables while examing the definition of intersections. I thought of it as, "For all x, x is in C and x is in D. x is not in D. Therefore, there is not an x such that x is in C and x is in D." Then that lead me to the conclusion that C intersect D is equal to the null set. Also, assuming x was not in D then wouldn't x not be present in the intersection set as well as B due to B being a subset of C intersect D?
     
    Last edited: Apr 24, 2014
  9. Apr 24, 2014 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I don't understand why you think those things. Why do you think A is a subset of C intersect D? A\B is. Not A. Pick some example sets like I did before.
     
    Last edited: Apr 24, 2014
  10. Apr 24, 2014 #9

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    Are you misreading the problem statement? The first assumption says that the set ##A\backslash B## is a subset of ##C\cap D##. It sounds like you're somehow parsing the expression as ##A \backslash (B \subset C \cap D)## (whatever that's supposed to mean) otherwise why do you think B is a subset of the intersection of C and D?
     
  11. Apr 24, 2014 #10
    That is exactly what I did, thank you so much. Will post new proof shortly.
     
    Last edited: Apr 24, 2014
  12. Apr 24, 2014 #11

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Well that's perceptive. I never would have thought of reading it that way, since it's wrong. That does explain a lot of strange notions.
     
  13. Apr 24, 2014 #12
    Theorem: Suppose that ##A\backslash B## is a subset of ##C\cap D##, and x is an element of [itex]\large A[/itex]. If x is not an element of [itex]\large D[/itex], then x is an element of [itex]\large B[/itex]

    Proof:
    Suppose that ##A\backslash B## is a subset of ##C\cap D##, x is an element of [itex]\large A[/itex], and x is not an element of [itex]\large D[/itex]. By our assumptions, x is not an element of ##C\cap D## by definition. Thus, x must not be an element of ##A\backslash B## and, in this case, occurs when x is an element of [itex]\large A[/itex] as well as [itex]\large B[/itex]. We assume x is an element of [itex]\large A[/itex] so it must be the case that x is an element of [itex]\large B[/itex] provided x is not an element of [itex]\large D[/itex]. Therefore, If x is not an element of [itex]\large D[/itex], then x is an element of [itex]\large B[/itex] as was to be proved.
     
  14. Apr 24, 2014 #13

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes, that works. Well done.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proof involving basic set theory
  1. Set theory Proof help (Replies: 4)

  2. Set Theory Proof (Replies: 3)

Loading...