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