FOM: 102:Turing Degrees/2
Harvey Friedman
friedman at math.ohio-state.edu
Sun Apr 8 17:20:30 EDT 2001
This is the second installment about Turing Degrees planned for FOM. We
continue the discussion.
1. UNIFORM ARITHMETICITY.
We introduce the notation UA(d), for degrees d, for the set of all reals
uniformly arithmetic in d.
The following is a restatement of a theorem from Turing Degrees/1.
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.
THEOREM 1. There exists d such that UA(d) containedin d. This is provable
in Z2+ not provable in Z2.
The following is a sharpening of a theorem from Turing Degrees/1.
Let Z be Zermelo set theory and Z- be Zermelo set theory with bounded
separation.
THEOREM 2. 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.
QUESTION: 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.
We will return to uniform arithmeticity after we discuss arithmetic
indiscernibles (in the third installment).
2. ARITHMETIC INDISCERNIBLES - FINITE TUPLES.
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
real "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*
For degrees d,e, we write
d << e
if and only if d' <= e, where d' is the Turing jump of d.
We now discuss some strong Sigma-1-1 sentences.
THEOREM 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 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 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 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-.
We now look at infinite sequences of degrees.
THEROEM 7. Let n > = 2. There exists 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 8. There exists 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}.
We can also equally well use "any two finite initial segments of the same
length are arithmetially equivalent".
3. ARITHMETIC INDISCERNIBLES - OMEGA SEQUENCES.
There seem to be several notions of arithmetic equivalence of omega
sequences of degrees. We are interested in using a natural notion which is
Sigma-1-1.
We first define the "arithmetic properties of omega sequences of degrees".
These are the arithmetic properties of omega sequences of reals whose truth
value depends only on the Turing degrees of the terms.
Finally, two omega sequences of degrees, d*,e*, are arithmetically
equivalent (written d* =A e*) if and only if there are choices of
representatives for d*,e* such that any arithmetic property of omega
sequences of degrees that holds of the choice of representatives for d*
holds of the choice of representatives for e*.
Note that d* =A e* is Sigma-1-1.
Also note that if we were to give this definition for finite sequences of
degrees, then it would agree with the simpler definition used in section 2
above.
PROPOSITION 9. There exists d1 << d2 << ... such that d1,d2,... =A
d2,d3,... . There exists an omega sequence of degrees such that any two
omega subsequences are arithmetically equivalent.
THEOREM 10. Both form of Proposition 10 are provable in ZFC + "there exists
a measurable cardinal" but neither is provable in ZFC + "for all x
containedin omega, x# exists".
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).
******************************
This is the 102nd 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:Qadratic 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 11:29AM 3/21/01
101:Turing Degrees/1 3:32AM 4/2/01
More information about the FOM
mailing list