✦ LIBER ✦
Orbits of computably enumerable sets: low sets can avoid an upper cone
✍ Scribed by Russell Miller
- Publisher
- Elsevier Science
- Year
- 2002
- Tongue
- English
- Weight
- 222 KB
- Volume
- 118
- Category
- Article
- ISSN
- 0168-0072
No coin nor oath required. For personal study only.
✦ Synopsis
We investigate the orbit of a low computably enumerable (c.e.) set under automorphisms of the partial order E of c.e. sets under inclusion. Given an arbitrary low c.e. set A and an arbitrary noncomputable c.e. set C, we use the New Extension Theorem of Soare to construct an automorphism of E mapping A to a set B such that C T B. Thus, the orbit in E of the low set A cannot be contained in the upper cone above C. This complements a result of Harrington, who showed that the orbit of a noncomputable c.e. set cannot be contained in the lower cone below any incomplete c.e. set.