P ∧ Q
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$.
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.
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$:
\[ \neg (P \Rightarrow Q) \;=\; \neg(\neg P \vee Q) \;=\; P \wedge \neg Q . \]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}, \qquad p, q \in \mathbb{Z}, \quad 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}, \qquad \text{hence} \qquad 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 table of proof methods above: press By induction. 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.