Predicates and quantifiers

In chapter 1 we carefully refused to call "$x > 3$" a proposition: there is no way to say whether it is true or false until $x$ is fixed. Yet mathematics overflows with statements of this kind. How do we give them a truth value, and therefore the right to enter a proof?

The answer comes in two gestures: naming these open statements, the predicates, then closing them with two tiny, formidable words, “for all” and “there exists”. By the end of this chapter you will know how to turn any open statement into a proposition, how to negate it correctly, and you will have understood the trap that everyone falls into: the order in which you stack “for all” and “there exists”.

The open statement

Take "$x > 3$" again. It is not a proposition, but it is not noise either: as soon as you replace $x$ by a number, the sentence becomes true ($x = 5$) or false ($x = 1$). It is a form with a blank to fill in.

A predicate Predicate A statement containing one or more free variables, whose truth value depends on what is substituted for those variables. "x > 3" is a predicate: it is neither true nor false until x is fixed or quantified. Once all its variables are fixed or bound by a quantifier, a predicate becomes a proposition. is exactly that: a statement containing one or more variables, whose truth value depends on what you put in the blanks. We write it like a function: $P(x)$, $Q(x, y)$. Here $P(x)$ means "$x > 3$", and:

• $P(5)$ is the proposition "$5 > 3$", true.
• $P(1)$ is the proposition "$1 > 3$", false.

As long as the variable stays free, $P(x)$ is neither true nor false: it waits. There are two ways to push it into the state of a proposition. The first we just saw: substitute a value. The second, far more powerful, is to quantify the variable, that is, to say in one stroke something about all possible values, or about at least one.

What the variable ranges over: the domain of discourse

Before quantifying, a question we cannot dodge: what does $x$ range over? The integers? The reals? The inhabitants of a city? This reference set is called the domain of discourse Domain of discourse The set of objects that the variables of a quantified predicate range over. The truth of a quantified statement depends entirely on it: "∃x, x² = 2" is false over the integers but true over the reals. Stating the domain is therefore not a detail, it is part of the statement. , and it is part of the statement just as much as the predicate is.

This is not bureaucratic detail. Consider “there exists a number whose square is $2$”:

• over the domain of integers, it is false (no integer squared gives $2$);
• over the domain of reals, it is true ($\sqrt{2}$ exists).

Same predicate, same quantifier, opposite truths: only the domain changed. Remember the rule: a quantified statement with no stated domain is incomplete.

The two quantifiers

To quantify is to bind the variable: it stops being a free blank and becomes the subject of a global claim. There are two ways to do it.

For all: ∀

The universal quantifier Universal quantifier The symbol ∀, read "for all" or "for every". The statement ∀x, P(x) is true when the predicate P holds for every element of the domain of discourse, without exception. A single counter-example is enough to refute it. is written $\forall$ and read “for all” or “for every”. The statement

$$\forall x,\ P(x)$$

reads “for every $x$ in the domain, $P(x)$ is true”. It claims that each element, without exception, satisfies the predicate.

• Over the integers, $\forall n,\ n + 0 = n$ is true.
• Over the integers, $\forall n,\ n > 3$ is false (take $n = 2$).

There exists: ∃

The existential quantifier Existential quantifier The symbol ∃, read "there exists". The statement ∃x, P(x) is true as soon as at least one element of the domain of discourse makes the predicate P true. Such an element is called a witness. Existence does not require uniqueness: one or several witnesses are enough. is written $\exists$ and read “there exists”. The statement

$$\exists x,\ P(x)$$

reads “there exists at least one $x$ in the domain such that $P(x)$ is true”. Such an $x$ is called a witness. Beware the everyday sense: “there exists” does not mean “there exists a unique”. One witness is enough, several are allowed.

• Over the integers, $\exists n,\ n > 3$ is true ($n = 4$ is a witness, so is $n = 100$).
• Over the integers, $\exists n,\ n^2 = 2$ is false: no witness.

Negating a quantifier

How do you refute “for all $x$, $P(x)$”? Not by checking every case, that would be endless. A single failure is enough. And symmetrically, negating “there exists” amounts to saying “none”, hence “all fail”. These two rules follow directly from chapter 1’s De Morgan laws, extended from the finite to the infinite:

¬(∀x, P(x)) ≡ ∃x, ¬P(x) | ¬(∃x, P(x)) ≡ ∀x, ¬P(x)

In plain words: negating “all satisfy $P$” gives “there is one that does not”; negating “there is one that satisfies $P$” gives “all fail to”. The quantifier flips, and the negation slides inward, onto the predicate. This is exactly De Morgan’s move ($\lnot$ turns $\land$ into $\lor$), seen here as an infinite “and” becoming an infinite “or”.

From the first rule comes the most economical tool in mathematics. To demolish a universal claim, you exhibit a counter-example Counter-example An element of the domain that makes a universal statement false. To refute "∀x, P(x)", it suffices to exhibit a single x such that P(x) is false: this is the direct reading of the equivalence ¬(∀x, P(x)) ≡ ∃x, ¬P(x). A counter-example demolishes a conjecture with nothing more to add. : a single element of the domain where the predicate is false. A counter-example does not “argue” with a conjecture, it kills it.

The trap: the order of quantifiers

Here is the point that trips everyone up, and the true reason for this chapter. When you stack two different quantifiers, their order changes the meaning. Compare:

∀x ∃y, R(x, y) | ∃y ∀x, R(x, y)

• $\forall x\, \exists y,\ R(x, y)$: “for each $x$, there exists a $y$ (which may depend on $x$) such that $R$”. Each one has its partner, possibly different.
• $\exists y\, \forall x,\ R(x, y)$: “there exists one $y$ that works for all $x$ at once”. A universal partner, the same for everyone.

The analogy that engraves the difference: “everyone has a mother” ($\forall x\, \exists y$, $y$ is the mother of $x$) is true. “there exists a mother of everyone” ($\exists y\, \forall x$) is false, thankfully. Same words, reversed order, opposite truths.

Manipulate it yourself below. The grid is the relation $R(x, y)$: a checked cell means ”$x$ is linked to $y$”. It starts on the diagonal: each one is linked to itself, and to no one else. Your mission: leave the statement on $\forall x\, \exists y$ and read the verdict, then click “Swap the axes” to move to $\exists y\, \forall x$ without changing anything else. The same table, two verdicts.

To pin down the direction of the arrows, the diagram below sets the two readings side by side on the diagonal. On the left, each $x$ points to its own witness: three arrows, the universal-existential statement holds. On the right, we look for a single $y$ that all reach: no column receives three arrows, the existential-universal statement fails.

In one sentence

A predicate is an open statement; quantifying it with “for all” or “there exists” over a stated domain closes it into a true-or-false proposition, its negation swaps the two quantifiers, and their order is never innocent.

Towards chapter 3

We kept talking about the “domain of discourse”, the set the variables range over, settling for an intuitive idea: a collection of objects. But what is a set, exactly? How do we describe one, how do we test whether an object belongs to it, how do we build new ones from old? The quantifiers of this chapter will become the very language of that construction: "$A \subseteq B$" will read "$\forall x,\ x \in A \Rightarrow x \in B$". That is all of chapter 3, set theory.

Exercises

Take a pen and paper. The solutions are right below, look at them only after trying.

Exercise 1: negate cleanly

The domain is the set of human beings. Consider the statement “everyone loves at least one person”, written $\forall x\, \exists y,\ A(x, y)$ where $A(x, y)$ means ”$x$ loves $y$”. Write its negation by sliding the $\lnot$ all the way to the predicate, then translate it into plain English.

Exercise 2: the order decides

The domain is the set of strictly positive integers $\{1, 2, 3, \dots\}$. Let $R(x, y)$ be "$y > x$". Determine whether $\forall x\, \exists y,\ R(x, y)$ is true, then whether $\exists y\, \forall x,\ R(x, y)$ is true. Justify each answer.

Sources

• Frege, G. (1879). Begriffsschrift. Louis Nebert. The birth certificate of quantifier notation.
• Euler, L. (1732). “Observationes de theoremate quodam Fermatiano aliisque ad numeros primos spectantibus.” Commentarii academiae scientiarum Petropolitanae. The refutation of Fermat’s conjecture on Fermat numbers.

Further reading

• Cori, R. & Lascar, D. (2003). Mathematical Logic, Part 1. Oxford University Press. The rigorous treatment of predicate calculus.
• Velleman, D. J. (2019). How to Prove It. Cambridge University Press. Chapters 2 and 3, excellent on quantifiers and their negation.
• Halmos, P. (1960). Naive Set Theory. Van Nostrand. To ease into chapter 3.