← MA0 1 · Introduction to University Mathematics (Proofs)

Lesson 2

Predicates, Quantifiers, and Proofs

Taught 12 Aug 2026

Predicates

There is a problem: So far, what we’ve built (propositional logic) has no way to express the classic (correct) argument “All men are mortal. Socrates is a man. Therefore Socrates is mortal,” because propositional logic treats each proposition as an indivisible whole. It therefore has no way to look inside a statement and relate the object (Socrates), the property (being a man), and the consequence (being mortal); without that internal structure, we cannot formally justify the conclusion.

What is missing is the ability to distinguish the object of our speech from the description we make about it, so we introduce predicate logic, which allows us to reason about objects and their properties.

Variables and Predicates

Recall that a term is a symbol that denotes an object: constants such as the natural number $5$ or $\pi$ are terms denoting specific objects, while an unquantified variable such as $x$ is a term whose value has not yet been specified. We can then form expressions describing the object denoted by a variable, such as $\operatorname{man}(x)$ to say ” $x$ is a man,” or $x>3$ to say ” $x$ is greater than $3$ .” We call these expressions predicates (also known as variable propositions), since they make a claim that depends on one or more variables.

Definition 2.1 (Predicate).

Let $x_1, \ldots, x_n$ be variable symbols. We say $\varphi(x_1, \ldots, x_n)$ is an $n$ -ary predicate if its truth value is determined once values are assigned to each of the variables $x_1, x_2, \ldots, x_n$ (or equivalently, replacing each variable by a term denoting a specific object produces a proposition).

A $1$ -ary (monadic) predicate describes a property, e.g., $\text{IsPrime}(x)$ .
A $2$ -ary (dyadic) predicate describes a relation between two terms, e.g., $\text{IsGreaterThan}(x, y)$ .
An $n$ -ary predicate describes a relation among $n$ terms.

Note that we would usually write such a declaration as: let $P(x)$ be the statement ” $x^2-1=0$ .”

Remark.

A term by itself is not a complete sentence, so it has no truth value; likewise, as hinted earlier the resulting expressions above ( $x>3$ ) are still not propositions because their truth value depends on the actual value of $x$ .

Applying a predicate to the appropriate number of terms gives an atomic formula, the simplest kind of formula in first-order logic; for example, if $P$ is the predicate “is prime,” then $P(x)$ and $P(7)$ are atomic formulas. If all the terms in an atomic formula denote specific objects, then the formula has a definite truth value and is a proposition.

Example 2.2.

Let $R(x, y, z)$ denote $x + y = z$ , where the variables range over the integers. Then $R(2, -1, 5)$ is $\bot$ since $2 + (-1) \neq 5$ ; $R(3, 4, 7)$ is $\top$ since $3 + 4 = 7$ ; and $R(x, 3, z)$ is still a predicate, since $x + 3 = z$ can be $\top$ or $\bot$ depending on the values of $x$ and $z$ .

Remark.

It is common to use capital letters such as $P, Q, R$ to denote predicates.

A predicate’s variables take values in a domain $U$ , called the universe of discourse (in the previous example, $U$ is the integers). Once values from $U$ are substituted, the predicate becomes a proposition with truth value $\top$ or $\bot$ ; hence we can now apply the logical connectives introduced earlier.

Example 2.3.

Let $P(x)$ denote $x > 0$ . Then the following are true: $P(3) \lor P(-1),$ $P(3) \to \neg P(-1);$ and the following are false: $P(3) \land P(-1),$ $P(3) \to P(-1)$ .

More generally, we can build new predicates out of old ones using connectives. Expressions constructed from predicates and logical connectives whose truth value still depends on one or more variables are called propositional functions.

Example 2.4.

Using $P(x)$ as above, the following are propositional functions:

R(x, y) \defeq P(x) \to P(y), \qquad S(y) \defeq P(3) \land P(y)

$R(x, y)$ is a predicate in two variables; $S(y)$ is a predicate in one variable (since $P(3)$ is already a proposition).

Problem 2.1.

Consider the expressions $\text{man}(x)$ , $x > 3$ , and $2 + 3 = 5$ . Which of these are propositions and which are predicates? For each predicate, give one substitution that makes it $\top$ and one that makes it $\bot$ .

Remark (History and Significance of Predicate Logic).

Aristotle developed a limited form of predicate logic through his theory of syllogisms. The modern version was independently developed by Frege and Peirce between the 19th and 20th centuries, roughly 2000 years later, mirroring the timeline of propositional logic itself. Predicate logic (also called first-order logic) is now the standard language for mathematical statements and is equally fundamental in computer science, appearing in database queries, logic programming (Prolog), automated theorem proving, software verification, and symbolic AI. Some mathematicians, notably Hilbert, hoped it would be a complete system for all of mathematics, but Gödel’s incompleteness theorem showed otherwise: no fixed collection of axioms can prove all true mathematical statements.

Introduction to Sets

We take a quick detour to study sets. Sets are probably the most important structure in mathematics right now; a precise answer as to why they are so important would fill an entire course, but for our purposes it might suffice as a rather crude approximation to say that sets are the building blocks of all mathematics.

Being so important, we introduce them now and will study them in greater detail later. For the moment, the following informal definition will suffice.

Definition 2.5 (Set (to be revised)).

A set is nothing more than a collection of objects. The objects in the collection are called its elements or members. We usually denote sets by uppercase letters $A,B,S,\dots$ , and elements by lowercase letters $a,b,x,\dots$ . If $S$ is a set, then $x \in S$ means ” $x$ is an element of $S$ ,” and $x \notin S$ or equivalently $\neg(x \in S)$ , means ” $x$ is not an element of $S$ .”

Example 2.6.

Let $S = \{2,3,5\}$ . Then $3 \in S$ , but $4 \notin S$ .

Remark.

Membership is a relation between an element and a set. That said, a set can itself be an element of another set. For example, $\{2,3\} \in \{\{2,3\},5\},$ because the collection on the right has two elements: the set $\{2,3\}$ and the number $5$ ; The problem arises when this is confused with the case where only the original objects are elements: $\{2,3\} \notin \{2,3,5\}.$ So $a \in A$ asks whether $a$ is literally a member of the collection $A$ , not merely whether its contents appear among the elements of $A$ .

Problem 2.2.

Let $S = \{2,3,5\}.$ Which of the following are true?

(a) $3 \in S$

(b) $4 \notin S$

(c) $5 \in S$

(d) $1 \in S$

There is one refinement we will need: Not every collection is useful in mathematics, for example, “a collection of all beautiful paintings” doesn’t make sense because whether a painting belongs to it depends on the judge; with a different panel of judges we might get a different result, “beauty is in the eye of the beholder” afterall.

Either way, to combat this we normally restrict ourselves to what is called a well-defined set. Informally, a well-defined set is a set such that, for every object, there is a specific objective rule that allows us to determine whether the object belongs to the set or not; one or the other must happen, but not both. Well aside from being a mouthfull, this definition runs into the same exact problems we introduced earlier; our current model cannot describe this so we finally introduce one which can.

Quantifiers

The natural next step is to make claims about all values in a domain, or to assert that at least one satisfying value exists. These are the universal and existential quantifiers, the final logical apparatus for formal mathematical reasoning.

The Universal Quantifier

Definition 2.7 (Universal Quantifier).

Let $\varphi(x)$ be a predicate with variable $x$ ranging over a universe of discourse $U$ . The universal quantification of $x$ in $\varphi$ , written $\forall x\,(\varphi(x))$ , is the proposition asserting that $\varphi(a)$ is $\top$ for every element $a \in U$ . It is read “for all $x$ , $\varphi(x)$ .”

Determining the truth of $\forall x\,(\varphi(x))$ amounts to exhaustive verification: examine every object in the universe, and if even one makes $\varphi$ false, the entire statement is false. If every object passes, the statement is true; a value $a$ for which $\varphi(a) = \bot$ is called a counterexample.

If the universe is the collection $U = \{a_1, a_2, \ldots, a_n\}$ , the universal quantifier reduces to a conjunction:

\forall x\,(\varphi(x)) \equiv \varphi(a_1) \land \varphi(a_2) \land \cdots \land \varphi(a_n)

Remark (Indexed Conjunction and Disjunction).

When a conjunction or disjunction extends over a collection of terms, we write

\bigwedge_{i=1}^{n} \varphi(a_i) \;\defeq\; \varphi(a_1) \land \varphi(a_2) \land \cdots \land \varphi(a_n), \qquad \bigvee_{i=1}^{n} \varphi(a_i) \;\defeq\; \varphi(a_1) \lor \varphi(a_2) \lor \cdots \lor \varphi(a_n)

More generally, for any index set $S$ the notations $\bigwedge_{a \in S} \varphi(a)$ and $\bigvee_{a \in S} \varphi(a)$ denote the conjunction and disjunction, respectively, of $\varphi(a)$ over every $a$ in $S$ . In this notation, the finite-universe equivalences above become $\forall x\,(\varphi(x)) \equiv \bigwedge_{a \in U} \varphi(a)$ and, as we shall see shortly, $\exists x\,(\varphi(x)) \equiv \bigvee_{a \in U} \varphi(a)$ .

Specifying the Quantification Set

Earlier our description of a quantification states that it “ranges over a universe of discourse,” take for example the sentence

\forall x\, (x^2 \geqslant 0)

which may look true, but as it stands it is meaningless. What is $x$ ? “For every $x$ ” from where? If $x$ ranges over colours, or over sentences, then $x^2 \geqslant 0$ is not false, it is not even grammatical. We need to know where the object $x$ comes from before we can ask whether the claim about it is true.

If we amend the sentence so that $x$ ranges over the real numbers, we get a well-formed statement, and a true one. If instead we let $x$ range over the complex numbers, we get an equally well-formed statement that is now false: the imaginary unit $i$ is a complex number with $i^2 = -1$ , and $-1 \geqslant 0$ fails. (We will make little real use of the complex numbers in these notes, but they are a convenient source of counterexamples.)

Example 2.8.

Let $P(x)$ denote ” $x > 0$ .”

If the universe is the integers, then $\forall x\,(P(x))$ is $\bot$ : the value $x = 0$ is a counterexample, since $P(0)$ is false. If $U$ is the positive integers (the natural numbers greater than 0), then $\forall x\,(P(x))$ is $\top$ . The truth value of a universally quantified statement depends on the choice of universe.

The Existential Quantifier

Definition 2.9 (Existential Quantifier).

Let $\varphi(x)$ be a predicate with variable $x$ ranging over a universe $U$ . The existential quantification of $x$ in $\varphi$ , written $\exists x\,(\varphi(x))$ , is the proposition asserting that there is at least one element $a \in U$ for which $\varphi(a)$ is $\top$ . It is read “there exists an $x$ such that $\varphi(x)$ .”

Where the universal quantifier demands exhaustive verification, the existential quantifier demands a search: examine objects in the universe until one satisfies $\varphi$ . If such an object is found, it is called a witness and the statement is true. If the entire universe is exhausted without finding a witness, the statement is false.

If the universe is the collection $U = \{a_1, a_2, \ldots, a_n\}$ , the existential quantifier reduces to a disjunction:

\exists x\,(\varphi(x)) \equiv \varphi(a_1) \lor \varphi(a_2) \lor \cdots \lor \varphi(a_n)

If $\forall x\,(\varphi(x))$ is true and $U$ is non-empty, then $\exists x\,(\varphi(x))$ must also be true: if every element satisfies $\varphi$ , at least one does.

Example 2.10.

Let $P(x)$ denote ” $x > 0$ .”

$\exists x\,(P(x))$ is $\top$ when the universe is the integers (witness: $x = 1$ ), $\top$ when $U$ is the positive integers, and $\bot$ when $U$ is the negative integers.

The following table summarises the two quantifiers:

Statement	True when	False when
$\forall x\,(P(x))$	$P(x)$ is $\top$ for every $x \in U$	There exists a counterexample: some $a$ with $P(a) = \bot$
$\exists x\,(P(x))$	There exists a witness: some $a$ with $P(a) = \top$	$P(x)$ is $\bot$ for every $x \in U$

Remark (Quantifiers and Finite Domains).

If the domain is finite, quantifiers are technically unnecessary: $\forall x\,(P(x))$ is a conjunction and $\exists x\,(P(x))$ is a disjunction, both expressible in propositional logic. The power of quantifiers lies in their ability to make claims about infinite domains, where no finite conjunction or disjunction suffices.

Scope and Variable Binding

Definition 2.11 (Scope, Bound Variables, and Free Variables).

The scope of a quantifier is the portion of the formula to which it applies, typically delimited by parentheses. A variable that falls within the scope of a quantifier is bound to that quantifier. A variable not bound by any quantifier is free. A formula with free variables is a predicate, and becomes a proposition only when all free variables are either substituted by terms or bound by quantifiers.

This is why we bracket the body of a quantifier. Quantifiers bind more tightly than all propositional connectives, so an unbracketed formula is read as narrowly as possible:

\forall x\, P(x) \lor Q(x) \quad \text{means} \quad \bigl(\forall x\,(P(x))\bigr) \lor Q(x)

This expression has a free variable $x$ in $Q(x)$ and is therefore a predicate. The two $x$ ‘s are in fact independent: the expression could equivalently be written $\bigl(\forall y\,(P(y))\bigr) \lor Q(x)$ . By contrast, $\forall x\,(P(x) \lor Q(x))$ has both occurrences of $x$ inside the brackets, so both are bound, and the result is a proposition.

Earlier it was shown that a quantifier always comes with a set attached, either named outright or fixed in advance as the universe of discourse. Writing that set into the quantifier itself is common enough to earn its own notation.

Definition 2.12 (Bounded Quantifiers).

Let $A$ be a set and let $P(x)$ be a predicate. The bounded quantifiers are defined by

\forall x \in A\,(P(x)) \;\defeq\; \forall x\,(x \in A \to P(x)), \qquad \exists x \in A\,(P(x)) \;\defeq\; \exists x\,(x \in A \land P(x))

read “for every $x$ in $A$ , $P(x)$ ” and “there is an $x$ in $A$ with $P(x)$ .” When several variables share a set we abbreviate further, writing $\forall x, y \in A\,(P(x,y))$ for $\forall x \in A\, \forall y \in A\,(P(x,y))$ , and likewise $\exists x, y \in A\,(P(x,y))$ for $\exists x \in A\, \exists y \in A\,(P(x,y))$ .

The restriction enters the universal quantifier through an implication and the existential one through a conjunction, and the pairing cannot be swapped. The statement $\exists x\,(x \in A \to P(x))$ is made true by any object outside $A$ whatsoever, since a false antecedent makes the implication true, so it says nothing about the elements of $A$ at all.

The Unique Existential Quantifier

It is often useful to assert that exactly one object satisfies a predicate.

Definition 2.13 (Unique Existential Quantifier).

The unique existential quantification $\exists!\, x\,(\varphi(x))$ asserts that exactly one element of $U$ satisfies $\varphi$ . It is defined in terms of the other quantifiers:

\exists!\, x\,(\varphi(x)) \;\equiv\; \exists x\,\bigl(\varphi(x) \land \forall y\,(\varphi(y) \to y = x)\bigr)

This reads: “there exists an $x$ such that $\varphi(x)$ , and any $y$ satisfying $\varphi(y)$ must equal $x$ .” It takes a bounded form like the other two: for a set $A$ ,

\exists!\, x \in A\,(P(x)) \;\defeq\; \exists!\, x\,(x \in A \land P(x))

Example 2.14.

Let $U$ be the integers and let $P(x)$ denote ” $x + 1 = 0$ .” Then $\exists!\, x \in U\,(P(x))$ is $\top$ : the unique witness is $x = -1$ . If instead $P(x)$ denotes ” $x > 0$ ,” then $\exists!\, x \in U\,(P(x))$ is $\bot$ , since every positive integer satisfies $P$ and there are infinitely many of them.

Formalising Arguments

We can now symbolise the prime-number argument that propositional logic could not handle. Let $U$ be the integers, let $P(x)$ denote ” $x$ is a prime number greater than $2$ ,” and let $O(x)$ denote ” $x$ is odd.”

“Every prime number greater than $2$ is odd” becomes $\forall x \in U\,(P(x) \to O(x))$ .
“The number $7$ is a prime number greater than $2$ ” becomes $P(7)$ .
By substituting $x = 7$ into (1) we obtain $P(7) \to O(7)$ . Since $P(7)$ is true by (2) and the conditional $P(7) \to O(7)$ is true, bivalence forces $O(7)$ to be true: ” $7$ is odd.”

More broadly, the four classical categorical propositions of Aristotelian logic can be expressed in first-order form. Given predicates $S(x)$ and $R(x)$ over a universe $U$ :

Type	Statement	First-order form
A	All $S$ are $R$	$\forall x \in U\,(S(x) \to R(x))$
E	No $S$ is $R$	$\forall x \in U\,(S(x) \to \neg R(x))$
I	Some $S$ is $R$	$\exists x \in U\,(S(x) \land R(x))$
O	Some $S$ is not $R$	$\exists x \in U\,(S(x) \land \neg R(x))$

Remark (The Connective Trap).

A common error is to write $\forall x \in U\,(S(x) \land R(x))$ , which makes the much stronger claim that everything in the universe is both $S$ and $R$ . Equally, $\exists x \in U\,(S(x) \to R(x))$ is almost always vacuously true: any element that is not $S$ makes the implication true and serves as a witness.

Example 2.15 (Translating Natural Language).

Let $U$ be all people, let $S(x)$ denote ” $x$ is a student in this class,” and let $P(x)$ denote ” $x$ has written a programme in Python.”

“Every student in this class has written a programme in Python” is formalised as $\forall x \in U\,(S(x) \to P(x))$ .

“Some student in this class has written a programme in Python” is formalised as $\exists x \in U\,(S(x) \land P(x))$ .

Quantifier Negation

The universal and existential quantifiers are duals, connected by negation in a manner analogous to De Morgan’s laws for conjunction and disjunction.

Theorem 2.16 (Quantifier Negation).

For any predicate $\varphi(x)$ with universe $U$ :

(1) $\neg\bigl(\forall x\,(\varphi(x))\bigr) \equiv \exists x\,(\neg\varphi(x))$

(2) $\neg\bigl(\exists x\,(\varphi(x))\bigr) \equiv \forall x\,(\neg\varphi(x))$

Proof.

The two quantifiers expand into an indexed conjunction and an indexed disjunction over $U$ :

\forall x\,(\varphi(x)) \equiv \bigwedge_{a \in U} \varphi(a), \qquad \exists x\,(\varphi(x)) \equiv \bigvee_{a \in U} \varphi(a)

(1)

\begin{aligned} \neg\bigl(\forall x\,(\varphi(x))\bigr) &\equiv \neg\Bigl(\bigwedge_{a \in U} \varphi(a)\Bigr) && \text{by the expansion of } \forall \\ &\equiv \bigvee_{a \in U} \neg\varphi(a) && \text{by generalised De Morgan} \\ &\equiv \exists x\,(\neg\varphi(x)) && \text{by the expansion of } \exists \end{aligned}

(2)

\begin{aligned} \neg\bigl(\exists x\,(\varphi(x))\bigr) &\equiv \neg\Bigl(\bigvee_{a \in U} \varphi(a)\Bigr) && \text{by the expansion of } \exists \\ &\equiv \bigwedge_{a \in U} \neg\varphi(a) && \text{by generalised De Morgan} \\ &\equiv \forall x\,(\neg\varphi(x)) && \text{by the expansion of } \forall \end{aligned}

Remark (De Morgan over a Universe).

The generalised De Morgan’s laws were stated for $n$ propositions, and the proof above applies them to a conjunction indexed by $U$ , which need not be finite (we explore this in a second). When $U = \{a_1, \ldots, a_n\}$ , the step is the corollary verbatim:

\neg\bigl(\varphi(a_1) \land \cdots \land \varphi(a_n)\bigr) \equiv \neg\varphi(a_1) \lor \cdots \lor \neg\varphi(a_n)

Which has an immediate consequences: $\forall x\,(\varphi(x)) \equiv \neg\bigl(\exists x\,(\neg\varphi(x))\bigr)$ and $\exists x\,(\varphi(x)) \equiv \neg\bigl(\forall x\,(\neg\varphi(x))\bigr)$ .

Example 2.17 (Negating in English).

Let $U$ be the real numbers.

“There is a real number $x$ with $x^2 = -1$ ,” in symbols $\exists x \in U\,(x^2 = -1)$ , is $\bot$ . Its negation is the universal statement “for every real number $x$ , $x^2 \neq -1$ ,” which is $\top$ .
“Every real number is positive or negative,” in symbols $\forall x \in U\,(x > 0 \lor x < 0)$ , is $\bot$ : the counterexample is $x = 0$ . Its negation is $\exists x \in U\,\neg(x > 0 \lor x < 0)$ , and De Morgan’s laws turn the negated disjunction into a conjunction, giving $\exists x \in U\,(x \leqslant 0 \land x \geqslant 0)$ : “there is a real number that is neither positive nor negative.” It is $\top$ , with $x = 0$ doing the existing.

Negation and Bounded Quantifiers

The bounded notation of Definition 2.12 is coherent with negation. Applying the theorem to a set $S$ :

\neg\bigl(\forall x \in S\,(P(x))\bigr) \equiv \exists x \in S\,(\neg P(x)) \quad \text{and} \quad \neg\bigl(\exists x \in S\,(P(x))\bigr) \equiv \forall x \in S\,(\neg P(x))

The restricted domain is preserved under negation: only the predicate is negated, not the domain condition. Unfolding the first one confirms this. Writing the bounded quantifier out in full, negating, and using the negation of a conditional:

\neg\bigl(\forall x\,(x \in S \to P(x))\bigr) \equiv \exists x\,\neg(x \in S \to P(x)) \equiv \exists x\,(x \in S \land \neg P(x))

which is the bounded existential $\exists x \in S\,(\neg P(x))$ .

Problem 2.3.

Show the negation of the existential claim to be true.

Distribution of Quantifiers over Connectives

The universal quantifier distributes over conjunction, and the existential quantifier distributes over disjunction:

\forall x\,(P(x) \land Q(x)) \equiv \forall x\,(P(x)) \land \forall x\,(Q(x))

\exists x\,(P(x) \lor Q(x)) \equiv \exists x\,(P(x)) \lor \exists x\,(Q(x))

However, the reverse pairings do not hold in general:

\exists x\,(P(x) \land Q(x)) \;\not\equiv\; \exists x\,(P(x)) \land \exists x\,(Q(x))

\forall x\,(P(x) \lor Q(x)) \;\not\equiv\; \forall x\,(P(x)) \lor \forall x\,(Q(x))

For both non-equivalences, a single counterexample suffices: Let $U = \{a, b\}$ , with $P(x)$ true exactly of $a$ and $Q(x)$ true exactly of $b$ . Then $\exists x,P(x) \land \exists x,Q(x)$ is $\top$ (witnesses $a$ and $b$ ), but $\exists x,(P(x) \land Q(x))$ is $\bot$ , since $P(a) \land Q(a)$ fails on the second conjunct and $P(b) \land Q(b)$ on the first. Likewise $\forall x,(P(x) \lor Q(x))$ is $\top$ (it holds at $a$ via $P$ and at $b$ via $Q$ ), while $\forall x,P(x) \lor \forall x,Q(x)$ is $\bot$ , since $P(b)$ and $Q(a)$ both fail.

Problem 2.4.

Come up with your own example as to why this fails, what situation does it not fail?

Validity and Satisfiability in Predicate Logic

Just as in propositional logic, a quantified statement with all variables bound can be classified by its truth behaviour across all possible interpretations. A statement is valid if it is true for every domain and every choice of predicates (the analogue of a tautology), satisfiable if there exists at least one domain and choice of predicates making it true, and unsatisfiable if no such choice exists.

Example 2.18.

The statement $\forall x\,(\neg S(x)) \leftrightarrow \neg\exists x\,(S(x))$ is valid: it is an instance of Theorem 2.16 and holds for any predicate $S$ and any domain.

The statement $\forall x\,(F(x) \leftrightarrow T(x))$ is satisfiable: taking $F \equiv T$ makes it true, while taking the domain to be the integers with $F(x) \equiv (x > 0)$ and $T(x) \equiv (x < 0)$ makes it false.

The statement $\forall x\,(F(x) \land \neg F(x))$ is unsatisfiable: it asserts that every element simultaneously satisfies and fails to satisfy $F$ , contradicting the principle of bivalence.

Problem 2.5.

Let $P$ be a predicate over an arbitrary universe $U$ . Determine whether each of the following statements is valid, satisfiable, or unsatisfiable, and justify your answer.

(a) $\exists!\, x \in U\,(P(x)) \to \exists x \in U\,(P(x))$

(b) $\forall x \in U\,(P(x)) \to \exists!\, x \in U\,(P(x))$

(c) $\exists!\, x \in U\,(\neg P(x)) \to \neg\forall x \in U\,(P(x))$

Problem 2.6.

Let $U$ be all English texts, and let $P(x)$ , $Q(x)$ and $R(x)$ denote ” $x$ is a clear explanation”, ” $x$ is satisfactory”, and ” $x$ is an excuse” respectively. Formalise the following in predicate logic:

(a) All clear explanations are satisfactory.

(b) Some excuses are unsatisfactory.

(c) Some excuses are not clear explanations.

Problem 2.7.

Let $Z$ be the integers and let $R$ be the real numbers. Using Theorem 2.16 , negate each of the following statements and simplify. State whether the original or its negation is true.

(a) $\forall x \in Z\,(x^2 \geqslant 0)$

(b) $\exists x \in R\,(x^2 < 0)$

(c) $\forall x \in R\,\exists y \in R\,(x + y = 0)$

Nested Quantifiers

The statements encountered so far have involved a single quantifier binding a single variable. Many mathematical claims, however, involve multiple variables and require several quantifiers applied in sequence. A nested quantifier is a quantifier that falls within the scope of another quantifier.

Example 2.19 (Additive Inverse).

The statement “every real number has an additive inverse” involves two variables: the number itself and its inverse. Letting $U$ be the real numbers, the formalisation is:

\forall x \in U\, \exists y \in U\,(x + y = 0)

The outer quantifier $\forall x \in U$ asserts that the claim holds for every real $x$ . The inner quantifier $\exists y \in U$ asserts that, for each such $x$ , a suitable $y$ exists. The two quantifiers are nested: $\exists y \in U$ lies within the scope of $\forall x \in U$ .

A nested quantified statement can be decomposed by treating each inner quantification as a propositional function. For instance, $\forall x \in U\, \exists y \in U\,(x + y = 0)$ can be read as $\forall x \in U\,(Q(x))$ , where $Q(x) \defeq \exists y \in U\,(P(x, y))$ and $P(x, y) \defeq (x + y = 0)$ . Note that $Q(x)$ is itself a predicate: the existential quantifier binds $y$ , but $x$ remains free until the outer $\forall x \in U$ binds it.

Order of Quantifiers

The order in which quantifiers appear is critical. Consider the same predicate $P(x, y) \defeq (x + y = 0)$ , with $U$ still the real numbers.

$\forall x \in U\, \exists y \in U\,(P(x, y))$ asserts: “for every real $x$ , there exists a real $y$ such that $x + y = 0$ .” This is $\top$ : for any given $x$ , the witness $y = -x$ works. Crucially, the witness may differ for each $x$ .

$\exists y \in U\, \forall x \in U\,(P(x, y))$ asserts: “there exists a single real $y$ such that $x + y = 0$ for every real $x$ .” This is $\bot$ : no single number is the additive inverse of every real number.

The difference shows up in how one would search for the answer. In the first statement, we walk through the values of $x$ one at a time and look for a fresh $y$ at each step. In the second, we pick a candidate $y$ first and then test it against every $x$ . The quantifier order dictates which variable is chosen first, and therefore which one the other is allowed to depend on.

Example 2.20 (Order Changes the Meaning).

Let $U$ be the real numbers and let $p(m, n)$ denote ” $m > n$ .” Then $\forall n \in U\, \exists m \in U\,(p(m, n))$ says “for every number there is a larger one,” which is $\top$ ; the witness $m = n + 1$ works for each $n$ . Flipping the two quantifiers, $\exists m \in U\, \forall n \in U\,(p(m, n))$ says “there is a number larger than every number,” which is $\bot$ ; among other embarrassments, such an $m$ would have to satisfy $m > m$ (this will be important in a second).

Example 2.21 (Captains).

Let $X$ be the professional footballers, let $Y$ be the clubs, and let $p(x, y)$ denote ” $x$ is the captain of $y$ .” Four formally similar statements have four very different meanings:

$\forall x \in X\, \exists y \in Y\,(p(x, y))$ : every footballer is some club’s captain. $\bot$ .
$\exists y \in Y\, \forall x \in X\,(p(x, y))$ : there is one club whose captain is every footballer at once. $\bot$ , and its dressing room does not bear thinking about.
$\forall y \in Y\, \exists x \in X\,(p(x, y))$ : every club has a captain. $\top$ .
$\exists x \in X\, \forall y \in Y\,(p(x, y))$ : there is one footballer who captains every club. $\bot$ .

Only the quantifier order and the choice of which set each variable is drawn from separate these.

Problem 2.8.

Negate statement (3) of the example above, “every club has a captain,” pushing the negation all the way inside. Then say the result in football English.

However, quantifiers of the same type may be freely reordered:

\forall x \in U\, \forall y \in U\,(P(x, y)) \equiv \forall y \in U\, \forall x \in U\,(P(x, y))

\exists x \in U\, \exists y \in U\,(P(x, y)) \equiv \exists y \in U\, \exists x \in U\,(P(x, y))

Both nested universal quantifiers demand that $P$ hold for every pair, and both nested existential quantifiers demand that at least one pair satisfies $P$ . In neither case does the order in which pairs are examined affect the outcome.

Quantification Fixes a Variable

Let $X$ be the even integers greater than or equal to $4$ , let $P$ be the prime numbers, and for $n \in X$ and $a, b \in P$ let $Q(n, a, b)$ denote ” $a + b = n$ .” Consider

\forall n \in X\, \exists a, b \in P\,(Q(n, a, b))

The initial quantification $\forall n \in X$ serves to fix a value of $n$ , which is then used for the rest of the statement. The assertion that follows, that there are primes $a$ and $b$ with $a + b = n$ , is made about that fixed but arbitrary value. Read as a whole, the statement says that no matter which $n$ is chosen from $X$ , we can find $a$ and $b$ satisfying $Q$ . The order of quantification is what tells us those values may depend on the chosen $n$ .

Take a particular value. We know $8 \in X$ , since $8$ is even and $8 \geqslant 4$ . Can we find $a, b \in P$ with $a + b = 8$ ? We can take $a = 3$ and $b = 5$ . Now take $n = 14$ ; our choices have to be different from before, and $a = 3$ , $b = 11$ will do (as will $a = b = 7$ ). This is what we mean when we say that $a$ and $b$ depend on $n$ .

Problem 2.9.

What is the difference between the statement above and the following one?

\exists n \in X\, \exists a, b \in P\,(Q(n, a, b))

Is it $\top$ or $\bot$ ? Why?

Remark.

The universal statement $\forall n \in X\, \exists a, b \in P\,(Q(n, a, b))$ is the Goldbach Conjecture, met as a proposition of unknown truth value in the previous chapter. Checking $n = 8$ and $n = 14$ settles two instances; it does not settle the statement, because a universal quantifier over an infinite set is not exhausted by any number of instances; but a single $n$ for which no such $a$ and $b$ exist would settle it the other way.

Example 2.22 (Translating from Mathematics).

The statement “the sum of two positive integers is always positive” contains implicit quantifiers and a hidden domain. Making these explicit step by step:

Rewrite with explicit quantifiers: “for every two integers, if both are positive, then their sum is positive.”
Introduce variables: “for all integers $x$ and $y$ , if $x > 0$ and $y > 0$ , then $x + y > 0$ .”
Formalise, taking $U$ to be the integers:

\forall x, y \in U\,(x > 0 \land y > 0 \to x + y > 0)

Example 2.23 (Carrying Restrictions Along).

The Archimedean principle says that if $b$ and $s$ are positive numbers, there is a natural number $n$ with $ns > b$ . This holds however large $b$ is and however small $s$ is.

Let $U$ be the real numbers, let $N$ be the natural numbers, and let $p(b, s, n)$ denote ” $ns > b$ .” If we agree in advance that $b$ and $s$ range over the positive reals and $n$ over the natural numbers, the principle encodes compactly. If instead all three variables range over $U$ , we have to carry the restrictions ourselves:

\forall b, s \in U\,\Bigl((b > 0 \land s > 0) \to \exists n\,\bigl(n \in N \land p(b, s, n)\bigr)\Bigr)

read “for every $b$ and $s$ , if both are positive, then there is a natural number $n$ satisfying $ns > b$ .” Writing $L$ for the positive real numbers, the bounded quantifiers of Definition 2.12 package the same statement as

\forall b, s \in L\, \exists n \in N\,(p(b, s, n))

The two say the same thing, and the second is the reason the abbreviation is worth having.

Example 2.24 (Translating Natural Language).

Let $U$ be all people and let $L(x, y)$ denote ” $x$ loves $y$ .”

\begin{array}{ll} \text{Everybody loves somebody.} & \forall x \in U\, \exists y \in U\,(L(x, y)) \\[4pt] \text{There is someone who is loved by everyone.} & \exists x \in U\, \forall y \in U\,(L(y, x)) \\[4pt] \text{There is someone who loves someone.} & \exists x, y \in U\,(L(x, y)) \\[4pt] \text{Everyone loves themselves.} & \forall x \in U\,(L(x, x)) \end{array}

Observe how the English phrasing obscures the quantifier order; “Everybody loves somebody” places the universal quantifier first: each person has their own someone. “There is someone who is loved by everyone” places the existential first: a single person is loved by all. Despite their superficial similarity, the two statements are logically independent.

Problem 2.10.

Let $U$ be all students in a class and let $F(x, y)$ denote ” $x$ and $y$ are friends.” Formalise the following in predicate logic, stating the set each variable is drawn from:

(a) Everyone has a friend.

(b) There is someone who is friends with everyone.

(c) No one is friends with everyone.

(d) There exists a pair of students who are not friends with each other.

Example 2.25 (Truth Values of Nested Statements).

Let $U$ be the real numbers. Determine the truth value of each statement:

(a) $\forall x \in U\, \exists y \in U\,(x^2 = y)$ is $\top$ : for any $x$ , choose $y = x^2$ .

(b) $\forall x \in U\, \exists y \in U\,(x = y^2)$ is $\bot$ : taking $x = -1$ , there is no real $y$ with $y^2 = -1$ .

(c) $\exists x \in U\, \forall y \in U\,(xy = 0)$ is $\top$ : choose $x = 0$ .

(d) $\exists x, y \in U\,(x + y \neq y + x)$ is $\bot$ : addition of real numbers is commutative, so $x + y = y + x$ for all $x, y \in U$ . This is the negation of $\forall x, y \in U\,(x + y = y + x)$ , which is $\top$ .

Problem 2.11.

Let $U$ be the integers. Determine the truth value of each statement, and justify your answer.

(a) $\forall x \in U\, \exists y \in U\,(x \cdot y = 1)$

(b) $\exists x \in U\, \forall y \in U\,(x + y = y)$

(c) $\forall x, y \in U\, \exists z \in U\,(x + z = y)$

Negating Nested Quantifiers

Theorem 2.16 extends to nested quantifiers by repeated application. Each quantifier flips ( $\forall \leftrightarrow \exists$ ) and the negation pushes inward:

\neg\bigl(\forall x\, \exists y\,(P(x, y))\bigr) \equiv \exists x\, \neg\bigl(\exists y\,(P(x, y))\bigr) \equiv \exists x\, \forall y\,(\neg P(x, y))

At each step, one quantifier is negated. The process terminates when the negation reaches the predicate.

Example 2.26.

Let $U$ be the real numbers and negate the statement $\forall x \in U\, \exists y \in U\,(x + y = 0)$ , “every real number has an additive inverse.”

Applying the negation rules from outside in:

\neg\bigl(\forall x \in U\, \exists y \in U\,(x + y = 0)\bigr) \equiv \exists x \in U\, \forall y \in U\,(x + y \neq 0)

In English: “there is a real number with no additive inverse.” This is $\bot$ , confirming that the original statement is $\top$ .

Problem 2.12.

Let $U$ be the real numbers. Negate each of the following statements and simplify. State whether the original or its negation is true.

(a) $\forall x, y \in U\,(x + y = y + x)$

(b) $\exists x \in U\, \forall y \in U\,(xy = 0)$

(c) $\forall x \in U\, \exists y, z \in U\,(y^2 + z^2 = x)$

Remark (Prenex Normal Form).

A formula is in Prenex Normal Form (PNF) if all quantifiers appear at the front, followed by a quantifier-free predicate:

Q_1 x_1\, Q_2 x_2\, \cdots\, Q_k x_k\,\bigl(\psi(x_1, x_2, \ldots, x_k)\bigr)

where each $Q_i$ is either $\forall$ or $\exists$ , each variable ranges over the universe fixed in advance, and $\psi$ contains no quantifiers. For example, the statement $\exists x\,(P(x)) \to \exists x\,(Q(x))$ is not in PNF because quantifiers appear on both sides of $\to$ . Rewriting using the defining equivalence of the conditional and renaming variables for clarity:

\neg\bigl(\exists x\,(P(x))\bigr) \lor \exists y\,(Q(y)) \equiv \forall x\,(\neg P(x)) \lor \exists y\,(Q(y)) \equiv \forall x\, \exists y\,(\neg P(x) \lor Q(y))

The last expression is in PNF. Every statement in predicate logic can be converted to PNF using quantifier negation, variable renaming, and the distribution rules established earlier.

Problem 2.13.

Let $P$ and $Q$ be predicates over a universe $U$ . Convert the following to Prenex Normal Form:

(a) $\forall x\,(P(x)) \to \exists x\,(Q(x))$

(b) $\neg\bigl(\forall x\, \exists y\,(P(x, y))\bigr) \lor \forall z\,(Q(z))$

Proofs

Valid Arguments and Inference Rules

We can use all of this to do what a mathematician (or an AI) was meant to do in the first place: write proofs. In the first chapter of the notes we built a proof system for propositional equivalences, but equivalence proofs are symmetric (carrying identical truth values under every assignment), but much of mathematics proceeds asymmetrically (we know certain facts and wish to derive new ones, in one direction only). If $p \to q$ is known and $p$ is true, we may conclude $q$ , but not the reverse. The tools for this one-way reasoning are called inference rules, and a proof is a structured chain of such inferences leading from premises to a conclusion.

Arguments and Validity

Definition 2.27 (Argument).

An argument in propositional logic is a finite sequence of propositions $p_1, p_2, \ldots, p_n, q$ . The propositions $p_1, \ldots, p_n$ are the premises and $q$ is the conclusion. The argument is valid if the truth of all premises guarantees the truth of the conclusion: $(p_1 \land p_2 \land \cdots \land p_n) \to q$ is a tautology. An argument that is not valid is invalid.

We write a valid argument with the premises above a horizontal line and the conclusion below:

\frac{p_1 \quad p_2 \quad \cdots \quad p_n}{q}

An inference rule is an argument form that remains valid regardless of which particular propositions are substituted for its variables: just as the axioms of earlier notes gave us equivalences that hold universally, inference rules give us one-directional deductions that hold universally.

Remark (The Turnstile).

The notation $p_1, p_2, \ldots, p_n \vdash q$ (read ” $p_1, \ldots, p_n$ entail $q$ ”) means that $q$ can be derived from the premises $p_1, \ldots, p_n$ using axioms, inference rules, and previously established theorems. When no premises are needed, we write $\vdash q$ , meaning $q$ is derivable from the axioms alone.

We start off with the most famous.

Modus Ponens

The cornerstone of deductive reasoning is Modus Ponens (from the Latin modus ponendo ponens, “the method of affirming by affirming”):

\frac{p \to q \quad p}{q}

If we know $p \to q$ and $p$ , we may conclude $q$ . Its validity rests on the tautology

((p \to q) \land p) \to q

To see why this is a tautology, suppose both $p \to q$ and $p$ are true: by the truth table of the conditional, the only circumstance under which $p \to q$ is true and $p$ is true is when $q$ is also true. Hence $q$ must hold.

Example 2.28.

Earlier established the universal statement “every prime greater than $2$ is odd.” Let $p$ denote “7 is prime and greater than 2” and $q$ denote “7 is odd.” The universal claim gives $p \to q$ , and we can verify $p$ directly (7 is prime, and $7 > 2$ ); modus Ponens yields $q$ : the integer 7 is odd.

Problem 2.14.

Let $p$ denote “it is snowing” and $q$ denote “the lecture is cancelled.” Suppose we know $p \to q$ and $p$ . State the conclusion and identify the inference rule. Now suppose instead we know $p \to q$ and $q$ . Can we conclude $p$ ? Justify your answer using the truth table of the conditional.

Modus Tollens

Theorem 2.29 (Modus Tollens).

For any propositions $p$ and $q$ ,

\frac{p \to q \quad \neg q}{\neg p}

Proof.

Assume $p \to q$ and $\neg q$ . By the Contrapositive equivalence, $p \to q \equiv \neg q \to \neg p$ . Since $\neg q$ is true, Modus Ponens applied to $\neg q \to \neg p$ and $\neg q$ yields $\neg p$ .

The Latin name modus tollendo tollens (“the method of denying by denying”) captures the reasoning: if the consequence of an implication fails, its premise must also fail.

Example 2.30.

If $n$ is even, then $n^2$ is even. We observe that $49$ is not even and by Modus Tollens, 7 is not even.

Hypothetical Syllogism

Theorem 2.31 (Hypothetical Syllogism).

For any propositions $p$ , $q$ , $r$ ,

\frac{p \to q \quad q \to r}{p \to r}

Proof.

Assume $p \to q$ and $q \to r$ . We wish to show $p \to r$ . Assume $p$ . From $p$ and $p \to q$ , Modus Ponens gives $q$ . From $q$ and $q \to r$ , a second application of Modus Ponens gives $r$ . Since assuming $p$ led to $r$ , we conclude $p \to r$ .

This inference is also called the chain rule or the transitivity of implication. Every multi-step mathematical deduction is, at its core, a sequence of hypothetical syllogisms. For instance, suppose we know “if $n$ is divisible by $4$ , then $n$ is even” and “if $n$ is even, then $n^2$ is even.” Hypothetical Syllogism yields: “if $n$ is divisible by $4$ , then $n^2$ is even.”

Implication Elimination

Theorem 2.32 (Implication Elimination).

For any propositions $p$ and $q$ , $(p \to q) \vdash (p \vdash q)$ .

Proof.

Assume $p \to q$ . We must show $p \vdash q$ . Assume $p$ . From $p \to q$ and $p$ , Modus Ponens yields $q$ . Thus $p \vdash q$ .

This gives one direction of the link between a conditional and a derivation: if $p \to q$ is known, then from the assumption $p$ one may derive $q$ . The reverse direction will appear later in Direct Proof, where we show that if assuming $p$ leads to $q$ , then the conditional $p \to q$ is established. Together, the two directions show how the turnstile and the conditional correspond: $p \vdash q$ if and only if $\vdash p \to q$ .

Further Propositional Inference Rules

Several additional inference rules arise from tautologies:

Conjunction. From two established truths, their conjunction follows.

\frac{p \quad q}{p \land q}

The tautological justification is immediate, but Conjunction can also be derived from Modus Ponens alone via reductio.

Proof.

Assume $p$ and $q$ . Suppose for contradiction that $\neg(p \land q)$ . By De Morgan’s Law (Theorem 6, 1), $\neg(p \land q) \equiv \neg p \lor \neg q$ . By the Conditional axiom, $\neg p \lor \neg q \equiv p \to \neg q$ . Since $p$ holds, Modus Ponens yields $\neg q$ . But $q$ is assumed, a contradiction. Therefore $p \land q$ .

Simplification. From a conjunction, either conjunct may be extracted.

\frac{p \land q}{p}

Addition. A known truth may be weakened to a disjunction.

\frac{p}{p \lor q}

Disjunctive Syllogism. If one disjunct is eliminated, the other must hold.

\frac{p \lor q \quad \neg p}{q}

Resolution. Two clauses sharing a complementary literal may be combined, eliminating the shared variable.

\frac{\neg p \lor r \quad p \lor q}{q \lor r}

Constructive Dilemma. Two conditionals with a disjunction of their antecedents yield the disjunction of their consequents.

\frac{(\alpha \to \gamma) \quad (\beta \to \delta) \quad (\alpha \lor \beta)}{\gamma \lor \delta}

Problem 2.15.

Prove that all of these are tautologies.

Notice the relationships among these rules. Disjunctive Syllogism is a special case of Resolution (set $r = \bot$ and apply the Identity axiom). Addition is dual to Conjunction, and Simplification is a special case of Modus Ponens (since $(p \land q) \to p$ is a tautology).

Remark (Resolution Subsumes Other Rules).

Resolution is remarkably powerful: It can recover Hypothetical Syllogism: rewrite $p \to q$ as $\neg p \lor q$ and $q \to r$ as $\neg q \lor r$ (by the Conditional axiom), then a single resolution step on $q$ yields $\neg p \lor r$ , which is $p \to r$ . It can also recover Modus Ponens: express $p$ as $p \lor \bot$ and $p \to q$ as $\neg p \lor q$ , and resolution gives $q \lor \bot \equiv q$ by the Identity axiom. This universality makes Resolution the basis of automated theorem proving in computer science.

The following table collects the propositional inference rules for reference.

\small \begin{array}{lll} \textbf{Name} & \textbf{Rule} & \textbf{Tautology} \\ \hline \text{Modus Ponens} & p,\; p \to q \;\vdash\; q & ((p \to q) \land p) \to q \\ \text{Modus Tollens} & \neg q,\; p \to q \;\vdash\; \neg p & ((p \to q) \land \neg q) \to \neg p \\ \text{Hyp.\ Syllogism} & p \to q,\; q \to r \;\vdash\; p \to r & ((p \to q) \land (q \to r)) \to (p \to r) \\ \text{Conjunction} & p,\; q \;\vdash\; p \land q & (p \land q) \to (p \land q) \\ \text{Simplification} & p \land q \;\vdash\; p & (p \land q) \to p \\ \text{Addition} & p \;\vdash\; p \lor q & p \to (p \lor q) \\ \text{Disj.\ Syllogism} & p \lor q,\; \neg p \;\vdash\; q & ((p \lor q) \land \neg p) \to q \\ \text{Resolution} & \neg p \lor r,\; p \lor q \;\vdash\; q \lor r & ((\neg p \lor r) \land (p \lor q)) \to (q \lor r) \\ \text{Constr.\ Dilemma} & (\alpha \to \gamma),\; (\beta \to \delta),\; \alpha \lor \beta \;\vdash\; \gamma \lor \delta & ((\alpha \to \gamma) \land (\beta \to \delta) \land (\alpha \lor \beta)) \to (\gamma \lor \delta) \\ \text{Disj.\ Elimination} & (p \to r),\; (q \to r),\; p \lor q \;\vdash\; r & ((p \to r) \land (q \to r) \land (p \lor q)) \to r \\ \text{Ex Falso} & p,\; \neg p \;\vdash\; q & (p \land \neg p) \to q \end{array}

Problem 2.16.

Identify the inference rule applied in each step of the following argument. Premises: (i) $p \to q$ , (ii) $\neg q \lor r$ , (iii) $\neg r$ .

From (ii) and (iii), conclude $\neg q$ .
From (i) and step 1, conclude $\neg p$ .

Building Complex Arguments

The power of inference rules lies in chaining them. A valid argument is a sequence of steps in which each step is either a premise or follows from earlier steps by a single inference rule.

Example 2.33.

We show the following argument is valid. Premises: (1) $p \land (p \to q)$ , (2) $q \to r$ . Conclusion: $r$ .

\begin{array}{rll} 1. & p \land (p \to q) & \text{Premise} \\ 2. & q \to r & \text{Premise} \\ 3. & p & \text{Simplification from 1} \\ 4. & p \to q & \text{Simplification from 1} \\ 5. & q & \text{Modus Ponens from 3, 4} \\ 6. & r & \text{Modus Ponens from 5, 2} \end{array}

Problem 2.17.

Show that the following argument is valid by listing each step and the inference rule used. Premises: (1) $p \to q$ , (2) $q \to (r \land s)$ , (3) $\neg r \lor u$ , (4) $p$ . Conclusion: $u$ .

Inference Rules for Quantified Statements

The rules above govern propositional logic. When predicates and quantifiers enter the picture, additional rules are needed to bridge the gap between universal or existential claims and their specific instances.

Universal Instantiation (UI). If a predicate holds for every element of the universe, it holds for any particular element $c$ :

\frac{\forall x\, P(x)}{P(c)} \quad \text{for any } c \text{ in the universe}

Universal Generalisation (UG). If $P(c)$ can be established for an arbitrary element $c$ (one about which no special assumptions are made), then $\forall x\, P(x)$ follows:

\frac{P(c) \text{ for arbitrary } c}{\forall x\, P(x)}

The word “arbitrary” is critical. If the proof of $P(c)$ exploits any property peculiar to $c$ , the generalisation is invalid.

Existential Instantiation (EI). If at least one element satisfies $P$ , we may introduce a name $c$ for such an element:

\frac{\exists x\, P(x)}{P(c) \text{ for some } c}

The name $c$ must be fresh: not previously used in the argument.

Existential Generalisation (EG). If a particular element $c$ satisfies $P$ , then at least one element does:

\frac{P(c)}{\exists x\, P(x)}

Universal Modus Ponens (UMP). Combining Universal Instantiation with Modus Ponens yields perhaps the most frequently used quantifier rule in practice:

\frac{\forall x\,(P(x) \to Q(x)) \quad P(c)}{Q(c)}

Example 2.34.

Write $R$ for the real numbers, and suppose we know $\forall x\,(x > 0 \to \sqrt{x} \in R)$ , the universe being $R$ , and that $9 > 0$ . Universal Modus Ponens yields $\sqrt{9} \in R$ .

Problem 2.18.

Identify the quantifier inference rule used in each step. The universe is the positive integers.

“Every multiple of $6$ is a multiple of $3$ .” (Premise)
” $18 = 6 \cdot 3$ , so $18$ is a multiple of $6$ .” (Premise)
“Therefore, $18$ is a multiple of $3$ .”
“Therefore, there exists a positive integer that is a multiple of $3$ .”

Example 2.35 (Combining Quantifier Rules).

We show that “a student in this class has not read the book” and “every student in this class passed the first exam” together imply “someone who passed the first exam has not read the book.”

Let $C(x)$ denote ” $x$ is in this class,” $B(x)$ denote ” $x$ has read the book,” and $E(x)$ denote ” $x$ passed the exam.” The premises are $\exists x\,(C(x) \land \neg B(x))$ and $\forall x\,(C(x) \to E(x))$ . We derive $\exists x\,(E(x) \land \neg B(x))$ .

\begin{array}{rll} 1. & \exists x\,(C(x) \land \neg B(x)) & \text{Premise} \\ 2. & \forall x\,(C(x) \to E(x)) & \text{Premise} \\ 3. & C(a) \land \neg B(a) \text{ for some } a & \text{EI from 1} \\ 4. & C(a) \to E(a) & \text{UI from 2} \\ 5. & C(a) & \text{Simplification from 3} \\ 6. & E(a) & \text{Modus Ponens from 4, 5} \\ 7. & \neg B(a) & \text{Simplification from 3} \\ 8. & E(a) \land \neg B(a) & \text{Conjunction from 6, 7} \\ 9. & \exists x\,(E(x) \land \neg B(x)) & \text{EG from 8} \end{array}

Fallacies

Definition 2.36 (Fallacy).

A fallacy is an argument form that appears valid but is not: the premises do not logically guarantee the conclusion, even though the reasoning may seem persuasive.

Two fallacies are especially common. Both arise from misapplying the conditional.

Affirming the Consequent. The argument ” $p \to q$ ; $q$ ; therefore $p$ ” is invalid. A counterexample: let $p = \bot$ and $q = \top$ . Then $p \to q$ is $\top$ and $q$ is $\top$ , but $p$ is $\bot$ .

Denying the Antecedent. The argument ” $p \to q$ ; $\neg p$ ; therefore $\neg q$ ” is equally invalid. With $p = \bot$ and $q = \top$ , both premises are satisfied but $\neg q$ is $\bot$ .

Both fallacies confuse an implication with its converse or its inverse: $p \to q$ does not entail $q \to p$ , nor does it entail $\neg p \to \neg q$ .

Example 2.37.

“If it rained, the pitch is wet. The pitch is wet. Therefore it rained.” This affirms the consequent. The pitch might be wet because the sprinklers were on. The converse “if the pitch is wet, then it rained” does not follow from the original implication.

Problem 2.19.

Identify the fallacy in each argument and provide a counterexample (an assignment under which the premises are true but the conclusion is false).

“If $x > 2$ , then $x > 1$ . The number $\tfrac{3}{2}$ satisfies $x > 1$ . Therefore $\tfrac{3}{2} > 2$ .”
“If $x > 0$ , then $x^2 > 0$ . The number $-1$ does not satisfy $x > 0$ . Therefore $(-1)^2 \leqslant 0$ .”

Proof Techniques

With inference rules in hand, we turn to the practical matter of constructing proofs. A proof is a finite sequence of statements, each of which is an axiom, a premise, or a consequence of earlier statements by an inference rule. What dictates the strategy is the shape of the claim: whether it asserts a conditional, a biconditional, a conjunction, a disjunction, or a quantification. Each shape comes with a direct method that builds the claim up from its parts, and an indirect method that assumes the negation and hunts for an absurdity.

Since these notes are about writing proofs, not merely admiring them, we will not simply state a result and prove it. Each proof comes with a Discussion, where we plan the argument and air the thought process, followed by the Proof itself, written in full English sentences with proper syntax and grammar. The two are kept apart on purpose. A discussion names the form of the statement, says which pieces have to be proved and by what method, and points to the definition or rule each piece will use; the proof then carries that plan out.

We have not built the numbers yet (although we have been using them), and doing so is where this course is headed. But until then we help ourselves to the arithmetic and order rules of school algebra, and we name our objects in words: a whole number is one of $\ldots, -2, -1, 0, 1, 2, \ldots$ , and a real number is any point of the number line. Every rule borrowed along the way is proved from the ground up once we have the objects to prove it about, and where a proof below leans on a borrowed rule we say which one (we will collect on any debt as we continue).

Two properties of whole numbers come up often enough in the examples to be worth fixing now.

Definition 2.38 (Even and Odd).

A whole number $n$ is even if it can be written as $n = 2k$ for some whole number $k$ , and odd if it can be written as $n = 2k + 1$ for some whole number $k$ . Every whole number is one or the other and never both.

Definition 2.39 (Prime and Composite).

A whole number greater than $1$ is composite if it is a product of two whole numbers each at least $2$ , and prime otherwise.

Proving Conditional Claims

Recall that $p \to q$ asserts that whenever $p$ holds, $q$ necessarily holds. The conditional is already true in every case where $p$ fails, so no proof need consider those cases: it is enough to suppose $p$ and deduce $q$ .

The strategies are collected below. The justification column speaks about our proofs rather than inside them, and it uses $\implies$ for that outer step, keeping it apart from the connective $\to$ that lives in the statements themselves; $\impliedby$ is the same arrow read right to left.

\small \begin{array}{lll} \textbf{Strategy} & \textbf{Approach} & \textbf{Justification} \\ \hline \text{Trivial proof} & \text{Show } q \text{ is true} & q \text{ true} \implies p \to q \text{ true} \\ \text{Vacuous proof} & \text{Show } p \text{ is false} & p \text{ false} \implies p \to q \text{ true} \\ \text{Direct proof} & \text{Assume } p,\text{ derive } q & p \vdash q \;\implies\; \vdash p \to q \\ \text{Contrapositive} & \text{Assume } \neg q,\text{ derive } \neg p & p \to q \equiv \neg q \to \neg p \\ \text{Contradiction} & \text{Assume } p \land \neg q,\text{ derive } r \land \neg r & (p \land \neg q) \to \bot \;\implies\; p \to q \end{array}

The last two are called indirect proofs, since they establish the conditional without constructing a chain from $p$ to $q$ .

The first two are degenerate, and they are worth naming only so that they are recognised when they occur. A trivial proof ignores the hypothesis altogether: “if $x > 5$ , then $x \cdot 0 = 0$ ” holds because the conclusion holds for every $x$ . A vacuous proof shows instead that the hypothesis is never met: “for every real number $x$ , if $x < x$ , then $x = 7$ ” holds because no $x$ satisfies $x < x$ .

Definition 2.40 (Direct Proof).

A direct proof of a conditional statement $p \to q$ proceeds by assuming $p$ and deriving $q$ through a sequence of valid inferences. The assumption of $p$ is not asserted as fact; it is a hypothesis under which the argument operates.

This strategy reflects the Deduction Rule, a meta-logical principle: if assuming $p$ allows us to derive $q$ using valid inferences, then the conditional $p \to q$ is established. The Deduction Rule is the bridge between the turnstile ( $\vdash$ ) and the conditional ( $\to$ ): the statement $p \vdash q$ (a syntactic derivation) becomes $p \to q$ (a logical truth).

Strategy (Direct proof of a conditional).

Claim: $p \to q$

Suppose $p$ holds.
Prove that $q$ holds.

Proposition 2.41.

If $x > 1$ , then $x^2 > 1$ .

Discussion.

We will assume $x > 1$ and show $x^2 > 1$ . Our tool is the well-known algebraic rule (which we prove later on) that if $a > b$ and $c > d$ with all four numbers positive, then $ac > bd$ .

Proof.

Assume $x > 1$ . Since $x > 1 > 0$ , both $x$ and $1$ are positive, so multiplying the inequality $x > 1$ by itself yields $x^2 > 1 \cdot 1 = 1$ . Thus $x^2 > 1$ .

Our statements will grow considerably more complicated than this, but the shape stays the same. With the proof done, we may now say with full mathematical confidence that whenever a number $x$ satisfies $x > 1$ , it automatically satisfies $x^2 > 1$ .

As we know the contrapositive $\neg q \to \neg p$ is logically equivalent to $p \to q$ , so proving either one proves the other. The swap is worth making when $p$ or $q$ carries a negation inside it, since negating it turns the assumption into a positive assertion we can compute with.

Strategy (Contrapositive proof of a conditional).

Claim: $p \to q$

Suppose $\neg q$ holds.
Prove that $\neg p$ holds.

This is the direct strategy applied to $\neg q \to \neg p$ .

Proposition 2.42.

If $x^3 < 0$ , then $x < 0$ .

Discussion.

Here $p$ is " $x^3 < 0$ " and $q$ is " $x < 0$ ". Proving this directly is awkward, since we would begin knowing a fact about $x^3$ and have to dig our way down to a fact about $x$ . The contrapositive turns the tables. Since $\neg q$ is " $x \geqslant 0$ " and $\neg p$ is " $x^3 \geqslant 0$ ", the contrapositive $\neg q \to \neg p$ reads “if $x \geqslant 0$ , then $x^3 \geqslant 0$ ”, where we start from $x$ and build up to $x^3$ ; that direction is straightforward. So we will assume $x \geqslant 0$ and show $x^3 \geqslant 0$ , announcing at the outset that we are proving the contrapositive.

Proof.

We prove the contrapositive: if $x \geqslant 0$ , then $x^3 \geqslant 0$ . Assume $x \geqslant 0$ . Since all terms are non-negative, multiplying $x \geqslant 0$ by itself thrice gives $x \cdot x \cdot x \geqslant 0 \cdot 0 \cdot 0$ , that is, $x^3 \geqslant 0$ . The contrapositive holds, so the original statement “if $x^3 < 0$ , then $x < 0$ ” holds as well.

Indirect proofs

Every indirect method below will lean on the same piece of apparatus.

Definition 2.43 (Proof by Contradiction).

A proof by contradiction (Latin: reductio ad absurdum) establishes a proposition $p$ by assuming $\neg p$ and deriving a contradiction, that is, a statement of the form $q \land \neg q$ for some proposition $q$ . Since a sound proof system cannot derive a false conclusion from true premises, the assumption $\neg p$ must be false, so $p$ is true.

The opening move of such a proof is written so often that i abbreviate it to AFSOC standing for “assume for the sake of contradiction.” What we assume is the logical negation of the claim, so each indirect strategy below is really the negation rules of earlier read as instructions.

So in the case of the direct proof, the indirect method rests on the negation of a conditional, $\neg(p \to q) \equiv p \land \neg q$ . Assuming the negation therefore means granting ourselves the hypothesis and the failure of the conclusion at once, which is one more fact to work with than a direct proof has.

Strategy (Indirect proof of a conditional).

Claim: $p \to q$

AFSOC that $p$ holds and $q$ fails.
Find a contradiction.

Proposition 2.44.

For all real numbers $x$ and $y$ , if $x + y > 2$ , then $x > 1$ or $y > 1$ .

Discussion.

Our statement is the conditional $p \to q$ , where $p$ is " $x + y > 2$ " and $q$ is the disjunction ” $x > 1$ or $y > 1$ ”. A direct proof would have to settle which half of $q$ to aim at, and the hypothesis does not decide that for us, so we go indirectly. The negation of the whole statement is $p \land \neg q$ , and De Morgan turns $\neg q$ into ” $x \leqslant 1$ and $y \leqslant 1$ ”. That leaves us with three inequalities: we add the two coming from $\neg q$ and set the result against $p$ .

Proof.

AFSOC that $x + y > 2$ and that the conclusion fails, so that $x \leqslant 1$ and $y \leqslant 1$ . Adding these two inequalities gives $x + y \leqslant 2$ . But we assumed $x + y > 2$ , and no number is both greater than $2$ and at most $2$ . Therefore, whenever $x + y > 2$ , at least one of $x > 1$ , $y > 1$ holds.

Remark (Contradiction Against Contrapositive).

The two indirect routes are easy to confuse. A proof by contradiction assumes the negation of the entire statement, $p \land \neg q$ , and derives an absurdity from it. A contrapositive proof assumes only $\neg q$ and derives $\neg p$ , which is a direct proof of an equivalent statement and never mentions absurdity at all. In practice both are often labelled “proof by contradiction,” but the contrapositive route is usually the cleaner of the two, and it is the one to reach for first.

Problem 2.20.

Prove that if $0 < x < 1$ , then $x^2 < x$ .

Problem 2.21.

Prove that for all whole numbers $n$ , if $3n + 2$ is odd, then $n$ is odd.

Problem 2.22.

Prove that for all real numbers $x$ , if $x^5 < 0$ , then $x < 0$ .

Proving Biconditional Claims

The connective $\leftrightarrow$ is defined entirely in terms of $\to$ : asserting $p \leftrightarrow q$ is asserting the conjunction $(p \to q) \land (q \to p)$ . That gives the obvious strategy, prove one conditional and then the other, and it exposes the most common mistake we see, which is proving one of them and stopping. The two directions are labelled ( $\implies$ ) and ( $\impliedby$ ), and each may be proved by whichever of the conditional methods suits it; there is no requirement that both use the same one.

Strategy (Direct proof of a biconditional).

Claim: $p \leftrightarrow q$

Prove that $p \to q$ , by any of the conditional methods.
Prove that $q \to p$ , by any of the conditional methods.

Consider ” $n$ is even if and only if $n^2$ is even”. Before the proof, recall the two forms an even and an odd whole number take, $n = 2k$ and $n = 2k + 1$ .

Proposition 2.45.

$n$ is even if and only if $n^2$ is even.

Discussion.

The two conditionals are $p \to q$ , “if $n$ is even, then $n^2$ is even”, and $q \to p$ , “if $n^2$ is even, then $n$ is even”. The first is straightforward: write $n = 2k$ and show that $n^2 = 2(\text{whole number})$ . The second is trickier, since its hypothesis tells us about $n^2$ when we want a conclusion about $n$ ; so we take its contrapositive $\neg p \to \neg q$ , “if $n$ is odd, then $n^2$ is odd”, assume $n = 2k + 1$ , and show that $n^2 = 2(\text{whole number}) + 1$ .

Proof.

( $\implies$ ) First, suppose $n$ is even, so $n = 2k$ for some whole number $k$ . Then $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$ , and since $2k^2$ is a whole number, $n^2$ is even.

( $\impliedby$ ) The remaining conditional is “if $n^2$ is even, then $n$ is even”, and we prove its contrapositive: if $n$ is odd, then $n^2$ is odd. Suppose $n = 2k + 1$ for some whole number $k$ . Squaring, $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1,$ and since $2k^2 + 2k$ is a whole number, $n^2$ is odd. The contrapositive holds, so the second conditional does too. Both conditionals are proven, and with them the biconditional.

Strategy (Indirect proof of a biconditional).

Claim: $p \leftrightarrow q$

AFSOC that $\neg(p \to q) \lor \neg(q \to p)$ .
In the first case, $p \land \neg q$ holds. Find a contradiction.
In the second case, $q \land \neg p$ holds. Find a contradiction.

Whether this route is worth taking depends entirely on what $p$ and $q$ are, and the direct one usually wins; but it earns its keep when both directions resist a straight argument: the two negations $p \land \neg q$ and $q \land \neg p$ each hand us two facts to work with where the direct proof gets one.

Proposition 2.46.

Let $x$ be a real number. Then $x = 0$ if and only if no real number $y$ satisfies $xy = 1$ .

Discussion.

Our statement is the biconditional $p \leftrightarrow q$ , where $p$ is " $x = 0$ " and $q$ is “no real number $y$ satisfies $xy = 1$ ”. Both directions resist a direct argument for the same reason, which is that $q$ is itself a denial: proving it outright would mean ruling out every candidate $y$ one at a time, thus negating gets round both problems. In the first case we hold $p$ along with $\neg q$ , and $\neg q$ produces an actual $y$ with $xy = 1$ , into which we may substitute $x = 0$ . In the second we hold $q$ along with $\neg p$ , and $x \neq 0$ is exactly the condition under which we may divide by $x$ , which builds the very $y$ that $q$ says is not there.

Proof.

AFSOC that one of the two conditionals fails.

Suppose first that $p$ holds and $q$ fails, so that $x = 0$ and some real number $y$ satisfies $xy = 1$ . Then $1 = xy = 0 \cdot y = 0$ , and $1 \neq 0$ .

Suppose instead that $q$ holds and $p$ fails, so that no real number $y$ satisfies $xy = 1$ , and $x \neq 0$ . Since $x \neq 0$ we may divide by it, and $y = \frac{1}{x}$ is then a real number with $xy = 1$ , which $q$ denies.

Neither case can stand, so both conditionals hold and the biconditional with them.

A third route is neither direct nor indirect. Rather than linking $p$ and $q$ to each other, we find an intermediary statement $r$ and prove $p \leftrightarrow r$ and $r \leftrightarrow q$ ; the chain then forces $p$ and $q$ to share a truth value. The acronym TFAE, “the following are equivalent,” names the theorems built this way: a list of conditions, all asserted to imply one another, proved by running a cycle of implications through the list.

Strategy (Intermediary proof of a biconditional).

Claim: $p \leftrightarrow q$

Find a statement $r$ .
Prove that $p \leftrightarrow r$ , by any of the methods above.
Prove that $r \leftrightarrow q$ , by any of the methods above.

Proposition 2.47.

For a real number $x$ , the following are equivalent: $x^2 = x$ ; the product $x(x - 1)$ is zero; $x = 0$ or $x = 1$ .

Discussion.

Our statement puts three conditions on a real number $x$ and asserts that any one of them forces the other two, so we take $r$ to be " $x(x-1) = 0$ " and prove the two biconditionals $x^2 = x \leftrightarrow r$ and $r \leftrightarrow$ ” $x = 0$ or $x = 1$ ”, each of them directly. The first is a rearrangement, and it runs in both directions because subtracting $x$ from both sides is undone by adding it back. The second is the zero product rule, which we borrow here and prove below.

Proof.

Take $r$ to be the statement " $x(x - 1) = 0$ ".

( $x^2 = x \leftrightarrow r$ ) Subtracting $x$ from both sides of $x^2 = x$ gives $x^2 - x = 0$ , and $x^2 - x = x(x - 1)$ , so $r$ holds. Adding $x$ to both sides of $x(x-1) = 0$ reverses the step, so the two conditions imply one another.

( $r \leftrightarrow x = 0$ or $x = 1$ ) We borrow the zero product rule: a product of two real numbers is zero exactly when one of the factors is zero. (It is proved below, in the section on disjunctions.) So $x(x - 1) = 0$ holds exactly when $x = 0$ or $x - 1 = 0$ , and the latter says $x = 1$ . The chain of equivalences carries the truth value from the first condition to the third, so all three stand or fall together.

Remark (Always Check the Converse).

A common error is to prove one direction of a biconditional and assume the other follows. Consider the equation $\sqrt{x - 3} + \sqrt{x + 4} = 7$ . Squaring both sides and simplifying produces $x = 12$ as the sole candidate. Squaring can introduce extraneous solutions, so we must substitute back: $\sqrt{9} + \sqrt{16} = 3 + 4 = 7$ , and here the candidate is genuine. Contrast this with $x + \sqrt{x} = 0$ : squaring leads to candidates $x = 0$ and $x = 1$ , but $1 + \sqrt{1} = 2 \neq 0$ , so only $x = 0$ is a true solution.

Problem 2.23.

Prove that a whole number $n$ is even if and only if $n + 1$ is odd. Then prove it a second time by the indirect method.

Problem 2.24.

Prove that a real number $x$ satisfies $x^3 = x$ if and only if $x = 0$ , $x = 1$ , or $x = -1$ .

Proving Conjunctions

A conjunction asks for two proofs; The only thing worth saying about the direct method is that both halves must actually appear.

Strategy (Direct proof of a conjunction).

Claim: $p \land q$

Prove that $p$ holds.
Prove that $q$ holds.

Proposition 2.48.

If $x > 1$ , then $x^2 > x$ and $x^3 > x^2$ .

Discussion.

Let $p$ be " $x^2 > x$ " and $q$ be " $x^3 > x^2$ ", with the hypothesis $x > 1$ available to both. For $p$ we borrow a second rule of order, that if $a > b$ and $c > 0$ , then $ac > bc$ ; since $x > 1 > 0$ , multiplying $x > 1$ by $x$ gives $x^2 > x$ . For $q$ we multiply $x > 1$ by $x^2$ instead, which the same rule permits once we know $x^2$ is positive, and $p$ has just told us that $x^2 > x > 1$ .

Proof.

Assume $x > 1$ . Since $x > 1 > 0$ , the number $x$ is positive, so multiplying both sides of $x > 1$ by $x$ gives $x^2 > x$ , which is the first half.

For the second half, note that $x^2 > x > 1 > 0$ , so $x^2$ is positive as well. Multiplying both sides of $x > 1$ by $x^2$ gives $x^3 > x^2$ . Both halves hold, so their conjunction does.

By De Morgan’s law the negation of $p \land q$ is a disjunction, so the indirect method splits into two cases, each of which must be run to an absurdity.

Strategy (Indirect proof of a conjunction).

Claim: $p \land q$

AFSOC that $\neg p \lor \neg q$ holds.
In the first case, $\neg p$ holds. Find a contradiction.
In the second case, $\neg q$ holds. Find a contradiction.

Problem 2.25.

Prove the proposition above a second time by the indirect method, assuming that $x > 1$ and that $x^2 \leqslant x$ or $x^3 \leqslant x^2$ . Compare the two proofs and say which you would rather read.

Proving Disjunctions

A disjunction asserts that at least one of two statements holds. If we can tell in advance which one it is, there is nothing to discuss: prove that one and ignore the other. That is the direct method, and it is a strategy in name only.

Strategy (Direct proof of a disjunction).

Claim: $p \lor q$

Prove that $p$ holds, or else prove that $q$ holds.

The interesting case is when neither half holds on its own, because $p$ and $q$ are predicates and which of them is true varies with the object. Rather than sort out exactly which objects satisfy which, we argue that if $p$ holds the claim is already proved and $q$ need not be looked at, which leaves only the cases where $p$ fails, and there we must guarantee $q$ . Since $p \lor q \equiv q \lor p$ , the roles may be swapped, and we assume whichever negation is more useful.

Strategy (Proof of a disjunction by otherwise).

Claim: $p \lor q$

Suppose $\neg p$ holds.
Prove that $q$ holds.

Proposition 2.49.

For every real number $x$ , either $x \leqslant 1$ or $x^2 > x$ .

Discussion.

Our statement is the disjunction $p \lor q$ , where $p$ is " $x \leqslant 1$ " and $q$ is " $x^2 > x$ ", and neither half holds for every $x$ : the number $\tfrac{1}{2}$ satisfies $p$ and fails $q$ , while $2$ does the reverse. Thus, we take the “otherwise” route: here $\neg p$ reads $x > 1$ , and multiplying that inequality by the positive number $x$ gives $q$ .

Proof.

Suppose $x \leqslant 1$ fails, so $x > 1$ . Then $x$ is positive, and multiplying both sides of $x > 1$ by $x$ gives $x^2 > x$ . Hence in every case at least one of the two holds.

The negation of a disjunction is a conjunction of negations, so the indirect method grants us both failures at once.

Strategy (Indirect proof of a disjunction).

Claim: $p \lor q$

AFSOC that $\neg p \land \neg q$ holds.
Find a contradiction.

Proposition 2.50.

For all real numbers $x$ and $y$ , if $xy = 0$ , then $x = 0$ or $y = 0$ .

Discussion.

This is the zero product rule we borrowed for the three equivalent conditions above: the conclusion is a disjunction, so we assume the hypothesis $xy = 0$ and negate the conclusion, which by gives us $x \neq 0$ and $y \neq 0$ together. A non-zero real number may be divided by, so we divide $xy = 0$ through by $x$ and read off a statement about $y$ that the second half of the negation denies.

Proof.

Assume $xy = 0$ , and AFSOC that both halves of the conclusion fail, so that $x \neq 0$ and $y \neq 0$ . Since $x \neq 0$ we may divide both sides of $xy = 0$ by $x$ , which gives $y = 0$ . But we assumed $y \neq 0$ , and no number is both zero and non-zero. Therefore at least one of $x = 0$ , $y = 0$ holds.

Problem 2.26.

Prove that for every real number $x$ , either $x = 0$ or $x^2 > 0$ .

Problem 2.27.

Prove the proposition about $x \leqslant 1$ and $x^2 > x$ a second time, by the indirect method.

Proving Universal Claims

To prove $\forall x \in S,\, p(x)$ we take an arbitrary element of $S$ and show that $p$ holds of it. Nothing may be assumed about that element beyond its membership in $S$ : it stands for every element at once, and Universal Generalisation is what licenses the step from it to the whole of $S$ .

Strategy (Direct proof of a universal claim).

Claim: $\forall x \in S,\; p(x)$

Let $y \in S$ be arbitrary and fixed.
Prove that $p(y)$ holds.

Proposition 2.51.

For all whole numbers $n \geqslant 3$ , the number $n^2 - 1$ is composite.

Discussion.

Our statement is universally quantified over all integers $n \geq 3$ . To prove that $n^2 - 1$ is composite, we must, by definition, produce two integers each strictly greater than $1$ whose product is $n^2 - 1$ . The identity $n^2 - 1 = (n+1)(n-1)$ gives us exactly such a factorisation. The only possible concern is whether the smaller factor, $n-1$ , is at least $2$ . The hypothesis $n \geq 3$ settles this: subtracting $1$ from both sides of $n \geq 3$ yields $n - 1 \geq 2$ , which is precisely the lower bound we need. (Had we allowed $n = 2$ , the factorisation would read $3 \cdot 1$ , which is prime and therefore would fail.)

Proof.

Let $n \geqslant 3$ be any whole number. Notice that $n^2 - 1 = (n + 1)(n - 1)$ , a product of two whole numbers. Since $n \geqslant 3$ , the smaller factor satisfies $n - 1 \geqslant 2$ , so $n^2 - 1$ is a product of two whole numbers each at least $2$ . Thus $n^2 - 1$ is composite.

Remark (Arbitrary Is Not Specific).

Consider the statement “for every whole number $n$ , $n^2 \geqslant 0$ ”. The following is not a valid proof: “let $n$ be an arbitrary whole number, say $n = 17$ . Then $17^2 = 289 \geqslant 0$ .” The writer has chosen a specific value, not an arbitrary one, and what has been proved is the existential claim, that some whole number has a non-negative square. A correct proof never names $n$ , and every step in it must hold for all the values $n$ might have taken.

The negation of a universal claim is an existential one, and the work is to show that no such object can exist. This is the route to take when the claim says that something does not happen, since “there is no object with this property” is a universal claim under a negation; it says that every object fails to have the property.

Strategy (Indirect proof of a universal claim).

Claim: $\forall x \in S,\; p(x)$

AFSOC that there is some $y \in S$ for which $\neg p(y)$ holds.
Find a contradiction.

Proposition 2.52.

There is no least positive real number. That is, no positive real number $a$ satisfies $a \leqslant b$ for every positive real number $b$ .

Discussion.

The statement says that every positive real number fails to be least, which is a universal claim although the negation in front of it hides the fact. Its negation is existential and supplies a positive $a$ with $a \leqslant b$ for every positive $b$ , so we assume such an $a$ and look for a positive number smaller than it. Halving serves: $\tfrac{a}{2}$ is positive whenever $a$ is, and it is smaller than $a$ , so it both must and cannot satisfy the inequality $a$ was assumed to satisfy.

Proof.

AFSOC that a least positive real number $a$ exists, so that $a > 0$ and $a \leqslant b$ for every positive real number $b$ . Consider $\tfrac{a}{2}$ . Since $a > 0$ we have $\tfrac{a}{2} > 0$ , so $\tfrac{a}{2}$ is itself a positive real number, and being one it must satisfy $a \leqslant \tfrac{a}{2}$ . But $\tfrac{a}{2} < a$ , and no number is both smaller than $a$ and at least $a$ . Therefore no least positive real number exists.

Problem 2.28.

Prove that for every real number $x$ there is a real number $y$ with $y > x$ .

Problem 2.29.

Let $x$ be a real number with $x \geqslant 0$ , and suppose $x \leqslant y$ for every positive real number $y$ . Prove that $x = 0$ .

Proving Existential Claims

An existential claim is a claim of existence: it asserts that some object belongs to a set and has a certain property. To prove one we exhibit such an object and verify, for our reader, both halves of the assertion, that the object is an element of the correct set and that it has the correct property. Existential Generalisation then yields the claim. A proof of this kind is called constructive, since the witness is produced.

Strategy (Direct proof of an existential claim).

Claim: $\exists x \in S,\; p(x)$

Define a specific object $y$ .
Prove that $y \in S$ .
Prove that $p(y)$ holds.

Proposition 2.53.

Fix real numbers $a, b, c, d, e, f$ with $ad - bc \neq 0$ . Then there are real numbers $x$ and $y$ satisfying both

ax + by = e \qquad \text{and} \qquad cx + dy = f.

Discussion.

The claim is existential, so the proof must produce a specific pair $x$ , $y$ and check that it satisfies both equations, which means we have to find the pair before we can write anything down. Multiplying the first equation by $d$ and the second by $-b$ makes the two $y$ terms cancel when we add:

\begin{aligned} adx + bdy &= de \\ -bcx - bdy &= -bf \\ \hline (ad - bc)x &= de - bf \end{aligned}

so $x = \frac{de - bf}{ad - bc}$ , which is a real number precisely because $ad - bc \neq 0$ . Cancelling the $x$ terms the same way, by multiplying the first equation by $c$ and the second by $-a$ , gives $(bc - ad)y = ce - af$ and so $y = \frac{af - ce}{ad - bc}$ .

None of this scratch work belongs in the proof. A reader does not care how we came upon the pair; they care what the pair is and why it works, and the proof is shorter and easier to check for leaving the search out.

Proof.

Since $ad - bc \neq 0$ , we may define

x = \frac{de - bf}{ad - bc} \qquad \text{and} \qquad y = \frac{af - ce}{ad - bc},

and both are real numbers. Substituting them into the two equations,

\begin{aligned} ax + by &= \frac{(ade - abf) + (abf - bce)}{ad - bc} = \frac{ade - bce}{ad - bc} = \frac{e(ad - bc)}{ad - bc} = e, \\ cx + dy &= \frac{(cde - bcf) + (adf - cde)}{ad - bc} = \frac{adf - bcf}{ad - bc} = \frac{f(ad - bc)}{ad - bc} = f. \end{aligned}

So the pair $x, y$ satisfies both equations, and such a pair exists.

In a non-constructive existence proof we establish that a witness must exist without identifying it. The indirect method is of this kind: it never produces the object, it only rules out a world in which the object is missing.

Strategy (Indirect proof of an existential claim).

Claim: $\exists x \in S,\; p(x)$

AFSOC that for every $y \in S$ , $\neg p(y)$ holds.
Find a contradiction.

Proposition 2.54.

Let $a$ , $b$ , $c$ be real numbers. Then two of them have a non-negative product.

Discussion.

The claim is again existential, but this time there is no pair we could name in advance, since which two work depends on the signs of $a$ , $b$ , $c$ and the statement gives us no signs. So we prove it indirectly. The negation says that every pair fails, and it hands us the three inequalities $ab < 0$ , $bc < 0$ and $ac < 0$ at once. Multiplying all three together produces $(abc)^2$ , and a square cannot be negative.

Proof.

AFSOC that no two of $a$ , $b$ , $c$ have a non-negative product, so that $ab < 0$ , $bc < 0$ , and $ac < 0$ . Multiplying the first two of these negative numbers gives a positive one, and multiplying that by the third gives a negative one, so

(ab)(bc)(ac) < 0.

But $(ab)(bc)(ac) = a^2b^2c^2 = (abc)^2$ , and we borrow the rule that the square of a real number is never negative. (It is proved below, in the section on disproving claims.) So $(abc)^2$ is both negative and non-negative, which is impossible. Therefore some two of $a$ , $b$ , $c$ have a non-negative product.

Notice what the proof does not tell us: which pair it is. It rules out the world in which no pair works and stops there, and that is the mark of a non-constructive argument.

Unique existence asks for a second step. We find the object that works, then show it is the only one, which we do by assuming that $x$ and $y$ both work and concluding that $x = y$ .

Strategy (Proof of a unique existential claim).

Claim: $\exists!\, x \in S,\; p(x)$

Prove $\exists x \in S,\; p(x)$ , by either method above.
Suppose $p(x)$ and $p(y)$ both hold, and prove that $x = y$ .

Proposition 2.55.

There exists a unique real number $x$ such that $3x - 1 = 0$ .

Discussion.

Unique existence is two claims, so the proof comes in two halves. Existence asks for one real number satisfying $3x - 1 = 0$ , and we verify $x = \tfrac{1}{3}$ by substitution rather than display the rearrangement that found it. Uniqueness is the half that gets forgotten: producing a solution says nothing about whether a second one is hiding somewhere, so we suppose that $x$ and $y$ both satisfy the equation and show that the supposition forces $x = y$ .

Proof.

Consider $x = \tfrac{1}{3}$ : then $3 \cdot \tfrac{1}{3} - 1 = 1 - 1 = 0$ , so at least one real number works. For uniqueness, suppose $x$ and $y$ both satisfy the equation. Then $3x - 1 = 0 = 3y - 1$ , so $3x = 3y$ , and dividing by $3$ gives $x = y$ . Thus exactly one real number satisfies $3x - 1 = 0$ .

Problem 2.30.

Fix a real number $a$ . Prove that the equation $x^2 + 2ax + a^2 = 0$ has exactly one real solution.

Problem 2.31.

Fix a real number $a$ . Prove that there is a real number $x$ satisfying $x^3 + (1 - a^2)x - a = 0$ .

Disproving Claims

To disprove a statement is to show that its truth value is $\bot$ , and by the definition of negation that is the same as showing its negation is $\top$ . So there is nothing new to learn: write down the logical negation, then prove that statement by whichever of the strategies above fits its shape. The negation rules are what turn the disproof into a proof, and they say which shape we end up with.

Disproving a universal claim therefore means proving an existential one, and the object we produce is the counterexample we met when the quantifier was introduced. Exhibiting a single one settles the matter, however many objects satisfy the claim.

Example 2.56 (A Universal Claim).

Disprove: for all prime numbers $n$ , the number $n$ is odd.

Discussion.

Disproving a universal claim means proving its negation, which here is the existential claim that some prime fails to be odd, so one prime is all we have to produce. An even number has the form $2k$ , and any $k \geqslant 2$ makes $2k$ a product of two whole numbers each at least $2$ , hence composite; that leaves $k = 1$ as the only candidate, and it works.

Disproof.

The number $2$ is prime, and $2$ is even. Thus it is not true that all primes are odd.

Disproving an existential claim is the harder direction, since its negation is universal: every single object must fail, and there is no shortcut through exhibiting one of them.

Example 2.57 (An Existential Claim).

Disprove: there exists a real number $x$ such that $x^2 < 0$ .

Discussion.

Disproving an existential claim means proving its negation, and that negation is universal: every real number must satisfy $x^2 \geqslant 0$ , so no single well-chosen $x$ will settle it and the argument has to cover all of them at once. What stands in the way is the sign of $x$ , which we are not told and which decides how the inequality behaves under multiplication, so we split on it and run the two cases separately.

Disproof.

We show that for all real numbers $x$ , $x^2 \geqslant 0$ . Every real number falls into one of two cases, $x \geqslant 0$ or $x < 0$ . If $x \geqslant 0$ , multiplying the inequality by itself preserves the sign, so $x \cdot x \geqslant 0 \cdot 0$ , that is, $x^2 \geqslant 0$ . If $x < 0$ , multiplying through by $-1$ flips the inequality to $-x > 0$ ; multiplying $-x > 0$ by itself then gives $(-x)(-x) > 0 \cdot 0$ , so $x^2 > 0$ and in particular $x^2 \geqslant 0$ . Either way $x^2 \geqslant 0$ , so the claim is false.

Problem 2.32.

Disprove: for every real number $x$ , $x^2 > x$ .

Problem 2.33.

Disprove: there is a real number $x$ with $x^2 + x + 1 = 0$ .

The Law of Excluded Middle

Theorem 2.58 (Law of Excluded Middle).

For any proposition $p$ , $p \lor \neg p$ is a tautology.

Proof.

By the Complement axiom, $\neg p \lor p \equiv \top$ . By the Commutativity axiom, $\neg p \lor p \equiv p \lor \neg p$ . Therefore $p \lor \neg p \equiv \top$ .

The Law of Excluded Middle (LEM) asserts that every proposition is either true or false; no third possibility exists. In proofs, LEM is what allows us to split into the exhaustive cases $p$ and $\neg p$ without knowing which of them actually holds, and a conclusion reached in both cases is established without our ever finding out.

Proposition 2.59.

Let $m$ and $n$ be whole numbers. If $mn$ is even, then $m$ is even or $n$ is even.

Discussion.

Our statement is the conditional whose hypothesis is ” $mn$ is even” and whose conclusion is the disjunction ” $m$ is even or $n$ is even”. The hypothesis says nothing about $m$ on its own and no computation extracts it, so we appeal to LEM and split on whether $m$ is even. One case gives the conclusion immediately. In the other $m$ is odd, and we show that an odd $n$ would make $mn$ odd against the hypothesis, which leaves $n$ even.

Proof.

Suppose $mn$ is even. By LEM, either $m$ is even or $m$ is odd.

Case 1. If $m$ is even, the conclusion holds immediately.

Case 2. Suppose $m$ is odd, so $m = 2j + 1$ for some whole number $j$ . If $n$ were also odd, say $n = 2k + 1$ , then $mn = (2j + 1)(2k + 1) = 4jk + 2j + 2k + 1 = 2(2jk + j + k) + 1,$ so $mn$ would be odd, contradicting the hypothesis that $mn$ is even. Therefore $n$ is even.

In both cases at least one of $m$ , $n$ is even.

Problem 2.34.

Using the Law of Excluded Middle, prove that for all whole numbers $n$ , the number $n(n + 1)$ is even.

Problem 2.35.

Look again at the proof above. Where was the Law of Excluded Middle used, where was contradiction used, and what was the contradiction? Prove the same result twice more: once using contradiction without LEM, and once using LEM without contradiction.

Ex Falso Quodlibet

The principle ex falso sequitur quodlibet (“from falsity follows whatever you like”) states that from a contradiction, any proposition may be derived:

\frac{p \quad \neg p}{q} \quad \text{for every } q

Its validity rests on the tautology $(p \land \neg p) \to q$ : since $p \land \neg p$ is identically false, the conditional holds for every $q$ by vacuous truth.

Example 2.60 (Consequences of a Contradiction).

Suppose we accept the false premise $-1 = 1$ . Adding $1$ to both sides gives $0 = 2$ , a false consequence. Squaring both sides gives $1 = 1$ , a true consequence. From a single contradiction, both true and false statements follow. Once a contradiction enters, the proof system can no longer distinguish truth from falsehood, and every proposition becomes derivable.

We rarely invoke Ex Falso directly, but it is the logical foundation of every indirect proof above: if assuming the negation of our claim produces a contradiction with our true premises, then that negation cannot coexist with those premises, and the claim must hold.

Using Assumptions in Proofs

When we state a theorem it usually has hypotheses and a conclusion, and those hypotheses are ours to use: we add them to our toolkit for the duration of the proof, along with whatever facts we develop along the way.

A disjunction means cases. Suppose that at some point we have assumed or deduced $p \lor q$ . Knowing the disjunction holds means at least one of $p$ , $q$ holds, so we may consider each separately and argue as follows.

Strategy (Using a disjunction).

Because $p \lor q$ , we have two cases.

Case 1. Suppose $p$ holds. Then …

Case 2. Suppose $q$ holds. Then …

As long as the goal is reached in both cases, the deduction stands; this is the disjunction elimination rule doing its work. There is no need for a third case in which both hold, since it might not arise at all, and reaching the goal from one or the other on its own shows that assuming both was never necessary.

Remark (Without Loss of Generality).

It sometimes happens that two cases are identical up to a relabelling of variables. We then handle one case and dismiss the other with the phrase “without loss of generality” (abbreviated WLOG). For instance, to prove by contrapositive that “if $x$ and $y$ are whole numbers and both $xy$ and $x + y$ are even, then $x$ and $y$ are both even,” we must show that if $x$ or $y$ is odd then $xy$ or $x + y$ is odd. Since the hypotheses are symmetric in $x$ and $y$ , we may assume WLOG that $x$ is odd; the remaining case follows by swapping $x$ and $y$ .

“There exists” is not “let such an $x$ be given”. Writing $\exists x \in S,\, p(x)$ in the middle of a proof asserts only that the line is true: that some element of $S$ with the property is out there. It does not introduce one. If we go on to refer to $x$ afterwards, the step is not valid, since nothing has been named; several such elements might exist, and a reader cannot be left to guess whether we mean all of them or one in particular. To bring one into play, say so: let such an $x$ be given. Thereafter $x$ names an element with that property and may be used like any other object. Several at once are introduced the same way: “and so we deduce that there exist whole numbers $x$ , $y$ , $z$ such that $p(x, y, z)$ holds. Let such $x$ , $y$ , $z$ be given.”

" $p \to q$ " is not ” $p$ , therefore $q$ ”. Writing $p \to q$ on the page asserts that the implication holds; it does not assert $q$ . To deduce $q$ we must make it clear that we also have $p$ , and that we are using Modus Ponens on the two.

Strategy (Using a conditional).

$p \to q$ because …

Also, $p$ holds because …

Therefore $q$ holds.

Remark (Mistakes in Proofs).

A chain of equalities is only as strong as its weakest step. Consider the “proof” that $-1 = 1$ :

\begin{aligned} -1 &= (-1)^1 \\ &= (-1)^{2/2} \\ &= \bigl((-1)^2\bigr)^{1/2} \\ &= 1^{1/2} \\ &= 1 \end{aligned}

The error is in the third step: the law $(x^a)^b = x^{ab}$ requires $x \geqslant 0$ . Each step in a proof must be a valid inference rather than a plausible manipulation.

Finally, Quantifiers can also conceal errors. The formula $(p \to q) \lor (q \to p)$ is a propositional tautology (verify this by truth table). Substituting predicates $p(n)$ = ” $n$ is odd” and $q(n)$ = ” $n$ is prime,” one might reason: “for every $n$ , either oddness implies primality or primality implies oddness.” Yet neither $\forall n\,(p(n) \to q(n))$ nor $\forall n\,(q(n) \to p(n))$ is true. The resolution is that $\forall n\,[(p(n) \to q(n)) \lor (q(n) \to p(n))]$ is not the same as $[\forall n\,(p(n) \to q(n))] \lor [\forall n\,(q(n) \to p(n))]$ . The universal quantifier does not distribute over disjunction. The first formula is indeed true (for each fixed $n$ , one of the two conditionals holds), but the second is false.

Exercises

Answers are checked in your browser, as often as you like. Nothing is sent anywhere and nothing is kept but your own work. A formula may be written with the symbols themselves or with ~ & | -> <-> ^, and \and, \or, \to expand as you type.

Exercises in Lean

The proofs below are checked in your browser. Nothing is sent anywhere, and nothing is stored but your own work. Type \to for →, \and for ∧, \< and \> for ⟨ ⟩.

The last sheet gave us three tactics, intro, exact and apply, and with them the implication, $\top$ , $\bot$ and negation. What is missing is the rest of the connectives. Each of $\land$ , $\lor$ and $\leftrightarrow$ comes with two questions: how to prove one, and what to do with one we have been handed. The quantifiers wait for the next sheet.

Conjunction

`constructor`

A conjunction is proved by proving both halves. If the goal is ⊢ p ∧ q, then constructor replaces it with the two goals ⊢ p and ⊢ q. A tactic acts on the first goal only, so from here on we write each goal’s proof under a focus dot ·, indented; the dot takes the first goal and the block under it must finish that goal off.

Example.

Put the caret on the constructor line and then on the line below it to watch one goal become two.

A conjunction may also be built in one term: ⟨hp, hq⟩ is the proof of p ∧ q made from a proof of each half. Type \< for ⟨ and \> for ⟩.

Taking one apart

If h : p ∧ q then h.1 is a proof of p and h.2 is a proof of q; they may also be written h.left and h.right.

Example.

The projection is a term, so it goes where any other proof would.

`obtain`

Where both halves are wanted, it reads better to take the hypothesis apart once and for all. obtain ⟨hp, hq⟩ := h replaces h : p ∧ q with hp : p and hq : q.

Example.

The same brackets take a conjunction apart on the left and build one on the right.

Exercise 2.13.

Two assumptions make their conjunction.

Exercise 2.14.

The order of a conjunction carries no information.

Exercise 2.15.

Nor does the bracketing.

Exercise 2.16.

Two hypotheses taken in turn, against the two taken together.

Exercise 2.17.

No statement holds alongside its own negation.

Disjunction

`left` and `right`

A disjunction is proved by proving one half and saying which. With the goal ⊢ p ∨ q, left changes it to ⊢ p and right changes it to ⊢ q. The choice is ours to make and cannot be deferred, so making the wrong one leaves a goal that cannot be closed. In term form the two are Or.inl and Or.inr, each applied to a proof of the half it names.

Example.

Nothing is known about $p$ , so the right half is the one to go for.

`rcases`

A disjunction we have been handed is weaker than a conjunction: it says that one of the two holds without saying which, so anything we conclude from it has to be concluded twice. rcases h with hp | hq splits h : p ∨ q into two goals, the first with hp : p and the second with hq : q, and the bar is what marks the split.

Example.

The goal is the same in both branches; only the hypothesis differs.

Exercise 2.18.

The order of a disjunction carries no information either, but here we must first find out which half we were handed.

Exercise 2.19.

Nor does the bracketing of a disjunction.

Exercise 2.20.

Conjunction distributes over disjunction.

Exercise 2.21.

One of De Morgan’s laws.

Exercise 2.22.

Half of the defining equivalence of the conditional.

Exercise 2.23.

And the other half.

Equivalence

Both directions

p ↔ q is the conjunction of p → q and q → p, and it behaves like one. On a goal ⊢ p ↔ q, constructor leaves the two implications as separate goals; ⟨h, k⟩ builds the equivalence from a proof of each direction.

Example.

The two goals arrive in the order the equivalence is written.

If h : p ↔ q then h.mp is the forward implication and h.mpr the backward one, so h.mp hp is a proof of q and h.mpr hq a proof of p. obtain ⟨f, g⟩ := h takes the two apart as it does for a conjunction.

Example.

An equivalence is used in whichever direction the goal asks for.

Exercise 2.24.

An equivalence may be read from either end.

Exercise 2.25.

Equivalence is transitive.

Exercise 2.26.

A statement conjoined with itself says no more than the statement.

Exercise 2.27.

Equivalent statements may be swapped for one another inside a disjunction.

Exercise 2.28.

No statement is equivalent to its own negation.

What the checker understands

Tactics

intro h	assume the hypothesis of an implication, naming it h
exact e	give the proof outright
apply f	reduce the goal to the hypotheses of f
assumption	close the goal with a hypothesis already present
trivial	close the goal True
exfalso	replace the goal with False
by_contra h	assume the negation of the goal
constructor	split ∧ into both halves, or ↔ into both directions
left / right	choose which half of a ∨ to prove
rcases h with a \| b	argue by cases on a disjunction
obtain ⟨a, b⟩ := h	take a conjunction or an existential apart
cases h	as above, keeping the name

Results you may cite

Classical.em	∀ (a : Prop), a ∨ ¬a — the law of excluded middle
Classical.byContradiction	∀ {a : Prop}, (¬a → False) → a — proof by contradiction; the tactic by_contra does this for you
Classical.byCases	∀ {a b : Prop}, (a → b) → (¬a → b) → b — split on whether a holds
not_not	∀ {a : Prop}, ¬¬a ↔ a — double negation
not_and_or	∀ {a b : Prop}, ¬(a ∧ b) ↔ ¬a ∨ ¬b — De Morgan
not_or	∀ {a b : Prop}, ¬(a ∨ b) ↔ ¬a ∧ ¬b — De Morgan
not_imp	∀ {a b : Prop}, ¬(a → b) ↔ a ∧ ¬b
and_comm	∀ {a b : Prop}, a ∧ b ↔ b ∧ a
or_comm	∀ {a b : Prop}, a ∨ b ↔ b ∨ a

From the logical core

And.intro	∀ {a b : Prop}, a → b → a ∧ b
And.left	∀ {a b : Prop}, a ∧ b → a
And.right	∀ {a b : Prop}, a ∧ b → b
And.symm	∀ {a b : Prop}, a ∧ b → b ∧ a
Or.inl	∀ {a b : Prop}, a → a ∨ b
Or.inr	∀ {a b : Prop}, b → a ∨ b
Or.elim	∀ {a b c : Prop}, a ∨ b → (a → c) → (b → c) → c
Or.symm	∀ {a b : Prop}, a ∨ b → b ∨ a
Iff.intro	∀ {a b : Prop}, (a → b) → (b → a) → (a ↔ b)
Iff.mp	∀ {a b : Prop}, (a ↔ b) → a → b
Iff.mpr	∀ {a b : Prop}, (a ↔ b) → b → a
Iff.symm	∀ {a b : Prop}, (a ↔ b) → (b ↔ a)
Iff.rfl	∀ {a : Prop}, a ↔ a
Iff.trans	∀ {a b c : Prop}, (a ↔ b) → (b ↔ c) → (a ↔ c)
True.intro	True
False.elim	∀ {a : Prop}, False → a
absurd	∀ {a b : Prop}, a → ¬a → b
id	∀ {a : Prop}, a → a
mt	∀ {a b : Prop}, (a → b) → ¬b → ¬a
Eq.refl	∀ {α : Type} (a : α), a = a
Eq.symm	∀ {α : Type} {a b : α}, a = b → b = a
Eq.trans	∀ {α : Type} {a b c : α}, a = b → b = c → a = c
congrArg	∀ {α : Type} {β : Type} {a b : α} (f : α → β), a = b → f a = f b
Exists.intro	∀ {α : Type} {p : α → Prop} (w : α), p w → ∃ x : α, p x
Exists.elim	∀ {α : Type} {p : α → Prop} {b : Prop}, (∃ x : α, p x) → (∀ y : α, p y → b) → b

Predicates

Variables and Predicates

Introduction to Sets

Quantifiers

The Universal Quantifier

Specifying the Quantification Set

The Existential Quantifier

Scope and Variable Binding

The Unique Existential Quantifier

Formalising Arguments

Quantifier Negation

Negation and Bounded Quantifiers

Distribution of Quantifiers over Connectives

Validity and Satisfiability in Predicate Logic

Nested Quantifiers

Order of Quantifiers

Quantification Fixes a Variable

Negating Nested Quantifiers

Proofs

Valid Arguments and Inference Rules

Arguments and Validity

Modus Ponens

Modus Tollens

Hypothetical Syllogism

Implication Elimination

Further Propositional Inference Rules

Building Complex Arguments

Inference Rules for Quantified Statements

Fallacies

Proof Techniques

Proving Conditional Claims

Indirect proofs

Proving Biconditional Claims

Proving Conjunctions

Proving Disjunctions

Proving Universal Claims

Proving Existential Claims

Disproving Claims

The Law of Excluded Middle

Ex Falso Quodlibet

Using Assumptions in Proofs

Exercises

Exercises in Lean

Conjunction

constructor

Taking one apart

obtain

Disjunction

left and right

rcases

Equivalence

Both directions

`constructor`

`obtain`

`left` and `right`

`rcases`