Spectrum of the Atomless Elements Ideal

Pavel Semukhin (paulsem@ngs.ru)
Novosibirsk State University (Russia)

A notion of the degree spectrum of a relation on a computable structure was first introduced by V.S. Harizanov in [1] as follows. Let U be a relation on a computable structure A. Then the degree spectrum (or simply the spectrum) of U is the set Spec(U)={ deg_T(U ') | there is a computable structure A ' @ A with U ' the image of U}, where deg_T(U) denotes Turing degree of U.

J.B. Remmel [2] studied the spectrum of a set of atoms of computable Boolean algebra. In particular, he proved that if computable Boolean algebra has a computable presentation with an infinite computable set of atoms, then the spectrum of the set of atoms consists of all c.e. Turing degrees.

We obtained the following results on the spectrum of the atomless ideal.

Theorem. 1 Given a computable Boolean algebra B with a computable non-principal atomless ideal Al, there exists a sequence of a computable Boolean algebras {B ⁿ } such that B ⁿ @ B for all n and Al ⁱ is not reducible to Al ^j for all i ≠ j, where Al ⁿ is the atomless ideal of B ⁿ.

Theorem. 2 Let B be a computable Boolean algebra with computable set of atoms, and let ch(B)=(1,1,0). If Al is the atomless ideal of B then Spec(Al) consists of all Turing degrees of Π₂⁰ sets.

References

[1]

V.S. Harizanov, Degree spectrum of a recursive relation on a recursive structure, PhD Thesis, University of Wisconsin, Madison, WI (1987).

[2]

J.B. Remmel, Recursive isomorphism types of recursive Boolean algebras, J. Symbolic Logic 46 (1981), 572-594.