复旦大学：《离散数学 Discrete Mathematics》英文讲义_15 Application and Limitations

Discrete Mathematics(II) Spring 2012 Lecture 15: Application and limitations Lecturer. yil 1 Overview In this lecture, we first introduce several applications of first order logic. And then we show you the amazing aspect of the logic. Finally, we show you the limitation of logic 2 Applications In this section, all application are concepts learned in previous courses, which are chosen from set theory, graph theory, and algebra. Example 1 (linear order). A structure A=< A, < is called an ordering if it is a model of the (vx)(-x<x) Pord=(Vr)(y)(Va)((<yAy<x))2<x) (Va)y(a<yva=yVy<a Example 2(dense order). In order to describe dense linear orders, we could add into linear order the following sentense vrVy(x<y→3z( x<D) Example 3(Graphs). Let L=(R where R is a binary relation. We can characterize undirected graphs without self-loop with the following sentences 1. VcR(, 2. Va Vy (R(c, y),R(y, r) Example 4(Equivalence relation). The equivalence relation can be formalized with the aid of a single binary relation symbols as folllows: (cR(, r), (vx)(y)(vz)(GR(x,y)∧R(y,z))→R(x,z) Example 5. Suppose R is a binary relation. If it is non-trival, which means nonempty transitive and symmetric, then it must be reflexive Ve can represent these properties as

Discrete Mathematics (II) Spring 2012 Lecture 15: Application and Limitations Lecturer: Yi Li 1 Overview In this lecture, we first introduce several applications of first order logic. And then we show you the amazing aspect of the logic. Finally, we show you the limitation of logic. 2 Applications In this section, all application are concepts learned in previous courses, which are chosen from set theory, graph theory, and algebra. Example 1 (linear order). A structure A = is called an ordering if it is a model of the following sentences: Φord =    (∀x)(¬x < x), (∀x)(∀y)(∀z)((x < y ∧ y < z) → x < z), (∀x)(∀y)(x < y ∨ x = y ∨ y < x). Example 2 (dense order). In order to describe dense linear orders, we could add into linear order the following sentense ∀x∀y(x < y → ∃z(x < z ∧ z < y)) Example 3 (Graphs). Let L = {R} where R is a binary relation. We can characterize undirected graphs without self-loop with the following sentences: 1. ∀x¬R(x, x), 2. ∀x∀y(R(x, y) → R(y, x)). Example 4 (Equivalence relation). The equivalence relation can be formalized with the aid of a single binary relation symbols as folllows: Φequ =    (∀x)R(x, x), (∀x)(∀y)(R(x, y) → R(y, x), (∀x)(∀y)(∀z)((R(x, y) ∧ R(y, z)) → R(x, z)). Example 5. Suppose R is a binary relation. If it is non-trival, which means nonempty, transitive and symmetric, then it must be reflexive. We can represent these properties as 1

1. trans=( r)(y)(Va((r(, y)A R(y, a)),R(a, a)) 2. sym=(Va)(Vy(R(a, y)+R(y, r)) 3. ref=(V)R(, a) 4. nontriv=(V)(u)R(a, y) Then Itrans, sym, nontriuFref Proof. We now prove that T,S,NI RWe have the following tableaux as Figure??. It is a FVrR( x R(, y) 3yR(e, yI TR(C, d), new d vvy(R(x,y)→R(y,x)) Tvy(R(c,y)→R(y,c) [(R(cd)→Rac y(R(xy)∧R(2)→R(x2 vy2(Rc)AR(2)→R(2 vz(R(cd)∧R(d,2)→RC2) R(cd)∧R(,c)→Rc FR(C d)AR(, a] TR(C,c) FR(c, d) FR(d, el T(R(cd)→R(a.c) Red[⑦R(d Figure 1: The tableau proof tableau proof. It is proved

1. trans = (∀x)(∀y)(∀z)((R(x, y) ∧ R(y, z)) → R(x, z)), 2. sym = (∀x)(∀y)(R(x, y) → R(y, x)), 3. ref = (∀x)R(x, x), 4. nontriv = (∀x)(∃y)R(x, y). Then {trans, sym, nontriv} |= ref. Proof. We now prove that {T, S, N} |= R.We have the following tableaux as Figure ??. It is a F∀xR(x, x) F R(c, c), new c T∀x∃yR(x, y) T∃yR(c, y) T R(c, d), new d T∀x∀y(R(x, y) → R(y, x)) T∀y(R(c, y) → R(y, c)) T(R(c, d) → R(d, c)) T∀x∀y∀z(R(x, y) ∧ R(y, z) → R(x, z)) T∀y∀z(R(c, y) ∧ R(y, z) → R(c, z)) T∀z(R(c, d) ∧ R(d, z) → R(c, z)) T R(c, d) ∧ R(d, c) → R(c, c) F R(c, d) ∧ R(d, c) F R(c, d) × F R(d, c) T(R(c, d) → R(d, c)) F R(c, d) × T R(d, c) × T R(c, c) × Figure 1: The tableau proof tableau proof. It is proved. 2

3 The Amazing of Fo Theorem 1(Upward Skolem-Lowenheim theorem). If s has a infinite model. Then for every set a there is a model of s which contains at least as many elements as A Idea. For each a E A let ca be a new constant (i. e. ca C). For distinct a, b E A, we show that the set S=SUn of Lc where c=cala e A is satisfiable Then make - (ca= cb)specific, which means consider n elements a1, a2,..., an of A. The remaining is to apply Compactness theorem and to set up a injective map from a to domain of new model It is left as an exercise In analysis, positive infinity likes a ghost, which is not a concrete number. However, we can persuade students it exists in logic with the following example Example 6. Let C=f, + <,,] and Th() be the set of all sentences of f true in N. There is a nonstandard model of Th(M), i.e., there is M Th(m and a E M larger than every n EM where M is the domain of struCtuTe Proof.(Sketch) Let L*=LUIh, where c is a new constant symbol. We can construct a set of ≥1} Let T=Th(M)US, given any finite subset 2, We can choose N as the model. Then sentence in Th()must be true. The other sentences are in the form of n. For 2 is finite, a number c car be chosen as one more larger than the largest number. Thus, T is finitely satisfiable and there MET. If a E M is interpreted as c, then a is larger than every n EM It is badly amazing that we indeed prove the existence of the number which is larger than any natural number. However, what are the affects of this number to Th(m are referred to the classical monograph book on nonstandard analysis if you are interested with this topics 4 Limitations As shown before, first order logic is very powerful. But it has its own limitation. We introduce here an examples to discover limitations Connectivity is a very simple property in graph theory. However, first order logic can not express this property Example 7. The property of being strongly-connected is not a first order property of directed graphs Proof. Assume that sentence sc represents the property of being strongly-connected. Define sentences sl,Φ nd更

3 The Amazing of FO Theorem 1 (Upward Skolem-L¨owenheim theorem). If S has a infinite model. Then for every set A there is a model of S which contains at least as many elements as A. Idea. For each a ∈ A let ca be a new constant (i.e. ca 6∈ L). For distinct a, b ∈ A, we show that the set S 0 = S ∪ {¬(ca = cb)} of LC where C = {ca|a ∈ A} is satisfiable. Then make ¬(ca = cb) specific, which means consider n elements a1, a2, . . . , an of A. The remaining is to apply Compactness theorem and to set up a injective map from A to domain of new model. It is left as an exercise. In analysis, positive infinity likes a ghost, which is not a concrete number. However, we can persuade students it exists in logic with the following example. Example 6. Let L = {·, +, <, 0, 1} and T h(N ) be the set of all sentences of L true in N . There is a nonstandard model of T h(N ), i.e., there is M |= T h(N ) and a ∈ M larger than every n ∈ N , where M is the domain of structure M. Proof. (Sketch) Let L ∗ = L ∪ {c}, where c is a new constant symbol. We can construct a set of sentence S = {ϕn = 1 + 1 + · · · + 1 | {z } n < c, n ≥ 1}. Let T = T h(N ) ∪ S, given any finite subset Σ, We can choose N as the model. Then sentence in T h(N ) must be true. The other sentences are in the form of ϕn. For Σ is finite, a number c can be chosen as one more larger than the largest number. Thus, T is finitely satisfiable and there is M |= T. If a ∈ M is interpreted as c, then a is larger than every n ∈ N . It is badly amazing that we indeed prove the existence of the number which is larger than any natural number. However, what are the affects of this number to T h(N ) are referred to the classical monograph book on nonstandard analysis if you are interested with this topics. 4 Limitations As shown before, first order logic is very powerful. But it has its own limitation. We introduce here an examples to discover limitations. Connectivity is a very simple property in graph theory. However, first order logic can not express this property. Example 7. The property of being strongly-connected is not a first order property of directed graphs. Proof. Assume that sentence ΦSC represents the property of being strongly-connected. Define sentences ΦSL, ΦIN and Φout as follows. 3

1.重sL=(x)(=E(x,x) 2.重oUr=(vx)(vy)(vz)(E(x,y)∧E(x,2)→y=2) 3.重IN=(vx)(vy)(vz)(E(y,x)∧E(z,x)→y=2) Let=sc∧sL∧ΦoUr∧ΦIN. Thus it describes the class of graphs that are strongly connected, have no self loops and have all vertices of in-degree and out-degree This is clearly the class of cycle graphs (of finite size). We can show that it has any arbitrary finite model. With the theorem in the last lecture, there must be a infinite graph satisfying But it is It must be something wrong with sc. So the property cannot be described by predict logic. D However, connectivity of graph can be expressed by extending first order logic. But it is out of the range of this course and is left for further reading Exercises 1. Given a unary function f on R and let A be the binary distance function on R, that ( ro, r1)=ro -ril. the continuity of it can be stated as follows For all a and for all e>0 there is a8>0 such that for all y, if A(a, y)< 8 then △(f(x),f(y))< Use a sentence to represent it 2. Use a sentence to formalize "there are at least k elements 3.11/P125

1. ΦSL = (∀x)(¬E(x, x)). 2. ΦOUT = (∀x)(∀y)(∀z)(E(x, y) ∧ E(x, z) → y = z). 3. ΦIN = (∀x)(∀y)(∀z)(E(y, x) ∧ E(z, x) → y = z). Let Φ = ΦSC ∧ΦSL ∧ΦOUT ∧ΦIN . Thus it describes the class of graphs that are strongly connected, have no self loops and have all vertices of in-degree and out-degree 1. This is clearly the class of cycle graphs (of finite size). We can show that it has any arbitrary finite model. With the theorem in the last lecture, there must be a infinite graph satisfying Φ. But it is impossible. It must be something wrong with ΦSC. So the property cannot be described by predict logic. However, connectivity of graph can be expressed by extending first order logic. But it is out of the range of this course and is left for further reading. Exercises 1. Given a unary function f on R and let ∆ be the binary distance function on R, that is, ∆(r0, r1) = |r0 − r1|. the continuity of it can be stated as follows: For all x and for all  > 0 there is a δ > 0 such that for all y, if ∆(x, y) < δ then ∆(f(x), f(y)) < . Use a sentence to represent it. 2. Use a sentence to formalize ”there are at least k elements”. 3. 11/P125 4