Hunter Liu's Website

1. What is a Proof?

Table of Contents | 2. What is a Number? ≫

Since it’s the first week of the quarter and there has only been a single lecture, there isn’t too much to say. Thus it is a pristine opportunity to discuss what proofs are and some common strategies, techniques, and pitfalls.

In fact we will begin with a question that’s not so much a proof but rather a gastronomical exercise.

Question 1.

Do there exist three different simple foods so that every pair among them makes a classic and delicious combination, but all three foods put together form something vile and disgusting?

The hope is that you discuss the question at moderate length with the people sitting next to you and realise, after violent deliberation, that this is a nontrivial question.

If I just said to you that the answer is yes, you may or may not believe me. In fact, you would likely ask for what those three foods are because you are not convinced and demand an example.

One potential answer I may offer is, “chocolate, chili peppers, and oranges.” And of course there’s all sorts of reasons that may cause dissatisfaction with this answer, and you may raise the following objections:

Hopefully you can think of some more objections to this.

The point of this little conversation is to demonstrate the following main ideas that I want you to keep in mind.

First and foremost, me making the claim “Yes, there are obviously three simple foods that fit the above criteria” isn’t good enough, and what happened in the above conversation is that I was demanded a proof of this claim. I had to exhibit an example of the three foods and justify that every part of my claim was met.

This is what’s required to have a “complete” proof. Note that some claims don’t really need to be called into question, such as the implicit claim that oranges are a simple food. We haven’t made clear yet what “simple food” means (more on that later), but no matter what our definition is, an orange is surely simple enough.

Second, some parts of my claim are ambiguous. What does “classic” mean? What is a “simple food”? What qualifies as “vile and disgusting”? Is “delicious” some quantifiable, measurable property, or is it relative and subjective? To furnish a proof, I need to make sure that whoever I am convincing (in this case, the reader or listener) and I both agree on what everything in the claim means.

The takeaway is that when writing a proof, you need something “complete” and “unambiguous”. In mathematics, the “complete” part means that you are verifying nonobvious statements (you don’t have to state the rules of logical inference every time you use them, e.g.), both those that are explicitly stated and those that are implicitly assumed. In particular, theorem and lemmas and such in class and in the textbook are often stated as “if \(P\) and \(Q\) are true, then \(R\) is true” — make sure you check that \(P\) and \(Q\) really are true!

The “unambiguous” means that everything you say should have a clear definition. A good example of this is the question of, “what does it mean for a region in the Cartesian plane to be connected?” The unit square and the unit circle (filled in or not, including the border or not) are certainly “connected” in the obvious sense of the word. What about two squares that touch only at one corner? This is where definitions become very important. All throughout the quarter, we’ll be providing very rigid definitions of certain words (“converge”, “limit”, “continuous function”, etc.), even when their meaning is intuitive and you believe you can use common sense to tell if the argument is sound or not.

But most of all, the ideas of what’s “complete” or “ambiguous” is ultimately…ambiguous. I can’t provide a complete, unambiguous, rigorous definition of these two terms, so if you’re unsure of something on the homework or on an exam, just ask!

I hope you can either give me a clear example of the above triple of foods or give a complete proof that no such triple can exist. But moving on, this example is one of a (failed) direct proof: I have started from some “clear” truths (“oranges are simple foods”, “chocolate and chili peppers go well together”, etc.) and tried to arrive at exactly the statement I wanted to prove.

When proving the statement “If \(P\), then \(Q\)”, a direct proof doesn’t always work out. Do not worry if you get stuck, and let’s give an example of an alternatives via biblical allegory.

Biblical Allegory 2. King Solomon and the Baby

Living in King Solomon’s glorious palace were two nameless women, both known to be excellent mothers of newborn children who deeply cared for their offspring. One night, in a tragic accident, one of the women rolled over in her sleep and crushed her baby. King Solomon awoke to the two women quarreling: both claimed to be the mother, both accusing the other of kidnapping the child. The two asked King Solomon to resolve the conflict.

King Solomon pulled a chainsaw out of his back pocket, revved it, and said to the women, “I’ll cut the baby in half. You’ll each have half a baby.” The first woman said, “I suppose that’s fair.” But the second woman pleaded King Solomon to spare the baby, even if it meant letting the alleged kidnapper go. King Solomon threw the chainsaw into the nearest river and returned the baby to the second woman.

A direct proof that either woman is or isn’t the rightful mother is impossible — there were no maternity tests back then, no surveillance cameras, birth certificates, etc. Instead, King Solomon followed this reasoning:

  1. Suppose the first woman is the mother of the baby.
  2. The first woman is an excellent mother.
  3. Excellent mothers would rather give up their children rather than let them die.
  4. This contrtadicts the action the first mother took.
  5. Therefore the first woman is not the mother of the baby.

Notice the structure of this argument: in order to prove the very last statement, we begin by assuming the opposite is true. We then deduce from axioms (step 3), known facts (steps 2 and 4), and logic a contradiction. Thus the assumptions we started with must be false. This is called a proof by contradiction, for hopefully obvious reasons.

Proofs by Contradiction

A technique that evades allegory is the proof by contrapositive. The statement “\(P\) implies \(Q\)” is exactly equivalent to “Not \(Q\) implies not \(P\)” — flip the positions of the two statements, then negate the statements! Sometimes, this mirrored version of the statement ends up being easier to prove than the original statement.

Example 3.

Prove the following statement:

Let \(x\) be an integer. If there exists some integer \(n>1\) such that \(x^n\) is even, then \(x\) is also even.

Here, the assumption is “there exists an integer \(n>1\) such that \(x^n\) is even”, and the conclusion is “\(x\) is even”. The contrapositive swaps then negates (or negates and swaps) the two:

If \(x\) is not even, then there exists no integer \(n > 1\) such that \(x^n\) is even.

Phrased equivalently, one could say

If \(x\) is odd, then for every integer \(n > 1\), \(x^n\) is also odd.

This last version of the statement is pretty straightforward — the product of odd numbers is always odd! (You could present a fully rigorous proof by induction if you really wanted to, but this one is obvious enough.) Since the contrapositive of our original statement is true, the original statement is also true.

Remark 4. Negating Complicated Statements

In these examples, negating a statement was not too difficult. Later in this course, statements can get very bulky and difficult to logically invert. For instance, what’s the logical negation of the following statement?

For all \(\epsilon > 0\), there exists a \(\delta > 0\) such that for all \(x\neq y\) with \(\left\lvert x-y \right\rvert < \delta \), \(\left\lvert x^2-y^2 \right\rvert < \epsilon \).

It’s too much! The trick is to read through the statement, left-to-right, and swap “for all” with “there exists” and vice-versa. Negate the conclusion of the statement when you get there.

There exists \(\epsilon > 0\) such that for all \(\delta > 0\), there exists \(x \neq y\) with \(\left\lvert x-y \right\rvert < \delta \) such that \(\left\lvert x^2-y^2 \right\rvert \geq \epsilon \).

You’ll inevitably have to restructure the grammar a bit, but that’s all there is to it!

Some Tips

If you see a problem and you get stuck, don’t panic! Try doing the following: