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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Simon Marynissen Feb 21 '17 at 21:38
  • $\begingroup$ Also, you can simplify your proof by using the following characterisation of well-orderings: there exists no infinite strictly decreasing sequence. $\endgroup$ – Simon Marynissen Feb 21 '17 at 21:42
  • $\begingroup$ The characterisation of well-orderings above depends on the axiom of dependent choice. $\endgroup$ – Simon Marynissen Feb 21 '17 at 21:49

Some axiom of choice is needed, since it is possible that there are sets which cannot be linearly ordered (and therefore must also be infinite).

But once you have the axiom of choice, every infinite set has a countably infinite subset. Now think, what sort of linear ordering can be made with a set which has a countably infinite subset and it is not a well-ordering?

  • $\begingroup$ 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. $\endgroup$ – math.h Feb 22 '17 at 1:55
  • $\begingroup$ You still need to linearly order the rest of $X$, though. $\endgroup$ – 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.


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.