We study the classes of hypersimple and semicomputable sets as well as their intersection in the weak truth table degrees. We construct degrees that are not bounded by hypersimple degrees outside any non-trivial upper cone of Turing degrees and show that the hypersimple-free c.e. wtt degrees are downwards dense in the c.e. wtt degrees. We also show that there is no maximal (w.r.t. ≤wtt) hypersimple wtt degree. Moreover, we consider the sets that are both hypersimple (...) and semicomputable, characterize them as the (bi-infinite) c.e. cuts of computable orderings of ℕ of order type ω+ω* and study their wtt degrees. We show that there are hypersimple degrees that are not bounded by any hypersimple semicomputable degree, investigate relationships with the join and look for maximal and minimal elements of related classes. (shrink)

We show that in the c.e. weak truth table degrees if b < c then there is an a which contains no hypersimple set and b < a < c. We also show that for every w < c in the c.e. wtt degrees such that w is hypersimple, there is a hypersimple a such that w < a < c. On the other hand, we know that there are intervals which contain no hypersimple set.

Let be an infinite computable structure, and let R be an additional computable relation on its domain A. The syntactic notion of formal hypersimplicity of R on , first introduced and studied by Hird, is analogous to the computability-theoretic notion of hypersimplicity of R on A, given the definability of certain effective sequences of relations on A. Assuming that R is formally hypersimple on , we give general sufficient conditions for the existence of a computable isomorphic copy of on (...) whose domain the image of R is hypersimple and of arbitrary nonzero computably enumerable Turing degree. (shrink)

An incomplete degree is cuppable if it can be joined by an incomplete degree to a complete degree. For sets fulfilling some type of simplicity property one can now ask whether these sets are cuppable with respect to a certain type of reducibilities. Several such results are known. In this paper we settle all the remaining cases for the standard notions of simplicity and all the main strong reducibilities.

We extend the dichotomy between 1-basedness and supersimplicity proved in Shami :309–332, 2011). The generalization we get is to arbitrary language, with no restrictions on the topology [we do not demand type-definabilty of the open set in the definition of essential 1-basedness from Shami :309–332, 2011)]. We conclude that every hypersimple unidimensional theory that is not s-essentially 1-based by means of the forking topology is supersimple. We also obtain a strong version of the above dichotomy in the case where (...) the language is countable. (shrink)

Let μ be a universal lower enumerable semi-measure . Any computable upper bound for μ can be effectively separated from zero with a constant . Computable positive lower bounds for μ can be nontrivial and allow one to construct natural examples of hypersimple sets.

A well-known theorem by Martin asserts that the degrees of maximal sets are precisely the high recursively enumerable degrees, and the same is true with ‘maximal’ replaced by ‘dense simple’, ‘r-maximal’, ‘strongly hypersimple’ or ‘finitely strongly hypersimple’. Many other constructions can also be carried out in any given high r. e. degree, for instance r-maximal or hyperhypersimple sets without maximal supersets . In this paper questions of this type are considered systematically. Ultimately it is shown that every conjunction (...) of simplicity- and non-extensibility properties can be accomplished, unless it is ruled out by well-known, elementary results. Moreover, each construction can be carried out in any given high r. e. degree, as might be expected. For instance, every high r. e. degree contains a dense simple, strongly hypersimple set A which is contained neither in a hyperhypersimple nor in an r-maximal set. The paper also contains some auxiliary results, for instance: every r. e. set B can be transformed into an r. e. set A such that A has no dense simple superset, the transformation preserves simplicity- or non-extensibility properties as far as this is consistent with , and A [TRIPLE BOND]TB if B is high, and A ≥TB otherwise. Several proofs involve refinements of known constructions; relationships to earlier results are discussed in detail. (shrink)

We suggest some new ways to effectivize the definitions of several classes of simple sets. On this basis, new completeness criterions for simple sets are obtained. In particular, we give descriptions of the class of complete maximal sets.

We show: for every noncomputable c.e. incomplete c-degree, there exists a nonspeedable c-degree incomparable with it; The c-degree of a hypersimple set includes an infinite collection of \-degrees linearly ordered under \ with order type of the integers and consisting entirely of hypersimple sets; there exist two c.e. sets having no c.e. least upper bound in the \-reducibility ordering; the c.e. \-degrees are not dense.

We show that the _sQ_-degree of a hypersimple set includes an infinite collection of \(sQ_1\) -degrees linearly ordered under \(\le _{sQ_1}\) with order type of the integers and each c.e. set in these _sQ_-degrees is a hypersimple set. Also, we prove that there exist two c.e. sets having no least upper bound on the \(sQ_1\) -reducibility ordering. We show that the c.e. \(sQ_1\) -degrees are not dense and if _a_ is a c.e. \(sQ_1\) -degree such that \(o_{sQ_1}, then (...) there exist infinitely many pairwise _sQ_-incomputable c.e. _sQ_-degrees \(\{c_i\}_{i\in \omega }\) such that \((\forall \,i)\;(a. (shrink)

If α and β are ordinals, α ≤ β, and $\beta \nleq \alpha$ , then α + 1 ≤ β. The first result of this paper shows that the restriction of this statement to countable well orderings is provably equivalent to ACA 0 , a subsystem of second order arithmetic introduced by Friedman. The proof of the equivalence is reminiscent of Dekker's construction of a hypersimple set. An application of the theorem yields the equivalence of the set comprehension scheme (...) ACA 0 and an arithmetical transfinite induction scheme. (shrink)

We prove that each Σ 0 2 set which is hypersimple relative to $\emptyset$ ' is noncuppable in the structure of the Σ 0 2 enumeration degrees. This gives a connection between properties of Σ 0 2 sets under inclusion and and the Σ 0 2 enumeration degrees. We also prove that some low non-computably enumerable enumeration degree contains no set which is simple relative to $\emptyset$ '.