[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