CommeUnJeu · L1 MPSI

Logic

⌚ ~266 min ▢ 31 blocks ✓ 98 exercises ➣ Prerequisites : Reasoning and Proof

This chapter is about the language we use to do mathematics. We have all written proofs before, and we have all said ``if $p$ then $q$'', ``for every $x$'', ``there exists''. This chapter tightens the screws. We stop treating these as informal phrasings and start treating them as mathematical objects in their own right. A connective is something we will define rigorously, by truth table; a quantifier is something whose negation we will state as a theorem; an implication is something we will know how to refute, by exhibiting one explicit counterexample.
The pay-off of this extra rigor is twofold. First, it removes the ambiguities that vague language inevitably carries: when we write $\neg(p \implies q)$, we will know exactly what we mean and we will know how to attack it. Second, it gives us a small, finite vocabulary --- five connectives, two quantifiers, four reasoning modes, three flavours of induction --- that suffices for the entire year of mathematics ahead. By the end of this chapter, every proof we will read should fit into this template.
We use T (true) and F (false) as the two truth values throughout. The chapter proceeds in five movements: we first build the connectives from their truth tables, then assemble them into tautologies and the language of necessary and sufficient conditions, next introduce the quantifiers and their negation rule, then catalogue the four classical reasoning modes, and finally treat induction in its three flavours.

I Propositions and Connectives

A proposition is a statement that has one of two truth values: V (true) or F (false). The operations one can build on propositions --- negation, conjunction, disjunction, implication, equivalence --- are called logical connectives. The decisive idea of this section is that each connective is fully described by its truth table: how it behaves on all combinations of truth values for its inputs. Once we have the table, we have the connective; everything else --- De Morgan, the negation of an implication, the equivalence of an implication with its contrapositive --- is read directly off the table.

I.1 Propositions and truth values

We start at the very beginning. Before connectives, before quantifiers, the atomic object of logic is the proposition: a statement to which one assigns exactly one truth value. The point of this short subsection is to draw a clean line between two things that students sometimes confuse: a proposition (which has a truth value as written) and a predicate (which depends on a free variable and only acquires a truth value once that variable is fixed). The distinction will matter as soon as we start writing $\forall x$ and $\exists x$ in the section on quantifiers.

Definition — Proposition$\virgule$ truth value$\virgule$ predicate

A proposition is a declarative statement to which one can assign exactly one of the two truth values T (true) or F (false). Propositions are denoted by lowercase letters $p, q, r, \dots$. A proposition is never simultaneously T and F; this is the principle of non-contradiction, which we take as a primitive law of mathematical discourse.
A statement that depends on a free variable, e.g. ``$n$ is even'' or ``$f(x) > 0$'', is called a predicate. A predicate has no truth value as such; it acquires one only when the variable is fixed.

Example

Each line below is a proposition with the indicated truth value:

$p$: ``$7$ is a prime number'' --- value T.
$q$: ``$\sqrt{2}$ is a rational number'' --- value F.
$s$: ``$\pi > 3$'' --- value T.
$t$: ``$0 = 1$'' --- value F.

Example

Consider the predicate $r(n) = $ ``$n$ is even''. As written, $r$ has no truth value: $n$ is unspecified. But once we substitute a specific value for $n$, the predicate becomes a proposition:

$r(4)$: ``$4$ is even'' --- value T.
$r(5)$: ``$5$ is even'' --- value F.
$r(0)$: ``$0$ is even'' --- value T.

The same is true of any predicate. The phrase ``$f$ is increasing'' is a predicate of $f$; the phrase ``the function $x \mapsto x^2$ is increasing on $\mathbb{R}_+$'' is a proposition (and its value is T).

Skills to practice

Determining the truth value of a proposition
Distinguishing proposition from predicate

I.2 Negation$\virgule$ conjunction$\virgule$ disjunction

We now build the three simplest connectives: negation (one input), conjunction, and disjunction (two inputs). Each is presented in the same way: a definition by truth table, an example to anchor the intuition, and we move on. The pay-off comes at the end of the subsection: the two De Morgan laws, which describe how negation distributes over the other two connectives. De Morgan is the first theorem of the chapter --- a statement we can prove, simply by inspecting truth tables.

Definition — Negation

The negation of a proposition $p$, denoted $\neg p$ (read ``not $p$''), is the proposition whose truth value is the opposite of that of $p$. Its truth table is:

$p$	$\neg p$
T	F
F	T

Example

Negating an inequality flips it strictly:

negation of ``$x \ge 0$'' is ``$x < 0$'' (not ``$x \le 0$'').
negation of ``$x = 1$'' is ``$x \ne 1$''.
negation of ``$f$ is increasing'' is ``$f$ is not increasing'' --- which is not the same as ``$f$ is decreasing''. A function can be neither.

The third item is the trap: the negation of a property is the absence of that property, not the opposite property.

Definition — Conjunction

The conjunction of two propositions $p$ and $q$, denoted $p \wedge q$ (read ``$p$ and $q$''), is true when both $p$ and $q$ are true, and false otherwise. Its truth table is:

$p$	$q$	$p \wedge q$
T	T	T
T	F	F
F	T	F
F	F	F

Example

For an integer $n$, let $p$: ``$n$ is a multiple of $2$'' and $q$: ``$n$ is a multiple of $3$''. The conjunction $p \wedge q$ is ``$n$ is a multiple of both $2$ and $3$'', which is the same as ``$n$ is a multiple of $6$'': $$ \big( 2 \mid n \big) \wedge \big( 3 \mid n \big) \ \Longleftrightarrow \ 6 \mid n. $$ The conjunction expresses the simultaneity of two constraints; in arithmetic, it is the LCM that captures it.

Definition — Disjunction

The disjunction of two propositions $p$ and $q$, denoted $p \vee q$ (read ``$p$ or $q$''), is true when at least one of $p$ or $q$ is true, and false otherwise. This is the inclusive ``or'': $p$ alone, $q$ alone, or both, are accepted. Its truth table is:

$p$	$q$	$p \vee q$
T	T	T
T	F	T
F	T	T
F	F	F

Example

For a real $x$, the disjunction ``$x \le -1$ or $x \ge 1$'' describes the union of two closed half-lines: $$ \{ x \in \mathbb{R} \mid x \le -1 \vee x \ge 1 \} = \mathbb{R} \setminus \, ]-1, 1[ = ]-\infty, -1] \cup [1, +\infty[. $$ The disjunction expresses the alternative between two cases; in geometry, it is the union of the two regions.

Proposition — De Morgan's laws

For any two propositions $p$ and $q$, the following equivalences hold: $$ \neg (p \wedge q) \ \Longleftrightarrow \ (\neg p) \vee (\neg q) \qquad \neg (p \vee q) \ \Longleftrightarrow \ (\neg p) \wedge (\neg q). $$

Proof

We prove the first equivalence by truth table; the second is obtained the same way.

$p$	$q$	$p \wedge q$	$\neg(p \wedge q)$	$\neg p$	$\neg q$	$\neg p \vee \neg q$
T	T	T	F	F	F	F
T	F	F	T	F	T	T
F	T	F	T	T	F	T
F	F	F	T	T	T	T

The columns $\neg(p \wedge q)$ and $\neg p \vee \neg q$ coincide on every row, so the two propositions have the same truth value in every case: they are equivalent.

Example

The negation of ``$x \le 1$ and $x \ge -1$'' is, by De Morgan, ``$x > 1$ or $x < -1$''. In set terms: the complement of a closed interval is the union of two open exterior rays. $$ \neg \big( -1 \le x \le 1 \big) \ \Longleftrightarrow \ x < -1 \vee x > 1. $$

Skills to practice

Computing the negation of an inequality
Evaluating a compound proposition
Applying De Morgan's laws

I.3 Implication and equivalence

Of all the connectives, the implication is the one most easily mishandled. The point of confusion is the convention that an implication with a false hypothesis is automatically true --- a fact that bumps against everyday intuition (``if pigs fly, then $0 = 1$'': yes, true). The convention exists because we need it: every theorem of the form $\forall x \in E, \mathcal{P}(x) \implies \mathcal{Q}(x)$ would otherwise become false at every $x$ that fails $\mathcal{P}$, and the universal statement would collapse. Once we accept the convention, the truth table is simple: an implication $p \implies q$ fails in exactly one case, namely $p$ true and $q$ false.
The same subsection introduces the equivalence ($p \iff q$, two implications), the contrapositive ($\neg q \implies \neg p$), and the converse ($q \implies p$). The crucial fact, proved as a Proposition below, is that an implication and its contrapositive always have the same truth value --- whereas an implication and its converse, in general, do not. We will exploit this asymmetry every time we choose to prove a statement by contrapositive.

Definition — Implication

The implication from $p$ to $q$, denoted $p \implies q$ (read ``if $p$, then $q$'' or ``$p$ implies $q$''), is the proposition that is false only when $p$ is true and $q$ is false; it is true in every other case. In particular, an implication with a false hypothesis is automatically true. Its truth table:

$p$	$q$	$p \implies q$
T	T	T
T	F	F
F	T	T
F	F	T

Example

The implication ``$0 = 1 \implies 1 = 1 $'' is true. The hypothesis $0 = 1$ is false, so by convention the implication is true regardless of what the conclusion is. This is called a vacuous truth: the implication holds for the trivial reason that there is no instance to check.
The implication ``$0 = 1 \implies 0 = 2$'' is also true, for the same reason. The principle is uncomfortable but unavoidable: from a false hypothesis, anything follows.

Definition — Equivalence$\virgule$ contrapositive$\virgule$ converse

Let $p$ and $q$ be two propositions.

The equivalence of $p$ and $q$, denoted $p \iff q$, is the proposition $(p \implies q) \wedge (q \implies p)$: it is true exactly when $p$ and $q$ have the same truth value.
The contrapositive of $p \implies q$ is the implication $(\neg q) \implies (\neg p)$.
The converse of $p \implies q$ is the implication $q \implies p$.

The truth table of the equivalence is:

$p$	$q$	$p \iff q$
T	T	T
T	F	F
F	T	F
F	F	T

Example

For a fixed real $x$, the implication ``$x = 1 \implies x^2 = 1$'' is true: starting from $x = 1$, we square both sides and get $x^2 = 1$.
Its converse is ``$x^2 = 1 \implies x = 1$''. This is false: for $x = -1$, we have $x^2 = 1$ but $x \ne 1$. The example $x = -1$ is a counterexample to the converse.
This shows that an implication and its converse are independent: knowing one tells us nothing about the other. By contrast, an implication and its contrapositive always agree --- a fact we prove next.

Proposition — Equivalence with the contrapositive

For any propositions $p$ and $q$: $$ \big( p \implies q \big) \ \Longleftrightarrow \ \big( (\neg q) \implies (\neg p) \big). $$ An implication and its contrapositive always have the same truth value. The converse, however, is in general not equivalent to the original implication.

Proof

Truth table:

$p$	$q$	$p \implies q$	$\neg q$	$\neg p$	$\neg q \implies \neg p$
T	T	T	F	F	T
T	F	F	T	F	F
F	T	T	F	T	T
F	F	T	T	T	T

The columns $p \implies q$ and $\neg q \implies \neg p$ coincide on every row.

Proposition — Negation of an implication

For any propositions $p$ and $q$: $$ \neg ( p \implies q ) \ \Longleftrightarrow \ p \wedge (\neg q). $$ The negation of ``if $p$ then $q$'' is ``$p$ and not $q$'' --- the unique configuration in which the implication fails.

Proof

By truth table:

$p$	$q$	$p \implies q$	$\neg(p \implies q)$	$\neg q$	$p \wedge \neg q$
T	T	T	F	F	F
T	F	F	T	T	T
F	T	T	F	F	F
F	F	T	F	T	F

The columns $\neg(p \implies q)$ and $p \wedge \neg q$ coincide.

Example

The implication ``if it is raining, then the ground is wet'' is, for instance, false on a day when it rains but the ground is sheltered (rains and not wet). It is, on the other hand, true on a sunny day with a wet lawn just watered: the hypothesis ``it is raining'' being false, the implication is automatically true.

Skills to practice

Determining the truth value of an implication
Writing the contrapositive and the converse
Negating an implication

II Tautologies and Logical Equivalences

With the connectives and their basic properties in hand, we can climb one level of abstraction. A formula built from propositional variables and connectives is a tautology when it is true regardless of the truth values assigned to its variables. Tautologies are the laws of logic; they capture exactly the manipulations one is allowed to perform on propositions without ever risking a falsehood.
This section has three parts. We define what a tautology is and verify the most famous one (the law of excluded middle, $p \vee \neg p$). We then collect the four other tautologies that we will use most frequently in the year ahead. We close with the standard mathematical vocabulary --- necessary and sufficient conditions --- which is essentially a re-reading of the implication and its contrapositive in human-friendly language.

II.1 Tautologies

A tautology is a propositional formula that is true on every line of its truth table. The simplest non-trivial example is $p \vee \neg p$ --- between $p$ and its negation, one of the two must be T. The opposite of a tautology is an antilogy: a formula that is false on every line. The simplest example is $p \wedge \neg p$, false everywhere because $p$ cannot simultaneously be T and F. These two formulas are the boundary markers of propositional logic: in between live all the formulas whose truth value depends on the input variables.

Definition — Tautology$\virgule$ antilogy$\virgule$ logical equivalence

A tautology is a propositional formula that takes the value T on every line of its truth table --- that is, regardless of the truth values of its propositional variables. An antilogy is a formula that takes the value F on every line.
Two formulas $A$ and $B$ are said to be logically equivalent when $A \iff B$ is a tautology. Equivalently, $A$ and $B$ have the same truth value on every line.

Example

The formula $p \vee \neg p$ is the famous law of excluded middle: every proposition is either true or false, no third option. The formula $p \wedge \neg p$ is a contradiction (always false); its negation $\neg(p \wedge \neg p)$ is the principle of non-contradiction (always true). Truth table for both:

$p$	$\neg p$	$p \vee \neg p$	$p \wedge \neg p$
T	F	T	F
F	T	T	F

Example

A non-trivial tautology that we will revisit in the next subsection: $\big( (p \implies q) \wedge p \big) \implies q$. Truth table:

$p$	$q$	$p \implies q$	$(p \implies q) \wedge p$	$\big((p\implies q) \wedge p\big) \implies q$
T	T	T	T	T
T	F	F	F	T
F	T	T	F	T
F	F	T	F	T

The last column is T everywhere, so the formula is a tautology --- this is modus ponens. By contrast, the formula $p \implies q$ is not a tautology (it is F on row 2): its truth depends on $p$ and $q$.

Skills to practice

Verifying a tautology by truth table

II.2 Classical tautologies

We collect here the four tautologies one will use most frequently throughout the year, in addition to the two De Morgan laws and the equivalence with the contrapositive that we already proved in the previous section on connectives. Each is stated as a Proposition and accompanied by a short truth-table proof. The point of giving them their own names is twofold: it lets us cite the result later by name (``by transitivity of $\implies$, $\dots$'') rather than re-proving it each time, and it disciplines us into recognizing that each step of a proof corresponds to applying some tautology.

Proposition — Double negation

For any proposition $p$: $$ \neg(\neg p) \ \Longleftrightarrow \ p. $$

Proof

$p$	$\neg p$	$\neg(\neg p)$
T	F	T
F	T	F

The first and third columns coincide.

Proposition — Modus ponens

For any propositions $p$ and $q$: $$ \big( p \wedge (p \implies q) \big) \implies q $$ is a tautology. In words: from $p$ and $p \implies q$ one may deduce $q$. This is the rule that licenses the word ``therefore'' in a written proof.

Proof

$p$	$q$	$p \implies q$	$p \wedge (p \implies q)$	$\big( p \wedge (p \implies q) \big) \implies q$
T	T	T	T	T
T	F	F	F	T
F	T	T	F	T
F	F	T	F	T

The last column is T everywhere.

Example

A concrete application. Take $p$: ``$n$ is a multiple of $4$'' and $q$: ``$n$ is a multiple of $2$''. We know $p \implies q$ (every multiple of $4$ is a multiple of $2$). For $n = 12$, the proposition $p$ holds. Modus ponens gives $q$: $12$ is a multiple of $2$. The whole inference fits in one line: $12$ is a multiple of $4$, hence a multiple of $2$.
The word hence is precisely the modus ponens being applied. In a written proof, every ``therefore'', ``thus'', ``consequently'' corresponds to a (silent) application of modus ponens.

Proposition — Transitivity of implication

For any propositions $p$, $q$, $r$: $$ \big( (p \implies q) \wedge (q \implies r) \big) \implies (p \implies r) $$ is a tautology. This is the rule one invokes implicitly every time one chains two implications.

Proof

A truth table on $(p, q, r)$ has $2^3 = 8$ rows. We compute the column $H = (p \implies q) \wedge (q \implies r)$ then the column $H \implies (p \implies r)$:

$p$	$q$	$r$	$p \implies q$	$q \implies r$	$H$	$p \implies r$	$H \implies (p \implies r)$
T	T	T	T	T	T	T	T
T	T	F	T	F	F	F	T
T	F	T	F	T	F	T	T
T	F	F	F	T	F	F	T
F	T	T	T	T	T	T	T
F	T	F	T	F	F	T	T
F	F	T	T	T	T	T	T
F	F	F	T	T	T	T	T

The last column is T on every row.

Example

A typical chain of implications: $$ \begin{aligned} n \in 12 \mathbb{Z} &\implies n \in 6 \mathbb{Z} && \text{(every multiple of 12 is a multiple of 6)} \\ n \in 6 \mathbb{Z} &\implies n \in 2 \mathbb{Z} && \text{(every multiple of 6 is even)}. \end{aligned} $$ By transitivity of $\implies$: $$ n \in 12 \mathbb{Z} \implies n \in 2 \mathbb{Z}. $$ The chain reasoning is so natural that we use it without naming it; the Proposition above is what makes it valid.

Proposition — Distributivity of $\wedge$ and $\vee$

For any propositions $p$, $q$, $r$: $$ p \wedge (q \vee r) \ \Longleftrightarrow \ (p \wedge q) \vee (p \wedge r) \qquad p \vee (q \wedge r) \ \Longleftrightarrow \ (p \vee q) \wedge (p \vee r). $$

Proof

We prove the first equivalence; the second is dual. We compare the columns $p \wedge (q \vee r)$ and $(p \wedge q) \vee (p \wedge r)$ over the eight rows on $(p, q, r)$:

$p$	$q$	$r$	$q \vee r$	$p \wedge (q \vee r)$	$p \wedge q$	$p \wedge r$	$(p \wedge q) \vee (p \wedge r)$
T	T	T	T	T	T	T	T
T	T	F	T	T	T	F	T
T	F	T	T	T	F	T	T
T	F	F	F	F	F	F	F
F	T	T	T	F	F	F	F
F	T	F	T	F	F	F	F
F	F	T	T	F	F	F	F
F	F	F	F	F	F	F	F

The columns $p \wedge (q \vee r)$ and $(p \wedge q) \vee (p \wedge r)$ coincide.

Skills to practice

Applying modus ponens
Chaining implications by transitivity

II.3 Necessary and sufficient conditions

The vocabulary of necessary and sufficient conditions is, formally, just a re-reading of the implication. But it is the vocabulary in which most theorems of the year will be stated --- ``necessary and sufficient'', ``it is necessary that'', ``it is sufficient that'' --- and learning to translate it instantly into implications saves time and avoids errors. A sufficient condition corresponds to an implication; a necessary condition corresponds to the converse implication. The contrapositive is equivalent to the original implication, but the converse is not in general.

Definition — Necessary$\virgule$ sufficient$\virgule$ necessary and sufficient

Let $p$ and $q$ be two propositions.

$p$ is a sufficient condition (SC) for $q$ when $p \implies q$ is true: ``it is enough that $p$ for $q$''.
$p$ is a necessary condition (NC) for $q$ when $q \implies p$ is true: ``it is necessary that $p$ for $q$''. Equivalently (by contrapositive), $\neg p \implies \neg q$: without $p$, no $q$.
$p$ is a necessary and sufficient condition (NSC) for $q$ when $p \iff q$ is true.

Saying ``$p$ is necessary for $q$'' corresponds to $q \implies p$. Saying ``$p$ is sufficient for $q$'' corresponds to $p \implies q$. The phrase ``$p$ if and only if $q$'' is exactly the equivalence $p \iff q$.

Example

For an integer $n$:

``$n$ is divisible by $4$'' is a sufficient condition for ``$n$ is divisible by $2$'': $4 \mid n \implies 2 \mid n$.
``$n$ is divisible by $2$'' is a necessary condition for ``$n$ is divisible by $4$'': $4 \mid n \implies 2 \mid n$, contrapositively ``if $n$ is odd, then $n$ is not divisible by $4$''.
``$n$ is divisible by $6$'' is a necessary and sufficient condition for ``$n$ is divisible by both $2$ and $3$''.

Example

The vocabulary on a non-mathematical example. To register to vote in France, two conditions must be met: be a French citizen, and be at least 18 years old.

``Being a French citizen'' is necessary (NC) but not sufficient (SC) to vote: a 16-year-old French citizen cannot vote.
``Being at least 18'' is necessary but not sufficient: a 25-year-old foreigner cannot vote.
``Being a French citizen and at least 18'' is necessary and sufficient (NSC).

The trap is to confuse ``sufficient'' with ``necessary''. In mathematics, the two go in opposite directions and getting them backwards turns a true theorem into a false statement.

Skills to practice

Identifying necessary and sufficient conditions
Translating necessary and sufficient conditions into implications

III Quantifiers

A predicate is a statement depending on a free variable; it acquires a truth value once the variable is fixed. Quantifiers turn a predicate into a proposition by ranging over a set: ``for every $x$ in $E$, $\mathcal{P}(x)$'', ``there exists $x$ in $E$ such that $\mathcal{P}(x)$''. The two quantifiers $\forall$ and $\exists$, together with their negation rules, are the second pillar of the chapter --- and the source of the most common student mistakes.
The mistakes come, as a rule, from one of three places: confusing $\forall$ with $\exists$ when negating; confusing $\exists$ with $\exists !$; or swapping the order of two quantifiers. We address each in turn: a first subsection introduces the three quantifiers, a second states the negation rule as a Proposition, and a third explains why the order matters.

III.1 Universal and existential quantifiers

The universal quantifier $\forall$ asserts that every element of a set satisfies a predicate; the existential quantifier $\exists$ asserts that at least one does. A third quantifier $\exists !$ asserts that exactly one does --- a strictly stronger statement than $\exists$. We list all three in one definition, with their reading conventions, and accompany them with examples that emphasise the gap between the three.

Definition — Universal$\virgule$ existential$\virgule$ unique

Let $E$ be a set and $\mathcal{P}(x)$ a predicate of a variable $x \in E$.

$\forall x \in E, \mathcal{P}(x)$ is the proposition ``for every $x \in E$, $\mathcal{P}(x)$ is true''. It is T exactly when every element of $E$ satisfies $\mathcal{P}$.
$\exists x \in E, \mathcal{P}(x)$ is the proposition ``there exists $x \in E$ such that $\mathcal{P}(x)$ is true''. It is T exactly when at least one element of $E$ satisfies $\mathcal{P}$.
$\exists ! x \in E, \mathcal{P}(x)$ is the proposition ``there exists a unique $x \in E$ such that $\mathcal{P}(x)$ is true''. It is T exactly when one and only one element of $E$ satisfies $\mathcal{P}$.

The symbols $\forall$ and $\exists$ belong to the formal language. They are not typographical abbreviations: do not write ``$\forall$ integer $n$'' in prose; write ``for every integer $n$''.

Example

Three propositions about real numbers, all true, that illustrate the gap $\forall$ / $\exists$ / $\exists !$:

$\forall x \in \mathbb{R}, x^2 \ge 0$. Every real has a non-negative square.
$\exists x \in \mathbb{R}, x^2 = 2$. At least one real squares to $2$ (in fact two: $\sqrt{2}$ and $-\sqrt{2}$).
$\exists ! x \in \mathbb{R}_+, x^2 = 2$. In the non-negative reals, only $\sqrt{2}$ squares to $2$ --- exactly one solution. The restriction to $\mathbb{R}_+$ is what turns ``at least one'' into ``exactly one''.

The last bullet shows the typical use of $\exists !$: pin down the unique representative of a class by a constraint (here, non-negativity).

Skills to practice

Translating a statement with quantifiers
Translating function properties with quantifiers

III.2 Negation of quantifiers

Proposition — Negation of quantifiers

For any set $E$ and any predicate $\mathcal{P}(x)$ on $E$: $$ \neg \big( \forall x \in E, \mathcal{P}(x) \big) \ \Longleftrightarrow \ \exists x \in E, \neg \mathcal{P}(x) $$ $$ \neg \big( \exists x \in E, \mathcal{P}(x) \big) \ \Longleftrightarrow \ \forall x \in E, \neg \mathcal{P}(x). $$

Proof

We prove the first equivalence; the second follows by applying the first to $\neg \mathcal{P}$ and using the double negation.
The proposition $\forall x \in E, \mathcal{P}(x)$ is V iff every element of $E$ satisfies $\mathcal{P}$, that is iff no element of $E$ falsifies $\mathcal{P}$. Its negation is therefore V iff at least one element of $E$ falsifies $\mathcal{P}$, that is V iff $\exists x \in E, \neg \mathcal{P}(x)$.

Example

The negation of ``$\forall n \in \mathbb{N}, n^2 \ge n$'' is ``$\exists n \in \mathbb{N}, n^2 < n$''. To refute the universal statement it suffices to exhibit one counterexample. Here, no counterexample exists (the statement is true), so the negation is false.
The negation of ``$\exists x \in \mathbb{R}, x^2 < 0$'' is ``$\forall x \in \mathbb{R}, x^2 \ge 0$''. The negation is true (a square is always non-negative), so the original existential statement is false.

Example

A more delicate example, the negation of the definition of convergence of a sequence. The statement ``the sequence $(u_n)$ converges to $\ell$'' is, formally: $$ \forall \varepsilon > 0, \exists N \in \mathbb{N}, \forall n \ge N, |u_n - \ell| < \varepsilon. $$ Negating it, we flip every $\forall$ to $\exists$ (and vice versa) and negate the innermost predicate: $$ \exists \varepsilon > 0, \forall N \in \mathbb{N}, \exists n \ge N, |u_n - \ell| \ge \varepsilon. $$ Read aloud: ``there exists an $\varepsilon > 0$ such that for every $N$, one can find $n \ge N$ with $|u_n - \ell| \ge \varepsilon$'' --- the sequence stays away from $\ell$ by at least $\varepsilon$ infinitely often.
This formal manipulation is the bread and butter of analysis: we will redo it many times in the chapter on sequences. Make sure now that the rule felt mechanical: scan left to right, flip every quantifier, negate the predicate at the end.

Skills to practice

Negating a universal or existential statement
Negating nested quantifiers
Distinguishing quantifier scope from disjunction

III.3 Combining quantifiers

Two consecutive quantifiers of the same type can be exchanged freely: $\forall x, \forall y$ is the same as $\forall y, \forall x$, and similarly for $\exists$. Two quantifiers of different types cannot. The implication $$ \big( \exists y, \forall x, \mathcal{P}(x, y) \big) \implies \big( \forall x, \exists y, \mathcal{P}(x, y) \big) $$ is always true (the same $y$ that works for all $x$ in the antecedent works for each $x$ in the consequent). The converse is in general false: in $\forall x, \exists y$, the chosen $y$ may depend on $x$, whereas in $\exists y, \forall x$ the same $y$ must work for every $x$. The asymmetry is at the heart of every nuance in analysis (uniform vs. pointwise convergence, uniform vs. pointwise continuity, $\dots$).

Example

Consider the predicate $\mathcal{P}(x, y) = $ ``$y > x$'' on $\mathbb{R}^2$.

$\forall x \in \mathbb{R}, \exists y \in \mathbb{R}, y > x$ is true: for each $x$, take $y = x + 1$. The choice of $y$ depends on $x$.
$\exists y \in \mathbb{R}, \forall x \in \mathbb{R}, y > x$ is false: no real number is greater than every real number.

This shows that $\forall \exists$ is strictly weaker than $\exists \forall$.

Skills to practice

Distinguishing $\forall \exists$ from $\exists \forall$
Comparing $\forall \exists$ and $\exists \forall$ on a finite set

IV Methods of Reasoning

The four classical methods of reasoning --- case analysis, contrapositive, contradiction, analysis--synthesis --- are not magic recipes. The first three are direct consequences of the law of excluded middle together with the tautologies of section~2. The fourth, analysis--synthesis, is a systematic method to determine the set of solutions of a problem, separated into a phase that restricts the candidates (analysis) and a phase that confirms which ones are genuine (synthesis).

IV.1 The law of excluded middle

Axiom of excluded middle

We adopt as an axiom of classical logic the law of excluded middle: for every proposition $p$, the proposition $p \vee \neg p$ is true. Equivalently, every proposition is either true or false --- there is no third option (tertium non datur). This axiom is the foundation that licenses the three reasoning modes of the next subsections: disjunction of cases, contrapositive, and contradiction. The fourth mode, analysis--synthesis, does not depend on it.

Skills to practice

Identifying uses of the law of excluded middle

IV.2 Case analysis

Principle. To prove a proposition $r$, suppose that the situation can be partitioned into a finite number of cases $p_1, \dots, p_n$ such that $p_1 \vee \dots \vee p_n$ is true. If under each $p_i$ we can deduce $r$, then $r$ is true. The simplest instance --- and the most frequent one --- comes from the law of excluded middle itself: take $p_1 = p$ and $p_2 = \neg p$.
The proof is rendered in writing as: ``We distinguish $n$ cases. Case 1: $p_1$. Then \dots, hence $r$. Case 2: $p_2$. Then \dots, hence $r$. (\dots) In every case, $r$.''

Example

Show that for every $n \in \mathbb{N}$, the integer $n(n+1)$ is even.

Answer

Let $n \in \mathbb{N}$. By excluded middle, $n$ is even or $n$ is odd.

Case 1: $n$ is even. Write $n = 2k$ with $k \in \mathbb{N}$. Then $n(n+1) = 2k(n+1)$, which is even.
Case 2: $n$ is odd. Then $n+1$ is even, so $n(n+1)$ is even.

In every case, $n(n+1)$ is even.

Example

The absolute value $|x| = \max(x, -x)$ is defined by case analysis on the sign of $x$. Show that $\forall x \in \mathbb{R}, |x| \ge 0$.

Answer

Let $x \in \mathbb{R}$. By excluded middle, $x \ge 0$ or $x < 0$.

Case 1: $x \ge 0$. Then $|x| = x \ge 0$.
Case 2: $x < 0$. Then $|x| = -x > 0 \ge 0$.

In every case, $|x| \ge 0$.
The case-analysis structure exactly mirrors the piecewise definition of $|x|$. Whenever an object is defined by cases, a proof about it will typically also proceed by cases.

Skills to practice

Proving by case analysis

IV.3 Contrapositive

Principle. To prove an implication $p \implies q$, prove its contrapositive $\neg q \implies \neg p$ instead. By the equivalence with the contrapositive (Proposition of section~1.3), the two implications are equivalent. Use this when the negation of $q$ has a more workable algebraic form than $q$ itself.
The proof is rendered in writing as: ``By contrapositive, suppose $\neg q$. Let us show $\neg p$.''

Example

Show that for every $n \in \mathbb{N}$, if $n^2$ is even, then $n$ is even.

Answer

Let $n \in \mathbb{N}$. We prove the contrapositive: suppose $n$ is odd. Show that $n^2$ is odd.
Write $n = 2k + 1$ with $k \in \mathbb{N}$. Then: $$ \begin{aligned} n^2 &= (2k + 1)^2 && \text{(squaring)} \\ &= 4 k^2 + 4 k + 1 && \text{(expanding)} \\ &= 2 (2 k^2 + 2 k) + 1 && \text{(factoring out 2)}. \end{aligned} $$ Setting $k' = 2 k^2 + 2 k \in \mathbb{N}$, we get $n^2 = 2 k' + 1$, which is odd.

Skills to practice

Proving by contrapositive

IV.4 Contradiction

Principle. A contradiction is any proposition of the form $r \wedge \neg r$ --- always false by the principle of non-contradiction. To prove $p$ by contradiction, suppose $\neg p$ and derive a contradiction; by the law of excluded middle, $p$ must hold. Use this when assuming $\neg p$ gives algebraic information that the truth of $p$ would not have given.
The proof is rendered in writing as: ``Suppose, for contradiction, that $\neg p$. \dots [deductions leading to a contradiction]. Contradiction. Hence $p$.''

Example

Show that for every $n \in \mathbb{N}$, $\sqrt{n^2 + 2}$ is not an integer.

Answer

Let $n \in \mathbb{N}$.
Suppose, for contradiction, that $\sqrt{n^2 + 2}$ is an integer; call it $p$.
Then: $$ \begin{aligned} p^2 &= n^2 + 2 && \text{(squaring)} \\ p^2 - n^2 &= 2 && \text{(rearranging)} \\ (p - n)(p + n) &= 2 && \text{(difference of squares)}. \end{aligned} $$ Since $p \ge 0$ and $p^2 > n^2$, we have $p > n \ge 0$.
So $p - n \ge 1$ and $p + n \ge p - n \ge 1$ are both natural numbers.
The only factorisation of $2$ in $\mathbb{N}^*$ is $2 \cdot 1$, hence $p - n = 1$ and $p + n = 2$.
Adding the two equations: $2p = 3$, so $p = \tfrac{3}{2}$ --- contradiction with $p \in \mathbb{N}$.
Hence $\sqrt{n^2 + 2}$ is not an integer.

Skills to practice

Proving by contradiction
Bounding by contradiction

IV.5 Analysis--synthesis

Method — Analysis--synthesis

To determine the set of objects $x$ in a set $E$ that satisfy a property $\mathcal{P}$, proceed in two phases:

Analysis. Suppose $x \in E$ satisfies $\mathcal{P}$. Deduce as much as possible about $x$, narrowing the candidates to a small explicit list. Analysis answers: what does $x$ look like, if it exists? It establishes uniqueness (or at least restricts the candidates).
Synthesis. For each candidate produced by the analysis, check whether it actually belongs to $E$ and satisfies $\mathcal{P}$. Synthesis answers: which of the candidates are genuine solutions? It establishes existence.

The two phases together describe all solutions: the analysis bounds the search; the synthesis confirms which candidates work.
Slogan. Analysis = restriction of candidates; synthesis = verification / existence.

Example

A first, very simple example: determine all $x \in \mathbb{R}$ such that $x^2 = x$.

Answer

Analysis. Let $x \in \mathbb{R}$ satisfy $x^2 = x$. Then: $$ \begin{aligned} x^2 - x &= 0 && \text{(rearranging)} \\ x (x - 1) &= 0 && \text{(factoring)} \\ x = 0 \ \text{or}\ x &= 1 && \text{(zero-product property in $\mathbb{R}$)}. \end{aligned} $$ The candidates are $\{0, 1\}$.
Synthesis. For $x = 0$: $x^2 = 0 = x$, OK. For $x = 1$: $x^2 = 1 = x$, OK. Both candidates are solutions.
Conclusion. The set of solutions is $\{0, 1\}$.

The whole structure --- analysis narrows to two candidates, synthesis confirms both --- is the canonical pattern.

Example

A richer example, showing that the analysis can leave many candidates and the synthesis has to validate each one. Determine all functions $f \colon \mathbb{R} \to \mathbb{R}$ such that for every $x \in \mathbb{R}$, $f(x) + f(-x) = 0$ and $f(1) = 3$.

Answer

Analysis. Let $f$ be a solution.
The condition imposes $f(-x) = -f(x)$ for every $x$: $f$ is odd.
Setting $x = 0$ gives $2 f(0) = 0$, hence $f(0) = 0$.
The hypothesis $f(1) = 3$ then forces $f(-1) = -3$.
The constraints thus fix $f$ on $\{-1, 0, 1\}$, but leave free the choice of values on a representative of each pair $\{x, -x\}$ with $x \notin \{-1, 0, 1\}$.
Any odd function with $f(1) = 3$ is therefore a candidate.
Synthesis. Take any odd function $f \colon \mathbb{R} \to \mathbb{R}$ with $f(1) = 3$, for example $f(x) = 3x$ or $f(x) = 3 \sin\!\big(\tfrac{\pi x}{2}\big)$.
For every $x$, $f(-x) = -f(x)$, so $f(x) + f(-x) = 0$.
And $f(1) = 3$ by hypothesis.
Each such $f$ is therefore a solution.
Conclusion. The set of solutions is the set of odd functions $f \colon \mathbb{R} \to \mathbb{R}$ such that $f(1) = 3$ --- there are infinitely many.

Compare with the previous example: there, the analysis pinned down two candidates and synthesis kept both. Here, the analysis pins down a whole family. The synthesis must therefore confirm the entire family, not just check two cases.

Skills to practice

Solving by analysis--synthesis

V Mathematical Induction

Mathematical induction is the standard tool to prove statements of the form $\forall n \in \mathbb{N}, \mathcal{P}_n$. Three flavours are commonly distinguished --- simple, double, strong --- chosen according to which previous ranks the heredity step needs to invoke. We state each as a Theorem and accompany it with a writing template plus an example. The three theorems look similar but differ in their initialization and heredity hypotheses; reading them side by side highlights what each variant lets you assume.

V.1 Simple induction

Theorem — Simple induction

Let $A$ be a subset of $\mathbb{N}$. If $$ 0 \in A \quad \ \text{and}\ \quad \forall n \in \mathbb{N}, \big( n \in A \implies n+1 \in A \big) $$ then $A = \mathbb{N}$. Equivalently: for any predicate $\mathcal{P}$ on $\mathbb{N}$, if $\mathcal{P}_0$ holds and $\mathcal{P}_n \implies \mathcal{P}_{n+1}$ for every $n \in \mathbb{N}$, then $\mathcal{P}_n$ holds for every $n \in \mathbb{N}$.

Method — Writing a simple induction

A simple induction proof is structured as:

Initialization: verify $\mathcal{P}_0$.
Heredity: let $n \in \mathbb{N}$; suppose $\mathcal{P}_n$; show $\mathcal{P}_{n+1}$.
Conclusion: by induction, $\forall n \in \mathbb{N}, \mathcal{P}_n$.

Two errors to avoid. Do not write ``suppose $\mathcal{P}_n$ for every $n \in \mathbb{N}$'': that would assume what is to be proved. Do not write ``suppose $\mathcal{P}_n$ for some $n \in \mathbb{N}$'': heredity must be proved for every $n$, the variable being introduced at the start of the step.

Example

The classical Gauss formula: $\forall n \in \mathbb{N}, \displaystyle \sum_{k=0}^{n} k = \frac{n(n+1)}{2}$.

Answer

Let $\mathcal{P}_n$ be ``$\displaystyle \sum_{k=0}^{n} k = \frac{n(n+1)}{2}$''.

Initialization. For $n = 0$: $\sum_{k=0}^{0} k = 0 = \tfrac{0 \cdot 1}{2}$. So $\mathcal{P}_0$.
Heredity. Let $n \in \mathbb{N}$, suppose $\mathcal{P}_n$. Then: $$ \begin{aligned} \sum_{k=0}^{n+1} k &= \sum_{k=0}^{n} k + (n+1) && \text{(splitting off the last term)} \\ &= \frac{n(n+1)}{2} + (n+1) && \text{(by } \mathcal{P}_n \text{)} \\ &= (n+1) \cdot \frac{n + 2}{2} && \text{(factoring out $n+1$)} \\ &= \frac{(n+1)(n+2)}{2}. \end{aligned} $$ Hence $\mathcal{P}_{n+1}$.
Conclusion. By induction, $\mathcal{P}_n$ holds for every $n \in \mathbb{N}$.

Example

A bound on a recursively-defined sequence. Let $(u_n)_{n \in \mathbb{N}}$ be defined by $u_0 = 1$ and $u_{n+1} = 1 + \dfrac{u_n}{n+1}$. Show that $\forall n \in \mathbb{N}, u_n \le 2$.

Answer

Let $\mathcal{P}_n$ be ``$u_n \le 2$''.

Initialization. $u_0 = 1 \le 2$. So $\mathcal{P}_0$.
Heredity. Let $n \in \mathbb{N}$, suppose $u_n \le 2$. Then: $$ \begin{aligned} u_{n+1} &= 1 + \frac{u_n}{n+1} && \text{(definition)} \\ &\le 1 + \frac{2}{n+1} && \text{(by } u_n \le 2 \text{)}. \end{aligned} $$ We split on $n$:
- if $n = 0$, $u_1 = 1 + u_0 = 2$;
- if $n \ge 1$, $\dfrac{2}{n+1} \le 1$, so $u_{n+1} \le 2$.
In every case $u_{n+1} \le 2$.
Conclusion. By induction, $\forall n \in \mathbb{N}, u_n \le 2$.

Skills to practice

Proving an identity by induction
Proving a bound by induction

V.2 Double induction

Theorem — Double induction

Let $A$ be a subset of $\mathbb{N}$. If $$ \{0, 1\} \subset A \quad \ \text{and}\ \quad \forall n \in \mathbb{N}, \big( (n \in A \wedge n+1 \in A) \implies n+2 \in A \big) $$ then $A = \mathbb{N}$.

Method — Writing a double induction

Use double induction when computing $\mathcal{P}_{n+2}$ requires both $\mathcal{P}_n$ and $\mathcal{P}_{n+1}$ --- typically for linear recurrences of order $2$.

Initialization: verify $\mathcal{P}_0$ and $\mathcal{P}_1$.
Heredity: let $n \in \mathbb{N}$; suppose $\mathcal{P}_n$ and $\mathcal{P}_{n+1}$; show $\mathcal{P}_{n+2}$.

Example

Let $(u_n)_{n \in \mathbb{N}}$ be defined by $u_0 = 4$, $u_1 = 5$, and $u_{n+2} = 3 u_{n+1} - 2 u_n$. Show that $\forall n \in \mathbb{N}, u_n = 2^n + 3$.

Answer

Let $\mathcal{P}_n$ be ``$u_n = 2^n + 3$''.

Initialization. $u_0 = 4 = 2^0 + 3$ and $u_1 = 5 = 2^1 + 3$.
Heredity. Let $n \in \mathbb{N}$, suppose $\mathcal{P}_n$ and $\mathcal{P}_{n+1}$. Then: $$ \begin{aligned} u_{n+2} &= 3 u_{n+1} - 2 u_n && \text{(definition)} \\ &= 3 (2^{n+1} + 3) - 2 (2^n + 3) && \text{(by } \mathcal{P}_{n+1}, \mathcal{P}_n \text{)} \\ &= (3 \cdot 2 - 2) \cdot 2^n + (9 - 6) && \text{(grouping)} \\ &= 4 \cdot 2^n + 3 && \text{(arithmetic)} \\ &= 2^{n+2} + 3. \end{aligned} $$ Hence $\mathcal{P}_{n+2}$.
Conclusion. By double induction, $\forall n \in \mathbb{N}, u_n = 2^n + 3$.

Skills to practice

Proving an explicit form for an order-2 recurrence

V.3 Strong induction

Theorem — Strong induction

Let $A$ be a subset of $\mathbb{N}$. If $$ 0 \in A \quad \ \text{and}\ \quad \forall n \in \mathbb{N}, \big( \{0, 1, \dots, n\} \subset A \implies n+1 \in A \big) $$ then $A = \mathbb{N}$.

Method — Writing a strong induction

Use strong induction when establishing $\mathcal{P}_{n+1}$ requires all previous ranks $\mathcal{P}_0, \dots, \mathcal{P}_n$, not just $\mathcal{P}_n$ alone.

Initialization: verify $\mathcal{P}_0$.
Heredity: let $n \in \mathbb{N}$; suppose $\mathcal{P}_k$ for every $k \in \{0, 1, \dots, n\}$; show $\mathcal{P}_{n+1}$.

Despite its name, strong induction is logically equivalent to simple induction (apply simple induction to $\mathcal{Q}_n = $ ``$\mathcal{P}_k$ for every $k \in \{0, \dots, n\}$''). The interest is purely tactical.

Example

Let $(v_n)_{n \in \mathbb{N}}$ be a real sequence such that $v_0 \ge 0$ and $v_{n+1} \le \displaystyle \sum_{k=0}^{n} v_k$ for every $n \in \mathbb{N}$. Show that $\forall n \in \mathbb{N}, v_n \le 2^n v_0$.

Answer

Let $\mathcal{P}_n$ be ``$v_n \le 2^n v_0$''.

Initialization. $v_0 = 2^0 v_0$, so $\mathcal{P}_0$ holds.
Heredity. Let $n \in \mathbb{N}$, suppose $\mathcal{P}_k$ for every $k \in \{0, \dots, n\}$. Then: $$ \begin{aligned} v_{n+1} &\le \sum_{k=0}^{n} v_k && \text{(hypothesis on } (v_n) \text{)} \\ &\le \sum_{k=0}^{n} 2^k v_0 && \text{(by } \mathcal{P}_k \text{ for each } k \text{)} \\ &= (2^{n+1} - 1) v_0 && \text{(geometric sum)} \\ &\le 2^{n+1} v_0 && \text{(since } v_0 \ge 0 \text{)}. \end{aligned} $$ Hence $\mathcal{P}_{n+1}$.
Conclusion. By strong induction, $\forall n \in \mathbb{N}, v_n \le 2^n v_0$.

Skills to practice

Proving a property by strong induction
Decomposing $n$ as $3a + 5b$

VI Going further

Skills to practice

Quiz

Jump to section

\(p\)	\(q\)	\(p \wedge q\)	\(\neg(p \wedge q)\)	\(\neg p\)	\(\neg q\)	\(\neg p \vee \neg q\)
T	T	T	F	F	F	F
T	F	F	T	F	T	T
F	T	F	T	T	F	T
F	F	F	T	T	T	T

\(p\)	\(q\)	\(p \implies q\)	\(\neg q\)	\(\neg p\)	\(\neg q \implies \neg p\)
T	T	T	F	F	T
T	F	F	T	F	F
F	T	T	F	T	T
F	F	T	T	T	T

\(p\)	\(q\)	\(p \implies q\)	\(\neg(p \implies q)\)	\(\neg q\)	\(p \wedge \neg q\)
T	T	T	F	F	F
T	F	F	T	T	T
F	T	T	F	F	F
F	F	T	F	T	F

\(p\)	\(\neg p\)	\(p \vee \neg p\)	\(p \wedge \neg p\)
T	F	T	F
F	T	T	F

\(p\)	\(q\)	\(p \implies q\)	\((p \implies q) \wedge p\)	\(\big((p\implies q) \wedge p\big) \implies q\)
T	T	T	T	T
T	F	F	F	T
F	T	T	F	T
F	F	T	F	T

\(p\)	\(q\)	\(r\)	\(p \implies q\)	\(q \implies r\)	\(H\)	\(p \implies r\)	\(H \implies (p \implies r)\)
T	T	T	T	T	T	T	T
T	T	F	T	F	F	F	T
T	F	T	F	T	F	T	T
T	F	F	F	T	F	F	T
F	T	T	T	T	T	T	T
F	T	F	T	F	F	T	T
F	F	T	T	T	T	T	T
F	F	F	T	T	T	T	T