# Show that a set is finite if and only if every linear ordering on it is a well-ordering

Show that a set is finite if and only if every linear ordering on it is a well-ordering

What i have done so far:

$\Rightarrow$: Let $(X,\prec)$, where X is finite and $\prec$ is linear ordering. Consider a subset $A\subset X$. Since $X$ is finite, $A$ is also finite. Hence, there exists some $f:I(x)\rightarrow A$ bijective, where $I(x)$ is a finite subset of the natural numbers. We redefine $f$ in a such way that it is an increasing function. Given $a,b\in A$, we have that $f(m)=a$ and $f(n)=b$, for some $m,n\in I(x)$. Since $\prec$ is linear ordering we have that $a\prec b$ or $b\prec a$. Considering the firt case $a\prec b$ (ie, $f(m)\prec f(n)$), we redefine $f$ only if $n<m$, and put $f(m)=b$ and $f(n)=a$. Similarly we redefine $f$ for $b\prec a$. Doing this process for all pairs $a,b\in A$, we ensure that $f$ is increasing and, recalling that every subset of the natural numbers has a minmal ement, we have that $A$ also has a minimal element. Since $A$ was arbitrary, this proves that $\prec$ is well-ordering.

That's what i could do. Is it correct? Any hints on the $\Leftarrow$ part?

• For $\Leftarrow$: If $\prec$ is a linear order on $X$, then $\succ$ is also a linear order. By hypothesis they are both well-orderings. You can try to show that only finite sets satisfy this. – Simon Marynissen Feb 21 '17 at 21:38
• Also, you can simplify your proof by using the following characterisation of well-orderings: there exists no infinite strictly decreasing sequence. – Simon Marynissen Feb 21 '17 at 21:42
• The characterisation of well-orderings above depends on the axiom of dependent choice. – Simon Marynissen Feb 21 '17 at 21:49

• What i tought so far: in order to prove that a linear ordering $\prec$ is not a well-ordering, we must exibit a subset wich has no minimal element. So, considering $X$ infinite and $V\subset X$ countably infinite, we define an ordering $<$ on it by putting $f(x_1)<f(x_2)$ if and only if $x_2<x_1$, where $f(x_1),f(x_2)\in V$ and $x_1,x_2\in N$. Supposing that $V$ has a minimal element $b=f(m)$, then $b<f(x)$ for all $f(x)\in V$ would imply $x<m$ for all $x\in N$. Hence this would imply that $N$ is limited, which is an absurd. – math.h Feb 22 '17 at 1:55
• You still need to linearly order the rest of $X$, though. – Asaf Karagila Feb 22 '17 at 6:49
For the opposite direction assume that $X$ is infinite and that any linear order on it is a well-order. Let's try to build an infinite descendant chain. Choose a linear order $<$ on $X$, the by hypothesis it is a well-order. Take a finite set $W_0$ let $a_0\in W_0$ be the bottom element according to $<$. Since $X$ is infinite you can choose another finite subset $W_1$ of $X$ disjoint from $W_0$. Let $a_1$ be the bottom of $W_1$ according to $<$, Now compare $a_0$ and $a_1$. If $a_0<a_1$, then exchange them.
Continuing this way you build a sequence $a_n$ which is an infinite descending chain.