Movatterモバイル変換

Direct download(2 more)   Export citation   Bookmark   12 citations  

Direct download(3 more)   Export citation   Bookmark   11 citations  

We show that the partial order of Σ0 3-sets under inclusion is elementarily definable with parameters in the semilattice of r.e. wtt-degrees. Using a result of E. Herrmann, we can deduce that this semilattice has an undecidable theory, thereby solving an open problem of P. Odifreddi.

Direct download(8 more)   Export citation   Bookmark   9 citations  

Ambos-Spies, K. and R.A. Shore, Undecidability and 1-types in the recursively enumerable degrees, Annals of Pure and Applied Logic 63 3–37. We show that the theory of the partial ordering of recursively enumerable Turing degrees is undecidable and has uncountably many 1-types. In contrast to the original proof of the former which used a very complicated O''' argument our proof proceeds by a much simpler infinite injury argument. Moreover, it combines with the permitting technique to get similar results for any (...) ideal of the r.e. degrees. (shrink)

Direct download(4 more)   Export citation   Bookmark   9 citations  

A recursively enumerable splitting of an r.e. setAis a pair of r.e. setsBandCsuch thatA=B∪CandB∩C= ⊘. Since for such a splitting degA= degB∪ degC, r.e. splittings proved to be a quite useful notion for investigations into the structure of the r.e. degrees. Important splitting theorems, like Sacks splitting [S1], Robinson splitting [R1] and Lachlan splitting [L3], use r.e. splittings.Since each r.e. splitting of a set induces a splitting of its degree, it is natural to study the relation between the degrees of (...) r.e. splittings and the degree splittings of a set. We say a setAhas thestrong universal splitting property if each splitting of its degree is represented by an r.e. splitting of itself, i.e., if for degA=b∪cthere is an r.e. splittingB, CofAsuch that degB=band degC=c. The goal of this paper is the study of this splitting property.In the literature some weaker splitting properties have been studied as well as splitting properties which imply failure of the SUSP. (shrink)

Direct download(8 more)   Export citation   Bookmark   7 citations  

We prove that every Turing degree a bounding some non-GL₂ degree is recursively enumerable in and above (r.e.a.) some 1-generic degree.

Direct download(5 more)   Export citation   Bookmark   5 citations  

It is shown that, if a, b are recursively enumerable degrees such that 0

In Reverse Mathematics, the axiom system DNR, asserting the existence of diagonally non-recursive functions, is strictly weaker than WWKL0.

Direct download(5 more)   Export citation   Bookmark   6 citations  

Direct download(7 more)   Export citation   Bookmark   4 citations  

Downey and Lempp 1215–1240) have shown that the contiguous computably enumerable degrees, i.e. the c.e. Turing degrees containing only one c.e. weak truth-table degree, can be characterized by a local distributivity property. Here we extend their result by showing that a c.e. degree a is noncontiguous if and only if there is an embedding of the nonmodular 5-element lattice N5 into the c.e. degrees which maps the top to the degree a. In particular, this shows that local nondistributivity coincides with (...) local nonmodularity in the computably enumerable degrees. (shrink)

Direct download(4 more)   Export citation   Bookmark   4 citations  

We give a decision procedure for the ∀∃-theory of the weak truth-table (wtt) degrees of the recursively enumerable sets. The key to this decision procedure is a characterization of the finite lattices which can be embedded into the r.e. wtt-degrees by a map which preserves the least and greatest elements: a finite lattice has such an embedding if and only if it is distributive and the ideal generated by its cappable elements and the filter generated by its cuppable elements are (...) disjoint. We formulate general criteria that allow one to conclude that a distributive upper semi-lattice has a decidable two-quantifier theory. These criteria are applied not only to the weak truth-table degrees of the recursively enumerable sets but also to various substructures of the polynomial many-one (pm) degrees of the recursive sets. These applications to the pm degrees require no new complexity-theoretic results. The fact that the pm-degrees of the recursive sets have a decidable two-quantifier theory answers a question raised by Shore and Slaman in [21]. (shrink)

Direct download(10 more)   Export citation   Bookmark   3 citations  

We give a simple structural property which characterizes the r.e. sets whose (Turing) degrees are cappable. Since cappable degrees are incomplete, this may be viewed as a solution of Post's program, which asks for a simple structural property of nonrecursive r.e. sets which ensures incompleteness.

Direct download(3 more)   Export citation   Bookmark   3 citations  

We explore the complexity of Sacks’ Splitting Theorem in terms of the mind change functions associated with the members of the splits. We prove that, for any c.e. set A, there are low computably enumerable sets $A_0\sqcup A_1=A$ splitting A with $A_0$ and $A_1$ both totally $\omega ^2$ -c.a. in terms of the Downey–Greenberg hierarchy, and this result cannot be improved to totally $\omega $ -c.a. as shown in [9]. We also show that if cone avoidance is added then there (...) is no level below $\varepsilon _0$ which can be used to characterize the complexity of $A_1$ and $A_2$. (shrink)

Direct download(2 more)   Export citation   Bookmark  

Export citation   Bookmark   1 citation  

Direct download(3 more)   Export citation   Bookmark  

Direct download   Export citation   Bookmark   1 citation  

We solve a longstanding question of Soare by showing that if ${\mathbf d}$ is a non-low $_2$ computably enumerable degree then ${\mathbf d}$ contains a c.e. set with no r-maximal c.e. superset.

Direct download(2 more)   Export citation   Bookmark  

Direct download   Export citation   Bookmark  

Direct download(3 more)   Export citation   Bookmark   1 citation  

Direct download(3 more)   Export citation   Bookmark  

No categories

Direct download(2 more)   Export citation   Bookmark  

We show that, in the partial ordering of the computably enumerable computable Lipschitz degrees, there is a degree a>0a>0 such that the class of the degrees which do not cup to a is not bounded by any degree less than a. Since Ambos-Spies [1] has shown that, in the partial ordering of the c.e. identity-bounded Turing degrees, for any degree a>0a>0 the degrees which do not cup to a are bounded by the 1-shift a+1a+1 of a where a+1 (...) that the elementary theories of the partial orderings and differ. (shrink)

Direct download(4 more)   Export citation   Bookmark  

We show that the theory of the partial ordering of the computably enumerable degrees in any given nontrivial interval is undecidable and has uncountably many 1-types.

Direct download(4 more)   Export citation   Bookmark   1 citation