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

180 Properties of first-order logic

and only if Mβ |= ϕ(a1, . . . , an) for all Mβ containing each ai in its universe (by the previous proposition, we can replace “all” with “some”). This describes how M interprets the vocabulary V and completes our definition of this structure.

Example 4.53 Let V< be the vocabulary consisting of a single binary relation <. We define a chain of V<-structures of length ω. For each finite ordinal i, let Mi be the V<-structure that has underlying set {−i, −i + 1, −i + 2, −i + 3, . . . , } and interprets < as the usual order.

So the underlying set of M0 is {0, 1, 2, . . .}, the underlying set of M1 is {−1, 0, 1, 2, . . .},

the underlying set of M2 is {−2, −1, 0, 1, 2, . . .}, and so forth.

This forms a chain of V<-structures. The length of this chain is ω. The union of this chain is the V<-structure M that interprets < as the usual order on the integers (that is, M is the structure Z< from Section 2.4.3).

Note that each Mi is necessarily a substructure of the union M . However, the structure M can be quite di erent from the Mis. In the previous example, each Mi is isomorphic to the structure N< = (N, <), but the union M is not even elementarily equivalent to this structure (this was shown in Section 2.3.4).

Definition 4.54 An elementary chain is a chain of the form M0 M1 M2 · · ·

Unlike the situation in Example 4.53, if a chain is an elementary chain, then the union of the chain is elementarily equivalent to each structure in the chain.

Proposition 4.55 The union of an elementary chain is an elementary extension of each structures in the chain.

Proof Let M0 M1 M2 · · · be an elementary chain of length α. Let M be the union of this chain. Given β < α, we apply the Tarski–Vaught criterion (Corollary 4.31) to show that Mβ M .

Let ψ(x1, . . . , xn, y) be an V-formula and let a¯ be an n-tuple of elements from the underlying set of Mβ . Suppose that M |= yψ(¯a, y). It su ces to show that Mβ |= yψ(¯a, y). By the semantics of , M |= ψ(¯a, b) for some b in the universe of M . By the definition of M , b must be in the universe of Mγ for some γ < α. So, Mγ |= yψ(¯a, y). Since the chain is elementary, Mβ |= yψ(¯a, y) as was required to show.

Definition 4.56 A formula ϕ(x1, . . . , xn) is said to be preserved under unions of chains if for any chain M0 M1 M2 · · · and any n-tuple a¯ of elements from the universe of M0, if each Mi models ϕ(¯a), then so does the union M of this chain.

If M0 M1 M2 · · · is an elementary chain, then each Mi models ϕ(¯a) if and only if the union M models ϕ(¯a) for any n-tuple of elements from the

universe of M0. For the formula ϕ(¯x) to be preserved under unions of chains, this must be true for arbitrary chains. We want to determine which formulas have this property. Clearly, by the definition of the union of a chain, every atomic formula is preserved under unions of chains. Moreover, every existential formula is preserved under unions of chains since they are preserved under extensions (Proposition 2.72). Example 4.53 demonstrates that not all formulas are preserved under unions of chains. In that example, each Mi in the chain models the sentence x y¬(y < x), but the union M does not.

Definition 4.57 A formula is said to be 2 if it has the form x1 · · · xn y1 · · ·

ymϕ for some quantifier-free formula ϕ.

More generally, we can define a hierarchy for all formulas in prenex normal form. A formula is 1 if it is universal and 1 if it is an existential formula. For each n N, we define the n+1 formulas inductively. A formula is n+1 if it has the form x1 · · · xmϕ for some n formula ϕ. Likewise, a formula is n+1 if it has the form x1 · · · xmϕ for some n formula ϕ.

Example 4.58 Let ϕ(¯x) be a quantifier-free formula.

x1 x2 x3 x4 x5 x6 x7 x8ϕ(¯x) is a 8 formula, andx1 x2 x3 x4 x5 x6 x7 x8ϕ(¯x) is a 3 formula.

Note that for m < n, a m formula is equivalent to both a n formula and an formula. The 2 formulas were singled out in the previous definition because these are the formulas of immediate interest. The following proposition shows that these formulas are preserved under unions of chains. As demonstrated by the sentence x y¬(y < x), the same cannot be said of 2 sentences nor for n formulas for n > 2.

Proposition 4.59 2 formulas are preserved under unions of chains.

Proof Let ϕ(x1, . . . , xn) be a 2 formula. Let M0 M1 M2 · · · be a chain and let M be the union of this chain. Let a¯ be an n-tuple of elements from the universe of M0. Suppose that each Mi |= ϕ(¯a). We must show that M |= ϕ(¯a).

Since it is a 2 formula, ϕ(¯x) has the form z1 · · · zl y1 · · · ymϕ0(¯x, y¯, z¯) where ϕ0 is quantifier-free. Let c¯ = (c1, . . . , cl) be an arbitrary l-tuple of elements from the universe UM of M . Each of these elements is contained in the universe

| ¯

of some structure Mβ in the chain. Since ϕ(¯a) holds in Mβ , Mβ = ϕ0(¯a, b, c¯) for

¯

some m-tuple b of elements from its universe. Since quantifier-free formulas are preserved under extensions,

| ¯

M = ϕ0(¯a, b, c¯). By the semantics of ,

M |= y1 · · · ymϕ0(¯a, y¯, c¯).

Since c¯ is arbitrary,

M |= z1 · · · zl y1 · · · ymϕ0(¯a, y¯, z¯)

by the semantics of . Thus, we have shown that M |= ϕ(¯a).

Let T be a theory. Let M0 M1 M2 · · · be a chain of models of T . If a formula is T -equivalent to a 2 formula, then, by Proposition 4.59, it is preserved under the union of this chain. We next prove that the converse of this also holds. If a formula is preserved under unions of chains of models of T , then that formula must be T -equivalent to a 2 formula. The following proposition shows that this is true for sentences. As with Proposition 4.45, this is only interesting for sentences that are not in T .

Proposition 4.60 Let T be a theory. If a sentence is preserved under unions of chains of models of T , then it is T -equivalent to a 2 sentence.

Proof Suppose that the sentence ϕ is preserved under unions of chains of models of T . Let C be the set of all 2 sentences ψ such that T {ϕ} ψ.

Claim T C ϕ.

Proof Suppose not. Then T C {¬ϕ} has a model M0.

We aim to construct a chain M0 N1 M1 N2 M2 · · · such that, for each i N

•Mi−1 Mi, and

•each Ni models T {ϕ}.

The existence of such a chain su ces to prove the claim. To see this, suppose that we have successfully constructed this chain and let M be the union. Then, by the definition of the union of a chain, M is also the union of both the chain M0 M1 M2 · · · and the chain N1 N2 N3 · · · . Since the former chain is an elementary chain and M0 models ¬ϕ, the union M models ¬ϕ by Proposition 4.55. Since each Ni models ϕ and ϕ is preserved under unions of chains of models of T , M models ϕ. This is a contradiction and this contradiction proves the claim.

So we must describe how to construct a chain M0 N1 M1 N2 · · ·

possessing the above properties. We have already defined M0. Suppose that, for some i N we have defined Mi−1 so that M0 Mi−1. Then Mi−1 |= T {¬ϕ}.

We must show that there exists an extension Ni of Mi−1 that models T {ϕ}. Let ED (Mi−1) be the set of all universal sentences in prenex normal form that are in ED(Mi−1).

Subclaim ED (Mi−1) T {ϕ} is consistent.

the Joint Embedding lemma 4.37 states that any two models M and N of a complete V-theory T can be elementarily embedded into a single model of T . Here it is understood that M and N have the same vocabulary as T . In this section, we show that this remains true even if M is a V1-structure and N is a V2-structure where V1 and V2 are di erent expansions of V. The primary result of this section is Robinson’s Joint Consistency lemma. From this lemma, we are able to deduce results that are analogous to the amalgamation theorems of Section 4.4. We are also able to deduce the Craig Interpolation theorem and the Beth Definability theorem for first-order logic.

Lemma 4.63 (Robinson’s Joint Consistency) Let T1 be a V1-theory and let T2 be a V2-theory. Let V∩ = V1 ∩ V2 and let V = V1 V2. If T1 ∩ T2 is a complete V∩-theory, then T1 T2 is a V -theory.

Proof We show that there exists a V∩-structure D that has expansions D1 |= T1 and D2 |= T2. If such a D exists, then we can define D to be the V -structure having the same underlying set as D that interprets V1 in the same manner as D1 and V2 in the same manner as D2. Since D is a model of both T1 and T2, we can conclude that T1 T2 is a theory as the lemma states.

To prove the existence of D, we construct elementary chains

M0 M1 M2 M3 · · · of models of T1 and

N0 N1 N2 N3 · · · of models of T2.

The arrows in this diagram represent embeddings that are elementary with

represented by . We want to define these embeddings in such a way that gi(fi(a)) = a for any a in the underlying set of Mi and fi+1(gi(b)) = b for any b in the underlying set of Ni.

Before constructing these chains, we show how their existence proves the lemma. Suppose that we have successfully defined two chains as described in the previous paragraph. Our goal is to find a V∩-structure D that has two expansions that model each of T1 and T2. Let M be the union of the chain M0 M1 M2 · · · and let D be the reduct of M to a V∩-theory (so D is

˜

the union of the chain of Mis). By Proposition 4.55, the expansion M of D

models T1. To complete the proof of the lemma, we must define an expansion of D that models T2.

Let N be the union of the chain N0 N1 · · · . Then N |= T2 by Pro-

only if fi(a) = b for some i. Note that fi(a) = b implies fj (a) = b for all j > i (since gi(fi(a)) = a and fi+1(gi(b)) = b). So f is a well defined function. Since each fi is elementary, so is f . Moreover, f is also one-to-one and onto. So f is an isomorphism as claimed. Let D2 be the expansion of D to a V2-structure defined as follows. For any V2-formula ϕ(x1, . . . , xn),

D2 |= ϕ(a1, . . . , an) if and only if N |= ϕ(f (a1), . . . , f (an))

for any n-tuple (a1, . . . , an) of elements from the underlying set of D. Since N models T2, so does D2. So given two chains as described above, we can define the V∩-structure D having expansions M |= T1 and D2 |= T2 as was required to prove the lemma.

It remains to be shown that the two desired chains can be constructed. We carry out this construction by repeatedly applying Claim 2 below. As a stepping-stone toward Claim 2, we prove the following:

Claim 1 For any M |= T1 and N |= T2 there exists an elementary extension

denote the reduct to the vocabulary V∩.

ED ˜ ED

Proof We show that the set (M ) (N ) is consistent. We assume that the

ED ˜ ED V only constants occuring in both (M ) and (N ) are those constants in ∩.

some θ ED(M ). As a sentence in ED(M ), θ has the form ϕ(¯a) for some V∩-

formula ϕ(¯x) and n-tuple a¯ of constants not in ED(N ). If, ED(N ) ¬ϕ(¯a), then ED(N ) x¯¬ϕ(¯x) by -Introduction. Since the theory T2 contains the complete V∩-theory T , the V∩-sentence x¯¬ϕ(¯x) must be in T . This contradicts the facts

embedding (where the tildes again denote the reduct to the vocabulary V∩).

Proof Let C = {ca|a UN } be a set consisting of constants for each element a in the underlying set UN of N . For any vocabulary V, let V(C) denote the expansion

186 Properties of first-order logic

V C. Let N (C) be the expansion of N to a V1(C)-structure that interprets each

˜

c¯ of constants from C. It follows that N (C) and M (C) are models of the same complete V∩(C)-theory. By Claim 1, there exist elementary extension N +(C) of

preserve constants, f (g(a)) = a for each a UN . Let N + be the reduct of N +(C) to a V2-structure.

Since T1 and T2 are theories, they have models. To begin the construction

Having successfully defined M0, N0, and f0, we proceed to define the rest of the two chains inductively.

Suppose that, for some i, we have defined Mi |= T1, Ni |= T2 and elementary

in the underlying set of Mi. (Here we have applied Claim 2 with Mi playing the role of N and Ni playing the role of M .) Applying Claim 2 yet again, there exist

such that fi+1(gi(b)) = b for any b in the underlying set of Ni. (Here Ni plays the role of N and Mi+1 plays the role of M .) Repeating this process produces the two desired chains.

The following generalization of the Joint Embedding lemma is an immediate consequence of Robinson’s Joint Consistency lemma.

Corollary 4.64 Let M be a V1-structure and N be a V2-structure such that M and N are elementarily equivalent as (V1 ∩ V2)-structures. There exists a (V1 V2)-structure D such that M can be V1-elementarily embedded into D and N can be V2-elementarily embedded into D.

Proof Let T1 be ED(M ) and T2 be ED(N ). By Robinson’s Joint Consistency lemma, there exists a model D of T1 T2.

Note that if V1 = V2, then the previous corollary is identical to the Joint Embedding lemma. Likewise, we can generalize the Elementary Amalgamation Over Structures theorem 4.38. We leave this as Exercise 4.34. We now turn our attention to the theorems of Craig and Beth.

Theorem 4.65 (Craig Interpolation) Let ϕ be a V1 sentence and ψ be a

V2-sentence. If |= ϕ → ψ, then there exists a sentence θ that is both a V1-sentence and a V2-sentence such that |= ϕ → θ and |= θ → ψ.

Proof Let V∩ = V1 ∩ V2. Let C be the set of all V∩ consequences of ϕ. That is C is the set of all V∩-sentences θ such that |= ϕ → θ. We want to show that ψ is a consequence of C.

Suppose for a contradiction that M is a V1 V2-structure that models both C and ¬ψ. Let T be the V∩-theory of M .

Claim T {ϕ} is consistent.

Proof Otherwise, T ¬ϕ. Since T is closed under conjunctions, {θ} ¬ϕ for some θ T (by compactness). So the contrapositive {ϕ} ¬θ also holds (by Example 1.34). So ¬θ is a consequence of ϕ and so ¬θ C. Since C T , we have both θ and ¬θ in T . Since M is a model of T , this is a contradiction.

The consistency of T {ϕ} leads to another contradiction. Let T1 = T {ϕ} and T2 = T {¬ψ}. If both T1 and T2 are consistent, then so is T1 T2 by Robinson’s Joint Consistency lemma. But since |= ϕ → ψ, T1 T2 cannot be consistent. The assumption that C {¬ψ} is satisfiable must be incorrect. It follows that C ψ. Since C is closed under conjunctions, {θ} ψ for some θ C. It follows that |= θ → ψ as was required.

In order to state the Beth Definability theorem concisely, we introduce some terminology. We distinguish between two ostensibly di erent notions of definability. Beth’s Definability theorem states that, for first-order logic, these two notions are the same.

Definition 4.66 Let T be a V-theory and let R be an n-ary relation in V. For any V V, we say that R is explicitly defined by T in terms of V if there exists a V -formula ϕ(x1, . . . , xn) such that

T ϕ(x1, . . . , xn) ↔ R(x1, . . . , xn).

Example 4.67 Let V = {≤, +, ·, 0, 1} and let V = {+, ·, 0, 1}. Let Ror = (R| ≤, +, ·, 0, 1) be the structure that interprets V in the usual way on the real numbers. Let T = T h(Ror). Then the binary relation ≤ is explicitly defined by T in terms of V . To see this, let ϕ(x, y) be the V -formula z(x+(z ·z) = y). Since (z ·z) ≥ 0 for any real number z, T ϕ(x, y) ↔ x ≤ y.

Definition 4.68 Let T be a V-theory and let R be an n-ary relation in V. For any V V, we say that R is implicitly defined by T in terms of V if the following holds. Given any V -structure M and two expansions N1 and N2 of M to V-structures that model T ,

N1 |= R(¯a) if and only if N2 |= R(¯a)

for any n-tuple a¯ of elements from the underlying set of M .

If R is explicitly defined by T in terms of V, then it is implicitly defined as well. So the binary relation ≤ from Example 4.67 is implicitly defined by T in terms of V . We now give a nonexample.

Example 4.69 Let M be the structure (Z|B) that interprets the binary relation B as a symmetric successor relation. By this we mean that M |= B(a, b) if and only if a = b + 1 or b = a + 1. Let N1 = (Z|B, <) be the expansion of M that interprets < as the usual order on the integers. Let N2 be the expansion of M that interprets < backwards. That is, N2 |= a < b if and only if the integer a is greater than b.

Let T = T h(N1). Since N1 and N2 are distinct expansions of M that model T , the relation < is not implicitly defined by T in terms of {B}.

If we replace the relation B with the successor relation S from Example 4.48, then the same conclusion holds. The relation < is not implicitly defined by T h(Z|S, <) in terms of {S}. We leave the verification of this as Exercise 4.37.

Proposition 4.70 A relation R is implicitly defined by T in terms of V if and only if for any V-structure M , there is at most one expansion N of M to a V {R}-structure such that T h(N ) T .

Proof Exercise 4.29.

Example 4.71 Let TQ be the theory of the rational numbers in the vocabulary Var = {0, 1, +, ·}. Let V = Var {R} where R is a ternary relation. Let T be the theory TQ {ϕ} for some V-sentence ϕ.

If ϕ has the form x y z(ψ(x, y, z) ↔ R(x, y, z)) for some Var-formula ψ(x, y, z), then, by definition, R is explicitly defined by T over Var. In this case, there is exactly one way to expand a given model of TQ to a model of T .

Conversely, suppose there is exactly one way to expand any given model of TQ to a model of T . Then, by Proposition 4.70, R is implicitly defined by T over Var. In this case, ϕ may not have the form x y z(ψ(x, y, z) ↔ R(x, y, z)). For example, suppose that ϕ is the V-sentence

x y z u v w(u · v = 1 (R(x, y, z) (x + x + y = z + v + u)

(w + y = 0 (R(x, y, z) → x + x = z + w).

There is exactly one way to expand a model of TQ to a model of this sentence. So this sentence implicitly defines the ternary relation R.

Beth’s Definability theorem states that R is defined implicitly if and only if it is defined explicitly. This means that the above sentence ϕ must be TQ- equivalent to a sentence of the form x y z(ψ(x, y, z) ↔ R(x, y, z)). Indeed, we can take ψ(x, y, z) to be 2x + y = z. We leave the verification of this to the reader.