2.2. Sets 15
Exercise 2.1.8. Over the real numbers, which of the following state-
ments are true? Over the natural numbers?
(i) (∀x)(x ≥ 0 ∨ x ≤ 0)
(ii) [(∀x)(x ≥ 0)] ∨ [(∀x)(x ≤ 0)]
(iii) (∃x)(x ≤ 0 & x ≥ 5)
(iv) [(∃x)(x ≤ 0)] & [(∃x)(x ≥ 5)]
How does negation work for quantifiers? If ∃xϕ(x) fails, it means
no matter what value we fill in for x the formula obtained is false;
i.e., ¬(∃xϕ(x)) ↔ ∀x(¬ϕ(x)). Likewise, ¬(∀xϕ(x)) ↔ ∃x(¬ϕ(x)): if
ϕ does not hold for all values of x, there must be an example for
which it fails. If we have multiple quantifiers, the negation walks in
one by one, flipping each quantifier and finally negating the predicate
inside. For example:
¬[(∃x)(∀y)(∀z)(∃w)ϕ(x, y, z, w)] ↔ (∀x)(∃y)(∃z)(∀w)(¬ϕ(x, y, z, w)).
Exercise 2.1.9. Negate the following sentences.
(i) (∀x)(∃y)(∀z)((z y) → (z x))
(ii) (∃x)(∀y)(∃z)(xz = y)
(iii) (∀x)(∀y)(∀z)(y = x ∨ z = x ∨ y = z)
[Bonus: over what domains of quantification would this be true?]
A final notational comment: you will sometimes see the sym-
The former means “there exist infinitely many;”
is shorthand for ∀y∃x(x y & ϕ(x)) (no matter how far up
we go, there are still examples of ϕ above us). The latter means “for
all but finitely many;”
is shorthand for ∃y∀x((x y) →
ϕ(x)) (we can get high enough up to bypass all the failed cases of ϕ).
Somewhat common in predicate logic but less so in computability
theory is ∃!x, which means “there exists a unique x.” The sentence
(∃!x)ϕ(x) expands into (∃x)(∀y)(ϕ(x) & (ϕ(y) → (x = y))).
A set is a collection of objects. If x is a member, or element, of a
set A, we write x ∈ A, and otherwise x / ∈ A. Two sets are equal if