模型论对（ε，δ）方法说不！

  为什么“模型论对（ε，δ）方法说不！”？

  有人抱着（ε，δ）方法亲不够。

根据模型论基础（Fundamentals）第0章最后一段话的论断，可以明显看出这一结论；

  这段话的原文如下：

There is a notion of rank on prenex formulas

— the number of alternations of quantifiers. The usual formulas of elementary mathematics have prenex rank 0, i.e. no alternations of quantifiers. For example: (∀x)(∀y)(2xy ≤ x2 + y2). However, the ε−δ definition of a limit of a function has prenex rank 2 and is much more difficult for students to comprehend at first sight: (∀ε)(∃δ)(∀x)((0 < ε∧0 < |x−a| < δ) →|F(x)−L| < ε). A formula of prenex rank 4 would make any mathematician look twice.

袁萌  陈启清 1月5日

附件：

Fundamentals of Model Theory

CHAPTER 0

Models, Truth and Satisfaction

We will use the following symbols: • logical symbols: – the connectives ∧ ,∨ , ¬ , → , ↔ called “and”, “or”, “not”, “implies” and “iff” respectively – the quantifiers ∀ , ∃ called “for all” and “there exists” – an infinite collection of variables indexed by the natural numbers N v0 ,v1 , v2 , ... – the two parentheses ), ( – the symbol = which is the usual “equal sign” • constant symbols : often denoted by the letter c with subscripts • function symbols : often denoted by the letter F with subscripts; each function symbol is an m-placed function symbol for some natural number m ≥ 1 • relation symbols : often denoted by the letter R with subscripts; each relational symbol is an n-placed relation symbol for some natural number n ≥ 1. We now define terms and formulas. Definition 1. A term is defined as follows: (1) a variable is a term (2) a constant symbol is a term (3) if F is an m-placed function symbol and t1,...,tm are terms, then F(t1 ...tm) is a term. (4) a string of symbols is a term if and only if it can be shown to be a term by a finite number of applications of (1), (2) and (3). Remark. This is a recursive definition. Definition 2. A formula is defined as follows : (1) if t1 and t2 are terms, then (t1 = t2) is a formula. (2) if R is an n-placed relation symbol and t1,...,tn are terms, then (R(t1 ...tn)) is a formula. (3) if ϕ is a formula, then (¬ϕ) is a formula (4) if ϕ and ψ are formulas then so are (ϕ∧ψ), (ϕ∨ψ), (ϕ → ψ) and (ϕ ↔ ψ) (5) if vi is a variable and ϕ is a formula, then (∃vi)ϕ and (∀vi)ϕ are formulas (6) a string of symbols is a formula if and only if it can be shown to be a formula by a finite number of applications of (1), (2), (3), (4) and (5). Remark. This is another recursive definition. ¬ϕ is called the negation of ϕ;ϕ ∧ψ is called the conjunction of ϕ and ψ; and ϕ∨ψ is called the disjunction of ϕand ψ.

4

0. MODELS, TRUTH AND SATISFACTION 5

Definition 3. A subformula of a formula ϕ is defined as follows: (1) ϕ is a subformula of ϕ (2) if (¬ψ) is a subformula of ϕ then so is ψ (3) if any one of (θ∧ψ), (θ∨ψ), (θ → ψ) or (θ ↔ ψ) is a subformula of ϕ, then so are both θ and ψ (4) if either (∃vi)ψ or (∀vi)ψ is a subformula of ϕ for some natural number i, then ψ is also a subformula of ϕ (5) A string of symbols is a subformula of ϕ, if and only if it can be shown to be such by a finite number of applications of (1), (2), (3) and (4).

Definition 4. A variable vi is said to occur bound in a formula ϕ iff for some subformula ψ of ϕ either (∃vi)ψ or (∀vi)ψ is a subformula of ϕ. In this case each occurrence of vi in (∃vi)ψ or (∀vi)ψ is said to be a bound occurrence of vi. Other occurrences of vi which do not occur bound in ϕ are said to be free.

Example 1.

F(v3) is a term, where F is a unary function symbol. ((∃v3)(v0 = v3)∧(∀v0)(v0 = v0)) is a formula. In this formula the variable v3 only occurs bound but the variable v0 occurs both bound and free.

Exercise 1. Using the previous definitions as a guide, define the substitution of a term t for a variable vi in a formula ϕ. In particular, demonstrate how to substitute the term for the variable v0 in the formula of the example above. Definition 5. A language L is a set consisting of all the logical symbols with perhaps some constant, function and/or relational symbols included. It is understood that the formulas of L are made up from this set in the manner prescribed above. Note that all the formulas of L are uniquely described by listing only the constant, function and relation symbols of L. We use t(v0,...,vk) to denote a term t all of whose variables occur among v0,...,vk. We use ϕ(v0,...,vk) to denote a formula ϕ all of whose free variables occur among v0,...,vk.

Example 2. These would be formulas of any language : • For any variable vi: (vi = vi) • for any term t(v0,...,vk) and other terms t1 and t2: ((t1 = t2) → (t(v0,...,vi−1,t1,vi+1,...,vk) = t(v0,...,vi−1,t2,vi+1,...,vk))) • for any formula ϕ(v0,...,vk) and terms t1 and t2: ((t1 = t2) → (ϕ(v0,...,vi−1,t1,vi+1,...,vk) ↔ ϕ(v0,...,vi−1,t2,vi+1,...,vk))) Note the simple way we denote the substitution of t1 for vi. Definition 6. A model (or structure) A for a language L is an ordered pair hA,Ii where A is a nonempty set and I is an interpretation function with domain the set of all constant, function and relation symbols of L such that: (1) if c is a constant symbol, then I(c) ∈ A; I(c) is called a constant

0. MODELS, TRUTH AND SATISFACTION 6

(2) if F is an m-placed function symbol, then I(F) is an m-placed function on A (3) if R is an n-placed relation symbol, then I(R) is an n-placed relation on A. A is called the universe of the model A. We generally denote models with Gothic letters and their universes with the corresponding Latin letters in boldface. One set may be involved as a universe with many different interpretation functions of the language L. The model is both the universe and the interpretation function. Remark. The importance of Model Theory lies in the observation that mathematical objects can be cast as models for a language. For instance, the real numbers with the usual ordering < < < and the usual arithmetic operations, addition + + + and multiplication · · · along with the special numbers 0 and 1 can be described as a model.Let L contain one two-placed (i.e. binary) relation symbol R0, two two-placed function symbols F1 and F2 and two constant symbols c0 and c1. We build a model by letting the universe A be the set of real numbers. The interpretation function I will map R0 to < < <, i.e. R0 will be interpreted as < < <. Similarly, I(F1) will be + + +, I(F2) will be · · ·, I(c0) will be 0 and I(c1) will be 1. So hA,Ii is an example of a model for the language described by {R0,F1,F2,c0,c1}. We now wish to show how to use formulas to express mathematical statements about elements of a model. We first need to see how to interpret a term in a model.

Definition 7. The value t[x0,...,xq] of a term t(v0,...,vq) at x0,...,xq in the universe A of the model A is defined as follows: (1) if t is vi then t[x0,··· ,xq] is xi, (2) if t is the constant symbol c, then t[x0,...,xq] is I(c), the interpretation of c in A, (3) if t is F(t1 ...tm) where F is an m-placed function symbol and t1,...,tm are terms, then t[x0,...,xq] is G(t1[x0,...,xq],...,tm[x0,...,xq]) where G is the m-placed function I(F), the interpretation of F in A. Definition 8. Suppose A is a model for a language L. The sequencex 0,...,xq of elements of A satisfies the formula ϕ(v0,...,vq) all of whose free and bound variables are among v0,...,vq, in the model A, written A |= ϕ[x0,...,xq] provided we have: (1) if ϕ(v0,...,vq) is the formula (t1 = t2), then A |= (t1 = t2)[x0,...,xq] means that t1[x0,...,xq] equals t2[x0,...,xq], (2) if ϕ(v0,...,vq) is the formula (R(t1 ...tn)) where R is an n-placed relation symbol, then A |= (R(t1 ...tn))[x0,...,xq] means S(t1[x0,...,xq],...,tn[x0,...,xq]) where S is the n-placed relation I(R), the interpretation of R in A,(3) if ϕ is (¬θ), then A |= ϕ[x0,...,xq] means not A |= θ[x0,...,xq], (4) if ϕ is (θ∧ψ), then A |= ϕ[x0,...,xq] means both A |= θ[x0,...,xq] and A |= ψ[x0,...xq],

0. MODELS, TRUTH AND SATISFACTION 7

(5) if ϕ is (θ∨ψ) then A |= ϕ[x0,...,xq] means either A |= θ[x0,...,xq] or A |= ψ[x0,...,xq], (6) if ϕ is (θ → ψ) then A |= ϕ[x0,...,xq] means that A |= θ[x0,...,xq] implies A |= ψ[x0,...,xq], (7) if ϕ is (θ ↔ ψ) then A |= ϕ[x0,...,xq] means that A |= θ[x0,...,xq] iff A |= ψ[x0,...,xq], (8) if ϕ is ∀viθ, then A |= ϕ[x0,...,xq] means for every x ∈ A,A |= θ[x0,...,xi−1,x,xi+1,...,xq], (9) if ϕ is ∃viθ, then A |= ϕ[x0,...,xq] means for some x ∈ A,A |= θ[x0,...,xi−1,x,xi+1,...,xq]. Exercise 2. Each of the formulas of Example 2 is satisfied in any model A for any language L by any (long enough) sequence x0,x1,...,xq of A. This is where you test your solution to Exercise 1, especially with respect to the term and formula from Example 1.

We now prove two lemmas which show that the preceding concepts are welldefined. In the first one, we see that the value of a term only depends upon the values of the variables which actually occur in the term. In this lemma the equal sign = is used, not as a logical symbol in the formal sense, but in its usual sense to denote equality of mathematical objects — in this case, the values of terms, which are elements of the universe of a model. Lemma 1. Let A be a model for L and let t(v0,...,vp) be a term of L. Letx 0,...,xq and y0,...,yr be sequences from A such that p ≤ q and p ≤ r, and letx i = yi whenever vi actually occurs in t(v0,...,vp). Then t[x0,...,xq] = t[y0,...,yr] .

Proof. We use induction on the complexity of the term t. (1) If t is vi then xi = yi and so we have t[x0,...,xq] = xi = yi = t[y0,...,yr] since p ≤ q and p ≤ r. (2) If t is the constant symbol c, then t[x0,...,xq] = I(c) = t[y0,...,yr] where I(c) is the interpretation of c in A.(3) If t is F(t1 ...tm) where F is an m-placed function symbol, t1,...,tm are terms and I(F) = G, then t[x0,...,xq] = G(t1[x0,...,xq],...,tm[x0,...,xq]) and t[y0,...,yr] = G(t1[y0,...,yr],...,tm[y0,...,yr]). By the induction hypothesis we have that ti[x0,...,xq] = ti[y0,...,yr] for 1 ≤ i ≤ m since t1,...,tm have all their variables among {v0,...,vp}. So we have t[x0,...,xq] = t[y0,...,yr].

---

 

0. MODELS, TRUTH AND SATISFACTION 8

In the next lemma the equal sign = is used in both senses — as a formal logical symbol in the formal language L and also to denote the usual equality of mathematical objects. This is common practice where the context allows the reader to distinguish the two usages of the same symbol. The lemma confirms that satisfaction of a formula depends only upon the values of its free variables. Lemma 2. Let A be a model for L and ϕ a formula of L, all of whose free and bound variables occur among v0,...,vp. Let x0,...,xq and y0,...,yr (q,r ≥ p) be two sequences such that xi and yi are equal for all i such that vi occurs free in ϕ. Then A |= ϕ[x0,...,xq] iff A |= ϕ[y0,...,yr] Proof. Let A and L be as above. We prove the lemma by induction on the complexity of ϕ. (1) If ϕ(v0,...,vp) is the formula (t1 = t2), then we use Lemma 1 to get: A |= (t1 = t2)[x0,...,xq] iff t1[x0,...,xq] = t2[x0,...,xq] iff t1[y0,...,yr] = t2[y0,...,yr] iff A |= (t1 = t2)[y0,...,yr]. (2) If ϕ(v0,...,vp) is the formula (R(t1 ...tn)) where R is an n-placed relation symbol with interpretation S, then again by Lemma 1, we get: A |= (R(t1 ...tn))[x0,...,xq] iff S(t1[x0,...,xq],...,tn[x0,...,xq]) iff S(t1[y0,...,yr],...,tn[y0,...,yr]) iff A |= R(t1 ...tn)[y0,...,yr]. (3) If ϕ is (¬θ), the inductive hypothesis gives that the lemma is true for θ. So, A |= ϕ[x0,...,xq] iff not A |= θ[x0,...,xq] iff not A |= θ[y0,...,yr] iff A |= ϕ[y0,...,yr]. (4) If ϕ is (θ∧ψ), then using the inductive hypothesis on θ and ψ we get A |= ϕ[x0,...,xq] iff both A |= θ[x0,...,xq] and A |= ψ[x0,...xq] iff both A |= θ[y0,...,yr] and A |= ψ[y0,...yr] iff A |= ϕ[y0,...,yr]. (5) If ϕ is (θ∨ψ) then A |= ϕ[x0,...,xq] iff either A |= θ[x0,...,xq] or A |= ψ[x0,...,xq] iff either A |= θ[y0,...,yr] or A |= ψ[y0,...,yr] iff A |= ϕ[y0,...,yr]. (6) If ϕ is (θ → ψ) then A |= ϕ[x0,...,xq] iff A |= θ[x0,...,xq] implies A |= ψ[x0,...,xq] iff A |= θ[y0,...,yr] implies A |= ψ[y0,...,yr] iff A |= ϕ[y0,...,yr].

0. MODELS, TRUTH AND SATISFACTION 9

(7) If ϕ is (θ ↔ ψ) then A |= ϕ[x0,...,xq] iff we have A |= θ[x0,...,xq] iff A |= ψ[x0,...,xq] iff we have A |= θ[y0,...,yr] iff A |= ψ[y0,...,yr] iff A |= ϕ[y0,...,yr]. (8) If ϕ is (∀vi)θ, then A |= ϕ[x0,...,xq] iff for every z ∈ A,A |= θ[x0,...,xi−1,z,xi+1,...,xq] iff for every z ∈ A,A |= θ[y0,...,yi−1,z,yi+1,...,yr] iff A |= ϕ[y0,...,yr]. The inductive hypothesis uses the sequences x0,...,xi−1,z,xi+1,...,xq and y0,...,yi−1,z,yi+1,...,yr with the formula θ. (9) If ϕ is (∃vi)θ, then A |= ϕ[x0,...,xq] iff for some z ∈ A,A |= θ[x0,...,xi−1,z,xi+1,...,xq] iff for some z ∈ A,A |= θ[y0,...,yi−1,z,yi+1,...,yr] iff A |= ϕ[y0,...,yr]. The inductive hypothesis uses the sequences x0,...,xi−1,z,xi+1,...,xq and y0,...,yi−1,z,yi+1,...,yr with the formula θ.

---

 Definition 9. A sentence is a formula with no free variables. If ϕ is a sentence, we can write A |= ϕ without any mention of a sequence fromA since by the previous lemma, it doesn’t matter which sequence from A we use. In this case we say: • A satisfies ϕ • or A is a model of ϕ • or ϕ holds in A • or ϕ is true in A If ϕ is a sentence of L, we write |= ϕ to mean that A |= ϕ for every model Afor L. Intuitively then, |= ϕ means that ϕ is true under any relevant interpretation (model forL). Alternatively, no relevant example (model forL) is a counterexample to ϕ — so ϕ is true. Lemma 3. Let ϕ(v0,...,vq) be a formula of the language L. There is anotherformula ϕ0(v0,...,vq) of L such that (1) ϕ0 has exactly the same free and bound occurrences of variables as ϕ. (2) ϕ0 can possibly contain ¬, ∧ and ∃ but no other connective or quantifier. (3) |= (∀v0)...(∀vq)(ϕ ↔ ϕ0) Exercise 3. Prove the above lemma by induction on the complexity of ϕ. As a reward, note that this lemma can be used to shorten future proofs by induction on complexity of formulas.

 

Definition 10. A formula ϕ is said to be in prenex normal form whenever (1) there are no quantifiers occurring in ϕ, or (2) ϕ is (∃vi)ψ where ψ is in prenex normal form and vi does not occur bound in ψ, or

0. MODELS, TRUTH AND SATISFACTION 10

(3) ϕ is (∀vi)ψ where ψ is in prenex normal form and vi does not occur bound in ψ.

Remark. If ϕ is in prenex normal form, then no variable occurring in ϕ occurs both free and bound and no bound variable occurring in ϕ is bound by more than one quantifier. In the written order, all of the quantifiers precede all of the connectives. Lemma 4. Let ϕ(v0,...,vp) be any formula of a language L. There is a formulaϕ ∗ of L which has the following properties: (1) ϕ∗ is in prenex normal form (2) ϕ and ϕ∗ have the same free occurrences of variables, and (3) |= (∀v0)...(∀vp)(ϕ ↔ ϕ∗) Exercise 4. Prove this lemma by induction on the complexity of ϕ.

There is a notion of rank on prenex formulas

— the number of alternations of quantifiers. The usual formulas of elementary mathematics have prenex rank 0, i.e. no alternations of quantifiers. For example: (∀x)(∀y)(2xy ≤ x2 + y2). However, the ε−δ definition of a limit of a function has prenex rank 2 and is much more difficult for students to comprehend at first sight: (∀ε)(∃δ)(∀x)((0 < ε∧0 < |x−a| < δ) →|F(x)−L| < ε). A formula of prenex rank 4 would make any mathematician look twice.

CHAPTER 1