Applications of Kolmogorov Complexity to Computable
Model Theory∗
Bakhadyr Khoussainov†, Pavel Semukhin‡, Frank Stephan§

Abstract
In this paper we answer the following well-known open question in computable model
theory. Does there exist a computable not ℵ0 -categorical saturated structure with aunique computable isomorphism type? Our answer is affirmative and uses a construction
based on Kolmogorov complexity. With a variation of this construction, we also provide
an example of an ℵ1 -categorical but not ℵ0 -categorical saturated Σ01 -structure with aunique computable isomorphism type. In addition, using the construction we give an
example of an ℵ1 -categorical but not ℵ0 -categorical theory whose only non-computablemodel is the prime one.

1

Introduction

Our main interest in this paper concerns the existence of a computable not ℵ0 -categoricalsaturated structure with a unique computable isomorphism type. Structures with exactly one
computable isomorphism type are called computably categorical. All the known standard
examples of computably categorical structures are usually prime models (of their own theories)
or become prime in expansions by finitely many constants. For example, finitely generated
computable algebras, the rational numbers under the natural ordering, finite dimensional
vector spaces over computable fields and the ring of integers are computably categorical. There
are also pathological examples of computably categorical structures that fail to satisfy certain
natural properties (for example, existence of Scott families) exhibited by most computably
categorical structures [2, 6, 8]. One notes that these specifically constructed computably
categorical structures fail to be prime models in expansions by finitely many constants. In∗

B. Khoussainov and P. Semukhin were partially supported by Marsden Fund grant of New Zealand.
F. Stephan is supported in part by NUS research grant R252-000-212-112.
†
Department of Computer Science University of Auckland, Private Bag 92019, Auckland, New Zealand,
bmk@cs.auckland.ac.nz.
‡
Department of Computer Science University of Auckland, Private Bag 92019, Auckland, New Zealand,
pavel@cs.auckland.ac.nz.
§
National University of Singapore, Mathematical Institute, 2 Science Drive 2, Singapore 117543, Republicof Singapore, fstephan@comp.nus.edu.sg.

1

fact, the theories of these specifically constructed structures do not have saturated models
due to the fact that the theories have uncountably many types.
We need some of the main definitions from computable model theory. The languages andstructures we consider are all countable unless we tell otherwise. We also assume that weare working in a recursive language, that is, that the arity of each relation and function
symbol in the language is uniformly recursive. A structure is said to be computable if it
has universe ω and the open diagram of the structure forms a recursive set of formulas. A
structure is computably presentable if it has a computable isomorphic copy; such a copy
is called a computable presentation of the structure.
Two isomorphic computable structures are called computably isomorphic if there is acomputable isomorphism between these two structures. A computable structure is said tobe computably categorical if any two computable presentations of the structure are computably isomorphic. As mentioned above, finitely generated computable algebras, the rational
numbers under the natural ordering, finite dimensional vector spaces over computable fields
are computably categorical. In this paper we are mostly interested in computably categoricalstructures.
The concepts of computable structure and computable categoricity can naturally be extended
as follows. A structure is said to be a Σ01 -structure if it has universe ω and the open
positive diagram of the structure, that is the set of all open formulas without negations
true in the structure, forms a recursively enumerable set of formulas. A structure is Σ01 presentable if it is isomorphic to a Σ01 -structure. We stress that in the definition of a Σ01 structure it is explicit that the domain of the structure is ω. A Σ01 -structure is computably
categorical if any two Σ01 -presentations of the structure are computably isomorphic. Clearly,
every computable structure is also a Σ01 -structure. Therefore if a computable structure iscomputably categorical when one considers Σ01 -presentations, then all Σ01 -presentations of thestructure must be computable. Similarly, if a non-computable Σ01 -structure is computably
categorical then the structure does not have a computable presentation. We note, however,that we deal with computably categorical Σ01 -structures in Section 4 only.
We briefly recall some basic notions and facts from model theory. Let T be a complete theory.
A countable model of T is said to be prime if every tuple of the model realizes a principal
type. It is well-known that every prime model is elementarily embedded into all models of
T . A countable model of T is said to be saturated if the model realizes all the types of thetheory in all possible expansions of T by finitely many constants. It is well known that T has
a saturated model if and only if T has at most countably many countable models. Moreover,every other countable model of T is elementarily embedded into the saturated model (seeHodges’ or Marker’s textbooks on model theory [4, 5, 10]). An important model-theoretic
property of prime and saturated models of a given theory T , in case they exist, is that they
are unique up to isomorphisms. We address this uniqueness property of the saturated models
from a computability-theoretic point. Finally, we call a structure saturated (prime) if it is
the saturated model (the prime model) of its own theory.

2

Above we have already provided examples of computably categorical prime models. It is also
not hard to have natural examples of prime but not computably categorical models. For
instance, the natural numbers with their order is the prime and non-computably categorical model. However, in spite the fact that saturated models (of a given theory) form one
isomorphism type, all the known computable saturated models are not computably categorical. Roughly, the main reason for them not being computably categorical hides in using thefollowing model-theoretic fact. There exists an infinite sequence p(x0 ) ⊂ p(x0 , x1 ) ⊂ . . . ⊂p(x0 , x1 , . . . , xn ) ⊂ . . . of non-principal types such that each type in the sequence is realized
by infinitely many elements of the model. A simple example here is the theory of vector
spaces over the field of rational numbers. The non-saturated models of the theory are all
finite dimensional vector spaces. They are all computably categorical. The saturated modelis the infinite dimensional vector space. The saturated model is, however, not computably
categorical. This is because there are two computable copies of the infinite dimensional vector space such that in one copy the dependency problem is computable and in the other isnot. Similarly, all the non-saturated models of the theory of one successor are computably
categorical while the saturated model of the theory is not. The reason for this is that thesaturated model has two computable presentations such that in one the algebraic dependency
relation is computable and in the other is not.
Here is the outline of the paper. In the next section we construct a specific uniformly recursively enumerable family {Bx }x∈ω of subsets of natural numbers. The family is defined basedon the notion of Kolmogorov complexity. We also prove that some special enumerations of
the family are equivalent to each other via computable permutations.
In Section 3, we provide an example of a saturated not ℵ0 -categorical structure with exactly
one computable isomorphism type. The idea is to code the family {Bx }x∈ω from the previous
section into a saturated structure so that the computable copies of the structure induce thespecial enumerations of the family. The construction of the structure is based on the wellknown model theoretic construction of Fraı̈ssé limits.
In Section 4 of the paper we also address a question of Goncharov that asks if there exists
an ℵ1 -categorical but not ℵ0 -categorical saturated model that has unique computable isomorphism type. Recall that a first order theory T is called κ-categorical (for an infinite cardinalκ) if A ∼= B whenever A, B |= T and |A| = |B| = κ. Morley [11] proved that if T is categorical in some uncountably cardinality, then it is categorical in all uncountable cardinalities.
Therefore, any ℵ1 -categorical theory has a unique model of each uncountable cardinality. We
partially answer the question of Goncharov positively by providing a saturated ℵ1 -categoricalbut not ℵ0 -categorical saturated Σ01 -structure that has unique computable isomorphism type.
Unfortunately, the structure is not computable. Our constructions codes the family {Bx }x∈ω .
In Section 4, we provide an alternative proof of the main result in [7]. There an ℵ1 -categoricalbut not ℵ0 -categorical theory T is constructed such that all models of T but the prime one
are computable. Our construction is again based on coding the family {Bx }x∈ω into an ℵ1 categorical but not ℵ0 -categorical theory.

3

2

The Role of Kolmogorov Complexity

The first result is the construction of an auxiliary family of recursively enumerable sets
B0 , B1 , . . . with the following properties:• the finite members of this family occur only once each;• all infinite members are equal and occur infinitely often in every recursive enumerationof the family.
The construction goes as follows. Let U be a universal partial-recursive function in the sensethat for every further partial-recursive function ψ there is a constant c, such that for all x in
the domain of ψ there is a y 6 c(x + 1) with U(y) = ψ(x). Then the Kolmogorov complexity
C (based on U) of any number z is defined as
C(z) = min{log(x) : U(x) ↓ = z}where in this paper the logarithm log(x) is defined as the smallest natural number y with2y > x. The rationale behind this definition is that it should roughly invert exponentiation,
have the base 2 and avoid undefined places, proper fractions and irrational numbers. Notethat C(z) > log(z) for infinitely many z. The reader should consult standard textbooks[1, 9, 12, 13] for more information on Kolmogorov Complexity and Recursion Theory. The
family in question is now defined as follows.
Definition 2.1. Let A = {x : C(x) < log(x)} be the set of compressible or non-random
numbers. Define({x} ∪ {y ∈ A : y < log(x)} if x ∈
/ A;
Bx =
A
if x ∈ A.
The family B0 , B1 , . . . is uniformly recursively enumerable as {x} ∪ {y ∈ A : y < log(x)} ⊆ Bx
for all x and the set A is recursively enumerable. So a uniform enumeration of the Bx starts
with an enumeration of {x} ∪ {y ∈ A : y < log(x)} and later adds all other elements of A inthe case that x turns out to be an element of A.
Theorem 2.2. If E0 , E1 , . . . is a recursive enumeration of r.e. sets such that for every x there
is y with Ex = By , and for every y ∈/ A there is a unique x with By = Ex , then there is acomputable permutation f with By = Ef (y) for all y.
Proof. For every y ∈/ A there is a unique x with y ∈ Ex . As every y ∈ A satisfies y ∈ Ex foralmost all x, one has that there are infinitely many x with y ∈ Ex . Thus there is a computablefunction g such that y ∈ Eg(y) for all y, this function can be obtained by searching in parallelin all E0 , E1 , . . . until an x with y ∈ Ex is found.
If y ∈/ A then Eg(y) = By as By is the unique set in the enumeration B0 , B1 , . . . containingy. Thus Eg(y) has to be equal to By . If y ∈ A and Eg(y) = A then By = Eg(y) . If y ∈ A
but Eg(y) = Bx for some x ∈/ A then y < log(x) and x is the unique element of Eg(y) , which4

is larger than log(x). Thus one can compute x from y and log(x). As Cantor’s pairing
function is invertible, one can compute x also from (y + log(x))(y + log(x) + 1)/2 + log(x).
As y < log(x), the logarithm of this expression is roughly 2 log log(x). So, on one hand, there
is a constant c1 with C(x) 6 2 log log(x) + c1 . On the other hand, log(x) 6 C(x). Therefore,log(x) 6 2 log log(x)+c1 and hence there are only finitely many such x. Thus it follows that g,
for all but finitely many y, satisfies Eg(y) = By . Since the errors occur on finitely many y ∈ A,
the other elements of A are mapped to an Ex with Ex = A. By modifying g at finitely many
places, one even obtains ∀y (Eg(y) = By ). Note that A occurs in the enumeration E0 , E1 , . . .
infinitely often as A is not computable and cannot be of the form g −1 (D) for any finite set D.
Now let I be an infinite computable subset of A which includes all y satisfying the condition
g(y) ∈ {g(z) : z < y}. Furthermore, let x be any index. If Ex = By for an y ∈/ A, then one
can compute y from x by inverting g and thus C(y) 6 C(x) + c2 for some constant c2 . As y is
incompressible, log(y) 6 C(x) + c2 6 log(x) + c3 for some constant c3 . Thus one knows thatwhenever x 6= g(y) for all y with log(y) 6 log(x) + c3 then Ex = A. So the set of all x with
Ex = A is recursively enumerable: Ex = A iff either g(y) = x for some y ∈ A or g(y) 6= x forthe finitely many y with log(y) 6 log(x) + c3 . In particular there is an infinite computable
set J such that Ex = A for all x ∈ J and J ∪ g(N) = N.
Now define f (y) to be the n-th element of J whenever y is the n-th element of the computable
set I ∪ g −1(J) and let f (y) = g(y) otherwise. Again Ef (y) = By for all y as f coincides withg on those y where By is finite while f is modified from one index of A to another one in thecase that y ∈ I ∪ g −1(J). Furthermore, by construction, f is a permutation. It is also easy to
see that f is computable.

3

The first application

Our main result in this section is the following theorem.
Theorem 3.1. There exists a saturated not ℵ0 -categorical model that has a unique computableisomorphism type.
We need to recall the construction of Fraı̈ssé limits. Let K be a class of finite structures
closed under isomorphisms. We assume the language of structures is finite and contains only
relational symbols. Assume that the class K has the following properties:
1. Hereditary property (HP): for all A ∈ K, if B is a substructure of A then B ∈ K.
2. Joint embedding property (JEP): for all A, B ∈ K there exists a C ∈ K, such that A
and B can be embedded into C.
3. Amalgamation property (AP): for all A, B, C ∈ K, if f : A → C and g : A → B are
embeddings then there exists a structure D ∈ K and embeddings h : B → D andk : C → D such that hf = kg on A.
A structure D is called weakly homogeneous if it has the property
5

if A, B are finite substructures of D, A ⊆ B and f : A → D is an embedding,then there is an embedding g : B → D which extends f .
A structure is called ultrahomogeneous if any finite partial isomorphism of the structure
into itself can be extended to an automorphism. A finite or countable structure is ultrahomogeneous if and only if it is weakly homogeneous (see Lemma 7.1.4(b) in [4]).
The age of a structure D is the class of all finite structures embeddable in D. There is a wellknown result in model theory that connects the ultrahomogeneous structures with classes K
that possess properties HP, JEP and AP. It is stated in the following theorem:
Theorem 3.2. For any class K that has HP, JEP and AP there exists a unique at mostcountable ultrahomogeneous structure lim(K) whose age coincides with K. Moreover, thestructure lim(K) is ℵ0 -categorical.
The structure lim(K) is called the Fraı̈ssé limit of the class K. We restate this theorem withan eye towards computable categoricity:
Theorem 3.3. Let K be a class finite structures with the following properties.
1. K has properties HP, JEP and AP.
2. There exists a sequence H0 , H1 , . . . such that
• {Hn | n ∈ ω} ⊆ K and each A ∈ K is isomorphic to some Hn ;• the domain and the atomic diagram of Hn is computable uniformly in n;• the function n 7→ |Hn | is computable.
Then the Fraı̈ssé limit of K is a computably categorical structure.
Proof. First, show that the Fraı̈ssé limit of K is computable. Let {(Ai , Bi )}i∈ω be a recursive
enumeration of pairs of structures from K such that Ai ⊆ Bi , and for every pair A, B ∈ Ksuch that A ⊆ B there exist i and an isomorphism f : B → Bi such that f (A) = Ai . We
now construct a computable structure D as follows. Let D0 = H0 . Suppose that Dk has been
constructed. Applying the AP property the required number of times one can show that there
is an isomorphic copy Hn0 of some Hn ∈ K such that Dk ⊆ Hn0 and for all i 6 k, if Ai can beembedded in Dk then for every embedding f : Ai → Dk , there is an embedding g : Bi → Hn0
extending f . For every n, we can effectively check whether there is a copy of Hn satisfying thecondition above. So let Dk+1 be an isomorphic copy of Hn with minimal index n satisfyingthat condition.
S
Now consider a computable structure D = k<ω Dk . Since each Dk is in K and K possesses
HP property, the age of D is included in K. Suppose A is in K; then by JEP there are
B ∈ K, such that D0 ⊆ B, and an embedding h : A → B. Now let a pair (Ai , Bi ) be suchthat there is an isomorphism f : Bi → B with f (Ai ) = D0 . By construction, the embeddingf  Ai : Ai → D0 extends to an embedding g : Bi → D. Hence both B and A are in the ageof D. Therefore, the age of D is exactly K.
6

Let A ⊆ B be finite substructures of D and h : A → D be an embedding. Since A, B ∈ K,
there are a pair (Ai , Bi ) and an isomorphism f : Bi → B with f (Ai ) = A. Furthermore,
there is k > i such that hf  Ai is an embedding of Ai into Dk . By construction, hf  Ai
extends to an embedding g : Bi → Dk+1 . Now gf −1 : B → D is an embedding that extends
h. This proves that D is weakly homogeneous and, therefore, ultrahomogeneous. Thus D is
the Fraı̈ssé limit of the class K.
We now show that D is computably categorical. Let D 0 be a computable structure isomorphic
S
to D; then there is a computable chain {Dk0 }k<ω of finite structures such that D 0 = k<ω Dk0 .
We construct a computable isomorphism from D to D 0 as follows. Let f0 be an embeddingof D0 into D 0 . Suppose that a finite partial embedding fn has been constructed. If n = 2m
then look for the smallest k > m, such that Dom(fn ) ⊆ Dk . Since D 0 is weakly homogeneous,
there is an embedding g : Dk → D 0 that extends fn and that can be found effectively. So let
fn+1 = g. If n = 2m + 1 then look for the smallest k > m, such that Im(fn ) ⊆ Dk0 . Since D isweakly homogeneous,
there is an embedding g : Dk0 → D that extends fn−1 . So let fn+1 = g −1 .
S
Thus f =fn : D → D 0 is a computable isomorphism.
n<ω

Now we define special classes of finite structures that have properties HP, JEP and AP. A
cycle of length n > 3 is the graph Cn = ({1, . . . , n}, E) with E = {(1, 2), (2, 1), (2, 3), (3, 2),. . ., (n − 1, n), (n, n − 1),(n, 1), (1, n)}. We say that a graph contains a cycle of length n if
there exists an embedding from Cn into the graph.
Let Y be a non-empty subset of natural numbers. Consider the following class of finite
directed graphs:
K(Y ) = {(V, E) | If (V, E) contains a cycle of length n + 3 then n ∈ Y }.
Lemma 3.4. The class K(Y ) possesses properties HP, JEP and AP.
Proof. It is easy to see that K(Y ) satisfies properties HP and JEP. We prove that K(Y )satisfies AP. Let A, B, C be graphs in K(Y ) such that A is a subgraph of B and C and thedomain of A is the intersection of the domains of B and C. Define the graph D as follows.
The domain of D is the union of domains of B and C. The graph D contains all the edges of
the graphs B and C. In addition, D contains all the edges of the form (b, c), where b ∈ B \ A
and c ∈ C \ A. It is not hard to see that the graph D built in this way belongs to K(Y ).
Now we construct the desired structure Cω as follows. To do this we use the family {Bx }x∈ωfrom the previous section. For each Bx consider the limit structure lim K(Bx ). One canconstruct a sequencelim K(B0 ), lim K(B1 ), lim K(B2 ), . . .
of these structures so that the following properties hold:1. the graphs in this sequence are all pairwise disjoint;
2. the union of domains of these graphs is ω;
7

3. the sequence is uniformly computable meaning that the set {(n, m) | m ∈ lim K(Bn )}is computable.
The signature of Cω consists of two binary relational symbols R and S. The domain of Cω isω. The relation R is the union of all edges of graphs that appear in the sequence above. The
relation S consists of all pairs (n, m) such that n, m belong to the same graph lim K(Bx ) forsome x. Clearly S is a computable equivalence relation. Thus, the structure Cω constructed
is computable. Our goal now is to show that Cω satisfies the theorem stated in the beginningof this section.
Lemma 3.5. The structure Cω is computably categorical.
Proof. Let D be any computable structure isomorphic to Cω . Since the equivalence relation
S in D is computable, there is a computable sequence {xi }i∈ω , which consists of exactly one
representative for each S-equivalence-class. Let Ei be a set such that the substructure of Dwith domain [xi ]S , S-equivalence-class of xi , is isomorphic to lim K(Ei ). Using the fact that D
is computable, one can show that the sequence {Ei }i∈ω is uniformly recursively enumerable.
Furthermore, for every x there is y with Ex = By , and for every y ∈/ A there is a unique x with
By = Ex . Thus, by Theorem 2.2, there is a computable permutation f such that Bi = Ef (i)for all i. By Theorem 3.3, lim K(Bi ) is a computably categorical structure. Note that theconstruction of the computable isomorphism between lim K(Bi ) and lim K(Ef (i) ) can be done
uniformly in i. Therefore, D is computably isomorphic to Cω .
Let T = Th(Cω ) be the first-order theory of Cω . Our goal is to show that Cω is the saturated
model of T . This is proved in the Lemma 3.6 below that also characterizes the isomorphism
types of the models of T . Call an S-equivalence-class non-standard if the restriction of R
to this class is isomorphic to the Fraı̈ssé limit lim K(A). Consider a subsequencelim K(Bn0 ), lim K(Bn1 ), lim K(Bn2 ), . . .
of the sequencelim K(B0 ), lim K(B1 ), lim K(B2 ), . . . ,where n1 , n2 , . . . is the list of all numbers outside of A in the increasing order. Consider thesubstructure of Cω restricted to the subsequence above and denote it by C0 . Let Cn be thestructure obtained by adjoining to C0 exactly n copies of non-standard S-equivalence-classes.
Lemma 3.6. The theory T satisfies the following properties.
1. C0 is the prime model of T .
2. The class of all countable models of T is {C0 , C1 , C2 , . . . , Cω }.
3. Cω is the saturated model of T .

8Proof. Let us write down the axioms for T . First, note that the fact that x and y lie inthe same component lim K(Bn ) of Cω can be expressed by a first-order formula. Indeed, letx, y ∈ lim K(Bn ) for some n. Suppose that there is no edge from x to y and from y to x. Let B
be the substructure of lim K(Bn ) with domain {x, y}. Let D be a graph with domain {x, y, z}that extends B and contains additional edges (x, z), (z, y). Note that D is in K(Bn ) since itdoes not contain any cycle. By the weakly homogeneity of lim K(Bn ), there is an embeddingof D into lim K(Bn ) that extends the identity map on B. Therefore, we can express the factthat x, y belong to the same lim K(Bn ) by the formulaϕ(x, y) = R(x, y) ∨ R(y, x) ∨ ∃z(R(x, z) ∧ R(z, y)).
We use the notation {c̄} for the set consisting of elements of the tuple c̄. Let ψ n (x0 , . . . , xn−1 )be a formula such that for any graph B
B |= ψ n (b̄) if and only if {b̄} is a cycle of length n in B.
For any graph B and n-tuple of distinct elements b̄ such that B = {b̄} let ψB,b̄ (x0 , . . . , xn−1 )be a conjunction of formulas R(xi , xj ) or ¬R(xi , xj ) satisfied by b̄ in B. Thus for any graph
D and a tuple d¯ ∈ D of the same length as b̄,¯ iff there is an isomorphism from B to {d}¯ which takes b̄ to d.
¯
D |= ψB,b̄ (d)Let Sn (x) be a formula that says the S-equivalence-class of x contains a cycle of length n + 3,
that is^n+3
Sn (x) = ∃ȳ ψ (ȳ) ∧S(x, yi ) .
i6n−1

VWe also use an abbreviation x̄ ∈ Sn for a formula
Sn (xi ) and x̄ ∈ [z] for a formulai6n−1
VS(xi , z), where x̄ = x0 , . . . , xn−1 . Let U be the following list of axioms.
i6n−1(Ax0 ) S is an equivalence relation.

(Ax1 ) S(x, y) → R(x, y) ∨ R(y, x) ∨ ∃z(R(x, z) ∧ R(z, y)).
For every n:(Ax2n )

^¬S(x, y) → ¬∃x0 , . . . , xn+1 x0 = x ∧ xn+1 = y ∧ (R(xi , xi+1 ) ∨ R(xi+1 , xi )) .
i6n

For every n ∈/ A:(Ax3n ) ∃x (Sn (x) ∧ ∀y (Sn (y) → S(x, y))).
For every n ∈/ A, every B, D ∈ K(Bn ) and every tuple b̄d of distinct elements such that
B = {b̄} and D = {b̄d}:(Ax4n,B,D,b̄d ) (∀x̄ ∈ Sn ) (ψB,b̄ (x̄) → (∃y ∈ Sn ) ψD,b̄d (x̄, y)).
If b̄ is empty then this sentence reduces to (∃y ∈ Sn ) ψD,d (y).
For every n ∈/ A:
9(Ax5n ) (∀x̄ ∈ Sn )_

ψB,b̄ (x̄),

B,b̄where the disjunction ranges over all pairs B, b̄ such that B ∈ K(Bn ) and b̄ is a tuple of thesame length as x̄ with B = {b̄}. Note that this disjunction is finite.
For every B, D ∈ K(A) and every tuple b̄d of distinct elements such that B = {b̄} andD = {b̄d}:
 ^


6
(AxB,D,b̄d ) ∀z
¬Sni (z) → (∀x̄ ∈ [z]) (ψB,b̄ (x̄) → (∃y ∈ [z]) ψD,b̄d (x̄, y)) ,i6k−1

where n0 , . . . , nk−1 are the indices of all components lim K(Bn ) of Cω into which D can not
be embedded. Note that ni ∈/ A for all i 6 k − 1. If b̄ is empty then this sentence reduces to
 ^


∀z
¬Sni (z) → (∃y ∈ [z]) ψD,d (y) .
i6k−1

Now let M be a countable model of U. Axioms Ax0 , Ax1 and Ax2n imply that S is anequivalence relation and that every S-equivalence-class is a connected component of M. For
every n ∈/ A, Ax3n states that there is a unique component that contains a cycle of length n.
Denote this component by Mn .
When b̄ is empty, Ax4n says that every one-element structure in K(Bn ) is embeddable in Mn .
In general, Ax4n says that
if B, D are finite structures in K(Bn ), D comes from B by adding one more element
and f : B → Mn is an embedding, then there is an embedding g : D → Mn which
extends f .
Now, using induction on the number of elements, it is not hard to see that every structure inK(Bn ) is embeddable in Mn . On the other hand, Ax5n implies that any finite substructure of
Mn is in K(Bn ). Thus, the age of Mn is exactly K(Bn ).
Using Ax4n again and an induction on the size of D \ B, we can show that
if B, D ∈ K(Bn ), B ⊆ D and f : B → Mn is an embedding, then there is anembedding g : D → Mn which extends f .
Thus Mn is a weakly homogeneous (hence ultrahomogeneous) model of age K(Bn ). Therefore,
Mn is isomorphic to lim K(Bn ). Note that, in particular, it means that Mn 6= Mk whenevern 6= k.
Let M ∗ be a connected component of M that is different from all Mn ’s. As shown above, any
cycle of length n, for n ∈/ A, can appear only in Mn . So the age of M ∗ is included in K(A).
Let D be one-element structure in K(A); then Ax6 implies that D is embeddable in M ∗ .
Now let B, D ∈ K(A), D comes from B by adding one more element and f : B → M ∗ is anembedding. Suppose that D is not embeddable in lim K(Bn0 ), . . . , lim K(Bnk−1 ), where ni ∈/A
6
for all i 6 k − 1. In this case Ax states that the embedding of B into any component of M
10other than Mn0 , . . . , Mnk−1 can be extended to an embedding of D into the same component.
In particular, f can be extended to an embedding g : D → M ∗ . Now, using induction on thesize of D, it is not hard to show that every D ∈ K(A) is embeddable in M ∗ . Thus the age ofM ∗ is exactly K(A).
Again, an induction on the size of D \ B tells us that if B, D ∈ K(A), B ⊆ D and f : B → M ∗is an embedding, then there is an embedding g : D → M ∗ which extends f . Thus M ∗ is aweakly homogeneous structure of the age K(A) and, therefore, is isomorphic to lim K(A).
So any countable model of U consists of exactly one component isomorphic to lim K(Bn ), forn∈/ A, and finite or infinite number of components isomorphic to lim K(A). In other words,
the class of all countable models of U is {C0 , C1 , C2 , . . . , Cω }.
We now show that, for every i ∈ ω, Ci is elementary equivalent to Cω . To do this, we will use
the method of Ehrenfeucht–Fraı̈ssé games.
Definition 3.7. Let A, B be the structures of the same language L and let γ be an ordinal.
Then EF γ [A, B], the unnested Ehrenfeucht–Fraı̈ssé game of length γ on A and B,
is defined as follows. There are two players ∀ and ∃. The game is played in γ steps. At
the ith step of the play, player ∀ takes one of the structures A, B and chooses an elementof this structure; then player ∃ chooses an element of the other structure. Each player isallowed to see and remember all previous moves in the play. At the end of the play, sequencesā = (ai : i < γ) ∈ A and b̄ = (bi : i < γ) ∈ B have been chosen. The pair (ā, b̄) is known as
the play. We say that player ∃ wins the play (ā, b̄) iff
for every unnested atomic formula ϕ of L, A |= ϕ(ā) ⇔ B |= ϕ(b̄).
Note that if the language L contains no function symbols or constants, as in our case, thenevery formula of L is unnested. We write A ≈γ B to mean that player ∃ has a winning
strategy for the game EF γ [A, B].
Theorem 3.8. Let L be a finite first-order language. Then for any two L-structures A and
B the following are equivalent.
(I) A ≡ B.
(II) For every k < ω, A ≈k B.
For the proof and more details, see chapters 3.2 and 3.3 in Hodges [4]. So let us fix any i andk and show that player ∃ has a winning strategy for the game EF k [Ci , Cω ].
The strategy for player ∃ that is described below has the following property. In the beginningof every step s, the sequences ās−1 = (a0 , . . . , as−1 ), b̄s−1 = (b0 , . . . , bs−1 ) have been chosen
by players ∀ and ∃ such that the substructures {ās−1 } and {b̄s−1 } of Ci and Cω respectively
are isomorphic via isomorphism that maps ās−1 to b̄s−1 . Moreover, for every t < s, if at ∈lim K(Bn ) and bt ∈ lim K(Bm ), then either(a) n ∈/ A, log(n) 6 k − 3 and n = m, or
11

(b) n ∈/ A ⇒ k − 3 < log(n) and m ∈/ A ⇒ k − 3 < log(m).
In both cases, we have that Bn ∩ [0, k − 3] = Bm ∩ [0, k − 3] and, therefore, any substructureof lim K(Bn ) with at most k elements is embeddable in lim K(Bm ) and vice versa.
Now suppose that at step s player ∀ has chosen as ∈ Ci . Then player ∃ chooses bs ∈ Cωsuch that the substructures {ās } and {b̄s } are isomorphic via isomorphism that maps ās tob̄s . Also, if as lies in the same component as at for some t < s, then bs has to be in the same
component as bt . The fact that |ās | 6 k ensures that player ∃ can always find such bs . If thecomponent of as does not contain any at for t < s, then player ∃ chooses bs such that bs is notin any component containing any bt for t < s and that property (a) or (b) given above holds
for the pair as , bs . Obviously, player ∃ can always find such a component, because there areinfinitely many components in both Ci and Cω that are isomorphic either to lim K(A) or tolim K(Bn ) for n ∈/ A and k < log(n).
The case when player ∀ has chosen bs ∈ Cω is similar to the above.
Now it is not hard to see that this strategy is indeed a winning strategy for player ∃. Thus all
the structures C0 , C1 , . . . , Cω are elementary equivalent to each other and U is the set of axioms
for T = Th(Cω ). Since T has countably many countable models, T has countable saturated
model and a prime model (see e.g. Corollary 4.3.8 in Marker [10]). None of {Ci : i < ω} canbe a saturated model, because Cω is not embeddable in any Ci. So we can conclude that Cω
is in fact the saturated model of T .

4

The second application

Here we partially answer the question of Goncharov about the existence of an ℵ1 -categoricalbut not ℵ0 -categorical structure with a unique computable isomorphism type. Here our answer
is affirmative if one considers Σ01 -structures rather than computable structures. Here is theresult.
Theorem 4.1. There is a ℵ1 -categorical but not ℵ0 -categorical theory whose saturated model
is a computably categorical Σ01 -structure.
Proof. We use the family {Bx }x∈ω constructed in Section 2. The language of the desired
structure is given by the family P0 , P1 , . . . of unary predicates. Define the following structure
M. The domain of the structure is the set of natural numbers. For each x, Py (x) holds iff
y ∈ Bx . Obviously, the structure is Σ01 .
Let T be the first-order theory of M. It can be described by the following set of axioms.
For every i ∈/ A:(Ax1i ) There is a unique z such that Pi (z).
For i ∈/ A, let ci be a new constant interpreted as an element on which Pi holds. The axioms
1
Axi imply that these constants are definable in the original language.
12

For every i ∈ A:^
(Ax2i )¬Pi (cj ) ∧ ∀z
{j: i∈B/ j}^{j: i∈B/ j}z 6= cj → Pi (z) ,that is Pi holds almost everywhere and does not hold only on constants cj for i ∈/ Bj . Notethat if i ∈ A, then the set {j : i ∈/ Bj } is finite; thus the conjunctions in Ax2i are finite, andthis is the first order formula.
The theory T is not ℵ0 -categorical since the prime model is given by the substructure of M
with domain N − A. The theory T is ℵ1 -categorical since any model of cardinality κ > ℵ0
consists of the following elements:• one element x with B = {n | Pn (x)}, for every finite set B in the enumeration {By }y∈ω ;• κ many elements x with A = {n | Pn (x)}.
The statement about Σ01 -categoricity can be derived by considering any further Σ01 -model M 0with domain N that is isomorphic to M; such a model defines a computable enumeration
E0 , E1 , . . . with n ∈ Ey ⇔ Pn (y). It is easy to see that every Bx with x ∈/ A appears inthis enumeration only once and that every Ey equals some Bx . By Theorem 2.2, there exists
a computable permutation f such that Ef (x) = Bx for all x. This computable permutation
clearly induces a computable isomorphism between two Σ01 -structures M and M 0 .

5

The third application

Khoussainov, Nies and Shore [7] give an example of ℵ1 -categorical but not ℵ0 -categoricaltheory such that all models of the theory but the prime model are computable. In thissection we provide an alternative proof of this result using the family {Bx } constructed in thesecond section.
To code this type of family, we generalize the notion of “cubes” introduced by Khoussainov,Nies and Shore [7]. Fix a language L consisting of binary relation symbols Fn (for n ∈ ω), all ofwhich we will assume to be symmetric and irreflexive relation coding the edges of a hypercube.
These cubes are constructed from given r.e. parameters sets X and have dimension |X|; foreach element n of the set X, the edges along one dimension are realized by the relation Fn .
More formally, this is done as follows.
Forof the default presentation of an X-cube be a set
P any subset X of ω, let the domain P{ m∈Y 2m : Y ⊆ X ∧ Y is finite} with m∈∅ 2m = 0. On this domain, define the relation
Fn (x, y) to be true iff there is a finite subset Y ⊆ X − {n} such thatPP
{x, y} = { m∈Y 2m , m∈Y ∪{n} 2m }.
An X-cube is then a structure isomorphic to the default presentation that we have justdefined. Note that every default presentation of an X-cube is uniformly Σ01 in X.
13

For example, a {0, 1, 3}-cube is an isomorphic copy of {0, 1, 2, 3, 8, 9, 10, 11} together with therelations F0 (0, 1), F0 (2, 3), F0 (8, 9), F0 (10, 11), F1 (0, 2), F1 (1, 3), F1 (8, 10), F1 (9, 11), F3 (0, 8),
F3 (1, 9), F3 (2, 10), F3 (3, 11). Other relations than these do not hold between the members ofthe {0, 1, 3}-cube.
|X|

Alternatively, an X-cube can be defined as follows (for example, see [3]). Consider A = Z2
as a vector space over Z2 , with basis {a0 , . . . , a|X|−1 }. Let f : X → |X| be a bijection. If, forevery n ∈ X and every x, y ∈ A, we define Fn (x, y) ⇔ x + af (n) = y, then every structure
isomorphic to A will be an X-cube.
Definition 5.1. Let the set A and the sequence B0 , B1 , . . . of sets as in Definition 2.1. Let
C0 be the disjoint union of all those Bx -cubes with x ∈/ A. Furthermore, let Cn be the disjoint
union of C0 and n many A-cubes for n ∈ {1, 2, 3, . . . , ω}.
Note that Cω is isomorphic to the disjoint union over all Bx -cubes for x ∈ ω.
Proposition 5.2. The structures C0 , C1 , C2 , . . . , Cω have all the same theory T ; this theory is ℵ1 -categorical, C0 is its prime model and Cω is its saturated model. The models
C0 , C1 , C2 , . . . , Cω are the only countable models of T up to isomorphism.
To prove this proposition we can consider the theory T = Th(Cω ) and formulate the list
U of its axioms. One group of axioms should say that the models of T consist of cubes.
Furthermore, for every x ∈ A, we need an axiom saying that Fx is adjacent to all but nx
nodes, where nx is the number of nodes in Cω that are not adjacent to Fx . Similarly, for everyx∈/ A, we need an axiom saying that Fx is adjacent only to nx many nodes, where nx is thenumber of nodes in Cω that are adjacent to Fx . Now one can show that C0 , C1 , C2 , . . . , Cω
are all countable models of U and all models of U of the same uncountable cardinality are
isomorphic. This implies that the theory determined by U is complete and U is indeed theset of axioms for T . More details can be found in the proof of Theorem 4.1 in [3].
Theorem 5.3. The models C1 , C2 , . . . , Cω have all computable presentations but C0 does nothave a computable presentation.
Proof. This is clear for Cω as there is a recursive one-one enumeration (a0 , b0 ), (a1 , b1 ), . . .
of pairs such that for each x the set {a : ∃s [as = a ∧ bs = x]} is the domain of the default
presentation of the Bx -cube from above. Then one defines for the given presentation thatFn (s, t) holds iff bs = bt and Fn (as , at ) in the default presentation of the Bbs -cube. It is easy
to see that the given model is computable and isomorphic to Cω .
We now describe how to construct a computable presentation for C1 . Fix some x0 ∈ A
and start the construction by enumerating all Bx -cubes in some effective way. Also we start
enumerating the set A. When at some stage s a number x is enumerated into As , we expand
the finite part of Bx0 -cube constructed so far and merge the finite part of Bx -cube into it. To
do this we might need to use new edges Ft with t ∈ A such that up to stage s it has not been
decided for any two nodes a, b whether Ft (a, b) holds or not. So we keep on enumerating A
until we have enough of such edges. To build a computable presentation for Cn with 2 6 n < ω
one need to add n − 1 computable copies of an A-cube to the computable presentation of C1 .
14

Now assume by contradiction that the prime model C0 also has a computable presentation.
Then there is a computable function mapping every n to a triple (a(n), b(n), y(n)) such that
2n < y(n) ∧ Fy(n) (a(n), b(n)). This function is total as there are infinitely many x > 2n suchthat x ∈/ A and a copy of Bx is merged into C0 . Let x(n) denote the index of the Bx(n) -cube
to which a(n) belongs. Note that Bx(n) is finite as C0 is the prime model. Note that x(n) ∈/ A,
x(n) > y(n) and C(x(n)) > log(x(n)). Now x(n) can be computed from n and log(x(n)) asx(n) is the only number z larger than log(x(n)) such that there is an d with Fz (a(n), d); sox(n) can be found by exhausting search once log(x(n)) and n are given. As n 6 log(x(n)),
C(x(n)) 6 C(log(x(n)), n) + c 6 2 log log(x(n)) + c0 for constants c, c0 and all n. Combining
the two conditions, one has log(x(n)) 6 2 log log(x(n)) + c0 for all n. But this is impossible
as x(n) > 2n for all n. Thus C0 cannot have a computable presentation.

References[1] Cristian Calude, Information and randomness: an algorithmic perspective, Springer,
Berlin, 2002.
[2] Peter Cholak, Richard Shore and Reed Solomon, A computably stable structure with no
Scott family of finitary formulas, Archive of Mathematical Logic, to appear.
[3] Denis Hirschfeldt, Bakhadyr Khoussainov and Pavel Semukhin, An uncountably categorical theory whose only computably presentable model is saturated, Notre Dame Journalof Formal Logic, 47:63–71, 2006.
[4] Wilfrid Hodges, Model Theory, Cambridge University Press, 1993.
[5] Wilfrid Hodges, A Shorter Model Theory, Cambridge University Press, 1997.
[6] Oleg V. Kudinov, An autostable 1-decidable model without a computable Scott familyof ∃-formulas, Algebra and Logic 35:255-260, 1996 (English translation).
[7] Bakhadyr Khoussainov, André Nies and Richard Shore, Computable models of theories
with few models, Notre Dame Journal of Formal Logic, 38:165-178, 1997.
[8] Bakhadyr Khoussainov and Richard Shore, Computable isomorphisms, degree spectraof relations and Scott families, Annals of Pure and Applied Logic, 91:1–15, 1998 and
98:297–298, 1999.
[9] Ming Li and Paul Vitányi, An introduction to Kolmogorov complexity and its applications,
Texts and Monographs in Computer Science, Springer, New York, 1993.
[10] David Marker, Model theory: an introduction, Springer, New York, 2002.
[11] Michael Morley, Categoricity in power, Transactions of the American MathematicalSociety, 114:514–538, 1965.
[12] Piergiorgio Odifreddi, Classical Recursion Theory, North-Holland, Amsterdam, 1989.
15

[13] Robert I. Soare, Recursively enumerable sets and degrees, Springer, Heidelberg, 1987.

16