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 in! B whenever nin!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?

kadirsmr9d

kadirsmr9d

Answered question

2022-09-10

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?

Answer & Explanation

Kimberly Evans

Kimberly Evans

Beginner2022-09-11Added 13 answers

The first key fact is that for every degree a there is a a-computable infinite tree T a 2 < ω 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 < ω 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'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 < ω × 2 ω such that, for all σ 2 < ω 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.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Research Methodology

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?