Min-Max Math, ep. 06: Proof by induction and contradiction

Climbing infinite staircases and other impossible feats

I owe you a confession. Contrary to its title, there hasn’t been much math in the Min-Max Math series.

So far, all we have done is just set up the scene for the really juicy part: sets, functions, and other fundamental d̶a̶t̶a̶ s̶t̶r̶u̶c̶t̶u̶r̶e̶s̶ mathematical objects.

We are almost there. The starting pistols are loaded. The engines are revving. Our foot is on the gas pedal, and we are ready to floor it in an instant.

This post is going to be our warm-up lap.

Last time, we saw what a proof is, and what is it made of. An idea and an execution. A chain of implications.

Proofs are not always that simple, but two tools can cut away the confusion like machetes cut vines in an Amazonian rainforest.

The last step is to put the most important methods of proof under our belt:

• proof by contradiction,

• and proof by induction.

We are diving deep into each of them.

---

This post is an episode of my Min-Max Math course, exclusive to paid subscribers. Instead of convoluted results and technical details, we’ll have weekly lessons about

• the tools of (mathematical) thinking,

• the fundamental mathematical objects,

• and how they relate to life, science, and technology.

Sign up for full access!

---

A set of contradictions

“Young man, in mathematics you don't understand things. You just get used to them.“ — John von Neumann

Finding a chain of implications that take us from our premise to the conclusion is hard.

The single most powerful tool in math is the free and clear mind. As the entire field of mathematics exists only in our collective minds, we can do whatever we want! We can perform wild thought experiments, reason about things that don’t exist, reduce premises to contradictions, and whatever.

First, we are going to familiarize ourselves with the last one: reducing premises to contradictions. This is called proof by contradiction.

Ideas first, examples second, explanations last.

The idea. Say we want to prove that A is true. If we can’t do that directly, we can always assume A to be false, then deduce that P is true for some proposition P which we know to be false. Hence, A must be true as well, otherwise, we have a contradiction.

The example. The following proof is directly from the legendary Euclid.

---

Theorem. There are infinitely many prime numbers.

---

Recall that prime numbers are positive integers that are only divisible by 1 and themselves. Such as 2, 3, 5, 7, 11, 13, 17, 23, 39, and so on.

According to the above theorem, there are infinitely many of them.

Let’s see the proof. By contradiction, as promised.