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)

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.

Calhoun, W.C., Incomparable prime ideals of recursively enumerable degrees, Annals of Pure and Applied Logic 63 39–56. We show that there is a countably infinite antichain of prime ideals of recursively enumerable degrees. This solves a generalized form of Post's problem.

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 re-express a previous general result in a way which seems easier to remember, using the terminology of infinite games. We show how this can be applied to construct recursive linear orderings, showing, for example, that if there is a ▵ 0 2β + 1 linear ordering of type τ, then there is a recursive ordering of type ω β · τ.

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...

Theories of classification distinguish classes with some good structure theorem from those for which none is possible. Some classes (dense linear orders, for instance) are non-classifiable in general, but are classifiable when we consider only countable members. This paper explores such a notion for classes of computable structures by working out a sequence of examples. We follow recent work by Goncharov and Knight in using the degree of the isomorphism problem for a class to distinguish classifiable classes from non-classifiable. In (...) this paper, we calculate the degree of the isomorphism problem for Abelian p-groups of bounded Ulm length. The result is a sequence of classes whose isomorphism problems are cofinal in the hyperarithmetical hierarchy. In the process, new back-and-forth relations on such groups are calculated. (shrink)

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)