Mostrar que un conjunto es finito si y solamente si cada orden lineal en es un bien pedido

Question

Demostrar que un conjunto es finito si y sólo si cada lineal pedido es un buen orden

Lo que he hecho hasta ahora:

$\Rightarrow$: Vamos a $(X,\prec)$, donde X es finito y $\prec$ es lineal pedido. Considerar un subconjunto $A\subset X$. Desde $X$ es finito, $A$ es también finito. Por lo tanto, existe cierta $f:I(x)\rightarrow A$ bijective, donde $I(x)$ es un subconjunto finito de los números naturales. Redefinimos $f$, de tal forma que es una función creciente. Dado $a,b\in A$,$f(m)=a$$f(n)=b$, para algunas de las $m,n\in I(x)$. Desde $\prec$ es lineal pedido tenemos que $a\prec b$ o $b\prec a$. Teniendo en cuenta el mest caso de $a\prec b$ (es decir, $f(m)\prec f(n)$), redefinimos $f$ si $n<m$, y poner $f(m)=b$$f(n)=a$. De igual manera debemos redefinir $f$$b\prec a$. Haciendo este proceso para todos los pares de $a,b\in A$, nos aseguramos de que $f$ es creciente y, recordando que cada subconjunto de los números naturales tiene un minmal de origen, tenemos que $A$ también tiene un mínimo elemento. Desde $A$ fue arbitraria, esto demuestra que $\prec$ es buena ordenación.

Eso es lo que yo podía hacer. Es correcto? Consejos sobre el $\Leftarrow$ parte?

Answer 1

Se necesita algún axioma de elección, ya que es posible que existan conjuntos que no puedan ordenarse linealmente (y, por lo tanto, también deben ser infinitos).

Pero una vez que tienes el axioma de elección, cada conjunto infinito tiene un subconjunto infinitamente contable. Ahora piense, ¿qué tipo de ordenamiento lineal puede hacerse con un conjunto que tiene un subconjunto infinitamente contable y no es un ordenamiento ordenado?

Answer 2

Para la dirección opuesta asumir que $X$ es infinito y que cualquier orden lineal en que es un bien de orden. Vamos a tratar de construir un infinito descendiente de la cadena. Elegir un orden lineal $<$$X$, la hipótesis es un bien de orden. Tomar un conjunto finito $W_0$ deje $a_0\in W_0$ ser la parte inferior del elemento de acuerdo a $<$. Desde $X$ es infinito puede elegir otro subconjunto finito $W_1$ $X$ disjunta de a $W_0$. Deje $a_1$ ser la parte inferior de $W_1$ según $<$, Ahora compare $a_0$$a_1$. Si $a_0<a_1$,, el cambio de ellos.

Continuando con esta manera de construir una secuencia $a_n$ que es un infinito descendente de la cadena.