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.
Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2012 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.