# For- and backwards well-ordered set is finite.

I'm working on the following problem and can't seem to come up with a satisfactory proof.

Let $$X$$ be a totally ordered set which is well-ordered forwards and backwards. Show that $$X$$ is finite.

I found this saying that both statements are in fact equivalent but I couldn't find anymore resources that helped.

I'm kind of stuck because $$X$$ being well-ordered forwards and backwards means that $$\forall (A \neq \emptyset) \subset X: (\exists a_{max}, a_{min} \in A: \forall a \in A: a_{min} \preceq a \preceq a_{max})$$ But I know that having a minimal/maximal element makes no statement about the set being finite (i.e. $$[0; 1] \subset \mathbb{R}$$ has 0 as minimal and 1 as maximal element but is in fact infinite.)

So I thought about proving the contraposition: $$X$$ infinite $$\implies X$$ is not well-ordered forwards & backwards. Since $$X$$ is infinite it holds that $$\not\exists x_{max} \in X: (\forall x \in X: x \preceq x_{max})$$ because for every element we would choose as $$x_{max}$$ there always exists an $$x$$ that is bigger than $$x_{max}$$ because $$X$$ is infinite. This means that $$X$$ cannot be well-ordered forwards.

But this seems to straight forward and to informal to be correct.

I also thought about how I could use a bijection $$f: X \to \{1, \ldots, n\} \subset \mathbb{N}$$ to show that $$X$$ is finite, but I wasn't able to come up with much of anything.

Any help is greatly appreciated.

• Consider $\{ \ldots, -1, 0, 1,2 \ldots \}$. Obviously, there are non-empty subsets of it that have no least element. – Mauro ALLEGRANZA Dec 1 '18 at 13:45
• @MauroALLEGRANZA right such as the set of negative integers. I'm sorry but I don't think I follow. Are you saying my contraposition argument is in fact correct and a valid proof? – TehQuila Dec 1 '18 at 13:49

It would help you to prove the following lemma:

Lemma. Let $$(X, \preceq)$$ be a well-ordered set. Then any strictly-$$\preceq$$-descending chain $$\cdots \preceq x_{n+1} \preceq x_n \preceq \cdots \preceq x_2 \preceq x_1 \preceq x_0$$ is finite, i.e. for some $$n_0 \in \mathbb{N}$$ you have $$x_n=x_{n_0}$$ for all $$n \ge n_0$$.

This lemma implies that if $$(X, \succeq)$$ is also well-ordered, then any strictly-$$\preceq$$-ascending chain is finite, too.

Suppose that $$X$$ is well-ordered forwards and backwards, then define sequences $$x_0,x_1,\dots$$ and $$y_0,y_1,\dots$$ mutually inductively as follows:

• Let $$x_0$$ be the $$\preceq$$-least element of $$X$$ and let $$y_0$$ be the $$\preceq$$-greatest element of $$X$$.
• Given $$x_n,y_n$$. If $$X \setminus \{ x_0,\dots,x_n,y_0,\dots,y_n \} = \varnothing$$ then stop; otherwise, let $$x_{n+1}$$ be its $$\preceq$$-least element of and let $$y_{n+1}$$ be the $$\preceq$$-greatest element of the same set.

This process must eventually terminate, since otherwise $$x_0,x_1,x_2,\dots$$ is a strictly $$\preceq$$-ascending chain and $$y_0,y_1,y_2,\dots$$ is a strictly $$\preceq$$-descending chain.

• Thank you for your fast response. I'm sorry but we didn't introduce the concept of chains in my course at uni. But I imagine the lemmas proof to be something along those lines: If it were the case that $(X, \preceq)$ contained such an infinite chain, then at least some of the elements would be repeated. But then would $\preceq$ not be transitive and thus not a total order, which would be a contradiction to $(X, \preceq)$ being well-ordered. Is that correct? Thank you very much for your help. – TehQuila Dec 2 '18 at 9:11
• @TehQuila: You can ignore the word 'chain' if you like, it's not necessarily a concept that you need to have explicitly defined: all it is is a set $\{ x_0, x_1, x_2, \dots \} \subseteq X$ such that $x_{n+1} \preceq x_n$ for all $n$. If $\{ x_0, x_1, x_2, \dots \}$ is any such set, then it has a $\preceq$-least element $x_{n_0}$ since $\preceq$ is a well-order. But then $x_n \preceq x_{n_0}$ for all $n \ge n_0$ by definition of the set, and $x_{n_0} \preceq x_n$ for all $n \ge n_0$ since $x_{n_0}$ is a $\preceq$-least element of the set. – Clive Newstead Dec 2 '18 at 13:14
• Ok it took me a while but I got it now. This is actually really elegant, thank you very much for taking the time to explain in such detail! Once I got everything together it really hit me. :D – TehQuila Dec 2 '18 at 15:37

Any infinite subset of a linearly ordered set contains a sequence $$\{x_n: n \in \omega\}$$ that is either increasing ($$x_n < x_{n+1}$$ for all $$n$$) or decreasing ($$x_n > x_{n+1}$$ for all $$n$$). See this post for a proof or be fancy and apply the Ramsey theorem on finitely coloured graphs on $$\aleph_0$$ many points.

A decreasing sequence (as a set) has no minimum, and an increasing one has no maximum so contradicts the backward well-order.

So the set cannot be infinite.

Every nonempty subset of your totally ordered set $$X$$ has a least element and a greatest element. Assume for a contradiction that $$X$$ is infinite.

Let $$A$$ be the set of all elements of $$X$$ with an infinite number of successors, and let $$B$$ be the set of all elements with an infinite number of predecessors. Since $$X$$ is infinite, each element of $$X$$ belongs to $$A$$ or $$B$$ (or both), so $$X=A\cup B$$. At least one of the sets $$A$$ and $$B$$ is nonempty; without loss of generality, we may assume $$A$$ is nonempty.

Let $$a$$ be the greatest element of $$A$$, and let $$b$$ be the least element greater than $$A$$. Then $$a$$ has infinitely many successors, since $$a\in A$$; while $$b$$ has finitely many successors, since $$b\notin A$$. Therefore there infinitely many successors of $$a$$ which are not successors of $$b$$. Choose two of them, $$c$$ and $$d$$. We may assume $$c\lt d$$, so that $$a\lt c\lt d\le b$$. But $$a\lt c\lt b$$ contradicts the fact that $$b$$ is the least element greater than $$a$$.