1. Not finding help here? Sign up for a free 30min 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!

Sets - Proving every set is a subset of itself

  1. Sep 7, 2009 #1
    1. The problem statement, all variables and given/known data

    Prove that for every set S, S [tex]\subseteq[/tex] S. Use 'proof by cases'.


    2. Relevant equations

    A [tex]\subseteq[/tex] B iff {X: X [tex]\in[/tex] A --> X [tex]\in[/tex] B}

    3. The attempt at a solution

    I know that A is a subset of B if every element of A is also an element of B. In the case of S [tex]\subseteq[/tex] S, all I can figure out, simply, is:

    For every element x in set S, x is an element of S, therefore, S [tex]\subseteq[/tex] S

    I do not know how to express this proof in terms of 'cases'. Any help would be appreciated.
     
  2. jcsd
  3. Sep 7, 2009 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    You are required to use "cases"? How strange.

    Try this:
    case 1: Suppose [itex]x\in S[/itex] then ...

    case 2: Suppose [itex]x\notin S[/itex] then ...
     
  4. Sep 7, 2009 #3

    statdad

    User Avatar
    Homework Helper

    Perhaps "cases" means to make a distinction between empty and non-empty sets.
     
  5. Sep 7, 2009 #4
    @HallsofIvy and @statdad: Thank you for the response.

    Should it be something like this?

    @HallsofIvy:

    For S [tex]\subseteq[/tex] S : [tex]\forall[/tex] x(x [tex]\in[/tex] S [tex]\rightarrow[/tex] x [tex]\in[/tex] S)

    Case 1: Let x [tex]\in[/tex] S, then x [tex]\in [/tex] S. p[tex]\rightarrow[/tex]p is true, therefore S [tex]\subseteq[/tex] S

    Case 2: Let x [tex]\notin[/tex] S, then p is false. Since the antecedent is false in a conditional statement, the condition is true by vacuous proof. Therefore S [tex]\subseteq[/tex] S.


    AND/OR


    @statdad:

    For S [tex]\subseteq[/tex] S : [tex]\forall[/tex] x(x [tex]\in[/tex] S [tex]\rightarrow[/tex] x [tex]\in[/tex] S)

    Case 1: Let S be an empty set, then S = [tex]\phi[/tex]. Let x [tex]\in [/tex] S. For S [tex]\subseteq[/tex] S : [tex]\forall[/tex] x(x [tex]\in[/tex] [tex]\phi[/tex] [tex]\rightarrow[/tex] x [tex]\in[/tex] S). Since [tex]\phi[/tex] has no elements, the first statement is false and thus the whole condition is true by vacuous proof. Therefore S [tex]\subseteq[/tex] S

    Case 2: Let S be a non-empty set, Let x [tex]\in[/tex] S, then x [tex]\in [/tex] S. p[tex]\rightarrow[/tex]p is true, therefore S [tex]\subseteq[/tex] S



    I hope I interpreted the cases correctly. Please advise.
     
  6. Sep 7, 2009 #5
    Upon discussion with the lecturer (apparently I was wrong, earlier, to think that lecturers are not supposed to help with assignments), he mentioned the same thing as statdad: use the two cases of S being an empty and a non-empty set.

    Thank you everyone. PF and its helping members are great.

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




Similar Discussions: Sets - Proving every set is a subset of itself
Loading...