A Kick in the Discovery

Ok, forewarning this will be covering deeeeeep mathematics. For those who already know of induction and/or well-ordering this’ll be a treat! We are going to describe the connections between these two concepts. For those who have not heard of either induction and/or well-ordering let me describe them to you.

The Well-Ordering Principle

First, let’s agree on calling the set of counting numbers {1,2,3,4,…} the natural numbers and denote them by a fancy-looking N that’s almost like two N’s written on top of each other: . With that taken care of, what would happen if we took some non-empty subset of these numbers? For example, the even numbers {2,4,6,8,…}. Or, maybe {5,120,200}. Or, maybe just the number {10}.

Notice how all of the sets have a smallest number in them. The number 2 is the smallest even number, 5 is the smallest number in {5,120,200}, and 10 is the smallest number of {10}.

Challenge: Can you think of a non-empty subset of that does NOT have a smallest number?

I sure hope not, since the well-ordering principle says you can’t!

Well-Ordering: Every non-empty subset of number(s) from contains a smallest number. Simple.

Some people when hearing this for the first time say something along the lines of, “That’s so obviously true! why is is a principle?” But this misses the point in my opinion. A goal of mathematics is to deduce truth from truth, in a manner of speaking. In order to do so, we must try to come up with some ground truths that are hard to argue with. Things that we can take to be like Newton’s laws of mechanics, but for math. And well-ordering can be one of these laws or axioms of mathematics.

Since almost no one I know has issues with the well-ordering principle we could take it to be one of those ground truths we just mentioned. Then we might try to find out what it might imply.

The Principle of Induction

Ugh… another principle… Yes, but this one seems to have more substance.

I already discussed induction in a recent blog post, here. So I recommend you check that one out if you are unfamiliar with induction. But, just in case you don’t want to have to read a whole other blog post here’s a brief description:

Induction states: Let the proposition that we want to prove be denoted P(n). If (i) If P(1) is true and (ii) P(n) being true implies the truth of P(n+1), then induction states that P(n) is true for all natural numbers in .

Why might this principle be true?

Well, if you show P(1) is true then we know at least the proposition with n=1 is true. But, if you show P(n) implies P(n+1) for any n, then P(1) implies P(2). And P(2) implies P(3). And P(3) implies P(4). And so on until … And P(100) implies P(101). And to infinity and beyond!

Thus, we build an infinite chain of implications. And induction tells us this is enough to conclude P(n) is true for all natural numbers.

Wow! Fantastic!

Many people would say that induction is less intuitive and less obvious than the well-ordering principle (including this author!). But there’s a surprising connection between the two!

The Connection

Before I tell you what the connection is, what would you guess? Does one imply the other? If so which implies the other? If not, then what’s the connection?

Keep thinking!

What if I told you that induction and well-ordering are equivalent! Meaning one implies the other! Neither is deeper than the other! They are one and the same (only in disguise!!!!!)

What?!?

How?!?

Huh?!?

I know, I know it’s awesome!

Let’s see why!

The Proof

So, how does one prove that statement A is equivalent to statement B?

You need to show that you can: assume A and deduce B or assume B and deduce A. For us, we need to show assuming well-ordering, induction works. Then, assuming induction, well-ordering is true!

Well-Ordering Implies Induction

Ok, what are we assuming? We assume: Every non-empty subset of number(s) from contains a smallest number.

What do we prove? We prove: For any proposition P(n) where (i) P(1) is true and (ii) P(n) being true implies the truth of P(n+1), then it must be that P(n) is true for all natural numbers in .

Let’s begin.

Let P(n) be a proposition such that (i) P(1) is true and (ii) P(n) being true implies the truth of P(n+1). And let’s focus our attention on the set of numbers n where P(n) is true and the set of n where P(n) is false, (for those unfamiliar with set notation check out the footnote)¹

,

.

*****Note that ‘means’ that F is the complement of T. This is a fancy mathy way of saying that: (i) T and F have no overlapping elements and (ii) every natural number is in either T or F. A succinct way of saying this is: any natural number is either in T or F but not both!*****

First, observe that we know at the very minimum that , since we assumed that P(1) is true. We also know, since any is also in . And likewise, .

Using our newly minted sets T and F, we are aiming to prove that and F is empty. Since this would imply that P(n) is true for all natural numbers. How might we do this?

We will assume that F is not empty and see if we can find a contradiction.

So, assume for the hope of a contradiction that F is not empty. Now guess what? We already knew that and now we know F is nonempty. Seems like the right time to use well-ordering huh?

By well-ordering there must be a smallest natural number in F, call it . But since m is in F it means that P(m) is false. Or, that m is not in T. Observe that this implies that m-1 is not in T either, for if it was, then P(m-1) being true would imply that P(m) is true (recall we assumed P(n) implies P(n+1)) and hence m is in T, which it’s not. We conclude m-1 is not in T, so it’s in F. But and . This contradicts that m was the smallest element in F! Wahooooo we found our contradiction. Our assumption that F was nonempty is false. Thus, F is empty, and every natural number is in T. Thus P(n) is true for all natural numbers. ie, the principle of induction works.

Induction Implies Well-Ordering

Ok, what are we assuming? We assume: For any proposition P(n) where (i) P(1) is true and (ii) P(n) being true implies the truth of P(n+1), then it must be that P(n) is true for all natural numbers in .

What do we prove? We prove: Every non-empty subset of number(s) from contains a smallest number.

We’re basically going to use a proof by induction to show that every non-empty subset of contains a smallest element.

Let’s begin.

Suppose some set S is both non-empty and a subset of . These are the two assumptions used in well-ordering. We aim to show that there is a least number in S.

How might we go about showing that there is a least element?

This is hard to do. A much simpler thing to show is a contradiction if S did not have a least element!

So, in a similar way as in the above proof, assume for the hope of a contradiction that did not have a least element. Recall, we want to use induction. This is our guiding light in this proof.

Since in order to use induction, we need to find a proposition that has the properties that P(1) is true, and P(n) implies P(n+1). A first guess at what P(n) might be something along the lines of: let P(n) be true if n is in . However, this cannot be the case, since we want P(1) to be true and this would imply that 1 is in . And since 1 is the smallest natural number in general 1 would have to be the smallest element in . But we assumed that did not have a smallest element.

Ok, so 1 is not in . So maybe P(n) has to do with numbers not in . But we also want to somehow capture that there is no minimum element in . For these reasons, it turns out to be more useful to consider the proposition:

P(n) is true when all natural numbers smaller than or equal to (ie ) are not in .

The same statement, but positive is

P(n) is true when all natural numbers smaller than or equal to (ie ) are in .

Where the set is the complement of (the set contains all numbers that are not in and in ).

Observe that if, say P(10) is true it must be true that P(1), P(2), … , P(9) are all true too. Since P(10) implies that every number less than or equal to 10 is in . Therefore P(n) has the property that if P(n) is true then P is also true for all numbers less than n.

Let’s check P(1). Since we already concluded that 1 is not in we know 1 is in , and there are no natural numbers smaller than 1. Thus, P(1) is true! Boom Base Case Done!

What’s left? The induction hypothesis and induction step.

So, let’s assume that P(n) is true which implies all are in . Does this imply that P(n+1) is true too? Or, are all in ? Well, imagine that n+1 was not in . This would imply that n+1 is in and by assumption no number less than n+1 is in . Thus, n+1 is the smallest number in . BOOOOOM contradiction! We assumed there is no smallest number in , so we conclude n+1 must not be in , or n+1 is in which in turn tells us P(n+1) is true. We just showed P(n) implies P(n+1). Boom Inductive Step DONE!

So, we conclude by induction that P(n) is true for all natural numbers . Therefore, every natural number is in , or no numbers are in . Thus, is empty! BOOM ROASTED … oops I meant BOOM CONTRADICTION! Since we assumed that was nonempty way back at the start. Thus, we conclude that must have a minimum element!

Closing Remarks

Wow, that was a journey huh? Let’s recap what we proved. We proved that The Well-Ordering Principle and The Principle of Induction are one and the same. What does this mean exactly? It means that they both imply each other. “Ok? So?” I hear you say. The upshot is that you can take either as your starting point and prove the other. So, if you were trying to build a mathematical theory, you could take either to be a law of math (an axiom for those who know that word) and deduce the other.

One lesson I took away from this was how there are many starting points to build a theory. One may be incredibly obvious and almost not worth stating (cough cough I’m looking at you well-ordering). And the other, very strange upon first encounter (induction anyone). But in the end, they are the same. They carry the same weight!

Next time you use induction remember that you might really be relying on the fact that all non-empty subsets of have a least element!

Footnote

1. Pro Tip: is math symbols for that the number n is in . And the colon : is math symbols for such that. Altogether we would read as: T is the set of all natural numbers n such that P(n) is true. ↩︎