Showing that $\Bbb{N}$ is well-ordered. Do I need an arbitrary case?

Question

proof (The way I did it):

Base Case: Consider $\{1,2\}$. Clearly $1<2$ by the natural order in $\Bbb{N}$.

Inductive case: Suppose $\{1,2,...,n\}$ is well-ordered then since $n<n+1$, the set $\{1,2,...,n,n+1\}$ is also well-ordered due to transitivity in $\Bbb{N}$.

My professor told me that I need to use an arbitrary well-ordered subset of $\Bbb{N}$ in my inductive case. But, I do not think that we need to because any arbitrary case will be "eventually" be covered by the method of induction I used above, for some $m+1\in\Bbb{N}$. What am I missing here?

Answer 1

Let's see what you have to show to prove that $\mathbb{N}$ is well-ordered.

Definition: A set $A$ is called well-ordered if there exists a total ordering $\leq_*$ on $A$ such that any subset $B \subseteq A$ has a minimum element with respect to $\leq_*$.

Now what does mathematical induction says?

It says that suppose I have a set of statements $P(n)$ for each $n \in \mathbb{N}$ and I know that $P(1)$ is true. If $P(n) \implies P(n+1)$ then $P(n)$ is true for any natural number $n \in \mathbb{N}$.

So, what you have proved is that any finite set of the form $\{1,2,\cdots,k\}$ is well-ordered. Of course, there are many subsets in $\mathbb{N}$ that are not necessarily of this form. But let's ignore this issue for now because it can be fixed easily.

Let's say that we have proved $P(k)=\{ \text{a set of size k is well-ordered}\}$ is true by mathematical induction using your method. Can we conclude that a set of infinite cardinality is well-ordered? No! Because infinity is not a natural number. So, you still need to prove that sets of infinite cardinality in $\mathbb{N}$ are well-ordered to have demonstrated that "any subset of $\mathbb{N}$" has a minimum element.

Here's a proof:

Claim I: Any non-empty subset of natural numbers with finite cardinality is well-ordered.

Proof: we will use mathematical induction on the size of subsets $\emptyset \neq A \subseteq \mathbb{N}$ where $|A| < \infty$.

If $n=1$, then we have only one element in the set and it is trivial. If $|A|=n+1$, consider $B \subset A$ which is obtained by removing only one element from $A$, i.e. $B \cup \{a\}=A$. Since $|B|=n$, it has a minimum element $b_0$. Now choose $a_0 = \min\{a,b_0\}$. Q.E.D

Claim II: Any non-empty subset of natural numbers, even with infinite cardinality is well-ordered.

Proof: the idea of the proof for this part was first posted by William Elliot. Take $\emptyset \neq A \subseteq \mathbb{N}$. Since $A$ is non-empty, there exists some natural number $m \in A$. Consider $B=\{n \in A: n \leq m\}$. $B$ has at most $m$ elements and therefore is finite and has a minimum: $b_0$. Now notice that $A = B \cup B^c$ where $B^c$ is the complement of $B$, i.e. $B^c = \{ n \in A: n > m \}$.

Now, $b_0$ is also the minimum of $A$ because any element $a$ in $A$ is either in $B$ or $B^c$. If $a$ is in $B$, then $b_0 \leq a$. If $a$ is in $B^c$, then $a > m$ and $b_0 \leq m$ and again we see that $b_0 \leq a$. Q.E.D.

Answer 2

I'm not entirely sure how you're showing well-orderedness. A total order is a well-ordering if every non-empty subset of the set has a minimum element. You haven't really established this. For example, how would your argument establish that $\lbrace 2, 3\rbrace$ has a minimum? It doesn't fit with any of the sets $\lbrace 1, 2, \ldots, n \rbrace$, and it's not clear how it inherits structure from supersets like $\lbrace 1, 2, 3 \rbrace$ from your argument alone.

Then there's the problem that you're missing out on infinite sets. Let's say that you have established that the set $\lbrace 1, \ldots, n \rbrace$ is well-ordered for all $n$. How does this prove that $\mathbb{N}$ is well-ordered? You haven't accounted for any infinite sets. For example, the set $\mathbb{N}$ itself is not a subset of $\lbrace 1, \ldots, n \rbrace$ for any $n$, so why must it have a minimum?

No, even if you nest countably many well-ordered sets, this does not produce a well-ordered set necessarily. For example, the sets $$\lbrace -n, -n + 1, \ldots, n - 1, n \rbrace$$ are well-ordered and will union to give $\mathbb{Z}$, which is not well-ordered.

So, in short, yes you need an arbitrary case.

Answer 3

First show that every finite subset of $\Bbb{N}$ has a minimum.
This OP has done.

Assume $A \subseteq \mathbb{N}$ is not empty. Pick any $n$ in $A$.
Show $B = \{ k \in A: k \leq n \}$ is a finite set.
Thus $B$ has a minimum $m$. Show $m$ is a minimum in $A$.