Discrete mathematics Yi li Software School Fudan University June9.2013
. . Discrete Mathematics Yi Li Software School Fudan University June 9, 2013 Yi Li (Fudan University) Discrete Mathematics June 9, 2013 1 / 15
Re eview o Soundness and Completeness theorem o Compactness Theorem 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 9, 2013 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 9, 2013 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 9, 2013 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 9, 2013 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 9, 2013 6 / 15
Application( Cont. Example(Groups) Let C=f, el where is a binary relation and e is a constant symbol. The class of group is described as oVxe·x=x.e=x O VxVyVzx·(yz)=(x·y)·z, xyx: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 9, 2013 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) pequ=(x)(Vy)(R(x,y)+R(y,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 9, 2013 8 / 15
Application( Cont. Example Suppose R is a binary relation. If it is non-trival, which means no isolated element, 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 no isolated element, 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 9, 2013 9 / 15
Expressibility Example Let C=, + <,0, 1) and Th()be the full theory of N. there is MH Th() and a E M such that a is larger than every membe Let C*=LUcl, where c is a new constant symbol. We can construct a set of sentence 5={yn=1+1+…+1<c,n≥1} Then apply compactness theorem
Expressibility . Example . . Let L = {·, +, <, 0, 1} and Th(N ) be the full theory of N . There is M |= Th(N ) and a ∈ M such that a is larger than every member. . Proof. . . Let L ∗ = L ∪ {c}, where c is a new constant symbol. We can construct a set of sentence S = {φn = 1 + 1 + · · · + 1 | {z } n < c, n ≥ 1}. Then apply compactness theorem. Yi Li (Fudan University) Discrete Mathematics June 9, 2013 10 / 15