3.6: Predicate Formulas

Quantifiers

The “for all” notation, \(\forall\), has already made an early appearance in Section 1.1. For example, the predicate

\[\nonumber “x^2 \geq 0”\]

is always true when \(x\) is a real number. That is,

\[\nonumber \forall x \in \mathbb{R}. x^2 \geq 0\]

is a true statement. On the other hand, the predicate

\[\nonumber “5x^2 - 7 = 0”\]

is only sometimes true; specifically, when \(x = \pm \sqrt{7/5}\). There is a “there exists” notation, \(\exists\), to indicate that a predicate is true for at least one, but not necessarily all objects. So

\[\nonumber \exists x \in \mathbb{R}: 5x^2 - 7 = 0\]

is true, while

\[\nonumber \forall x \in \mathbb{R}: 5x^2 - 7 = 0\]

is not true.

There are several ways to express the notions of “always true” and “sometimes true” in English. The table below gives some general formats on the left and specific examples using those formats on the right. You can expect to see such phrases hundreds of times in mathematical writing!

Always True

\[\nonumber \begin{array}{ll} \text{For all } x \in D, P(x) \text{ is true.} & \text{For all } x \in \mathbb{R}, x^2 \geq 0. \\ P(x) \text{ is true for every } x \text{ in the set, } D. & x^2 \geq 0 \text{ for every } x \in \mathbb{R}. \end{array}\]

Sometimes True

\[\nonumber \begin{array}{ll} \text{There is an } x \in D \text{ such that } P(x) \text{ is true.} & \text{There is an } x \in \mathbb{R} \text{ such that } 5x^2 - 7 = 0. \\ P(x) \text{ is true for some } x \text{ in the set, } D. & 5x^2 - 7 = 0 \text{ for some } x \in \mathbb{R}. \\ P(x) \text{ is true for at least one } x \in D. & 5x^2 - 7 = 0 \text{ for at least one } x \in \mathbb{R}.\end{array}\]

All these sentences “quantify” how often the predicate is true. Specifically, an assertion that a predicate is always true is called a universal quantification, and an assertion that a predicate is sometimes true is an existential quantification. Sometimes the English sentences are unclear with respect to quantification:

\[\label{3.6.1} \text{If you can solve any problem we come up with, then you get an } A \text{ for the course.}\]

The phrase “you can solve any problem we can come up with” could reasonably be interpreted as either a universal or existential quantification:

\[\label{3.6.2} \text{you can solve } \textit{every} \text{ problem we come up with,}\]

or maybe

\[\label{3.6.3} \text{you can solve } \textit{at least one} \text{ problem we come up with.}\]

To be precise, let Probs be the set of problems we come up with, Solves\((x)\) be the predicate “You can solve problem \(x\),” and \(G\) be the proposition, “You get an \(A\) for the course.” Then the two different interpretations of (3.16) can be written as follows:

\((\forall x \in \text{ Probs.Solves}(x)) \text{ IMPLIES } G,\) for (\ref{3.6.1}),

\((\exists x \in \text{ Probs.Solves}(x)) \text{ IMPLIES } G,\) for (\ref{3.6.2}),

Mixing Quantifiers

Many mathematical statements involve several quantifiers. For example, we already described

Goldbach’s Conjecture 1.1.8: Every even integer greater than 2 is the sum of two primes.

Let’s write this out in more detail to be precise about the quantification:

For every even integer \(n\) greater than 2, there exist primes \(p\) and \(q\) such that \(n = p + q\).

Let Evens be the set of even integers greater than 2, and let Primes be the set of primes. Then we can write Goldbach’s Conjecture in logic notation as follows:

\[\nonumber \underbrace{\forall n \in \text{Evens}}_{\text{for every even integer }n > 2} \quad \underbrace{\exists p \in \text{Primes } \exists q \in \text{Primes.}}_{\text{there exists primes } p \text{ and } q \text{ such that }} \quad n = p + q.\]

Order of Quantifiers

Swapping the order of different kinds of quantifiers (existential or universal) usually changes the meaning of a proposition. For example, let’s return to one of our initial, confusing statements:

“Every American has a dream.”

This sentence is ambiguous because the order of quantifiers is unclear. Let \(A\) be the set of Americans, let \(D\) be the set of dreams, and define the predicate \(H(a, d)\) to be “American \(a\) has dream \(d\).” Now the sentence could mean there is a single dream that every American shares—such as the dream of owning their own home:

\[\nonumber \exists d \in D \text{ } \forall a \in A. H(a, d)\]

Or it could mean that every American has a personal dream:

\[\nonumber \exists a \in A \text{ } \forall d \in D. H(a, d)\]

For example, some Americans may dream of a peaceful retirement, while others dream of continuing practicing their profession as long as they live, and still others may dream of being so rich they needn’t think about work at all.

Swapping quantifiers in Goldbach’s Conjecture creates a patently false statement that every even number \(\geq 2\) is the sum of the same two primes:

\[\nonumber \underbrace{\exists p \in \text{Primes } \exists q \in \text{Primes.}}_{\text{there exists primes } p \text{ and } q \text{ such that }} \quad \underbrace{\forall n \in \text{Evens}}_{\text{for every even integer }n > 2} n = p + q.\]

Variables Over One Domain

When all the variables in a formula are understood to take values from the same nonempty set, \(D\), it’s conventional to omit mention of \(D\). For example, instead of \(\forall x \in D \exists y \in D. Q(x, y)\) we'd write \(\forall x \exists y. Q(x, y).\) The unnamed nonempty set that \(x\) and \(y\) range over is called the domain of discourse, or just plain domain, of the formula.

It’s easy to arrange for all the variables to range over one domain. For example, Goldbach’s Conjecture could be expressed with all variables ranging over the domain \(\mathbb{N}\) as

\[\nonumber \forall n. n \in \text{ Evens IMPLIES } (\exists p \text{ }\exists q. p \in \text{Primes AND } q \in \text{Primes AND } n = p + q).\]

Negating Quantifiers

There is a simple relationship between the two kinds of quantifiers. The following two sentences mean the same thing:

Not everyone likes ice cream.

There is someone who does not like ice cream.

The equivalence of these sentences is a instance of a general equivalence that holds between predicate formulas:

\[\label{3.6.4} \text{NOT } (\forall x. P(x)) \text{ is equivalent to } \exists x. \text{ NOT}(P(x)).\]

Similarly, these sentences mean the same thing:

There is no one who likes being mocked.

Everyone dislikes being mocked.

The corresponding predicate formula equivalence is

\[\label{3.6.5} \text{NOT } (\exists x. P(x)) \text{ is equivalent to } \forall x. \text{ NOT}(P(x)).\]

The general principle is that moving a \(\text{NOT}\) across a quantifier changes the kind of quantifier. Note that (\ref{3.6.5}) follows from negating both sides of (\ref{3.6.4}).

Validity for Predicate Formulas

The idea of validity extends to predicate formulas, but to be valid, a formula now must evaluate to true no matter what the domain of discourse may be, no matter what values its variables may take over the domain, and no matter what interpretations its predicate variables may be given. For example, the equivalence (\ref{3.6.4}) that gives the rule for negating a universal quantifier means that the following formula is valid:

\[\label{3.6.6} \text{NOT } (\forall x. P(x)) \text{ IFF } \exists x. \text{ NOT}(P(x)).\]

Another useful example of a valid assertion is

\[\label{3.6.7} \exists x \forall y. P(x,y) \text{ IMPLIES } \forall y \text{ } \exists x. P(x, y).\]

Here’s an explanation why this is valid: Let D be the domain for the variables and \(P_0\) be some binary predicate² on \(D\). We need to show that if

\[\label{3.6.8} \exists x \in D. \forall y \in D. P_0(x, y)\]

holds under this interpretation, then so does

\[\label{3.6.9} \forall y \in D \text{ } \exists x \in D. P_0(x, y).\]

So suppose (\ref{3.6.8}) is true. Then by definition of \(\exists\), this means that some element \(d_0 \in D\) has the property that

\[\nonumber \forall y \in D. P_0(d_0, y).\]

By definition of 8, this means that

\[\nonumber P_0(d_0, d)\]

is true for all \(d \in D\). So given any \(d \in D\), there is an element in \(D\), namely, \(d_0\), such that \(P_0(d_0, d)\) is true. But that’s exactly what (\ref{3.6.9}) means, so we’ve proved that (\ref{3.6.9}) holds under this interpretation, as required.

We hope this is helpful as an explanation, but we don’t really want to call it a “proof.” The problem is that with something as basic as (\ref{3.6.7}), it’s hard to see what more elementary axioms are ok to use in proving it. What the explanation above did was translate the logical formula (\ref{3.6.7}) into English and then appeal to the meaning, in English, of “for all” and “there exists” as justification.

In contrast to (\ref{3.6.7}), the formula

\[\label{3.6.10} \forall y \text{ } \exists x. P(x, y) \text{ IMPLIES } \forall x \text{ } \exists y. P(x, y)\]

is not valid. We can prove this just by describing an interpretation where the hypothesis, \(\forall y \exists x. P(x, y)\), is true but the conclusion, \(\forall x \exists y. P(x, y)\), is not true. For example, let the domain be the integers and \(P(x, y)\) mean \(x > y\). Then the hypothesis would be true because, given a value, \(n\), for \(y\) we could choose the value of \(x\) to be \(n + 1\), for example. But under this interpretation the conclusion asserts that there is an integer that is bigger than all integers, which is certainly false. An interpretation like this that falsifies an assertion is called a counter model to that assertion.

 

²That is, a predicate that depends on two variables.