Multi-Page Printing

2.1. First-Order Logic 13 which are true or false inherently via quantifiers. Note that writing ϕ(x) indicates the variable x appears in the formula ϕ, and does not technically forbid ϕ containing other variables. The existential quantification ∃x is read “there exists x.” The formula ∃xϕ(x) is true if for some value n the unquantified formula ϕ(n) is true. Universal quantification, on the other hand, is ∀xϕ(x) (“for all x, ϕ(x) holds”), true when no matter what n we fill in for x, ϕ(n) is true. Quantifiers must have a specified set of values to range over, be- cause the truth value of a formula may be different depending on this domain of quantification. For example, take the formula (∀x)(x = 0 → (∃y)(xy = 1)). This asserts every nonzero x has a multiplicative inverse. If we are letting our quantifiers range over the real numbers (denoted R) or the rational numbers (Q), this statement is true, because the reciprocal of x is available to play the role of y. However, in the integers (Z) or natural numbers (N) this is false, because 1/x is only in the domain when x is ±1. Introducing quantification opens us up to two kinds of logical formulas. If all variables are quantified over (bound variables), then the formula is called a sentence. If there are variables that are not in the scope of any quantifier (free variables), the formula is called a predicate. The truth value of a predicate depends on what values are plugged in for the free variables a sentence has a truth value, period. For example, (∀x)(∃y)(x y) is a sentence, and it is true in all our usual domains of quantification. The formula x y is a predicate, and it will be true or false depending on whether the specific values plugged in for x and y satisfy the inequality. Exercise 2.1.5. Write the following statements as formulas, speci- fying the domain of quantification. (i) 5 is prime. (ii) For any number x, the square of x is nonnegative. (iii) There is a smallest positive integer.