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
    $\begingroup$ What do you mean by "same"? $\endgroup$ – Qiaochu Yuan Sep 19 '11 at 2:37
  • 9
    $\begingroup$ I think he means "same" in the sense of the axiom of extensionality. $(\forall x)(x \in A \Leftrightarrow x \in B) \Rightarrow (A = B)$ $\endgroup$ – William Sep 19 '11 at 2:41
  • 1
    $\begingroup$ "the same" isn't the same, depending on the context! $\endgroup$ – The Chaz 2.0 Sep 19 '11 at 2:59

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)$.

  • $\begingroup$ +1 Is the statement that $\{ x \} \notin \mathscr P(B)$ evident or does it need proof? (It seems "clearly" true, but I do not know what to say if someone asks me to justify it.) $\endgroup$ – Srivatsan Sep 19 '11 at 2:44
  • 2
    $\begingroup$ I would just use the definition of subset. $D \subset E$ if and only if $(\forall n)(n \in D \Rightarrow n \in E)$. So by assumption $x \notin B$ and $x \in A$. So we have there exists $n$ (in particular that $x$) such that $n \in \{x\}$ and $n \notin B$. Thus I have proved $(\exists n)(n \in \{x\} \wedge n \notin B) = \neg((\forall n)(n \in \{x\} \Rightarrow n \in B))$. Thus $\neg(\{x\} \subset B)$ and hence $\{x\} \notin \mathscr{P}(B)$. $\endgroup$ – William Sep 19 '11 at 2:49
  • $\begingroup$ Thanks, I appreciate your answer and the follow up. $\endgroup$ – mathmath8128 Sep 19 '11 at 3:00
  • 1
    $\begingroup$ "Conversely"...but you have shown the same direction twice. $\endgroup$ – 6005 Sep 20 '16 at 21:56

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$.

  • 1
    $\begingroup$ @anon: $\bigcup_{B\subseteq A} B$ can be written as $\bigcup\{B\mid B\subseteq A\}$. $\endgroup$ – Asaf Karagila Sep 19 '11 at 5:35
  • $\begingroup$ Hmm. Never seen the notation, guess I'll keep it in mind. $\endgroup$ – anon Sep 19 '11 at 5:45

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} $$

  • $\begingroup$ Instead of posting the same answer twice, you can post it once and point out that the question is the same. $\endgroup$ – Asaf Karagila Mar 16 '13 at 20:36
  • $\begingroup$ @AsafKaragila I'm sorry, I did not intend to post the same answer twice. Which two answers are you referring to? $\endgroup$ – MarnixKlooster ReinstateMonica Mar 16 '13 at 20:43
  • $\begingroup$ While not word for word, it is the same question and the same answer: math.stackexchange.com/a/332186/622 $\endgroup$ – Asaf Karagila Mar 16 '13 at 20:45
  • 1
    $\begingroup$ The questions are actually slightly different: this one is about $\mathcal{P}(A) = \mathcal{P}(B) \Rightarrow A = B$, while the other is about $\mathcal{P}(A) \subseteq \mathcal{P}(B) \equiv A \subseteq B$. But you are of course correct that these two theorems are very much related: (a stronger version of) the former follows directly from the latter using extensionality. $\endgroup$ – MarnixKlooster ReinstateMonica Mar 16 '13 at 20:54
  • $\begingroup$ @MarnixKlooster: +1. I'm very grateful that you uncloak all the detail and steps. I made two ancillary edits for layout but please feel free to revert them. Just a question: How is the update "a stronger version of this theorem"? In this answer, you're only proving in two ways the same result: $A = B \iff P(A) = P(B)$? $\endgroup$ – Greek - Area 51 Proposal Jan 7 '14 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.