# Question with power sets

Printable View

• Oct 1st 2013, 12:09 PM
neojac93
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.(Doh))

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!
• Oct 1st 2013, 12:23 PM
SlipEternal
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.
• Oct 1st 2013, 12:28 PM
neojac93
Re: Question with power sets
Ah, that makes perfect sense! Thank you so much :)
• Oct 1st 2013, 12:42 PM
Plato
Re: Question with power sets
Quote:

Originally Posted by neojac93
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~?~?~?$