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-

bols

∃∞

and

∀∞.

The former means “there exist infinitely many;”

∃∞xϕ(x)

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;”

∀∞xϕ(x)

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))).

2.2. Sets

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