There is no fat orbit
type: Item
instance of: scholarly article
title: There is no fat orbit
zbMATH Open document ID: 0858.03043
DOI: 10.1016/0168-0072(96)83748-1
author: Rodney G. Downey
author: Leo Harrington
published in: Annals of Pure and Applied Logic
publication date: 1997-03-17T00:00:00Z
review text: \({\mathcal E}\) is the lattice of r.e. sets. The relation that holds between members of \({\mathcal E}\) iff there is an automorphism of \({\mathcal E}\) taking one to the other induces a partition of \({\mathcal E}\) into orbits. The present paper proves and refines Harrington's unpublished result that no orbit contains representatives of every nonzero r.e. degree. The theorem is established by specifying an elementary property \({\mathcal S}\) and showing that there is a nonzero r.e. degree \(\underset\sim d\) all of whose r.e. members have \({\mathcal S}\), while there is a nonzero r.e. degree \(\underset\sim e\) such that no r.e. set whose degree is \(\leq \underset \sim e\) has \({\mathcal S}\). Thus no orbit can contain both a set of degree \(\underset \sim d\) and a set of degree \(\leq \underset \sim e\). The theorem is extended by showing that the degree \(\underset \sim e\) in the above can be \(\text{high}_2\), and that there are a low degree \({\underset \sim d} {_1}\) and a \(\text{high}_2\) degree \({\underset \sim d} {_2}\) such that \({\mathcal S}\) holds for every r.e. set with degree in the interval \([{\underset\sim d} {_1}, {\underset \sim d} {_2}]\). The paper poses some interesting open questions.
Mathematics Subject Classification ID: 03D25
Mathematics Subject Classification ID: 03D30
zbMATH DE Number: 933083
zbMATH Keywords: lattice of recursively enumerable sets
zbMATH Keywords: automorphism
zbMATH Keywords: orbits
reviewed by: Joseph S. Ullian
MaRDI profile type: Publication
full work available at URL: 0168-0072(96)83748-1
OpenAlex ID: W1992701385
cites work: A jump class of noncappable degrees
cites work: Highness and bounding minimal pairs
cites work: Jumps of Hemimaximal Sets
cites work: Automorphisms of the lattice of recursively enumerable sets: Orbits
cites work: Minimal pairs in initial segments of the recursively enumerable degrees
cites work: Post's program and incomplete recursively enumerable sets.
cites work: Definable properties of the computably enumerable sets
cites work: Variations on promptly simple sets
cites work: Classes of Recursively Enumerable Sets and Degrees of Unsolvability
cites work: Recursively enumerable sets of positive integers and their decision problems
cites work: A non-inversion theorem for the jump operator
cites work: Automorphisms of the lattice of recursively enumerable sets. I: Maximal sets
cites work: Q4040892
cites work: Q3657980
description: scientific article; zbMATH DE number 933083