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, M_{5} and N_{5}, 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 Π^{0}_{2}-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.
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.
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: 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 x ≤ a, b ∪ x ≥ a.
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 high_{2} r. e. degree not bounding any minimal pair. We conclude with another application of our high_{2} 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.
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 Π^{1}_{1}-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 A_{0} and A_{1} then the jumps of both A_{0} and A_{1} are strictly below the jump of A.
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 Σ^{0}_{3}-complete. This implies that for this A, there is no uniformly computably enumerable "tower" of sets exhausting exactly the coinfinite sets in L^{*}(A).
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 d_{1} > d_{2} > 0 forms a double bubble if all d.c.e. degrees below d_{1} are comparable with d_{2}.
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 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.
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 Δ^{0}_{2} 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.
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 A ≤_{e} C and B ≤_{e} 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: We show that every finite lattice is embeddable into the Σ^{0}_{2}-enumeration degrees via a lattice-theoretic embedding which preserves 0 and 1.
Abstract: We give an algorithm for deciding whether an embedding of a finite partial order P into the enumeration degrees of the Σ^{0}_{2}-sets can always be extended to an embedding of a finite partial order Q extending P.
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:
- 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.
- There exists an infinite family of d. c. e. sets without a Friedberg numbering.
- 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.
- 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.
Abstract: We study computably enumerable equivalence relations (ceers) under the reducibility R ≤ S 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 Σ^{0}_{3}-complete (the former answering an open question of Gao and Gerdes).
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'.
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 study Turing degrees a for which there is a countable structure 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 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 Δ^{0}_{2}-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 Π^{1}_{1}-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(M_{M}) is a model complete L_{M}-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 Σ^{0}_{5}.
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(T_{fin}) of the theory T_{fin} = Th(M_{fin}) of the class M_{fin} 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 Π^{0}_{1}-numeration. Moreover, the quotient algebra (L(T_{fin})/F, γ/F) modulo the Fréchet ideal F is a Σ^{0}_{2}-algebra, which is universal over the class of all Σ^{0}_{2}-Boolean algebras. These conditions characterize uniquely the algebra L(T_{fin}); moreover, these conditions characterize up to recursive isomorphism the numerated Boolean quotient algebra (L(T_{fin})/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 Π^{0}_{3}-complete; and the property of being an Ehrenfeucht theory Π^{1}_{1}-complete. We also show that the property of having continuum many models is Σ^{1}_{1}-hard. Finally, as a corollary, we note that the properties of having only decidable models, and of having only computable models, are both Π^{1}_{1}-complete.
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 Π^{0}_{1}-statements, whereas statements of totality of computable functions are Π^{0}_{2}-statements); and the structure of the degrees of provability can be viewed as the Lindenbaum algebra of true Π^{0}_{2}-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 Π^{0}_{1}-statements as a substructure, and connecting the degrees of provability to escape and domination properties of computable functions.
Abstract: Simpson and X. Yu introduced an axiom system WWKL_{0} and showed it to be strictly intermediate between RCA_{0} and WKL_{0} as well as equivalent to some statements on Lebesgue and Borel measure. WWKL_{0} 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 WKL_{0} and implied the DNR axiom. They pointed out that DNR is intermediate between RCA_{0} and WWKL_{0}, but left open the question whether DNR coincides with WWKL_{0}, i. e., has the same theorems as WWKL_{0}. Simpson conjectured that DNR is strictly weaker than WWKL_{0}.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 Σ^{0}_{2}-Bounding principle BΣ^{0}_{2} over RCA_{0}, answering one of their open questions.We also fill a gap in a proof in Cholak, Jockusch and Slaman [2001] by showing that D^{2}_{2} implies BΣ^{0}_{2} and is thus indeed equivalent to Stable Ramsey's Theorem for Pairs SRT^{2}_{2}.
Furthermore, this also allows us to conclude that the combinatorial principles IPT, SPT and SIPT defined by Dzhafarov and Hirst [2009] all imply BΣ^{0}_{2}, and thus that SPT and SIPT are both equivalent to SRT^{2}_{2} as well.
Our proof uses the notion of a bi-tame cut, the existence of which we show to be equivalent, over RCA_{0}, to the failure of BΣ^{0}_{2}.
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 SRT^{2}_{2} implies DNR over RCA_{0} but COH does not, and answer a question of Mileti by showing that every computable stable 2-coloring of pairs has an incomplete Δ^{0}_{2} infinite homogeneous set. We also give some extensions of the latter result, and relate it to potential approaches to showing that SRT^{2}_{2} does not imply RT^{2}_{2}.
Abstract: We determine the complexity of torsion-freeness of finitely presented groups in Kleene's arithmetical hierarchy as Π^{0}_{2}-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: 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 RCA_{0}, while if subgroups are defined by generators, the theorem is equivalent to ACA_{0}.
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 compare Aut(Q), the classical automorphism group of a countable dense linear order, with Aut_{c}(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 Aut_{c}(Q). Also, Aut(Q) has three fundamental properties which fail in Aut_{c}(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.
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 WKL_{0} over RCA_{0}, 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 ACA_{0} over RCA_{0}. We also prove that there are computable commutative rings with identity where the nilradical is Σ^{0}_{1}-complete, and the Jacobson radical is Π^{0}_{2}-complete, respectively.
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 WKL_{0} over RCA_{0}, and that the existence of a finite-dimensional nontrivial proper subspace of such a vector space is equivalent to ACA_{0} over RCA_{0}.
Abstract: We show that any Σ^{0}_{2}-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 (RCA_{0})) to arithmetic comprehension (ACA_{0}).
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: In this paper, we solve a long-standing open question (see, e.g., Downey [1998] and Downey and Moses [1991), about the spectrum of the successivity relation on a computable linear ordering. We show that if a computable linear ordering L has infinitely many successivities, then the spectrum of the adjacency relation is closed upwards in the computably enumerable Turing degrees. To do this, we use a new method of constructing Δ^{0}_{3}-isomorphisms, which has already found other applications such as Downey, Kastermans and Lempp [2009] and is of independent interest. It would seem to promise many further applications.Remark: Maxim Zubkov has pointed out a small error in our corrigendum: We also need to consider the additional case of the order-type
∑_{i ∈ ω} (η+fin) + (η ⋅ ∑_{i ∈ ζ} (η+fin)) + ∑_{i ∈ ω*} (η+fin) where fin stands for a finite block of any size. This case can be handled as in the Corrigendum, with minor adjustments.
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: 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 Π^{0}_{1}-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 Π^{0}_{1}-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 Π^{0}_{1}-antichain. In Reverse Mathematics, we show that SCAC, the principle that every infinite stable poset contains an infinite chain or antichain, is equivalent over RCA_{0} 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 Σ^{0}_{3}-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 Δ^{0}_{n+1}-categorical but not Δ^{0}_{n}-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 Δ^{0}_{2} maximal filter, and there is a computable poset with no Π^{0}_{1} or Σ^{0}_{1} 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 ACA_{0} over RCA_{0}.
An unbounded filter is a filter which achieves each of its lower bounds in the poset. We show that every computable poset has a Σ^{0}_{1} unbounded filter, and there is a computable poset with no Π^{0}_{1} 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 ACA_{0} over RCA_{0}. We obtain additional reverse mathematics results related to extending arbitrary filters to unbounded filters and forming the upward closures of subsets of computable posets.
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 Π^{0}_{1}-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.
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(n^{k}})-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 K^{A}(n)/K(n) is 1.We show that there is a perfect Π^{0}_{1}-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.
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: 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.