There is no fat orbit (Q1923566)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | There is no fat orbit |
scientific article |
Statements
There is no fat orbit (English)
0 references
17 March 1997
0 references
\({\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.
0 references
lattice of recursively enumerable sets
0 references
automorphism
0 references
orbits
0 references