Invariance of properties under automorphisms of the lattice of recursively enumerable sets
type: Item
instance of: scholarly article
title: Invariance of properties under automorphisms of the lattice of recursively enumerable sets
zbMATH Open document ID: 0534.03017
author: Michael Stob
published in: Pacific Journal of Mathematics
publication date: 1982-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03D25
Mathematics Subject Classification ID: 03D30
zbMATH DE Number: 3847371
zbMATH Keywords: recursively enumerable set
zbMATH Keywords: hypersimple
zbMATH Keywords: dense simple
zbMATH Keywords: infinite injury priority
zbMATH Keywords: automorphism
reviewed by: Peter Clote
MaRDI profile type: Publication
full work available at URL: pjm.1982.100.445
OpenAlex ID: W1997375978
DOI: 10.2140/PJM.1982.100.445
description: scientific article; zbMATH DE number 3847371