0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Consider $\{ \ldots, -1, 0, 1,2 \ldots \}$. Obviously, there are non-empty subsets of it that have no least element. $\endgroup$ – Mauro ALLEGRANZA Dec 1 '18 at 13:45
  • 1
    $\begingroup$ @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? $\endgroup$ – TehQuila Dec 1 '18 at 13:49
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – TehQuila Dec 2 '18 at 9:11
  • $\begingroup$ @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. $\endgroup$ – Clive Newstead Dec 2 '18 at 13:14
  • $\begingroup$ 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 $\endgroup$ – TehQuila Dec 2 '18 at 15:37
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.