Parameter definability in the recursively enumerable degrees

摘要

The biinterpretability conjecture for the r.e. degrees asks whether, for each sufficiently large k, the Σ_k~0 relations on the r.e. degrees are uniformly definable from parameters. We solve a weaker version: for each k ≥ 7, the Σ_k~0 relations bounded from below by a nonzero degree are uniformly definable. As applications, we show that Low_1 is parameter definable, and we provide methods that lead to a new example of a 0-definable ideal. Moreover, we prove that automorphisms restricted to intervals [d,1], d ≠ 0, are Σ_7~0. We also show that, for each c ≠ 0, (N,+,X) can be interpreted in [0,c] without parameters.