Effectively and Noneffectively Nowhere Simple Subspaces
Rodney G. Downey, Jeffrey B. Remmel · Birkhäuser Boston eBooks · 1993
Let ωe denote the e th r.e. subset of the natural numbers N, i.e. ωe = {x: φe(x) converges} where φe is the partial recursive function computed by the e th Turing machine. Then an r.e. set A is called nowhere simple if A is coinfinite and for any r.e. set W e, there exists an r.e. set W’e ⊆ W e such that W’e ⋂ A = Ø and card(W e − A) = ∞ if and only if card(W’e) = ∞. We say A is effectively nowhere simple if there is an effective procedure to find the index of such a W’e from e, i.e. if there is a recursive function f such that W f(e) = W’e. In this case, f is said to be a witness function for A. These classes of sets were introduced by Shore in [20] where he used them to investigate automorphism bases for ℒ(ω) (the lattice of r.e. sets) and ℒ*(ω) (ℒω) modulo finite sets). In particular he was able to give an easy proof of the main result of [19] that any nontrivial class of r.e. sets closed under recursive isomorphisms is an automorphism base for ℒ*(ω) using these sets. Subsequent to this paper, various investigations concerning automorphisms of ℒ(ω) and ℒ*(ω) have utilized properties of r.e. sets with rich lattices of supersets. For example, for effectively nowhere simple sets, Maass [11] proved that any two effectively nowhere simple sets have effectively isomorphic lattices of supersets. Another such property is the outer splitting property [11].