The Journal of Symbolic Logic Volume 00, Number 0, XXX 0000

BARWISE: INFINITARY LOGIC AND ADMISSIBLE SETS

H. JEROME KEISLER AND JULIA F. KNIGHT

Contents

0. Introduction 1 1. Background on infinitary logic 2 1.1. Expressive power of L_{ω_{1}ω} 2 1.2. The back-and-forth construction 3 1.3. The Scott isomorphism theorem 4 1.4. ω-logic 7 1.5. Familiar theorems 8 1.6. Failure of compactness 9 2. Background on admissible sets 10 2.1. Δ_{0} formulas and Σ-formulas in set theory 10 2.2. Axioms of KP 11 2.3. Examples of admissible sets 12 2.4. The admissible set 𝕃(ω_{1}^{CK}) 12 3. Admissible fragments 14 3.1. Completeness and compactness 14 3.2. Computable structures via Barwise compactness 15 3.3. Other applications of Barwise compactness 16 4. Admissible sets over M 19 4.1. KP with urelements 19 4.2. Truncation lemma 20 4.3. Admissible sets above M 21 4.4. Inductive definitions 21 5. Saturation properties 23 5.1. Computable saturation 23 5.2. Σ_{A}-saturation 26 6. Conclusion 27

§0. Introduction. In [15], Barwise described his graduate study at Stanford. He told of his interactions with Kreisel and Scott, and said how he chose Feferman as his advisor. He began working on admissible fragments of infinitary logic after reading and giving seminar talks on two Ph.D. theses which had recently been

\begin{matrix}c \\ ◯ \end{matrix} 0000, Association for Symbolic Logic 0022-4812/00/0000-0000/$00.00

completed: that of Lopez-Escobar, at Berkeley, on infinitary logic [45] (see also the papers [46], [47]), and that of Platek [57], at Stanford, on admissible sets.

Barwise’s work on infinitary logic and admissible sets is described in his thesis [3], the book [12], and papers [4]—[15]. We do not try to give a systematic review of these papers. Instead, our goal is to give a coherent introduction to infinitary logic and admissible sets. We describe results of Barwise, of course, because he did so much. In addition, we mention some more recent work, to indicate the current importance of Barwise’s ideas. Many of the central results are stated without proof, but occasionally we sketch a proof, to indicate how the ideas fit together.

Chapters 1 and 2 describe infinitary logic and admissible sets at the time Barwise began his work, circa 1965. From Chapter 3 on, we survey the developments that took place after Barwise appeared on the scene.

§1. Background on infinitary logic. In this chapter, we describe the situation in infinitary logic at the time that Barwise began his work. We need some terminology. By a vocabulary, we mean a set L of constant symbols, and relation and operation symbols with finitely many argument places. As usual, by an L-structure M, we mean a universe set M with an interpretation for each symbol of L. In cases where the vocabulary L is clear, we may just say structure.

For a given vocabulary L and infinite cardinals μ ≤ κ, L_{κμ} is the infinitary logic with κ variables, conjunctions and disjunctions over sets of formulas of size less than κ, and existential and universal quantifiers over sets of variables of size less than μ. All logics that we consider also have equality, and are closed under negation. The equality symbol is always available, but is not counted as an element of the vocabulary L.

As usual, ω is the first infinite ordinal, and ω_{1} is the first uncountable ordinal. Thus, L_{ωω} is the ordinary elementary first order logic, with finite conjunctions, disjunctions, and quantifiers. Formulas in L_{ωω} are called finitary, or elementary. A set of finitary sentences, closed under logical consequence, is called an elementary first order theory. Another important case is the logic L_{ω_{1}ω}, which has ω_{1} variables, countable disjunctions and conjunctions, and finite quantifiers. The union of L_{κω} over all cardinals κ is the logic L_{∞ω}, which has a variable v_{α} for each ordinal α, conjunctions and disjunctions over arbitrary sets of formulas, and quantifiers over finite sets of variables. In this article, we will be concerned with L_{∞ω} and its sublanguages. We only allow formulas with finitely many free variables.

1.1. Expressive power of L_{ω_{1}ω}. Some mathematically interesting classes of structures, such as algebraically closed fields of a given characteristic, are characterized by a set of axioms in L_{ωω}. Other classes cannot be characterized in this way, but can be axiomatized by a single sentence of L_{ω_{1}ω}.

Example 1: The Abelian torsion groups are the models of a sentence obtained by taking the conjunction of the usual axioms for Abelian groups (a finite set) and the following further conjunct:

(∀x) ⋁_{n} \underbrace{x + … + x}_{n} = 0 .

In [17], Barwise and Eklof made a serious study of these groups, using infinitary sentences to express natural mathematical invariants.

Example 2: The Archimedean ordered fields are the models of a sentence obtained by taking the conjunction of the usual axioms for ordered fields and the following further conjunct:

(∀x) ⋁_{n} \underbrace{1 + … + 1}_{n} > x .

Example 3: Let L be a countable vocabulary. Let T be an elementary first order theory, and let Γ(\overline{x}) be a set of finitary formulas in a fixed tuple of variables \overline{x}. The models of T that omit Γ are the models of the single L_{ω_{1}ω} sentence obtained by taking the conjunction of the sentences of T and the following further conjunct:

(∀\overline{x}) ⋁_{γ∈Γ} ¬γ(\overline{x}) .

There are many natural examples of mathematical properties expressible in L_{ω_{1}ω}. Let α be a countable ordinal. In the vocabulary L = {≤} of orderings, there is an L_{ω_{1}ω} sentence whose models are just the orderings of type α, and there is an L_{ω_{1}ω} formula saying, in a linear ordering, that the interval to the left of x has type α. In a vocabulary appropriate for Boolean algebras, there is an L_{ω_{1}ω} sentence whose models are just the Boolean algebras of type I(ω^{α}), and there is an L_{ω_{1}ω} formula saying, in a Boolean algebra, that x is an α-atom. In a vocabulary appropriate for groups, there is an L_{ω_{1}ω} formula saying, in an Abelian p-group, that x has height α.

There are limits to the expressive power of L_{ω_{1}ω}. Morley [50], and Lopez-Escobar [47] showed that the class of well orderings is not definable in L_{ω_{1}ω}.

Theorem 1.1.1 (Morley, Lopez-Escobar). If σ is an L_{ω_{1}ω} sentence true in all countable well orderings, then σ has a model with a subset of order type η—the order type of the rationals.

1.2. The back-and-forth construction. One of the earliest and most powerful tools in infinitary logic is the back-and-forth construction. This was first used by Cantor to prove that every countable dense linear ordering without endpoints is isomorphic to the rationals. Back-and-forth constructions were developed as a general method in finitary logic by Ehrenfeucht and Fraïssé, and in infinitary logic by Karp. Barwise’s paper [9] gives a beautiful exposition of their role in infinitary logic.

Let M, N be structures with universes M, N, respectively. A partial isomorphism from M to N is a pair of tuples (\overline{a}, \overline{b}), of the same finite length, such that \overline{a} is from M, \overline{b} is from N, and \overline{a} and \overline{b} satisfy the same quantifier-free formulas. We will sometimes add new constant symbols to the vocabulary, and we note that (\overline{a}, \overline{b}) is a partial isomorphism from M to N if and only if the empty pair (∅, ∅) is a partial isomorphism from (M, \overline{a}) to (N , \overline{b}). A back-and-forth family for M, N is a set F of partial isomorphisms from M to N such that:

• F ≠ ∅,

• for each (\overline{a}, \overline{b}) ∈ F and c ∈ M, there exists d ∈ N such that (\overline{a}c, \overline{b}d) ∈ F,

• for each (\overline{a}, \overline{b}) ∈ F and d ∈ N, there exists c ∈ M such that (\overline{a}c, \overline{b}d) ∈ F. We say that two structures M and N, of arbitrary cardinality, are poten-

tially isomorphic if there is a back-and-forth family for M, N. It is obvious that isomorphic structures are potentially isomorphic. In the other direction, potentially isomorphic structures are very similar to each other, but are not necessarily isomorphic. For example, any two infinite structures with the empty vocabulary are potentially isomorphic. While two potentially isomorphic structures may not be isomorphic, Barwise [9] and Nadel [54] showed that they would become isomorphic if the set-theoretic world were extended in such a way as to collapse the cardinalities of both structures to ℵ_{0}. There is one special case where potential isomorphism does imply isomorphism. Using Cantor’s original argument, one can show that any two countable structures which are potentially isomorphic are isomorphic.

The link between back-and-forth constructions and infinitary logic is given by the following basic theorem of Karp [37].

Theorem 1.2.1 (Karp’s Theorem). Two structures are potentially isomorphic if and only if they satisfy the same sentences of L_{∞ω}.

Proof. For the implication from left to right, we first note that if F is a back-and-forth family witnessing the potential isomorphism of M and N and (\overline{a}, \overline{b}) ∈ F, then (M, \overline{a}) and (N , \overline{b}) are potentially isomorphic. Now, it is not difficult to show, by induction on complexity of formulas, that for all (\overline{a}, \overline{b}) ∈ F, M ⊧ φ(\overline{a}) iff N ⊧ φ(\overline{b}). For the implication from right to left, we define a backand-forth family F consisting of the pairs (\overline{a}, \overline{b}) such that the L_{∞ω} formulas satisfied by \overline{a} in M are the same as those satisfied by \overline{b} in N. Let (\overline{a}, \overline{b}) ∈ F, and let c ∈ M. We need d such that (\overline{a}c, \overline{b}d) ∈ F. For each d ∈ N such that (\overline{a}c, \overline{b}d) ∉ F, choose a formula φ_{d}(\overline{u}, x) satisfied by \overline{a}c in M but not by \overline{b}d in N. Let ψ(\overline{u}, x) be the conjunction of the formulas φ_{d}(\overline{u}, x). Since ∃x ψ(\overline{u}, x) is true of \overline{a} in M, it is true of \overline{b} in N. Taking d such that N ⊧ ψ(\overline{b}, d), we get (\overline{a}c, \overline{b}d) ∈ F. ⊣

For countable structures, Karp’s theorem has a simpler form.

Corollary 1.2.2. Two countable structures for a countable vocabulary L are isomorphic if and only if they satisfy the same sentences of L_{ω_{1}ω}.

1.3. The Scott isomorphism theorem. The following result of Scott [62] gives further evidence of the expressive power of L_{ω_{1}ω} for countable structures.

Theorem 1.3.1 (Scott Isomorphism Theorem). Suppose the vocabulary L is countable. Then for any countable L-structure M, there is an L_{ω_{1}ω} sentence θ such that the countable models of θ are just the isomorphic copies of M.

A sentence θ with the property in Theorem 1.3.1 is called a Scott sentence for M. We will first give a quick proof of Scott’s Theorem, and then give a longer proof which provides additional information. We need some definitions. Consider a countable structure M. For any tuple \overline{a} in M, the orbit of \overline{a} is the set of tuples \overline{b} such that some automorphism of M maps \overline{a} to \overline{b}. A partial isomorphism from M to M is called a partial automorphism of M. Note that if \overline{a} and \overline{b} are in the same orbit then (\overline{a}, \overline{b}) is a partial automorphism of M.

A Scott family for M is a set Φ of L_{∞ω} formulas such that for each tuple \overline{a} in M,

• There is some φ ∈ Φ such that M ⊧ φ(\overline{a}), and

• If φ ∈ Φ and M ⊧ φ(\overline{a}), then φ defines the orbit of \overline{a} in M—so, if φ ∈ Φ and M ⊧ φ(\overline{a}) & φ(\overline{b}), then \overline{a} and \overline{b} are in the same orbit.

In some settings, it is useful to allow a finite tuple of parameters in the formulas of a Scott family, in hopes of one that consists of formulas of a special form—e.g., finitary existential. In the definition above, we do not allow parameters, and we put no restrictions on the complexity of the L_{∞ω} formulas in the Scott family. In the case where the vocabulary and the structure are both countable, we can do better.

Lemma 1.3.2 (Scott). Let L be a countable vocabulary. Then each countable structure M has a countable Scott family of formulas in L_{ω_{1}ω}.

Proof of Lemma 1.3.2. Let \overline{a} be a tuple in M. For each tuple \overline{b} in M, of the same length as \overline{a}, if there is a formula of L_{ω_{1}ω} true of \overline{a} and not true of \overline{b}, we choose one, and we let φ\overline{a}(\overline{x}) be the conjunction of the chosen formulas. Let Φ be the set of these formulas— Φ = \{φ\overline{a}(\overline{x}) : \overline{a} in M\}. Since M is countable, Φ is a countable set of formulas of L_{ω_{1}ω}. Clearly, each tuple \overline{a} in M satisfies the formula φ\overline{a} ∈ Φ. Moreover, if φ ∈ Φ, then φ = φ\overline{a} for some tuple \overline{a} in M, and φ defines the set of all tuples which satisfy the same L_{ω_{1}ω} formulas as \overline{a} in M. By the corollary to Karp’s Theorem, this set is the orbit of \overline{a} in M. It follows that Φ is a Scott family for M. ⊣

Proof of Theorem 1.3.1. ¿From the Scott family Φ in Lemma 1.3.2, with φ\overline{a} defining the orbit of \overline{a}, we obtain a Scott sentence θ as follows. Let

θ_{∅} = (∀y) ⋁_{b} φ_{b}(y) & ⋀_{b}(∃y) φ_{b}(y)

(where the conjunctions and disjunctions are over all b ∈ M). More generally, for each tuple \overline{a} in M, let

θ\overline{a} = (∀\overline{x}) [φ\overline{a}(\overline{x}) → ( (∀y) ⋁_{b} φ_{\overline{a}b}(\overline{x}, y) & ⋀_{b} (∃y) φ_{\overline{a}b}(\overline{x}, y))] .

Then the desired Scott sentence is

θ = ⋀_{\overline{a}} θ\overline{a} .

⊣

The longer proof of Scott’s Theorem takes into account refinements due to Chang [25] and Nadel [54], and gives additional information. The formulas in the Scott family will be chosen in a canonical way, and are defined for uncountable as well as countable vocabularies and structures. The proof gives an ordinal, the Scott height of M, which provides a measure of model-theoretic complexity. To give an idea how the argument goes, we will break it into a series of definitions and easy lemmas whose proofs are left as exercises.

We first define the quantifier rank qr(φ) of a formula φ of L_{∞ω}. There is no prenex normal form for L_{∞ω} (in general, we cannot bring all of the quantifiers to the front), but the quantifier rank is a useful substitute. The definition is by induction on the complexity of formulas.

• If φ is atomic, then qr(φ) = 0,

• qr(¬φ) = qr(φ),

• qr(⋀ Φ) = qr(⋁ Φ) = sup_{φ∈Φ} qr(φ),

• qr((∃v) φ) = qr((∀v)φ) = qr(φ) + 1.

We write M ≡_{α} N if M and N satisfy the same sentences of quantifier rank at most α. It is clear that every finitary formula has finite quantifier rank, and that every formula of L_{ω_{1}ω} has countable quantifier rank.

Now, for each structure M, tuple \overline{a} in M, and ordinal α, we define the formula σ_{M,\overline{a}}^{α}(\overline{v}) as follows, where the tuple of variables \overline{v} has the same length as \overline{a}.

• For α = 0, σ_{M,\overline{a}}^{0}(\overline{v}) is the conjunction of all atomic and negated atomic formulas satisfied by \overline{a} in M.

• For α = β + 1, σ_{M,\overline{a}}^{α}(\overline{v}) is the conjunction

σ_{M,\overline{a}}^{β}(\overline{v}) & (∀u) ⋁_{c∈M} σ_{M,\overline{a}c}^{β}(\overline{v}, u) & ⋀_{c∈M}(∃u)σ_{M,\overline{a}c}^{β}(\overline{v}, u).

• For a limit ordinal α, σ_{M,\overline{a}}^{α}(\overline{v}) is the conjunction ⋀_{β<α} σ_{M,\overline{a}}^{β}(\overline{v}).

It is not difficult to see that σ_{M,\overline{a}}^{α}(\overline{v}) is a formula of L_{∞ω} of quantifier rank α. Note that \overline{a} satisfies σ_{M,\overline{a}}^{α}(\overline{v}). Moreover, if α ≤ γ, then σ_{M,\overline{a}}^{γ}(\overline{v}) logically implies σ_{M,\overline{a}}^{α}(\overline{v}).

Lemma 1.3.3. For any structures M and N, any tuples \overline{a} in M and \overline{b} in N, of the same length, and any ordinal α, the following are equivalent.

(a) (M, \overline{a}) ≡_{α} (N , \overline{b}).

(b) N ⊧ σ_{M,\overline{a}}^{α}(\overline{b}).

(c) σ_{M,\overline{a}}^{α}(\overline{v}) = σ_{N ,\overline{b}}^{α}(\overline{v}).

Lemma 1.3.4.

1. For each M there is a least ordinal α, called the Scott height of M, such that for all partial automorphisms (\overline{a}, \overline{b}) of M, (M, \overline{a}) ≡_{α} (M, \overline{b}) implies (M, \overline{a}) ≡_{α+1} (M, \overline{b}).

2. If α is the Scott height of M and (M, \overline{a}) ≡_{α} (M, \overline{b}), then (M, \overline{a}) is potentially isomorphic to (M, \overline{b}).

It is easily seen that each countable structure M has countable Scott height.

Let α be the Scott height of M. We define the canonical Scott sentence of M to be the sentence

σ_{M} = σ_{M,∅}^{α} & ⋀_{\overline{a}}(∀\overline{v}) [σ_{M,\overline{a}}^{α}(\overline{v}) → σ_{M,\overline{a}}^{α+1}(\overline{v})] ,

where the infinite conjunction is over all tuples \overline{a} in M. Note that if M has Scott height α, then the canonical Scott sentence σ_{M} has quantifier rank α + ω.

Theorem 1.3.5. N is a model of the canonical Scott sentence of M if and only if N is potentially isomorphic to M.

Corollary 1.3.6. If L is a countable vocabulary, and M is a countable L-structure, then the canonical Scott sentence of M is a Scott sentence for M in the sense of the Scott Isomorphism Theorem.

Makkai [49] gave the following definition. A structure M is absolutely characterizable if M is at most countable and the canonical Scott sentence has no uncountable models (so the class of models of the canonical Scott sentence is just the class of all isomorphic copies of M).

Examples: The countable structure for the pure identity vocabulary, and the ordered set of rational numbers, both have Scott height 0 and are not absolutely characterizable.

We have mentioned that the Scott height gives a measure of complexity of a structure. A further distinction can be made by asking whether or not the Scott height is “attained”, in the following sense. The local height of a tuple \overline{a} in M is the least ordinal α such that for all tuples \overline{b} in M, (M, \overline{a}) ≡_{α} (M, \overline{b}) implies that (M, \overline{a}) and (M, \overline{b}) are potentially isomorphic. Then the Scott height of M equals the supremum of the local heights of the tuples \overline{a} in M. We will say that the Scott height is attained in M if there is a tuple \overline{a} in M whose local height is equal to the Scott height of M.

Example: For each countable ordinal α > 0, the structure (α, <) is absolutely characterizable. If α is a limit ordinal, then (α, <) has Scott height α, and the Scott height is not attained. If α is a successor ordinal β + 1, then (α, <) has Scott height β, and the Scott height is attained.

1.4. ω-logic. Before proceeding with the Completeness Theorem and other results for the logic L_{ω_{1}ω}, we mention a somewhat simpler related logic. By an ω-vocabulary we mean a countable vocabulary L with a special constant symbol n for each n ∈ ω. A structure M (for such a vocabulary) is called an ω-model if each element a is the interpretation of the constant n for some n ∈ ω. For a proof system for deriving sentences true in all ω-models, we add to the usual finitary rules the following infinitary rule of proof, called the ω-rule:

{φ(n) : n ∈ ω} ⊢ (∀x) φ(x) .

The Henkin construction [33] is a useful method for constructing countable models for a countable set of L_{ωω} sentences. Henkin [34], [35] and Orey [56] used essentially the same construction to produce ω-models, in the following result.

Theorem 1.4.1 (ω-Completeness). Let L be an ω-vocabulary.

1. An L-sentence is true in all ω-models if and only if it is provable using the ω-rule.

2. A set T of L-sentences has an ω-model if and only if there is no proof of a contradiction from T, using the ω-rule.

We may think of ω-logic as logic omitting the type

Γ(x) = {x ≠ n : n ∈ ω} .

The ω-Completeness Theorem may be modified so that it applies to other types, or countable families of types. Given an L_{ω_{1}ω}-sentence φ, we can produce a countable elementary first order theory T and a countable family of types (Γ_{i}(\overline{x}_{i}))_{i∈ω}, involving different tuples of free variables, such that φ has a model if and only if T has a model omitting all of the types Γ_{i}(\overline{x}_{i}).

Kreisel [39] proved a Compactness Theorem for ω-logic. The usual statement fails, of course. Kreisel’s Compactness Theorem, which we shall state later, involves changing the notion of “finite”.

1.5. Familiar theorems. C. Karp [36] gave rules of proof for L_{ω_{1}ω}, including the following variant of the ω-rule, for infinite conjunctions.

{φ_{i} : i ∈ ω} ⊢ ⋀_{i} φ_{i} .

Karp proved the following Completeness Theorem. As usual, we write ⊧ for logical consequence and ⊢ for provability from the infinitary rules.

Theorem 1.5.1 (Completeness). For an L_{ω_{1}ω} sentence φ, ⊧ φ if and only if ⊢ φ.

Makkai [48] gave a useful criterion for model existence. Let L be a countable vocabulary, and let C be a countably infinite set of new constant symbols. A consistency property is a non-empty family S of finite or countable sets of sentences of (L∪C)_{ω_{1}ω} such that for each Φ ∈ S, Φ has no explicitly contradictory pair ψ, ¬ψ, and

• if (∀x) ψ(x) ∈ Φ, then for all c ∈ C, Φ ∪ {ψ(c)} ∈ S,

• if ⋀_{i} ψ_{i} ∈ Φ, then for all i, Φ ∪ {ψ_{i}} ∈ S,

• if (∃x) ψ(x) ∈ Φ, then for some c ∈ C, Φ ∪ {ψ(c)} ∈ S,

• if ⋁_{i} ψ_{i} ∈ Φ, then for some i, Φ ∪ {ψ_{i}} ∈ S,

• if ¬ψ ∈ Φ, and ψ¬ is the sentence obtained from ¬ψ by bringing the negations inside, then Φ ∪ {ψ¬} ∈ S.

Theorem 1.5.2 (Model Existence).

1. Let φ be an L_{ω_{1}ω} sentence. Then φ has a model if and only if there is a consistency property S with an element Φ containing φ.

2. Let T be a countable set of L_{ω_{1}ω} sentences. Then T has a model if and only if there is a consistency property S such that for all φ ∈ T and all Φ ∈ S, Φ ∪ {φ} ∈ S.

Lopez-Escobar [45], [46] proved the following Interpolation Theorem.

Theorem 1.5.3 (Interpolation). Let L^{1} and L^{2} be vocabularies with L = L^{1} ∩ L^{2}. Let φ ∈ L_{ω_{1}ω}^{1} and ψ ∈ L_{ω_{1}ω}^{2} be sentences such that ⊧ φ → ψ. Then there is a sentence θ ∈ L_{ω_{1}ω} such that ⊧ φ → θ and ⊧ θ → ψ.

Here is a version of the Downward Löwenheim-Skolem-Tarski Theorem.

Theorem 1.5.4 (Downward Löwenheim-Skolem-Tarski Theorem). Suppose ℵ_{0} ≤ μ ≤ κ. If a sentence φ of L_{ω_{1}ω} has a model M of cardinality κ, then it has a model N of cardinality μ.

The proof of Theorem 1.5.4 resembles that of the corresponding result for L_{ωω} in that we take N to be a substructure of M. However, we do not try to preserve satisfaction for all L_{ω_{1}ω} formulas—there are too many. It is enough to preserve satisfaction just for the subformulas of φ. The possible strengthening of Theorem 1.5.4, saying that M has a substructure N, of the smaller cardinality, preserving satisfaction of all L_{ω_{1}ω} formulas, is false.

Corollary 1.5.5.

(a) If two sentences of L_{ω_{1}ω} have the same finite and countable models, then they are logically equivalent.

(b) Let L be a countable vocabulary and M be a countable structure. Then any two Scott sentences of M are logically equivalent.

Example: Let M be an ordering of type ω_{1}, and let N be a countable substructure of M. Now, N has order type α, for some countable ordinal α. As we mentioned before, N is absolutely characterizable, so its Scott sentence is true in N but false in M.

1.6. Failure of compactness. There are obvious differences between L_{ωω} and L_{ω_{1}ω}. The usual Compactness Theorem fails. The Upward Löwenheim-Skolem-Tarski Theorem also fails. We have already seen examples of sentences in L_{ω_{1}ω} that have infinite models, but no uncountable models. There are also sentences in L_{ω_{1}ω} that have uncountable models, but only up to a certain size.

Example: Let ψ be the sentence whose models are just the Archimedean ordered fields (described in §1.1). Then ψ has models of cardinality κ just for ℵ_{0} ≤ κ ≤ 2^{ℵ_{0}}.

There is a whole family of examples of this kind—sentences which, for some cardinal μ, have models of cardinality κ just for ℵ_{0} ≤ κ ≤ μ. The Hanf number for a language L is the least cardinal κ such that for each sentence φ ∈ L, if for each cardinal μ < κ, φ has a model of cardinality ≥ μ, then φ has models of arbitrarily large cardinality. Hanf [29] observed that even abstract languages have Hanf numbers, so long as the collection of sentences is a set rather than a proper class.

Theorem 1.6.1 (Hanf). For a language with a set S of sentences, there is a cardinal κ such that for all φ ∈ S, if φ has a model of cardinality ≥ κ, then it has models of arbitrarily large cardinality.

Proof. The proof is simple. For each φ ∈ S such that φ does not have models of arbitrarily large cardinality, let μ_{φ} be an upper bound on the cardinalities of models, and let κ be the least cardinal greater than any μ_{φ}. ⊣

The Upward Löwenheim-Skolem-Tarski Theorem shows that the Hanf number for L_{ωω} is ℵ_{0}. Morley [50] determined the Hanf number for L_{ω_{1}ω}. The statement involves the cardinals ℶ_{α}, which are defined as follows:

(i) ℶ_{0} = ℵ_{0},

(ii) ℶ_{α+1} = 2^{ℶ_{α}},

(iii) for limit α, ℶ_{α} = sup_{β<α} ℶ_{β}.

Theorem 1.6.2 (Morley). The Hanf number for L_{ω_{1}ω} is ℶ_{ω_{1}}.

Morley [51] also determined the Hanf number for ω-logic. The terminology needed for this result will be also be used later. An ordinal α is computable if there is a computable ordering of type α, on on ω, or a finite subset. It is not difficult to see that the computable ordinals form an initial segment of the ordinals. The first non-computable ordinal, which is still countable, is called Church-Kleene ω_{1}, or ω_{1}^{CK}.

Theorem 1.6.3 (Morley). The Hanf number for ω-logic is ℶ_{ω_{1}^{CK}}.

§2. Background on admissible sets. In this chapter, we will describe the situation in the theory of admissible sets at the time that Barwise began his research. An admissible set is a transitive set A such that (A, ∈) is a model of the set theory KP of Kripke [41] and Platek [57]. Here we abuse notation, writing (A, ∈) for the structure (A, R) where R = {(a, b) ∈ A^{2} : a ∈ b}.

The original purpose of admissible sets was to generalize classical computability theory (once called “recursion” theory) from the natural numbers to the ordinals, building on earlier work of Kleene [38], Takeuti [63], Tugue [64], and Kreisel-Sacks [40]. The axioms of KP are considered to be the minimum necessary for a good notion of computation. For each ordinal α, there is a corresponding family of constructible sets 𝕃(α). An ordinal α such that (𝕃(α), ∈) is a model of KP is called an admissible ordinal.

2.1. Δ_{0} formulas and Σ-formulas in set theory. The theory KP is an elementary first order theory in the vocabulary {∈}. It is a weakening of Zermelo-Fraenkel set theory where the power set axiom is removed, and the separation and collection axiom schemes are restricted to “Δ_{0}” formulas. The Δ_{0} formulas, introduced by Levy in [43], are the members of the smallest class of formulas that contains the atomic formulas in the vocabulary {∈} and is closed under finite conjunction and disjunction, bounded quantifiers (∃x ∈ u) and (∀x ∈ u), and negation. In particular, the negation of a Δ_{0} formula is a Δ_{0} formula. The Σ-formulas are the members of the smallest class of formulas which contains the Δ_{0} formulas and is closed under finite conjunction and disjunction, bounded quantifiers (∃x ∈ u) and (∀x ∈ u), and existential quantifiers (∃x). Thus, every Δ_{0} formula is a Σ formula, and every Σ formula is finitary.

The Δ_{0} and Σ formulas are of interest because of the following persistence and absoluteness properties. Given a structure (A, E) with one binary relation E, for each a ∈ A we let a_{E} = {b ∈ A : bEa}. Intuitively, a person living in (A, E) would consider a_{E} to be the set of elements of a. An end extension of (A, E) is an extension (B, F) of (A, E) such that for all a ∈ A, a_{F} = a_{E} (that is, a gets no new elements). Note that if A and B are transitive sets, and A ⊆ B, then (B, ∈) is an end extension of (A, ∈).

Now, consider an elementary first order theory T in the vocabulary of set theory. For example, T can be the theory KP. A formula φ(\overline{u}) is said to be persistent with respect to T if whenever (A, E), (B, F) ⊧ T and (B, F) is an end extension of (A, E), (A, E) ⊧ φ(\overline{c}) implies (B, F) ⊧ φ(\overline{c}), for all \overline{c} in A. A formula φ(\overline{u}) is said to be absolute with respect to T if both φ and its negation are persistent with respect to T.

Proposition 2.1.1. For every elementary first order theory T, every Σ formula is persistent with respect to T.

Proposition 2.1.1 is proved by an easy induction on the complexity of formulas. Feferman and Kreisel [27] proved a deeper converse result, saying that every formula which is persistent with respect to T is T -equivalent to a Σ formula. A formula φ is said to be Δ over T if both φ and ¬φ are T -equivalent to Σ formulas.

Corollary 2.1.2.

(a) Every formula that is Δ over a theory T is absolute with respect to T.

(b) Every Δ_{0} formula is absolute with respect to every theory T.

Remark: Suppose that A, B are transitive sets, A ⊆ B, (A, ∈), (B, ∈) are models of a theory T, and φ(u) is a finitary formula with parameters in A which is absolute with respect to T. If C is the set defined by φ(u) in (B, ∈), then C ∩ A is the set defined by φ(u) in (A, ∈). Moreover, for each a ∈ A, the formula u ∈ a & φ(u) defines the same set in (B, ∈) as in (A, ∈).

2.2. Axioms of KP. Kripke-Platek set theory, or KP, has the usual axioms of extent, foundation, pairing, and union (as in ZF), together with the following separation and collection axiom schemes.

• Δ_{0}-separation: Let φ(x, \overline{y}) be a Δ_{0} formula with no free occurrence of v. Then we have the axiom

(∀\overline{y}) (∀v) (∃u) (∀x) (x ∈ u ↔ [x ∈ v & φ(x, \overline{y})]) .

• Δ_{0}-collection: Let φ(x, y, \overline{z}) be a Δ_{0} formula with no free occurrence of v. Then we have the axiom

(∀\overline{z}) (∀u) [(∀x ∈ u) (∃y) φ(x, y, \overline{z}) → (∃v) (∀x ∈ u) (∃y ∈ v) φ(x, y, \overline{z})] .

Now that we have stated the axioms of KP, we can give a rigorous definition of admissible set. An admissible set is a transitive set A such that (A, ∈) is a model of KP.

Remark: In the axioms of KP, we included collection for Δ_{0} formulas. Collection for Σ formulas follows, and is an important basic theorem of KP. Another important basic theorem of KP is the Σ-reflection principle, which says that (in KP) every Σ formula φ is equivalent to (∃u) φ^{(u)}.

For an admissible set A, the least ordinal which is not an element of A is called the ordinal of A, and is denoted by o(A). The ordinal o(A) plays a major role in the subject. Note that o(A) is always a limit ordinal, and is equal to the set of all ordinals which are elements of A. Moreover, o(A) is a subset of A, definable in (A, ∈) by a Δ_{0} formula.

The smallest example of an admissible set is the set of hereditarily finite sets ℍ𝔽 = ℍ(ω)—a set is hereditarily finite if its transitive closure is finite. The set ℍ𝔽 corresponds to classical computability theory, and it is the only admissible set A such that o(A) = ω. A set X ⊆ ℍ𝔽 is said to be computably enumerable (or c.e.) if it is definable in (ℍ𝔽, ∈) by a Σ formula with parameters in ℍ𝔽. A set X is said to be computable if both X and its complement ℍ𝔽 \ X are c.e. For X ⊆ ω, these definitions agree with the usual ones.

To highlight the analogy with classical computability theory, for an arbitrary admissible set A, the elements of A are called A-finite sets. A subset of A which is definable in (A, ∈) by a Σ formula, with parameters in A, is called A-computably enumerable, or A-c.e. A set X ⊆ A is called A-computable if both X and A \ X are A-c.e. For example, for any admissible set A, the set o(A) is A-computable but not A-finite.

Proposition 2.2.1 (Δ-separation). If A is an admissible set, S is A-finite, and X ⊆ S is A-computable, then X is A-finite.

Proof. Using Σ-reflection and Δ_{0}-collection, one can show that X is definable by a Δ_{0} formula in (A, ∈). Then by Δ_{0}-separation, X ∈ A. ⊣ Remark: If A is admissible and X is an A-c.e. subset of an A-finite set, X need not be A-finite, or even A-computable.

Theories which are stronger than KP but weaker than ZF C are often used in the literature. For example, the power set axiom can be added, or the Separation or Collection schemes can be used with a wider class of formulas.

2.3. Examples of admissible sets. We have already mentioned the smallest admissible set, the set ℍ𝔽 of hereditarily finite sets. A really large example of an admissible set, due to Kripke and Platek, is the set ℍ(κ), consisting of all sets whose transitive closure has power < κ, where κ is an uncountable cardinal. The ordinal is o(ℍ(κ)) = κ. An important special case is the set ℍℂ = ℍ(ω_{1}) of hereditarily countable sets. Thus, o(ℍℂ) = ω_{1}. Another example of an admissible set is the uncountable set 𝕃(ω_{1}). This admissible set satisfies full separation and collection. As for ℍℂ, the ordinal is o(L(ω_{1})) = ω_{1}.

Using the Downward Löwenheim-Skolem-Tarski Theorem, together with the Mostowski Collapsing Lemma, we obtain from 𝕃(ω_{1}) a whole family of countable admissible sets, of the form 𝕃(α), for arbitrarily large countable ordinals α. Thus, ω_{1} is an admissible ordinal, and there are arbitrarily large countable admissible ordinals. For each admissible ordinal α, we have o(L(α)) = α.

There is a least admissible set with ω as an element, namely 𝕃(ω_{1}^{CK}) (so ω and ω_{1}^{CK} are the first two admissible ordinals). More generally, it is shown in [18] that for each X ⊆ ω, there is a least admissible set A with X ∈ A; it is the set A = 𝕃(X, ω_{1}^{X}), the family of sets constructible over X by level ω_{1}^{X}, where ω_{1}^{X} is the first ordinal not computable in X.

2.4. The admissible set 𝕃(ω_{1}^{CK}). In this section we will look at the subsets of ω that are 𝕃(ω_{1}^{CK})-finite, and the subsets of ω that are 𝕃(ω_{1}^{CK})-computably enumerable. These sets are the first levels of the analytical hierarchy.

Facts 2.4.1. (a) The subsets of ω which are 𝕃(ω_{1}^{CK})-computably enumerable are just the Π_{1}^{1} sets.

(b) The subsets of ω which are 𝕃(ω_{1}^{CK})-finite are just the Δ_{1}^{1} sets.

Let us pause to give a quick review of the Π_{1}^{1} and Δ_{1}^{1} sets. The “analytical” relations, on numbers n ∈ ω and functions f ∈ ω^{ω}, are built up from “computable” relations by adding function quantifiers and number quantifiers. For an excellent introduction, see [58]. Roughly speaking, a relation R(x, f), on numbers and functions, is computable if we can determine whether it holds, for a given x ∈ ω and f ∈ ω^{ω}, by applying some effective procedure to x and restrictions f|t, for sufficiently large t. We may identify the restrictions f|t with their Gödel numbers. Formally, we say that R(x, f) is computable if it has a pair of definitions of the forms (∀t) R_{1}(f|t, x), and (∃t) R_{2}(f|t, x), where R_{1}(u, x), R_{2}(u, x) are computable relations, of the usual kind, on pairs of numbers.

Now, let S ⊆ ω. We say that S is Π_{1}^{1} if it has a definition of the form (∀f) R(f, x), where R(f, x) is a computable relation on functions f and numbers x. Similarly, S is Σ_{1}^{1} if it has a definition of the form (∃f) R(f, x), where R(f, x) is a computable. Thus, S is Σ_{1}^{1} just in case its complement is Π_{1}^{1}. A set S is Δ_{1}^{1} if it is both Π_{1}^{1} and Σ_{1}^{1}. Unravelling the definition of a Π_{1}^{1} set, as Kleene did, we see that a set S is Π_{1}^{1} if it has a definition of the form (∀f) (∃t) R(f|t, x), where R(u, x) is a computable relation on pairs of numbers. From R(u, x), we get a uniformly computable family (T_{n})_{n∈ω} of trees, subsets of ω^{<ω} which are closed under initial segments, such that for all n ∈ ω, n ∈ S if and only if T_{n} has no path. We let T_{n} be the set of sequences v such that for all initial segments u ⊆ v, R(u, n) holds. So, we have yet another definition of the class of Π_{1}^{1} subsets of ω.

Theorem 2.4.2 (Kleene). For S ⊆ ω, S is Π_{1}^{1} if and only if there is a uniformly computable sequence of trees (T_{n})_{n∈ω} such that S = {n : T_{n} has no path}.

There is a natural ordering on the elements of a tree T ⊆ ω^{<ω}, the Kleene-Brouwer ordering, such that the ordering is a well-ordering if and only if the tree has no path. Under the Kleene-Brouwer ordering, for σ, τ ∈ T , σ < τ if either σ ⊇ τ, or else there exist ν and m < n such that νm ⊆ σ and νn ⊆ τ. So, Theorem 2.4.2 yields the following.

Corollary 2.4.3 (Kleene). For S ⊆ ω, S is Π_{1}^{1} if and only if there is a uniformly computable sequence of linear orderings (M_{n})_{n∈ω} such that

S = {n : M_{n} is a well ordering}.

Kleene showed that the Δ_{1}^{1} subsets of ω are the same as the hyperarithmetical sets. Roughly speaking, these are the sets which are computable relative to one of a family of sets H(a) obtained by iterating the jump function over computable well orderings. For more about the hyperarithmetical sets, see [58].

Kleene constructed a computable tree T ⊆ ω^{<ω} which has a path, but no hyperarithmetical path (again, see [58]). Harrison [30], [31] showed that for such a tree T , the Kleene-Brouwer ordering has type ω_{1}^{CK}(1 + η) + α, for some computable ordinal α.

Theorem 2.4.4 (Harrison). There is a computable linear ordering of type ω_{1}^{CK}(1 + η).

Theorem 2.4.4 is clearly related to Theorem 1.1.1—the result of Morley and Lopez-Escobar on undefinability of well orderings.

§3. Admissible fragments. We have now completed our survey of the landscape at the time that Barwise entered the picture, and we are ready to move on. For simplicity, let L be a finite vocabulary. Let A be an admissible set. The admissible fragment L_{A} is the set of all L_{∞ω} formulas that are elements of A. In particular, if A = ℍ𝔽, the smallest admissible set, then L_{A} is the classical finitary logic L_{ωω}. If A = ℍℂ, the set of hereditarily countable sets, then L_{A} is the infinitary logic L_{ω_{1}ω}. For any admissible set A, L_{A} is an A-computable set and is closed under basic syntactical operations such as finite connectives, finite quantification, subformulas, and substitution.

3.1. Completeness and compactness. Most of the results in this section appeared in Barwise’s thesis, which combines infinitary logic with admissible sets. The monograph [37] describes the model theory of L_{ω_{1}ω} and its admissible fragments shortly after the appearance of Barwise’s thesis, and illustrates the large and immediate impact that this work had on the subject.

Barwise re-worked the proof system for L_{ω_{1}ω} used by Lopez-Escobar, a sequent calculus, in such a way that the notion of a proof in L_{A} is Δ over KP, so for each admissible A, the set of proofs in L_{A} is A-computable. This required some ingenuity—the usual notions of a proof as a sequence of formulas, or a tree of sequents, did not work. In this way, Barwise arrived at the following version of Completeness for countable admissible fragments.

Theorem 3.1.1 (Completeness I). Let A be a countable admissible set. Any logically valid sentence in L_{A} has a proof in A. Moreover, the set of logically valid L_{A} sentences is A-c.e.

This is satisfying. The statement that the set of logically valid sentences is c.e. implies that there is a nice proof system, without referring to any particular one. A second version of Completeness produces models for some infinitary theories.

Theorem 3.1.2 (Completeness II). Let A be a countable admissible set. If Γ is an A-c.e. set of L_{A} sentences, and there is no proof of a contradiction from Γ, then Γ has a model.

This version of Completeness immediately yields the following.

Theorem 3.1.3 (Barwise Compactness). Let A be a countable admissible set, and suppose Γ is an A-c.e. set of L_{A} sentences. If every A-finite subset of Γ has a model, then Γ has a model.

Barwise’s original arguments for these results were proof-theoretic. Later, Makkai [48] used consistency properties to give Henkin-style proofs.

Here is Kreisel’s Compactness Theorem for ω-logic. The result appears as a footnote in [39].

Theorem 3.1.4 (Kreisel Compactness). Let Γ be a Π_{1}^{1} set of L-sentences. If every Δ_{1}^{1} subset of Γ has an ω-model, then Γ set has an ω-model.

Theorem 3.1.4 looks as though it could have suggested the Barwise Compactness Theorem, but it did not do so directly.^{1}

The next result is a special case of Barwise Compactness which has had a number of recent applications in computable structure theory (see [2]). Computable infinitary formulas are essentially formulas in L_{A}, where A = 𝕃(ω_{1}^{CK}), but the formulas are assigned indices so that they can be identified with natural numbers.

Theorem 3.1.5 (Kreisel-Barwise Compactness). Let Γ be a Π_{1}^{1} set of computable infinitary sentences. If every Δ_{1}^{1} subset of Γ has a model, then Γ has a model.

We have been looking at countable admissible sets, and countable admissible fragments. Compactness is also interesting for uncountable admissible fragments. Let A be an admissible set of arbitrary cardinality. The strict Π_{1}^{1} subsets of A are those definable by formulas of the form (∀R) φ(R, x), where φ is finitary, in a vocabulary that includes the predicate R, addition to ∈. In [5], building on work of Kunen, Barwise showed that his Compactness Theorem holds for L_{A} if and only if A satisfies reflection for these formulas.

Barwise [6] extended Lopez-Escobar’s Interpolation Theorem to admissible fragments.

Theorem 3.1.6 (Interpolation). Let L^{1} and L^{2} be vocabularies with L = L^{1} ∩ L^{2}. Let A be a countable admissible set. If φ ∈ L_{A}^{1} and ψ ∈ L_{A}^{2} are sentences such that ⊧ φ → ψ, then there is a sentence θ ∈ L_{A} such that ⊧ φ → θ and ⊧ θ → ψ.

3.2. Computable structures via Barwise compactness. We could never produce computable models using the ordinary Compactness Theorem, but with Barwise Compactness, we can.

Theorem 3.2.1 (Computable Compactness). Let A be a countable admissible set with ω ∈ A. Let Γ be an A-c.e. set of L_{A}-sentences. If every A-finite subset of Γ has a computable model, then Γ has a computable model.

Proof. Let C be an infinite computable set of new constant symbols, one for each natural number. Then there is an (L ∪ C)_{A} sentence φ whose models are just the computable L-structures, with elements named by the constants in C. We obtain the desired computable model by applying Barwise Compactness to the set of sentences Γ ∪ {φ}. ⊣

Theorem 3.2.1 can be varied. For example, we may replace computable by arithmetical, or X-computable, for some A-finite set X ⊆ ω.

We can now obtain Harrison’s Theorem (Theorem 2.4.4), and a natural generalization.

Theorem 3.2.2 (Harrison, Barwise). 1. There is a computable linear ordering of type ω_{1}^{CK}(1 + η).

1Barwise was unaware of Kreisel’s result until after he had proved his own Compactness Theorem. However, Kreisel’s result may well have had an indirect influence, since Kreisel already had his result when he was one of Barwise’s research advisors at Stanford.

2. Suppose X ⊆ ω, and let α = ω_{1}^{X}. Then there is an X-computable linear ordering of type α(1 + η).

Proof. We shall give the proof for Part 1—the proof for Part 2 is essentially the same. Let A = 𝕃(ω_{1}^{CK}). Showing that there is a computable ordering with an initial segment of type ω_{1}^{CK} is simpler, and we do that first. Let Γ be an A-c.e. set of sentences saying that < is a linear ordering of the universe, with an initial segment of type α, for each computable ordinal α. Every A-finite subset of Γ has a computable model. Therefore, by Barwise Compactness, Γ has a computable model.

To get a computable ordering of type ω_{1}^{CK}(1 + η), we must do a little more. We add to the vocabulary an infinite computable set B of constants, one for each element of the universe of our ordering. We add to Γ sentences saying that B is the universe, < is a computable linear ordering of B, and there is no hyperarithmetical sequence of elements of B which is <-decreasing. ⊣

Barwise’s ideas continue to find new and unexpected applications. Arana, in his soon-to-be completed Ph.D. thesis, used Barwise Compactness to produce infinite families of sentences with special independence properties.

Theorem 3.2.3 (Arana). For each n ≥ 1, there exist a computable ordering (H, <_{H}) of type ω_{1}^{CK}(1+η) (the type of the Harrison ordering) and a computable function F from H to the set of finitary Π_{n} sentences, in the vocabulary of arithmetic, such that

• for any set Γ of Σ_{n−1} and Π_{n−1} sentences, if P A ∪ Γ is consistent, then so is P A ∪ Γ ∪ {F (a) : a ∈ H},

• for all a ∈ H, and all sets Λ of Σ_{n} sentences, if P A ∪ Λ ∪ {F (b) : b <_{H} a} is consistent, then so is P A ∪ Λ ∪ {F (b) : b <_{H} a} ∪ {¬F (a)}.

If M is a nonstandard model of P A and n ∈ ω, then the set T_{n} of finitary Σ_{n} sentences true in M is coded in M in a natural way. Arana’s independent sentences can be used to show that this property of nonstandard models of P A fails for various weak fragments of P A.

The Harrison ordering is a computable structure with 2^{ℵ_{0}} automorphisms, but with no non-trivial hyperarithmetical automorphism. Morozov [52] used Barwise Compactness to produce other examples with this feature.

3.3. Other applications of Barwise compactness. In his doctoral dissertation [3], Barwise used his Compactness Theorem to compute the Hanf numbers of countable admissible fragments.

Theorem 3.3.1 (Barwise). If A is a countable admissible set with A ≠ ℍ𝔽, the Hanf number for L_{A} is ℶ_{o(A)}.

In the case where A = ℍ𝔽, L_{A} is just the finitary logic L_{ωω}, and the classical Löwenheim-Skolem-Tarski theorem tells us that the Hanf number of L_{ℍ𝔽} is ℵ_{0}. In the case where A = 𝕃(ω_{1}^{CK}), Theorem 3.3.1 says that the Hanf number for L_{A} is ℶ_{ω_{1}^{CK}}, the same as in Morley’s result for ω-logic.

The paper [20] gives a result on Hanf numbers for uncountable admissible sets. Stating it requires another definition. Let A be an arbitrary admissible set. An ordinal α is pinned down by A if there is a sentence φ of L_{A} whose models are orderings with an initial segment of type α. Let h(A) be the first ordinal not pinned down by A. If A is countable, then o(A) = h(A). For any admissible set A, we have o(A) ≤ h(A), and there are examples of uncountable admissible sets A such that o(A) < h(A).

Theorem 3.3.2 (Barwise-Kunen). For an admissible set A ≠ ℍ𝔽 of arbitrary cardinality, the Hanf number of L_{A} is ℶ_{h(A)}.

In the paper [8], Barwise shows that the Hanf number for second order logic is “badly behaved”, and its existence requires very strong instances of the replacement axiom scheme.

Given an L-structure M and another vocabulary L′ ⊇ L, an expansion of M to L′ is an L′-structure M′ which has the same universe, and the same interpretation of each symbol of L, as M. A finite extension of L is a vocabulary L′ ⊇ L such that L′ \ L is finite. Here is another simple application of Barwise Compactness.

Theorem 3.3.3 (Expansions). Let A be a countable admissible set. Suppose L is an A-finite vocabulary, L′ is a finite extension of L, and M is an A-finite L-structure. Suppose Γ is an A-c.e. set of L′_{A}-sentences such that for each A-finite Γ′ ⊆ Γ, M can be expanded to a model of Γ′. Then M can be expanded to a model of Γ.

Proof. We add to the vocabulary L a constant symbol m for each m ∈ M. Let φ be the conjunction of the atomic and negated atomic sentences true in M, together with the sentence

(∀x) ⋁_{m∈M} x = m .

The models of φ represent the expansions of M. Now, we obtain the desired model by applying the Barwise Compactness Theorem to Γ ∪ {φ}. ⊣

Theorem 3.3.4 (Uniqueness). Let A be a countable admissible set. Suppose that L is an A-finite vocabulary, and M, N are A-finite L-structures. If M and N satisfy the same L_{A} sentences, then M ≅ N.

Proof. Let F be the set of finite partial isomorphisms from M to N preserving satisfaction of L_{A} formulas. We can show that F is a back-and-forth family. Suppose (\overline{a}, \overline{b}) ∈ F, and let c be a further element of M. We want d ∈ N such that (\overline{a}c, \overline{b}d) ∈ F. We add to L constants representing the elements of \overline{b} and a further new constant e. We apply Theorem 3.3.3 to the structure (N , \overline{b}) and the set of sentences φ(\overline{b}, e), where M ⊧ φ(\overline{a}, c). The interpretation of e in the expansion is the desired d. ⊣

Theorem 3.3.5 (Homogeneity). Let A be a countable admissible set, and let L be A-finite and M be an A-finite L-structure. If \overline{a}, \overline{b} are tuples in M satisfying the same L_{A} formulas, then there is an automorphism of M taking \overline{a} to \overline{b}.

The proof is the same as for Theorem 3.3.4, where the back-and-forth family consists of extensions of the partial automorphism (\overline{a}, \overline{b}).

Theorem 3.3.5 has important consequences for the Scott height of a structure. If M belongs to a countable admissible set A, then for any tuple \overline{a} in M, the orbit of \overline{a} is defined by the conjunction of the L_{A} formulas true of \overline{a}. One consequence is the following result of Nadel [54].

Theorem 3.3.6 (Nadel). Let A be a countable admissible set, and let L be A-finite and M be an A-finite L-structure. Then the Scott height of M is at most o(A).

Let A = 𝕃(ω_{1}^{CK}). In this case, Theorem 3.3.6 says that every computable, or even hyperarithmetical, structure has Scott height at most ω_{1}^{CK}. Recall the Harrison ordering, from Theorem 3.2.2. This is a computable ordering H of type ω_{1}^{CK}(1 + η). The Scott height of H is ω_{1}^{CK}, maximum possible for a hyperarithmetical structure. Moreover, this Scott height is attained, for if a is not on the initial copy of ω_{1}^{CK}, then the orbit of a is definable by the conjunction of all L_{A} formulas true of a, but not by any single L_{A}-formula, so the local height of a is ω_{1}^{CK}. There are other examples of computable structures where the Scott height ω_{1}^{CK} is attained, including certain computable Abelian p-groups, Boolean algebras, and fields.

It is natural to wonder about structures whose Scott height is ω_{1}^{CK}, and is not attained. We have already remarked that a well ordering of type (ω_{1}^{CK}, <) has Scott height ω_{1}^{CK}, which is not attained. This structure is not A-finite, so it is not hyperarithmetical. It is not easy to think of examples of computable, or hyperarithmetical, structures where the Scott height is ω_{1}^{CK} and is not attained. Such a structure must have the feature that for each tuple, the orbit is defined by an L_{A}-formula, but there is no set in A containing definitions for all of the orbits. However, Makkai [49] showed the following.

Theorem 3.3.7 (Makkai). There is an arithmetical structure whose Scott height is ω_{1}^{CK} and is not attained.

The proof uses Theorem 3.2.5. The structure is an expansion of the an ordering of type (ω^{∗} + ω)ω, and it is absolutely characterizable.

Related to Theorem 3.3.6 is the fact that for a computable, or hyperarithmetical, Abelian p-group, the length (that is, the length of the Ulm sequence) is at most ω_{1}^{CK}. If the group is reduced, then the length is a computable ordinal. Similarly, for a computable, or hyperarithmetical, superatomic Boolean algebra, the isomorphism type must be I(ω^{α}n), for some computable ordinal α and some n ∈ ω—this means that the Boolean algebra is a join of n α-atoms. In [21], Barwise and Moschovakis gave abstract principles behind these results.

In [7], Barwise proved the following surprising fact.

Theorem 3.3.8 (Barwise). Any countable model of ZF has a proper end extension satisfying ZF + V = L.

Absoluteness was an important theme in Barwise’s work. Theorem 3.3.8 seems to say that being constructible is not absolute. The proof uses Barwise Compactness, together with the Levy-Shoenfield Absoluteness Theorem, which says that a Σ sentence true in V (the real world of sets) is also true in L (the constructible world).

§4. Admissible sets over M. The admissible sets we have considered up to this point are sometimes called pure admissible sets. We now introduce a larger collection, the admissible sets over an L-structure M. The axioms of KP, like those of ZF, were based on the idea that everything should be a set built up from ∅. We have seen that there is useful information to be gotten by locating a structure in an admissible set. However, membership of a structure in an admissible set is influenced very much by the way the structure has been built up. Barwise realized that it is possible to gain information about properties intrinsic to M—properties such as the Scott height—by taking the elements of M as “urelements” and building an admissible set over M.

Barwise fully developed his theory of admissible sets over a structure in the book [12]. An exposition of some basic results is given in [10], and the first general treatment of admissible sets with urelements is in [11].

4.1. KP with urelements. For simplicity, we fix once and for all a finite vocabulary L with only relation and constant symbols. The theory KP U is intended to describe two-sorted structures of the form

A_{M} = (M, A, ∈, (R^{M})_{R∈L}) ,

where M is the collection of urelements, M = (M, (R^{M})_{R∈L}) is an L-structure, the family of sets A is disjoint from M, and ∈ is the membership relation restricted to (M ∪A)×A. We allow the possibility that M is the empty structure, and in this way, we get the pure admissible sets.

In writing the axioms, we need to distinguish between urelements and sets. Following Barwise, we use variables p, q, r … for urelements, a, b, c, … for sets, and x, y, z, … when we do not wish to distinguish between urelements and sets. Built into the definition of the two-sorted structures we are considering is the fact that (M, (R^{M})_{R∈L}) is a structure for the vocabulary L. The classes of Δ_{0} and Σ formulas are defined exactly as before, except that one starts with atomic formulas in the two-sorted vocabulary L∪{∈}. Quantifiers are allowed over both sorts of variables.

We will also need to allow structures (M, A, E, (R^{M})_{R∈L}), where the binary relation E ⊆ (M ∪ A) × A is not the ∈ relation, and perhaps not even wellfounded. The theory KP U is a first-order theory in the two-sorted vocabulary L ∪ {∈}. The axioms, describing the family of sets and the membership relation, are given below.

Axioms for KP U

Extent: For all sets a, b, (∀x) (x ∈ a ↔ x ∈ b) → a = b.

Foundation: For each finitary formula φ(x, \overline{u}) with no free occurrence of y, we have the axiom

(∀\overline{u})(∃x) φ(x, \overline{u}) → (∃x) [φ(x, \overline{u}) & (∀y ∈ x) ¬φ(y, \overline{u}) ].

Pairing: For all x, y, there is a set a such that x ∈ a & y ∈ a.

Union: For any set a, there is a set b such that (∀y ∈ a) (∀x ∈ y) x ∈ b Δ_{0}-separation: For each Δ_{0} formula φ(x, \overline{y}) with no free occurrence of b, we have an axiom saying that for all \overline{y} and for all sets a, there is a set b such that (∀x) [x ∈ b ↔ (x ∈ a & φ(x, \overline{y}))].

Δ_{0}-collection: For each Δ_{0} formula φ(x, \overline{y}) with no free occurrence of b, we have an axiom saying that for all \overline{y} and all sets a, if (∀x ∈ a) (∃y) φ(x, \overline{y}), then there is a set b such that (∀x ∈ a) (∃y ∈ b) φ(x, \overline{y}).

We wish to generalize the notion of an admissible set to the notion of an admissible set over M. Intuitively, an admissible set over M should be a model of KP U which is “transitive over” M. As a first step, we say that

A_{M} = (M, A, E, (R^{M})_{R∈L})

is a model of KP U over M if A_{M} is a model of KP U, with M as its built-in L-structure. Next, we need to say what it means for the set A to be “transitive over” the set M. For this purpose, we introduce the cumulative hierarchy of sets over M.

(i) V_{M}(0) = ∅,

(ii) V_{M}(α + 1) = P (M ∪ V_{M}(α)),

(iii) for limit ordinals α, V_{M}(α) = ∪_{β<α}V_{M}(β).

Let V_{M} = ∪_{α}V_{M}(α). Now, a set A is transitive over M if it satisfies the following conditions.

• A ⊆ V_{M},

• x ∈ y ∈ A implies x ∈ M ∪ A.

Finally, we say that A_{M} = (M, A, E, (R^{M})_{R∈L}) is an admissible set over M if A_{M} is a model of KP U over M, A is transitive over M, and E is the restriction of the ∈ relation to (M ∪ A) × A. If A_{M} is an admissible set over M, we use the notation o(A_{M}), called the ordinal of A_{M}, to denote the first ordinal that is not an element of A. As before, o(A_{M}) is equal to the set of all ordinals in A.

There is a least admissible set ℍ𝔽_{M} over a given structure M, consisting of the hereditarily finite sets in V_{M}. This has some mathematical interest. In [16], Barwise and Eklof considered a principle stated by Lefschetz, saying that there is essentially only one algebraic geometry of each characteristic, not a different one for each domain. Over an algebraically closed field of a particular characteristic, Barwise and Eklof built a structure which seems to include all of the important objects occurring in algebraic geometry for that characteristic. There are separate sorts for integers, field elements, n-tuples of field elements, subfields finitely generated over the prime field, algebraic closures of finitely generated subfields, polynomials in various fixed tuples of variables, polynomial ideals, etc. All of the elements—of all sorts—come from the least admissible set over a certain two-sorted structure, with one sort for field elements, and the other for integers.

4.2. Truncation lemma. The Truncation Lemma is a valuable tool for building an admissible set over a given structure M by restricting an arbitrary model of KP U over M to its “well-founded part”. To prepare the way, we need some definitions. A model A_{M} = (M, A, E, (R^{M})_{R∈L}) of KP U over M is said to be well-founded if the relation E is well-founded. One can readily check that every admissible set over M is well-founded, and every well-founded model of KP U over M is isomorphic to a unique admissible set over M.

Given a pair of models A_{M} = (M, A, E, (R^{M})_{R∈L}), B_{M} = (M, B, F, (R^{M})_{R∈L}) of KP U over M, we say that A_{M} is an end extension of B_{M} if (A, E) is an end extension of (B, F).

Lemma 4.2.1. For every model A_{M} = (M, A, E, (R^{M})_{R∈L}) of KP U over M, the class of well-founded models B_{M} = (M, B, F, (R^{M})_{R∈L}) of KP U, over M, such that A_{M} is an end extension of B_{M}, has a unique largest element with respect to the end extension relation. This is called the well-founded part of A_{M}.

Theorem 4.2.2 (Truncation Lemma). If A_{M} is a model of KP U over M, then its well-founded part is an admissible set over M.

The idea of the proof of Theorem 4.2.2 is clear—restrict to the well-founded part of A_{M}, and apply the appropriate version of Mostowski’s collapse. The details are tricky. While special cases had been proved earlier, the most general version appears first in the book [12].

4.3. Admissible sets above M. Among the admissible sets over M, those which contain M as an element are of particular interest. These admissible sets are the intended models of the theory KP U^{+}.

Axioms for KP U^{+}: This system has the axioms of KP U, plus an axiom saying that M is an element of A, that is, there is a set a whose elements are just the urelements p. Formally, the axiom is

(∃a)(∀x)[x ∈ a ↔ (∃p)x = p].

We say that A_{M} is an admissible set above M if A_{M} is an admissible set over M and M ∈ A; i.e., A_{M} satisfies the axioms of KP U^{+}. The Truncation Lemma is used to prove the following key existence theorem in [12].

Theorem 4.3.1 (Existence of HY P_{M}). For any countable L-structure M, there is a least admissible set above M.

The least admissible set above M is denoted by HY P_{M}. The least admissible set HY P_{M} above M is of more interest than the least admissible set ℍ𝔽_{M} over M. Theorem 3.3.6 of Nadel can be generalized to show the following.

Theorem 4.3.2. For a countable structure M, the Scott height is at most o(HY P_{M}).

A central idea in the book [12] is to use infinitary logic on the admissible fragment L_{A}, where A = HY P_{M}, as a tool for the study of a structure M.

4.4. Inductive definitions. An inductive definition on a set X is a function Γ, from relations on X to relations (of the same arity) on X, such that Γ is monotone; that is, R ⊆ S implies Γ(R) ⊆ Γ(S). A fixed point for Γ is a relation R on X such that Γ(R) = R. A least fixed point of Γ is a fixed point of Γ which is a subset of every other fixed point of Γ.

Lemma 4.4.1. Every inductive definition Γ has a unique least fixed point.

Proof. Uniqueness is trivial. Starting with ∅, we iterate Γ through steps corresponding to ordinals. Let Γ_{0} = ∅, and for α > 0, let Γ_{α} = Γ(∪_{β<α}Γ_{β}). There is a least ordinal α such that Γ_{α+1} = Γ_{α}. Then Γ_{α} is the least fixed point of Γ. ⊣

In the proof above, the ordinal α is called the closure ordinal for Γ, and is denoted by ∥Γ∥.

Example: Let X be the set of all sentences in an admissible fragment L_{A}. Let Γ be the operation taking a set R ⊂ X to the set S of sentences L_{A}-provable from the set R in a single step. The least fixed point of Γ is the set of all sentences φ ∈ L_{A} which are provable from the empty set.

In the book [53], Moschovakis developed a general theory of inductive definitions of the following kind. Let R be a relation symbol outside the finite vocabulary L, and let L(R) = L ∪ \{R\}. A finitary formula φ(R, \overline{x}) is said to be positive in R if φ is built from atomic formulas of L(R) and quantifier-free formulas of L using finite conjunction, disjunction, and quantifiers. Given an Lstructure M, a formula φ(R, \overline{x}) which is positive in R, and an expansion (M, P) of M to L(R), let Γ_{φ}(P) be the set of tuples \overline{a} in M such that (M, P) ⊧ φ(R, \overline{a}). It is clear that Γ_{φ} is an inductive definition on M. By unravelling the definition, we see the following.

Proposition 4.4.2. For any L-structure M, and any formula φ which is positive in R, the least fixed point of Γ_{φ} is a Π_{1}^{1} relation on M.

The supremum of the closure ordinals ∥Γ_{φ}∥, over all formulas φ positive in R, is called the closure ordinal of M, and is denoted by κ^{M}. Moschovakis [53] established a connection between closure ordinals of structures M and admissible ordinals (see also [12]).

Theorem 4.4.3 (Moschovakis).

1. For every admissible ordinal α there exists a structure M with closure ordinal α = κ^{M}.

2. For each structure M, the closure ordinal κ^{M} is either an admissible ordinal or a limit of admissible ordinals.

Moschovakis asked whether every closure ordinal of a structure is admissible. In [13], Barwise answered the question negatively, showing the following.

Theorem 4.4.4 (Barwise). If α is a limit of admissible ordinals, and α has cofinality ω, then there exists a structure M with closure ordinal α = κ^{M}.

Another result in [13] shows that the closure ordinal of a structure M can differ radically from the ordinal o(HY P_{M}).

Theorem 4.4.5 (Barwise). Let α, β be countable admissible ordinals such that ω ≤ α ≤ β. Then there exists a structure M, in a finite vocabulary, such that κ^{M} = α and o(HY P_{M}) = β. Moreover, κ^{M} = ∥φ∥ for some formula φ positive in R.

The paper [13] is notable for another, quite different, reason. In that paper, Barwise first introduced infinitary logic with finitely many variables. For each finite n, L_{∞ω}^{n} is the sublanguage of L_{∞ω} consisting of those formulas with at most n bound variables, and L_{∞ω}^{ω} is the set of formulas with finitely many bound variables. Barwise needed the following extension of Karp’s Theorem (Theorem 1.2.1).

Theorem 4.4.6 (Barwise). Two structures M, N satisfy the same sentences of L_{∞ω}^{n} if and only if there is a nonempty set F of partial isomorphisms from M to N such that

• The empty pair (∅, ∅) belongs to F,

• For each (\overline{a}, \overline{b}) ∈ F with |\overline{a}| < n and c ∈ M, there exists d ∈ N such that (\overline{a}c, \overline{b}d) ∈ F,

• For each (\overline{a}, \overline{b}) ∈ F with |\overline{a}| < n and d ∈ N, there exists c ∈ M such that (\overline{a}c, \overline{b}d) ∈ F.

The logic L_{∞ω}^{ω} and its sublanguages have become important in the model theory of finite structures. There are two reasons for this. On the one hand, L_{∞ω}^{ω} is expressive enough on finite structures to subsume logics with fixed point operators and closure operators. But on the other hand, for every formula φ ∈ L_{∞ω}^{ω}, there is a finitary formula ψ which is equivalent to φ on “almost all” finite structures. For more on these matters, see [32], [24].

§5. Saturation properties. Saturated structures have long played a prominent role in classical model theory. In this chapter we consider newer notions of saturation which have a computable flavor and arise in the theory of admissible sets.

5.1. Computable saturation. We assume throughout this section that L is a computable vocabulary. Vaught [65] introduced the notions of ω-homogeneous and ω-saturated structures. A structure M is called ω-homogeneous if the set of all pairs of tuples (\overline{a}, \overline{b}) in M which satisfy the same finitary formulas is a back-and-forth family for M, M. A structure M is ω-saturated, provided that for every tuple \overline{c} in M and every set of finitary formulas Γ(\overline{c}, x), if every finite subset of Γ(\overline{c}, x) is satisfied in M, then the whole set is satisfied in M. In [23], Barwise and Schlipf defined a structure M to be computably saturated if the condition above holds for every computable set of finitary formulas Γ(\overline{c}, x). Thus every ω-saturated structure is computably saturated. Barwise and Schlipf proved the following.

Theorem 5.1.1 (Barwise-Schlipf). Every computably saturated structure is ω-homogeneous.

Proof. The main point is that for any pair of tuples (\overline{a}, \overline{b}) in M and any element c ∈ M, there is a computable set of formulas Γ(\overline{a}, \overline{b}, c, x) which says that \overline{a}c and \overline{b}x satisfy the same finitary formulas in M. ⊣

For countable structures, Barwise and Schlipf gave an elegant characterization of computable saturation in terms of the ordinal o(HY P_{M}).

Theorem 5.1.2 (Barwise-Schlipf). Let M be a countable structure. Then M is computably saturated if and only if o(HY P_{M}) = ω.

Recall that ℍ𝔽 is the only pure admissible set with ordinal ω. Theorem 5.1.2 implies that there are many admissible sets over structures with ordinal ω; o(HY P_{M}) = ω for every countable computably saturated M.

Corollary 5.1.3. Every countable computably saturated structure has Scott height ≤ ω.

Here is another connection between a computably saturated structure M and HY P_{M}.

Theorem 5.1.4 (Barwise-Schlipf). If M is computably saturated, then the subsets of M which are elements of HY P_{M} are just those definable in M by finitary formulas with parameters in M.

Countable computably saturated structures have the nice property in the next theorem, called resplendence (Barwise-Schlipf [23] and Ressayre [58]).

Theorem 5.1.5 (Resplendence). Let M be a countable computably saturated structure, let L′ = L ∪ {R_{1}, …, R_{n}} be a finite extension of L, and let Γ be a c.e. set of finitary L′-sentences. If Γ ∪ T h(M) is consistent, then M can be expanded to a (computably saturated) model (M, S_{1}, …, S_{n}) of Γ.

The advantage of countable computably saturated models over countable ω-saturated models is that they exist for every consistent elementary first order theory (Barwise and Schlipf [23]).

Theorem 5.1.6 (Existence). Every structure has a computably saturated elementary extension of the same cardinality.

Computable saturation is also preserved under unions of elementary chains.

In applications of computable saturation, it is often useful to form the model pair (M, N), which is the two-sorted structure built from M and N in the natural way. If the model pair (M, N) is computably saturated, then each of the single structures M and N is computably saturated. However, it is possible for both single structures to be computably saturated while the model pair is not.

Schipf [61] demonstrated that computable saturation makes it possible to simplify many arguments in classical model theory by replacing a transfinite induction (often a back and forth construction) by an induction with just ω steps on countable structures. For example, he used computable saturated model pairs to give easy proofs of the Robinson consistency theorem and the Lyndon homomorphism theorem. He also gave a result which yields easy proofs of completeness for many particular elementary first order theories.

Theorem 5.1.7 (Schlipf). An elementary first order theory T is complete if and only if for every countable computably saturated model pair (M, N) of models of T, M is isomorphic to N.

Proof. If T is complete and (M, N) is a countable computably saturated model pair of models of T, then the Resplendence Theorem 5.1.5 shows that (M, N) can be expanded by adding an isomorphism from M to N. If T is not complete, there is a pair (M′, N′) of countable models of T which are not elementarily equivalent. By the Existence Theorem 5.1.6, there is a countable computably saturated elementary extension (M, N). The models M and N cannot be isomorphic because they are not even elementarily equivalent. ⊣

The following similar result can often be used to show that particular theories admit quantifier elimination.

Theorem 5.1.8. A complete elementary first order theory T admits quantifier elimination if and only if for every countable computably saturated model M of T, the set of partial automorphisms of M is a back-and-forth family.

Proof. Suppose T admits quantifier elimination, let M be a countable computably saturated model of T, and let (\overline{a}, \overline{b}) be a finite partial isomorphism. By quantifier elimination, \overline{a} and \overline{b} satisfy the same finitary formulas. By the Resplendence Theorem 5.1.5, M has an automorphism sending \overline{a} to \overline{b}, so the back-and-forth property holds.

For the converse, suppose every countable computably saturated model M of T has the property above. By Karp’s Theorem, every partial automorphism of M can be extended to an automorphism. Consider a finitary formula φ(\overline{v}) and let Δ(\overline{v}) be the set of all quantifier-free consequences of T ∪ \{φ(\overline{v})\}. By the Compactness Theorem, it suffices to show that φ is a consequence of T ∪ Δ. Suppose not. Then there is a countable model (M, \overline{a}) of T ∪ Δ(\overline{a}) ∪ \{¬φ(\overline{a})\}.

By the Existence Theorem 5.1.6, we may take this model to be computably saturated. Let Γ(\overline{v}) be the set of all quantifier-free formulas satisfied by \overline{a} in M. Then T ∪ Γ(\overline{v}) ∪ \{φ(\overline{v})\} is consistent, because otherwise, by Compactness, there would be a finite Γ_{0} ⊆ Γ such that T ∪{φ} implies ¬ ⋀ Γ_{0} and hence ¬ ⋀ Γ_{0} ∈ Δ, a contradiction. Since T is complete and M is computably saturated, there is a tuple \overline{b} in M such that (\overline{a}, \overline{b}) is a partial automorphism of M but \overline{b} satisfies φ(\overline{v}), contradicting the fact that every partial automorphism can be extended to an automorphism. ⊣

The third edition of the book [26] took advantage of computably saturated structures to simplify several proofs from the earlier editions.

In [22], Barwise and Schlipf studied computably saturated models of P A. They showed that for a countable model of P A, being computably saturated is the same as being expandable to a model of analysis; i.e., Induction plus Δ_{1}^{1} Comprehension. Lipschitz and Nadel [44] used the notion of computable saturation to characterize the additive parts of countable models of first order Peano arithmetic (P A). The set of axioms of P A which are sentences in the vocabulary with just + is known as Pressburger arithmetic.

Theorem 5.1.9 (Lipschitz-Nadel). A countable structure M = (M, +) can be expanded to a model of P A if and only if either M ≅ (ω, +), or M is a computably saturated model of Pressburger arithmetic.

Schlipf [61] gave some amusing properties of countable computably saturated models of ZF.

Theorem 5.1.10 (Schlipf). Let M be a countable computably saturated model of ZF. Then there is an indiscernible set I of ordinals of M such that (M, I) is computably saturated and satisfies the replacement and separation schemes relative to I, and for each α ∈ I, (V_{α}, ∈)^{M} ≺ M and (V_{α}, ∈)^{M} ≅ M.

5.2. Σ_{A}-saturation. Ressayre [58] developed a notion of saturation corresponding to an arbitrary countable admissible set A. Schlipf [60], independently, described the special case where A has the form 𝕃(α). Given an admissible set A and a structure M, we say that M is Σ_{A} saturated if it satisfies the following conditions:

1. For any tuple \overline{a} in M and any A-c.e. set Γ(\overline{a}, x) of formulas γ(\overline{a}, x) ∈ L_{A}, if every A-finite subset of Γ(\overline{a}, x) is satisfiable in M, then Γ(\overline{a}, x) is satisfiable in M.

2. For every tuple \overline{a} in M, A-finite set I, and A-c.e. set Γ of pairs (i, γ(\overline{a}, x)) ∈ I × L_{A}, if for each A-finite Γ′ ⊆ Γ, there exists i ∈ I such that the set of formulas

\{γ(\overline{a}, x) : (i, γ(\overline{a}, x)) ∈ Γ′\}

is satisfiable in M, then there exists i ∈ I such that the set of formulas

\{γ(\overline{a}, x) : (i, γ(\overline{a}, x)) ∈ Γ\}

is satisfiable in M. The following result was proved in a special case by Schlipf [60], and in general

by Adamson [1] and Ressayre [58].

Theorem 5.2.1. Let A be a countable admissible set. A structure M is Σ_{A}-saturated if and only if A can be extended to an admissible set B above M such that o(B) = o(A).

Ressayre [58] proved the following.

Theorem 5.2.2 (Existence and Resplendence). Let A be a countable admissible set.

1. Every consistent A-c.e. set of L_{A}-sentences has a Σ_{A}-saturated model.

2. Suppose M is a countable Σ_{A}-saturated L-structure, L′ is a finite extension of L, and Γ is an A-c.e. set of L′_{A} sentences. If every consequence of Γ in L_{A} is true in M, then M can be expanded to a Σ_{A}-saturated model of Γ.

In Theorem 5.2.2, Part 1 is a special case of Part 2, where M is taken to be just an infinite set. The proof of Part 2 involves a consistency property S whose elements are A-c.e. sets of sentences Λ(\overline{a}), where \overline{a} is a tuple in M which satisfies all the consequences of Γ(\overline{x}) in L_{A}.

Just as for computably saturated structures, for each countable admissible set A, the Σ_{A}-saturated structures are closed under unions of L_{A}-elementary chains. We conclude the chapter with some proofs that use Σ_{A}-saturated structures. Here is proof of Barwise’s Interpolation Theorem (Theorem 3.1.6).

Proof of Theorem 3.1.6. Let Γ_{0} be the set of sentences of the common language L_{A} which are consequences of φ. This is an A-c.e. set. If ¬ψ is consistent with Γ_{0}, then in the vocabulary L^{2}, Γ_{0} ∪ {¬ψ} has a Σ_{A}-saturated model M, by Part 1 of Theorem 5.2.2. By Part 2 of Theorem 5.2.2, M can be expanded to a model N of φ in the vocabulary L^{1} ∪ L^{2}. This contradicts the fact that ⊧ φ → ψ. Therefore, ¬ψ is not consistent with Γ_{0}. By Barwise Compactness, ψ is a consequence of an A-finite subset of Γ_{0}, and the conjunction of this subset is the desired sentence θ. ⊣

The next result is of the earliest applications of Barwise Compactness.

Theorem 5.2.3 (Sacks [59], Friedman-Jensen [28]). For any countable admissible ordinal α > ω, there exists X ⊆ ω such that α = ω_{1}^{X}.

Proof. Take a countable admissible set A such that α = o(A) and ω ∈ A. There is an A-c.e. set Γ of L_{A} sentences describing a structure of the form (M, X, R), where M is a model of KP including all of the ordinals in A, X ⊆ ω, and R is a linear ordering of ω which is computable in X and has an initial segment of order type α. By Theorem 5.2.2, there is a Σ_{A}-saturated model (M, X, R) of Γ. Now, for β < α, the initial segment of R of type β is computable in X, so α ≤ ω_{1}^{X}. To complete the proof, it is enough to show that no ordering of type α on ω is computable in X, for then ω_{1}^{X} ≤ α.

We suppose there is such an ordering S and arrive at a contradiction as follows. Consider the A-c.e. set of formulas Θ(y) saying that y ∈ ω and for each β < α there is a z ∈ ω such that S(z, y) and the initial segment of S below z has order type β. Every A-finite subset of Θ(y) is satisfied in (M, X, R), so by Σ_{A}-saturation the whole set Θ(y) is satisfied in (M, X, R) by some element y ∈ ω. Therefore S cannot have order type α. ⊣

We now give a proof of Barwise’s strengthening of the theorem of Lopez-Escobar and Morley on non-axiomatizability of the class of well orderings (Theorem 1.1.1).

Theorem 5.2.4 (Barwise). Let A be a countable admissible set, and let σ be a sentence in L_{A} such that for each ordinal α in A, σ has a model of order type α. Then σ has a model which is a linear ordering with a subset of order type η.

Proof. Let Γ be an A-c.e. set of sentences in L_{A}, consisting of σ, axioms for linear orderings, and for each ordinal α ∈ A, a sentence saying that the ordering has an initial segment of type α. By Theorem 5.2.2, Γ has a Σ_{A}-saturated model M = (M, R). Now, we can build an embedding f from the rationals into M by induction, making sure as we go along that for any finite subset of ran(f), the intervals to the left of the first element, between two successive elements, and to the right of the last element, all have sub-intervals of type α for all α ∈ A. ⊣

§6. Conclusion. Barwise’s work in infinitary logic and admissible sets cut across the usual divisions in logic. When it appeared, the work was seen as unifying important parts of model theory, computability theory, and set theory. Right away, there were many applications. We have described some of them.

Barwise and others have shown that many of the methods developed for admissible fragments of the logic L_{∞ω} carry over to non-classical logics. See, for example, the paper of Barwise [14] on monotone quantifiers, the paper of Barwise, Kaufmann, and Makkai [19] on stationary logic, and the survey article of Nadel [55], which includes a section on logic with extra propositional connectives.

The landscape of logic has changed in the past 30 years. The growth in the popularity of classification theory and o-minimal structures has left infinitary logic with a much diminished place in model theory. As a result, Barwise’s idea of using HY P_{M} to study a structure M has remained on the back burner. Perhaps this attractive idea will be taken up again by some future logician. On the other hand, infinitary logic is of growing importance for computable structure theory, finite model theory, and certain parts of theoretical computer science. The result of Arana, Theorem 3.2.3, is just one of many recent applications of Barwise Compactness in computable structure theory. It seems likely that there will be further applications in pure computability. There is general machinery, developed by Harrington, Ash [1], and Lempp and Lerman [42], for carrying out Δ_{α}^{0} priority constructions, for an arbitrary computable ordinal α. Harrington asked, in a casual conversation in 1984, whether there might be general machinery which is the limit of such constructions. The Barwise Compactness Theorem does exactly this.

REFERENCES

[1] A. Adamson, Admissible sets and the saturation of structures, Queen’s Mathematical Preprint, no. 1977—4, 1977.

[2] C. J. Ash and J. F. Knight, Computable structures and the hyperarithmetical hierarchy, Elsevier, 2000.

[3] K. J. Barwise, Infinitary logic and admissible sets, Ph.D. thesis, Stanford University, 1967.

[4] , Implicit definability and compactness in infinitary languages, The syntax and semantics of infinitary languages (K. J. Barwise, editor), Springer-Verlag, 1968, pp. 1–35.

[5] , Applications of strict π_{1}^{1} predicates to infinitary logic, this Journal, vol. 34 (1969), pp. 409–432.

[6] , Infinitary logic and admissible sets, this Journal, vol. 34 (1969), pp. 226–252.

[7] , Infinitary methods in the model theory of set theory, Logic colloquium ’69 (R. O. Gandy and C. M. Yates, editors), 1969, pp. 63–66.

[8] , The hanf number of second order logic, this Journal, vol. 37 (1972), pp. 588– 594.

[9] , Back and forth through infinitary logic, Studies in model theory (M. D. Morley, editor), Mathematical Association of America, 1973, pp. 5–34.

[10] , Admissible sets and the interaction of model theory, recursion theory, and set theory, Proceedings of the international congress of mathematicians (J. E. Fenstad and P. G. Hinman, editors), vol. II, 1974, pp. 229–234.

[11] , Admissible sets over models of set theory, Generalized recursion theory (J. E. Fenstad and P. G. Hinman, editors), North-Holland, 1974, pp. 97–122.

[12] , Admissible sets and structures, Springer-Verlag, 1975.

[13] , On moschovakis’ closure ordinals, this Journal, vol. 42 (1977), pp. 292–298.

[14] , Monotone quantifiers and admissible sets, Generalized recursion theory ii (J. E. Fenstad, R. O. Gandy, and G. E. Sacks, editors), North-Holland, 1978, pp. 1–38.

[15] , The right things for the right reasons, Kreiseliana: About and around georg kreisel (P. Odifreddi, editor), Peters, 1996, pp. 15–23.

[16] K. J. Barwise and C. Eklof, P, Lefschetz’s principle, Journal of Algebra, vol. 13 (1969), pp. 554–570.

[17] , Infinitary properties of abelian torsion groups, Annals of Mathematical Logic, vol. 2 (1970), pp. 25–68.

[18] K. J. Barwise, R. O. Gandy, and Y. N. Moschovakis, The next admissible set, this Journal, vol. 36 (1971), pp. 108–120.

[19] K. J. Barwise, M. Kaufmann, and M. Makkai, Stationary logic, Annals of Mathematical Logic, vol. 13 (1978), pp. 171–224.

[20] K. J. Barwise and K. Kunen, Hanf numbers for fragments of l_{∞ω}, Israel Journal of Mathematics, vol. 10 (1971), pp. 306–320.

[21] K. J. Barwise and Y. N. Moschovakis, Global inductive definability, this Journal, vol. 43 (1978), pp. 521–534.

[22] K. J. Barwise and J. S. Schlipf, On recursively saturated models of arithmetic, Model theory and algebra (D. H. Saracino and V. B. Weispfenning, editors), Springer-Verlag, 1973, pp. 42–55.

[23] , An introduction to recursively saturated and resplendent models, this Journal, vol. 41 (1976), pp. 531–536.

[24] K. J. Barwise and J. van Bentham, Interpolation, preservation, and pebble games, this Journal, vol. 64 (1999), pp. 881–903.

[25] C. C. Chang, Some remarks on the model theory of infinitary languages, The syntax and semantics of infinitary languages (K. J. Barwise, editor), Springer-Verlag, 1968, pp. 36– 63.

[26] C. C. Chang and H. J. Keisler, Model theory, third ed., North-Holland, 1990.

[27] S. Feferman and G. Kreisel, Persistent and invariant formulas relative to theories of higher order, Bulletin of the American Mathematical Society, vol. 72 (1966), pp. 480–485.

[28] H. Friedman and R. Jensen, Note on admissible ordinals, The syntax and semantics of infinitary languages (K. J. Barwise, editor), Springer-Verlag, 1968, pp. 77–79.

[29] W. Hanf, Incompactness in languages with infinitely long expressions, Fundamenta Mathematicae, vol. 53 (1964), pp. 309–324.

[30] J. Harrison, Recursive pseudo well-orderings, Ph.D. thesis, Stanford University, 1966.

[31] , Recursive pseudo well-orderings, Transactions of the American Mathematical Society, vol. 131 (1968), pp. 526–543.

[32] L. Hella, P. G. Kolaitis, and K. Luosto, Almost everywhere equivalence of logics in finite model theory, The Bulletin of Symbolic Logic, vol. 12 (1996), pp. 422–443.

[33] L Henkin, The completeness of the first-order predicate calculus, this Journal, vol. 14 (1949), pp. 159–166.

[34] , A generalization of the concept of ω-consistency, this Journal, vol. 19 (1954), pp. 183–196.

[35] , A generalization of the concept of ω-completeness, this Journal, vol. 22 (1957), pp. 1–14.

[36] C. Karp, Languages with expressions of infinite length, Ph.D. thesis, University of Southern California, 1959.

[37] H. J. Keisler, Model theory for infinitary logic, North-Holland, 1971.

[38] S. C. Kleene, On the forms of the predicates in the theory of constructive ordinals, ii, American Journal of Mathematics, vol. 77 (1955), pp. 405–428.

[39] G. Kreisel, Set-theoretic problems suggested by the notion of potential totality, Infinitistic methods, Pergamon, 1961, pp. 103–140.

[40] G. Kreisel and G Sacks, Metarecursive sets, this Journal, vol. 30 (1965), pp. 318– 338.

[41] S. Kripke, Transfinite recursions on admissible ordinals, i and ii, this Journal, vol. 29 (1964), pp. 161–162.

[42] S. Lempp and M. Lerman, A general framework for priority arguments, The Bulletin of Symbolic Logic, vol. 1 (1995), pp. 189–201.

[43] A. Levy, A hierarchy of formulas in set theory, Memoirs of the Americal Mathematical Society, vol. 57, American Mathematical Society, 1965.

[44] L. Lipschitz and M. Nadel, The additive structure of models of arithmetic, Proceedings of the American Mathematical Society, vol. 68 (1978), pp. 331–336.

[45] E. K. Lopez-Escobar, Infinitely long formulas with countable quantifier degrees, Ph.D. thesis, University of California, Berkeley, 1964.

[46] , An interpolation theorem for denumerably long sentences, Fundamenta Mathematicae, vol. 57 (1965), pp. 253–272.

[47] , On definable well-orderings, Fundamenta Mathematicae, vol. 59 (1966), pp. 13–21 and 299–300.

[48] M. Makkai, An application of a method of smullyan to logics on admissible sets, Bulletin of the Polish Academy of Sciences, vol. 17 (1969), pp. 341–346.

[49] , An example concerning scott heights, this Journal, vol. 46 (1981), pp. 301– 318.

[50] M. Morley, Omitting classes of elements, The theory of models (J. Addison, L. Henkin, and A. Tarski, editors), North-Holland, 1965, pp. 263–273.

[51] , The hanf number for ω-logic (abstract), this Journal, vol. 32 (1967), p. 437.

[52] A. S. Morozov, Functional trees and automorphisms of models, Algebra and Logic, vol. 32 (1993), pp. 28–38.

[53] Y.N. Moschovakis, Elementary induction on abstract structures, North-Holland, 1974.

[54] M. E. Nadel, Scott sentences for admissible sets, Annals of Mathematical Logic, vol. 7 (1974), pp. 267–294.

[55] , L_{ω_{1}ω} and admissible fragments, Model-theoretic logics (K. J. Barwise and S. Feferman, editors), Springer-Verlag, 1985, pp. 271–316.

[56] S. Orey, On ω-consistency and related properties, this Journal, vol. 21 (1956), pp. 246–252.

[57] R. Platek, Foundations of recursion theory, Ph.D. thesis, Stanford University, 1966.

[58] J.-P. Ressayre, Models with compactness properties relative to an admissible language, Annals of Mathematical Logic, vol. 11 (1977), pp. 31–55.

[59] G. E. Sacks, Metarecrusively enumerable sets and admissible ordinals, Bulletin of the American Mathematical Society, vol. 72 (1966), pp. 59–64.

[60] J. Schlipf, A guide to the identification of admissible sets above structures, Annals of Mathematical Logic, vol. 12 (1977), pp. 151–192.

[61] , Model theory and recursive saturation, this Journal, vol. 43 (1978), pp. 183– 206.

[62] D. Scott, Logic with denumerably long formulas and finite strings of quantifiers, The theory of models (J. Addison, L. Henkin, and A. Tarski, editors), North-Holland, 1965, pp. 329–341.

[63] G. Takeuti, Recursive functions and arithmetical functions of ordinal numbers, Logic, methodology and philosophy of science (Y. Bar-Hillel, editor), North-Holland, 1965, pp. 179– 196.

[64] T. Tugue, On the partial recursive functions of ordinal numbers, Journal of the Mathematical Society of Japan, vol. 16 (1964), pp. 1–31.

[65] R. Vaught, Denumerable models of complete theories, Infinitistic methods, Pergamon, 1961, pp. 303–321.

DEPARTMENT OF MATHEMATICS

UNIVERSITY OF WISCONSIN

480 LINCOLN DRIVE

MADISON WI 53706, U.S.A.

E-mail: keisler@math.wisc.edu

DEPARTMENT OF MATHEMATICS

UNIVERSITY OF NOTRE DAME

255 HURLEY HALL

NOTRE DAME IN 46556, U.S.A.

E-mail: Knight.1@nd.edu