Prove the Well-Ordering Principle by Mathematical Induction.

Question

So I want to prove that every non-empty subset of the natural numbers has a least element. I used induction but I'm not sure if doing that proves the statement for infinite subsets of $\mathbb{N}$. Here is my attempt at the proof please point out any errors.

Proof:

Let $X$ be a non-empty subset of $\mathbb{N}$

P(1): $X = \{x_1\}$, then $x_1 \leq x_i$ for all $x_i \in X$ - clearly.

Assume P(k): $X = \{x_1, \dots x_k\}$, then $\exists n\in X$ such that $n\leq x_i$ for all $x_i\in X$.

P(k+1): $X' = \{x_1, \dots x_k, x_{k+1}\}$, then by the induction hypothesis $\exists n\in X'$ such that $n\leq x_i$ for all $x_i\in X'$ and $1\leq i\leq k$

By trichotomy of order, it follows that $x_{k+1} > n$ or $x_{k+1} \leq n$.

If $x_{k+1} > n$, then $n\leq x_i$ for all $x_i \in X'$.

If $x_{k+1} \leq n$, then $x_{k+1} \leq x_i$ for all $x_i\in X'$.

I.) Does this prove the statement for a finite subset of $\mathbb{N}$?

II.) Do I have to do something different to prove it for an infinite subset?

Answer 1

Allow me to rewrite your proof in a slightly different way.

Base case: (singleton)

$$P(1): X=\{x\}\implies \min_{x\in X}(x)=x\in X$$ This is trivial.

Inductive step:

$$P(k)\implies P(k+1):Y=X\cup\{z\}\implies \min(\min_{x\in X}(x),z)=\min_{x\in X\cup\{z\}}(x)\in X\cup\{z\}$$

The minimum of the augmented $X$ is either the minimum of $X$ or the added element, in both cases an element of the augmented $X$.

---

Anyway the proof is not valid for infinite sets because no property of the underlying set ($\mathbb N$) appears and the same proof applied on $\mathbb Z$ would conclude wrongly.

Answer 2

It's a good proof. It just misses a few details in order to be perfect:

1. You should redefine $P(k)$ as $X = \{x_1, \dots x_k\}$, then $\exists n\in \{1, ..., k\}$ such that $x_n\leq x_i$ for all $x_i\in X$. The reason to do so is that the well-ordering condition states not only that any set $X$ must be lower bounded, but also that it is lower bounded by one of its elements.

2. Your proof ensures the property for finite sets. You can use it to derive the property for infinite sets. Fix any set $X$ and consider, for any $n\in\mathbb N$, $X_n = X\cap\{1, ..., n\}$. Since $X=\bigcup_{n\in\mathbb N} X_n$ and $X\neq\emptyset$, there exists $n\in\mathbb N$ such that $X_n\neq\emptyset$. Then, by your proof, there exists $x\in X_n$ such that $$ x\leq u,\ \forall u\in X_n. $$ Moreover, if $u\in X\setminus X_n$, we have, in particular, that $u\notin\{1, ..., n\}$, so $$x\leq n< u.$$ Therefore, $$ x\leq u,\ \forall u\in X, $$ and the property is proved for infinite sets, as well.