# well-ordering principle and induction in the natural numbers

As this is the first post in this kind-of mindset let me explain why I may post something like this from time to time.

Well I have a degree in math (a German Diplom) but took the easy (software-developer) route instead of going into this – why? Well because while having some skill in those kind of stuff I just lack the genius or determination to really become a (research-)mathematician and I just did not want to go along the finance road. As I programmed since my youth this one was a no-brainer and get’s me enough in both the money and my interests to keep me going.

But at the same time I cannot stop myself from feeling some kind of failure (programming and all this stuff might seem complicated to some people but it certainly ain’t math) and this might be why I’m so interested in functional programming and all this Haskell-Voodoo.

Anyway I try to – at least – keep my undergraduate skills (I never reached the frontier and you just forget so much in a few years that I never will be able to do real stuff again – if I ever have) so I take some time with the simpler stuff on occasion.

So I see some interesting – while not overcomplicated – stuff from time to time – and so did with the simple observation that the well-ordering principle and the induction principle are equal for the natural numbers.

Well of course everyone know that both is true (well you might not know the names but you will know the concept – both are very intuitive and will be taken as granted – Axioms – in some introductions.

But there I was – for the first time seeing this and in this cases I just cannot stop myself from taking a pen and get some good old math going.

Of course a simple Google search would have been enough (just saw that this is even proofed on the wiki-article for one direction) – but where is the fun?

So let’s go…

# What the heck is “well-ordering”?

Well as I said: it’s a impressive name for a simple thing (a feat. often found in math) – a mathematician calls a set $S$ well-ordered if every subset $U$ of it has a least element $u \in U$ – and here “least” means that for each $x \in U$, $u \leq x$.

For many sets like the real numbers this is certainly false ( $\left\{ \frac{1}{1}, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, .. \right\}$ ).

For the set of all natural numbers (I will include 0) this is very intuitive (and so is the proof below).

# Induction?

Depending on weather you heard of this before it’s either easy or might sound hard but it really is nothing else but the way we construct the numbers ourselves by starting at zero and “counting up” – you can define the naturals in the same way (see Peano Axioms).

Now Induction is based on this – suppose you have a proposition on the naturals $P( n )$. If you have

$P( 0 )$ is true and

from $P( n )$ is always follows that $P (n+1)$ is true as well (the induction step) the principle tells you that [late]P[/latex] is true for all natural numbers.

# These both are really the same…

Now the “lemma” for today just states that those two are equivalent (one follows from the other). So we have to proof the two implications…

## given the well-ordering the induction-principle follows

Let $P$ given as defined above and suppose that the induction principle is false

Define a set $S$ of natural numbers by

$S = \left\{ n : P( n ) false \right\}$.

Because we assume that the principle is false this set must be non-empty and now the well-ordering of the natural numbers tells us that there is a minimum in this set: $m \in S$.

Because $P( 0 )$ is true $m$ cannot be 0. But if it’s not 0 then $n = m-1$ is a natural number and not in $S$. But now we know that $P( n )$ is true and therefore $P( m ) = P (n + 1)$ must be true as well in contrast to our assumption – which must now be false and the Induction principle must hold.

## given the induction-principle the well-ordering follows

Let $S$ be a non-empty subset of the natural numbers and assume that contrary to the well-ordering there is no smallest element in it.

Define $P( n )$ to be true iff $\left\{ 0,..,n \right\} \cap S = \emptyset$.

As 0 is certainly smaller than every other natural number, 0 cannot be in $S$ and so $P( 0 )$ is true.

If now $P(n)$ is true then $n+1$ cannot be in $S$ as this now surely would be the smallest element in it (ever natural number smaller than this certainly not in $S$) so $P(n+1)$ is true as well and the induction-principle tells us that indeed $P$ is true for all natural numbers implying that $S$ must be empty … and again we must throw away our assumption as false and got our proof.

## Note to the reader…

Did you like this one? I mean really? Give me some feedback