Introduction to Pure Mathematics — implication, proof and light switches

The statement we are proving

Every theorem in mathematics has the shape

\[ P \;\Longrightarrow\; Q, \]

read “$P$ implies $Q$”, or “if $P$ then $Q$”. Here $P$ and $Q$ are statements: each is either true or false, with nothing in between. $P$ is called the hypothesis, and you will also see it called the assumption, the premise or the antecedent. All four name the same thing, the statement you are given. $Q$ is the conclusion, also called the consequent: the statement you are to reach.

It is worth being clear from the start about what $P \Rightarrow Q$ does not claim. It does not claim that $P$ is true. It does not claim that $Q$ is true. It claims only that $Q$ cannot fail while $P$ holds. A true implication with a false hypothesis tells you nothing at all about the world.

Let us look at a bigger truth table below. Note that in mathematics and and or are sometimes denoted by $\wedge$ and $\vee$: $P \wedge Q$ means “$P$ and $Q$”, and $P \vee Q$ means “$P$ or $Q$”. Notice the similarity with $\cap$ and $\cup$.

	$P$	$Q$	$\neg P$	$P \vee Q$	$P \wedge Q$	$P \Rightarrow Q$
1	T	T	F	T	T	T
2	T	F	F	T	F	F
3	F	T	T	T	F	T
4	F	F	T	F	F	T

Each column has a picture below: think of $P$ as $x \in A$ and $Q$ as $x \in B$.

Not $P$. It ignores $Q$ entirely and simply turns the $P$ column over, so only $A$ is worth drawing. The statement is the shaded region outside it, the complement $A^{c}$.

Reading the $\neg P$ column row by row

$P$ holds, so $\neg P$ fails.
$P$ holds again, so $\neg P$ fails again.
$P$ fails, so $\neg P$ holds.
$P$ fails again, so $\neg P$ holds. Only the $P$ column was ever consulted: negation does not look at $Q$ at all.

$P$ or $Q$. True when at least one of them holds, and false only when both fail. The mathematical or is inclusive: both are allowed to hold at once. In the picture it is $A$ together with $B$.

Reading the $P \vee Q$ column row by row

Both hold, which is more than enough. An or does not object to both being true.
$P$ holds, and one of them is enough.
$Q$ holds, and again one is enough.
Neither holds, and this is the only way an or can fail.

$P$ and $Q$. True only when both hold, so one failure is enough to sink it. It is what you mean when you order a main course and a dessert: if the waiter forgets one of them your order has not been filled, and it is no comfort that the other arrived. In the picture it is the overlap of $A$ and $B$.

Reading the $P \wedge Q$ column row by row

Both hold, and this is the only way an and can succeed.
$Q$ fails, and one failure is enough to sink it.
$P$ fails, so again the and fails.
Both fail.

Reading the $P \Rightarrow Q$ column

Think of $P$ as the statement $x \in A$, and of $Q$ as the statement $x \in B$. Then $P \Rightarrow Q$ says that being in $A$ forces being in $B$, which is exactly $A \subseteq B$, and the four rows are the four things that can happen to a single $x$.

Row 1. Reasoning correctly from a true $P$ lands you on $Q$, and $Q$ is true: here $x \in A$, and the argument carries it to $x \in B$. A true hypothesis and sound steps give a true conclusion, which is the situation a direct proof works in, and we say more about it below.
Row 2. The only row in which the reasoning is wrong. Starting from a correct assumption and arriving at an incorrect conclusion means the deduction itself is incorrect. In sets, if we find an $x$ with $x \in A$ but $x \notin B$, then $A \subseteq B$ is false, and this is exactly what it means to call $x$ a counterexample to $A \subseteq B$.
Rows 3 and 4. Starting from an incorrect assumption and arriving at any conclusion at all is mathematically sound. In real life, this is like when someone says something invalid, and without any fault of our own, we might conclude something invalid. We might also, by chance, deduce something valid. This happens in maths too: take the false assumption $0 = 1$. Multiplying both sides by $0$ is a legitimate step and gives $0 = 0$, which is true, and that is row 3. Adding $1$ to both sides is equally legitimate and gives $1 = 2$, which is false, and that is row 4. The same false start, the same lawful steps, and conclusions of either kind. In sets: when $A \subseteq B$ and $x \notin A$, we may still have $x \in B$ or $x \notin B$, and the inclusion is untroubled either way. The pictures below show both.

The truth table of $P \Rightarrow Q$

Since $P$ and $Q$ are each either true or false, there are exactly four situations to consider. A truth table lists all four and records the truth value of the compound statement in each. The table below shows that the three statements $P \Rightarrow Q$, $\neg P \vee Q$ and $\neg Q \Rightarrow \neg P$ are equivalent, since they are all true or false at the same time.

	$P$	$Q$	$\neg P$	$\neg Q$	$P \Rightarrow Q$	$\neg P \vee Q$	$\neg Q \Rightarrow \neg P$
1	T	T	F	F	T	T	T
2	T	F	F	T	F	F	F
3	F	T	T	F	T	T	T
4	F	F	T	T	T	T	T

The shaded row is the only one in which $P \Rightarrow Q$ is false.

Row 1. $P$ true, $Q$ true, so $P \Rightarrow Q$ is true.

This is the essence of the direct proof. If $P$ is true, and correct logic carries you from $P$ to $Q$, that is, if $P \Rightarrow Q$ is true as well, then $Q$ has to be true. Start where the hypothesis puts you, take valid steps, and you arrive at the conclusion. In the picture for the direct proof below, $x$ is in $A$, and the argument carries it into $B$.

Row 2. $P$ true, $Q$ false, so $P \Rightarrow Q$ is false.

The one row that breaks the promise, and so the only one a proof has to rule out. The hypothesis holds and the conclusion fails: this is what a counterexample looks like. In sets it is an $x$ lying in $A$ but not in $B$, which is why $A \subseteq B$ and $A \cap B^{c} = \emptyset$ say the same thing.

Row 3. $P$ false, $Q$ true, so $P \Rightarrow Q$ is true.

The hypothesis fails, so the promise was never put to the test and cannot have been broken. Notice that $Q$ happens to be true here anyway. An implication never claims to explain why $Q$ holds, only that $Q$ cannot fail while $P$ holds.

Row 4. $P$ false, $Q$ false, so $P \Rightarrow Q$ is true.

This is the essence of the proof by a contrapositive argument. If $Q$ is false, and $P \Rightarrow Q$ is true, then $P$ has to be false. Read the table the other way up: assuming $\neg Q$ leaves only rows 2 and 4, and row 2 is the one a true implication forbids, so you land here, where $P$ is false.

It is also where a false premise shows how empty it is: with $P$ false you may put anything at all in $Q$ and the implication still stands, which is exactly why nothing can be learned from it.

Here is what each method of proof does with the claim $A \subseteq B$, which is worked out in full further down, and which row of the table it goes after.

Direct proof (row 1)

To prove $A \subseteq B$, we take an arbitrary $x \in A$ and show that $x \in B$.

By contradiction (row 2)

We want to prove that row 2 never happens. Rows 1, 3 and 4 are the three a true implication allows, and row 2 is the one it forbids. So instead of proving $A \subseteq B$ directly, we prove that $x \in A$ and $x \notin B$ never happens, that is, $A \cap B^{c} = \emptyset$.

By contrapositive (row 4)

We want to prove $A \subseteq B$. Instead we prove that $B^{c} \subseteq A^{c}$, or equivalently, that if $x \notin B$ then $x \notin A$.

Counterexample

To say that $A$ is not a subset of $B$, we only need to find one $x$ with $x \in A$ and $x \notin B$. One is enough: a universal claim is refuted by a single case, which is why the circles no longer sit one inside the other.

One animal is enough

Biology is full of confident universal claims, and they fall the same way. Take “every mammal gives birth to live young”. It is tidy, it is almost always right, and the platypus destroys it by laying eggs. Echidnas lay them too, but the first one was already enough: a single counterexample retires the claim, and what survives is the weaker statement that most mammals do, together with a name for the ones that do not.

By induction

The idea of induction. If the first few fall, and every domino that falls is close enough to knock over the next, then all of them must eventually fall. Pushing the first is the base case; each domino being within reach of its neighbour is the inductive step. Take away either one and the argument stops, as the second row shows.

Every domino within reach of the next: push the first and all of them fall.

The step from k to k+1 fails, so everything from k+1 onwards stays standing.

Read the $P \Rightarrow Q$ column and notice how little it takes for an implication to be true. It is false in exactly one situation: $P$ true and $Q$ false. In rows 3 and 4 the hypothesis fails, and the implication is declared true by default. Mathematicians call such a statement vacuously true, and it is the formal counterpart of the umbrella above.

Food for thought

Read “every integer divisible by $6$ is even” as a promise made about each integer in turn, and ask which integers could ever break it.

Two claims, three proofs each

Here are two claims, each proved three times, so that the only thing changing is the method.

Claim (the running example)

Let $A = \{\, n \in \mathbb{Z} : 6 \mid n \,\}$ and $B = \{\, n \in \mathbb{Z} : 2 \mid n \,\}$. Then $A \subseteq B$.

In words: every integer divisible by $6$ is even. Each method proves it in its own form:

Direct proof. If $n$ is divisible by $6$, then $n$ is even.
Contrapositive. If $n$ is odd, then $n$ is not divisible by $6$.
Contradiction. No integer is both divisible by $6$ and odd.

Complements are taken in $\mathbb{Z}$, so $B^{c}$ is the set of odd integers.

Proof (direct)

Let $x \in A$. By definition of $A$ there is some $k \in \mathbb{Z}$ with

\[ x = 6k. \]

Then $x = 2(3k)$, and $3k \in \mathbb{Z}$, so $2 \mid x$, which says precisely that $x \in B$.

The element $x$ was arbitrary, so $A \subseteq B$.□

Proof (by contrapositive)

We show $B^{c} \subseteq A^{c}$. Let $x \notin B$, so $x$ is odd.

If $x$ were in $A$ then $x = 6k = 2(3k)$ would be even, which it is not. So $x \notin A$.

As $x$ was arbitrary, $B^{c} \subseteq A^{c}$, and therefore $A \subseteq B$.□

Proof (by contradiction)

Suppose $A \cap B^{c} \neq \emptyset$, and choose $x \in A \cap B^{c}$. Then $6 \mid x$ and $x$ is odd.

From $6 \mid x$ we get $x = 6k = 2(3k)$, so $x$ is even. So $x$ is both even and odd, which is impossible.

The assumption is untenable, so $A \cap B^{c} = \emptyset$, that is $A \subseteq B$.□

Claim (a second example)

Let $n \in \mathbb{Z}$. If $n^{2}$ is odd, then $n$ is odd.

Each method proves it in its own form:

Direct proof. If $n^{2}$ is odd, then $n$ is odd.
Contrapositive. If $n$ is even, then $n^{2}$ is even.
Contradiction. No integer $n$ is even while $n^{2}$ is odd.

Proof (direct)

Divide $n$ by $2$: $n = 2q + r$ with $q \in \mathbb{Z}$ and $r \in \{0, 1\}$. Then

\[ \begin{aligned} n^{2} &= 4q^{2} + 4qr + r^{2} \\ &= 2\bigl(2q^{2} + 2qr\bigr) + r , \end{aligned} \]

since $r^{2} = r$ when $r$ is $0$ or $1$. So $n^{2}$ leaves the same remainder $r$ on division by $2$ as $n$ does. As $n^{2}$ is odd, that remainder is $1$, and $n = 2q + 1$ is odd.□

Proof (by contrapositive)

We prove: if $n$ is even, then $n^{2}$ is even. Suppose $n = 2m$ with $m \in \mathbb{Z}$. Then $n^{2} = 4m^{2} = 2(2m^{2})$, and $2m^{2} \in \mathbb{Z}$, so $n^{2}$ is even. This is the contrapositive of the claim.□

Proof (by contradiction)

Suppose $n^{2}$ is odd but $n$ is not odd, so that $n$ is even: $n = 2m$ with $m \in \mathbb{Z}$. Then $n^{2} = 4m^{2} = 2(2m^{2})$ is even. So $n^{2}$ is both odd and even, which is impossible. Hence $n$ is odd.□

More discussion on proof by contradiction

Start by negating the implication, because its negation is exactly what this method assumes. Take the middle of the three equivalent forms, $\neg P \vee Q$, and negate it. The negation of an or is an and, by De Morgan's law, and negating $\neg P$ gives back $P$:

\[ \begin{aligned} \neg (P \Rightarrow Q) &= \neg(\neg P \vee Q) \\ &= P \wedge \neg Q . \end{aligned} \]

So the statement to be ruled out is $P \wedge \neg Q$: the hypothesis holds and the conclusion fails, both at once. That is row 2, and a proof by contradiction assumes it and shows that it cannot happen.

Why do we use proof by contradiction?

Because sometimes it is easier to show that if something were not true, it would cause chaos, so it has to be true. Here is the classic example, proved below: the axioms of mathematics $\Longrightarrow \sqrt{2} \notin \mathbb{Q}$. By contradiction: if $\sqrt{2}$ were rational, mathematics would fall apart!

In fact, legend has it that someone was killed over it. The Pythagoreans of ancient Greece taught that everything could be described by whole numbers and their ratios. One of them, usually named as Hippasus of Metapontum, in the fifth century BC, is said to have found that the side and the diagonal of a square have no common unit of length, which is the statement that $\sqrt{2}$ is irrational, and to have been drowned at sea for revealing it. The story was written down many centuries later, and its versions disagree, so it is a legend rather than history.

Claim

$\sqrt{2}$ is irrational, that is, $\sqrt{2} \notin \mathbb{Q}$.

Before proving it, ask what $P$ and $Q$ are here, because at first sight the claim has no hypothesis at all. It simply says that $\sqrt{2}$ is irrational. So where is the implication?

$Q$ is the easy half: it is the statement $\sqrt{2} \notin \mathbb{Q}$. And $P$ is everything we are standing on when we assert it. The axioms for the integers and for the rationals, what it means for one integer to divide another, the rules of arithmetic, the definition of a square root. A theorem with no visible hypothesis is a theorem whose hypothesis is the background mathematics itself, and the implication is

\[ \text{The axioms of maths} \;\Longrightarrow\; \sqrt{2} \notin \mathbb{Q} . \]

Proof (by contradiction)

Suppose instead that $\sqrt{2} \in \mathbb{Q}$. Then we may write

\[ \sqrt{2} = \frac{p}{q}, \quad p, q \in \mathbb{Z}, \; q \neq 0, \]

in lowest terms, so $p$ and $q$ have no common factor greater than $1$. Squaring and clearing the denominator,

\[ 2q^{2} = p^{2}. \]

So $p^{2}$ is even, and therefore $p$ is even, by the lemma below. Write $p = 2m$, so that

\[ 2q^{2} = 4m^{2}, \quad \text{hence} \quad q^{2} = 2m^{2}. \]

Now $q^{2}$ is even, so by the same lemma $q$ is even. But then $2$ divides both $p$ and $q$, contradicting lowest terms.□

Food for thought

Where exactly did the proof use that $2$ is prime? Run the same argument on $\sqrt{4}$ and watch it break; the step that fails is the one that deserves your attention.

Proof by a contrapositive argument

The contrapositive of $P \Rightarrow Q$ is $\neg Q \Rightarrow \neg P$, and the truth table above showed that the two are the same statement.

Warning: the contrapositive is not $\neg P \Rightarrow \neg Q$

Negating both sides and leaving them in place gives $\neg P \Rightarrow \neg Q$, which is not equivalent to $P \Rightarrow Q$. Row 3 settles it: there $P$ is false and $Q$ is true, so $P \Rightarrow Q$ is true while $\neg P \Rightarrow \neg Q$ reads $\mathrm{T} \Rightarrow \mathrm{F}$ and is false. The arrow has to be reversed as well as negated.

Concretely: “divisible by $6$ $\Rightarrow$ even” is true, but “not divisible by $6$ $\Rightarrow$ not even” is false, as $4$ shows ($4$ is both not divisible by $6$ and still even).

Here is where the contrapositive genuinely earns its place, and the lemma the $\sqrt{2}$ proof borrowed.

Lemma

Let $n \in \mathbb{Z}$. If $n^{2}$ is even, then $n$ is even.

Directly, the hypothesis gives $n^{2} = 2k$, and getting from there to $n$ means taking a square root. The contrapositive hands you $n$ itself.

Proof (by contrapositive)

We prove: if $n$ is odd, then $n^{2}$ is odd. Suppose $n = 2m + 1$ with $m \in \mathbb{Z}$. Then

\[ \begin{aligned} n^{2} &= (2m+1)^{2} \\ &= 4m^{2} + 4m + 1 \\ &= 2\bigl(2m^{2} + 2m\bigr) + 1 , \end{aligned} \]

and $2m^{2} + 2m \in \mathbb{Z}$, so $n^{2}$ is odd. This is exactly the contrapositive of the lemma.□

Proof by induction

The idea is in the dominoes above. Here are two proofs that use it.

Two dominoes to push: the Fibonacci numbers

Set $F_{1} = F_{2} = 1$ and $F_{n+1} = F_{n} + F_{n-1}$. Each term leans on the two before it, so one push will not do: the first two have to be toppled by hand.

Claim: $F_{n} < 2^{n}$ for every $n \geq 1$.

The two base cases are $F_{1} = 1 < 2$ and $F_{2} = 1 < 4$. For the step, suppose $F_{k-1} < 2^{k-1}$ and $F_{k} < 2^{k}$. Then

\[ \begin{aligned} F_{k+1} &= F_{k} + F_{k-1} \\ &< 2^{k} + 2^{k-1} \\ &< 2^{k} + 2^{k} \;=\; 2^{k+1}. \end{aligned} \]

So domino $k+1$ goes over as soon as $k$ and $k-1$ have, and with the first two pushed by hand every one of them falls.

One domino to push: the triangle inequality for many vectors

Theorem 1.14 (iii) of the notes says that for $v, w \in \mathbb{R}^{n}$,

\[ \|v + w\| \;\leq\; \|v\| + \|w\| . \]

It is stated for two vectors. Induction gets it for any number of them at once: for all $m \geq 2$ and all $v_{1}, \dots, v_{m} \in \mathbb{R}^{n}$,

\[ \begin{aligned} &\|v_{1} + v_{2} + \dots + v_{m}\| \\ &\qquad \leq\; \|v_{1}\| + \|v_{2}\| + \dots + \|v_{m}\| . \end{aligned} \]

Here one push is enough, because each term leans only on the one before it. The base case $m = 2$ is the theorem itself. For the step, suppose the claim holds for $m = k$. Bracket the first $k$ vectors together and apply the two-vector case:

\[ \begin{aligned} &\|v_{1} + \dots + v_{k} + v_{k+1}\| \\ &\qquad =\; \bigl\| (v_{1} + \dots + v_{k}) + v_{k+1} \bigr\| \\ &\qquad \leq\; \|v_{1} + \dots + v_{k}\| + \|v_{k+1}\| , \end{aligned} \]

and the inductive hypothesis bounds the first term by $\|v_{1}\| + \dots + \|v_{k}\|$, which gives the claim for $m = k+1$.

Compare the two examples. Fibonacci needed two dominoes pushed by hand because each term leans on the two before it. This one needs only one, because each step reaches back a single place. How many you must push by hand is decided by how far back the step reaches.

Switches and truth

A switch is a statement

In 1937 Claude Shannon noticed that the algebra of switching circuits and the algebra of true and false are the same algebra. The dictionary is short enough to give in one line. A switch is a statement. Closed means true and open means false, and the lamp at the end of the circuit lights exactly when the whole expression is true.

That gives you three things to build with.

$P \wedge Q$ is two switches in series. Current has to get through both, so the lamp lights only when both are closed.
$P \vee Q$ is two switches in parallel. Either branch will do, so the lamp lights when at least one is closed.
$\neg P$ is a break contact. This is the piece people usually mean when they ask what negation looks like in a circuit: a contact wired so that it conducts when the switch is not pressed. Electricians call it normally closed; in logic gates the same idea is the inverter, drawn as a triangle with a small bubble on its output. The bubble is the negation.

Food for thought: a circuit for $\Rightarrow$

There is no switch for $\Rightarrow$. Implication has to be built out of the other three, and the truth table says how: $P \Rightarrow Q$ is the same statement as $\neg P \vee Q$. So the circuit for an implication is a break contact for $P$ in parallel with an ordinary contact for $Q$. Watch for it below.

Using this equivalence, the light switches for $P \Rightarrow Q$ are the ones for $\neg P \vee Q$, drawn here.

Are two statements the same?

Two statements are logically equivalent when they are true in exactly the same circumstances, which is to say that their truth tables agree row for row. In circuits that reads even more plainly: wire both up to the same switches, and ask whether the two lamps ever disagree.

So here is a machine for settling it. Pick a pair of statements, and the checker walks through every combination of the switches in turn. If it ever finds a combination where one lamp is on and the other is off, it stops there and reports that the two are not equivalent, with the combination that separates them. If it gets through all of them with the lamps always agreeing, they are equivalent.

Three of the pairs in that list are worth sitting with. The contrapositive $\neg Q \Rightarrow \neg P$ agrees with $P \Rightarrow Q$ on every row, which is why you are allowed to prove either one in place of the other. The converse-negation $\neg P \Rightarrow \neg Q$ does not, and the checker stops on the row that separates them. And De Morgan's laws turn a series pair into a parallel pair the moment you negate it, which is exactly what the two circuits show.

The same table, done in arithmetic

Nothing above needs the words true and false. Write $1$ for true and $0$ for false, so that $P, Q \in \{0, 1\}$, and the four statements become ordinary operations on numbers:

\[ \begin{aligned} \neg P &= 1 - P, \\ P \vee Q &= \max(P, Q), \\ P \wedge Q &= P \cdot Q, \\ P \Rightarrow Q &= \max(1 - P,\; Q) . \end{aligned} \]

Each one is worth a moment. Negation flips $0$ and $1$, which is what subtracting from $1$ does. An or takes the larger of the two, so it is $1$ as soon as either is. An and multiplies, so a single $0$ destroys it, which is exactly the one-failure-is-enough rule. And the implication is read off its own equivalent form, $\neg P \vee Q$, giving $\max(1 - P, Q)$: it is $0$ only when $1 - P$ and $Q$ are both $0$, that is, only when $P = 1$ and $Q = 0$. That is row 2 again, arrived at by arithmetic.

You could equally write $P \wedge Q = \min(P, Q)$, since on $\{0,1\}$ the product and the minimum agree. The point is not which formula you choose but that the whole table is a calculation.

This is related to tropical algebra, which computes with $\max$ in place of $+$, as or does here, and with $+$ in place of $\times$. Tropical geometry is built on it.