The question itself:

For a given set A, prove P(P(A)) exists. You may only use the axiom of pairing, axiom of union and axiom of empty set.

This is how I solved it:

Let A be the given set. If A is the empty set, then using the axiom of empty set, $\varnothing$ exists. Using the axiom of pairing, {$\varnothing$} exists too. Using the axiom of pairing again, {{$\varnothing$},$\varnothing$} exists. that is precisely P(P(A)).

For the rest of the proof I will use induction, proving it for A with one item in it, and then going on. This is obviously the weak point of my proof - I do not know if I really may do it, and it gets really ugly here. Trying to get it 'nicer' I split it so I first prove it about P(A) only, later on the proof for P(P(A)) is really much the same.

Let A be the given set, and let A have one item in it, a. Again, using the axiom of empty set, $\varnothing$ exists. Using the axiom of pairing, {a} exists. Using the axiom of pairing again, {{a},$\varnothing$} exists. That is of course, P(A). Assuming that for given set An with n items in it, P(An) exists, we will show that for given set An+1 with n+1 items in it, P(An+1) exists:

Let y be the 'new' item. According to the axiom of pairing, {y} exists. According to the axiom union, we can 'add' it to each given set in P(A), and the new set will exist. Each new set we pair up (axiom of pairing) with the set it was 'created' from. We get a certain number of paired up sets. Each two of these seperate sets we use the axiom of union to add up. We go on with this process - pairing, union, pairing, union - until we get one set. This set should be P(B).

Now I am really unsure about it of course, and it's rather 'ugly' line of thought.

So, if anyone can point me to a faulty in my proof, or suggest a better/worse way to do it, or any thoughts at all really about this will be welcome.


Edit: another idea that came to me is using the axiom of pairing on A, so I get {A}, and then I set P(A)={{A},$\varnothing$}, however it does not really hold for A={{1,2},{3,4}} for example, or does it?

Edit 2: Recieved a clarification. The question is wrong, there was a typo when they wrote it. The question should be for given set A, prove that P(P({A})) exists. That's rather easy.

  • 1
    $\begingroup$ Is there some assumption on $A$? The claim you try to prove is certainly not provable in the general case. $\endgroup$ – Asaf Karagila Feb 6 '14 at 5:44
  • $\begingroup$ There's no assumption on A what so ever. Just given a set A, and have to prove P(P(A)) exists with these three axioms. $\endgroup$ – Studentmath Feb 6 '14 at 6:27
  • 1
    $\begingroup$ Then (1) induction is not going to help you prove the infinite case; and (2) it's not even true. $\endgroup$ – Asaf Karagila Feb 6 '14 at 6:32
  • $\begingroup$ I see, cheers - I will ask the teaching coordinator for explanation. It felt a bit too messy with induction. Perhaps they are speaking of finite sets, yet they certainly don't mention it. $\endgroup$ – Studentmath Feb 6 '14 at 6:34

This is generally not true.

Recall that given a set $X$, its transitive closure is the smallest set $A$ such that $X\subseteq A$ and $A$ is transitive (i.e. $a\in A\implies a\subseteq A$). We say that a set is hereditarily countable, if its transitive closure is countable.

The collection of all sets which are hereditarily countable, denoted by $H(\aleph_1)$ satisfies the axioms of pairing, union and the empty set, however if $A\in H(\aleph_1)$ is infinite, then $H(\aleph_1)\models\lnot\exists B(B=\mathcal P(A))$.

The proof that it satisfies the axioms is easy, note that the axiom of union holds because every collection in $H(\aleph_1)$ is countable, and its elements are countable. So the union is countable; and it is not hard to show that it is in fact hereditarily countable.

The proof that it fails to have power sets for infinite sets is also easy. If $A$ is infinite then $\mathcal P(A)$ is uncountable, so it cannot be hereditarily countable.

  • $\begingroup$ Thank you very much for clarifying that. If I get a clarification I will edit the question of course. $\endgroup$ – Studentmath Feb 6 '14 at 7:05

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.