Nested quantifiers and rules of inference

Last week you saw statements with a single quantifier. Real mathematical sentences usually contain two or three quantifiers: “every number has an inverse”, “there is no number greater than everything”. The first half of this page explains how to read these statements, how to find their truth value and how to negate them. The second half covers rules of inference: going from premises to a conclusion step by step, writing a rule name next to each step. Both come up on the midterm; the truth value of a quantified statement is almost certain, and “is the argument valid” is also common.

Golden rules:

1. Quantifiers are read and chosen from left to right. The one that comes first is chosen first; the next one can be chosen looking at it.
2. In $\forall x\,\exists y$, $y$ may depend on $x$. In $\exists y\,\forall x$ it may not.
3. When negating, every quantifier flips and the order does not change.
4. Valid argument = if the premises are true, the conclusion is certainly true. To show invalidity, a single row with premises T and conclusion F is enough.

Nested quantifiers

Let $P(x, y)$ be a predicate of two variables. Think of $\forall x\,\exists y\, P(x,y)$ as two nested loops:

∀x ∃y P(x,y):   for each x:              (outer loop, all must pass)
                    search some y        (inner loop, finding one is enough)
                    with P(x,y) true
∃y ∀x P(x,y):   find ONE y such that
                    for each x: P(x,y)   (the same y must work with all x)

From a programmer’s point of view: $\forall$ means all items in a for loop return true, and $\exists$ means break as soon as one true is found in the loop. Changing the order means swapping the loops, and it changes the result.

Everyday example. Domain: the players and coaches on a team. $C(y, x)$: ”$y$ is the coach of $x$”.

• $\forall x\,\exists y\, C(y, x)$: “Every player has a coach.” The striker’s coach can be one person and the defender’s another.
• $\exists y\,\forall x\, C(y, x)$: “There is a single person who is everyone’s coach.” A much stronger claim.

If the second is true, the first is also true (you choose that single person for everyone). The converse is generally not true.

The four basic statements with two variables

Domain: the integers, $P(x, y)$: "$x < y$".

On the exam you write the truth value of a statement like this:

• If you say True: for $\exists$ give the concrete value (“take $y = x + 1$”), for $\forall$ argue with an arbitrary element (“for any integer $x$ …”).
• If you say False: for $\forall$ give a concrete counterexample, for $\exists$ show that no element satisfies it.

Worked examples

The domain is the integers.

$\forall x\,\exists y\,(x = 2y)$. False. Counterexample $x = 1$: if $1 = 2y$ then $y = \tfrac12 \notin \mathbb{Z}$. (If the domain were the reals it would be true with $y = x/2$.)

$\exists x\,\forall y\,(x + y = y)$. True. Take $x = 0$: $0 + y = y$ for every integer $y$.

$\forall x\,\exists y\,(xy = 1)$. False. Counterexample $x = 2$: $2y = 1$ has no integer solution. $x = 0$ also breaks it.

PITFALL · Thinking “the order doesn’t matter”. $\forall x\,\exists y$ and $\exists y\,\forall x$ can swap places only when the quantifiers are of the same kind ($\forall\forall$ or $\exists\exists$). With mixed quantifiers the order changes the meaning.

Translation

The domain is the students in a class, $F(x, y)$: ”$x$ and $y$ are friends”.

Pattern: $\forall$ for “every” and “all”, $\exists$ for “some”, “a”, “at least one”. The connective inside again follows last week’s rule: if there is a condition under $\forall$ use $\to$, under $\exists$ use $\land$.

Negating nested quantifiers

The rule is the same as last week’s, just applied several times: as you push the $\lnot$ from left to right, you flip each quantifier.

¬ ∀x ∃y (P(x,y) ∧ Q(x))
≡ ∃x ¬∃y (P(x,y) ∧ Q(x))
≡ ∃x ∀y ¬(P(x,y) ∧ Q(x))
≡ ∃x ∀y (¬P(x,y) ∨ ¬Q(x))        De Morgan

With restricted quantifiers the restriction stays as it is: $\lnot\,\forall x > 0\; P(x) \equiv \exists x > 0\; \lnot P(x)$. If “every positive number satisfies it” is false, there is a positive number that does not satisfy it.

Rules of inference

An argument consists of premises and a conclusion. An argument is valid if the conclusion is certainly true whenever all the premises are true. That is, $(p_1 \land p_2 \land \dots \land p_n) \to q$ is a tautology. Validity is about the form, not the content.

Instead of building a long truth table, you chain known valid patterns:

Rules with quantifiers:

Two classic fallacies

• Affirming the conclusion: $p \to q$, $q$ $\therefore p$. Invalid. “Whoever studies hard passes. Ali passed. So Ali studied hard.” Maybe he was lucky.
• Denying the hypothesis: $p \to q$, $\lnot p$ $\therefore \lnot q$. Invalid. “Whoever studies hard passes. Ali did not study. So Ali failed.” Maybe he passed anyway.

In both, the row that breaks it is $p = F$, $q = T$: the premises are true and the conclusion is false.

Worked example: solving an argument with rules

Premises: “If I wake up early and I am not tired, I go to the gym.” “I did not go to the gym.” “I woke up early.” Conclusion: “I was tired.”

First assign letters: $w$: wake up early, $h$: tired, $g$: go to the gym. The premises are $(w \land \lnot h) \to g$, $\lnot g$, $w$. The conclusion is $h$.

1. (w ∧ ¬h) → g      premise
2. ¬g                premise
3. ¬(w ∧ ¬h)         modus tollens, 1, 2
4. ¬w ∨ h            De Morgan + double negation, 3
5. w                 premise
6. h                 disjunctive syllogism, 4, 5   (¬w is false, so h remains)

The argument is valid. Step 4 is not a rule of inference but an equivalence law; it is enough to write its name too.

Worked example: resolution

Premises $p \lor q$, $\lnot p \lor r$, $\lnot q \lor r$. Conclusion $r$.

1. p ∨ q        premise
2. ¬p ∨ r       premise
3. q ∨ r        resolution, 1, 2
4. ¬q ∨ r       premise
5. r ∨ r        resolution, 3, 4
6. r            idempotent law, 5

In everyday terms: “I will go either by bus ($p$) or by train ($q$). If I go by bus I will be late. If I go by train I will also be late. So I will be late.” This pattern is also called proof by cases; you will see it again on the proof page.

TIP · Write the letters first. The line “Let $p$: …, $q$: …” is part of your marks on the exam. Then go on with numbered lines; to the right of each line write “premise” or the rule name and the line numbers you used.

Common mistakes