ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

1. Logic

1991 MS Classification: 03D30 Arslanov, Marat M., Kazan State University, Russia The enumeration degree structures A set A is enumeration reducible (e-reducible) to a set B if there exists a recursively enumerable (r. e.) set Φ (called in this context an e-operator) such that A = {x : (∃u)[⟨x, u⟩ ∈ Φ & D_{u} ⊆ B]}. The structure D_{e} of the e-degrees is the structure of the equivalence classes (called e-degrees) of sets of numbers under the equivalence relation ≡_{e} generated by the preordering ≤_{e}; the e-degree of A is denoted by the symbol deg_{e}(A). D_{e} is in fact an upper semilattice with least element 0_{e}, where 0_{e} = deg_{e}(W), any r. e. set W. We study the structures D_{α,e} of α-r. e. e-degrees for α ≤ ω. In [CSY] it was shown that for any Δ_{2}^{0}-e-degree a >_{e} 0_{e} there exists a Δ_{2}^{0}-e-degree b <_{e} 0′_{e} such that 0′_{e} = a ∪ b. In [AS] we showed that here in general we can not choose b as an ω-r. e. e-degree: there is a Δ_{2}^{0}-e-degree a >_{e} 0_{e} such that a ∪ b <_{e} 0′_{e} for any ω-r. e. e-degree b <_{e} 0′_{e}. We will discuss further results of this kind. In particular, we prove that structures of n-r. e., ω-r. e. and total e - degrees for n < ω are not pairwise elementarily equivalent, and discuss the analog of Downey’s Conjecture for the structures of n-r. e. e-degrees, 1 < n < ω. References: [CSY] S. B. Cooper, A. Sorbi, and X. Yi. Cupping and noncupping in the enumeration degrees of Σ_{2}^{0}-sets. To appear.

[AS] M. M. Arslanov, A. Sorbi. A note on the Δ_{2}^{0} enumeration degrees. To appear.