Nonarithmetical ℵ₀-categorical theories with recursive models

Extract

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 an ℵ₀-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 B_nformulas are Boolean combinations of Σ_n formulas. For an L-structure , D_n() denotes the set of B_n sentences in the complete diagram D^c(). A complete Σ_n theory is a maximal consistent set of Σ_nL-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 B_n type for x is a maximal consistent set Γ(x) of B_n formulas with just the free variables x.

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

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