Categoricity and Scott Families

Bakhadyr Khoussainov Cornell University, Ithaca NY 14850 USA

Richard A. Shore ^{∗} Cornell University, Ithaca NY 14853 USA

1 Introduction

Effective model theory is an area of logic that analyzes the effective content of the typical notions and results of model theory and universal algebra. Typical notions in model theory and universal algebra are languages and structures, theories and models, models and their submodels, automorphisms and isomorphisms, embeddings and elementary embeddings. In this paper languages, structures, and models are assumed to be countable.

There are many ways to introduce considerations of effectiveness into the area of model theory or universal algebra. Here we will briefly explain considerations of effectiveness for theories and their models on the one hand, and for just structures on the other hand.

Let us begin by considering effectiveness for theories and their models. From the model theoretic point of view, given a first order theory, one is interested in finding models for the theory with specific algebraic or modeltheoretic properties. In this sense theories are the basic objects in model theory. A natural way of introducing effectiveness is, therefore, to begin by considering decidable theories, i.e. ones whose theorems form a decidable (i.e. computable or recursive) set.

∗Partially supported by NSF Grant DMS-9503503 and ARO through MSI, Cornell University, DAAL-03-C-0027.

Given a decidable complete theory, one can effectively carry out a Henkin type construction and build a model of the theory. This procedure guarantees that the satisfaction predicate for the model constructed is decidable. Thus we are led to the following definition.

Definition 1.1 A structure A is decidable if there is a computable enumeration a_{i} of the elements of A such that T h(A, a_{i}) is decidable.

Just as model theory investigates the class of models of a given theory, effective model theory is concerned with decidable models of decidable theories. There have been a significant number of results about decidable models of decidable theories. These results typically discuss questions related to finding decidable prime, saturated, homogeneous models; omitting or realizing types by decidable models; the number of decidable models for decidable theories, etc. We refer the reader to [8] and [15] for survey articles in this area.

If we begin to introduce consideration of effectiveness just for the structures themselves, then we are essentially in the realm of general effective mathematics. Considerations of effectiveness for structures have been extensively developed since the early 60’s beginning with Frölich and Shepherdson [5], Rabin [17], and Malcev [13]. However, it is worth to noting that even in the early 60’s the idea of considering effectiveness in structures was not new. In the 30’s Kleene and Church considered effectiveness in well-ordered sets and invented recursive ordinals. In the early 70’s Nerode and his collaborators in the U. S., as well as Ershov and his colleagues in Novosibirsk, developed the powerful idea of combining model-theoretic and algebraic constructions with priority arguments from computability theory. This approach embodies the technical core of many results in effective model theory.

More recently, there have been many papers devoted to investigating effectiveness in structures. For example, Cenzer, Nerode and Remmel [1] have been developing the theory of p-time structures. Khoussainov and Nerode have begun the development of the theory of automatic structures [11]. These theories are based, respectively, on computations which can be performed in p-time and by finite automata. We will not discuss these topics but turn instead to structures in which the basic functions and relations can be computed by Turing machines.

Definition 1.2 A structure A for a language L is computable if its domain A is a computable subset of ω and its functions and relations are uniformly computable. A structure isomorphic to a computable structure is called computably presentable, and any such isomorphism is called a computable presentation.

The requirements of computability are significantly weaker than those for decidability. However, the definition captures what one normally means by an effective structure or presentation in mathematical discourse.

Identification of isomorphic structures is typical in model theory and universal algebra or, indeed, generally in classical mathematics. A typical model-theoretic or algebraic problem about isomorphisms can often be stated as follows: Find some invariants such that any two structures from the class are isomorphic if only if they have the same invariants.

Introducing effectiveness considerations into the area, we would like to understand the relationship between classical invariants and effective invariants; in particular, between isomorphism types and effective isomorphism types. Thus, while model theory identifies isomorphic structures, effective model theory is concerned with computable isomorphisms and finding characterizations for structures which have the same computable isomorphism type. A fundamental concept is therefore that of computable isomorphism type.

Definition 1.3 Two computable structures A and B are of the same computable isomorphism type if there is computable isomorphism taking A to B. The dimension of a computable structure A is the number of its computable isomorphism types.

To what extent computable isomorphism types can differ from classical ones can be seen from the following result of Goncharov:

Theorem 1.4 ([7]) For each n ≤ ω there is a computable structure with computable dimension n.

There has been significant interest in understanding the nature of the structures of dimension 1. The basic model theoretic notion which motivated this interest is that of ω–categoricity. A theory T is ω–categorical if all countable models of T are isomorphic. A structure A is ω–categorical if its theory is ω–categorical. The analogous concept for effective model theory deals only with computable structures and isomorphisms:

Definition 1.5 A structure A is computably categorical if any two computable structures isomorphic to A are computably isomorphic.

The result of Nurtazin [16] is one of the first about the nature of computably categorical structures. His theorem characterizes structures whose decidable presentations form one computable isomorphism type.

Theorem 1.6 ([16]) For a structure A the following two conditions are equivalent:

1. Any two decidable presentations of A are computably isomorphic.

2. There exists a finite sequence c̄ of constants from A such that (A, c̄) is the prime model of the theory T h(A, c̄) and the set of atoms of this theory is computable.

In the late 70’s Goncharov [6] and Remmel [18] independently gave an algebraic characterization for Boolean Algebras and Linear Orderings to be computably categorical.

Theorem 1.7 ([6] [18]) 1. A Boolean Algebra is computably categorical if and only if has finitely many atoms.

2. A linear ordering is computably categorical if and only if the number of pairs of adjacent elements is finite.

2 Scott Families

Interestingly, all the structures which have been shown to be computably categorical have one common property. They all have Scott families.

Definition 2.1 A Scott family for a structure A is a computable sequence ϕ_{0}(ā, x_{1}, …, x_{n_{0}}), ϕ_{1}(ā, x_{1}, …, x_{n_{1}}), … of ∃-formulas satisfiable in A, where ā is a fixed tuple of elements from A, such that every tuple in A satisfies one these formulas and any two tuples satisfying the same formula from the sequence can be sent to each other via an automorphism of A.

The basic idea behind this definition is the following. If a computable structure A has a Scott family and B is a computable structure isomorphic to A, then we can effectively carry out a back and forth argument to construct a computable isomorphism from A to B.

Theorem 2.2 If a structure A has a Scott family, then the structure is computably categorical. Moreover, for any n-tuple (d_{1}, …, d_{n}) the expanded structure (A, d_{1}, …, d_{n}) also has a Scott Family.

Proof. Let ϕ_{0}(ā, x_{1}, …, x_{n_{0}}), ϕ_{1}(ā, x_{1}, …, x_{n_{1}}), … be a Scott family for A, where ā = (a_{0}, …, a_{m−1}). Let A_{1} and A_{2} be computable presentations of A. We define a mapping f : A_{1} → A_{2} by stages. We can assume that for each j ∈ {0, …, m − 1}, a_{j}^{i} is the element in A_{i} corresponding to the constant a_{j}. At even stages we define images of elements from A_{1}, at odd stages we define preimages of elements from A_{2}.

Stage 0. Set f_{1} = {(a_{0}^{1}, a_{0}^{2}), …, (a_{m−1}^{1}, a_{m−1}^{2})}.

Stage 2k. We can suppose that the function f_{2k−1} has been defined. Assume that f_{2k−1} = {(a_{0}^{1}, a_{0}^{2}), …, (a_{m−1}^{1}, a_{m−1}^{2}), (b_{1}, c_{1}), …, (b_{s}, c_{s})} and that f_{2k−1} can be extended to an isomorphism of A_{1} to A_{2}. Let b be the first number not in the domain of f_{2k−1}. Consider the tuple (b_{1}, …, b_{s}, b). Find an i such that ϕ_{i}(ā, b_{1}, …, b_{s}, b) holds in A_{1}. Hence ∃xϕ_{i}(ā, c_{1}, …, c_{s}, x) holds in A_{2}. Find the first c ∈ A_{2} for which ϕ_{i}(ā, c_{1}, …, c_{s}, c) holds. Extend f_{2k−1} by letting f_{2k} = f_{2k−1} ⋃{(b, c)}.

Stage 2k+1. We define f_{2k+1} similarly so as to put the least element of A_{2} not yet in the range of f_{2k} into that of f_{2k+1}.

Finally, let f = ⋃_{i∈ω} f_{i}. Thus, f is a computable isomorphism.

For the second part of the theorem, we slightly change the original Scott family. Namely, set ψ_{i} = ϕ_{i}(ā, x_{1}, …, x_{n_{i}})&∃y_{1} … ∃y_{n}(&_{j}(d_{j} = y_{j}). Then, one can easily check that the sequence ψ_{0}, ψ_{1}, … is a Scott family for the expanded structure (A, d_{1}, …, d_{n}). The theorem is proved.

Corollary 2.3 If a structure A has a Scott family, then any expansion of A by finitely many constants is computably categorical. □

At this point we would like to make the following two observations about the effect of expanding computably categorical structures by finitely many constants. First, as we have mentioned, all the known examples of computably categorical structures have Scott families. Thus, it is natural to ask whether there exists a computably categorical structure without a Scott family. By Corollary 2.3, one possible way to build a such structure is to provide an example of a computably categorical structure whose expansion by finitely many constants is not computably categorical. Second, as we mentioned, the notion of ω–categoricity is a basic model-theoretic motivation in the investigation of computably categorical structures. It is an easy consequence of the Ryll-Nardzewski theorem that if a structure A is ω-categorical then so is (A, ā), the structure expanded by finitely many constants. It is the analogous situation in effective model theory that we wish to consider.

Millar [14] proved that a small amount of decidability is enough to guarantee that categoricity is preserved under such expansions. Informally his theorem states that if a structure A is computably categorical and we can effectively solve systems of algebraic equations and inequations over this structure, then computable categoricity is preserved under expansions by a finite number of constants.

Theorem 2.4 ([14]) If a structure A is computably categorical and its existential theory is decidable, then the expansion of A by finitely many constants is also computably categorical.

Without the assumption of the decidability of the existential diagram, the question (known as Ash-Goncharov problem) has been open:

Does there exist a computably categorical structure whose expansion by a finite number of constants is not computably categorical?

An answer to this question has recently been found:

Theorem 2.5 ([2]) For each natural number n, there exists a computably categorical structure A such that, for every a ∈ A, the expanded structure (A, a) has dimension n.

An immediate consequence of Corollary 2.3 is now the following result:

Corollary 2.6 There exists a computably categorical structure without a Scott family.

However, based on Corollary 2.3, one could suggest that the reason the structure constructed in Theorem 2.5 does not have a Scott family is that the structure has an expansion by a finite number of constants which is not computably categorical. We construct a counterexample to this suggestion in the next section.

3 Scott Sequences for Families of Computably Enumerable Sets

Our basic result is the following theorem.

Theorem 3.1 There exists a structure without a Scott family such that every expansion of the structure by a finite number of constants is computably categorical.

The structure required to establish the theorem is constructed by coding certain (uniformly) computably enumerable families of sets of natural numbers.

Definition 3.2 A family S of sets of natural numbers has a one-to-one computable enumeration if there is a bijection f : ω → S such that {(i, x)|x ∈ f(i)} is computably enumerable. We then call f a (computable) one-to-one enumeration of S.

We wish to consider a preordering on the one-to-one computable enumerations of S that naturally induces an equivalence relation corresponding to computable isomorphism:

Definition 3.3 A computable enumeration f of S is reducible to g, f ≤ g, if there is a computable Φ such that f = gΦ. If f ≤ g and g ≤ f, then we say that f and g are equivalent.

Note that if f is a one-to-one enumeration of S and f = gΦ, then Φ is a permutation of ω and so f ≤ g. Thus the equivalence classes of one-to-one enumerations are minimal elements in the induced partial ordering. These are the enumerations that we need to consider to define the family that supplies the structure required for Theorem 3.1. Informally, computable categoricity corresponds to there being a single such equivalence class and dimension corresponds to the number of such classes.

Definition 3.4 A computable sequence D_{0}, D_{1}, … of (canonical indices for) finite sets is a Scott sequence for a family S if the following properties hold:

1. For each D_{i} there exists exactly one M_{i} ∈ S such that D_{i} ⊂ M.

2. The set S \ {M_{0}, M_{1}, …} is finite.

The reader can easily prove the following:

Theorem 3.5 If S has a Scott sequence, then any two computable enumerations of S are equivalent. □

For any given family S, we want to construct a structure A_{S} such that A_{S} has a Scott family if and only if S has a Scott sequence. Thus, let S be a family of sets and let f be a one-to-one computable enumeration of S. We assume that each set in S has at least two elements. Based on f, we will construct a computable structure, indeed a graph, A_{f} = (ω, P_{f}), where P_{f} is a computable binary predicate on ω.

Consider a uniformly effective, possibly finite, sequence a_{i,0}, a_{i,1}, a_{i,2}, … without repetitions such that, for each i ∈ ω, f(i) = {a_{i,0}, a_{i,1}, a_{i,2}, …}.

For each i ∈ ω, we can consider a computable structure G_{i}^{f} = (G_{i}, P_{i}^{f}) defined as follows. G_{i} has an element d_{i} such that for each a_{i,j} the predicate P_{i}^{f} defines a unique cycle C_{i,j} of length a_{i,j} for which d_{i} ∈ C_{i,j}. In addition, for all j, k the cycles C_{i,k} and C_{i,j} have only one element in common which is d_{i}. Thus, we see that for all j ≠ k we have d_{i} ∈ C_{i,k}, d_{i} ∈ C_{i,j} and (C_{i,j} \ {d_{i}}) ⋂(C_{i,k} \ {d_{i}}) = ∅. We call the element d_{i} a cluster point. Informally, the structure G_{i}^{f} codes the set f(i). The structure (graph) G_{i}^{f} is computable and satisfies the following properties:

1. For every number t, t belongs to f(i) if and only if there exist distinct elements x_{0}, …, x_{t} of the structure G_{i}^{f} such that the formula

P_{i}^{f}(x_{0}, x_{1}) & … P_{i}^{f}(x_{t−1}, x_{t}) & P_{i}^{f}(x_{t}, x_{0})

holds in the structure G_{i}^{f}.

2. Any two cycles in G_{i}^{f} have only one element in common.

By the construction of G_{i}^{f} and the computability of f, we can conclude that there exists a computable sequence A_{0}^{f} = (A_{0}^{f}, P_{0}), A_{1}^{f} = (A_{1}^{f}, P_{1}), A_{2}^{f} = (A_{2}^{f}, P_{2}), … of computable structures such that:

1. For each i the structure A_{i}^{f} is isomorphic to the structure G_{i}^{f}.

2. For each pair i ≠ j, A_{i}^{f} ⋂ A_{j}^{f} = ∅ and ω = ⋃_{i} A_{i}^{f}.

3. The relation P_{f} = ⋃_{i} P_{i} is computable.

Consider the computable structure A_{f} defined in some canonical way so that A_{f} is isomorphic to (ω, P_{f}). Note that the set of all cluster points of A_{f} is recursive in every recursive presentation of A_{f}. (We are here using the assumption that every set in the family S has at least two elements.) The following lemma describes the relationship between S and A_{f}.

Lemma 3.6 The structure A_{f} satisfies the following conditions.

1. If g is a one-to-one computable enumeration of S, then A_{f} is isomorphic to A_{g}.

2. The structure A_{f} is rigid, that is it does not have any nontrivial automorphisms.

3. If g is a one-to-one computable enumeration of S, then A_{f} is computably isomorphic to A_{g} if and only if f and g are equivalent.

4. The dimension of the structure A_{f} is equal to the maximal number of nonequivalent one-to-one computable enumerations of S.

5. The structure A_{f} has a Scott family if and only if S has a Scott sequence.

Proof. To prove 1, first, note that for any pair i, j ∈ ω the graphs G_{i}^{f} and G_{j}^{g} are isomorphic if and only if f(i) = g(j). Hence, since f and g are one-to-one enumerations of S, we can conclude that A_{f} is isomorphic to A_{g}.

Any automorphism α of A_{f} must be the identity by the construction of A_{f} and the fact that f is a one-to-one mapping. This proves 2.

Suppose that f and g are equivalent. There exists a recursive function Φ such that f = gΦ. Hence the structure G_{i}^{f} is isomorphic to the structure G_{Φ(i)}^{g}. Hence A_{f} and A_{g} are computably isomorphic. Let B be a computable presentation of A_{f}. Consider an effective sequence e_{0}, e_{1}, e_{2}, … without repetition of all cluster points in B. We define a one-to-one computable enumeration fB of S as follows:

fB(i) = {n|e_{i} belongs to a circle of length n}.

It follows that B is computably isomorphic to A_{g} if and only if g is equivalent to fB. This proves 3.

4 follows from the proof of 3.

We are left to prove the last part of the lemma. Suppose that S has a Scott sequence D_{0}, D_{1}, D_{2}, …. Without lost of generality we can suppose that D_{i} ⊂ f(i). We have to prove that A_{f} has a Scott family. Take an x ∈ A_{f}. Find a d_{i} which is connected to x via P_{f}. Suppose that the length of a path which connects x with d_{i} is n. Define the following formula: ψ(x) = [there exists a path of length n which connects x with a cluster point y such that for each m ∈ D_{i} the element y belongs to a cycle of length m]. Now for every s–tuple (x_{1}, …, x_{s}) let ϕ_{(x_{1},...,x_{s})} be ψ(x_{1})& … &ψ(x_{s}). It is not hard to check that the sequence {ϕ_{(x_{1},...,x_{s})}} is a Scott family for A_{f}.

Now suppose for simplicity that A_{f} has a Scott family

ϕ_{0}(x_{1}, …, x_{n_{0}}), ϕ_{1}(x_{1}, …, x_{n_{1}}), …

without parameters. The proof below will show that we do not lose any generality by making this assumption. Let d_{0}, d_{1}, d_{2} … be an effective sequence of all cluster points from A_{f}. Let

ϕ_{i_{0}}(x_{0}), ϕ_{i_{1}}(x_{1}), …

be an effective subsequence of the original sequence such that ϕ_{i_{k}}(d_{k}) holds for each k ∈ ω. Since the formulas are all existential and the structure is computable, we can effectively find a finite substructure B_{i} of A_{f} such that d_{i} ∈ B_{i} and ϕ_{i_{k}}(d_{k}) holds in B_{i}. Define

D_{i} = {n|d_{i} belongs to a cricle of length n in substructure B_{i}}.

Since we have a Scott family for A_{f} and since the structure A_{f} is rigid, we can see that the sequence D_{0}, D_{1}, … is a Scott sequence for family S. □

Corollary 3.7 Any two one-to-one computable enumerations of S are equivalent if and only if A_{f} is computably categorical. □

Now, to prove Theorem 3.1 it suffices, by lemma 3.6, to build a computably enumerable family S of sets without a Scott sequence any two computable one-to-one enumerations of which are equivalent.

Lemma 3.8 There is a computably enumerable family S of sets with no Scott sequence any two computable one-to-one enumerations of which are equivalent.

In order to build a such family S and its one-to-one enumeration f, we need to satisfy the following requirements:

D_{e} : F_{e} is not a Scott sequence for S,

R_{j} : g_{j} ≡ f or g_{j} is not a one-to-one enumeration of S,

where {g_{j}}_{j} is a computable sequence of all potential one-to-one enumerations of a family of sets, and {F_{e}}_{e} is a computable sequence of all potential Scott sequences for S. These requirements are similar to the requirements for constructing a computable structure as needed for Theorem 2.5 (see [2]). In fact, to construct such a family S, we essentially use the ideas from the proof of Theorem 2.5. A detailed proof of this lemma and similar results will appear in [12].

References

[1] D. Cenzer, J.Remmel, Polynomial Time vs Recursive Models, Ann. Pure and Appl. Logic 54, 1991.

[2] , P.Cholak, S. Goncharov, B.Khoussainov and R. Shore, On Recursively Categorical Models, in preparation.

[3] J. N. Crossley, ed., Aspects of Effective Algebra, Proceedings of a Conference at Monash University, 1979.

[4] Yu. Ershov and S. S. Goncharov, eds., Logic Notebook: Problems in Mathematical Logic, Novosibirsk University, 1986.

[5] A. Frölich and J. C. Shepherdson, Effective Procedures in Field Theory, Phil. Trans. Roy. Soc. London ser. A 248 (1956), 407-432.

[6] V. D. Dzgoev and S. S. Goncharov, Autostability of Models, Algebra i Logika 19 (1980), 45-58.

[7] S. S. Goncharov, The Problem of the Number Of Non-Self-Equivalent Constructivizations, Algebra i Logika 19 (1980), 621-539.

[8] V. Harizanov, Pure Recursive Model Theory, preprint, to appear in Handbook of Recursive Mathematics, Y. Ershov, S. Goncharov, A. Nerode, J. Remmel eds.

[9] L. Harrington, Recursively Presentable Prime Models, J. Symbolic Logic 39 (1973), 305-309.

[10] N. Khissamiev, On Strongly Constructive Models of Decidable Theories, Izvestia AN Kaz. SSR (1974), 83-84, 94.

[11] B. Khoussainov and A. Nerode, Automata Representable Structures, in Proceedings of Logic and Computational Complexity Conference, 1995, Springer-Verlag Lecture Notes in Computer Science, to appear.

[12] B. Khoussainov and R. Shore, Recursive Categoricity and Degree Spectra of Relations, in preparation.

[13] A. I. Mal‘cev , Constructive Algebras, Uspekhi Matem. Nauk 16 (1961), 3-60.

[14] T. Millar, Recursive Categoricity and Persistence, J. Symbolic Logic 51 (1986), 430-434.

[15] T. Millar, Abstract Recursive Model Theory, in Handbook of Recursion Theory, E. Griffor, ed., North-Holland, to appear.

[16] A. Nurtazin, Strong and Weak Constructivizations and Computable Families, Algebra i Logika 13 (1974), 311-323,364.

[17] M. O. Rabin, Computable Algebra, General Theory and Theory of Computable Fields, Trans. Am. Math. Soc. 95 (1960), 341-360.

[18] J. B. Remmel, Recursive Isomorphisms Types of Recursive Boolean Algebras, J. Symbolic Logic 46 (1981), 572-593.

[19] J. B. Remmel and J. N. Crossley, The Work of Anil Nerode: A Retrospective, in Logical Methods, J. N. Crossley, J. B. Remmel, R. A. Shore and M. E. Sweedler, eds., Birkhäuser, Boston, 1993, 1-91.