Discrete Mathematics(ID) Spring 2013 Lecture 16: Application and Limitations 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 following sentences: 「(wx)(-<x) 4m={(m)(wy)c2)(x<yAy<2)→x<2) )(vy)( Example 2(dense order). In order to describe dense linear orders, we could add into linear order the following sentense vy(x<y→3(x<z∧z<y) Example 3(Graphs). Let C=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, ) Example 4(Equivalence relation). The equivalence relation can be formalized with the aid of a single binary relation symbols as folllows: 「(vx)R(x,x) (x)(√y)(R(x,y)→R(y,x) (vx)(vy)(vz)(R(x,y)∧R(y,z))→R(x,z) Example 5. Suppose R is a binary relation. If it is non-trival, which means every element has a neighbor, transitive and symmetric, then it must be reflexive We can represent these properties as
Discrete Mathematics (II) Spring 2013 Lecture 16: 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 every element has a neighbor, 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 20mtr20= (Va) y)(a, y) Then itrans, sym, nontriu ref Proof. We now prove that iT,S, N) R We have the following tableaux as Figure 1. It is a FVaR(c, c) FR(e, c), new c TVr=yR(, v) TR(e, d),new vrvy(R(x,y)→R(y,x) Ty(Rcy)→R(,c (R(cd)→R(d,c) y(R(xy)∧R2)→R(x2 Yy:(Rcy)∧R(,2)→R(c2 v:(R(c山)∧Ra2)→R(c2) TR(cd)∧R(ac)→R(cl PFR(cd∧R(dcl FR( d. c) (Rcd)→Ra R(cd⑦Ra,c Figure 1: The tableau proof tableau proof. It is pro
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 1. 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
Remark 1. This proof is every different from a proof in set theory. The key is to represent the original problem as a set of sentences. Then you just apply tableau proof to seek truth. According to knowledge in completeness theorem, we know that we can construct a counterexample if it is not true 3 The Amazing of Fo A there is a model of S which contains at least as many elements as y model. Then for every set Theorem 1(Upward Skolem-Lowenheim theorem). If S has a infinite 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=SUf(ca= cb) 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 L= + <,0, 1) and Th(m) be the set of all sentences of f true in M.There is a nonstandard model of Th(), i. e, there is MTh(M and a E M larger than every n EN. where M is the domain of structure M Proof( Sketch) Let L*=LUc, where c is a new constant symbol. We can construct a set of sentence S={yn=1+1+……+1<c,n≥1} Let T=Th()US, given any finite subset 2, We can choose N as the model. Then sentence in Th(M must be true. The other sentences are in the form of n. For E is finite, a number c can be chosen as one more larger than the largest number. Thus, T is finitely satisfiable and there is MET. If a E M is interpreted as c, then a is larger than every n EN. 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 th 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
Remark 1. This proof is every different from a proof in set theory. The key is to represent the original problem as a set of sentences. Then you just apply tableau proof to seek truth. According to knowledge in completeness theorem, we know that we can construct a counterexample if it is not true. 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 ̸∈ L). For distinct a, b ∈ A, we show that the set S ′ = 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. 3
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 graph Proof. Assume that sentence sc represents the property of being strongly-connected. Define sentencesΦsL,Φ In andΦ out as follows. 1.更sL=(vx)(-E(x,x) 2.重oUT=(v)(vy)(2)(E(x,y)∧E(x,2)→y=2) 3.重N=(x)(vy)(vz)(E(y,x)∧E(2,x)→y=2) Letφ=ΦSC∧ΦsSL∧重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 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 d. But it is impossible 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 readin 5 Conclusion First order logic is a very powerful tool. It can make us rigid. It is widely used in computer science And it forms a special branch named finite model theory for computer program can only handle finite object Any formal system has its own limitation. Godel incompleteness theorem confirms that there are problems in a formal system which cannot be proved and disprove Exercises Given a unary function f on R and let a be the binary distance function on R, that is A(ro, r1)=Iro-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(, 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
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. 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. 5 Conclusion First order logic is a very powerful tool. It can make us rigid. It is widely used in computer science. And it forms a special branch named finite model theory for computer program can only handle finite objects. Any formal system has its own limitation. G¨odel incompleteness theorem confirms that there are problems in a formal system which cannot be proved and disproved. 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