I'm trying to solve problem 4.4.8 of Hrbacek & Jech's Introduction to Set Theory. The problem reads in part,

Let $(A,<)$ be linearly ordered. Define $\prec$ on $\operatorname{Seq}(A)$ by: $\langle a_0, \dots, a_{m-1} \rangle \prec \langle b_0, \dots, b_{n-1} \rangle$ if and only if there is $k < n$ such that $a_i = b_i$ for all $i < k$ and either $a_k < b_k$ or $a_k$ is undefined (i.e. $k = m < n$)... If $(A, <)$ is well-ordered, $(\operatorname{Seq}(A), \prec)$ is also well-ordered.

This looks to me like the lexicographic ordering of dictionary words, where a finite sequence that extends a shorter sequence comes after in the ordering. But then the sequence of strings $ab > aab > aaab > \cdots$ is an infinite decreasing sequence of words in $\operatorname{Seq}(A)$, which I think proves that $\operatorname{Seq}(A)$ cannot be a well ordering.

I must be making a simple mistake here, but in two days I haven't managed to find it! Can someone point out where I am going wrong?


1 Answer 1


You are correct, and there is an error in the definition of $\prec$ that you have written. The definition of $\prec$ should instead require $a_i=b_i$ for all $i\color{red}>k$ (meaning that for each $i>k$, either $a_i$ and $b_i$ are both defined and equal or they are both undefined). That is, you should use the reverse lexicographic order, where you start from the end of the sequence instead of the beginning. (Note in particular that if $n>m$ then always $\langle a_0, \dots, a_{m-1} \rangle \prec \langle b_0, \dots, b_{n-1} \rangle$ by taking $k=n-1$.)


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .