Comments on the powerset axiom

Prerequisites to these comments:

The need of the powerset axiom

( A set is said countable, if it has a bijection with ℕ.)

Most of mathematics (with some exceptions such as geometry, which will be discussed later) uses one or both of

With some more work, the "ordinarily interesting" uses of quantifiers on P(ℝ) (thus indirectly of ∀ XP(ℕ)) and other uses of P(P(ℕ)) may usually be encoded as elaborate uses of P(ℕ).
In fact, most of ordinary mathematics can be indirectly developed using only ℕ and P(ℕ), that is, in the theory of second-order arithmetic. Further uses of the powerset (the P(P(P(ℕ))) and more) usually appear useless in ordinary mathematics. Their main uses may be the following :

Still, while quite less necessary, the powersets of uncountably infinite sets may be also considered for convenience. It is just formally simpler in set theory to assume the powerset tool to apply to all sets, as it is involved in some important concepts (descriptions of sets and systems).
Ultimately, the precise initial axiomatic system of set theory that will suffice to comfortably develop all mathematics (a simple but powerful enough one), will consist of the components (symbols and axioms) that we mentioned up to the powerset, plus the axiom of infinity, which equivalently states the existence of ℕ or of some infinite set (these conditions will be precisely formalized later, when needed).

Its fundamentally incomplete meaning (Skolem's paradox)

By identifying P(E) to the class of subsets of E, the powerset axiom aims to mean that this class is a set, thus fixed when the universe expands. Thus to imagine the universe big enough to contain "really", "absolutely" all subsets of E, in its supposedly "true" set P(E). But formally, its determination of P(E) depends on the universe, thus merely constitutes a relation between P(E) and the universe. There is no way to formally interpret the phrase «For all subsets of X...» except to satisfy ourselves letting it somehow mean «For all subsets of X that we can find...» since there can «exist» subsets that cannot be found, and there is no way to formalize desired claims about them. As mathematical theories can only describe objects that "are here" and not those which are "not here", no formalism can exclude the possible (meta-)"existence" of subsets of ℕ (or of any infinite set) that would not even actually exist inside our universe but only outside it (thus outside our P(E)), in a bigger universe (that may have its own functor P with another value on the same E). So, the intended meaning of the powerset of an infinite set, transcends any possible specific formalization as a mathematical theory.

One aspect of this phenomenon was explored by incompleteness results, that exclude any extension of the completeness theorem to the case of second-order logic. Thus, second-order logic cannot have any complete rules of proof (except those given by a first-order interpretation).

Another aspect comes by comparing the Completeness theorem with Cantor's theorem:

Skolem's Paradox. There are models of set theory, whose interpretation of P(ℕ) is a countable set from an external viewpoint, but thus does not exhaust "the true P(ℕ)".

Indeed the construction in the proof of the completeness theorem provides to any consistent theory (in particular any consistent set theory with axiom of infinity) some possible countable models, i.e. where the objects (all sets) can be labelled by numbers in the meta-ℕ (as they are equivalence classes of terms). This numbering exhausts all the internal "P(ℕ)" (all the subsets of ℕ which belong to this internal universe), but Cantor's theorem ensures that this sequence cannot exhaust "the true P(ℕ)" as viewed in the external universe.

One might object that the countable model made by this construction only simulates a powerset, not of the true ℕ, but of a non-standard model of ℕ. Indeed, the models provided by the precise construction we described in the proof of the Completeness theorem, all contain non-standard natural numbers.

However, the argument of the Skolem's paradox still holds in 2 ways.

On the one hand, by the fact that it is still anyway a countable simulation of the powerset of a countable set : as (inside a fixed model of set theory) bijections between sets provide bijections between their powersets, the oddity of this being lost (thus getting a "powerset" that cannot be the "true" one) when comparing the interpretations of countability between different models, remains intact. We can also consider the correspondance by the embedding of the standard (external) ℕ into the internal (non-standard) one : being externally countable, the internal "P(ℕ)" is insufficient not only to exhaust the external powerset of the internal ℕ, but also (by restriction of the ∈ predicate) that of its (external) subset of standard numbers.

On the other hand, for example, in the framework of set theory with the axiom of choice, there is another construction of a countable model of (the first-order theory of) second-order arithmetic, with the "true" (standard) ℕ but a different (countable) P(ℕ), with an elementary embedding from this model (ℕ, P(ℕ)) to the "true" one.

On the axiom of choice

A big success of mathematical logic has been the proof (too difficult here) of the independence of the Axiom of Choice (AC) : each universe where it is true contains another where it is false, and vice versa.
In 1938, Gödel proved that in each universe, the sub-universe of "constructible" objects (the objects that can be considered definable in some elaborate sense so that it forms a universe) has in each nonempty set a "first constructed element" that can be used as a choice, so that this sub-universe satisfies AC.
In 1966, Paul Cohen showed that AC is unprovable in ZF.
The possible counterexamples to AC are families of sets where an infinity of them are without any choice tool. The sets with no choice tool (i.e. with no privileged element that can be specified in a systematic way), are mainly
(In a finite set of subsets of ℕ, you may choose "the smallest one" for a total order roughly defined as the order between real numbers between 0 and 1, seeing subsets of ℕ as binary expressions of these numbers; but an infinite set of them needs not contain any smallest one for this order).

Namely for example, even if AC is true, AC may fail on the partition of P(ℕ) defined by the equivalence relation of finiteness of difference (A,B ↦ (AB is finite)).

Such possible exceptions to AC are not uniformly expressible by parameters in second-order arithmetic; but exceptions to AC may still appear there in the form of a formula F(x,y) with variables x∈ℕ and yP(ℕ) such that ∀x∈ℕ, ∃yP(ℕ), F(x,y), where the formula F has at least 3 quantifiers.
In practice, mathematical questions subtle enough (involving sufficiently high infinities) to depend on AC but still "not too high", can often be resolved with a weaker axiom such as AC. AC only becomes important for higher studies of set theory beyond ordinary purposes. It is then usually accepted as true for the questions that depend on it, as it intuitively feels more true and usually leads to more uniform and effective consequences than any contrary of it (that needs to be specified).

Finally, as (contrary to the powerset) the axiom of choice is unnecessary for the core (vital) constructions at the foundation of mathematics, we shall generally do without it in this work.



[The below is a draft, to be completed later...]


The strength hierarchy of set theories

The relativity of meaning of the powerset, which brings as formally bounded formulas on given objects, some undecidabilities that would otherwise merely concern unbounded formulas (with open quantifiers, subject to indeterminations on the size of the universe) are the key to many paradoxes in the foundations of mathematics.



The Zermelo-Frankel axiomatic system of set theory not only accepts P (ℕ) as a set, but the whole infinite series P (P (.....P (N)..)) also. And it even goes further after this, to more infinite sequences of higher and higher powersets. Then, you may ask: up to what point does it go ?
The answer is that this question cannot be answered, because, from the way ZF is formalized, it turns out that the hierarchy of powersets that it requires of its universe, goes very far beyond any possible imagination or description.

The search for stronger and stronger but hopefully still justified axiomatic systems such as ZF, can help to reduce the margin of undecidabilities (and deduce the consistency of other axiomatic systems), by forcing to enrich some sets with subsets that could have been ignored by smaller universes.


Next section :

 Second-order theories

Back to homepage : Set Theory and Foundations of Mathematics