[FOM] simpler Borel/PD

Harvey Friedman friedman at math.ohio-state.edu
Mon May 26 08:58:25 EDT 2003


I want to simplify posting 173, 5/25/03 2:11AM.

1. Turing Degrees.

Let d be a Turing degree. We write cone(d) for the cone of d, which 
is the set of all Turing degrees e >= d.

PROPOSITION 1. Let F be a Borel function from countable sets of 
Turing degrees into countable sets of Turing degrees. There exists A 
and d in A such that F(A) containedin A intersect cone(d) or F(A) 
containedin A\cone(d).

PROPOSITION 2. Let F be a Borel function from countable sets of 
Turing degrees into countable sets of countable sets of Turing 
degrees. There exists A such that for all B in F(A) there exists d in 
A with: B containedin A intersect cone(d) or B containedin A\cone(d).

THEOREM 3.  Proposition 1 is provable in ZFC + the existence of a 
Woodin cardinal, but not in ZFC + there are arbitrarily large strong 
cardinals.

THEOREM 4. Proposition 2 is provable in ZFC + there exists infinitely 
many Woodin cardinals, but not in ZFC + {there exists n Woodin 
cardinals}_n.

2. Analysis Degrees.

I want to replace the use of Turing degrees above with "analysis degrees".

The analysis degrees live on the real line. Let x,y be real numbers. 
We say that x is immediately analytic in y if and only if x can be 
written as a "basic analytic expression" using only the constant y.

The relation <=A is defined as the transitive closure of "immediately 
analytic in".

Then we simply repeat the previous section line for line with this 
new reducibility <=A.

The fundamental bridge between <=A and degrees in recursion theory is 
the following.

LEMMA. Let x be sufficiently high in <=A. Then y <= A x if and only 
if y is arithmetic in x.

The only problem is that I haven't yet defined what a "basic analytic 
expression" is. I know how to do this reasonably well, but some 
simplifications have to be examined before I present it. In addition 
to standard functions from real analysis, one uses infinite series 
whose terms are given by expressions that are standard in real 
analysis.

This will become a numbered posting when I fix on the meaning of 
"basic analytic expressions" for this purpose.

Harvey Friedman





More information about the FOM mailing list