Sublanguages of L(ω1,ω) and the Barwise Compactness Theorem

Given what we now know about infinitary languages, it would seem that L(ω1,ω) is the only one to be reasonably well behaved. On the other hand, the failure of the compactness theorem to generalize to L(ω1,ω) in any useful fashion is a severe drawback as far as applications are concerned. Let us attempt to analyze this failure in more detail.
Recall from §4 that we may code the formulas of a first-order language L as hereditarily finite sets, i.e., as members of H(ω). In that case each finite set of (codes of) L-sentences is also a member of H(ω), and it follows that the compactness theorem for L can be stated in the form:

اقتباس :: (5.1) If Δ ⊆ Sent(L) is such that each subset Δ0 ⊆ Δ, Δ0 ∈ H(ω) has a model, so does Δ.

Now it is well-known that (5.1) is an immediate consequence of the generalized completeness theorem for L, which, stated in a form similar to that of (5.1), becomes the assertion:

اقتباس :: (5.2) If Δ ⊆ Sent(L) and σ ∈ Sent(L) satisfy Δ ⊨ σ, then there is a deduction D of σ from Δ such that D ∈ H(ω).[8]

In §2 we remarked that the compactness theorem for L(ω1,ω) fails very strongly; in fact, we constructed a set Γ ⊆ Sent(ω1,ω) such that

اقتباس :: (5.3) Each countable subset of Γ has a model but Γ does not.

Recall also that we introduced the notion of deduction in L(ω1,ω); since such deductions are of countable length it quickly follows from (5.3) that

اقتباس :: (5.4) There is a sentence[9]σ ∈ Sent(ω1,ω) such that Γ ⊨ σ, but there is no deduction of σ inL(ω1,ω) from Γ.

Now the formulas of L(ω1, ω) can be coded as members of H(ω1), and it is clear that H(ω1) is closed under the formation of countable subsets and sequences. Accordingly (5.3) and (5.4) may be written:

اقتباس :: (5.3 bis) Each Γ0 ⊆ Γ such that Γ0 ∈ H(ω1) has a model, but Γ does not;
(5.4 bis) There is a sentence σ ∈ Sent(ω1,ω) such that Γ ⊨ σ, but there is no deduction D ∈H(ω1) of σ from Γ.

It follows that (5.1) and (5.2) fail when “L” is replaced by “L(ω1,ω)” and “H(ω)” by “H(ω1)”. Moreover, it can be shown that the set Γ ⊆ Sent(ω1,ω) in (5.3 bis) and (5.4 bis) may be taken to be Σ1 on H(ω1). Thus the compactness and generalized completeness theorems fail even for Σ1-sets of L(ω1, ω)-sentences.
We see from (5.4 bis) that the reason why the generalized completeness theorem fails for Σ1-sets in L(ω1,ω) is that, roughly speaking, H(ω1) is not “closed” under the formation of deductions from Σ1-sets of sentences in H(ω1). So in order to remedy this it would seem natural to replaceH(ω1) by sets A which are, in some sense, closed under the formation of such deductions, and then to consider just those formulas whose codes are in A.
We now give a sketch of how this can be done.
First, we identify the symbols and formulas of L(ω1,ω) with their codes in H(ω1), as in §4. For each countable transitive[10] set A, let

اقتباس :: LA = Form(L(ω1,ω)) ∩ A.

We say that LA is a sublanguage of L(ω1,ω) if the following conditions are satisfied:

L ⊆ LA
if φ, ψ ∈ LA, then φ ∧ ψ ∈ LA and ¬φ ∈ LA
if φ ∈ LA and x ∈ A, then ∃xφ ∈ LA
if φ(x) ∈ LA and y ∈ A, then φ(y) ∈ LA
if φ ∈ LA, every subformula of φ is in LA
if Φ ⊆ LA and Φ ∈ A, then [size=undefined]∧[/size]Φ ∈ LA.

The notion of deduction in LA is defined in the customary way; if Δ is a set of sentences of LA and φ ∈ LA, then a deduction of φ from Δ in LA is a deduction of φ from Δ in L(ω1, ω) every formula of which is in LA. We say that φ is deducible from Δ in LA if there is a deduction D of φ from Δ inLA; under these conditions we write Δ ⊢A φ. In general, D will not be a member of A; in order to ensure that such a deduction can be found in A it will be necessary to impose further conditions on A.
Let A be a countable transitive set such that LA is a sublanguage of L(ω1, ω) and let Δ be a set of sentences of LA. We say that A (or, by abuse of terminology, LA) is Δ-closed if, for any formula φ of LA such that Δ ⊢A φ, there is a deduction D of φ from Δ such that D ∈ A. It can be shown that the only countable language which is Δ-closed for arbitrary Δ is the first-order language L, i.e., when A = H(ω). However J. Barwise discovered that there are countable sets A ⊆ H(ω1) whose corresponding languages LA differ from L and yet are Δ-closed for all Σ1-sets of sentences Δ. Such sets A are called admissible sets; roughly speaking, they are extensions of the hereditarily finite sets in which recursion theory—and hence proof theory—are still possible (for the full definition, see Section 5.1 below).
From Barwise's result one obtains immediately the

اقتباس :: Barwise Compactness Theorem. Let A be a countable admissible set and let Δ be a set of sentences of LA which is Σ1 on A. If each Δ′ ⊆ Δ such that Δ′ ∈ A has a model, then so does Δ.

The presence of “Σ1” here indicates that this theorem is a generalization of the compactness theorem for recursively enumerable sets of sentences.
Another version of the Barwise compactness theorem, useful for constructing models of set theory, is the following. Let ZFC be the usual set of axioms for Zermelo-Fraenkel set theory, including the axiom of choice. Then we have:

اقتباس :: 5.5 Theorem. Let A be a countable transitive set such that A = ⟨A, ∈ ⨡ A⟩ is a model ofZFC. If Δ is a set of sentences of LA which is definable in A by a formula of the language of set theory and if each Δ′ ⊆ Δ such that Δ′ ∈ A has a model, so does Δ.

To conclude, we give a simple application of this theorem. Let A = ⟨A, ∈ ⨡ A⟩ be a model ofZFC. A model B = ⟨B, E⟩ of ZFC is said to be a proper end-extension of A if (i) A ⊆ B, (ii) A ≠B, (iii) a ∈ A, b ∈ B, bEa ⇒ b∈A. Thus a proper end-extension of a model of ZFC is a proper extension in which no “new” element comes “before” any “old” element. As our application of5.5 we prove

اقتباس :

5.6 Theorem. Each countable transitive model of ZFC has a proper end-extension.
Proof. Let A = ⟨A, ∈ ⨡ A⟩ be a transitive model of ZFC and let L be the first-order language of set theory augmented by a name a for each a ∈ A, and an additional constant c. Let Δ be the set of LA-sentences comprising:

all axioms of ZFC;
c ≠ a, for each a ∈ A;
∀x(x ∈ a → [size=undefined]∨[/size]b∈a x = b), for each a ∈ A;
a ∈ b, for each a ∈ b ∈ A.

[size]
It is easily shown that Δ is a subset of A which is definable in A by a formula of the language of set theory. Also, each subset Δ′ ⊆ Δ such that Δ′ ∈ A has a model. For the set C of all a ∈A for which a occurs in Δ′ belongs to A — since Δ′ does — and so, if we interpret c as any member of the (necessarily nonempty) set A − C, then A is a model of Δ′. Accordingly, (5.5) implies that Δ has a model ⟨B, E⟩. If we interpret each constant a as the element a ∈ A, then ⟨B, E⟩ is a proper end-extension of A. The proof is complete.[/size]

The reader will quickly see that the first-order compactness theorem will not yield this result.

5.1 Definition of the Concept of Admissible Set

A nonempty transitive set A is said to be admissible when the following conditions are satisfied:

if a, b ∈ A, then {a, b} ∈ A and ∪A ∈ A;
if a ∈ A and X ⊆ A is Δ0 on A, then X ∩ a ∈ A;
if a ∈ A, X ⊆ A is Δ0 on A, and ∀x∈a∃y(<x,y> ∈ X), then, for some b ∈ A, ∀x∈a∃y∈b(<x,y> ∈ X).

Condition (ii) — the Δ0-separation scheme — is a restricted version of Zermelo's axiom of separation. Condition (iii) — a similarly weakened version of the axiom of replacement — may be called the Δ0-replacement scheme.
It is quite easy to see that if A is a transitive set such that <A, ∈ | A> is a model of ZFC, then A is admissible. More generally, the result continues to hold when the power set axiom is omitted from ZFC, so that both H(ω) and H(ω1) are admissible. However, since the latter is uncountable, the Barwise compactness theorem fails to apply to it.

6. Historical and Bibliographical Remarks

§§1 and 2. Infinitary propositional and predicate languages seem to have made their first explicit appearance in print with the papers of Scott and Tarski [1958] and Tarski [1958]. The completeness theorem for L(ω1,ω), as well as for other infinitary languages, was proved by Karp [1964]. The Hanf number calculations for L(ω1,ω) were first performed by Morley [1965]. The nondefinability of well-orderings in finite-quantifier languages was proved by Karp [1965] and Lopez-Escobar [1966]. The interpolation theorem for L(ω1,ω) was proved by Lopez-Escobar [1965] and Scott's isomorphism theorem for L(ω1,ω) by Scott [1965].
Karp's partial isomorphism theorem was first proved in Karp [1965]; see also Barwise [1973]. Result (2.2) appears in Chang [1968], result (2.3) in Ellentuck [1976] and result (2.4) in Bell [1981].
§3. Results (3.2) and (3.3) are due to Hanf [1964], with some refinements by Lopez-Escobar [1966] and Dickmann [1975], while (3.4) was proved by Tarski. Result (3.5) is due to Scott [1961], (3.6) to Bell [1970] and [1972]; and (3.7) to Bell [1974]. Measurable cardinals were first considered by Ulam [1930] and Tarski [1939]. The fact that measurable cardinals are weakly compact was noted in Tarski [1962].
§4. Concerning the undefinability theorem for L(ω1,ω1). Carol Karp remarks (1964, 166), “At the International Congress of Logic, Methodology and the Philosophy of Science at Stanford University in 1960, Dana Scott circulated an outline of a proof of the impossibility of a complete definable formal system for (γ+, γ+) languages with a single two-place predicate symbol in addition to the equality symbol.” Scott never published his result, and a fully detailed proof first appeared in Karp [1964]. The approach to the theorem adopted here is based on the account given in Dickmann [1975].
§5. The original motivation for the results presented in this section came from Kreisel; in his [1965] he pointed out that there were no compelling grounds for choosing infinitary formulas solely on the grounds of “length”, and proposed instead that definability or “closure” criteria be employed. Kreisel's suggestion was taken up with great success by Barwise [1967], where his compactness theorem was proved. The notion of admissible set is due to Platek [1966]. Theorem (5.6) is taken from Keisler [1974].
For further reading on the subject of infinitary languages, see Aczel [1973], Dickmann [1975], Karp [1964], Keisler [1974], and Makkai [1977]. A useful account of the connection between infinitary languages and large cardinals can be found in Chapter 10 of Drake [1974].

Sublanguages of L(ω1,ω) and the Barwise Compactness Theorem

5.1 Definition of the Concept of Admissible Set

6. Historical and Bibliographical Remarks

Sublanguages of L(ω1,ω) and the Barwise Compactness Theorem :: تعاليق

Sublanguages of L(ω1,ω) and the Barwise Compactness Theorem