We investigate the complexity of isomorphisms of computable structures on cones in the Turing degrees. We show that, on a cone, every structure has a strong degree of categoricity, and that degree of categoricity is${\rm{\Delta }}_\alpha ^0 $-complete for someα. To prove this, we extend Montalbán’sη-system framework to deal with limit ordinals in a more general way. We also show that, for any fixed computable structure, there is an ordinalαand a cone in the Turing degrees such that the exact complexity (...) of computing an isomorphism between the given structure and another copy${\cal B}$in the cone is a c.e. degree in${\rm{\Delta }}_\alpha ^0\left$. In each of our theorems the cone in question is clearly described in the beginning of the proof, so it is easy to see how the theorems can be viewed as general theorems with certain effectiveness conditions. (shrink)

In [7] and [8], it is established that given any abstract countable structure S and a relation R on S, then as long as S has a recursive copy satisfying extra decidability conditions, R will be ∑0α on every recursive copy of S iff R is definable in S by a special type of infinitary formula, a ∑rα() formula. We generalize the typ e of constructions of these papers to produce conditions under which, given two disjoint relations R1 and R2 (...) on S, there is a recursive copy of S in which R1 and R2 are 0α inseparable. We then apply these theorems to specific everyday structures such as linear orderings, boolean algebras andvector spaces. (shrink)

A Turing degreedis the degree of categoricity of a computable structure${\cal S}$ifdis the least degree capable of computing isomorphisms among arbitrary computable copies of${\cal S}$. A degreedis the strong degree of categoricity of${\cal S}$ifdis the degree of categoricity of${\cal S}$, and there are computable copies${\cal A}$and${\cal B}$of${\cal S}$such that every isomorphism from${\cal A}$onto${\cal B}$computesd. In this paper, we build a c.e. degreedand a computable rigid structure${\cal M}$such thatdis the degree of categoricity of${\cal M}$, butdis not the strong degree of categoricity (...) of${\cal M}$. This solves the open problem of Fokina, Kalimullin, and Miller [13].For a computable structure${\cal S}$, we introduce the notion of the spectral dimension of${\cal S}$, which gives a quantitative characteristic of the degree of categoricity of${\cal S}$. We prove that for a nonzero natural numberN, there is a computable rigid structure${\cal M}$such that$0\prime$is the degree of categoricity of${\cal M}$, and the spectral dimension of${\cal M}$is equal toN. (shrink)

A recursive algebra is a structure for which A is a recursive set of numbers and the Fi are uniformly recursive operations. We define an r.e. quotient algebra to be the quotient by an r.e. congruence .We say that is recursively stable among r.e. quotient algebras if, for each r.e. quotient algebra and each isomorphism from onto ′, the set {a,baA,bB and =[b]′} is r.e.We shall consider examples of recursive stability. Then, assuming that has a recursive existential diagram, we show (...) that the task of determining its recursive stability among r.e. quotient algebras can be reduced to a more routine consideration of syntactical conditions. To this result, we provide a counter-example which demonstrates the necessity of having a recursive existential diagram. This result and counter-example are on similar lines to ones obtained by Goncharov , for the recursive stability of recursive structures. (shrink)

We say that a theory [Formula: see text] satisfies arithmetic-is-recursive if any [Formula: see text]-computable model of [Formula: see text] has an [Formula: see text]-computable copy; that is, the models of [Formula: see text] satisfy a sort of jump inversion. We give an example of a theory satisfying arithmetic-is-recursive non-trivially and prove that the theories satisfying arithmetic-is-recursive on a cone are exactly those theories with countably many [Formula: see text]-back-and-forth types.

A computable structure [Formula: see text] is decidable if, given a formula [Formula: see text] of elementary first-order logic, and a tuple [Formula: see text], we have a decision procedure to decide whether [Formula: see text] holds of [Formula: see text]. We show that there is no reasonable classification of the decidably presentable structures. Formally, we show that the index set of the computable structures with decidable presentations is [Formula: see text]-complete. We also show that for each [Formula: see text] (...) the index set of the computable structures with [Formula: see text]-decidable presentations is [Formula: see text]-complete. (shrink)

Hurlburt, K.R., Sufficiency conditions for theories with recursive models, Annals of Pure and Applied Logic 55 305–320. We give conditions under which it is possible to construct recursive models for certain highly non-recursive theories. The main idea is to find an ‘α-friendly family’ of structures corresponding to the given theory and then to construct the desired recursive model by copying appropriate parts of these structures, choosing the part to copy in each structure so as to include important witnesses. All of (...) this is done using the recursive labelling systems designed by C. Ash. An example is given which involves orderings whose elementary first-order theories have degree O. (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.

§1. Introduction. A linear ordering embedsinto another linear ordering if it is isomorphic to a subset of it. Two linear orderings are said to beequimorphicif they can be embedded in each other. This is an equivalence relation, and we call the equivalence classesequimorphism types. We analyze the structure of equimorphism types of linear orderings, which is partially ordered by the embeddability relation. Our analysis is mainly fromthe viewpoints of Computability Theory and Reverse Mathematics. But we also obtain results, as the (...) definition of equimorphism invariants for linear orderings, which provide a better understanding of the shape of this structure in general.This study of linear orderings started by analyzing the proof-theoretic strength of a theorem due to Jullien [Jul69]. As is often the case in Reverse Mathematics, to solve this problem it was necessary to develop a deeper understanding of the objects involved. This led to a variety of results on the structure of linear orderings and the embeddability relation on them. These results can be divided into three groups. (shrink)

The degrees of unsolvability were introduced in the ground-breaking papers of Post [20] and Kleene and Post [7] as an attempt to measure theinformation contentof sets of natural numbers. Kleene and Post were interested in the relative complexity of decision problems arising naturally in mathematics; in particular, they wished to know when a solution to one decision problem contained the information necessary to solve a second decision problem. As decision problems can be coded by sets of natural numbers, this question (...) is equivalent to: Given a computer with access to an oracle which will answer membership questions about a setA, can a program be written which will correctly compute the answers to all membership questions about a setB? If the answer is yes, then we say thatBisTuring reducibletoAand writeB≤TA. We say thatB≡TAifB≤TAandA≤TB. ≡Tis an equivalence relation, and ≤Tinduces a partial ordering on the corresponding equivalence classes; the poset obtained in this way is called thedegrees of unsolvability, and elements of this poset are calleddegrees.Post was particularly interested in computability from sets which are partially generated by a computer, namely, those for which the elements of the set can be enumerated by a computer. (shrink)

We say that a theory T satisfies arithmetic-is-recursive if any X′-computable model of T has an X-computable copy; that is, the models of T satisfy a sort of jump inversion. We give an example of a...

We construct a recursive model , a recursive subset R of its domain, and a Turing degree x 0 satisfying the following condition. The nonrecursive images of R under all isomorphisms from to other recursive models are of Turing degree x and cannot be recursively enumerable.

In this paper, we state a metatheorem for constructions involving coding. Using the metatheorem, we obtain results on coding a family of sets into a family of relations, or into a single relation. For a concrete example, we show that the set of limit points in a recursive ordering of type ω 2 can have arbitrary 2-REA degree.

Let be a model of a theory T. Depending on wether is decidable or recursive, and on whether T is strongly minimal or -minimal, we find conditions on which guarantee that every infinite independent subset of is not recursively enumerable. For each of the same four cases we also find conditions on which guarantee that every infinite independent subset of has Turing degree 0'. More generally, let be a recursive -structure, R a relation symbol not in , ψ a recursive (...) infiniatary Π2 sentence in the language {R}, and let 0<α<ωCK1. We discuss conditions under which we can construct a recursive -structure such that ,Rψ for every Δ0α relation R on. (shrink)