Discrete mathematics Yi li Software School Fudan University June20.2012
Discrete Mathematics Yi Li Software School Fudan University June 20, 2012 Yi Li (Fudan University) Discrete Mathematics June 20, 2012 1 / 15
Review o Soundness and completeness Theorem ● Compactness Theore o Size of model o Compactness theorem
Review Soundness and Completeness Theorem Compactness Theorem Size of model Compactness theorem Yi Li (Fudan University) Discrete Mathematics June 20, 2012 2 / 15
Or utline o Application of logic o Limitation of first Order logic
Outline Application of Logic Limitation of First Order Logic Yi Li (Fudan University) Discrete Mathematics June 20, 2012 3 / 15
Application Example(linear order) A structure A=< A, < is called an ordering if it is a model of the following sentences Solution )(-x<x) d。d=(x)(y)(z)(x<y∧y<z)→x<z (Vx)(y)(x<yvx=yvy<x)
Application Example (linear order) A structure A = is called an ordering if it is a model of the following sentences: Solution. Φord = (∀x)(¬x < x), (∀x)(∀y)(∀z)((x < y ∧ y < z) → x < z), (∀x)(∀y)(x < y ∨ x = y ∨ y < x). Yi Li (Fudan University) Discrete Mathematics June 20, 2012 4 / 15
Application( Cont. Example(dense order) In order to describe dense linear orders we could add into linear order the following sentence vxvy(x<y→3z(x<z∧z<y)
Application(Cont.) Example (dense order) In order to describe dense linear orders, we could add into linear order the following sentence ∀x∀y(x < y → ∃z(x < z ∧ z < y)) Yi Li (Fudan University) Discrete Mathematics June 20, 2012 5 / 15
Application( Cont. Example(Graphs) Let C=R where R is a binary relation. We can characterize undirected irreflexive graphs with O VXR(x, x). oxvy(R(x,y)→R(y,x)
Application(Cont.) Example (Graphs) Let L = {R} where R is a binary relation. We can characterize undirected irreflexive graphs with 1 ∀x¬R(x, x), 2 ∀x∀y(R(x, y) → R(y, x)). Yi Li (Fudan University) Discrete Mathematics June 20, 2012 6 / 15
Application( Cont. Example(Groups) Let C=[, e where is a binary relation and e is a constant symbol. The class of group is described as o Vxe x=xe=x O VXVyVzX·(yz)=(xy)·z, wxyx·y=y.x=e
Application(Cont.) Example (Groups) Let L = {·, e} where · is a binary relation and e is a constant symbol. The class of group is described as 1 ∀xe · x = x · e = x, 2 ∀x∀y∀zx · (y · z) = (x · y) · z, 3 ∀x∃yx · y = y · x = e. Yi Li (Fudan University) Discrete Mathematics June 20, 2012 7 / 15
Application( Cont. Example(Equivalence relation) The equivalence relation can be formalized with a single binary relation symbols as follows: Solution (XR(x, x), (x)(y(R(x,y)>R(, x) (x)(y)(Vz)(R(x,y)∧R(y,z))→R(x,z)
Application(Cont.) Example (Equivalence relation) The equivalence relation can be formalized with a single binary relation symbols as follows: Solution. Φ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)). Yi Li (Fudan University) Discrete Mathematics June 20, 2012 8 / 15
Application( Cont. Example Suppose R is a binary relation. If it is non-trival, which means nonempty, transitive and symmetric, then it must be reflexive Solution We can represent these properties as O nontriv=(Vxr(x,y) O sym=(Vx)(Vy(R(,y)+R(, x)) o ref=(Vx)R(x, x) o trans=(wx)(y)(z)(R(x,y)∧R(y,z)→R(x,z) Then itrans, sym, nontriv) ref
Application(Cont.) Example Suppose R is a binary relation. If it is non-trival, which means nonempty, transitive and symmetric, then it must be reflexive. Solution. We can represent these properties as: 1 nontriv = (∀x)(∃y)R(x, y). 2 sym = (∀x)(∀y)(R(x, y) → R(y, x)). 3 ref = (∀x)R(x, x). 4 trans = (∀x)(∀y)(∀z)((R(x, y) ∧ R(y, z)) → R(x, z)). Then {trans,sym, nontriv} |= ref . Yi Li (Fudan University) Discrete Mathematics June 20, 2012 9 / 15
Compactness Theorem satisfiable in arbitrarily large finite models is satisfiable in some<'s Let l be a first-order language. Any set S of sentences of l that infinite model Sketch Idea Suppose s is satisfiable in arbitrary large finite models. Let r be a 2-ary relation symbol that is not part of the language L, and enlarge L to L' by adding R We can modify the interpretation of R without affecting the truth values of members of s, sincer does not occur in members of S. so we can write a sentence An that asserts there are at least n thing We can imply Theorem by applying Compactness Theorem
Compactness Theorem Let L be a first-order language. Any set S of sentences of L that is satisfiable in arbitrarily large finite models is satisfiable in some infinite model. Sketch Idea: Suppose S is satisfiable in arbitrary large finite models. Let R be a 2-ary relation symbol that is not part of the language L, and enlarge L to L 0 by adding R. We can modify the interpretation of R without affecting the truth values of members of S, since R does not occur in members of S. So we can write a sentence An that asserts there are at least n thing. We can imply Theorem by applying Compactness Theorem. Yi Li (Fudan University) Discrete Mathematics June 20, 2012 10 / 15