We study the learnability of classes of computable structures under models that allow finitely many mind changes. Extending classical notions of explanatory learning from informant and from text, we introduce new paradigms where the information source and the convergence requirements are modified. In particular, we define Δ 2 0 -learning, where each atomic fact may be presented with finitely many errors before stabilizing, and c.e.- and d.c.e.-learning , where information is restricted to positive atomic facts that may either never be retracted (c.e.) or be retracted at most once (d.c.e.). We provide syntactic characterizations for these notions: Δ 2 0 -learning coincides with definability by finite existential sentences, and c.e.-learning coincides with TxtEx-learning. For d.c.e.-learning we give partial characterization in restricted languages. Furthermore, for n -learning from informant, where learners are allowed at most n mind changes, we establish a complete syntactic characterization in terms of specific infinitary formulas of bounded depth.

Abstract Working toward showing the decidability of the $\forall \exists $ -theory of the ${\Sigma ^0_2}$ -enumeration degrees, we prove that no so-called Ahmad pair of ${\Sigma ^0_2}$ -enumeration degrees can join to ${\mathbf 0}_e'$ .

Abstract The tower number ${\mathfrak t}$ and the ultrafilter number $\mathfrak {u}$ are cardinal characteristics from set theory. They are based on combinatorial properties of classes of subsets of $\omega $ and the almost inclusion relation $\subseteq ^*$ between such subsets. We consider analogs of these cardinal characteristics in computability theory. We say that a sequence $(G_n)_{n \in {\mathbb N}}$ of computable sets is a tower if $G_0 = {\mathbb N}$ , $G_{n+1} \subseteq ^* G_n$ , and $G_n\smallsetminus G_{n+1}$ is infinite for each n. A tower is maximal if there is no infinite computable set contained in all $G_n$ . A tower ${\left \langle {G_n}\right \rangle }_{n\in \omega }$ is an ultrafilter base if for each computable R, there is n such that $G_n \subseteq ^* R$ or $G_n \subseteq ^* \overline R$ ; this property implies maximality of the tower. A sequence $(G_n)_{n \in {\mathbb N}}$ of sets can be encoded as the “columns” of a set $G\subseteq \mathbb N$ . Our analogs of ${\mathfrak t}$ and ${\mathfrak u}$ are the mass problems of sets encoding maximal towers, and of sets encoding towers that are ultrafilter bases, respectively. The relative position of a cardinal characteristic broadly corresponds to the relative computational complexity of the mass problem. We use Medvedev reducibility to formalize relative computational complexity, and thus to compare such mass problems to known ones. We show that the mass problem of ultrafilter bases is equivalent to the mass problem of computing a function that dominates all computable functions, and hence, by Martin’s characterization, it captures highness. On the other hand, the mass problem for maximal towers is below the mass problem of computing a non-low set. We also show that some, but not all, noncomputable low sets compute maximal towers: Every noncomputable (low) c.e. set computes a maximal tower but no 1-generic $\Delta ^0_2$ -set does so. We finally consider the mass problems of maximal almost disjoint, and of maximal independent families. We show that they are Medvedev equivalent to maximal towers, and to ultrafilter bases, respectively.

Abstract We generalize the analysis of Andrews, Schweber and Sorbi of the first-order theory of the partial order of degrees of c.e. equivalence relations to higher computability theory, specifically to the setting of a regular cardinal.

Abstract We characterize the linear order types $\tau $ with the property that given any countable linear order $\mathcal {L}$ , $\tau \cdot \mathcal {L}$ is a computable linear order iff $\mathcal {L}$ is a computable linear order, as exactly the finite nonempty order types.

Abstract We study Turing degrees a for which there is a countable structure ${\cal A}$ whose degree spectrum is the collection {x : x ≰ a}. In particular, for degrees a from the interval [0′, 0″], such a structure exists if a′ = 0″, and there are no such structures if a″ > 0‴.

Abstract We study the computable structure theory of linear orders of size $\aleph _1 $ within the framework of admissible computability theory. In particular, we characterize which of these linear orders are computably categorical.

Abstract We study the computable structure theory of linear orders of size $\aleph _1 $ within the framework of admissible computability theory. In particular, we study degree spectra and the successor relation.

Abstract We study computably enumerable equivalence relations (ceers), under the reducibility $R \le S$ if there exists a computable function f such that $x\,R\,y$ if and only if $f\left( x \right)\,\,S\,f\left( y \right)$ , for every $x,y$ . We show that the degrees of ceers under the equivalence relation generated by $\le$ form a bounded poset that is neither a lower semilattice, nor an upper semilattice, and its first-order theory is undecidable. We then study the universal ceers. We show that 1) the uniformly effectively inseparable ceers are universal, but there are effectively inseparable ceers that are not universal; 2) a ceer R is universal if and only if $R\prime \le R$ , where $R\prime$ denotes the halting jump operator introduced by Gao and Gerdes (answering an open question of Gao and Gerdes); and 3) both the index set of the universal ceers and the index set of the uniformly effectively inseparable ceers are ${\rm{\Sigma }}_3^0$ -complete (the former answering an open question of Gao and Gerdes).

Abstract We prove that the degree structures of the d.c.e. and the 3-c.e. Turing degrees are not elementarily equivalent, thus refuting a conjecture of Downey. More specifically, we show that the following statement fails in the former but holds in the latter structure: There are degreesf>e>d>0such that any degreeu≤fis either comparable with botheandd, or incomparable with both.

Abstract Khutoretskii's Theorem states that the Rogers semilattice of any family of c.e. sets has either at most one or infinitely many elements. A lemma in the inductive step of the proof shows that no Rogers semilattice can be partitioned into a principal ideal and a principal filter. We show that such a partitioning is possible for some family of d.c.e. sets. In fact, we construct a family of c.e. sets which, when viewed as a family of d.c.e. sets, has (up to equivalence) exactly two computable Friedberg numberings μ and ν, and μ reduces to any computable numbering not equivalent to ν. The question of whether the full statement of Khutoretskii's Theorem fails for families of d.c.e. sets remains open.

Abstract We solve a longstanding question of Rosenstein, and make progress toward solving a long-standing open problem in the area of computable linear orderings by showing that every computableη-like linear ordering without an infinite stronglyη-like interval has a computable copy without nontrivial computable self-embedding. The precise characterization of those computable linear orderings which have computable copies without nontrivial computable self-embedding remains open.

Abstract Hirschfeldt and Shore have introduced a notion of stability for infinite posets. We define an arguably more natural notion called weak stability, and we study the existence of infinite computable or low chains or antichains, and of infinite chains and antichains, in infinite computable stable and weakly stable posets. For example, we extend a result of Hirschfeldt and Shore to show that every infinite computable weakly stable poset contains either an infinite low chain or an infinite computable antichain. Our hardest result is that there is an infinite computable weakly stable poset with no infinite chains or antichains. On the other hand, it is easily seen that every infinite computable stable poset contains an infinite computable chain or an infinite antichain. In Reverse Mathematics, we show that SCAC, the principle that every infinite stable poset contains an infinite chain or antichain, is equivalent over RCA0 to WSAC, the corresponding principle for weakly stable posets.

Abstract We characterize the structure of computably categorical trees of finite height, and prove that our criterion is both necessary and sufficient. Intuitively, the characterization is easiest to express in terms of isomorphisms of (possibly infinite) trees, but in fact it is equivalent to a -condition. We show that all trees which are not computably categorical have computable dimension ω. Finally, we prove that for every n ≥ 1 in ω, there exists a computable tree of finite height which is Σ30-categorical but not Δn3-categorical

Abstract. In Reverse Mathematics, the axiom system DNR. asserting the existence of diagonally non-recursive functions, is strictly weaker than WWKL0 (weak weak König's Lemma).

A computably enumerable Turing degree a is called contiguous iff it contains only a single computably enumerable weak truth table degree (Ladner and Sasso [2]). In [1], the authors proved that a nonzero computably enumerable degree a is contiguous iff it is locally distributive, that is, for all a1, a2, c with a1 ∪a2 = a and c ≤ a, there exist ci, ≤ ai with c1 ∪ c2 = c. To do this we supposed that W was a computably enumerable set and ∪ a computably set with a Turing functional Φ such that ΦW = U. Then we constructed computably enumerable sets A0, A1 and B together with functionals Γ0, Γ1, Γ, and Δ so that and so as to satisfy all the requirements below. That is, we built a degree-theoretical splitting A0, A1 of W and a set B ≤TW such that if we cannot beat all possible degree-theoretical splittings V0, V1 of B then we were able to witness the fact that U ≤WW (via Λ). After the proof it was observed that the set U of the proof (page 1222, paragraph 4) needed only to be Δ20. It was then claimed that a consequence to the proof was that every contiguous computably enumerable degree was, in fact, strongly contiguous, in the sense that all (not necessarily computably enumerable) sets of the degree had the same weak truth table degree.

Abstract We show that every finite lattice is embeddable into the Σ20 enumeration degrees via a lattice-theoretic embedding which preserves 0 and 1.

Abstract We construct the set of the title, answering a question of Cholak, Jockusch. and Slaman [1], and discuss its connections with the study of the proof-theoretic strength and effective content of versions of Ramsey's Theorem. In particular, our result implies that every ω-model of must contain a nonlow set.

Abstract We construct a degree which fails to be computably enumerable in any computably enumerable set strictly below .

Abstract We prove that a (recursively) enumerable degree is contiguous iff it is locally distributive. This settles a twenty-year old question going back to Ladner and Sasso. We also prove that strong contiguity and contiguity coincide, settling a question of the first author, and prove that no m-topped degree is contiguous, settling a question of the first author and Carl Jockusch [11]. Finally, we prove some results concerning local distributivity and relativized weak truth table reducibility.

We provide three new results about interpolating 2-r.e. (i.e. d-r.e.) or 2-REA (recursively enumerable in and above) degrees between given r.e. degrees: Proposition 1.13. If c < h are r.e., c is low and h is high, then there is an a < h which is REA in c but not r.e. Theorem 2.1. For all high r.e. degrees h < g there is a properly d-r.e. degree a such that h < a < g and a is r.e. in h. Theorem 3.1. There is an incomplete nonrecursive r.e. A such that every set REA in A and recursive in 0′ is of r. e. degree. The first proof is a variation on the construction of Soare and Stob (1982). The second combines highness with a modified version of the proof strategy of Cooper et al. (1989). The third theorem is a rather surprising result with a somewhat unusual proof strategy. Its proof is a 0‴ argument that at times moves left in the tree so that the accessible nodes are not linearly ordered at each stage. Thus the construction lacks a true path in the usual sense. Two substitute notions fill this role: The true nodes are the leftmost ones accessible infinitely often; the semitrue nodes are the leftmost ones such that there are infinitely many stages at which some extension is accessible. Another unusual feature of the construction is that it involves using distinct priority orderings to control the interactions of different parts of the construction.

Abstract 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 thepmdegrees require no new complexity-theoretic results. The fact that thepm-degrees of the recursive sets have a decidable two-quantifier theory answers a question raised by Shore and Slaman in [21].

Abstract We show that the Π4-theory of the partial order of recursively enumerable weak truth-table degrees is undecidable, and give a new proof of the similar fact for r.e. T-degrees. This is accomplished by introducing a new coding scheme which consists in defining the class of finite bipartite graphs with parameters.

Abstract We show the decidability of the existential theory of the recursively enumerable degrees in the language of Turing reducibility, Turing reducibility of the Turing jumps, and least and greatest element.

Abstract Work in the setting of the recursively enumerable sets and their Turing degrees. A set X is low if X′, its Turing jump, is recursive in ∅′ and high if X′ computes ∅″. Attempting to find a property between being low and being recursive, Bickford and Mills produced the following definition. W is deep, if for each recursively enumerable set A, the jump of A ⊕ W is recursive in the jump of A. We prove that there are no deep degrees other than the recursive one. Given a set W, we enumerate a set A and approximate its jump. The construction of A is governed by strategies, indexed by the Turing functionals Φ. Simplifying the situation, a typical strategy converts a failure to recursively compute W into a constraint on the enumeration of A, so that (W ⊕ A)′ is forced to disagree with Φ(−;A′). The conversion has some ambiguity; in particular, A cannot be found uniformly from W. We also show that there is a “moderately” deep degree: There is a low nonzero degree whose join with any other low degree is not high.

Abstract An r.e. degree a ≠ 0, 0′ is called strongly noncappable if it has no inf with any incomparable r.e. degree. We show the existence of a high strongly noncappable degree.