# [FOM] Definability and Natural Sets of Real Numbers

Dmytro Taranovsky dmytro at mit.edu
Sun Feb 19 16:20:12 EST 2012

```An interesting mathematical and philosophical question is:
What is the complexity of the Sigma^2_1 theory of natural sets of real
numbers?

The philosophical part is answering which sets of real numbers are
natural -- and also which axioms to accept in set theory.  Natural sets
of real numbers are those that avoid the paradoxes associated with the
axiom of choice.  Natural sets of real numbers are determined and are
Wadge comparable with each other.  If X and Y are natural sets of real
numbers, then (under reasonable axioms) all sets of reals in L(R, X, Y)
are natural.
Note: A Sigma^2_1 statement about natural sets of real numbers is a
statement of the form: There is a natural set of reals X such that
phi(X), where phi is a formula in second order arithmetic (using X as a
predicate).

I will present and explain (a non-exclusive list of) 5 different answers
to the question:
(1) Natural sets of reals are the universally Baire sets, and their
Sigma^2_1 theory is definable in third order arithmetic.
(2) Natural sets of reals are the universally Baire sets, and their
Sigma^2_1 theory can be used to define Theory(V_delta) but is definable
in Theory(V_{delta+1}) where delta is the least Woodin cardinal.
(3) Natural sets of reals are those in HOD(R), and their Sigma^2_1
theory is inter-interpretable with the Sigma_2 theory of V.
(4) The hierarchy of natural sets of reals extends far beyond what is
definable in set theory, and their Sigma^2_1 theory is much more
expressive than the truth predicate for set theory.
(5) The property of being a natural set of real numbers is not ordinal
definable, but their Sigma^2_1 theory is definable in third order
arithmetic.

(1) is the conventional answer.  A set is universally Baire iff all of
its continuous preimages into compact Hausdorff spaces have the property
of Baire.  All universally Baire sets are determined (assuming 2 Woodin
cardinals), and no natural set of reals is known not to be universally
Baire.  A result of Woodin claimed that (assuming a proper class of
Woodin cardinals) the Sigma^2_1 theory of universally Baire sets is
definable in third order arithmetic, and Woodin used that in his
argument against the Continuum Hypothesis.  However, in 2009, Woodin
discovered that his proof (which was unpublished) was mistaken, and now
it is not even known whether the theory is definable in V_delta, where
delta is the least Woodin cardinal. However, (assuming a second Woodin
cardinal) the theory is definable in V_{delta+1}.

To motivate (2)-(4), consider this definition: "T is the most natural
completion of the theory ZFC".  While on its face, this definition
refers only to countable sets (specifically, completions of ZFC), in
reality, T appears to be the truth predicate for set theory.  The
complexity of being "natural" is turned into the complexity of the
notion of T.  Similarly, as we ascend the Wadge hierarchy of natural
sets of real numbers, defining the next step becomes increasingly
difficult.  However, since unnatural sets of real numbers do not appear
to be definable (not even from a countable sequence of ordinals), there
is no ambiguity about which sets of real numbers are natural -- at least
no apparently hopeless ambiguity such as the one present in the notion
of the most natural completion.  One simply extends the language, and
more inclusive sets of natural sets of reals become definable -- and if
an attempted definition (even one relying on a particular countable
sequence of ordinals) of a set of natural sets of real numbers is
overinclusive, then (we expect that) the defined set will have a Wadge
incomparable pair.  It is plausible that the complexity of these
definitions leaks into the Sigma^2_1 theory of natural sets of real
numbers, but there are three questions:
* What is the complexity of the notion of a natural set of real numbers,
or is that complexity essentially unbounded?
* Does that complexity translate into complexity of real numbers that
are ordinal definable in L(R, A) for some natural set of real numbers A?
* How much of this complexity is captured into the Sigma^2_1 theory of
natural sets of real numbers?

Answer (2) corresponds to the theory of universally Baire sets being as
complex as not known to be impossible (assuming 2 Woodin cardinals).
Answer (3) implies (assuming 2 Woodin cardinals) that the hierarchy of
natural sets of reals continues beyond universally Baire sets.  We do
not know if large cardinal axioms that are substantially stronger than
Woodin cardinals imply existence of definable sets of reals that are not
universally Baire.  It appears that such large cardinal axioms would
have to violate Woodin's Omega Conjecture.

Answer (4) corresponds to our intuition that the property of being a
natural set of real numbers is essentially an indefinable one.  A
definition of a subset of the hierarchy of natural sets of real numbers
arguably allows us to transcend it, and a definition of the full
hierarchy seems as unlikely as a definition of the canonical
well-ordering of real numbers.  In fact, the hierarchy potentially
promises to give us a canonical well-ordering of definable real
numbers--roughly, real numbers are well-ordered based on the least
ordinal alpha that is needed to define the real number using alpha and

If answer (4) is true, then to define a more expressive language than
set theory, we can pick a sufficiently closed (that is having
sufficiently strong reflection properties) stopping point alpha, and
consider the theory of integers, reals, and natural sets of reals of
Wadge rank less than alpha.  If alpha is sufficiently closed, then the
theory should be independent of alpha, so for definitiveness, we can
pick the least alpha that gives the "correct" theory.  The reason I am
not proposing using all natural sets of reals for the theory is that
even if this totality is well-defined, then for all we know, it might be
used to define a well-ordering of the reals.
To go further, we can pick a sufficiently closed pair (or even n-tuple)
of stopping points (alpha, beta) and consider the theory of integers,
reals, alpha (as an ordinal constant or predicate), and natural sets of
reals of Wadge rank below beta.  It is conceivable that still greater
expressiveness is reached using the full set theory augmented with the
canonical well-ordering of V.

However, the answer that I am currently learning towards is (5), with
one possibility being that the complexity is Sigma-2-2 (or Pi-2-2)
complete.  Essential indefinability of being a natural set of real
numbers does not necessarily imply high complexity of Sigma-2-1 theory.
While sets of reals can become arbitrarily complex, Sigma-2-1 complexity
depends on identifying a set of real numbers, and the restriction to
natural sets of real numbers only identifies the set (from its Wadge
rank) up to continuous reducibility.  This is best understood by analogy
with definability from Turing degrees.  For example (under projective
determinacy), if r is a real of sufficiently high Turing degree, then
the reals ordinal definable in L[r] are simply those that are Delta-1-3
in a countable ordinal, even if the Turing degree of r is added as a
predicate.  This is possible because a Turing degree only identifies a
real number up to recursive reducibility.  Sigma-2-1 theory of natural
sets of real numbers may similarly reach a supremum.

Dmytro Taranovsky
http://web.mit.edu/dmytro/www/main.htm
```