- The meaning of
the distinction between sets and classes

- From the second text on set theory:
- The powerset axiom (in 2.5)
- The expression of the axiom of choice (in 2.9)
- Notion of Second-order theories
- Arithmetic with its non-standard models
- The
Incompleteness Theorem

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

- The set ℕ of natural numbers. We characterized the theory of
natural numbers as a second-order theory, i.e. using the
powerset
*P*(ℕ). - 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

- 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)*E*can be used to express the finiteness of a set^{E}*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).

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.

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

- Sets of several pure elements
- Infinite sets of (undefinable) subsets of ℕ.

Namely for example, even if AC

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*
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 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

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