$$ %---- MACROS FOR SETS ----% \newcommand{\znz}[1]{\mathbb{Z} / #1 \mathbb{Z}} \newcommand{\twoheadrightarrowtail}{\mapsto\mathrel{\mspace{-15mu}}\rightarrow} % popular set names \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\I}{\mathbb{I}} % popular vector space notation \newcommand{\V}{\mathbb{V}} \newcommand{\W}{\mathbb{W}} \newcommand{\B}{\mathbb{B}} \newcommand{\D}{\mathbb{D}} %---- MACROS FOR FUNCTIONS ----% % linear algebra \newcommand{\T}{\mathrm{T}} \renewcommand{\ker}{\mathrm{ker}} \newcommand{\range}{\mathrm{range}} \renewcommand{\span}{\mathrm{span}} \newcommand{\rref}{\mathrm{rref}} \renewcommand{\dim}{\mathrm{dim}} \newcommand{\col}{\mathrm{col}} \newcommand{\nullspace}{\mathrm{null}} \newcommand{\row}{\mathrm{row}} \newcommand{\rank}{\mathrm{rank}} \newcommand{\nullity}{\mathrm{nullity}} \renewcommand{\det}{\mathrm{det}} \newcommand{\proj}{\mathrm{proj}} \renewcommand{\H}{\mathrm{H}} \newcommand{\trace}{\mathrm{trace}} \newcommand{\diag}{\mathrm{diag}} \newcommand{\card}{\mathrm{card}} \newcommand\norm[1]{\left\lVert#1\right\rVert} % differential equations \newcommand{\laplace}[1]{\mathcal{L}\{#1\}} \newcommand{\F}{\mathrm{F}} % misc \newcommand{\sign}{\mathrm{sign}} \newcommand{\softmax}{\mathrm{softmax}} \renewcommand{\th}{\mathrm{th}} \newcommand{\adj}{\mathrm{adj}} \newcommand{\hyp}{\mathrm{hyp}} \renewcommand{\max}{\mathrm{max}} \renewcommand{\min}{\mathrm{min}} \newcommand{\where}{\mathrm{\ where\ }} \newcommand{\abs}[1]{\vert #1 \vert} \newcommand{\bigabs}[1]{\big\vert #1 \big\vert} \newcommand{\biggerabs}[1]{\Bigg\vert #1 \Bigg\vert} \newcommand{\equivalent}{\equiv} \newcommand{\cross}{\times} % statistics \newcommand{\cov}{\mathrm{cov}} \newcommand{\var}{\mathrm{var}} \newcommand{\bias}{\mathrm{bias}} \newcommand{\E}{\mathrm{E}} \newcommand{\prob}{\mathrm{prob}} \newcommand{\unif}{\mathrm{unif}} \newcommand{\invNorm}{\mathrm{invNorm}} \newcommand{\invT}{\mathrm{invT}} \newcommand{\P}{\text{P}} \newcommand{\pmf}{\text{pmf}} \newcommand{\pdf}{\text{pdf}} % real analysis \renewcommand{\sup}{\mathrm{sup}} \renewcommand{\inf}{\mathrm{inf}} %---- MACROS FOR ALIASES AND REFORMATTING ----% % logic \newcommand{\forevery}{\ \forall\ } \newcommand{\OR}{\lor} \newcommand{\AND}{\land} \newcommand{\then}{\implies} % set theory \newcommand{\impropersubset}{\subseteq} \newcommand{\notimpropersubset}{\nsubseteq} \newcommand{\propersubset}{\subset} \newcommand{\notpropersubset}{\not\subset} \newcommand{\union}{\cup} \newcommand{\Union}[2]{\bigcup\limits_{#1}^{#2}} \newcommand{\intersect}{\cap} \newcommand{\Intersect}[2]{\bigcap\limits_{#1}^{#2}} \newcommand{\intersection}[2]{\bigcap\limits_{#1}^{#2}} \newcommand{\Intersection}[2]{\bigcap\limits_{#1}^{#2}} \newcommand{\closure}{\overline} \newcommand{\compose}{\circ} % linear algebra \newcommand{\subspace}{\le} \newcommand{\angles}[1]{\langle #1 \rangle} \newcommand{\identity}{\mathbb{1}} \newcommand{\orthogonal}{\perp} \renewcommand{\parallel}[1]{#1^{||}} % calculus \newcommand{\integral}[2]{\int\limits_{#1}^{#2}} \newcommand{\limit}[1]{\lim\limits_{#1}} \newcommand{\approaches}{\rightarrow} \renewcommand{\to}{\rightarrow} \newcommand{\convergesto}{\rightarrow} % algebra \newcommand{\summation}[2]{\sum\nolimits_{#1}^{#2}} \newcommand{\product}[2]{\prod\limits_{#1}^{#2}} \newcommand{\by}{\times} \newcommand{\integral}[2]{\int_{#1}^{#2}} \newcommand{\ln}{\text{ln}} % exists commands \newcommand{\notexist}{\nexists\ } \newcommand{\existsatleastone}{\exists\ } \newcommand{\existsonlyone}{\exists!} \newcommand{\existsunique}{\exists!} \let\oldexists\exists \renewcommand{\exists}{\ \oldexists\ } % statistics \newcommand{\distributed}{\sim} \newcommand{\onetoonecorresp}{\sim} \newcommand{\independent}{\perp\!\!\!\perp} \newcommand{\conditionedon}{\ |\ } \newcommand{\given}{\ |\ } \newcommand{\notg}{\ngtr} \newcommand{\yhat}{\hat{y}} \newcommand{\betahat}{\hat{\beta}} \newcommand{\sigmahat}{\hat{\sigma}} \newcommand{\muhat}{\hat{\mu}} \newcommand{\transmatrix}{\mathrm{P}} \renewcommand{\choose}{\binom} % misc \newcommand{\infinity}{\infty} \renewcommand{\bold}{\textbf} \newcommand{\italics}{\textit} \newcommand{\step}{\text{step}} $$

How to Really Prove Something

Featured image

“Prove it” is a phrase thrown around with glee. But rarely are you really challenging a friend to provide a rigorous proof of some statement you disagree with. In science, there is no proof. Instead, the scientific method encourages you to form a hypothesis, collect data, and test that hypothesis.

Repeating this process advances you closer and closer to the truth, but nowhere in this process can you say you’ve proven a hypothesis. This would be impossible as you would have to exhaustively collect all data in the known universe to see if your hypothesis still holds. And even then, your measurements will always be imprecise.

The scientific body of knowledge will always be subject to revision as more data is collected and better measuring instruments are built.

On the other hand, mathematics is built from the ground up using a set of simple statements called axioms. These axioms are statements composed of sets, functions, and logical symbols.

I’ve always found this a beautiful fact of mathematics - that it’s nothing more than some sets, functions, and logic. Of course this means that now you can build the whole of mathematics and ensure that every new statement is coherent with previous ones. This naturally endows anyone looking to prove a mathematical statement with the ability to:

So how do you prove a mathematical statement? There are generally four methods:

  1. Implication
  2. Contradiction
  3. Contrapositive
  4. Induction

Proof by implication

Proof by implication (also sometimes called proof by direct implication) is a method where you start with one fact, and use that fact to imply other facts. Through this chain of implications, you reach some conclusion. More simply, you’re saying “if A, then B”. This is commonly written as:

$$ A \then B $$

To drive this home, say you’re trying to prove that if $m$ and $n$ are perfect squares, then $mn$ is a perfect square.

You first start off with the fact you know $m$ and $n$ are perfect squares. What does this mean? Well, $m = x^2$ and $n = y^2$ where $x$ and $y$ are some integers. Using that fact, you can show that $mn = x^2y^2 = (xy)^2$, thus showing that $mn$ is also a perfect square.

In practice, proof by implication is a common first-approach to proving some statement. By working forward from A and backward from B, you eventually bridge the gap and create a chain of implications.

Proof by contradiction

But sometimes that gap can’t be bridged. In these cases, it might be helpful to consider proving “if A, then B” by reaching a contradiction. The reasoning is as follows: if you’re trying to prove “if A, then B” and this statement is indeed true, then there must be a reason why B cannot be false. Your goal is to find that reason by seeking a contradiction.

To do this, you assume A is true and (not B) is true, then work forward by implication. The hope is that you reach some contradiction and if you do, then you’ve successfully proven “if A, then B”.

You should try this with an example. Let $n$ be an integer. If $n^2$ is even, then $n$ is even. If you were to try and prove this using implication, you might say that since $n^2$ is even, then there exists some integer $m$ such that $n^2 = 2m$. And since $n$ is even, then there exists some integer $k$ such that $n = 2k$. But how do you get $\sqrt{2m}$ to look like $2k$? This is where you can use the contradiction method.

Suppose $n$ is an integer and $n^2$ is even and $n$ is odd. Then there exists some integer $k$ such that $n = 2k + 1$. This would imply that

$$ \begin{aligned} n^2 &= (2k + 1)^2 \\\ &= 4k^2 + 4k + 1 \\\ &= 2(2k^2 + 2k) + 1 \\\ \end{aligned} $$

If you let $z = 2k^2 + 2k$ then $n^2 = 2z + 1$, an odd number. But wait! This is a contradiction since you had assumed $n^2$ was even. So “if $n^2$ is even, then $n$ is even” must be true.

A proof by contradiction isn’t the only method you can try if implication doesn’t work. Sometimes you can just turn implication on its head.

Proof by contrapositive

You’re still trying to prove “if A, then B” but it’s not working out. You might instead try “if not B, then not A”. In fact, this statement is the logical equivalent to “if A, then B” and is called its contrapositive. If you’re not familiar with why it’s logically equivalent, it happens to be a result of boolean logic which is usually represented as a truth table.

However, consider the example statement “if it’s raining outside, then the grass is wet”. The contrapositive of this statement would be “if the grass is not wet, then it’s not raining outside”. Both statements are logically equivalent to each other. And once the statement you’re trying to prove is in its contrapositive form, you can then use implication to complete the proof.

Take the statement we recently proved via contradiction:

Let $n$ be an integer. If $n^2$ is even, then $n$ is even.

Now take the contrapositive of this statement:

Let $n$ be an integer. If $n$ is odd, then $n^2$ is odd.

If $n$ is odd, then there is some integer $k$ such that $n = 2k + 1$. So by implication,

$$ \begin{aligned} n^2 &= (2k + 1)^2 \\\ &= 4k^2 + 4k + 1 \\\ &= 2(2k^2 + 2k) + 1 \\\ \end{aligned} $$

If you let $z = 2k^2 + 2k$ then $n^2 = 2z + 1$ which is an odd number. And the proof is complete.

Another way to think about a proof by contrapositive is that you suppose A and (not B) are both true and work forward to prove that A is false (i.e. not A). In essence, you’re really doing a proof by contradiction but this time you know what contradiction you’re looking for.

Proof by induction

A proof by induction is a bit like falling dominos. The first domino falls. Then when any domino falls, the next one falls. Proof by induction is similar. You first start by proving the base case, $n = 1$. Then you assume the statement is true for $k$ and show that it’s also true for $k + 1$. Once you’ve done that, then you’ve officially proven the statement for all $n$.

It’s now mathematical lore that in the late 1700s while in elementary school, Carl Friedrich Gauss was given busy work by his math teacher. He was told to sum the numbers from 1 to 100. After some clever observations, he found that he could easily calculate the total with the following formula, $\frac{n(n + 1)}{2}$. This is what you’ll prove by induction, that the sum of $n$ positive integers is equal to the function $\frac{n(n + 1)}{2}$.

First you prove the base case where $n = 1$. Does the sum of 1 equal $f(n) = \frac{n(n + 1)}{2}$? Plugging in 1 for $n$, it most assuredly does. So the base case is proven. Now assume $f(k) = \frac{k(k + 1)}{2}$ to be true. You want to show that $f(k + 1)$ is also true. Well $f(k + 1)$ is just the sum of the first $k + 1$ positive integers

$$ 1 + 2 + \dots + k + (k + 1) $$

Well this is equal to the sum of the first $k$ positive integers plus $k + 1$, giving you $\frac{k(k + 1)}{2} + (k + 1)$. If you use some basic algebra to apply a common denominator and factor out some terms, you’ll end up with $\frac{(k + 1)((k + 1) + 1)}{2}$. Taking a closer look at that expression, you’ll see that it resembles our initial function, $\frac{n(n + 1)}{2}$. And now the proof is complete!

To wrap you head around what you just did, you assumed the function was true for $k$ and proved it was also true for $k+1$. Since you proved it was true for $f(1)$ (our base case), then you know it’s true for $f(2)$. And since you know it’s true for $f(2)$, then it’s true for $f(3)$, and so on… So by induction, you’ve proven the function must be true for all of $n$ (i.e. $f(n) = \frac{n(n + 1)}{2}$ is true).

Logical symbols in statements

With the above proof methods, you’re ready to tackle most proofs out there. However, in some statements you might see phrases (or their logical symbol equivalents) like “there exists”, “for all”, or “unique”. Statements that contain these phrases are still tackled with the four proof methods, but there are some helpful guidelines for addressing each one. For simplicity, assume you’re still thinking about the statement, “if A, then B”.

Existential crisis

If you see that B has the phrase “there exists”, do the following:

  1. Suppose A is true
  2. Guess or construct the object having the certain property and show that the something happens
  3. Conclude the desired object exists

Me too

If you see that B has the term “for all” or “for every”, do the following:

  1. Suppose A is true
  2. Choose an object with the certain property
  3. Use implication to conclude that the something happens

The only one

If you see that B has the word “unique”, do the following:

  1. Suppose A is true and that two such objects exist
  2. Use implication to conclude that the two objects are equal thus showing there’s really only one

This or that

If B has the form “C or D”:

  1. Suppose A is true and (not C) is true
  2. Use implication to prove that D is true

Or you could also:

  1. Suppose A is true and (not D) is true
  2. Use implication to prove that C is true

Conclusion

Through the use of making iron-clad logical deductions, you now know how to really prove something. Hedging your bets is no longer required. If you want to learn more about how to do proofs, Daniel Solow has a really good book called How to Read and Do Proofs. Jeremy Kun also has some good primers on the methods of proof available at his blog.

comments powered by Disqus