Todo orden parcial puede extenderse a un ordenamiento lineal

Question

¿Cómo puedo demostrar que todo orden parcial puede extenderse a un ordenamiento lineal?

Creo que consigo demostrar esa afirmación para un conjunto finito, ¿cómo puedo demostrarla para un conjunto infinito?

Gracias.

Answer 1

Hay que usar el axioma de elección en el caso infinito. Y este uso es esencial porque es consistente que hay conjuntos que no pueden ser linealmente ordenados (en cuyo caso la relación de identidad no puede extenderse a un orden lineal).

Dejemos que $(P,R)$ sea un conjunto parcialmente ordenado. Definimos la colección $\{\leq\mid (P,\leq)\text{ is a poset and }R\subseteq\leq\}$ , ordene esto por $\subseteq$ y demostrar que satisface las condiciones del lema de Zorn. El elemento maximal tiene que ser de orden lineal.

---

Cabe destacar que exigir simplemente que todo conjunto parcialmente ordenado pueda extenderse a un orden lineal es estrictamente más débil que el axioma de elección.

Aquí hay un truco muy limpio que utiliza el Teorema de la compacidad de la lógica de primer orden (que es más débil que el axioma de elección). Aunque probablemente no lo hayan tratado en el curso, es un buen truco que hay que conocer:

Dejemos que $(P,\leq)$ sea un conjunto parcialmente ordenado. Sea $\cal L$ sea el lenguaje con una relación binaria $\preceq$ y un símbolo constante $c_p$ por cada $p\in P$ . Escribimos lo siguiente $T$ :

1. $\preceq$ es un orden parcial;
2. siempre que $p\leq q$ añadimos el axioma $c_p\preceq c_q$ ;
3. para cada par $p,q\in P$ añadimos el axioma $c_p\preceq c_q\lor c_q\preceq c_p$ .

Ahora demostraremos que $T$ es finitamente satisfactoria. Si $S\subseteq T$ sólo tiene axiomas de la forma $1$ o del esquema descrito en $2$ entonces $(P,\leq)$ es un modelo para $S$ . En caso contrario, tiene un número finito de axiomas del esquema en $3$ . Podemos ampliar $\leq$ a algunos $\leq^\ast$ que satisfacen estos axiomas.

Lo hacemos por inducción: si sólo hay un axioma y no se ha cumplido, entonces $p$ y $q$ son incomparables, y podemos tomar $\leq^\ast=\leq\cup\{\langle p,q'\rangle\mid q\leq q'\}$ .

Supongamos que hacemos esto para $k$ axiomas; basta con repetir el argumento para el $k+1$ . Esto no requiere ningún axioma de elección porque sólo tenemos que hacer un número finito de elecciones.

(Como alternativa se puede sustituir el esquema $3$ por el axioma $3'$ , $\forall x\forall y(x\preceq y\lor y\preceq x)$ Ahora bien, fíjate en que cualquier fragmento finito sólo habla de un número finito de constantes, $c_{p_1},\ldots,c_{p_k}$ . Restringir $\leq$ a $\{p_1,\ldots,p_k\}$ es un conjunto finito parcialmente ordenado, y puede extenderse a un ordenamiento lineal que satisfaga $3'$ como se quería).

Por lo tanto, todo fragmento finito de $T$ tiene un modelo, por lo que por el teorema de compacidad $T$ tiene un modelo $(P',\leq')$ . Definimos $\preceq$ en $P$ de la siguiente manera: $p\preceq q\iff (P',\leq')\models c_p\preceq c_q$ . El esquema $2$ garantiza que esto se extienda $\leq$ y el esquema $3$ (o axioma $3'$ ) garantiza que se trata de una ordenación lineal.

Answer 2

Tendrá que utilizar el axioma de elección (o una de sus consecuencias) de alguna forma. Una posibilidad es utilizar el lema de Zorn. Sea $\langle P,\le\rangle$ sea un orden parcial. Sea $$\mathscr{L}=\big\{\langle X,\preceq_X\rangle:X\subseteq P\text{ and }\preceq_X\text{ is a linear order on }X\\\text{ extending }\le\upharpoonright(X\times X)\}\;.$$

Para $\langle X,\preceq_X\rangle,\langle Y,\preceq_Y\rangle\in\mathscr{L}$ definir $\langle X,\preceq_X\rangle\sqsubseteq\langle Y,\preceq_Y\rangle$ si $X\subseteq Y$ y $\preceq_Y\upharpoonright(X\times X)=\preceq_X$ claramente $\langle\mathscr{L},\sqsubseteq\rangle$ es un orden parcial. Sea $\mathscr{C}$ sea una cadena en $\langle\mathscr{L},\sqsubseteq\rangle$ .

• Demuestra que $\mathscr{C}$ tiene un límite superior en $\langle\mathscr{L},\sqsubseteq\rangle$ La opción más obvia funciona.

• Utilice el lema de Zorn para concluir que $\langle\mathscr{L},\sqsubseteq\rangle$ tiene un elemento máximo $\langle M,\preceq_M\rangle$ .

• Demostrar que $M=P$ .

Añadido: Sin embargo, no es necesario utilizar el axioma de elección completo: el resultado se deduce, por ejemplo, del teorema del ideal primo booleano, que es estrictamente más débil que el AC. Por ejemplo, uno de los equivalentes del BPI es el teorema de compacidad para la lógica de primer orden, que puede utilizarse para dar una prueba muy sencilla. Sea $R$ sea un símbolo de relación binaria, y para cada $p\in P$ dejar $c_p$ sea un símbolo constante. Sea $\Phi$ sea el conjunto de todas las sentencias $R(c_p,c_q)$ tal que $p,q\in P$ y $p\le q$ junto con los axiomas que hacen $R$ un orden lineal. Entonces $\Phi$ es finitamente satisfacible, así que por el teorema de compacidad $\Phi$ tiene un modelo. Ese modelo produce una extensión lineal de $\le$ .

Añadido ₂ : Vale, me gustan los ultrafiltros. Para $F\in[P]^{<\omega}$ dejar $U_F=\big\{G\in[P]^{<\omega}:F\subseteq G\big\}$ claramente $\big\{U_F:F\in[P]^{<\omega}\big\}$ está centrado (= tiene la propiedad de intersección finita), por lo que puede extenderse a un ultrafiltro $\mathscr{U}$ en $[P]^{<\omega}$ . (Esto requiere el teorema de la extensión del ultrafiltro, que es equivalente al BPI). Para cada $F\subseteq P$ dejar $\preceq_F$ sea un orden lineal en $F$ que se extiende $\le\upharpoonright\!\!(F\times F)$ , dejemos que $\le_F\,=\,\le\cup\preceq_F$ y denotar por $P_F$ la orden parcial $\langle P,\le_F\rangle$ .

Para $p,q\in P$ escribir $p\preceq q$ si $\big\{F\in[P]^{<\omega}:p\le_F q\big\}\in\mathscr{U}$ . Si $p\le q$ entonces $p\le_F q$ para todos $F\in[P]^{<\omega}$ Así que $p\preceq q$ . Ahora dejemos que $p,q\in P$ con $p\ne q$ . Entonces exactamente uno de los conjuntos $\big\{G\in U_{\{p,q\}}:p\le_G q\big\}$ y $\big\{G\in U_{\{p,q\}}:q\le_G p\big\}$ pertenece a $\mathscr{U}$ , por lo que exactamente uno de $p\preceq q$ y $q\preceq p$ se mantiene. Por último, si $p,q,r\in P$ con $p\preceq q\preceq r$ entonces

$$\big\{G\in U_{\{p,q,r\}}:p\le_G r\big\}\supseteq\\\big\{G\in U_{\{p,q,r\}}:p\le_G q\big\}\cap\big\{G\in U_{\{p,q,r\}}:q\le_G r\big\}\in\mathscr{U}\;,$$

así que $p\preceq r$ . Así, $\preceq$ es un orden lineal en $P$ ampliando $\le$ .