[FOM] Definability and Natural Sets of Real Numbers

[Dmytro Taranovsky]

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 
the Wadge hierarchy below alpha+1.

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