On the d-c.e. and n-c.e. Turing and enumeration degrees

                          Marat M. Arslanov
                        Kazan State University

The well-known problem of the elementary equivalence of the partial
orderings of the n-c.e. degrees for all n>1 and the investigation
of our team in this area will be considered. We will discuss the
problem from three angles:

1. The analogue of the problem for the enumeration (e-) degrees.

a) The diamond lattice is embeddable into the 3-c.e. e-degrees preserving 0 
   and 1. Therefore, the partial orderings D_2 and D_n, n>2, (of the 2-c.e.
   and n-c.e. degrees, respectively) are not elementarily equivalent.

b) - If 1<m<2n then each m-c.e. e-degree a>0
     is n-splittable avoiding any nonzero Delta_2^0-e-degree c,
     i. e. there exist m-c.e. e-degrees b_1,...,b_n
     such that a = b_1 \cup ... \cup b_n and c
     \not\le b_i for all i, 1 \le i \le n.

   - For all n>1 there is a 2n-c.e. e-degree a which is not
     n-splittable avoiding some nonzero 3-c.e. e-degree c.

     Therefore, the partial orderings D_m and D_n, n>2 are
     not elementarily equivalent if 1<m<2p \le n for some integer p.

     The question of elementarily equivalence of the partial orderings
     D_{2n} and D_{2n+1} for n>1 remains open. But,

   - if the unary relation $R(a) = "a is a Pi_1^0-e-degree"
     is uniformly (i. e. by the same formula) definable in the partial 
     orderings D_{2n}, and D_{2n+1}, then they are not elementarily equivalent.

2. This last result highlights the following question for Turing degrees:
Are the partial orderings of n-c.e. and m-c.e. Turing degrees elementarily 
equivalent for n \not= m if there is a unary predicate for the c.e. degrees
available, so the elementary difference would be allowed to mention the 
existence of certain c.e. degrees. This question is open.

3. It is known that the existential theory of the n-c.e.
degrees is decidable and the AEAE-theory of the n-c.e. degrees is undecidable.
Further in my talk I will discuss the AE-theory of this structure as well 
as some other related questions.