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/P125Connectivity 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