# The existence of the power set of an infinite set

A large part of the set theory is devoted to infinities of various kinds, and this has been built on Cantor's groundbreaking work on uncountable sets. However, even Cantor's proof is based on the assumption that certain sets exist, namely that the power set of a countably infinite set exists. Sure, after assuming that the set of natural numbers has a power set, Cantor's proof shows that this power set is uncountable. However, he does not address why such a power set should exist in the first place. Is the existence of the power set of an infinite set assumed as an axiom of set theory?

Intuitively, I found the existence of such a power set troubling. By definition, most of the elements of this set consist of purely random infinite sets. For example, the power set of natural numbers can be partitioned into:

1. Those elements that can be constructed by an algorithm (i.e. a Turing Machine), such as all the finite sets, or the infinite sets with a constructive algorithm (e.g., set of odd numbers, set of natural numbers that build the digits of $$\pi$$ in some form such as {3, 14, 159, ...}, etc.)
2. All the other elements that no Turing Machine can generate them, e.g., an infinite set of entirely random natural numbers.

These purely random sets have (1) an infinite amount of information packed into them, and (2) we cannot even construct them. Both these aspects are unsettling to me.

Setting the intuition aside, is there a concrete reason why mathematicians accept the existence of the power set of an infinite set? Can we prove that such a set must exist? Has there been any inquiry on whether the existence of such a set would result in inconsistencies or not?

• Well, yes, one of the axioms of ZF(C) is the existence of the power set of any set. – Berci Aug 15 '20 at 23:07
• The real numbers have the same size as the power set of the natural numbers, so if you accept that the points on a line are in 1-1 correspondence with the reals, you accept the existence of at least one power set of an infinite set. – Rivers McForge Aug 15 '20 at 23:07
• People struggled really hard with this kind of stuff in the early 20th Century. People wore themselves out, and now they put this on the proverbial back burner. – Stephen Montgomery-Smith Aug 15 '20 at 23:50
• @RiversMcForge: Are you claiming that ZFC-power set+existence of the reals implies that the power set of the natural numbers exists? I don't think that's obvious. – tomasz Aug 15 '20 at 23:50
• Prove using what? This sort of fundamental question can be very sensitive to the foundations you use, including the axioms and the logic. – tomasz Aug 15 '20 at 23:59

## 2 Answers

This should perhaps be a comment, but it's too long. The question emphasizes a dichotomy among the subsets of $$\mathbb N$$: computable sets versus all the others. But there's actually a much richer spectrum here: computable sets, computably enumerable sets (like the set of code numbers of Turing machines that eventually halt when started on an empty tape), arithmetically definable sets, predicative sets, constructible sets (in the sense of Gödel), etc.

Early in the 20th century, there was considerable discussion (or dispute) as to whether mathematics should work with completely arbitrary sets or should require some degree of definability. This question played a central role in discussions about the axiom of choice. Eventually, when mathematical logic had been developed to the point where one could talk precisely about the many levels of definability, it became clear that the natural way to proceed is to let "set" mean "completely arbitrary set"; if one wants to work instead with definable sets, then one should say so and one should specify exactly what sorts of definitions are to be allowed. This decision in favor of arbitrary sets is the basis for most set theorists' acceptance of the axiom of choice.

It is entirely possible for someone (like me) who accepts arbitrary sets (and the ZFC axioms that are intended to describe them) to also consider more restricted universes in which only the computable sets are guaranteed to exist. One important axiom system often used to describe such a universe is called $$\text{RCA}_0$$ (abbreviating "recursive comprehension axiom"). Another axiom system, $$\text{ACA}_0$$, describes a universe with arithmetical sets; KP+Inf provides for the existence of hyperarithmetical sets; etc.

From the point of view of mathematics in general, it is interesting to ask whether various well-known theorems (like the Bolzano-Weierstrass theorem or the existence of prime ideals in non-degenerate rings, or the dominated convergence theorem) are provable with such limited supplies of sets. The detailed study of such questions is called "reverse mathematics", because to verify that one has just the right axiom system A for proving some theorem T, the usual method is to deduce A from T --- the reverse of the usual business of mathematics, deducing theorems from axioms. The standard reference for this topic is Stephen Simpson's book "Systems of Second-Order Arithmetic".

I should also mention that sets at the other end of the spectrum, random sets that have very high information content, have also been studied extensively by computability theorists. As with definability, randomness also has a spectrum; there are different levels of randomness. And the two spectra are (somewhat) related: A subset of $$\mathbb N$$ is random (to some degree) if it lies in all definable (to some degree) sets of probability 1 (in the standard probability space of subsets of $$\mathbb N$$).

The "undefinable" end of the spectrum also contains non-random sets of various sorts, for example the so-called generic sets, which lie in all definable sets that are comeager (i.e., their complement is of first Baire category). As with randomness, there are levels of genericity, related to levels of definability.

• Thank you for your thorough response. Regarding the existing (though non-mainstream) schools of thought such as finitists, or predicativists, is the reason for these mathematicians to not accept "completely arbitrary sets" as real, just a matter of taste? or are there more concrete reasons for them not to accept such sets? e.g. do they think accepting $P(\mathbb{N})$ can lead to inconsistencies? – nebeleh Aug 18 '20 at 7:28
• My impression is that there are different opinions among those who don't accept arbitrary sets (of natural numbers). Some don't think the notion of "arbitrary set" is clear enough to be used in mathematics. Or at least not clear enough to be used in foundations of mathematics. Others expect the notion to lead to inconsistency. Others expect inconsistency just from the notion of natural numbers, without even worrying about sets. – Andreas Blass Aug 18 '20 at 16:34
• Besides Stephen Simpson's book that you mentioned, can I ask what books/articles do you suggest for further reading on these topics? Most of the set theory books that I have read do not discuss these foundational matters in much depth and mostly focus on the set theory as it is practiced by most mathematicians. On the other hand, the philosophy of math books that I have seen do not go much into the technical details of these topics. Where do you think is a good starting point to get a deeper understanding of these viewpoints? Thank you. – nebeleh Aug 19 '20 at 0:01

Firstly, let's discuss the situation in classical logic (ordinary logic where $$P \lor \neg P$$ is a tautology). Suppose the existence of a set $$S$$, and suppose that the set $$\{f : S \to 2\}$$ exists, where $$2$$ is some fixed 2-element set $$\{\top, \bot\}$$. In other words, suppose that the collection of all functions $$S \to 2$$ forms a set. In this case, we can plainly see that the power set of $$S$$ exists by the Axiom of Replacement, since every subset $$J \subseteq S$$ defines a characteristic function $$f : S \to 2$$ by $$f(j) = \top$$ if $$j \in J$$, and $$f(x) = \bot$$ if $$x \notin J$$, and every function $$f : S \to 2$$ defines a subset $$\{x : f(x) = \top\}$$. Thus, if we want the collection of functions between two fixed sets to form a set, we must accept the existence of power sets. On the other hand, accepting the existence of power sets (along with the existence of cartesian products, which follows from ZF's replacement axiom schema) allows one to define the set of functions between two sets. Basically, if we want to consider sets of functions with a given domain and codomain, we also must accept the existence of powersets.

In general, this concept generalises to intuitionist logic (logic which doesn't necessarily accept $$P \lor \neg P$$ as a tautology) as follows: let $$1$$ be the one-element set, and suppose the set $$\Omega = \{S : S \subseteq 1\}$$ exists. Then the powerset of an arbitrary set $$S$$ exists iff the collection $$\{f : S \to \Omega\}$$ is a set. For if we have the set $$\{f : S \to \Omega\}$$, then just as before we can define for every $$f : S \to \Omega$$ a subset $$\{x \in S : f(x) = 1\}$$; and conversely, for every $$J \subseteq S$$, we can define a function $$f(x) = \{y \in 1 : x \in J\}$$, $$f : S \to \Omega$$, so we can again apply Replacement.

If we want the power set of $$1$$ to exist and we want function sets to exist, we must accept the existence of power sets as a necessary consequence. In classical logic, we can prove that the powerset of $$1$$ exists since it is equal to $$\{\emptyset, 1\}$$ which exists by the axiom of pairing.

There are weaker theories of set theory in which the law of excluded middle ($$P \lor \neg P$$) is not considered a tautology and in which function sets $$\{f : A \to B\}$$ exist but it cannot be proven that powersets exist (even $$\Omega = P(1)$$ may not exist). An example is CZF. Other examples of such theories (moving beyond the realm of "set theory") include Homotopy Type Theory and, in general, the theory of $$\Pi W$$ pretoposes.

If we eliminate the power set axiom from $$ZFC$$, then power sets can't be proven to exist. This is why the power set axiom is, in fact, an axiom. But then we'd also be forced to give up the existence of sets of functions, which would make set theory a completely miserable place for most mathematics.

Indeed, it seems difficult to even discuss point-set topology at all without the axiom of the power set. We'd essentially have to write that branch of mathematics off.

Of course, the axiom of the powerset does introduce one complication; it's possible that $$ZF$$ including powerset is inconsistent but $$ZF$$ without powerset is consistent. In fact, because we can prove that $$ZFC -$$powerset is consistent within $$ZFC$$, we cannot possibly prove that $$ZFC$$ is consistent from $$ZFC -$$ powerset unless both theories are inconsistent. But at the end of the day, constant fear of foundational inconsistencies is no way to live mathematical life.

• I am curious: how do you show that ZFC$^-$ has a model from ZFC? – tomasz Aug 16 '20 at 0:02
• @tomasz Just take $\kappa$ an uncountable regular cardinal; then let $H_\kappa$ be the set of all sets with hereditary size $< \kappa$. Then $(H_\kappa, \in_{H_\kappa})$ is a model of $ZFC$ without powerset. In particular, it can be shown in ZFC that every successor cardinal is regular. Thus, we can take the set of all sets with hereditary size at most countably infinite. This will form a model of $ZFC$ without powerset. In particular, in this model, we would have only one infinite cardinal. – Doctor Who Aug 16 '20 at 2:20
• @tomasz: You can find the details in Ken Kunen’s Set Theory: An Introduction to Independence Proofs, Ch. IV, Theorem $6.5$. – Brian M. Scott Aug 16 '20 at 3:26
• Thank you. Let me rephrase what I've understood from your answer. You accept the Cartesian product of two sets exists. Now, if we're mapping set $S$ to set $\{\top, \bot\}$, every function defines one of the subsets of $S$, hence $P(S)$ should exist. That is fine, however, my question is why should the Cartesian product of two sets exist in the first place? For example, if $S$ is infinite, some of these functions can be constructed (e.g. map odd members to $\top$ and evens to $\bot$), however, most cannot be constructed or written in any form. Why do we accept their existence? – nebeleh Aug 16 '20 at 3:49