I was reading a Proof concerning the well ordering of the natural numbers, but I don't quite understand what is going on. I'm a complete beginner concerning rigorous mathematics so maybe I'm missing out the obvious.
We defined that a set $X$ is well-orderd if every non-empty subset contains a first element. We use a proof by contradiction where we assume the existence of a subset M of the natural Numbers that has no first element.
Here is the complete Proof:
Let $M \subset \mathbb{N}$ be non-empty. We assume $M$ has no first element. Let $$L := \{n \in \mathbb{N}\ |\ \forall m \in M, n\leq m\}.$$
Now:
1.) $1 \in L$ (why?)
2.) $n \in L \Rightarrow n+1\in L$
It follows that $M = \emptyset$.
Could someone please enlighten me? For example, I don't know why 1 should be in L, does every subset of the natural numbers has to contain 1? I mean sure, 1 is the smallest element so it is less than or equal to every element from M.
Best Answer
Here's a a rundown of the proof. I'll make use of the following (along with the supposition that $\mathbb{N}$ here does not conatin $0$):
So let's tackle the two claims:
1) $1 \in L$. To see this, suppose towards a contradiction that $1 \not \in L$. By the definition of $L$, this means that there is $m \in M$ such that $1 > m$. But, by the two facts above, this is absurd. So we have $1 \in L$.
2) Next, suppose $n \in L$ and consider $n+1$. Suppose, again towards a contradiction, that $n+1 \not \in L$. Then there is some $m \in M$ such that $n+1 > m$. But, since $n \in L$, it follows by the definition of $L$ that $n \leq m$, that is, either $n < m$ or $n =m$. If $n=m$, then $n$ is the smallest element of $M$, contradicting the hypothesis that $M$ has no smallest element. If $n <m$, we have $n < m < n+1$, contradicting Fact 3. Either way, we reach a contradiction. So $n+1 \in L$, as required.
So the proof rests on the three facts above (plus, of course, the principle of induction). How can you prove those? Well, they can be obtained by reasoning from the definition of $<$, namely $n < m$ iff there is a $z$ such that $n+z =m$.