23
$\begingroup$

I am really sure that if two sets have the same power set, then they are the same set. I just am wondering how does one exactly go about proving/showing this?

I'm usually wrong, so if anyone can show me an example where this fails, I'd like that too.

The homework just asks for true/false, but I'm wanting to show it if possible. My thoughts are that since the power set is by definition the set of all subsets of a set, if each of the two power sets are identical, we have an identity map between each set, thus it's indistinguishable which power set is a given set's power set. I hope that wasn't verbose. Since a set has only one power set, we can conclude they are in fact the same set.

  • 1
    "the same" isn't the same, depending on the context!2011-09-19

3 Answers 3

20

Suppose $A \neq B$. Without loss of generality, there exists an $x \in A$ such that $x \notin B$. Then $\{x\} \in \mathscr{P}(A)$ whereas $\{x\} \notin \mathscr{P}(B)$. Thus $\mathscr{P}(A) \neq \mathscr{P}(B)$.

Conversely, if $\mathscr{P}(A) = \mathscr{P}(B)$, then all their singletons are the same. Thus $A = B$.

$A = B$ if and only if $\mathscr{P}(A) = \mathscr{P}(B)$.

  • 0
    "Conversely"...but you have shown the same direction twice.2016-09-20
20

To add on William's answer with a positive proof, first one has to note the following observation:

$A=\bigcup\{B\mid B\subseteq A\}$

To prove this, the inclusion $A\subseteq\bigcup\{B\mid B\subseteq A\}$ is trivial since $A\subseteq A$, so we take $A$ into the union. In the other direction, since every $B$ in the union is a subset of $A$ the union is a subset of $A$.

Now we can proceed. The above identity can be written in terms of the power set as $A=\bigcup\mathcal P(A)$.

Assume $\mathcal P(A)=\mathcal P(B)$, therefore $\bigcup\mathcal P(A)=\bigcup\mathcal P(B)$, therefore $A=B$.

  • 0
    Hmm. Never seen the notation, guess I'll keep it in mind.2011-09-19
8

An alternative way to answer this old question: for all sets A and B,

$ \begin{array}{ll} & \mathcal{P}(A) = \mathcal{P}(B) \\ \equiv & \;\;\;\text{"extensionality"} \\ & \langle \forall V :: V \in \mathcal{P}(A) \equiv V \in \mathcal{P}(B) \rangle \\ \equiv & \;\;\;\text{"definition of $\mathcal{P}$, twice"} \\ & \langle \forall V :: V \subseteq A \equiv V \subseteq B \rangle \\ \Rightarrow & \;\;\;\text{"choose $V:=A$, and choose $V:=B$"} \\ & (A \subseteq A \equiv A \subseteq B) \;\land\; (B \subseteq A \equiv B \subseteq B) \\ \equiv & \;\;\;\text{"$\subseteq$ is reflexive, so $A \subseteq A$ and $B \subseteq B$"} \\ & A \subseteq B \land B \subseteq A \\ \equiv & \;\;\;\text{"definition of set equality"} \\ & A = B \\ \end{array} $

Update: As a comment rightly points out, the above proof is very similar to my answer to another question. In fact, we can directly prove the stronger version of this question's theorem from that one:

$ \begin{array}{ll} & \mathcal{P}(A) = \mathcal{P}(B) \;\equiv\; A = B \\ \equiv & \;\;\;\text{"double inclusion, twice"} \\ & \mathcal{P}(A) \subseteq \mathcal{P}(B) \land \mathcal{P}(B) \subseteq \mathcal{P}(A) \;\equiv\; A \subseteq B \land B \subseteq A \\ \Leftarrow & \;\;\;\text{"logic"} \\ & (\mathcal{P}(A) \subseteq \mathcal{P}(B) \;\equiv\; A \subseteq B) \;\land\; (\mathcal{P}(B) \subseteq \mathcal{P}(A) \;\equiv\; B \subseteq A) \\ \equiv & \;\;\;\text{"the other theorem, twice"} \\ & \text{true} \\ \end{array} $

  • 0
    Thanks! With "this theorem" I referred to the theorem of the question, not the one from the first proof. Edited in [revision](http://math.stackexchange.com/posts/332220/revisions) [5](http://math.stackexchange.com/revisions/332220/5) to clarify. And I've reverted the spacing changes: the ones around $\;\land\;$ because I dislike so much whitespace, and the one around the first line of the second proof because they don't fit the Dijkstra-Scholten-Gries-Schneider calculational proof format (see [EWD1300](http://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1300.html)).2014-01-07