FOM: 17:Very Strong Borel statements

[Harvey Friedman]

This is the 17th in a series of positive self contained postings to fom
covering a wide range of topics in f.o.m. Previous ones are:

1:Foundational Completeness   11/3/97, 10:13AM, 10:26AM.
2:Axioms  11/6/97.
3:Simplicity  11/14/97 10:10AM.
4:Simplicity  11/14/97  4:25PM
5:Constructions  11/15/97  5:24PM
6:Undefinability/Nonstandard Models   11/16/97  12:04AM
7.Undefinability/Nonstandard Models   11/17/97  12:31AM
8.Schemes 11/17/97    12:30AM
9:Nonstandard Arithmetic 11/18/97  11:53AM
10:Pathology   12/8/97   12:37AM
11:F.O.M. & Math Logic  12/14/97 5:47AM
12:Finite trees/large cardinals  3/11/98  11:36AM
13:Min recursion/Provably recursive functions  3/20/98  4:45AM
14:New characterizations of the provable ordinals  4/8/98  2:09AM
14':Errata  4/8/98  9:48AM
15:Structural Independence results and provable ordinals  4/16/98  10:53PM
16:Logical Equations, etc.  4/17/98  1:25PM
16':Errata  4/28/98  10:28AM

A complete archiving of fom, message by message, is available at
http://www.math.psu.edu/simpson/fom/
Also, my series of positive postings (only) is archived at
http://www.math.ohio-state.edu/foundations/manuscripts.html

Let A,B containedin X^k, k >= 2. For x in X, let A_x = {y in S^k-1: (x,y)
in X}. These are the cross sections of A. We say that A refines B if and
only if for all x in X, if B_x is nonempty then A_x is a nonempty subset of
B_x. Note that we do not require A containedin B. If k = 2 then we say A is
symmetric if and only if (x,y) in A implies (y,x) in A.

Let R be the set of all real numbers. The following is essentially from my
paper "On the necessary use of abstract set theory," Adv. in Math., 1981.

THEOREM A. Every symmetric Borel subset of R^2 or its complement is refined
by a closed set. In fact, by a closed set that meets every vertical line.

It was essentially proved there that for both forms of this statement, it
is necessary and sufficient to use uncountably many cardinals.

Let CS(R^3) be the space of countable subsets of R^3. The Borel sets and
Borel mappings are defined in the usual way in terms of codes. A code for
an element of CS(R^3) is an infinite sequence of real numbers whose range
is that element.

PROPOSITION B. For all Borel F:CS(R^3) into CS(R^3) there exists A such
that every symmetric cross section of F(A) or its complement is refined by
the closure of some cross section of A.

Here "closure" means "topological closure."

It is necessary and sufficient to use uncountably many Woodin cardinals in
order to prove Proposition B.

We now consider Turing degrees. Let TD be the space of all Turing degrees
on Baire space. Let CS(TD) be the space of all countable subsets of TD. The
Borel sets and functions and again defined in terms of codes in the
standard way.

Let A,B in CS(TD). We say that A is a cone in B if and only if A = {x in B:
x >= b} for some b in B.

The familiar Borel Turing degree determinacy says:

THEOREM C. Every Borel subset of TD or its complement contains or is
disjoint from a cone.

It is necessary (Friedman) and sufficient (Martin) to use uncountably many
cardinals in order to prove Theorem C.

PROPOSITION D. For all Borel F:CS(TD) into CS(TD) there exists A such that
F(A) is a subset of A that contains or is disjoint from a cone in A.

It is necessary and sufficient to use infinitely many Woodin cardinals in
order to prove Propositions B and D. More specifically, B and D each
individually proves the consistency of ZFC + {there are at least n Woodin
cardinals}_n, and B,D are both provable in ZFC + "there are infinitely many
Woodin cardinals."

A cardinal kappa is Woodin if and only if for all f:kappa into kappa, there
is an alpha < kappa with f[alpha] containedin alpha and an elementary
embedding j from V into a transitive class M containing all ordinals, with
critical point alpha and where V(j(f)(alpha)) containedin M.

We can of course talk in terms of PD (projective determinacy) instead of
large cardinals. Then Propositions B and D implies the consistency of ZFC +
PD, and Propositions B,D are provable in ZFC + determinacy for
L_omega_1(R).