FOM: 104:Turing Degrees/3

Harvey Friedman friedman at
Thu Apr 12 15:19:53 EDT 2001

This is the third installment about Turing Degrees planned for FOM.

We begin by correcting some statements made in #102.

a. We used the terminology "spread apart" in section 2. As is clear from
context, we mean that "n degrees are spread apart" if and only if the jump
of each degree is recursive in the next.

b. At the very end of section 2, we wrote

>We can also equally well use "any two finite initial segments of the same
>length are arithmetically equivalent".

This is false. See below after this list of corrections.

c. We wrote:

>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 indicates the strength of these two statements. But the first
statement in Proposition 9 is too weak (roughly at the level of Zermelo set
theory). Here is the corrected version that supports Theorem 10..

PROPOSITION 9. There exists d1 << d2 << ... such that d1,d2,d3,... =A
d1,d3,d4,...  . There exists an omega sequence of degrees such that any two
omega subsequences are arithmetically equivalent.



Here is the new Sigma-1-1 statement.

THEOREM 1. Some degree is arithmetically equivalent to its jump.

THEOREM 2. Theorem 1 is provable in Zermelo set theory but not in Zermelo
set theory with bounded separation.

Of course, "some degree is arithmetically equivalent to all higher degrees"
also works, but is Sigma-1-2.

Note that from Theorem 1, we get d1 << d2 << ... such that any two finite
initial segments of the same length are arithmetically equivalent. Also,
from a slight extension of Theorem 1, still roughly at the level of Z, we
get d1,d2,... =A d2,d3,... by taking di = the i-th jump of d.

THEOREM 3. It is provable in ACA that "some degree is arithmetically
equivalent to its jump" implies the existence of an omega model of Zermelo
set theory with bounded separation but follows from the existence of an
omega model of Zermelo set theory.


 This is the 104th 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
 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
102: 102:Turing Degrees/2  5:20PM  4/8/01
103:Hilbert's Program for Consistency Proofs/1  11:10AM  4/11/01

More information about the FOM mailing list