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

Some Basic Set Theory Proofs

  1. Dec 19, 2011 #1
    1. The problem statement, all variables and given/known data

    I'm working on some set theory stuff to prepare for Topology next semester. I'm actually working out of a Topology book from Dover Publications. I could really use some direction/correction.

    1. If S ⊂ T, then T - (T - S) = S.

    2. If S is any set, then ∅ ⊂ S.

    3. The attempt at a solution

    1. Let x ∈ (S ⊂ T). Therefore, x ∉ (T – S). If x ∉ (T – S), then x ∈ T – (T – S). But x ∈ (S ⊂ T). Therefore, S ⊂ (T - (T - S))
    Let x ∈ (T - (T - S)). This implies that x ∉ (T – S). Which implies that x ∈ S. Therefore, T – (T – S) ⊂ S and T - (T - S) = S.

    2. A set A is a subset of a set S if every element of A is in S. If A is ∅, then A has no elements. Therefore all of its elements are in S.
  2. jcsd
  3. Dec 19, 2011 #2


    Staff: Mentor

    VENN diagram-wise #1 true. S is a subset of T so T - S is T without S which looks like a donut on a VENN diagram. T minus the set (T - S) takes away all of T except for those elements in S hence T - (T - S) is S.

    I think your proofs look okay and nicely done too.

    For every element x of S you concluded that x is also an element of T - (T - S) and hence S is a subset of T - (T - S). Similarly for every x element of T - (T - S) you concluded that x is also an element of S and hence T - (T - S) is a subset of S. Finally you concluded that when S is a subset of T - (T - S) and when T - (T - S) is a subset of S then these two sets must be equal hence T - (T - S) = S .
  4. Dec 19, 2011 #3
    Can one use Venn diagrams as proofs? I've heard that's a no-no...
  5. Dec 19, 2011 #4


    Staff: Mentor

    I don't know if VENN diagrams are accepted as proof. I would think no because of the issues on set set boundaries like is a given point inside or outside the set.Conceptually though they help to visualize the truth of the statement so you know beforehand that it is in fact provable.
  6. Dec 19, 2011 #5


    User Avatar
    Science Advisor

    Ultimately, only rigorous way I know is to use inclusions: Show A=B if every x in A is contained in B, and viceversa.

    So, e.g., if x is in S, is x also in T-(T-S)? If y is in T-(T-S) , is y in S?

    Maybe a bit tedious, but maybe you'll get used to it after a while. I can't think of a better way. But then start with the parentheses: x is in T-S. Then x is not in S. Then we apply
    T-(T-S): elements of T-(T-S) are in T, but not in T-S.

    A good way of determining if a suggested equality holds, is to test if it holds for a couple of randomly-chosen elements. Of course, it is not a proof, but , if equality holds, then you should consider a proof first.
  7. Dec 19, 2011 #6

    To begin, this is a meaningless expression (that is, if the symbol "⊂" is the proper subset symbol- which I expect it is).

    Your proof should begin as follows:

    Suppose S ⊂ T. {from here, show that T - (T - S) = S by proving both directions (that is, that each set on either side of the equality is a subset of the other}

    2. This proof follows by the vacuous truth resulting from the logical form of the statement.
  8. Dec 19, 2011 #7
    I was just going by the pattern in my book. My book proved DeMorgan's laws this way. It starts out "Suppose x [itex]\in[/itex] [itex]\bigcup[/itex](T - Si)..."
  9. Dec 19, 2011 #8
    Ah, but that is quite different than what you have above, however. The statement x ∈ ⋃(T - Si) is valid since it asserts that x is an element of the set union of T - Si [⋃(T - Si), which IS a set]. Your previous post contains a nonsense expression since (S ⊂ T) is a statment about the sets S and T, and is not itself a set.
  10. Dec 20, 2011 #9


    User Avatar
    Science Advisor

    I imagine it may be shorthand for x is a element of S, which ( meaning S) is a subset of T, but I guess the author should explain so.

    Sorry, lockedup, that I did not read your OP, and my suggestion is then exactly what you
    were doing initially.
  11. Dec 20, 2011 #10
    This is what I meant. I guess I need to work on my use of notation.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook