The translation theorem (Q1325048)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The translation theorem |
scientific article |
Statements
The translation theorem (English)
0 references
7 July 1994
0 references
The paper brings new proofs for some known results concerning orbits in the lattice of recursively enumerable sets, in particular Soare's result on maximal sets and Maass's result on hyperhypersimple sets. The author claims that the new proofs should be more understandable. He shows that it suffices to construct uniformly \(0''\)-recursive enumerations rather than uniformly recursive enumerations; this is ensured by the Translation Theorem (showing translation of uniformly \(0''\)-recursive enumerations into uniformly recursive ones). The Translation Theorem is also used to show a modified version of Soare's Extension Theorem. In the proof of the Translation Theorem, the author follows the techniques used in his dissertation on automorphisms of the lattice of recursively enumerable sets; in particular in building a \(\Delta_ 3\)- branching tree. The author also mentions that Downey and Stob's results on hemimaximal sets and on Friedberg splittings of hyperhypersimple sets can also be recast in the format of the new proofs.
0 references
orbits in the lattice of recursively enumerable sets
0 references
maximal sets
0 references
hyperhypersimple sets
0 references
Translation Theorem
0 references
Soare's Extension Theorem
0 references