It is shown that for every nonzero r.e. degree c there is a linear ordering of degree c which is not isomorphic to any recursive linear ordering. It follows that there is a linear ordering of low degree which is not isomorphic to any recursive linear ordering. It is shown further that there is a linear ordering L such that L is not isomorphic to any recursive linear ordering, and L together with its ‘infinitely far apart’ relation is of low (...) degree. Finally, an analogue of the recursion theorem for recursive linear orderings is refuted. (shrink)

Whenever a structure with a particularly interesting computability-theoretic property is found, it is natural to ask whether similar examples can be found within well-known classes of algebraic structures, such as groups, rings, lattices, and so forth. One way to give positive answers to this question is to adapt the original proof to the new setting. However, this can be an unnecessary duplication of effort, and lacks generality. Another method is to code the original structure into a structure in the given (...) class in a way that is effective enough to preserve the property in which we are interested. In this paper, we show how to transfer a number of computability-theoretic properties from directed graphs to structures in the following classes: symmetric, irreflexive graphs; partial orderings; lattices; rings ; integral domains of arbitrary characteristic; commutative semigroups; and 2-step nilpotent groups. This allows us to show that several theorems about degree spectra of relations on computable structures, nonpreservation of computable categoricity, and degree spectra of structures remain true when we restrict our attention to structures in any of the classes on this list. The codings we present are general enough to be viewed as establishing that the theories mentioned above are computably complete in the sense that, for a wide range of computability-theoretic nonstructure type properties, if there are any examples of structures with such properties then there are such examples that are models of each of these theories. (shrink)

Fraïssé studied countable structures S through analysis of the age of S i.e., the set of all finitely generated substructures of S. We investigate the effectiveness of his analysis, considering effectively presented lists of finitely generated structures and asking when such a list is the age of a computable structure. We focus particularly on the Fraïssé limit. We also show that degree spectra of relations on a sufficiently nice Fraïssé limit are always upward closed unless the relation is definable by (...) a quantifier-free formula. We give some sufficient or necessary conditions for a Fraïssé limit to be spectrally universal. As an application, we prove that the computable atomless Boolean algebra is spectrally universal. (shrink)

We study the weak truth table degree spectra of first-order relational structures. We prove a dichotomy among the possible wtt degree spectra along the lines of Knight’s upward-closure theorem for Turing degree spectra. We prove new results contrasting the wtt degree spectra of finite- and infinite-signature structures. We show that, as a method of defining classes of reals, the wtt degree spectrum is, except for some trivial cases, strictly more expressive than the Turing degree spectrum.

Much previous study has been done on the degree spectra of prime models of a complete atomic decidable theory. Here we study the analogous questions for homogeneous models. We say a countable model A has a d-basis if the types realized in A are all computable and the Turing degree d can list $\Delta _{0}^{0}$ -indices for all types realized in A. We say A has a d-decidable copy if there exists a model B ≅ A such that the elementary (...) diagram of B is d-computable. Goncharov, Millar, and Peretyat'kin independently showed there exists a homogeneous A with a 0-basis but no decidable copy. We prove that any homogeneous A with a 0'-basis has a low decidable copy. This implies Csima's analogous result for prime models. In the case where all types of the theory T are computable and A is a homogeneous model with a 0-basis, we show A has copies decidable in every nonzero degree. A degree d is 0-homogeneous bounding if any automorphically nontrivial homogeneous A with a 0-basis has a d-decidable copy. We show that the nonlow₂ $\Delta _{2}^{0}$ degrees are 0-homogeneous bounding. (shrink)

A Turing degree d is homogeneous bounding if every complete decidable (CD) theory has a d-decidable homogeneous model A, i.e., the elementary diagram De (A) has degree d. It follows from results of Macintyre and Marker that every PA degree (i.e., every degree of a complete extension of Peano Arithmetic) is homogeneous bounding. We prove that in fact a degree is homogeneous bounding if and only if it is a PA degree. We do this by showing that there is a (...) single CD theory T such that every homogeneous model of T has a PA degree. (shrink)

The spectrum of a relation on a computable structure is the set of Turing degrees of the image of R under all isomorphisms between and any other computable structure . The relation is intrinsically computably enumerable if its image under all such isomorphisms is c.e. We prove that any computable partially ordered set is isomorphic to the spectrum of an intrinsically c.e. relation on a computable structure. Moreover, the isomorphism can be constructed in such a way that the image of (...) the minimum element of the partially ordered set is computable. This solves the spectrum problem. The theorem and modifications of its proof produce computably categorical structures whose expansions by finite number of constants are not computably categorical and, indeed, ones whose expansions can have any finite number of computable isomorphism types. They also provide examples of computably categorical structures that remain computably categorical under expansions by constants but have no Scott family. (shrink)

We analyze the degree spectra of structures in which different types of immunity conditions are encoded. In particular, we give an example of a structure whose degree spectrum coincides with the hyperimmune degrees. As a corollary, this shows the existence of an almost computable structure of which the complement of the degree spectrum is uncountable.

In the last five years there have been a number of results about the computable content of the prime, saturated, or homogeneous models of a complete decidable theory T in the spirit of Vaught's "Denumerable models of complete theories" combined with computability methods for degrees d ≤ 0′. First we recast older results by Goncharov, Peretyat'kin, and Millar in a more modern framework which we then apply. Then we survey recent results by Lange, "The degree spectra of homogeneous models," which (...) generalize the older results and which include positive results on when a certain homogeneous model of T has an isomorphic copy of a given Turing degree. We then survey Lange's "A characterization of the 0-basis homogeneous bounding degrees" for negative results about when does not have such copies, generalizing negative results by Goncharov, Peretyat'kin, and Millar. Finally, we explain recent results by Csima, Harizanov, Hirschfeldt, and Soare, "Bounding homogeneous models," about degrees d that are homogeneous bounding and explain their relation to the PA degrees. (shrink)

We prove an effective version of the Lopez-Escobar theorem for continuous domains. Let $Mod(\tau )$ be the set of countable structures with universe $\omega $ in vocabulary $\tau $ topologized by the Scott topology. We show that an invariant set $X\subseteq Mod(\tau )$ is $\Pi ^0_\alpha $ in the Borel hierarchy of this topology if and only if it is definable by a $\Pi ^p_\alpha $ -formula, a positive $\Pi ^0_\alpha $ formula in the infinitary logic $L_{\omega _1\omega }$. As (...) a corollary of this result we obtain a new pullback theorem for positive computable embeddings: Let $\mathcal {K}$ be positively computably embeddable in $\mathcal {K}'$ by $\Phi $, then for every $\Pi ^p_\alpha $ formula $\xi $ in the vocabulary of $\mathcal {K}'$ there is a $\Pi ^p_\alpha $ formula $\xi ^{*}$ in the vocabulary of $\mathcal {K}$ such that for all $\mathcal {A}\in \mathcal {K}$, $\mathcal {A}\models \xi ^{*}$ if and only if $\Phi (\mathcal {A})\models \xi $. We use this to obtain new results on the possibility of positive computable embeddings into the class of linear orderings. (shrink)

We consider a recursive model and an additional recursive relation R on its domain, such that there are uncountably many different images of R under isomorphisms from to some recursive model isomorphic to . We study properties of the set of Turing degrees of all these isomorphic images of R on the domain of.

We say a countable model ������ has a 0-basis if the types realized in ������ are uniformly computable. We say ������ has a (d-)decidable copy if there exists a model ������ ≅ ������ such that the elementary diagram of ������ is (d-)computable. Goncharov, Millar, and Peretyat'kin independently showed there exists a homogeneous model ������ with a 0-basis but no decidable copy. We extend this result here. Let d ≤ 0' be any low₂ degree. We show that there exists a homogeneous (...) model ������ with a 0-basis but no d-decidable copy. A degree d is 0-basis homogeneous bounding if any homogenous ������ with a 0-basis has a d-decidable copy. In previous work, we showed that the nonlow₂ $\Delta _{2}^{0}$ degrees are 0-basis homogeneous bounding. The result of this paper shows that this is an exact characterization of the 0-basis homogeneous bounding $\Delta _{2}^{0}$ degrees. (shrink)

We give a straightforward computable-model-theoretic definition of a property of \Delta^0_2 sets called order-computability. We then prove various results about these sets which suggest that, simple though the definition is, the property defies any easy characterization in pure computability theory. The most striking example is the construction of two computably isomorphic c.e. sets, one of which is order-computable and the other not.

In the framework of Stewart Shapiro, computations are performed directly on strings of symbols (numerals) whose abstract numerical interpretation is determined by a notation. Shapiro showed that a total unary function (unary relation) on natural numbers is computable in every injective notation if and only if it is almost constant or almost identity function (finite or co-finite set). We obtain a syntactic generalization of this theorem, in terms of quantifier-free definability, for functions and relations relatively intrinsically computable on certain types (...) of equivalence structures. We also characterize the class of relations and partial functions of arbitrary finite arities which are computable in every notation (be it injective or not). We consider the same question for notations in which certain equivalence relations are assumed to be computable. Finally, we discuss connections with a theorem by Ash, Knight, Manasse and Slaman which allow us to deduce some (but not all) of our results, based on quantifier elimination. (shrink)

The paper studies Heyting algebras within the framework of computable structure theory. We prove that the class _K_ containing all Heyting algebras with distinguished atoms and coatoms is complete in the sense of the work of Hirschfeldt et al. (Ann Pure Appl Logic 115(1-3):71-113, 2002). This shows that the class _K_ is rich from the computability-theoretic point of view: for example, every possible degree spectrum can be realized by a countable structure from _K_. In addition, there is no simple syntactic (...) characterization of computably categorical members of _K_ (i.e., structures from _K_ possessing a unique computable copy, up to computable isomorphisms). (shrink)

Mereological theories are based on the binary relation “being a part of”. The systematic investigations of mereology were initiated by Leśniewski. More recent authors (including Simons, Casati and Varzi, Hovda) formulated a series of first‐order mereological axioms. These axioms give rise to a plenitude of theories, which are of great philosophical interest. The paper considers first‐order mereological theories from the point of view of computable (or effective) algebra. Following the approach of Hirschfeldt, Khoussainov, Shore, and Slinko, we isolate two important (...) computability‐theoretic properties P (namely, degree spectra of structures, and effective dimensions), and consider the following problem: for a given mereological theory T, is it true that its models can realize every possible variant of the property P? If the answer is positive, then we say that the theory T is ‐universal. We obtain the following results about known mereological theories. Any theory T which is weaker than Extensional Closure Mereology (CEM) is ‐universal. A similar fact is true for the theory GM2. On the other hand, any theory stronger that CEM + (C) + (G) is not ‐universal. In particular, General Extensional Mereology is not ‐universal. (shrink)

Several researchers have recently established that for every Turing degree \, the real closed field of all \-computable real numbers has spectrum \. We investigate the spectra of real closed fields further, focusing first on subfields of the field \ of computable real numbers, then on archimedean real closed fields more generally, and finally on non-archimedean real closed fields. For each noncomputable, computably enumerable set C, we produce a real closed C-computable subfield of \ with no computable copy. Then we (...) build an archimedean real closed field with no computable copy but with a computable enumeration of the Dedekind cuts it realizes, and a computably presentable nonarchimedean real closed field whose residue field has no computable presentation. (shrink)

These are the lecture notes from a 10-hour course that the author gave at the University of Notre Dame in September 2010. The objective of the course was to introduce some basic concepts in computable structure theory and develop the background needed to understand the author’s research on back-and-forth relations.

Computable model theory, also called effective or recursive model theory, studies algorithmic properties of mathematical structures, their relations, and isomorphisms. These properties can be described syntactically or semantically. One of the major tasks of computable model theory is to obtain, whenever possible, computability-theoretic versions of various classical model-theoretic notions and results. For example, in the 1950's, Fröhlich and Shepherdson realized that the concept of a computable function can make van der Waerden's intuitive notion of an explicit field precise. This led (...) to the notion of a computable structure. In 1960, Rabin proved that every computable field has a computable algebraic closure. However, not every classical result “effectivizes”. Unlike Vaught's theorem that no complete theory has exactly two nonisomorphic countable models, Millar's and Kudaibergenov's result establishes that there is a complete decidable theory that has exactly two nonisomorphic countable models with computable elementary diagrams. In the 1970's, Metakides and Nerode [58], [59] and Remmel [71], [72], [73] used more advanced methods of computability theory to investigate algorithmic properties of fields, vector spaces, and other mathematical structures. (shrink)

We investigate effective categoricity for polymodal algebras. We prove that the class of polymodal algebras is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations. In particular, this implies that every categoricity spectrum is the categoricity spectrum of a polymodal algebra.

One of the main problems in effective model theory is to find an appropriate information complexity measure of the algebraic structures in the sense of computability. Unlike the commonly used degrees of structures, the structure degree measure is total. We introduce and study the jump operation for structure degrees. We prove that it has all natural jump properties (including jump inversion theorem, theorem of Ash), which show that our definition is relevant. We study the relation between the structure degree jump (...) (in the sense of Soskov) and the jump degrees of a structure (in the sense of Jockusch) and give necessary and sufficient conditions for their existence in the terms of structure degrees. We show some properties, distinguishing the structure degrees from the enumeration degrees. (shrink)

We show, for each computable ordinal α and degree $\alpha > {0^{\left( \alpha \right)}}$, the existence of a torsion-free abelian group with proper α th jump degree α.

Results of R. Miller in 2009 proved several theorems about algebraic fields and computable categoricity. Also in 2009, A. Frolov, I. Kalimullin, and R. Miller proved some results about the degree spectrum of an algebraic field when viewed as a subfield of its algebraic closure. Here, we show that the same computable categoricity results also hold for finite-branching trees under the predecessor function and for connected, finite-valence, pointed graphs, and we show that the degree spectrum results do not hold for (...) these trees and graphs. We also offer an explanation for why the degree spectrum results distinguish these classes of structures: although all three structures are algebraic structures, the fields are what we call effectively algebraic. (shrink)

In this paper, we solve a long-standing open question, about the spectrum of the successivity relation on a computable linear ordering. We show that if a computable linear ordering [Formula: see text] has infinitely many successivities, then the spectrum of the successivity relation is closed upwards in the computably enumerable Turing degrees. To do this, we use a new method of constructing [Formula: see text]-isomorphisms, which has already found other applications such as Downey, Kastermans and Lempp [9] and is of (...) independent interest. It would seem to promise many further applications. (shrink)