Results 1 to 4 of 4

Math Help - Question with power sets

  1. #1
    Newbie
    Joined
    Oct 2013
    From
    Texas
    Posts
    2

    Question with power sets

    How can I prove or disprove that no set is equal to its power set?
    (I'm relatively new to Discrete Mathematics so this may be a very simple question.)

    Things I think might help with proving this are:

    The definition of a power set: Given a set S, the power set of S is the set of all subsets of the set S.
    (I have trouble wrapping my head around what this means)

    and

    Every set is a subset of itself.

    So if a power set is a set, then it contains a subset of itself...does that mean anything for this problem?

    Any help is appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,904
    Thanks
    764

    Re: Question with power sets

    Let's start with a small discrete example: S = \{1,2\}. Then, the power set of S would be the set \{\emptyset, \{1\}, \{2\}, \{1,2\}\}. So, it contains all subsets with zero elements (the empty set), all subsets with 1 element, and all subsets with two elements. How do you show that two sets are equal? You show that the first set is a subset or equal to the second set. Then, you show that the second set is a subset or equal to the first. So, since S \subseteq S, we know that S \in P(S) (the power set of S) since P(S) contains all subsets of S. But, S \notin S since no set can contain itself (that is one of the axioms of set theory). So, P(S) contains at least one element that S does not contain. Hence, the two sets cannot be equal.
    Last edited by SlipEternal; October 1st 2013 at 12:26 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2013
    From
    Texas
    Posts
    2

    Re: Question with power sets

    Ah, that makes perfect sense! Thank you so much
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,714
    Thanks
    1642
    Awards
    1

    Re: Question with power sets

    Quote Originally Posted by neojac93 View Post
    How can I prove or disprove that no set is equal to its power set?
    (I'm relatively new to Discrete Mathematics so this may be a very simple question.
    In think that that you mean equinumerous and not equal. This is Cantor's theorem.

    Suppose S is a set and there is a bijection f:S\leftrightarrow\mathcal{P}(S)
    Because the function is onto if G\in\mathcal{P}(S) then if \exists x\in S such that f(x)=G.

    What if A=\{x\in S:x\notin f(x)\}. Now because A\in \mathcal{P}(S) then \exists t\in S such that f(t)=A.

    Question does t\in f(t)=A~?~?~?
    Last edited by Plato; October 1st 2013 at 12:49 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Power Sets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 25th 2013, 01:02 PM
  2. [SOLVED] Cardinality of Sets and Power Sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 8th 2011, 05:26 PM
  3. Question about power sets and the empty set element
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 26th 2010, 12:26 PM
  4. Power Sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 9th 2009, 02:27 AM
  5. Power sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 22nd 2007, 07:21 PM

Search Tags


/mathhelpforum @mathhelpforum