There is no fat orbit (Q1923566)

From MaRDI portal
Revision as of 08:28, 29 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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
    0 references
    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

    Identifiers