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.
