Invariance of properties under automorphisms of the lattice of recursively enumerable sets (Q790103): Difference between revisions

A coinfinite r.e. set A of integers is dense simple (D. A. Martin) if the principal function enumerating the complement \(\bar A\) of A in increasing order, \(p_{\bar A}\), dominates every total recursive function. The author proves that the property of an r.e. set being dense simple is not invariant under automorphism of the collection \({\mathcal E}\) of r.e. sets. This extends the result of D. A. Martin that hypersimplicity is not invariant under automorphisms of \({\mathcal E}\). The argument involves an infinite injury ''pinball machine'' construction and uses the automorphism machinery of R. I. Soare.