𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Effectively and Noneffectively Nowhere Simple Sets

✍ Scribed by Valentina S. Harizanov


Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
445 KB
Volume
42
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis


R. Shore proved that every recursively enumerable (r. e.) set can be split into two (disjoint) nowhere simple sets. Splitting theorems play an important role in recursion theory since they provide information about the lattice E of all r. e. sets. Nowhere simple sets were further studied by D. Miller and J. Remmel, and we generalize some of their results. We characterize r.e. sets which can be split into two (non)effectively nowhere simple sets, and r.e. sets which can be split into two r.e. non-nowhere simple sets. We show that every r. e. set is either the disjoint union of two effectively nowhere simple sets or two noneffectively nowhere simple sets. We characterize r. e. sets whose every nontrivial splitting is into nowhere simple sets, and r. e. sets whose every nontrivial splitting is into effectively nowhere simple sets. R. Shore proved that for every effectively nowhere simple set A, the lattice L'(A) is effectively isomorphic to E', and that there is a nowhere simple set A such that L*(A) is not effectively isomorphic to E'. We prove that every nonzero r. e. Turing degree contains a noneffectively nowhere simple set A with the lattice L'(A) effectively isomorphic to E' . M a t h e m a t i c s Subject Classification: 03D25, 03D10.


πŸ“œ SIMILAR VOLUMES