Universes of definable sets and the axiom of choice

[Dmytro Taranovsky]

The main argument against the axiom of choice (AC) is and has been that 
it is nonconstructive, and that it leads to existence of 'pathological' 
sets that are apparently not definable.  Still, AC has been accepted 
because of its obviousness and its enormous utility in 'making' the set 
universe tractable and well-behaved. There is another argument for AC:  
A mathematician insisting that all sets be definable will end up with a 
model of AC (such as an elementary substructure of HOD) -- or that has 
been the traditional view.

HOD is only one of different notions of the universe of definable sets, 
and intriguingly, some other notions suggest ZF+AD.

I will start with a motivating example; next, make general observations 
on definability; then present a potential construction of natural 
definable universes with large cardinals beyond choice; and finally 
discuss ordinal definability and beyond.

For a motivating example, suppose that L(R) satisfies AD (the axiom of 
determinacy), and R^# exists.  Let r_0 = 0 and r_{j+1} = 
M_omega^#(r_j).  Then the definable sets in (L(R),in,r_1,r_2,...) form 
an elementary substructure of L(R).  Or if we let M = L(R)[G] with G 
generic over L(R) for Add(omega_1,1), then M satisfies ZFC, and the 
transitive extensional collapse of the set of (M,in,r_1,r_2,...) 
definable sets is elementarily embeddable in L(R).  (The transitive 
extensional collapse can be defined as collapse(a) = collapse_a(a) and 
collapse_a(b) = {collapse_a(c): c in (a intersect b)}.)

Up to notational differences, r_{j+1} = theory(L(R),in,r_j,i_0,i_1,...) 
where ordinals i_0,i_1,... are the first omega canonical indiscernibles 
for L(R).  By contemplating L(R), we might see r_1,r_2,... as natural 
additions to the language (L(R),in).  Alternatively, for the above, we 
can let r be any sequence of reals of length omega with M_omega^#(r_j) 
computable from r_{j+1}.

Alternatively, even simpler (if we are content with finite fragments of 
ZF/ZFC), for every statement phi that holds in some L_alpha(R), I think 
we can set r_j=0, and in place of L(R), use L_alpha(R) for the least 
alpha>0 such that L_alpha(R) satisfies phi.  For such alpha (assuming AD 
in L_{alpha+2}(R)), the first order definable in L_{alpha+1}(R) elements 
of L_alpha(R) should form an elementary substructure of L_alpha(R).  
(alpha+1 is sometimes necessary; for example, see "Scales in K(R)" by 
John Steel.)

Going further, while our understanding of uncountable sets is limited, 
we can still make informed guesses about definability (or for a 
formalist, guesses about how we will want it to be) and try to uncover 
the right principles.  Some of my previous writings can be found at:
"Definability and Natural Sets of Real Numbers" 
https://cs.nyu.edu/pipermail/fom/2012-February/016198.html
"On the Nature of Reals" 
https://cs.nyu.edu/pipermail/fom/2016-October/020147.html
"Symmetry and Infinity" 
https://cs.nyu.edu/pipermail/fom/2018-December/021326.html

Existence of a reasonable structure for definable sets depends on a 
sufficiently closed notion of definability.  Closure/symmetry and not 
merely strength is crucial.  For example, it is because of closure and 
symmetry that we can quantify over the totality of definable reals, and 
still end up with definable reals.

Next, definability is extensible.  Suppose that we extend definability 
from L_0 to L_1 (for some L_0 and L_1).  If (per standard platonic 
view), there is a background universe, then the set of L_0 definable 
sets should be (assuming sufficient closure) an elementary substructure 
(for definability levels in L_0) of the set of L_1 definable sets (or 
for a slight weakening of sufficient closure, the elementarity is for a 
definability level slightly below L_0).  However, even without assuming 
metaphysical existence of uncountable sets, we can make sense of 
concepts like the set of all reals as follows.  With some caveats, a 
definability level leads to a universe of definable sets, say V_0 for 
L_0 and V_1 for L_1. Assuming sufficient coherence, L_0 makes sense both 
for V_0 and V_1, and by taking L_0 definitions of sets in V_0 and 
applying them in V_1, we get an L_0-elementary embedding of V_0 into 
V_1.  Thus, while the set of all reals may have additional elements in 
V_1, we have full agreement about its L_0-properties, and similarly for 
other sets.  A related discussion is in my above-mentioned posting 
"Symmetry and Infinity".

If V=HOD, then at sufficient expressiveness, the resulting structures 
satisfy AC and are elementarily embeddable into (V,in).

However, there are good reasons to reject V=HOD.  Intuitively, there is 
no definable way to well-order the reals.  Moreover at definability 
levels that are well-understood, a relation whose restriction to reals 
of definability level X (for typical X) is a well-order requires a 
definability level close to X (and models with simple well-orderings 
(such as L) have simple reals).  For example, under projective 
determinacy (PD), there is no Sigma-1-9 well-ordering of Delta-1-10 
reals.  Also, we can force V=HOD by for example coding V into the 
continuum function, but doing so would break the symmetry we intuitively 
expect of V.  Also, some large cardinal-like symmetry principles 
contradict V=HOD.

Without a definable well-ordering, the set of definable sets might fail 
to be an elementary substructure.  However, we can still take, for 
example, among sets first order definable in V_kappa, the transitive 
extensional collapse S_kappa.  This maps definable sets without 
definable elements into the empty set, and so on.  We do not know much 
about S_kappa, but one optimistic possibility is that for appropriate kappa:
- S_kappa satisfies a large fragment of ZF, including the full 
separation schema.
- All elements of S_kappa are definable in S_kappa.
- We have coherence between different kappa in terms of (say) 
S_{kappa_1} being elementarily embeddable into a rank-initial segment of 
S_{kappa_2}.
- AD holds in S_kappa.
- For some kappa, S_kappa has large cardinals beyond choice such as 
totally Reinhardt cardinals (as they are currently called; note that 
existence of a totally Reinhardt cardinal is a Sigma_2 statement).

Notes:
- It could be that transitive extensional collapse is the wrong way of 
extracting good definable structure.  Even bounded quantifier separation 
is not a given (i.e. there likely are models in which it fails in 
S_kappa).  It might also be that quantification over some levels of 
S_kappa has different expressiveness than for the corresponding levels 
of V_kappa.
- AC should fail in S_kappa if adding more unbounded quantifiers 
increases expressiveness beyond the addition of ordinal parameters.
- Without AC, the intuitive case for AD is very strong.
- Without AC, there are no apparent problems with Reinhardt-like cardinals.

However, if V_kappa satisfies ZFC, then so does S_kappa.  Also, for all 
large enough kappa, S_kappa satisfies "there is a well-ordering of the 
reals".  (On the other hand, it should be consistent that for the least 
kappa such that V_kappa has the same Sigma_10 theory as V, S_kappa 
satisfies "there is no well-ordering of the reals".)

The problem, I submit, is that ordinal definability, while very 
expressive, is not sufficiently closed; it allows defining certain 
constructs without also defining the canonical indiscernibles for those 
constructs.

A key result of descriptive set theory is uniformization.  For 
well-understood expressiveness levels, every relation on the reals can 
be uniformized by a function that is definable at the same or 'slightly' 
higher level.  For example, under PD, we have Pi^1_{2n-1}(r) and 
Sigma^1_{2n}(r) uniformization for all positive integers n and reals r.  
However, with ordinal definability (unless V=HOD), we get a nonempty 
Pi^V_2 set of reals (that is co-countable if |R^{HOD}|=omega) without an 
ordinal definable element.  For the analogous situation for L(R), we get 
definable elements with R^#.

And for HOD, we can extend the language of set theory with the canonical 
indiscernibles for V (which I call omega-reflective cardinals) and 
(likely) define HOD sharp to get definable sets beyond OD.  For details, 
see my paper: "Reflective Cardinals" https://arxiv.org/abs/1203.2270 .

To get sufficient closure relative to itself, the extension would have 
to be done omega times -- thus extending (V,in) with omega new predicate 
symbols -- and if our assumptions are right, the transitive extensional 
collapse of definable sets may be a canonical model for ZF+AD that 
coheres with appropriate S_kappa described above.  I expect that the 
appropriate axioms (leading to a true reasonably complete theory) will 
be amenable to fine-structural analysis, but that is for another day.  
Fine structural models for, say, totally Reinhardt cardinals, would be 
very different from what we have now (and very interesting), but at the 
high level, it would still be a well-understood canonical model that 
appears built level-by-level.

I will close with some (non-exhaustive) possibilities:
- (pessimistic view) set theory is incoherent even at the level of third 
order arithmetic, with basic independent propositions having no 
preferred resolutions.
- (not likely) V=HOD.
- (radical view) the analysis of definable sets (in the above style) 
works out, with the sets satisfying ZF+AD, and this universe (or 
coherent collection of universes) becomes the main subject of infinitary 
mathematics.
- the universe of all sets V (satisfying ZFC) and the canonical 
universes for ZF+AD are both considered important.

Even with V satisfying ZFC but not V=HOD, an approach to V through a 
coherent sequence of universes V_0, V_1, ... is possible but with some 
complications: The canonical definitions for sets in V_0 go slightly 
beyond first order definability in V_0 (unless we choose to limit 
correctness/elementarity; in a way, V_0 is defined as a whole), and 
applying these definitions to V_1 gives non-unique sets (example: a 
well-ordering of V_0 reals can be extended in multiple ways to V_1 
reals), but crucially, we can still have elementary embeddings of V_0 
into V_1 and so on.

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