# Prove the Well Ordered Theorem with mathematical induction.

More formally stated: "Suppose $A \subset C$ with $|A|=n$. Then one could identify each element in $A$ as $a_1,...,a_n$ such that $a_i<a_{i+1}$ for $1\leq i\leq n-1$."

Sorry if the $\LaTeX$ is not up to par, but I'm still a novice at typesetting.

Anyway, this is what I understand to be a way to state the well ordered theorem for a finite set through induction. I had the idea that one could try and examine each element and put them in order since the set isn't infinite, but it might not be the case. This may seem trivial, but I just have a difficulty wrapping my head around it. Help is appreciated.

-
I may be incorrect but I thought you needed the existence well ordering as a property in your set to perform induction over that set first, since you need to define a "first, second third... nth" element before you could act. That said I think you can get the well ordering without induction in this case by simply defining a function from A to N. – Vilid Sep 17 '12 at 21:03
@Vilid Yes I understand what you mean. I read about this here: proofwiki.org/wiki/… still they prove induction is true previously, but for an infinite set. – Casquibaldo Sep 17 '12 at 21:06

Let $\bar{n} = \{1, ..., n\}$. If you know that $\mathbb{N}$ is a well-ordering, then the ordering restricted to $\bar{n}$ is a well-ordering for each $n \in \mathbb{N}$. By the way, you can show that the well-ordering of $\mathbb{N}$ is equivalent to induction on $\mathbb{N}$.
If $A$ is a finite set, then there exists a bijection $f : A \rightarrow \bar{n}$ for some $n \in \mathbb{N}$.
Define the ordering $\prec$ on $A$ by $a \prec a'$ if and only if $f(a) <_\mathbb{N} f(a')$. Then $\prec$ is a well-ordering of $A$.