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

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.