The Journal of Symbolic Logic

Research Article

Nonarithmetical ℵ0-categorical theories with recursive models

Julia F. Knight

Department of Mathematics, University of Notre Dame, Notre Dame, Indiana 46556

In what follows, L is a recursive language. The structures to be considered are L-structures with universe named by constants from ω. A structure is recursive A if the open diagram D() is recursive. Lerman and Schmerl [L-S] proved the following result.

Let T be an0-categorical elementary first-order theory. Suppose that for all n, , and T is arithmetical. Then T has a recursive model.

The aim of this paper is to extend Theorem 0.1. Stating the extension requires some terminology. Consider finitary formulas with symbols from L and sometimes extra constants from ω. For each nω, the Σ n and Π n formulas are as usual. Then Bn formulas are Boolean combinations of Σ n formulas. For an L-structure , Dn () denotes the set of Bn sentences in the complete diagram D c(). A complete Σ n theory is a maximal consistent set of Σ n L-sentences. We may write φ(x), or Γ(x), to indicate that the free variables of the formula φ, or the set Γ, are among those in x. A complete Bn type for x is a maximal consistent set Γ(x) of Bn formulas with just the free variables x.

If T is ℵ0-categorical, then for each x only finitely many complete types Γ(x) are consistent with T. While Lerman and Schmerl stated their result just for ℵ0-categorical theories, essentially the same proof yields the following.

Theorem 0.2. Let T be a consistent, complete theory such that for all n and x, only finitely many complete Bn types Γ(x) are consistent with T.

(Received December 03 1991)

(Revised March 30 1993)