¿Puede un orden parcial bien fundado extenderse siempre a un orden total bien fundado

Question

Un orden parcial siempre puede extenderse a un orden total (teorema de la extensión del orden, se deduce del axioma de elección). Además, cualquier conjunto tiene un orden bien fundado (teorema del buen orden, también se deduce de AC). Pero, ¿es cierto que cualquier orden parcial fundado puede ampliarse a un orden total fundado ?

Answer 1

Dejemos que $\operatorname{rk}_{\le} : P \to Ord$ sea la función de rango (que requiere $\le$ estar bien fundado para tener valores ordinales). Además, utilice el principio de buen orden para encontrar un buen ordenamiento $\le'$ en $P$ (que no necesariamente se extiende $\le$ ). Entonces, podemos definir un ordenamiento bueno $\le''$ en $P$ que amplía $\le$ como imagen inversa del producto lexicográfico de $\le_{Ord}$ y $\le'$ bajo el mapa $(P, \le) \to Ord \times (P, \le'), p \mapsto (\operatorname{rk}_{\le}(p), p)$ . En otras palabras: $$x \le'' y \Leftrightarrow \operatorname{rk}_{\le}(x) < \operatorname{rk}_{\le}(y) \lor (\operatorname{rk}_{\le}(x) = \operatorname{rk}_{\le}(y) \land x \le' y).$$

Answer 2

Todo orden parcial bien fundado puede, en efecto, extenderse a un orden total bien fundado (= un orden bien fundado). Esta es una de las muchas variantes del teorema de Szpilrajn. En general, digamos que un orden lineal $L$ es extensible (o ejecutable , a veces) si siempre que $P$ es una orden parcial que no contiene una copia de $L$ , $P$ tiene una linealización que tampoco contiene una copia de $L$ . Así que el resultado anterior dice que $\omega^*$ es extensible, ya que los órdenes parciales mal fundados son exactamente los que no contienen una copia de $\omega^*$ .

(Sí, esa terminología es horrible. C'est la vie).

La extensibilidad de $\omega^*$ se afirma sin atribución en la introducción de este documento de Downey/Hirschfeldt/Lempp/Solomon (página $5$ ); sospecho que es folclore.

Answer 3

Esto sí es posible utilizando un argumento que se inspira en clasificación topológica .

Dejemos que $(A, R)$ sea un poset bien fundado, y tome una función de elección $f : \{U \subseteq A | U \neq \emptyset\} \to A$ tal que $f(U)$ es un $R$ -elemento mínimo de $U$ para todos $U$ en el dominio.

Designar un valor especial $UNDEF \notin A$ (tal vez elija el canónico $UNDEF = \{a \in A | a \notin a\}$ ).

Ahora define por inducción ordinal, para cada ordinal $\alpha$ , $g(\alpha) = UNDEF$ si $A \subseteq \{g(\beta) | \beta < \alpha\}$ Si no es así $g(\alpha) = f(A \setminus \{g(\beta) | \beta < \alpha\}$ .

Tenga en cuenta que para todos los $\alpha$ , $g(\alpha) \in A \cup \{UNDEF\}$ .

Supongamos que no hay $\alpha$ tal que $g(\alpha) = UNDEF$ . A continuación, observe que si $\beta < \alpha$ tenemos $g(\alpha) = f(A \setminus \{g(\beta) | \beta < \alpha\}) \in A \setminus \{g(\beta) | \beta < \alpha\}$ y así $g(\alpha) \neq g(\beta)$ . Entonces $g$ es una función 1-1 de la clase de ordinales a $A$ , lo cual es imposible ya que implica que la clase de los ordinales es un conjunto.

Ahora dejemos que $\kappa$ sea el ordinal más pequeño tal que $g(\kappa) = UNDEF$ . Entonces, considere $g : \kappa \to A$ . Vemos que por el argumento anterior, $g$ es una función 1-1. Y sabemos que $g$ es proyectiva porque $g(\kappa) = UNDEF$ y por lo tanto $A \subseteq \{g(x) | x \in \kappa\}$ . Donc $g : \kappa \to A$ es una biyección.

Ahora, supongamos que tenemos $g(\alpha) R g(\beta)$ . Entonces $g(\alpha) \neq g(\beta)$ y por lo tanto $\alpha \neq \beta$ desde $g$ es una función. Supongamos que $\beta < \alpha$ . Entonces, en ese caso, tendríamos $g(\beta) = f(A \setminus \{g(\gamma) | \gamma < \beta\})$ . Y tendríamos $g(\alpha) \in A \setminus \{g(\gamma) | \gamma < \beta\}$ . Así, por $R$ -minimidad, no podemos tener $g(\alpha) R g(\beta)$ : contradicción. Entonces debe ser el caso que $\alpha < \beta$ .

Por último, defina $R'$ por $R' = \{(g(\alpha), g(\beta)) | \alpha < \beta\} \subseteq A^2$ . En otras palabras, definir $R'$ tal que $g : \kappa \to A$ es un isomorfismo de orden. Entonces $R'$ es una orden de bien que es una extensión de $R$ .

Answer 4

Dejemos que $(P,\leq)$ sea un orden parcial sin elementos mínimos. Entonces cualquier extensión de orden total no tiene ningún elemento mínimo.

En particular, $\mathbb Z$ con el orden habitual ya es un orden total, y no hay ninguna extensión no trivial del orden, por lo que no hay ninguna extensión bien ordenada.

Incluso con elementos mínimos, no puede haber una buena ordenación. Dado cualquier $p\in P,$ si el conjunto de $\{q\in P\mid p<q\}$ es no vacía y no tiene elementos mínimos, entonces $P$ no puede estar bien ordenado.