14 2. Background Exercise 2.1.6. Consider N, Z, Q, and R. Over which domains of quantification are each of the following statements true? (i) (∀x)(x 0) (ii) (∃x)(5 x 6) (iii) (∀x)((x2 = 2) (x = 5)) (iv) (∃x)(x2 1 = 0) (v) (∃x)(x2 = 5) (vi) (∃x)(x3 + 8 = 0) (vii) (∃x)(x2 2 = 0) When working with multiple quantifiers the order of quantifica- tion can matter a great deal, as in the following formulas. ϕ = (∀x)(∃y)(x · x = y) ψ = (∃y)(∀x)(x · x = y) ϕ says “every number has a square” and is true in our typical domains. ψ says “there is a number which is all other numbers’ square” and is true only if your domain contains only 0 or only 1. Exercise 2.1.7. Over the real numbers, which of the following state- ments are true? Over the natural numbers? (i) (∀x)(∃y)(x + y = 0) (ii) (∃y)(∀x)(x + y = 0) (iii) (∀x)(∃y)(x y) (iv) (∃y)(∀x)(x y) (v) (∃x)(∀y)(x y2) (vi) (∀y)(∃x)(x y2) (vii) (∀x)(∃y)(x = y x y) (viii) (∃y)(∀x)(x = y x y) The order of operations when combining quantification with con- junction or disjunction can also make the difference between truth and falsehood.
Previous Page Next Page