[FOM] 172:Ordered Fields/Countable DST//PD/Large Cardinals
Harvey Friedman
friedman at math.ohio-state.edu
Fri May 23 01:55:01 EDT 2003
ORDERED FIELDS, COUNTABLE DESCRIPTIVE SET THEORY, PROJECTIVE
DETERMINACY, AND LARGE CARDINALS
FIRST DRAFT
by
Harvey M. Friedman
May 22, 2003
INTRODUCTION. The unexpected simplicity of Theorem 1 (or if you
prefer, Theorem 2), in posting 170, has consequences. See
http://www.cs.nyu.edu/pipermail/fom/2003-May/006651.html and section
1 below.
It now makes very good mathematical sense to shift the context to
definable sets in (expansions of) ordered fields, instead of Borel
sets in the reals. As an intermediate step, we will first shift the
context to definable sets in the field of all reals with Z as a new
predicate. The latter is well known to be identical with the
projective sets in R, in the sense of descriptive set theory.
The result is a range of statements of a very familiar character,
particularly to model theorists, involving only (expansions of)
ordered fields, which exhibit strong metamathematical properties,
including the necessary use of PD = projective determinacy. This
unbreakable connection with higher set theory persists even if we
restrict attention to countable ordered fields.
In particular, we obtain sentences equivalent to the consistency of
ZFC + PD (scheme). In terms of large cardinals, they are equivalent
to the consistency of ZFC + {there exists n Woodin cardinals}_n.
***Of course, these statements are NOT intended for the general
mathematical community, with anticipated deep connections with
virtually the entire mathematical landscape. That purpose is being
served by BRT. But these statements here are very friendly to
mathematical logicians, and in particular, model theorists.***
###These statements show just what happens when the known celebrated
tameness in the reals is combined in a seemingly innocent way with
the integers.###
Also, in a way that will be made clear below, the results can be
viewed as a new kind of descriptive set theory - a new countable
descriptive set theory - that I think can profitably be pursued for
its own sake, independently of large cardinals.
In particular, we discuss the following two statements.
*) Every definable set in the plane contains or is disjoint from a
definable perfect set whose fld (i.e., set of coordinates) is
definably connected.
**) Every arithmetically definable set in the plane contains or is
disjoint from a definable perfect set whose fld is definably
connected.
In the context of ordered fields, *) is readily understood. It holds
if and only if the ordered field is real closed.
*) and **) become delicate in the context of ordered fields with a
distinguished discrete (additive) subgroup. In **), "arithmetically
defined" means defined in the given ordered field with the given
discrete subgroup, where all quantifiers are relativized to the
discrete subgroup, and where parameters are allowed as usual from the
ordered field.
In fact, the mere existence of any ordered field/discrete subgroup in
which **) holds, can be proved in Z (Zermelo set theory) but not in
BZ (bounded Zermelo set theory), and not in the theory of types with
infinity. Thus we have a necessary use of infinitely many uncountable
cardinals.
The connection of *) with set theory is far stronger. The mere
existence of any ordered field/discrete subgroup in which *) holds,
can be proved in ZF + PD but not in ZFC + PD (scheme). Here PD
(scheme) is
{projective determinacy for Sigma-1-n)_n.
In light of work of Martin, Steel, Woodin, we can restate these
results, both for the subfield of reals case and the general case, in
terms of large cardinals. We have provability in ZFC + "there are
infinitely many Woodin cardinals" but not in ZFC + {there exists n
Woodin cardinals}_n. Thus we have a necessary use of large cardinals,
which are considered "medium sized" since they are incompatible with
V = L.
In fact, we can go further. The statements in question are almost in
the form of the existence of a model of a scheme in predicate
calculus. The problem is the existential quantifier over definable
perfect sets. However, this definability can be easily seen to be
localizable, and so the resulting equivalent modified form is of the
form: a certain scheme in predicate calculus is consistent.
Therefore, the statement is equivalent to a Pi-0-1, and exhibits the
strongest form of absoluteness.
In fact, we obtain equivalence over WKL0 with the consistency of ZFC
+ PD (scheme), or equivalently, with the consistency of ZFC + {there
exists n Woodin cardinals}_n.
More can be gleaned from the work:
The ordered fields with discrete subgroup satisfying **) are
"exactly" the "real" parts of models of the Russell theory of types
with infinity.
The ordered fields with discrete subgroup satisfying *) are "exactly"
the "real" parts of models of ZFC + PD (scheme), or the real parts of
models of ZFC + {there exists n Woodin cardinals}_n.
In the Archimedean case, where we require that the ordered field be
Archimedean, we replace "models" in the above by "omega models".
1. BOREL SETS AND PROJECTIVE SETS.
We begin with a simple modification of the Borel statement which
requires iterations of the power set operation of every countable
transfinite length to prove. See
http://www.cs.nyu.edu/pipermail/fom/2003-May/006651.html.
We call a set of reals perfect if and only if it is nonempty and its
limit points are exactly its elements.
The following result is very classical.
THEOREM 1.1. Every Borel set in the plane contains or is disjoint
from a perfect set.
Theorem 1.1 is provable in ATR0, as is the very classical "every
uncountable Borel set in the plane contains a perfect set".
Now look at this strengthening:
THEOREM 1.2. Every Borel set in the plane contains or is disjoint
from a perfect set whose fld is connected.
Here fld refers to the set of all coordinates. Obviously, this is equivalent to
THEOREM 1.3. Every Borel set in the plane contains or is disjoint
from a perfect set whose fld is an interval.
However, the reason for the formulation in Theorem 1.2 will be clear later.
This, in turn, is sharpened by the natural
THEOREM 1.4. Every Borel set in the plane contains or is disjoint
from a perfect set whose fld is the line.
And we can sharpen further by the more awkward
THEOREM 1.5. Every Borel set in the plane contains a perfect set
whose first projection is the line or is disjoint from a perfect set
whose second projection is the line.
THEOREM 1.6. It is necessary and sufficient to use uncountably many
iterations of the power set operation to prove Theorem 1.2. Theorem
1.2 is provably equivalent to the existence of a countable well
founded model of the cumulative hierarchy of every countable ordinal
length, containing any given subset of omega, over ATR0. The same
holds for Theorems 1.3 - 1.5.
We now use the projective sets of descriptive set theory.
PROPOSITION 1.7. Every projective set in the plane contains or is
disjoint from a perfect set.
THEOREM 1.8. Proposition 1.7 is refutable in ZF + V = L, and so is
not provable in ZFC. It holds in Solovay's model, which uses an
inaccessible cardinal, and so is not refutable in ZFC. The
inaccessible can be avoided for the nonrefutability proof, since
Proposition 1.7 follows from "every projective set in the plane has
the Baire property", which is known to be independent of ZFC without
using an inaccessible cardinal (Shelah).
Now look at this strengthening:
PROPOSITION 1.9. Every projective set in the plane contains or is
disjoint from a perfect set whose fld is connected.
Once again, we can sharpen as before, culminating in the more awkward
PROPOSITION 1.10. Every projective set in the plane contains a
perfect set whose first projection is the line or is disjoint from a
perfect set whose second projection is the line.
THEOREM 1.11. Proposition 1.9 is provably equivalent to PD
(projective determinacy) over ZF. Proposition 1.9, stated as a
scheme, is provably equivalent to PD, stated as a scheme, over ZF. By
Martin, Steel, Woodin, ZF can be replaced here by Z_2.
We don't have a really good name for the regularity property of Borel
sets in Theorem 1.2, which is also used in Proposition 1.9.
So we will, at least temporarily, call this regularity property
***special regularity***.
So Theorem 1.2 asserts that
#every Borel set in the plane has special regularity.#
And Proposition 1.9 asserts that
#every projective set in the plane has special regularity.#
2. PRELIMINARIES.
Fix an ordered field F = (F,+,x,<), and an expansion M of F. Fix n >=
1 and S containedin F^n.
We say that M is definably lub if and only if every M definable
subset of F with an upper bound in F has a least upper bound in F.
We say that S is open in M if and only if for every x in S there
exists epsilon > 0 in F such that for all y in F^n, if |x-y| <
epsilon then y in S.
We say that x in F^n is a limit point of S if and only if for all
epsilon > 0 in F, there exists y in F^n, y not= x, such that |x-y| <
epsilon. We take | | to be the maximum of the absolute values (sup
norm).
We say that S is closed in M if and only if every limit point of S lies in S.
We say that S is perfect in M if and only if S is nonempty, closed,
and every element of S is a limit point of S.
We say that S is M definably disconnected in M if and only if there
are two nonempty V,W containedin F^n such that
V,W are nonempty;
V,W are open in F;
U,V are M definable;
S containedin V union W;
S intersect V intersect W = emptyset.
We say that S is M definably connected in M if and only if S is not M
definably disconnected in M.
We say that M is definably connected if and only if F is definably
connected in M.
We say that M is special regular if and only if the following holds:
Every M definable subset of F^2 contains or is disjoint from an M
definable perfect set whose fld is M definably connected.
We finally make some definitions that apply only to a modified
context. Here we have F,G, where F is an ordered field and G is a
discrete subgroup of F. I.e., G is a subgroup of (F,+) where G does
not meet the open interval (0,1) of F. We call such a pair, an
ordered field/discrete group. Fix an expansion M of (F,G). Fix n >= 1
and S containedin F^n.
We say that S is M arithmetically definable if and only if S can be
defined in M with all quantifiers relativized to G, and parameters
allowed from F as usual. Note that only F,G are used here.
We say that M is arithmetically lub if and only if every M
arithmetically definable subset of F with an upper bound in F has a
least upper bound in F.
We say that M is arithmetically disconnected if and only if there are
two nonempty V,W containedin F^n such that
V,W are nonempty;
V,W are open in F;
U,V are M arithmetically definable;
V union W = F;
V intersect W = emptyset.
We say that M is arithmetically connected if and only if M is not
arithmetically disconnected.
We say that M is arithmetically regular if and only if the following holds:
Every M arithmetically definable subset of F^2 contains or is
disjoint from an M definable perfect set whose fld is M definably
connected.
3. CONNECTEDNESS AND LUB IN ORDERED FIELDS.
THEOREM 3.1. Let F be an ordered field. F is definable lub if and
only if F is definably connected if and only if F is a real closed
field.
THEOREM 3.2. Let F be an ordered field and M be an expansion of F. M
is definable lub if and only if F is M is definably connected.
THEOREM 3.3. There is a (countable) ordered field/discrete subgroup
which is arithmetically connected.
THEOREM 3.4. There is a (countable) ordered field/discrete subgroup
which is arithmetically lub.
THEOREM 3.5. There is a (countable) ordered field/discrete subgroup
which is definable lub, or equivalently, is definably connected.
Note that Theorems 3.3 - 3.5 assert the consistency of a scheme in
predicate calculus with equality.
THEOREM 3.6. Theorem 3.3 is provably equivalent, over WKL0, to the
consistency of PA (Peano Arithemtic). In particular, it cannot be
proved in ACA0.
THEOREM 3.7. Theorem 3.4 is provably equivalent, over WKL0, to the
consistency of Pi-1-1-CA0. In particular, it cannot be proved in
Pi-1-1-CA0.
THEOREM 3.8. Theorem 3.5 is provably equivalent, over WKL0, to the
consistency of Z_2. In particular, it cannot be proved in Z_2.
4. SPECIAL REGULARITY IN ORDERED FIELDS.
THEOREM 4.1. Every real closed field has special regularity.
PROPOSITION 4.2. There is a (countable) ordered field/discrete
subgroup which has special regularity.
Note that special regularity is NOT simply given by a set of
sentences in predicate calculus with equality. This is because we
have an existential quantifier over "definable perfect set".
Let us modify special regularity as follows. We will be content for
present purposes to use a very crude complexity measure for formulas:
simply the number of occurrences of variables and constants (0,1).
Every definable set in the plane contains or is disjoint from a
perfect set defined with at most 1 million occurrences of variables
and constants whose fld is definably connected.
THEOREM 4.3. Suppose a given (countable) ordered field/discrete
subgroup is modified special regular. Then it is special regular.
Furthermore this is provable in WKL0.
COROLLARY 4.4. Proposition 4.2 is provably equivalent, in WKL0, to a
Pi-0-1 sentence.
THEOREM 4.5. Proposition 4.2 can be proved in ZFC + PD but not in ZFC
+ (Sigma-1-n determinacy)_n. It is equivalent, over WKL, to the
consistency of ZFC + {Sigma-1-n determinacy)_n. In terms of large
cardinals, Proposition 4.2 can be proved in ZFC + "there are
infinitely many Woodin cardinals" but not in ZFC + (there are n
Woodin cardinals}_n. It is provably equivalent, over WKL, to the
consistency of ZFC + {there are n Woodin cardinals}_n. .
THEOREM. 4.6. There is a (countable) ordered field/discrete subgroup
which is arithmetical regular.
THEOREM 4.7. Theorem 4.6 can be proved in Z but not in BZ or finite
type theory with infinity. It is equivalent, over WKL0, to the
consistency of BZ or finite type theory with infinity.
5. THE ARCHIMEDEAN CASE.
In the Archimedean case, we can view the ordered fields as subfields
of the reals, under the usual ordering of the reals. Of course, in
this case, the only discrete additive subgroup is the integers (of
the ordered field).
Theorems 3.3, 3.4, 3.5, 4.6, and Proposition 4.2, are modified by
replacing "a" by "an Archimedian".
Theorem 3.6 is dropped. The metamathematical Theorems 3.7, 3.8, 4.5,
4.6 are modified by
i) replacing WKL0 with ACA;
ii) replacing "consistency" with "existence of an omega model".
Corollary 4.4 is modified by replacing WKL0 with ACA and replacing
Pi-0-1 with Sigma-1-1.
Here are some additional developments.
The R,Z definable sets are exactly the projective sets in the sense
of descriptive set theory. The R arithmetical sets are exactly the
Borel sets of finite rank in the sense of descriptive theory.
It is important to understand the one sentence proof of the existence
of a countable subfield F of the reals such that F,Z is definably
lub. Take a countable elementary substructure of (R,+,x,<,Z).
THEOREM 5.1. There is a smallest countable subfield of R which is
arithmetically connected. It is precisely the arithmetic real numbers
in the sense of recursion theory.
THEOREM 5.2. The intersection of all countable subfields of R that
are arithmetically lub = the intersection of all subfields of R that
are arithmetically lub. This intersection forms a real closed
subfield of the reals that is not arithmetically lub. It is
arithmetically connected. It is precisely the hyperarithmetic real
numbers in the sense of recursion theory.
In very precise senses,
i) the subfields of R such that R,Z is arithmetically connected are
"identical" with the omega models of ACA;
ii) the subfields of R such that R,Z is arithmetically lub are
"identical" with the omega models of Pi-1-1-CA;
iii) the subfields of R such that R,Z is definably lub are
"identical" with the omega models of Z_2;
iv) the subfields of R such that R,Z is arithmetically regular are
"identical" with the omega models of ???
There is an old theorem of mine that there is no minimal omega model
of Z_2. This has since been sharpened and generalized. See Simpson's
book, Subsystems of Second Order Arithmetic.
Applied to the present context, we have the following.
THEOREM 5.3. There is no minimal (countable) subfield F of R among
those for which F,Z is arithmetically lub. There is no minimal
(countable) subfield of R among those for which F,Z is definably lub.
*********************************************
I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.
This is the 172nd in a series of self contained numbered postings to
FOM covering a wide range of topics in f.o.m. The list of previous
numbered postings #1-149 can be found at
http://www.cs.nyu.edu/pipermail/fom/2003-May/006563.html in the FOM
archives, 5/8/03 8:46AM. Previous ones counting from #150 are:
150:Finite obstruction/statistics 8:55AM 6/1/02
151:Finite forms by bounding 4:35AM 6/5/02
152:sin 10:35PM 6/8/02
153:Large cardinals as general algebra 1:21PM 6/17/02
154:Orderings on theories 5:28AM 6/25/02
155:A way out 8/13/02 6:56PM
156:Societies 8/13/02 6:56PM
157:Finite Societies 8/13/02 6:56PM
158:Sentential Reflection 3/31/03 12:17AM
159.Elemental Sentential Reflection 3/31/03 12:17AM
160.Similar Subclasses 3/31/03 12:17AM
161:Restrictions and Extensions 3/31/03 12:18AM
162:Two Quantifier Blocks 3/31/03 12:28PM
163:Ouch! 4/20/03 3:08AM
164:Foundations with (almost) no axioms, 4/22/0 5:31PM
165:Incompleteness Reformulated 4/29/03 1:42PM
166:Clean Godel Incompleteness 5/6/03 11:06AM
167:Incompleteness Reformulated/More 5/6/03 11:57AM
168:Incompleteness Reformulated/Again 5/8/03 12:30PM
169:New PA Independence 5:11PM 8:35PM
170:New Borel Independence 5/18/03 11:53PM
171:Coordinate Free Borel Statements 5/22/03 2:27PM
More information about the FOM
mailing list