Re: Question with power sets

Let's start with a small discrete example: $\displaystyle S = \{1,2\}$. Then, the power set of $\displaystyle S$ would be the set $\displaystyle \{\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 $\displaystyle S \subseteq S$, we know that $\displaystyle S \in P(S)$ (the power set of S) since $\displaystyle P(S)$ contains all subsets of $\displaystyle S$. But, $\displaystyle S \notin S$ since no set can contain itself (that is one of the axioms of set theory). So, $\displaystyle P(S)$ contains at least one element that $\displaystyle S$ does not contain. Hence, the two sets cannot be equal.

Re: Question with power sets

Ah, that makes perfect sense! Thank you so much :)

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 $\displaystyle S$ is a set and there is a bijection $\displaystyle f:S\leftrightarrow\mathcal{P}(S)$

Because the function is onto if $\displaystyle G\in\mathcal{P}(S)$ then if $\displaystyle \exists x\in S$ such that $\displaystyle f(x)=G$.

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

Question does $\displaystyle t\in f(t)=A~?~?~?$