The existence of the power set of an infinite set

Question

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?

Answer 1

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.

Answer 2

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.