For- and backwards well-ordered set is finite.

elementary-set-theorywell-orders

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.

Best Answer

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.

Related Question