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.
