Mathematical Logic Quarterly 42 (1):241-248 (1996)

Authors
Valentina Harizanov
George Washington University
Abstract
R. Shore proved that every recursively enumerable set can be split into two nowhere simple sets. Splitting theorems play an important role in recursion theory since they provide information about the lattice ϵ 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 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* is effectively isomorphic to ϵ*, and that there is a nowhere simple set A such that L* is not effectively isomorphic to ϵ*. We prove that every nonzero r. e. Turing degree contains a noneffectively nowhere simple set A with the lattice L* effectively isomorphic to ϵ*
Keywords Recursively enumerable  Nowhere simple set  Effectively nowhere simple set  Splitting of r. e. sets
Categories (categorize this paper)
DOI 10.1002/malq.19960420121
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 57,199
Through your library

References found in this work BETA

Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
Splitting Theorems in Recursion Theory.Rod Downey & Michael Stob - 1993 - Annals of Pure and Applied Logic 65 (1):1-106.
Effectively Nowhere Simple Sets.D. Miller & J. B. Remmel - 1984 - Journal of Symbolic Logic 49 (1):129-136.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Analytics

Added to PP index
2013-11-03

Total views
25 ( #416,709 of 2,411,826 )

Recent downloads (6 months)
1 ( #538,761 of 2,411,826 )

How can I increase my downloads?

Downloads

My notes