For- and backwards well-ordered set is finite.

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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