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
bad has happened.

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

read "d,e are arithmetically equivalent"

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

read "alpha,beta are arithmetically equivalent"

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
 36:Adjacent Ramsey Theory  3/23/99  1:00AM
 37:Adjacent Ramsey Theory/more  5:45AM  3/25/99
 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
 68:Bad to Worse/Conjectures  10/28/99  10:00PM
 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
 78:Quadratic Axioms/Literature Conjectures  1/7/00  11:51AM
 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
 96:Comments on BRT  12/20/00  9:20AM
 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






More information about the FOM mailing list