EconGraphs Logo BETA
Note: This work is under development and has not yet been professionally edited.
If you catch a typo or error, or just have a suggestion, please submit a note here. Thanks!
Chapter 6 / Introduction to Proofs

6.1 Writing Proofs

Intro

Alethiology and epistemology are branches of philosophy concerned with the nature of truth and knowledge. What does it really mean to know that something is true? My initial instinct is to appeal to reality—to treat truth as whatever can be observed, measured, or touched. However, this view immediately encounters two important difficulties.

  1. First, our senses are fallible. People hallucinate, misremember events, etc.
  2. Second, many truths appear to lie entirely outside the realm of sensory verification. How can I use my senses to determine \(x^2 - 5x + 6 = (x - 2)(x - 3)\) is always true? It sure seems true for any reasonable definition of that word, but there doesn’t seem like an obvious way to use your senses to verify it.

Part of the beauty of mathematics comes from its rejection of physical reality as a source of fundamental truth. Truth, in the world of mathematics, comes purely from assumptions and logic. Most* modern mathematicians take a certain set of 9 “axioms,” or assumptions, to be true simply because they want them to be, and then leverage logic to obtain new truths. This makes math a playground of our imagination—choosing different axioms would lead to a different incarnation of mathematics, a different set of results. The 9 ZFC axioms were chosen in part because we knew they would lead to nice truths like $2+2=4$ and the quadratic equation.

While the bottom up approach of starting from assumptions and building out with logic is great theoretically, starting from the axioms every time we want to build a new result is a tremendous pain. It took Whitehead and Russell literally hundreds of pages in their Principia Mathematica to prove $1+1=2$ from the 9 axioms. In practice, we instead use stepping stones reached by prior results to obtain new ones. Since Russell and Whitehead showed $1+1=2$ follows from the axioms, we consider this a proposition or theorem, and can use it freely to grow the tree of mathematical results further.

As we’ve discussed, doing so comes down to leveraging logic, which itself is surprisingly unwieldy—see Phil 150, 151, or 152 if this sounds interesting to you. Mathematicians have developed logical “cheat codes” we call proof techniques which can let you build results more quickly from whatever assumptions you want to make. This lesson will introduce you to some of these techniques so that you can leverage them yourself in future classes.

Proof by Contradiction

Proof by Contradiction relies on the idea that math should be internally consistent. If we want to show some idea $A$ is true, we proceed as follows:

  1. First, assume $A$ is false.
  2. Second, show that if $A$ were false, then something obviously wrong (like $1=0$) would have to be true.
  3. Since we know that $1=0$ isn’t actually true, then $A$ can’t be false.
  4. Therefore $A$ is true.

Here’s my personal favorite proof by contradiction. It’s a really pretty argument showing that $\sqrt{2}$ is an irrational number.

Theorem 1: $\sqrt{2}$ is irrational.

Proof: First, let’s assume that $\sqrt{2}$ is rational. By definition, that means $\exists$ integers $a$ and $b$ such that $\sqrt{2}=a/b$. Now rational numbers can be represented by lots of such $a$ and $b$. For instance, the number $3$ can be written as $3/1$, $6/2$, $9/3$, and so on. So let’s pick $a$ and $b$ so that $\sqrt{2}$ is as simplified as possible, that is, so $a$ and $b$ are coprime.

Ok, so far we have $\sqrt{2}=a/b$ by our assumption. Let’s play with this expression a bit. \(\sqrt{2} = a/b\) \(2 = a^2/b^2\) \(2b^2=a^2\) So far so good. Notice this means $a^2$ is an even number. That follows just by definition: what it means to be an even number is that you are some other integer (in this case, $b^2$) multiplied by 2.

Great, so $a^2$ is even. You might recall from 7th grade algebra (and if not, check this for yourself!) that even numbers squared always stay even and odd numbers squared always stay odd. Since $a^2$ is even, and only even numbers squared become even, we know $a$ is also even.

Lemma: if $\sqrt{2} = a/b$, then $a$ is an even number.

Now like we said before, being even means you can be written as some other integer, say $c$, times 2. So we can write $a=2c$. Let’s plug that back into what we had before. \(2b^2 = a^2\) \(2b^2 = (2c)^2\) \(2b^2 = 4c^2\) \(b^2 = 2c^2\)

By the same logic we used before, this means $b^2$ is even, and so $b$ is also even.

Lemma: if $\sqrt{2} = a/b$, then $b$ is an even number.

But wait a minute!! At the very start, we chose $a/b$ to be as simplified as possible (that is so $a$ and $b$ were coprime/not a fraction like $6/2$). But if $a$ is even and $b$ is even, then we weren’t actually simplified. This is our contradiction: $a/b$ is both simplified and not simplified, so our initial assumption that $\sqrt{2}$ could be written as a fraction was wrong. Therefore, we indeed have that $\sqrt{2}$ is an irrational number. QED.

Proof by Induction

There’s a famous, and unfortunately probably apocryphal story, where Gauss and his kindergarten teacher had a fight that he won so definitively, it’s still discussed in classrooms today.

Gauss, as the story goes, was being a brat, as kindergarteners are wont to do. His teacher told him to add up all the numbers between 1 and 100 before he could continue talking in class. He paused only briefly before yelling out the correct answer of 5050. How did he know?

Here was his intuition:

This general approach does hint at the true formula for the sum of the first $n$ integers, which we’ve known about since at least the time of Pythagoras: \(\sum_{i=1}^n i=1+2+3+...+n=\frac{n(n+1)}{2}\)

Gauss’ argument feels pretty good for the number 100, but we can’t go and just start applying this formula to any number yet. If the number we’re adding up to is odd, for instance, the argument is mostly the same, but needs some tweaks. Instead, let’s use the formula above as a chance to practice proof by induction. A general proof by induction goes something like this:

[Insert visual: (natural) number line with a blue colored line at n=1 for the base case, and then red arrows curving from each number to its successor. Each arrow could be labeled something like $A_k \to A_{k+1}$]

The inductive step is the magic that makes this whole process work. It’s sort of like an infinite game of leapfrog: we start with the base case of $n=1$, but then use the inductive step to “hop” to $n=2$, then to $n=3$, and so on. Let’s see it in action with the sum formula.

Theorem 2: The sum of the first $n$ integers may be expressed as $$\sum_{i=1}^n i=1+2+3+...+n=\frac{n(n+1)}{2}$$

Proof: First, the base case of $n=1$. If $n=1$, then $\sum_{i=1}^1 i = 1$. So far so good.

For the inductive step, we assume that the formula works for some arbitrary number $k$. That is, we assume the following to be true: \(\sum_{i=1}^k i=1+2+3+...+k=\frac{k(k+1)}{2}\)

Using this, we want to prove the formula would also work if we added $k+1$ to both sides. Indeed, notice \(\begin{aligned} \frac{k(k+1)}{2} + (k+1) &= \frac{k(k+1)}{2} + \frac{2(k+1)}{2} \\ &= \frac{(k+2)(k+1)}{2} \end{aligned}\)

Thus the formula works for $n=k+1$ when it works for $n=k$. So since the statement was true when $n=1$, we now know it’s also true for $n=2, n=3, n=4, …$, that is, true for every number, which is what we wanted to show. QED

Proof by Derivation or Direct Application

Sometimes we can derive new results just by leveraging existing formulae or even by direct computation. Let’s finally prove the simplest version of the Envelope Theorem by leveraging calculus and Fermat’s Theorem of the Optimum. If you want to check out some more general versions of the Envelope Theorem, as well as some cutting edge applications, see Milgrom and Segal (2002), from Stanford’s own Ilya Segal and Paul Milgrom.

Theorem 3 (Envelope Theorem): Assuming all functions are continuously differentiable, the derivative of a value function with respect to a parameter of the problem is equal to the derivative of the objective with respect to that parameter, evaluated at the optimum.

Proof: Consider an arbitrary minimization problem with two choice variables $x_1$ and $x_2$, and one parameter, $p$. This proof will naturally generalize to higher dimensional problems with more choice variables and parameters, so long as everything is differentiable. The problem is to minimize the objective function \(f(x_1, x_2; p) \tag{1}\) The first order necessary conditions are \(\frac{\partial f(x_1, x_2; p)}{\partial x_1} = \frac{\partial f(x_1, x_2; p)}{\partial x_2} = 0 \tag{2}\) If second-order conditions are met, these two equations implicitly define the solution functions \(x_1 = h_1(p) \qquad x_2 = h_2(p) \tag{3}\) If we substitute these solution functions into the objective function, we obtain the value function \(e(p) = f(h_1(p), h_2(p); p) \tag{4}\) If we differentiate $e$ with respect to $p$, the chain rule gives \(\frac{\partial e}{\partial p} = \frac{\partial f(\textcolor{blue}{x_1}, \textcolor{blue}{x_2}; p)}{\partial x_1} \frac{\partial h_1}{\partial p} + \frac{\partial f(\textcolor{blue}{x_1}, \textcolor{blue}{x_2}; p)}{\partial x_2} \frac{\partial h_2}{\partial p} + \frac{\partial f(\textcolor{blue}{x_1}, \textcolor{blue}{x_2}; p)}{\partial p}\) Evaluating at the optimal choice of $\vec x = \vec h$, we obtain \(\frac{\partial e}{\partial p} = \frac{\partial f(\textcolor{blue}{h_1(p)}, \textcolor{blue}{h_2(p)}; p)}{\partial x_1} \frac{\partial h_1}{\partial p} + \frac{\partial f(\textcolor{blue}{h_1(p)}, \textcolor{blue}{h_2(p)}; p)}{\partial x_2} \frac{\partial h_2}{\partial p} + \frac{\partial f(\textcolor{blue}{h_1(p)}, \textcolor{blue}{h_2(p)}; p)}{\partial p} \tag{5}\) However, from the first order conditions we know $\frac{\partial f(h_1(p), h_2(p); p)}{\partial x_1} = \frac{\partial f(h_1(p), h_2(p); p)}{\partial x_2} = 0$. Therefore, the first two terms disappear and the result becomes \(\frac{\partial e}{\partial p} = \frac{\partial f(\textcolor{blue}{h_1(p)}, \textcolor{blue}{h_2(p)}; p)}{\partial p}= \left.\frac{\partial f}{\partial p}\right|_{\textcolor{blue}{\vec x = \vec h(p)}} \tag{6}\) This is the Envelope Theorem. The slope of the value function with respect to the parameter is just the partial derivative of the objective with respect to that parameter, evaluated at the optimal solution functions. QED

[ End of chapter ]
Copyright (c) Christopher Makler / econgraphs.org