Switch to: References

Citations of:

Π01-classes and Rado's selection principle

C. G. Jockusch, A. Lewis & J. B. Remmel

Journal of Symbolic Logic 56 (2):684 - 693 (1991)

Add citations

You must login to add citations.

The complexity of recursive constraint satisfaction problems.Victor W. Marek & Jeffrey B. Remmel - 2010 - Annals of Pure and Applied Logic 161 (3):447-457.details We investigate the complexity of finding solutions to infinite recursive constraint satisfaction problems. We show that, in general, the problem of finding a solution to an infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through a recursive tree. We also identify natural classes of infinite recursive constraint satisfaction problems where the problem of finding a solution to the infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through (...) Download Export citation Bookmark
(1 other version)Index sets for< i> Π_< sup> 0< sub> 1 classes.Douglas Cenzer & Jeffrey Remmel - 1998 - Annals of Pure and Applied Logic 93 (1):3-61.details Download Export citation Bookmark
(1 other version)Index sets for Π01 classes.Douglas Cenzer & Jeffrey Remmel - 1998 - Annals of Pure and Applied Logic 93 (1-3):3-61.details A Π01 class is an effectively closed set of reals. We study properties of these classes determined by cardinality, measure and category as well as by the complexity of the members of a class P. Given an effective enumeration {Pe:e < ω} of the Π01 classes, the index set I for a certain property is the set of indices e such that Pe has the property. For example, the index set of binary Π01 classes of positive measure is Σ02 complete. (...) Download Export citation Bookmark 7 citations
Index sets for ω‐languages.Douglas Czenzer & Jeffrey B. Remmel - 2003 - Mathematical Logic Quarterly 49 (1):22-33.details An ω-language is a set of infinite sequences on a countable language, and corresponds to a set of real numbers in a natural way. Languages may be described by logical formulas in the arithmetical hierarchy and also may be described as the set of words accepted by some type of automata or Turing machine. Certain families of languages, such as the equation image languages, may enumerated as P0, P1, … and then an index set associated to a given property R (...) Download Export citation Bookmark 1 citation
On degree-preserving homeomorphisms between trees in computable topology.Iraj Kalantari & Larry Welch - 2008 - Archive for Mathematical Logic 46 (7-8):679-693.details In this paper we first give a variant of a theorem of Jockusch–Lewis– Remmel on existence of a computable, degree-preserving homeomorphism between a bounded strong ${\Pi^0_2}$ class and a bounded ${\Pi^0_1}$ class in 2 ω . Namely, we show that for mathematically common and interesting topological spaces, such as computably presented ${\mathbb{R}^n}$ , we can obtain a similar result where the homeomorphism is in fact the identity mapping. Second, we apply this finding to give a new, priority-free proof of existence (...) Download Export citation Bookmark
On notions of computability-theoretic reduction between Π21 principles.Denis R. Hirschfeldt & Carl G. Jockusch - 2016 - Journal of Mathematical Logic 16 (1):1650002.details Several notions of computability-theoretic reducibility between [Formula: see text] principles have been studied. This paper contributes to the program of analyzing the behavior of versions of Ramsey’s Theorem and related principles under these notions. Among other results, we show that for each [Formula: see text], there is an instance of RT[Formula: see text] all of whose solutions have PA degree over [Formula: see text] and use this to show that König’s Lemma lies strictly between RT[Formula: see text] and RT[Formula: see (...) Download Export citation Bookmark 9 citations
A blend of methods of recursion theory and topology: A Π1 0 tree of shadow points. [REVIEW]Iraj Kalantari & Larry Welch - 2004 - Archive for Mathematical Logic 43 (8):991-1008.details This paper is a sequel to our [7]. In that paper we constructed a Π1 0 tree of avoidable points. Here we construct a Π1 0 tree of shadow points. This tree is a tree of sharp filters, where a sharp filter is a nested sequence of basic open sets converging to a point. In the construction we assign to each basic open set on the tree an address in 2<ω. One interesting fact is that while our Π1 0 tree (...) Download Export citation Bookmark 1 citation

1