3
$\begingroup$

What does the axiom of power set add to ZF or ZFC set theory?

https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory

More specifically, it seems that once the axiom of infinity and the axiom schema of specification are used, then all of the elements of the power set of integers, P(N), could exist. If that is true, then wouldn't the axioms of pairing and union ensure that P(N) itself also existed?

P(N) contains many elements that are not computable sets: https://en.wikipedia.org/wiki/Recursive_set

Perhaps the axiom schema of specification could not be relied upon to assert the existence of any element of P(N) that is not computable (because there is no specifying formula)?

So, what is the point of the axiom of power set? It must add something to the other axioms... What elements of P(N) would not exist without the axiom of power set?

Bonus question: Given the existence of P(N), could the axiom schema of specification be used to assert the existence of...:

$$\{ p \in P( \,\mathbb{N}) \, : p \text{ is a computable set} \}$$

...where the formula for determining whether a set is computable is itself non-computable (think halting problem) and may not exist even though it is easily defined? I'm wondering what the limitations are when it comes to formulas that can be used in conjunction with the axiom schema of specification, thinking maybe it allows formulas to be used that literally cannot exist...

|cite|improve this question
$\endgroup$
  • $\begingroup$ See also math.stackexchange.com/questions/1619210/… $\endgroup$ – Asaf Karagila♦ Oct 31 '17 at 0:15
  • $\begingroup$ And also math.stackexchange.com/questions/1446509/… $\endgroup$ – Asaf Karagila♦ Oct 31 '17 at 0:26
  • 1
    $\begingroup$ "If that is true, then wouldn't the axioms of pairing and union ensure that P(N) itself also existed?" Think harder about how you would actually go about proving it using those axioms. Keep in mind two facts: (1) the axiom of union allows you to form the union of a set of sets - not a class. (2) Proofs have to be of finite length. $\endgroup$ – Nate Eldredge Oct 31 '17 at 5:53
  • $\begingroup$ Your bonus question is unrelated to your main one, so please ask it in a separate post; otherwise it won't receive proper attention. But I think you're making it too complicated. What formulas can be used with specification? Any first-order formula over $\in$; i.e. any well-formed formula of finite length involving logical symbols, $\forall, \exists, \in$. That is all. $\endgroup$ – Nate Eldredge Oct 31 '17 at 5:59
10
$\begingroup$

Here is a fun exercise. If you assume all the axioms except power set, then you cannot prove the existence of any uncountable set.

You can do it the hard way, or the smart way, by finding out that there is a model of the theory "$\sf ZFC-Power +\textrm{ Every set is countable}$".

In particular, to answer your question, no, you cannot prove that $\mathcal P(\Bbb N)$ exists. Because even without the power set axiom, you can show that given a countable set of subsets of $\Bbb N$, there is a subset of $\Bbb N$ which is not there. Namely, Cantor's theorem does not require $\mathcal P(\Bbb N)$ to actually be a set, if you formulate it correctly.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you Asaf. I've found some of your other answers helpful on this site too. You really seem to know your stuff. $\endgroup$ – AplanisTophet Oct 31 '17 at 0:32
  • $\begingroup$ If I assume ZFC - Power only (omitting the every set is countable part), then I assume we still cannot prove the existence of P(N)? I'm not sure why the axiom schema of specification can only create a countable number of subsets of N, unless it can only create computable subsets. $\endgroup$ – AplanisTophet Oct 31 '17 at 0:34
  • $\begingroup$ If you can't prove something from a theory AND extra assumptions, why would you be able to prove it without the extra assumptions? $\endgroup$ – Asaf Karagila♦ Oct 31 '17 at 0:35
  • $\begingroup$ I'm not sure I follow... Given the natural numbers and the axiom schema of specification, we can assert the existence of the computable elements of P(N) at least (I believe). Applying Cantor's logic to an enumeration of those computable elements would allow for the creation of a non-computable element not in the list. Still, we're only going to get a countable number of subsets this way... So is it true that the axiom schema of specification can only be used to create computable elements of P(N) given N? $\endgroup$ – AplanisTophet Oct 31 '17 at 0:41
  • $\begingroup$ You have a theory, ZF-Power. I've told you that if you assume more, then you cannot prove something. If you could prove that something without assuming more, then how would that be possible? $\endgroup$ – Asaf Karagila♦ Oct 31 '17 at 0:44
0
$\begingroup$

The axiom of specification only produces smaller sets than the natural numbers, i.e. sets that are subsets of $\mathbb{N}$ and are therefore members of $\mathcal{P} (\mathbb{N}) $. On the other hand, the axiom of infinity only guarantees that some $\aleph_0$ or larger infinite set exists -- it does not help us construct one from a smaller set like the naturals. What the power set axiom guarantees is not that any particular subset of $\mathbb{N}$ exists, but that the set of all these subsets is a set. This is also the axiom which guarantees the existence of a set with cardinality of exactly $2^{\lvert \mathbb{N} \rvert} $.

|cite|improve this answer
$\endgroup$

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.