Mathematical Preprints by Steffen Lempp

(The preprints are listed by research area, within research area in alphabetical order of coauthor(s). Some browsers may not represent the Greek letters and mathematical symbols correctly.)

Research Areas

Classical Computability Theory

Computably enumerable degrees

Lattice embeddings into the c.e. degrees

Abstract: We show that a finite distributive lattice can be embedded into the r. e. degrees preserving least and greatest element iff the lattice contains a join-irreducible noncappable element.
Abstract: We show that the two nondistributive five-element lattices, M5 and N5, can be embedded into the r. e. degrees preserving the greatest element.
Abstract: We exhibit a finite lattice without critical triple that cannot be embedded into the enumerable Turing degrees, and outline a proposed characterization of the finite lattices embeddable into the enumerable Turing degrees.
Abstract: We survey the current status of an old open question in classical computability theory: Which finite lattices can be embedded into the degree structure of the computably enumerable degrees? Does the collection of embeddable finite lattices even form a computable set?

Two recent papers by the second author show that for a large subclass of the finite lattices, the so-called join-semidistributive lattices (or lattices without so-called "critical triple"), the collection of embeddable lattices forms a Π02-set.

This paper surveys recent joint work by the authors, concentrating on restricting the number of meets by considering "quasilattices", i.e., finite upper semilattices in which only some meets of incomparable elements are specified. In particular, we note that all finite quasilattices with one meet specified are embeddable; and that the class of embeddable finite quasilattices with two meets specified, while nontrivial, forms a computable set. On the other hand, more sophisticated techniques may be necessary for finite quasilattices with three meets specified.

Decidability of fragments of theories of the c.e. degrees

Abstract: We survey some recent work on the (recursively) enumerable Turing degrees, with particular emphasis on work relating to decidability and undecidability.
Abstract: We give a decision procedure for the AE-theory of the weak truth-table (wtt) degrees of the recursively enumerable sets. The key for 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 the ideal generated by its cappable elements and the filter generated by its cuppable elements are disjoint.
Abstract: We show that the existential theory of the recursively enumerable degrees in the language L containing predicates for order and n-jump comparability for all n, and constant symbols for least and greatest elements, is decidable. The decidability follows from our main theorem, where we show that any finite L-structure which is consistent with the order relation, the order-preserving property of the jump operator, and the property of the jump operator that the jump of an element is strictly greater than the element, can be embedded into the r. e. degrees.
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: 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 undecidability of the Π3-theory of the partial order of enumerable Turing degrees.

Other work on the c.e. degrees

Abstract: An r. e. degree a (not equal to 0 or 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.
Abstract: We give an example of a subset of the recursively enumerable Turing degrees which generates the recursively enumerable degrees using meet and join but does not generate them using join alone.
Abstract: Combinatorial operations on sets are almost never well-defined on Turing degrees, a fact so obvious that counterexamples are worth exhibiting. The case we focus on is the symmetric difference operator; there are pairs of (nonzero) degrees for which the symmetric difference operation is well-defined. Some examples can be extracted from the literature, for example, from the existence of nonzero degrees with strong minimal covers. We focus on the case of incomparable r.e. degrees for which the symmetric difference operation is well-defined.
Abstract: We show that there is a strong minimal pair in the computably enumerable Turing degrees, i.e., a pair of nonzero c.e. degrees a and b such that a ∩ b = 0 and for any nonzero c.e. degree xa, b ∪ xa.
Abstract: We show that for every nontrivial r. e. wtt-degree a, there are r. e. wtt-degrees b and c incomparable to a such that the infimum of a and b exists but the infimum of a and c fails to exist. This shows in particular that there are no strongly noncappable r. e. wtt-degrees, in contrast to the situation in the r. e. Turing degrees.
Abstract: Answering a question of Per Lindström, we show that there is no "plus-capping" degree, i.e., that for any incomplete r. e. degree w, there is an incomplete r. e. degree a > w such that there is no r. e. degree v > w with a cap v = w.
Abstract: We prove that a (recursively) enumerable degree is contiguous iff it is locally distributive. We also prove that no m-topped degree is contiguous. Finally, we prove some results concerning local distributivity and relativized weak truth table reducibility.
Abstract: We explore the limits on r. e. degrees bounding minimal pairs. On the one hand, we show that there is a high r. e. degree such that any r. e. degree below it is the top of a minimal pair. On the other hand, there is a high2 r. e. degree not bounding any minimal pair. We conclude with another application of our high2 technique.
Abstract: An r. e. degree w > 0 is called deep if for all r. e. degrees a, (w ∪ a)' = a'. We prove that no such degree exists. We also show a weak converse of this.
Abstract: We show that the top of any diamond with bottom 0 in the r. e. degrees is also the top of a stack of n diamonds with bottom 0.

Computably enumerable sets

Abstract: We define a family of properties on hyperhypersimple sets and show that they yield index sets at each level of the hyperarithmetical hierarchy. An extension yields a Π11-complete index set. We also classify the index set of quasimaximal sets, of coinfinite r. e. sets not having an atomless superset, and of r. e. sets major in a fixed nonrecursive r. e. set.
Abstract: In an infinite injury construction, we construct a nonrecursive recursively enumerable set A such that whenever A is split into nonrecursive r. e. sets A0 and A1 then the jumps of both A0 and A1 are strictly below the jump of A.
Abstract: The tower number t and the ultrafilter number u are cardinal characteristics from set theory, They are based on combinatorial properties of classes of subsets of ω and the almost inclusion relation ⊆* between such subsets. We consider analogs of these cardinal characteristics in computability theory.

We say that a sequence ⟨Gnn ∈ ω of computable sets is a tower if G0 = ω, Gn+1* Gn, and Gn - Gn+1 is infinite for each n. A tower is maximal if there is no infinite computable set contained in all Gn. A tower ⟨Gnn ∈ ω is an ultrafilter base if for each computable R, there is n such that Gn* R or Gn* R; this property implies maximality of the tower. A sequence ⟨Gnn ∈ ω of sets can be encoded as the "columns" of a set G ⊆ ω. Our analogs of t and 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 Δ02-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 study the filter L*(A) of computably enumerable supersets (modulo finite sets) of an r-maximal set A and show that, for some such set A, the property of being cofinite in L*(A) is still Σ03-complete. This implies that for this A, there is no uniformly computably enumerable "tower" of sets exhausting exactly the coinfinite sets in L*(A).

D.c.e. and n-c.e. set and degrees

Abstract: In this paper, we show that the so-called "double bubbles" are not downward dense in the d.c.e. degrees. Here, a pair of d.c.e. degrees d1 > d2 > 0 forms a double bubble if all d.c.e. degrees below d1 are comparable with d2.
Abstract: This paper gives a brief survey of work on the d.c.e. and n-c.e. degrees done over the past fifty years, with particular emphasis on work done by or in collaboration with the Kazan logic group founded and headed by Arslanov.
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 degrees f > e > d > 0 such that any degree u < f is either comparable with both e and d, or incomparable with both.
Abstract: This paper investigates the connection between r. e. degrees and degrees REA in an r. e. degree. Specifically, we show that a theorem of Soare and Stob cannot be improved by proving that there is a nontrivial r. e. degree a such that any degree REA in a and below 0' must be r. e. We also show that this degree a can be neither high nor low.
Abstract: We show a variety of results on the distribution of r. e., d. r. e., and REA degrees: Nonisolated d. r. e. degrees can be found between any two comparable r. e. degrees. There is a nontrivial r. e. degree which isolates no d. r. e. degree, and such a degree can be found below any nonzero r. e. degree and in any jump class. On the other hand, between any two comparable r. e. degrees we can find a d. r. e. degree not r. e. in the lesser one.
Abstract: By constructing a maximal incomplete d. r. e. degree, the nondensity of the partial order of the d. r. e. degrees is established. An easy modification yields the nondensity of the n-r. e. degrees (n > 2) and of the ω-r. e. degrees.
Abstract: We show that there is a properly d. r. e. degree between any two comparable r. e. degrees, and that given a high r. e. degree h, every nonrecursive d. r. e. degree < h cups to h by a low d. r. e. degree.
Abstract: We prove that every finite distributive lattice is isomorphic to a final segment of the d.c.e. Turing degrees (i.e., the degrees of differences of computably enumerable sets). As a corollary, we are able to infer the undecidability of the ∃∀∃-theory of the d.c.e. degrees in the language of partial ordering.
Abstract: We consider the lower semilattice D of differences of c.e. sets under inclusion. It is shown that D is not distributive as a semilattice, and that the c.e. sets form a definable subclass.

Δ02-degrees and sets

Abstract: We construct the set of the title, answering a question of Cholak, Jockusch, and Slaman, and discuss its connections with the study of the proof-theoretic strength and effective content of versions of Ramsey's Theorem.
Abstract: We construct a Δ02 degree which fails to be computably enumerable in any computably enumerable set strictly below 0'.
Abstract: We show that there is a degree a REA in and low over 0' such that no minimal degree below 0' jumps to a degree above a. We also show that every nonlow r. e. degree bounds a nonlow minimal degree.

Enumeration degrees

Abstract: A set A ⊆ ω is cototal if it is enumeration reducible to its complement. The skip of A is the uniform upper bound of the complements of all sets enumeration reducible to A. These are closely connected: A has cototal degree if and only if it is enumeration reducible to its skip. We study cototality and related properties, using the skip operator as a tool in our investigation. We give many examples of classes of enumeration degrees that either guarantee or prohibit cototality. We also study the skip for its own sake, noting that it has many of the nice properties of the Turing jump, even though the skip of A is not always above A (i.e., not all degrees are cototal). In fact, there is a set that is its own double skip.
Abstract: We show that if A and B form a nontrivial K-pair, then there is a semi-computable set C such that Ae C and Be C. As a consequence, we obtain a definition of the total enumeration degrees: A nonzero enumeration degree is total if and only if it is the join of a nontrivial maximal K-pair. We also obtain a definition of the "c.e. in" relation of total degrees in the enumeration degrees.
Abstract: We study Kalimullin pairs, a definable class (of pairs) of enumeration degrees that has been used to give first-order definitions of other important classes and relations, including the enumeration jump and the total enumeration degrees. We show that the global definition of Kalimullin pairs is also valid in the local structure of the enumeration degrees, giving a simpler local definition than was previously known. We prove that the typical enumeration degree is not half of a nontrivial Kalimullin pair, both in the sense of category and measure. Using genericity, we show that not all members of nontrivial Kalimullin pairs are half of a maximal Kalimullin pair. Finally, we construct such a set that has no maximal Kalimullin partner, making it qualitatively different from half of a maximal Kalimullin pair.
Abstract: In her 1990 thesis, Ahmad showed that there is a so-called "Ahmad pair", i.e., there are incomparable Σ02-enumeration degrees a0 and a1 such that every enumeration degree x < a0 is ≤ a1. At the same time, she also showed that there is no "symmetric Ahmad pair", i.e., there are no incomparable Σ02-enumeration degrees a0 and a1 such that every enumeration degree x0 < a0 is ≤ a1 and such that every enumeration degree x1 < a1 is ≤ a0.

In this paper, we first present a direct proof of Ahmad's second result. We then show that her first result cannot be extended to an "Ahmad triple", i.e., there are no Σ02-enumeration degrees a0, a1 and a2 such that both (a0, a1) and (a1, a2) are an Ahmad pair. On the other hand, there is a "weak Ahmad triple", i.e., there are pairwise incomparable Σ02-enumeration degrees a0, a1 and a2 such that every enumeration degree x < a0 is also ≤ a1 or ≤a2; however, neither (a0, a1) nor (a0, a2) is an Ahmad pair.

Remark: The main result of this paper (the non-existence of an Ahmad triple) refutes a claim of mine from the early 2010's.

Abstract: Working toward showing the decidability of the ∀∃-theory of the Σ02enumeration degrees, we prove that no so-called Ahmad pair of Σ02-enumeration degrees can join to 0e'.
Abstract: We give an algorithm for deciding whether an embedding of a finite partial order P into the enumeration degrees of the Σ02-sets can always be extended to an embedding of a finite partial order Q extending P.
Abstract: We prove that every finite distributive lattice can be strongly embedded into the enumeration degrees as an interval, i.e., that there is an interval [a0, a1] of enumeration degrees isomorphic to the lattice, and any enumeration degree ba1 lies in this interval or below a0. As corollaries, we conclude that the ∃∀∃-theory of the enumeration degrees is undecidable, while the extension of embeddings problem (a subproblem of the ∀∃-theory) is decidable.
Remark: The undecidability result claimed in this paper actually already follows as an easy corollary for the same result for the Σ02-enumeration degrees proved by Kent in his Ph.D. thesis.
Abstract: We show that every finite lattice is embeddable into the Σ02-enumeration degrees via a lattice-theoretic embedding which preserves 0 and 1.

Weihrauch reducibility

Abstract: A partial order (P,≤) admits a jump operator if there is a map j: P → P that is strictly increasing and weakly monotone. Despite its name, the jump in the Weihrauch lattice fails to satisfy both of these properties: It is not degree-theoretic and there are functions f such that f ≡W f '. This raises the question: Is there a jump operator in the Weihrauch lattice? We answer this question positively and provide an explicit definition for an operator on partial multi-valued functions that, when lifted to the Weihrauch degrees, induces a jump operator. This new operator, called the totalizing jump, can be characterized in terms of the total continuation, a well-known operator on computational problems. The totalizing jump induces an injective endomorphism of the Weihrauch degrees. We study some algebraic properties of the totalizing jump and characterize its behavior on some pivotal problems in the Weihrauch lattice.
Abstract: In this paper, we study the existence of minimal covers and strong minimal covers in the Weihrauch degrees. We characterize when a problem f is a minimal cover or strong minimal cover of a problem h. We show that strong minimal covers only exist in the cone below id and that the Weihrauch lattice above id is dense. From this, we conclude that the degree of id is first-order definable in the Weihrauch degrees and that the first-order theory of the Weihrauch degrees is computably isomorphic to third-order arithmetic.

Theory of numberings and learning theory

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 establish a number of results on numberings, in particular on Friedberg numberings, of families of d.c.e. sets:
  1. There exists a Friedberg numbering of the family of all d.c.e. sets. We also show that this result, patterned on Friedberg's famous theorem for the family of all c.e. sets, holds for the family of all n-c.e. sets for any n > 2.
  2. There exists an infinite family of d.c.e. sets without a Friedberg numbering.
  3. There exists an infinite family of c.e. sets with a numbering (as a family of d.c.e. sets) which is unique up to equivalence.
  4. There exists a family of d.c.e. sets with a least numbering (under reducibility) such that this numbering is a Friedberg numbering but not the only numbering (modulo reducibility).
Abstract: This paper considers reductions between types of numberings; these reductions preserve the Rogers Semilattice of the numberings reduced and also preserve the number of minimal and positive degrees in their semilattice. It is shown how to use these reductions to simplify some constructions of specific semilattices. Furthermore, it is shown that for the basic types of numberings, one can reduce the left-r.e. numberings to the r.e. numberings and the k-r.e. numberings to the (k+1)-r.e. numberings; all further reductions are obtained by concatenating these reductions.

Computational complexity of equivalence relations

Abstract: We study computably enumerable equivalence relations (ceers) under the reducibility RS if there exists a computable function f such that, for every x and y, x R y if and only if f(x) S f(y). We show that the degrees of ceers under the equivalence relation generated by ≤ 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'R, where R' 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 Σ03-complete (the former answering an open question of Gao and Gerdes).
Abstract: We generalize the analysis of Andrews, Schweber and Sorbi of the first-order theory of the degrees of the c.e.\ equivalence relations to higher computability theory, specifically to the setting of an uncountable regular cardinal.
Abstract: Inspired by the very successful study of Borel equivalence relations under Borel reducibility in descriptive set theory and equivalence relations on ω under computable reducibility in computability theory, R. Miller defined a family of reducibility notions. Defined on equivalence relations on Baire space or Cantor space, these reducibilities are required to succeed (uniformly) on all finite or countable subsets of the whole space. In this paper, we combine methods from computability theory and descriptive set theory to study equivalence relations under these reductions. In particular, we show existence and non-existence results of complete equivalence relations in various settings.

Frameworks for priority arguments

Abstract: We present in informal fashion a new framework for priority arguments in computability theory. This framework was used in a theorem by the authors using a 0(n) priority argument for arbitrary n and is applicable and useful for all currently known priority arguments.
Abstract: We explain the use of iterated trees of strategies in priority arguments at the example of various classical priority arguments.
Abstract: A general framework for priority arguments in classical recursion theory, using iterated trees of strategies, is introduced and used to present new proofs of four fundamental theorems of recursion theory.
Abstract: We use the iterated trees of strategies approach developed by Lempp and Lerman to prove some theorems about minimal pairs, in particular that there is a minimal pair of r. e. degrees such that their jumps form a minimal pair above 0'.

Applied Computability Theory

Applications to and in model theory

Abstract: We study, for a fixed first-order theory T, which countable models of T can be presented effectively. We consider this question for the class of strongly minimal disintegrated theories, where the countable models can be characterized by their dimension. The spectrum of computable models of T is the subset S of ω+1 such that α ∈ S if and only if the α-th model of T can be effectively presented.

We examine the class of strongly minimal disintegrated theories in computable relational languages where each relation symbol defines a set of Morley rank at most 1. We characterize the spectra of computable models of such theories (exactly, with the exception of three sets) under the assumption of bounded arity on the language, and (with the exception of one specific set and one specific class of sets) without that assumption. We also determine the exactly seven possible spectra for strongly minimal theories in binary relational languages and show that there are at least nine but no more than eighteen spectra of disintegrated theories in ternary relational languages.

Abstract: We analyze the spectra of theories that are ω-stable, theories whose spectra include almost every degree, and theories with uniformly arithmetical n-quantifier fragments. We answer a question from Andrews and Miller by showing that there are ω-stable theories whose spectra are not structure spectra. We show that the spectrum created in Andrews and Knight is not the spectrum of an ω-stable theory, but is the minimal spectrum of any theory with uniformly arithmetical n-quantifier fragments. In addition, we give examples of theory spectra that contain almost every degree, including ones that are known not to be structure spectra.
Abstract: We investigate the descriptive complexity of the set of models of first-order theories. Using classical results of Knight and Solovay, we give a sharp condition for complete theories to have a Π0ω-complete set of models. We also give sharp conditions for theories to have a Π0n-complete set of models. Finally, we determine the Turing degrees needed to witness the completeness.
Abstract: What information does one need to know in order to build the models of a strongly minimal theory? To answer this question, we first formalize it in two ways. Note that if a theory T has a computable model, then T ∩ ∃n is uniformly Σ0n. We call such theories Solovay theories. A degree is strongly minimal computing if it computes a copy of every model of every strongly minimal Solovay theory. A second notion, introduced by Lempp in the mid-1990's, is that of a strongly minimal relatively computing degree. A degree d is strongly minimal relatively computing if whenever T is a strongly minimal theory with one computable model, d computes a copy of every model of T. We characterize both classes of degrees as exactly the degrees which are high over 0'', i.e., d0'' and d' ≥ 0(4).
Abstract: We study Turing degrees a for which there is a countable structure A whose degree spectrum is the collection {x : xa}. 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: What information does one need to know in order to build the models of a strongly minimal theory? To answer this question, we first formalize it in two ways. Note that if a theory T has a computable model, then T ∩ ∃n is uniformly Σ0n. We call such theories Solovay theories. A degree is strongly minimal computing if it computes a copy of every model of every strongly minimal Solovay theory. A second notion, introduced by Lempp in the mid-1990's, is that of a strongly minimal relatively computing degree. A degree d is strongly minimal relatively computing if whenever T is a strongly minimal theory with one computable model, d computes a copy of every model of T. We characterize both classes of degrees as exactly the degrees which are high over 0'', i.e., d0'' and d' ≥ 0(4).
Abstract: We study the notion of computable categoricity of computable structures, comparing it especially to the notion of relative computable categoricity and its relativizations. We show that every 1-decidable computably categorical structure is relatively Δ02-categorical. We study the complexity of various index sets associated with computable categoricity and relative computable categoricity. We also introduce and study a variation of relative computable categoricity, comparing it to both computable categoricity and relative computable categoricity and its relativizations.
Abstract: We show that the index set complexity of the computably categorical structures is Π11-complete, demonstrating that computable categoricity has no simple syntactic characterization. As a consequence of our proof, we exhibit, for every computable ordinal α, a computable structure that is computably categorical but not relatively Δ0α-categorical.
Abstract: We prove that if M is any model of a trivial, strongly minimal theory, then the elementary diagram Th(MM) is a model complete LM-theory. We conclude that all countable models of a trivial, strongly minimal theory with at least one computable model are 0''-decidable, and that the spectrum of computable models of any trivial, strongly minimal theory is Σ05.
Abstract: We construct a strongly minimal (and thus uncountably categorical) but not totally categorical theory in a finite language of binary predicates whose only constructive (or recursive) model is the prime model.
Abstract: We show the existence of a trivial, strongly minimal (and thus uncountably categorical) theory for which the prime model is computable and each of the other countable models computes 0''. This result shows that the result of Goncharov/Harizanov/Laskowski/Lempp/McCoy (2003) is best possible for trivial strongly minimal theories in terms of computable model theory and in terms of axiomatizability. We conclude with some remarks about axiomatizability.
Abstract: In this paper, we investigate the Lindenbaum algebra L(Tfin) of the theory Tfin = Th(Mfin) of the class Mfin of all finite models of a finite rich signature. We prove that this algebra is an atomic Boolean algebra while its Gödel numeration γ is a Π01-numeration. Moreover, the quotient algebra (L(Tfin)/F, γ/F) modulo the Fréchet ideal F is a Σ02-algebra, which is universal over the class of all Σ02-Boolean algebras. These conditions characterize uniquely the algebra L(Tfin); moreover, these conditions characterize up to recursive isomorphism the numerated Boolean quotient algebra (L(Tfin)/F, γ/F).

These results extend the work of Trakhtenbrot and Vaught on the first order theory of the class of all finite models of a finite rich signature.

Abstract: We classify the computability-theoretic complexity of two index sets of classes of first-order theories: We show that the property of being an א0-categorical theory is Π03-complete; and the property of being an Ehrenfeucht theory Π11-complete. We also show that the property of having continuum many models is Σ11-hard. Finally, as a corollary, we note that the properties of having only decidable models, and of having only computable models, are both Π11-complete.

Applications to proof theory

Abstract: We investigate the structure of the degrees of provability, which measure the proof-theoretic strength of statements asserting the totality of given computable functions. The degrees of provability can also be seen as an extension of the investigation of relative consistency statements for first-order arithmetic (which can be viewed as Π01-statements, whereas statements of totality of computable functions are Π02-statements); and the structure of the degrees of provability can be viewed as the Lindenbaum algebra of true Π02-statements in first-order arithmetic. Our work continues and greatly expands the second author's paper on this topic by answering a number of open questions from that paper, comparing three different notions of a jump operator and studying jump inversion as well as the corresponding high/low hierarchies, investigating the structure of true Π01-statements as a substructure, and connecting the degrees of provability to escape and domination properties of computable functions.

Applications to reverse mathematics

Abstract: Simpson and X. Yu introduced an axiom system WWKL0 and showed it to be strictly intermediate between RCA0 and WKL0 as well as equivalent to some statements on Lebesgue and Borel measure. WWKL0 was further studied by Giusto and Simpson; and by Brown, Giusto and Simpson. Giusto and Simpson found that a certain version of the Tietze extension theorem was provable in WKL0 and implied the DNR axiom. They pointed out that DNR is intermediate between RCA0 and WWKL0, but left open the question whether DNR coincides with WWKL0, i. e., has the same theorems as WWKL0. Simpson conjectured that DNR is strictly weaker than WWKL0.

In the current paper, we confirm Simpson's conjecture.

Abstract: We show that the principle PART from Hirschfeldt and Shore [2007] is equivalent to the Σ02-Bounding principle BΣ02 over RCA0, answering one of their open questions.

We also fill a gap in a proof in Cholak, Jockusch and Slaman [2001] by showing that D22 implies BΣ02 and is thus indeed equivalent to Stable Ramsey's Theorem for Pairs SRT22.

Furthermore, this also allows us to conclude that the combinatorial principles IPT, SPT and SIPT defined by Dzhafarov and Hirst [2009] all imply BΣ02, and thus that SPT and SIPT are both equivalent to SRT22 as well.

Our proof uses the notion of a bi-tame cut, the existence of which we show to be equivalent, over RCA0, to the failure of BΣ02.

Abstract: We study the reverse mathematics and computability-theoretic strength of (stable) Ramsey's Theorem for pairs and the related principles COH and DNR. We show that SRT22 implies DNR over RCA0 but COH does not, and answer a question of Mileti by showing that every computable stable 2-coloring of pairs has an incomplete Δ02 infinite homogeneous set. We also give some extensions of the latter result, and relate it to potential approaches to showing that SRT22 does not imply RT22.

Applications to, and reverse mathematics of, classical algebraic theories

Abstract: We determine the complexity of torsion-freeness of finitely presented groups in Kleene's arithmetical hierarchy as Π02-complete. This implies in particular that there is no effective listing of all torsion-free finitely presented groups, or of all non-torsion-free finitely presented groups.
Abstract: We show that the existence of a nontrivial proper subspace of a vector space of dimension greater than one (over an infinite field) is equivalent to WKL0 over RCA0, and that the existence of a finite-dimensional nontrivial proper subspace of such a vector space is equivalent to ACA0 over RCA0.
Abstract: The Nielsen-Schreier Theorem states that every subgroup of a free group is free. To formalize this theorem in weak subsystems of second order arithmetic, one has to choose between defining a subgroup in terms of a set of group elements and defining it in terms of a set of generators. We show that if subgroups are defined by sets, then the Nielsen-Schreier Theorem is provable in RCA0, while if subgroups are defined by generators, the theorem is equivalent to ACA0.
Abstract: We show that the existence of a nontrivial proper ideal in a commutative ring with identity which is not a field is equivalent to WKL0 over RCA0, and that the existence of a nontrivial proper finitely generated ideal in a commutative ring with identity which is not a field is equivalent to ACA0 over RCA0. We also prove that there are computable commutative rings with identity where the nilradical is Σ01-complete, and the Jacobson radical is Π02-complete, respectively.
Abstract: Let G be a computable ordered abelian group. We show that the computable dimension of G is either 1 or ω, that G is computably categorical if and only if it has finite rank, and that if G has only finitely many Archimedean classes, then G has a computable presentation which admits a computable basis.
Abstract: We establish that the computable isomorphism problem for the classes of nilpotent rings, distributive lattices, nilpotent groups, and nilpotent semigroups is Σ11-complete, which is as complicated as possible. The method we use is based on uniform effective interpretations of computable binary relations into computable structures from the corresponding algebraic classes.
Abstract: We compare Aut(Q), the classical automorphism group of a countable dense linear order, with Autc(Q), the group of all computable automorphisms of such an order. They have a number of similarities, including the facts that every element of each group is a commutator and each group has exactly three nontrivial normal subgroups. However, the standard proofs of these facts in Aut(Q) do not work for Autc(Q). Also, Aut(Q) has three fundamental properties which fail in Autc(Q): it is divisible, every element is a commutator of itself with some other element, and two elements are conjugate if and only if they have isomorphic orbital structures.

Applications to, and reverse mathematics of, linear and partial orders and trees

Abstract: We show that any Σ02-initial segment of a recursive linear order can be presented recursively.
Abstract: We show that the Dushnik-Miller Theorem for countable linear orderings (stating that any countable linear ordering has a nontrivial self-embedding) is equivalent (over recursive comprehension (RCA0)) to arithmetic comprehension (ACA0).
Abstract: Szpilrajn's Theorem states that any partial order P = (S, <P) has a linear extension L = (S, <L). This is a central result in the theory of partial orderings, allowing one to define, for instance, the dimension of a partial ordering. It is now natural to ask questions like "Does a well-partial ordering always have a well-ordered linear extension?" Variations of Szpilrajn's Theorem state, for various (but not for all) linear order types τ, that if P does not contain a subchain of order type τ, then we can choose L so that L also does not contain a subchain of order type τ. In particular, a well-partial ordering always has a well-ordered extension.

We show that several effective versions of variations of Szpilrajn's Theorem fail, and use this to narrow down their proof-theoretic strength in the spirit of reverse mathematics.

Abstract: We 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: We indicate how to fix an error in the proof of the main theorem of our original paper, pointed out to us by Maxim Zubkov. In correcting this error, we are now able to give a uniform proof for coding into the adjacency relation for a computable η-like linear ordering with infinitely many adjacencies. The proof is quite unusual in the construction of the isomorphism on the priority tree and uses some other unusual combinatorics as well.
Abstract: We characterize the linear order types τ with the property that given any countable linear order L, τ ⋅ L is a computable linear order iff L is a computable linear order, as exactly the finite nonempty order types.
Abstract: We study the computable structure theory of linear orders of size א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 א1 within the framework of admissible computability theory. In particular, we study degree spectra and the successor relation.
Abstract: We show that the order dimension of any locally countable partial ordering (P, <) of size κ+, for any κ of uncountable cofinality, is at most κ. In particular, this implies that it is consistent with ZFC that the dimension of the Turing degrees under partial ordering can be strictly less than the continuum.
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 Π01-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 Π01-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 Π01-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 WSCAC, 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 Σ03-condition. We show that all trees which are not computably categorical have computable dimension ω. Finally, we prove that for every n > 0 in ω, there exists a computable tree of finite height which is Δ0n+1-categorical but not Δ0n-categorical.
Abstract: We show the existence of a computable linear order without nontrivial 0'-computable self-embedding.
Remark: The proof of the main result of this paper contains a fatal error, which has been fixed by Downey, Jockusch, and J. Miller.
Abstract: We explore the problem of constructing maximal and unbounded filters on computable posets. We obtain both computability results and reverse mathematics results.

A maximal filter is one that does not extend to a larger filter. We show that every computable poset has a Δ02 maximal filter, and there is a computable poset with no Π01 or Σ01 maximal filter. There is a computable poset on which every maximal filter is Turing complete.We obtain the reverse mathematics result that the principle "every countable poset has a maximal filter" is equivalent to ACA0 over RCA0.

An unbounded filter is a filter which achieves each of its lower bounds in the poset. We show that every computable poset has a Σ01 unbounded filter, and there is a computable poset with no Π01 unbounded filter. We show that there is a computable poset on which every unbounded filter is Turing complete, and the principle "every countable poset has an unbounded filter" is equivalent to ACA0 over RCA0. We obtain additional reverse mathematics results related to extending arbitrary filters to unbounded filters and forming the upward closures of subsets of computable posets.

Applications to Boolean algebras, lattices and universal algebra

Abstract: A finite lattice L is interval dismantlable if it can be partitioned into an ideal and a filter, each of which can be partitioned into an ideal and a filter, etc., until you reach 1-element lattices. In this note, we find a quasi-equational basis for the pseudoquasivariety of interval dismantlable lattices, and show that there are infinitely many minimal interval non-dismantlable lattices.
Abstract: We study the set of depths of subalgebras of countable Boolean algebras, in particular the extent to which this set may not be downward closed within the countable ordinals for a fixed countable Boolean algebra. Doing so, we exhibit a structural difference between the class of arbitrary rank countable Boolean algebras and the class of rank one countable Boolean algebras.
Abstract: Computably enumerable algebras are the ones whose positive atomic diagrams are computably enumerable. Computable algebras are the ones whose atomic diagrams are computable. In this paper we investigate computably enumerable algebras and provide several algebraic and computable theoretic distinctions of these algebras from the class of computable algebras. We give a characterization of computably enumerable but not computable algebras in terms of congruences and effective conjunctions of Π01-sentences. Our characterization, for example, shows that computable conjunctions of negative atomic formulas true in a given c.e. algebra can be preserved in infinitely many of its homomorphic images. We also study questions on how expansions of algebras by finitely many new functions affect computable isomorphism types. In particular, we construct a c.e. algebra with unique computable isomorphism type but which has no finitely generated c.e. expansion.

Applications to algorithmic randomness and theoretical computer science

Abstract: We show that the question whether the p-tt-complete or p-T-complete sets for the deterministic time classes E and EXP have measure 0 in these classes in the sense of Lutz's resource-bounded measure cannot be decided by relativizable techniques. On the other hand we obtain the following absolute results if we bound the norm, i.e., the number of oracle queries of the reductions: For r = tt, T,
μp({C : C p-r(kn)-complete for E}) = 0

and
μp2({C : C p-r(nk})-complete for EXP) = 0.

In the second part of the paper we investigate the diagonalization strength of random sets in an abstract way by relating randomness to a new genericity concept. This provides an alternative quite elegant and powerful approach for obtaining results on resource-bounded measures like the ones in the first part of the paper.
Abstract: Let r be a real number in the unit interval [0,1]. A set A ⊆ ω is said to be coarsely computable at density r if there is a computable function f such that {n | f(n) = A(n)} has lower density at least r. Our main results are that A is coarsely computable at density 1/2 if A is either computably traceable or truth-table reducible to a 1-random set. In the other direction, we show that if a degree a is either hyperimmune or PA, then there is an a-computable set which is not coarsely computable at any positive density.
Abstract:We investigate the truth-table degrees of (co-)c.e. sets, in particular, sets of random strings. It is known that the set of random strings with respect to any universal prefix-free machine is Turing complete, but that truth-table completeness depends on the choice of universal machine. We show that for such sets of random strings, any finite set of their truth-table degrees do not meet to the degree 0, even within the c.e. truth-table degrees, but when taking the meet over all such truth-table degrees, the infinite meet is indeed 0. The latter result proves a conjecture of Allender, Friedman and Gasarch. We also show that there are two Turing complete c.e. sets whose truth-table degrees form a minimal pair.
Abstract: Recently, several authors have explored the connections between NP-complete problems for finite objects and the complexity of their analogs for infinite objects. In this paper, we will categorize infinite versions of several problems arising from finite complexity theory in terms of their recursion theoretic complexity and proof theoretic strength. These infinite analogs can behave in a variety of unexpected ways.
Abstract: It is an open problem in the area of effective (algorithmic) randomness whether Kolmogorov-Loveland randomness coincides with Martin-Löf randomness. Joe Miller and André Nies suggested some variations of Kolmogorov-Loveland randomness to approach this problem and to provide a partial solution. We show that their proposed notion of injective randomness is still weaker than Martin-Löf randomness. Since in its proof some of the ideas we use are clearer, we also show the weaker theorem that permutation randomness is weaker than Martin-Löf randomness.
Abstract: We examine the sequences A that are low for dimension, i.e., those for which the effective (Hausdorff) dimension relative to A is the same as the unrelativized effective dimension. Lowness for dimension is a weakening of lowness for randomness, a central notion in effective randomness. By considering analogues of characterizations of lowness for randomness, we show that lowness for dimension can be characterized in several ways. It is equivalent to lowishness for randomness, namely, that every Martin-Löf random sequence has effective dimension 1 relative to A, and lowishness for K, namely, that the limit of KA(n)/K(n) is 1.

We show that there is a perfect Π01-class of low for dimension sequences. Since there are only countably many low for random sequences, many more sequences are low for dimension. Finally, we prove that every low for dimension sequence is jump-traceable in order nε, for any ε > 0.

Lecture notes, reviews and Ph. D. thesis

Abstract: In Chapter I, we exhibit a high strongly noncappable degree.

Chapter II answers negatively the question whether a deep degree exists. It also shows a weak converse of this.

Chapter III is devoted to index sets. We define a family of properties on hyperhypersimple sets and show that they yield index sets at each level of the hyperarithmetical hierarchy. We also classify the index set of quasimaximal sets, of coinfinite r.e. sets not having an atomless superset, and of r.e. sets major in a fixed nonrecursive r.e. set.

Chapter IV investigates properties of the partial order of ω-degrees. We show that the ω-degree of 0' splits and that there is a minimal pair in the r.e. ω-degrees. A forcing argument shows that the ω-degrees below 0(ω) do not form an upper semilattice.

Abstract: These notes (to be extended over the next few years) are intended to present various priority arguments in classical computability theory, effective model theory, and complexity theory in a uniform style.
Abstract: The two papers under review discuss aspects of the history of logic from antiquity to the twentieth century. The first paper deals with the history of induction from Aristotle and Euclid to the axiomatization of number theory by Dedekind and Peano and subsequent applications in proof theory. The second paper covers the history of the axiomatization from Euclid to Hilbert's "Grundlagen der Mathematik".
Abstract: The book under review, written by my colleague Ken Kunen, is intended as a first logic book at the graduate level, not assuming any prior knowledge of logic but just the usual mathematical maturity of a beginning graduate student in mathematics (including some elementary facts from undergraduate algebra).
Abstract: These lecture notes (for the UW-Madison course Math 135 by the same name) cover the main topics and concepts needed for the effective teaching of algebra in middle school: the properties of arithmetic, the use of letters in algebra, equations and inequalities, the concept of a function and its graph, and linear, quadratic and exponential functions. Great emphasis is placed on the underlying basic concepts and typical student misconceptions.

Legal Notice: The above preprints are copyrighted and may be downloaded and/or printed for personal or non-profit educational use only.
Prepared by Steffen Lempp (@math.wisc.edu">lemppmath.wisc.edu)