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.