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.