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