Supongamos que $<$ es un orden parcial en un conjunto de $A$. Demostrar que existe un orden lineal $<'$ $A$ tales que para todos los $x,y \in A$, si $x < y$ y $x <' y$.
Por favor alguien me da una prueba simple.
Respuestas
¿Demasiados anuncios?
Jim Petkus
Puntos
3447
Edit: el resultado que usted desea que se conoce como el fin de la extensión de principio. El quid del argumento es mostrar que una extensión máxima de que la primera orden es un orden total. Las verificaciones que conduce a la aplicación de Zorn son de rutina.
El conjunto de parcial de las órdenes en $A$ está parcialmente ordenado por: $<$ no es mayor que $<'$ si $x<y\Rightarrow x<'y$.
El conjunto de parcial de las órdenes en $A$ que se extienden (es decir, no serán inferiores) $<$ no está vacía, por supuesto. Si $(<_i)_i$ es una cadena de tales parcial de las órdenes, a continuación, definir $$ x<'y\qquad\mbox{si}\qquad \existe i\;\;x<_iy. $$ Este es un límite superior para la cadena, y de nuevo una extensión de la inicial $<$.
Por Zorn, existe una máxima tal orden parcial $<_m$. Vamos a mostrar que es total.
Supongamos por contradicción que $x_0\not<_m y_0$$y_0\not<_mx_0$. Definimos una relación binaria en a $A$ como sigue: $$ x R y\qquad\mbox{si}\qquad x<_mi\quad\mbox{o}\quad\{x<_mx_0\;\mbox{y}\;y_0<_mi\}. $$ Es claramente reflexivo. También es transitivo. Hay cuatro casos a considerar, dado $x Ry$$yRz$. El último no es posible por $y_0\not<_mx_0$. Por definición, $xRy$ siempre $x<_my$, e $x_0Ry_0$. Si $R$ fue un fin de la relación (es decir, antisimétrica, que es la única cosa que no he comprobado), sería una estricta extensión de $<_m$, contradiciendo la maximality de este último. Por lo tanto, $R$ no es antisimétrica, por lo que no existe $a\neq b$ tal que $aRb$$bRa$. De nuevo, dada la definición de $R$, hay cuatro casos a considerar:
1) $a<_mb$$b<_ma$: esto implica $a=b$ por antisymmetry de $<_m$, imposible.
2) $a<_mb$$b<_mx_0$$y_0<_ma$: a continuación, $y_0<_ma<_mb<_mx_0$ por lo tanto $y_0<_mx_0$, imposible.
3) $a<_mx_0$$y_0<_mb$$b<_ma$: a continuación, $y_0<_mb<_ma<_mx_0$ por lo tanto $y_0<_mx_0$, imposible.
4) $a<_mx_0$$y_0<_mb$$b<_mx_0$$y_0<_ma$: a continuación,$y_0<_ma<_mx_0$$y_0<_mx_0$, imposible.
Hemos llegado a la deseada contradicción, por lo $<_m$ es un orden total en $A$ extender $<$.
Moralmente, lo que quieres hacer es agregar fuertes desigualdades entre los elementos que no son distinguibles por $<$, y dejar todo lo demás como está.
Formalmente, las cosas podrían obtener un poco menos agradable, y algunas aplicaciones del axioma de elección no puede ser evitado, creo. Usted podría utilizar Kuratowski-Zorn lema para imitar inductivo de construcción. Deje $Ord$ ser parte de la familia de parcial de las órdenes $<'$ $A$ que para cualquier $x,y$ si $x < y$ $x <' y$ (pero podría ocurrir que el orden parcial $<$ no distingue $x$$y$, es decir, $x \not < y$ $y \not < x$ - - - pero $x <' y$). Ahora, establecer el orden en $Ord$ (sí, es de orden en un conjunto de órdenes...) declarando $<''$ a ser más grande que la de $<'$ fib para cualquier $x,y$, $x <' y$ se sigue que $x <'' y$. Si usted piensa de órdenes como conjuntos de pares, esto es sólo la inclusión de la orden. Se puede comprobar que la hipótesis de Kuratowski-Zorn lema están satisfechos (es decir, cada cadena tiene una cota superior), entonces por el lema, existe un elemento mayor, decir $<_{max}$. Me dicen que este elemento maximal es de hecho un orden total. Para supongamos que no lo es. Entonces, hay $x$ $y$ tal que $x \not <_{max} y$$y \not <_{max} x$. Definir un orden $<'$ definiendo $u <' v$ si y sólo si $u <_{max} v$ o $u = x$$v = y$. Edit: Este es el todavía no de un orden parcial, pero puede ser extendido a un orden parcial, que es mayor que $<_{max}$ --- una contradicción. Por eso, $<_{max}$ es realmente un orden total, por lo que estamos por hacer.
Muchas gracias a Julien para señalar la brecha en el post original. Ver otras respuestas para obtener más detalles
user27515
Puntos
214
Sugerencia: Aplicar el lema de Zorn para el conjunto parcialmente ordenado de todas las órdenes parciales en $A$, ordenada al declarar $\mathord{\prec}$ a ser que menos de $\mathord{\prec^\prime}$ iff $x \prec y$implica $x \prec^\prime y$ % todo $x , y \in A$. (Usted tendrá que mostrar que máxima elementos de este orden parcial son órdenes lineales en $A$.)
