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 attempt - Basic Set Theory

  1. May 16, 2013 #1

    reenmachine

    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data

    Prove that if A and B are sets , then ##A \subseteq B \ \ \leftrightarrow \ \ A - B = \varnothing##


    3. The attempt at a solution

    Let ##A \subseteq B## be arbitrary.The definition of ##A \subseteq B## implies that ##\forall x \in A## , ##x \in B##.This implies that ##A - B = \varnothing## , which also disprove that ##A - B ≠ \varnothing##.Since we disproved the previous statement , we proved that ##A \subseteq B \ \ \leftrightarrow \ \ A - B = \varnothing##.

    I think I understand the logic of why the statement is true pretty clearly , but I'm not sure if I took a shortcut somewhere or made a bad notation choice (or any other mistakes).Or do I have to explain why ##\forall x \in A## , ##x \in B## implies all of this?

    Any thoughts would be appreciated.Thank you!
     
    Last edited: May 16, 2013
  2. jcsd
  3. May 16, 2013 #2

    reenmachine

    User Avatar
    Gold Member

    Second version:

    If ##A - B ≠ \varnothing## , then at least one ##x \in A## isn't in ##B##.Since the definition of ##A \subseteq B## means that ##\forall x \in A## , ##x \in B## , those previous statements implies that ##A \subseteq B \ \ \leftrightarrow \ \ A - B = \varnothing##.
     
  4. May 16, 2013 #3

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    With these "if and only if" proofs you need to be careful that you've proved both directions (not the same direction twice). Your proof above only does one direction.
     
  5. May 16, 2013 #4
    You're pretty much there, but when proving [itex]p \leftrightarrow q[/itex], you first assume that p is true and show that [itex]p \rightarrow q[/itex] and then you assume that q is true and show that [itex] q \rightarrow p[/itex]. So really, all you need to do is combine your two versions of the proof. Also, you could use the definition of A - B more explicitly, but I don't think that's as important.
     
  6. May 17, 2013 #5

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I don't see anything wrong here, but once you have concluded that ##A-B=\varnothing##, there's no need to add that this implies that it's not the case that ##A-B\neq\varnothing##.

    Also, the statements at the start of the proof can be a bit more precise. What you're trying to prove here is that the implication
    $$A\subseteq B\Rightarrow A-B=\varnothing$$ is true for all sets A and B. So it can't be a bad idea to start like this: "Let A and B be arbitrary sets. Suppose that ##A\subseteq B##." You can also combine these two sentences into one by saying "Let A and B be arbitrary sets such that ##A\subseteq B##."

    Then you need to prove that ##A-B=\varnothing##, and here you definitely took a shortcut. You pretty much just said that it's true. What you need to do is to prove that the definition of A-B (together with our assumption about A and B) implies that this equality holds. This is simple enough that I think it's OK to just say that ##A-B=\{x\in A:x\notin B\}=\varnothing##. This way you're at least letting the reader know that you're using the definition of A-B.

    If you want to show this in more detail, you can e.g. set out to derive a result that's known to be false from the assumption that A-B is non-empty. If you succeed, then you have proved that A-B is empty. Another option (which turns out to be pretty much the same) is to prove that every element of A-B is an element of ∅, and every element of ∅ is an element of A-B.

    When you're done with this, you still have to prove the other implication of course. You can start like this: "Let A,B be arbitrary sets such that A-B=∅. Let ##x\in A## be arbitrary." Then you prove that ##x\in B##.

    Edit: One more thing... I would interpret the statement "Let ##A\subseteq B## be arbitrary" as a shortened version of "Let A be an arbitrary set such that ##A\subseteq B##". So it leaves B undeclared. This is why it's better to say "Let A and B be arbitrary sets such that ##A\subseteq B##".
     
    Last edited: May 17, 2013
  7. May 21, 2013 #6

    reenmachine

    User Avatar
    Gold Member

    Ok I'm back in full force this week !

    I'm not sure how to do the bolded (not sure I understand what you want me to do).

    My try at the proof again:

    Let ##A## and ##B## be arbitrary sets.Suppose that ##A \subseteq B##.By definition , this implies that ##\forall x \in A## , ##x \in B##.Since ##A - B = \{x \in A : x \notin B \}## , this combined with our previous assumptions and implications means that ##A - B = \varnothing##.

    Let ##A## and ##B## be arbitrary sets such that ##A - B = \varnothing##.Let ##x \in A## be arbitrary.The result of ##A - B = \varnothing## implies that all ##x \in A## have been substracted , which implies that ##\forall x\in A## , ##x \in B##.This proves that ##A \subseteq B \leftrightarrow A - B = \varnothing##.

    Thoughts?

    About the quote , what would I need to do to "derive a result that's known to be false from the assumption that A-B is none-empty"?

    EDIT: Is it something like this:

    If ##A - B = Y## , then ##Y = \{x \in A : x \notin B \}## , this means that for some ##x \in A## , ##x \notin B##.This implies that ##A \not\subseteq B##.If ##A \subseteq B## , then ##\forall x \in A## , ##x \in B##.From the definition of ##Y## , this prove that if ##A \subseteq B## , then ##A - B = \varnothing##.
     
    Last edited: May 21, 2013
  8. May 21, 2013 #7

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The word "implications" sounds odd to me. I suppose you mean "results", as in "our assumptions and previous results". If you say "previous assumptions", it sounds like you want to distinguish the assumptions you made before from an assumption you're making right now. And if you say "Since (something), this implies (something)" I would interpret the word "this" as referring to the statement in the sentence before this one. And in this case, that statement alone implies the next result. So there's no need to mention assumptions and previous results. The word "this" already refers to the previous result.

    Let's say that you find a result P, and then you say "Since Q, this implies R". To me this means that Q is true, and that P and Q together imply R, because the word "this" is a reference to P. You seem to interpret these sentences as saying only that Q is true and Q implies R. (If that's what we want to say, we would only say "Since Q, P". There wouldn't be a "this" in the sentence).

    Here's a version of the proof of this implication that I like better than the version in my previous post:

    Let A and B be arbitrary sets. Suppose that ##A\subseteq B##. This means that every element of A is an element of B. Since ##A-B=\{x\in A:x\notin B\}##, this implies that ##A-B=\varnothing##.

    Note that every "this" refers to the previous sentence.


    "The result of ##A-B=\varnothing## implies..." Shouldn't that be "The assumption that ##A-B=\varnothing## implies..."?

    What this assumption implies is not that "all ##x\in A## have been subtracted". (What does that mean?) Since ##A-B=\{x\in A:x\notin B\}##, what's implied is that there are no elements of A that satisfy the condition ##x\notin B##.

    Prove that if ##A-B\neq\varnothing##, then pigs can fly. You can of course substitute any false statement for "pigs can fly", for example "it's not true that ##A\subseteq B##".

    I assume that the start is supposed to be "If ##A-B\neq\varnothing##, then for some ##x\in A##, ##x\notin B##. (This would be a good start). This implies that ##A\not\subseteq B##.

    That's where the proof (of the first implication) should end. You have not proved the equivalence. What you have done is to prove the implication
    $$A\subseteq B\Rightarrow A-B=\varnothing$$ by proving the equivalent implication
    $$A-B\neq\varnothing \Rightarrow A\not\subseteq B.$$
     
    Last edited: May 21, 2013
  9. May 21, 2013 #8

    reenmachine

    User Avatar
    Gold Member

    (EDIT: you posted while I was editing , then the site froze for a couple of minutes , here's my fresher version)

    Let ##A## and ##B## be arbitrary sets such that ##A \subseteq B##.This implies that all elements of ##A## are elements of ##B##.Since ##A - B = \{ x \in A : x \notin B\}## , our assumption implies that no ##x \in A## satisfies the property and therefore that ##A - B = \varnothing##.

    Now let ##A## and ##B## be arbitrary sets such that ##A - B = \varnothing##.Since ##A - B = \{x \in A : x \notin B \}## , our assumption implies that no ##x \in A## satisfies that property and therefore that ##\forall x \in A## , ##x \in B##.This implies that ##A \subseteq B##.

    This prove that ##A \subseteq B \leftrightarrow A - B = \varnothing##

    Thanks!!!
     
    Last edited: May 21, 2013
  10. May 21, 2013 #9

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It's a bit odd to first mention that the assumption ##A\subseteq B## implies that every element of A is an element of B, and then immediately ignore that result and refer back to the assumption ##A\subseteq B## instead of the result "every element of A is an element of B". I think you should also state the property explicitly instead of just referring to it as "that property".

    Good, but it would be easier to understand if you state explicitly what property you're talking about.

    Here it's not clear that the word "this" refers back to both of the preceding two paragraphs.
     
  11. May 21, 2013 #10

    reenmachine

    User Avatar
    Gold Member

    All fair points.Thanks a lot!

    Corrected version:

    Let ##A## and ##B## be arbitrary sets such that ##A \subseteq B##.This implies that all elements of ##A## are elements of ##B##.Since ##A - B = \{ x \in A : x \notin B\}## , the fact that all elements of ##A## are elements of ##B## implies that no ##x \in A## satisfies the property ##x \notin B## and therefore that ##A - B = \varnothing##.

    Now let ##A## and ##B## be arbitrary sets such that ##A - B = \varnothing##.Since ##A - B = \{x \in A : x \notin B \}## , our assumption implies that no ##x \in A## satisfies the property ##x \notin B## and therefore that ##\forall x \in A## , ##x \in B##.This implies that ##A \subseteq B##.

    The two previous paragraphs proves that ##A \subseteq B \leftrightarrow A - B = \varnothing##
     
    Last edited: May 21, 2013
  12. May 21, 2013 #11

    reenmachine

    User Avatar
    Gold Member

    Just a random question , if ##A - B = \{x \in A : x \notin B\}## , then what is ##A + B## ???

    I can't start a notation by saying "The set of all ##x \in A## such that..." because then an element only in ##B## wouldn't be included.Is it ##A \cup B##? So ##\{ x : x \in A \ or \ x \in B\}## ?
     
    Last edited: May 21, 2013
  13. May 21, 2013 #12

    reenmachine

    User Avatar
    Gold Member

    Just wondering , would it better to indicate at the end of both paragraphs that I proved both statements in the form of ##p \rightarrow q## and ##q \rightarrow p##? (even if only to make it clearer to the reader)

    Like this: (read the last sentence of both paragraphs)

    Let ##A## and ##B## be arbitrary sets such that ##A \subseteq B##.This implies that all elements of ##A## are elements of ##B##.Since ##A - B = \{ x \in A : x \notin B\}## , the fact that all elements of ##A## are elements of ##B## implies that no ##x \in A## satisfies the property ##x \notin B## and therefore that ##A - B = \varnothing##.This prove that ##A \subseteq B \rightarrow A - B = \varnothing##.

    Now let ##A## and ##B## be arbitrary sets such that ##A - B = \varnothing##.Since ##A - B = \{x \in A : x \notin B \}## , our assumption implies that no ##x \in A## satisfies the property ##x \notin B## and therefore that ##\forall x \in A## , ##x \in B##.This implies that ##A \subseteq B##.This prove that ##A - B = \varnothing \rightarrow A \subseteq B##.

    The two previous proofs proves that ##A \subseteq B \leftrightarrow A - B = \varnothing##
     
    Last edited: May 21, 2013
  14. May 21, 2013 #13

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I think that's just fine.
     
  15. May 21, 2013 #14

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Doesn't mean much if you don't have a definition for it. It's not a notation you generally use in set theory.
     
  16. May 22, 2013 #15

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yes, that's an improvement, in the sense that it's easier to understand the proof. Even better would be to say at the start of each paragraph what it's going to prove.

    There's still one thing in your proof that looks odd.

    You're saying "Since [definition of A-B], ##A\subseteq B## implies that no ##x\in A## satisfies the condition ##x\notin B##..." But this suggests that you need both the definition of A-B and the assumption ##A\subseteq B## to show that no ##x\in A## is such that ##x\notin B##. You clearly only need the latter.

    Then you continued with "and therefore that ##A-B=\varnothing##". The "therefore" will be interpreted as a reference only to the result that there's no ##x\in A## such that ##x\notin B##. It will not be interpreted as a reference to that result and the definition of A-B.

    I think that's the last problem with the logic of your proof, so I will nitpick your language a bit.
    • It's customary to type a space between a period that ends a sentence and the letter that begins the next.
    • The phrase "satisfies the property" sounds a little bit odd to me. I'm not sure that it's wrong, but "has the property" and "satisfies the condition" both sound better to me. Hm, now that I think about it, there's a minor issue with "has the property" as well. It's weird to say "x has the property P(x)" when P is the property and P(x) is the statement "x has property P". Maybe it would be an improvement just to add the word "that", as in "no ##x\in A## has the property that ##x\notin B##". Yes, I like that better, because now we're not calling ##x\notin B## a "property". The property here is "not being an element of B". ##x\notin B## is the statement that x has that property. You can think of this property as a function P that takes an arbitrary set y to the statement ##y\notin B##. Another way to say what we want to say is "no ##x\in A## is such that ##x\notin B##".
    • You said "prove" where "proves" would have been correct, and "proves" where "prove" would have been correct.
     
    Last edited: May 22, 2013
  17. May 22, 2013 #16

    reenmachine

    User Avatar
    Gold Member

    I'll get back at you a little later with the corrected version of the proof but I wanted to ask you something about this comment.

    Can I say " no ##x \in A## has the property ##\notin B## " ?

    This version is "x has the property P" instead of "x has the property P(x)".

    Thank you for your comments on my english , I don't work on it as much as I used to so criticisms are always welcomed.

    I admit I always went with my gut in these cases :rofl:

    Is there a simple rule to follow?
     
    Last edited: May 22, 2013
  18. May 22, 2013 #17

    reenmachine

    User Avatar
    Gold Member

    We will attempt to prove that ##A \subseteq B \rightarrow A - B = \varnothing##. Let ##A## and ##B## be arbitrary sets such that ##A \subseteq B##. This implies that all elements of ##A## are elements of ##B##. We know that ##A - B = \{ x \in A : x \notin B\}##. The fact that all elements of ##A## are elements of ##B## implies that no ##x \in A## has the property that ##x \notin B## .This implies that ##A - B = \varnothing##.

    We will now attempt to prove that ##A - B = \varnothing \rightarrow A \subseteq B##. Let ##A## and ##B## be arbitrary sets such that ##A - B = \varnothing##. We know that ##A - B = \{x \in A : x \notin B \}##. Our assumption implies that no ##x \in A## has the property that ##x \notin B## and therefore that ##\forall x \in A## , ##x \in B##. This implies that ##A \subseteq B##.

    Both of these proofs prove that ##A \subseteq B \leftrightarrow A - B = \varnothing##
     
  19. May 22, 2013 #18

    reenmachine

    User Avatar
    Gold Member

    So substraction is more present than addition in set theory?
     
  20. May 22, 2013 #19

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    This would make sense in this specific case, but it's a non-standard way of saying it, so you should avoid it anyway. It would also be hard to generalize this idea to situations where P(x) is a more complicated statement about x.


    A good rule of thumb is: Put an s at the end of the verb if and only if it refers back to just one thing.

    It's "he proves" and "it proves", but "they prove", because "he" and "it" refers to one thing, and "they" to several things. The terrible movie "Jay and Silent Bob strike back" has "strike" in the title rather than "strikes", because "Jay and Silent Bob" are two people.

    Unfortunately it's not always this easy. It's "everyone proves", "no one proves" and "neither of them proves". I'm not sure how to explain these. I suppose the first two can be explained by the way they use the word "one". "Everyone proves" means that "one proves, no matter who that one is". In more mathematical terms, "for all x, x proves". Here x is just one thing. "Neither" can be interpreted as "not one, nor the other one".
     
  21. May 22, 2013 #20

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    This is good, but I can still nitpick a few things:

    1. The phrase "let A and B" comes after the first time you mention those sets, so the symbols A and B are undeclared the first time you mention them.

    2. The last sentence can be interpreted as saying that each of the two paragraphs separately prove the equivalence.

    There are at least two ways to solve issue 1 above. Keep in mind that what we want to do is to prove that the equivalence ##A\subseteq B\Leftrightarrow A-B=\varnothing## holds for all sets A and B.

    a) Start the first paragraph like this: We will attempt to prove that for all sets A and B, we have ##A\subseteq B\to A-B##. Let A and B be...

    Then you start the second paragraph in a similar way.

    b) Start the proof like this: Let A and B be arbitrary sets.

    Start the first paragraph after that like this: We will attempt to prove that ##A\subseteq B\to A-B=\varnothing##. Suppose that ##A\subseteq B##.

    Then you start the second paragraph in a similar way.

    I prefer option b.
     
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 attempt - Basic Set Theory
  1. Set Theory Proof (Replies: 3)

  2. Set theory proof help? (Replies: 6)

  3. Set theory, proof (Replies: 3)

Loading...