Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer 1

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.