复旦大学：《离散数学 Discrete Mathematics》英文讲稿_15 Application of Logic Limitation of First Order Logic

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