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 ∀ X⊂ P(ℕ))
and other uses of P(P(ℕ)) may usually be encoded as
elaborate uses of P(ℕ).
- The set ℕ of natural numbers. We characterized the theory of
natural numbers as a second-order theory, i.e. using the
- The set ℝ of real numbers. It may be naturally characterized
using its own powerset P(ℝ); but it may also be built
from P(ℕ) (i.e. there is a way to let P(ℕ) play
the role of ℝ).
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 :
- A meta-theory interpreting a theory in some universe U
of objects, roughly involves P(Uℕ).
- Without ℕ, either P(P(E)) or (with more
work) EE can be used to express the
finiteness of a set E, and to rebuild ℕ from E
if E is infinite.
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
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
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
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).
- Sets of several pure elements
- Infinite sets of (undefinable) subsets of ℕ.
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 ↦ (A∆B is
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 y∈P(ℕ)
such that ∀x∈ℕ,
∃y∈P(ℕ), F(x,y), where the formula F
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
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 :
Back to homepage : Set Theory and
Foundations of Mathematics