FOM: 105:Turing Degrees/4

Harvey Friedman friedman at math.ohio-state.edu
Thu Apr 26 19:44:22 EDT 2001

```We have looked at the proofs of some of the claims in Turing Degrees 1-3 in
more detail and have to make some adjustments in some of them. Nothing too

So at this point, we make a complete restatement, and add some additional
material.

Therefore this posting supercedes postings #101, 102, and 104.

TURING DEGREES
by
Harvey M. Friedman
April 25, 2001

Here we make the common conventions that

i) "degree" always means Turing degree;
ii) "real" always means a subset of omega.

1. UNIFORM ARITHMETICITY.

Let d be a degree and x be a real. We say that x is uniformly arithmetic in
d if and only if there is an arithmetic formula phi(n,y), with only the
free variables shown, such that for ALL y in d,

x = {n: phi(n,y)}.

I.e, x is not only arithmetic in every real of degree d, but x is uniformly
arithmetic in every real of degree d.

Note that under usual terminology, x is arithmetic in d if and only if
there is an arithmetic formula phi(n,y), with only the free variables
shown, such that for SOME y in d,

x = {n: phi(n,y)}.

We introduce the notation UA(d), for degrees d, for the set of all reals
uniformly arithmetic in d. We let A(d) be the set of all reals arithmetic
in d.

There is a concept that is closely related to this question. We say that an
element of d is arithmetically distinguished if and only if there is an
arithmetic predicate which has exactly one solution among the elements of
d.

THEOREM 1.1. The following are equivalent.
i) there is an arithmetically distinguished element of d;
ii) every element of d is an arithmetically distinguished element of d;
iii) UA(d),d meet;
iv) UA(d) = A(d).

THEOREM 1.2. If d is the degree of an arithmetic singleton then UA(d) =
A(d). If d is Cohen generic over the arithmetic reals then UA(d),d are
disjoint, and UA(d) is the arithmetic sets.

PROBLEM: When does UA(d) = A(d)?

As we shall now see, it might well be the case that UA(d) is quite small.

Let Z2 be the usual first order system of second order arithmetic. Let Z2+
be Z2 with a satisfaction predicate added and induction and comprehension
are extended to all formulas in the expanded language.

We use <=d to denote the set of all reals recursive in some (all) elements
of d.

THEOREM 1.3. There exists d such that UA(d) containedin <=d. This is provable
in Z2+ not provable in Z2.

Note by Theorem 1.1 that UA(d) containedin <=d implies UA(d) containedin <d.

Let Z be Zermelo set theory and Z- be Zermelo set theory with bounded
separation.

THEOREM 1.4. UA is constant on a cone. This is provable in Z but not in Z-.

The preferred value of UA is the unique A such that UA is constantly A on
some cone.

PROBLEM: What is the structure of the preferred value of UA? It contains
all reals x such that for some n, x lies in the minimum beta model of n-th
order arithmetic.

Much more detailed investigations can be made by stratifying UA and
"arithmetically distinguished". We say that x is uniformly Sigma-0-k
(Pi-0-k) in d if and only if there is a Sigma-0-k (Pi-0-k) formula
phi(n,y), with only the free variables shown, such that for all y in d,

x = {n: phi(n,y)}.

We say that x is a Sigma-0-k (Pi-0-k) distinguished element of d if and
only if there is a Sigma-0-k (Pi-0-k) formula phi(n,y) with only the free
variables shown, such that x is the unique solution among d of phi(n,y).

And the same definition of uniformity can be given with respect to
practically any notion of reducibility. I.e., take a notion of reducibility
to be a countable collection of partial functions from the power set of
omega into itself.

We say that x is uniformly Delta-0-k in d if and only if it and its
complement are uniformly Sigma-0-k in d. We say that x is uniformly
recursive in d if and only if x is uniformly Delta-0-1 in d.

Obviously x is uniformly Delta-0-k in d if and only if x is uniformly
recursive in the k-th jump of d.

PROBLEM: Rework everything said here using these stratified notions. This
will obviously be more delicate and lead to a number of new issues.

2. ARITHMETIC INDISCERNIBLES - FINITE SUBSEQUENCES OF FINITE SEQUENCES.

Let Zn be the usual first order system of n-th order arithmetic. Let Zn+ be
Zn with a satisfaction predicate added and induction and comprehension are
extended to all formulas in the expanded language.

For degrees d,e, we say that

d =A e

if and only if

*any arithmetic property that holds of some element of d also holds of some
element of e*

More generally, let alpha and beta be finite sequences of degrees. We say that

alpha =A beta

if and only if

*alpha,beta are of the same length, and any arithmetic property that holds
of some sequence of representatives for alpha also holds of some sequence
of representatives for beta*

We can modify the notion of alpha =A beta by replacing "... of some
sequence of representatives ..." with "... of all sequence of
representatives ..."

THEOREM 2.1. For all finite sequences alpha,beta, alpha =A beta if and only
if alpha =A beta in this modified sense.

THEOREM 2.2. Some degree is arithmetically equivalent to its jump. This is
provable in Z but not in Z-.

For degrees d,e, we write

d << e

if and only if d' <= e, where d' is the Turing jump of d.

THEOREM 2.3. There exist degrees d << e such that d =A e. I.e., there exist
two spread apart degrees which are arithmetically equivalent. This is
provable in Z2+ but not in Z2.

THEOREM 2.4. There exist degrees d1 << d2 << d3 such that d1,d2 =A d2,d3.
I.e., there exist three spread apart degrees such that the first two are
arithmetically equivalent to the last two. This is provable in Z3+ but not
in Z3.

THEOREM 2.5. Let n >= 2. There exist d1 << ... << dn such that d1,...,dn-1 =A
d2,...,dn. This is provable in Zn+ but not in Zn. Ths statement for all n
at once is provable in Z but not in Z-.

THEOREM 2.6. Let n >= 2. There exist d1 << ... << dn such that any two
subsequences of the same length are arithmetically equivalent. This is
provable in Zn+ but not in Zn. The statement for all n at once is provable
in Z but not in Z-.

What happens if we replace << with <? We can use mutually Cohen generic
reals to prove the following.

THEOREM 2.7. Let n >= 2. There exist d1 < ... < dn such that any two
subsequences of the same length are arithmetically equivalent. This is
provable in RCA0 + 0^omega exists.

3. ARITHMETIC INDISCERNIBLES - FINITE SUBSEQUENCES OF INFINITE SEQUENCES.

THEROEM 3.1. Let n > = 2. There exist d1 << d2 << ... such that any two
subsequenes of length n are arithmetically equivalent. This is provable in
Zn+1+ but not in Zn+1. The statement for all n at once is provable in Z but
not in Z-.

THEOREM 3.2. There exist d1 << d2 << ... such that any two finite
subsequences of the same length are arithmetically equivalent. This
statement is provable in ZC + "for all recursive well orderings e, V(e)
exists". This statement is not provable in ZC + {V(e) exists: e is a
provably recursive well ordering of ZC}.

What happens if we replace << with <? We can use mutually Cohen generic
reals to prove the following.

THEOREM 3.3. There exists d1 << d2 << ... such that any two finite
subsequences of the same length are arithmetically equivalent. This is
provable in RCA0 + 0^omega exists.

4. ARITHMETIC INDISCERNIBLES - INFINITE SUBSEQUENCES OF INFINITE SEQUENCES.

There seem to be several notions of arithmetic equivalence of infinite
sequences of degrees.

DEFN 1. Two infinite sequences of degrees are arithmetically equivalent if
and only if every arithmetic property that holds of some sequence of
representatives of the first holds of some sequence of representatives of
the second, and vice versa.

DEFN 2. Two infinite sequences of degrees are arithmetically equivalent if
and only if every arithmetic property that holds of every sequence of
representatives of the first holds of every sequence of representatives of
the second, and vice versa.

For the third definition, we first define the "arithmetic properties of
infinite sequences of degrees". These are the arithmetic properties of
inifnite sequences of reals whose truth value depends only on the Turing
degrees of the terms.

DEFN 3. Two infinite sequences of degrees are arithmetically equivalent if
and only if every arithmetic property of infinite sequences of degrees that
holds of the first holds of the second, and vice versa.

THEOREM 4.1. Defn 1 implies Defn 3. Defn 2 implies Defn 3.

PROBLEM: What are the relationships between Defn's 1-3?

We will only be using Defn 3. Note that it is Sigma-1-1. We will write =A.

Also note that these three definitions coincide if we make them for finite
sequences of degrees (and is the same as =A used in sections 1-3 above).

The following is contrary to what was claimed in posting #102 and #104.

THEOREM 4.2. There exist d1 << d2 << ... where any two infinite
subsequences are arithmetically equivalent. This is provable in ZC + "for
all recursive well orderings e, V(e) exists". This statement is not
provable in ZC + {V(e) exists: e is a provably recursive well ordering of
ZC}.

However, there is a satisfactory fix of the bug we found in the proof. Let
W be the (degree of the) set of all indices of recursive well orderings (or
any other complete Pi-1-1 set).

PROPOSITION 4.3. There exist d1 << d2 << d3 ... << W where any two infinite
subsequences of the d's are arithmetically equivalent.

THEOREM 4.4. Proposition 4.3 is provable in ZFC + "there exists
a measurable cardinal" but not in ZFC + V = L + "for all x
containedin omega, x# exists". The same is true of Proposition 4.3
relativized to L.

Using core model theory, both the upper and lower bounds can be sharpened
considerably. ZFC + "there exists an omega closed cardinal" is an upper
bound, and, say, ZFC + "a # for L(#) exists" is a lower bound. (Help from
Philip Welch).

What happens if we replace << with <? We can use mutually Cohen generic
reals to prove the following.

THEOREM 4.5. There exist d1 < d2 < ... < 0^omega such that any two infinite
subsequences of the same length are arithmetically equivalent. This is
provable in RCA0 + 0^omega exists.

Note that Proposition 4.3 is a Sigma-1-2 sentence. Also, note that it lives
below the double hyperjump. It follows from the existence of an omega model
of ZFC + "there exists an omega closed cardinal".

5. ARITHMETIC INDISCERNIBLES - INFINITE CONTRACTIONS OF INFINITE SEQUENCES.

Let d1 <= d2 <= ... be an infinite sequence of degrees. We say that
e1,e2,... is a contraction of d1 <= d2 <= ... if and only if for all n >= 1
there exists m >= 1 such that

d1 <= en <= dm
dm+1 <= en+1.

PROPOSITION 5.1. There exist d1 << d2 << d3 ... << W where any two
contractions of the d's are arithmetically equivalent. We can even require
that the sequences of degrees have a sequence of representatives that is <<
W.

THEOREM 5.2. Proposition 5.1 is provable in ZFC + "there exists
infinitely many Woodin cardinals" but not in ZFC + {there exists at least n
Woodin cardinals}n. The same is true of Proposition 5.1 relativized to L.

Theorem 5.2 passes through projective determinacy and uses work of Martin
and Steel.

What happens if we replace << with <? We can use mutually Cohen generic
reals to prove the following.

THEOREM 5.3. There exist d1 < d2 < ... < 0^omega such that any two infinite
contractions are arithmetically equivalent. This is provable in RCA0 +
0^omega exists.

Note that Proposition 5.1 is a Sigma-1-2 sentence. Also, note that it lives
below the double hyperjump. It follows from the existence of an omega model
of ZFC + "there are infinitely many Woodin cardinals".

6. DEGREES ARITHMETIC IN INFINITE SEQUENCES OF DEGREES.

Here we avoid using << and W.

Let d1,d2,... be an infinite sequence of degrees. We say that d is
arithmetic in d1,d2,... if and only if there is an arithmetic formula
phi(n,x) such that for all infinite sequences x of representatives from
d1,d2,...,

{n: phi(n,x)} lies in d.

Note that there are many other notions of "degree arithmetic in an infinite
sequence of degrees", and we have not considered them.

THEOREM 6.1. There exist d1,d2,... such that every degree arithmetic in
d1,d2,... is recursive in some term. This is provable in Z but not in Z-.

PROPOSITION 6.2. There exist d1,d2,... such that every degree that is
arithmetic in some infinite subsequence is recursive in some term. We can
even require that the sequence of degrees have a sequence of
representatives that is << W.

THEOREM 6.3. Proposition 6.2 is provable in ZFC + "there exists a
measurable cardinal" but not in ZFC + "for all x containedin omega, x#
exists". The same is true of Proposition 6.2 relativized to L.

Using core model theory, both the upper and lower bounds can be sharpened
considerably. ZFC + "there exists an omega closed cardinal" is an upper
bound, and, say, ZFC + "a # for L(#) exists" is a lower bound. (Help from
Philip Welch).

PROPOSITION 6.4. There exist d1 <= d2 <= ... such that every degree that is
arithmetic in some contraction is recursive in some term. We can even
require that the sequence of degrees have a sequence of representatives
that is << W.

THEOREM 6.5. Proposition 6.4 is provable in ZFC + "there exists infinitely
many Woodin cardinals" but not in ZFC + {there exists at least n Woodin
cardinals}n. The same is true of Proposition 6.4 relativized to L.

Theorem 6.5 passes through projective determinacy and uses work of Martin
and Steel.

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

This is the 105th in a series of 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
17:Very Strong Borel statements  4/26/98  8:06PM
18:Binary Functions and Large Cardinals  4/30/98  12:03PM
19:Long Sequences  7/31/98  9:42AM
20:Proof Theoretic Degrees  8/2/98  9:37PM
21:Long Sequences/Update  10/13/98  3:18AM
22:Finite Trees/Impredicativity  10/20/98  10:13AM
23:Q-Systems and Proof Theoretic Ordinals  11/6/98  3:01AM
24:Predicatively Unfeasible Integers  11/10/98  10:44PM
25:Long Walks  11/16/98  7:05AM
26:Optimized functions/Large Cardinals  1/13/99  12:53PM
27:Finite Trees/Impredicativity:Sketches  1/13/99  12:54PM
28:Optimized Functions/Large Cardinals:more  1/27/99  4:37AM
28':Restatement  1/28/99  5:49AM
29:Large Cardinals/where are we? I  2/22/99  6:11AM
30:Large Cardinals/where are we? II  2/23/99  6:15AM
31:First Free Sets/Large Cardinals  2/27/99  1:43AM
32:Greedy Constructions/Large Cardinals  3/2/99  11:21PM
33:A Variant  3/4/99  1:52PM
34:Walks in N^k  3/7/99  1:43PM
35:Special AE Sentences  3/18/99  4:56AM
35':Restatement  3/21/99  2:20PM
38:Existential Properties of Numerical Functions  3/26/99  2:21PM
39:Large Cardinals/synthesis  4/7/99  11:43AM
40:Enormous Integers in Algebraic Geometry  5/17/99 11:07AM
41:Strong Philosophical Indiscernibles
42:Mythical Trees  5/25/99  5:11PM
43:More Enormous Integers/AlgGeom  5/25/99  6:00PM
44:Indiscernible Primes  5/27/99  12:53 PM
45:Result #1/Program A  7/14/99  11:07AM
46:Tamism  7/14/99  11:25AM
47:Subalgebras/Reverse Math  7/14/99  11:36AM
48:Continuous Embeddings/Reverse Mathematics  7/15/99  12:24PM
49:Ulm Theory/Reverse Mathematics  7/17/99  3:21PM
50:Enormous Integers/Number Theory  7/17/99  11:39PN
51:Enormous Integers/Plane Geometry  7/18/99  3:16PM
52:Cardinals and Cones  7/18/99  3:33PM
53:Free Sets/Reverse Math  7/19/99  2:11PM
54:Recursion Theory/Dynamics 7/22/99 9:28PM
55:Term Rewriting/Proof Theory 8/27/99 3:00PM
56:Consistency of Algebra/Geometry  8/27/99  3:01PM
57:Fixpoints/Summation/Large Cardinals  9/10/99  3:47AM
57':Restatement  9/11/99  7:06AM
58:Program A/Conjectures  9/12/99  1:03AM
59:Restricted summation:Pi-0-1 sentences  9/17/99  10:41AM
60:Program A/Results  9/17/99  1:32PM
61:Finitist proofs of conservation  9/29/99  11:52AM
62:Approximate fixed points revisited  10/11/99  1:35AM
63:Disjoint Covers/Large Cardinals  10/11/99  1:36AM
64:Finite Posets/Large Cardinals  10/11/99  1:37AM
65:Simplicity of Axioms/Conjectures  10/19/99  9:54AM
66:PA/an approach  10/21/99  8:02PM
67:Nested Min Recursion/Large Cardinals  10/25/99  8:00AM
69:Baby Real Analysis  11/1/99  6:59AM
70:Efficient Formulas and Schemes  11/1/99  1:46PM
71:Ackerman/Algebraic Geometry/1  12/10/99  1:52PM
72:New finite forms/large cardinals  12/12/99  6:11AM
73:Hilbert's program wide open?  12/20/99  8:28PM
74:Reverse arithmetic beginnings  12/22/99  8:33AM
75:Finite Reverse Mathematics  12/28/99  1:21PM
76: Finite set theories  12/28/99  1:28PM
77:Missing axiom/atonement  1/4/00  3:51PM
79:Axioms for geometry  1/10/00  12:08PM
80.Boolean Relation Theory  3/10/00  9:41AM
81:Finite Distribution  3/13/00  1:44AM
82:Simplified Boolean Relation Theory  3/15/00  9:23AM
83:Tame Boolean Relation Theory  3/20/00  2:19AM
84:BRT/First Major Classification  3/27/00  4:04AM
85:General Framework/BRT   3/29/00  12:58AM
86:Invariant Subspace Problem/fA not= U  3/29/00  9:37AM
87:Programs in Naturalism  5/15/00  2:57AM
88:Boolean Relation Theory  6/8/00  10:40AM
89:Model Theoretic Interpretations of Set Theory  6/14/00 10:28AM
90:Two Universes  6/23/00  1:34PM
91:Counting Theorems  6/24/00  8:22PM
92:Thin Set Theorem  6/25/00  5:42AM
93:Orderings on Formulas  9/18/00  3:46AM
94:Relative Completeness  9/19/00  4:20AM
95:Boolean Relation Theory III  12/19/00  7:29PM
97.Classification of Set Theories  12/22/00  7:55AM
98:Model Theoretic Interpretation of Large Cardinals  3/5/01  3:08PM
99:Boolean Relation Theory IV  3/8/01  6:08PM
100:Boolean Relation Theory IV corrected  3/21/01  11:29AM
101:Turing Degrees/1  4/2/01  3:32AM
102: 102:Turing Degrees/2  4/8/01  5:20PM
103:Hilbert's Program for Consistency Proofs/1 4/11/01  11:10AM
104:Turing Degrees/3   4/12/01  3:19PM

```