The following letters a,b,e,… denote Turing degrees. We say a ≫ b if there exists a complete extension of degree a to the Peano Arithmetic augmented with axioms n ˙ ∈ B ˙ whenever n ∈ B, and n ˙ ∉ B ˙ whenever n ∉ B, where n˙ are constant symbols for n ∈ ω and B is any given set of degree b. Now in Volume 90, Pages ii-viii, 1-1165 (1977) HANDBOOK OF MATHEMATICAL LOGIC, Degrees of Unsolvability: A Survey of Results, Pages 631-652 by Stephen G. Simpson, Theorem 6.5 i), it is claimed that if a≫b then there exists another degree e such that a ≫ e ≫ b. There was no proof there. I am wondering how to prove this?

Question

The following letters a,b,e,… denote Turing degrees. We say   a  ≫  b if there exists a complete extension of degree a to the Peano Arithmetic augmented with axioms             n      ˙        ∈            B      ˙       whenever   n  ∈  B, and             n      ˙        ∉            B      ˙      whenever   n  ∉  B, where n˙ are constant symbols for   n  ∈  ω and B is any given set of degree b. Now in Volume 90, Pages ii-viii, 1-1165 (1977) HANDBOOK OF MATHEMATICAL LOGIC, Degrees of Unsolvability: A Survey of Results, Pages 631-652 by Stephen G. Simpson, Theorem 6.5 i), it is claimed that if a≫b then there exists another degree e such that   a  ≫  e  ≫  b. There was no proof there. I am wondering how to prove this?

Kimberly Evans · Accepted Answer

The first key fact is that for every degree a there is a a-computable infinite tree       T    a    ⊆      2          &amp;lt;      ω       such that an arbitrary degree c is PA over a if and only if c computes a path through       T    a  , that is, an element of [      T    a  ]. This fact is mentioned relatively often in the literature.The second key fact is that we can iterate finding paths in a certain way. There is another a-computable infinite tree                     T        ~              a    ⊆      2          &amp;lt;      ω       such that any path through                     T        ~              a   is of the form   f  ⊕  g where   f  ∈  [      T    a    ] and   g  ∈  [      T    f    ]. (In the language of Reverse Mathematics, we might say that we can combine two successive applications of weak König&#039;s lemma into a single application.) This is well known to experts in the field, but perhaps not directly emphasized in the literature.To see how to construct                     T        ~              a  , first note that       T    a   is uniformly computable from a, which means there is a computable relation   R  ⊆  ω  ×      2          &amp;lt;      ω        ×      2          ω       such that, for all   σ  ∈      2          &amp;lt;      ω       and   f  ∈      2          ω      ,  σ  ∈      T    f    ⇔  (  ∀  n  )  R  (  n  ,  σ  ,  f  )  .Next define a class   A  ⊆      2          ω       as follows. Given   f  ∈      2          ω      , write   f  =      f    0    ⊕      f    1  . Then we put   f  ∈  A if and only if       f    0    ∈  [      T    a    ] and, for all k and n,   R  (  n  ,      f    1    [  k  ]  ,      f    0    ). This is a       Π    1          0      ,      a       definition of A, so there is an a-computable infinite tree                     T        ~              a   such that   A  =  [                    T        ~              a    ], and the definition of A ensures that             T      ~       has the desired property.Now, because                     T        ~              a   is computable from a, and   b  ≫  a, there is a path   h  =  f  ⊕  g  ∈  [                    T        ~              a    ]computable from b. Let c be the degree of f. Then   c  ≫  a, because   f  ∈      T    a  , and   b  ≫  c, because b computes g, which is a path through       T    f  .We can extend this construction farther to show that, if   a  ≪  b, then there is an f computable from b such that, if   f  =      ⊕          i      ∈      ω            f    i  , then   a  =      f    0   and       f          i        ≪      f          i      +      1      for all i. So b uniformly computes an entire increasing sequence above a separated by ≪. In fact, b computes a countable coded   ω-model of             W      K      L        0   containing a (which is the same as a Scott set containing a).The method in the previous paragraph, in turn, is one way to show that every countable coded   ω-model of             W      K      L        0  contains, as a single real, another countable coded   ω-model of             W      K      L        0  . This is one of the more amazing and remarkable results of the field.

Answered question

Answer & Explanation

New Questions in Research Methodology