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) refApplication(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