[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