Hedman. A First Course in Logic, 2004 (Oxford)

An amalgamation theorem states that given these structures, sets, and functions, there exists structure D and functions g1 : M1 → D and g2 : M2 → D so that g1(f1(c)) = g2(f2(c)) for each c C. That is, given the bottom half of this diagram, an amalgamation theorem asserts the existence of the top half.

We prove several amalgamation theorems in this section. The above diagram depicts each of these theorems. Di erent amalgamation theorems arise from the various restrictions we may place on the structures, sets, and functions in this diagram. For example, in Theorem 4.38 we require that C is a structure and f1 and f2 are elementary embeddings. We refer to this theorem as Elementary Amalgamation over Structures. The conclusion of this theorem states that the functions g1 and g2 in the diagram are in fact elementary embeddings. This theorem, as with all of the amalgamation theorems, is a consequence of compactness. We repeatedly use the following corollary of compactness.

Definition 4.35 A set of sentences Γ is said to be closed under conjunction if for any sentences ϕ and ψ in Γ, the sentence ϕ ψ is also in Γ.

Corollary 4.36 Let Γ be a set of sentences that is closed under conjunction. Let T be any consistent set of sentences. The set T Γ is inconsistent if and only if T ¬ϕ for some ϕ in Γ.

Proof Clearly, if T entails the negation of a sentence that is in Γ, then T Γ is not consistent. The converse is a direct consequence of compactness. If T Γ inconsistent, then, by compactness, there exists an inconsistent finite subset ∆ of T Γ. Since T is consistent, there must exists sentences from Γ in ∆. Let Φ be the conjunction of the sentences in both ∆ and Γ. Then T {Φ} is inconsistent. By Proof by Contradiction, we have T ¬Φ. Since Γ is closed under conjunction, Φ is a sentence in Γ as was required.

This corollary provides an alternative version of compactness. From now on, when we say that something is true “by compactness” we mean that it follows either from the Compactness theorem 4.29 or, equivalently, from Corollary 4.36.

Our first amalgamation theorem is known as the Joint Embedding lemma. This lemma states that any two models of a complete theory can be elementarily embedded into some other model of the same theory. This is a basic way to amalgamate many structures into one. In the above diagram, M1 ≡ M2, g1 and g2 are elementary embeddings, and C is the empty set.

Lemma 4.37 (Joint Embedding) Let M and N be V-structures that model a complete V-theory T . There exists a model D of T such that both M and N can be elementarily embedded into D. Moreover, if M or N is infinite, then we can take D so that |D| is the same as the larger of |M | and |N |.

172 Properties of first-order logic

Proof Consider the elementary diagrams ED(M ) and ED(N ). We may assume that the added constants in each of these sets are distinct. That is, we assume that the only constants occurring in both ED(M ) and ED(N ) are those constants occurring in V. We show that ED(M ) ED(N ) is consistent.

Suppose not. Suppose that ED(M ) ED(N ) is contradictory. By compactness, ED(M ) ¬ϕ for some sentence ϕ ED(N ). As a sentence in ED(N ), ϕ

not in V. Since M and N are elementarily equivalent V-structures, n must be at least 1.

¯ ED ED ¬

Since the parameters b do not occur in (M ), we have (M ) x¯ ψ(¯x) by -Introduction. We have

M|= x¯¬ψ(¯x) which implies

M|= ¬ xψ¯ (¯x) which implies N |= ¬ xψ¯ (¯x) since M ≡ N .

¯ ED

But this contradicts the fact that ψ(b) (N ). We conclude that our supposition must be wrong and ED(M ) ED(N ) is consistent. By Theorem 4.27, there exists a model D of ED(M ) ED(N ). By Proposition 2.80(b), both M and N can be elementarily embedded into D as required.

The “moreover” clause in this lemma is a direct consequence of the Downward L¨owenheim–Skolem theorem.

In fact, any number of models of a theory can be elementarily embedded into a single model of that theory. We leave this generalization of the Joint Embedding lemma as Exercise 4.23.

We now prove the previously mentioned Elementary Amalgamation over Structures theorem.

Theorem 4.38 (Elementary Amalgamation over Structures) Let M1, M2 and

N be V-structures that model a complete V-theory T . Let f1 : N → M1 and f2 : N → M2 be elementary embeddings. There exists a model D of T such that both M1 and M2 can be elementarily embedded into D in a manner that agrees on N . That is, there exists D |= T and elementary embeddings g1 : M1 → D and g2 : M2 → D such that f2(f1(c)) = g2(g1(c)) for each c in the universe of N .

Proof Let V(N ) be the expansion of V that includes a constant ca for each element a of the underlying set of N .

Let M1 be the expansion of M1 to a V(N )-structure that interprets each ca as f1(a).

Let M2 be the expansion of M2 to a V(N )-structure that interprets each ca as f2(a).

the complete theory of these structures. By the Joint Embedding lemma, there exists a model D of T such that both M1 and M2 can be elementarily embedded into D.

From the proof of Theorem 4.38, we see that something stronger is true. Nowhere in this proof did we use the fact that N is a model of T . In fact, N does not even have to be a structure. We need only that M1 ≡ M2 where the primes denote expansions by constants representing elements of N . This su ces to show that D and the two elementary embeddings exist.

Theorem 4.39 (Elementary Amalgamation over Sets) Let M1 and M2 be V- structures that model a complete V-theory T . Let C be a set of constants not in the vocabulary V of M1 and M2. Let V(C) be V C. Let M1(C) be an expansion of M1 to a V(C)-structure and let M2(C) be an expansion of M2 to a V(C)-structure. If M1(C) ≡ M2(C), then there exists a V(C)-structure D(C) into which both M1(C) and M2(C) can be elementarily embedded.

Proof The proof is the same as the proof of Theorem 4.38.

If we do not require the two embeddings into D to be elementary, then we can relax the condition that the two structures are elementarily equivalent. The following lemma is a modified version of the Joint Embedding lemma. Instead of requiring that M1 models every sentence that M2 models, we require only that M1 models every existential sentence that M2 models. Under this hypothesis, we still obtain a structure D and embeddings of M1 and M2 into D, but now only one of these embeddings is elementary.

Lemma 4.40 Let M and N be V-structures. Suppose that for any existential V-sentence ϕ, if N |= ϕ then M |= ϕ. Then there exists a V-structure D such that N can be embedded into D and M can be elementarily embedded into D.

Proof Consider the literal diagram D(N ) and the elementary diagram ED(M ). We may assume that the added constants in each of these sets are distinct. That is, we assume that the only constants occurring in both ED(M ) and D(N ) are those constants occurring in V. We show that ED(M ) D(N ) is consistent.

Suppose not. Suppose that ED(M ) D(N ) is contradictory. By compactness, ED(M ) ¬ϕ for some sentence ϕ D(N ). As a sentence in D(N ), ϕ has the

¯ ¯

form ψ(b) where ψ(¯x) is a literal and b is an n-tuple of constants that do not occur in ED(M ).

174 Properties of first-order logic

¯ ED ED ¬

Since the parameters b do not occur in (M ), we have (M ) x¯ ψ(¯x) by -Introduction. We have

M|= x¯¬ψ(¯x) which implies

M|= ¬ xψ¯ (¯x).

Since ψ(¯x) is a literal, xψ¯ (¯x) is existential. So, by the hypothesis of the theorem, if N |= xψ¯ (¯x), then M |= xψ¯ (¯x). Since this is not the case, N |= ¬ xψ¯ (¯x).

¯ D

But this cannot be the case either. It contradicts the fact that ψ(b) (N ). We conclude that our supposition must be wrong and ED(M ) D(N ) is consistent.

By Theorem 4.27, there exists a model D of ED(M ) D(N ). By Propositions 2.79 and 2.80, N can be embedded into D and M can be elementarily embedded into D.

The following theorem follows from Lemma 4.40 just as Theorem 4.39 follows from the Joint Embedding lemma.

Theorem 4.41 (Existential Amalgamation over Sets) Let M1, M2 be

V-structures and let C be a set of constants not in V. Let V(C) be V C. Let M1(C) be an expansion of M1 to a V(C)-structure and let M2(C) be an expansion of M2 to a V(C)-structure. If M2(C) models every existential V-sentence that M1(C) models, then there exists a V(C)-structure D into which M1(C) can be embedded and M2(C) can be elementarily embedded.

Proof Apply Lemma 4.40 with M1(C) as N and M2(C) as M .

4.5 Preservation of formulas

If a formula is equivalent to an existential formula, then it is preserved under extensions by Proposition 2.72 of Section 2.6.2. Using Theorem 4.41, we prove the converse.

Proposition 4.42 If a formula is preserved under extensions, then it is equivalent to an existential formula.

We in fact prove something stronger.

Definition 4.43 Let T be a theory (not necessarily complete). We say that a formula ϕ(¯x) is preserved under supermodels of T if for any two models M and N of T with M N and any tuple a¯ of elements from the universe of M ,

M |= ϕ(¯a) implies N |= ϕ(¯a). If instead

N |= ϕ(¯a) implies M |= ϕ(¯a),

then we say that ϕ(¯x) is preserved under submodels of T .

In this section, we prove that a formula ϕ is preserved under supermodels of

Tif and only if ϕ is T -equivalent to an existential formula. In particular, taking

Tto be the empty set of sentences, Proposition 4.42 holds. As a corollary to this, a formula is preserved under submodels of T if and only if it is T -equivalent to a universal formula. In the second part of this section, we define the notion of a chain of models and prove a preservation theorem regarding formulas of the form x¯ yϕ¯ for quantifier-free ϕ.

4.5.1 Supermodels and submodels. Let T be a theory. We show that a formula ϕ is preserved under supermodels of T if and only if ϕ is T -equivalent to an existential formula. First, we show this is true in the case where ϕ is a sentence. Note that this is only interesting if neither ϕ nor ¬ϕ is in T . Otherwise, ϕ is T -equivalent to either the existential tautology x(x = x) or the contradictionx¬(x = x).

Proposition 4.45 Let T be a theory. If a sentence is preserved under supermodels of T , then it is T -equivalent to an existential sentence.

Proof Suppose that ϕ is a sentence that is preserved under supermodels of T . Let V be the vocabulary of T {ϕ}.

Let C be the set of all existential V-sentences ψ such that T {ϕ} ψ. We want to show that T C {¬ϕ} is inconsistent.

Let D be the set of all existential V-sentences that are not in C. So C D equals the set of all existential V-sentences. Let Γ be the set of all V-sentences that are equivalent to the negation of some sentence in D.

Our goal is to show that T C {¬ϕ} is inconsistent. It su ces to show that T Γ {ϕ} is consistent.

Claim If T Γ {ϕ} is consistent, then T C {¬ϕ} is inconsistent.

Proof Suppose that T Γ {ϕ} is consistent. Let N be a model. Then N models each existential sentence in C (since these are consequences of ϕ) and N models none of the existential sentences in D (since these are equivalent to the negation of sentences in Γ).

Suppose for a contradiction that T C {¬ϕ} is also consistent. Let M be a model. Since the only existential sentences that N models are in C, M models every existential sentence that N models. By Theorem 4.41, there exists a structure D into which N can be embedded and M can be elementarily embedded.

Since M can be elementarily embedded into D and M |= T , D is a model of T . Since M |= ¬ϕ, D |= ¬ϕ.

of T . This contradicts the assumption that ϕ is preserved under extentions of models of T . This contradiction proves the claim.

Claim T Γ {ϕ} is consistent.

Proof Note that Γ is closed under conjunction. If T Γ {ϕ} is inconsistent, then T {ϕ} ¬γ for some γ Γ (If ϕ is contradictory, then this is the Contradiction rule. Otherwise, this is Corollary 4.36.) By the definition of Γ, ¬γ is T -equivalent to a sentence ψ in D. Since T {ϕ} ψ, ψ C. This contradicts the fact that C and D are disjoint sets of sentences. We conclude that T Γ {ϕ} is consistent as claimed.

By the two claims, T C {¬ϕ} is inconsistent. So T C ϕ. By compactness, T {ψ1 ψ2 · · · ψn} ϕ for some ψ1, . . . , ψn in C. Since each ψi is existential, their conjunction is equivalent to an existential sentence Ψ. Since T {ϕ} ψi for each ψi, T {ϕ} Ψ. By →-Introduction, we have both T ϕ → Ψ and T Ψ → ϕ. So ϕ is T -equivalent to the existential sentence Ψ.

Using Proposition 4.45, we now prove two preservation theorems for formulas. Note that the sentence ϕ in Proposition 4.45 is not necessarily in the same vocabulary as T .

Theorem 4.46 Let T be a V-theory. A V-formula ϕ(x1, . . . , xn) is preserved under supermodels of T if and only if ϕ(x1, . . . , xn) is T -equivalent to an existential formula.

Proof If ϕ(x1, . . . , xn) is T -equivalent to an existential formula, then it is preserved under extensions by Proposition 2.72. We must prove the other direction of the theorem.

Suppose that ϕ(x1, . . . , xn) is preserved under supermodels of T . If n = 0, then ϕ is a sentence and we may apply Proposition 4.45. Otherwise, for n N,

ψ(c1, . . . , cn) (This sentence may or may not contain each constant ci). We have

T ϕ(c1, . . . , cn) ↔ ψ(c1, . . . , cn).

Since the constants ci do not occur in T ,

T x1 . . . xn(ϕ(x1, . . . , xn) ↔ ψ(x1, . . . , xn)) by -Introduction.

Theorem 4.47 Let T be a V-theory. A V-formula ϕ(x1, . . . , xn) is preserved under submodels of T if and only if ϕ(x1, . . . , xn) is T -equivalent to a universal formula.

Proof A formula ϕ is preserved under submodels of T if and only if its negation ¬ϕ is preserved under supermodels of T . If this is the case, then, by Theorem 4.46, ¬ϕ is T -equivalent to an existential sentence. Finally, ¬ϕ is T -equivalent to an existential sentence if and only if ϕ is T -equivalent to a universal sentence.

We now turn our attention to quantifier-free formulas. These formulas are preserved under both supermodels and submodels (this follows from Proposition 2.71). Conversely, suppose that a given formula ϕ is preserved under both supermodels and submodels of T . Then, by the previous two theorems, ϕ is T -equivalent to both an existential formula and a universal formula. This does not necessarily mean that ϕ is T -equivalent to a quantifier-free formula as the following example shows.

Example 4.48 Let VS be the vocabulary consisting of a single binary relation. Consider the VS -structure ZS = (Z|S). This structure has the set of integers as its underlying set and interprets S as the successor relation. That is, for any integers a and b, ZS |= S(a, b) if and only if b = a + 1. Let T be T h(ZS ).

Consider the formula z(S(x, z) S(z, y)). This formula says that y is the successor of the successor of x. We claim that this existential formula is not only preserved under supermodels of T , but also under submodels of T . To see this, consider the universal formula z1 z2(S(x, z1) S(z2, y) → z1 = z2). This formula says that there is at most one element between x and y. Since the theory T says that every element has a unique successor and no element is a successor of itself, this formula implies that there is exactly one element between x and y. So z(S(x, z) S(z, y)) is T -equivalent to this universal formula.

We now argue that z(S(x, z) S(z, y)) is not T -equivalent to a quantifierfree formula. Consider the ordered pairs (0, 2) and (4, 7) in Z2. Since the only atomic VS -formulas are S(x, y) and x = y, each of these pairs satisfy the same atomic formulas in the structure ZS . It follows that

ZS |= ψ(0, 2) if and only if ZS |= ψ(4, 7)

178 Properties of first-order logic

for any quantifier-free VS -formula ψ (by induction on the complexity of ψ). However,

ZS |= z(S(0, z) S(z, 2)) and ZS |= ¬ z(S(4, z) S(z, 7)).

This shows that the formula z(S(x, z) S(z, y)), although it is preserved under both submodels and supermodels of T , is not T -equivalent to a quantifier-free formula.

The following theorem provides a su cient criterion for a formula to be T -equivalent to a quantifier-free formula (provided T is complete). As the previous example shows, the property of being preserved under both submodels and supermodels of T is not su cient.

Theorem 4.49 Let T be a complete V-theory and let ϕ(x1, . . . , xn) be a V- formula. The following are equivalent:

(i) The formula ϕ(x1, . . . , xn) is T -equivalent to a quantifier-free formula.

¯

(ii) Let M be a model of T . Let a¯ and b be n-tuples from the universe of M such

¯ V |

that a¯ and b satisfy the same atomic -formulas in M . Then, M = ϕ(¯a) if

| ¯ and only if M = ϕ(b).

Proof Clearly (i) implies (ii). We must prove the converse. Suppose (ii) holds. We want to show that ϕ(¯x) is T -equivalent to a quantifier-free formula.

that T {ϕ(¯c)} ψ.

Claim T Q ϕ(¯c).

Proof Suppose not. Then T Q {¬ϕ(¯c)} is consistent. By Theorem 4.27, there is a model M of this set of V(C)-sentences. Let P be the set of all quantifier-free V(C)-sentences that hold in M . Note that P is closed under conjunction and

Q P.

Subclaim T P {ϕ(¯c)} is consistent.

Proof Otherwise, by compactness, T {ϕ(¯c)} ¬ψ for some ψ P. By the definition of Q we have ¬ψ Q. Since Q P, ¬ψ is in P. But ψ is also in P. This contradicts the fact that P has a model M . This contradiction proves the subclaim.

By Theorem 4.27, there is a model N of T P {ϕ(¯c)}. Both M and N are V(C)-structures. Let a¯ = (a1, . . . , an) be the n-tuple of elements from the

¯

underlying set of M that M interprets as the constants c¯. Let b = (b1, . . . , bn) be the n-tuple that N interprets as c¯. Let M and N be the reducts of M and N to the vocabulary V.

Since both M and N model the complete theory T , we can apply the Joint Embedding lemma 4.37. There exists a model D of T and elementary embeddings f : M → D and g : N → D. Consider the two n-tuples f (¯a) = (f (a1), . . . , f (an))

¯

and g(b) = (g(b1), . . . , g(bn)) of elements from the universe of D. Each of these tuples satisfy the same atomic formulas in D, namely those from P. However,

| ¬ | ¯

D = ϕ(f (¯a)) and D = ϕ(g(b)). This contradicts (ii). This contradiction proves the claim.

By compactness T {ψ} ϕ(¯c) for some ψ Q (since Q is closed under conjunction). Moreover, ψ, like every V(C)-sentence, has the form ψ0(¯c) for some V-formula ψ0(¯x). We have

Tψ0(¯c) → ϕ(¯c) by →-Introduction. Since ψ Q, we also have

Tϕ(¯c) → ψ0(¯c).

And so T ϕ(¯c) ↔ ψ0(¯c)

and T x¯(ϕ(¯x) ↔ ψ0(¯x)) by -Introduction.

4.5.2 Unions of chains.

Definition 4.50 A sequence M0 M1 M2 · · · of V-structures is called a chain. The length of the chain is the least ordinal α such that β < α for each Mβ in the sequence.

Proposition 4.51 Let M0 M1 M2 · · · be a chain of V-structures of length α (for some ordinal α). Suppose that, for some β < α, a¯ is an n-tuple of elements in the universe of Mβ that are not in the universe of Mι for ι < β. For any quantifier-free V-formula ϕ(x1, . . . , xn),

Mγ |= ϕ(¯a) for some γ such that β ≤ γ < α if and only if

Mγ |= ϕ(¯a) for all γ such that β ≤ γ < α.

Proof This follows immediately from the fact that quantifier-free formulas are preserved under both extensions and substructures (Proposition 2.55).

Definition 4.52 We define the union of a chain of V-structures M0 M1

M2 · · · . Let α be the length of this chain. The union of the chain is the

V-structure M defined as follows. The underlying set of M is β<α Uβ where Uβ is the underlying set of Mβ . Given any atomic V-formula ϕ(x1, . . . , xn) and any n-tuple (a1, . . . , an) of elements from the universe of M , M |= ϕ(a1, . . . , an) if