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 asDiscrete 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 =< 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