[FOM] 173:Borel/DST/PD

Sun May 25 02:11:35 EDT 2003

We now want to convert this version of the Borel statement in posting 
#170 to a Borel statement which is in the spirit of DST that 
corresponds to PD.

THEOREM. Every Borel set in the plane contains or is disjoint from a 
closed set whose fld is R.

1. COUNTABLE SETS OF REALS.

Let us revisit my old work on Borel diagonalization in

On the Necessary Use of Abstract Set Theory, Advances in Math., 
September, 1981.

CANTOR. Every sequence of reals omits a real.

OBSERVATION. There is a Borel function F:R^infinity into R such that 
for all x, F(x) is off of x.

QUESTION: Is there an invariant Borel function F:R^infinity into R 
such that for all x, F(x) is off of x?

The answer is NO for various notions of "invariant". Consider the 
following three equivalence relations on R^infinity.

a) having the same set of terms;
b) being permutations of each other;
c) being finite permutations of each other.

By an "invariant" F:R^infinity into R we mean that for all x 
equivalent to y, F(x) = F(y). Thus we have three notions of invariant.

THEOREM 1.1. Let F:R^infinity into R be an "invariant" Borel 
function. There exists x such that F(x) is a coordinate of x.

THEOREM 1.2. Theorem 1.1 is not provable in Z_2 or in ZFC\P, but is 
provable in very weak fragments of Z_3 or in ZFC\P + P(omega) exists. 
This holds for any of the three senses of "invariant" listed above.

It is very natural in light of this development to consider the space 
CS(R) of all countable subsets of R.

There is a very natural and robust way to talk about the Borel 
subsets of CS(R).

Let F:R into R^infinity be any surjective Borel function. We say that 
E containedin CS(R) is Borel if and only if

{x in R: rng(F(x)) in E}

is Borel.

Once we pass to CS(R), only the equivalence relation a) retains relevance.

THEOREM 1.3. This definition does not depend on the choice of the 
surjective Borel function F:R into R^infinity.

We now come to G:CS(R) into R. Here are some possible definitions of 
G is Borel.

i. The inverse image of every open subset of R is a Borel subset of CS(R).
ii. The inverse image of every Borel subset of R is a Borel subset of CS(R).
iii. The function H:R into R given by H(x) = G(rng(F(x))) is Borel.

THEOREM 1.4. All three definitions of G:CS(R) into R being Borel are 
equivalent. Definition iii does not depend on the choice of the 
surjective Borel function F:R into R^infinity.

I also have worked with Borel functions F:R^infinity into R^infinity. 
There is a literal proliferation of interesting notions of invariant 
here. I only looked at three such.

1. If x,y have the same set of terms then F(x),F(y) have the same set of terms.
2. If x,y are permutations of each other then F(x),F(y) are 
permutations of each other.
3. Every permutation of x,y is a permutation of F(x),F(y).

THEOREM 1.5. Let F:R^infinity into R^infinity be invariant. There 
exists x such that F(x) is a subsequence of x.

THEOREM 1.6. Theorem 1.5 is not provable in Z_2 or in ZFC\P, but is 
provable in very weak fragments of Z_3 or in ZFC\P + P(omega) exists. 
This holds for any of the three senses of "invariant" listed above.

It is invariant notion 1 above that is relevant to where we are going.

Let G:CS(R) into CS(R). What does it mean to say that G is Borel? 
Here are two notions.

iv. The inverse image of every Borel subset of CS(R) is a Borel 
subset of CS(R).
v. There is a Borel function H:R into R such that for all x, G(F(x)) = F(H(x)).

In v, we assume that we have chosen some Borel surjective F:R into R^infinity.

It is clear that v implies iv, no matter what F we have chosen. 
However, I doubt that iv implies v.

THEOREM 1.7. Definition v does not depend on the choice of the 
surjective Borel function F:R into R^infinity.

So v is our official definition of Borel G:CS(R) into CS(R).

The definition obviously extends to Borel F:CS(T) into CS(T), where T 
is any Polish space, with the same robustness.

We can now restate one form of Theorem 1.5.

THEOREM 1.8. Let F:CS(R) into CS(R). There exists A such that F(x) 
containedin x. We can replace R by any Polish space T.

THEOREM 1.9. Theorem 1.8, either form, is not provable in Z_2 or in 
ZFC\P, but is provable in very weak fragments of Z_3 or in ZFC\P + 
P(omega) exists.

2. COUNTABLE SUBSETS OF R^3.

Let A containedin R^n. For x in R, write A_x for the cross section

{y in R^n-1: (x,y) in A}.

We write cl(A) for the usual topological closure of A, which is the 
least closed set in R^n containing A.

We write fld(A) for the fld of A, which is the set of all coordinates 
of elements of A.

We say that A is relatively closed if and only if

A = cl(A) intersect fld(A)^n.

PROPOSITION 2.1. Let F:CS(R^3) into CS(R^3) be a Borel function. 
There exists A such that every F(A)_x contains or is disjoint from 
some relatively closed A_y with the same fld as F(A).

THEOREM 2.2. Proposition 2.1 can be proved in ZFC + AD(L_omega1(R)), 
but not in ZFC + PD. ATR0 + Proposition 2.1 proves the existence of 
an omega model of ZFC + PD. In terms of large cardinals, Proposition 
2.1 can be proved in ZFC  + "there are infinitely many Woodin 
cardinals" but not in ZFC + {there are n Woodin cardinals}_n.

We rely on results of Martin, Steel, and Woodin.

*********************************************

I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.
This is the 173rd 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
172:Ordered Fields/Countable DST/PD/Large Cardinals  5/34/03  1:55AM

Harvey Friedman