Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $(A,<)$ be well-ordered set, using <, how can one define well-order on set of finite sequences?

(I thought using lexicographic order)

Thank you!

share|cite|improve this question
What's the problem with the lexicographic order? – Isaac Solomon Jan 5 '13 at 0:32
Haim told me to say hi. :-) – Asaf Karagila Jan 5 '13 at 0:34
@AsafKaragila, now his question are famous! :) – 17SI.34SA Jan 5 '13 at 0:45
I would have written better questions! :-) – Asaf Karagila Jan 5 '13 at 0:46
up vote 3 down vote accepted

The lexicographic order is fine, but you need to make a point where one sequence extends another -- there the definition of the lexicographic order may break down. In this case you may want to require that the shorter sequence comes before the longer sequence.

Generally speaking, if $\alpha$ and $\beta$ are two well-ordered sets, then we know how to well-order $\alpha\times\beta$ (lexicographically, or otherwise). We can define by recursion a well-order of $\alpha^n$ for all $n$, and then define the well-order on $\alpha^{<\omega}$ as comparison of length, and if the two sequences have the same length, $n$, then we can compare them by the well-order of $\alpha^n$.

share|cite|improve this answer

Your Answer


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.