Cómo demostrar que existe un conjunto bien ordenado incontable sin utilizar el axioma de sustitución

Question

Parece que debemos utilizar el hecho de que todo conjunto bien ordenado es isomorfo a un ordinal único, que depende del axioma de sustitución, para demostrar la existencia de un conjunto bien ordenado incontable. ¿Puede alguien aportar una prueba alternativa?

Answer 1

Sí, podemos demostrar la existencia de un conjunto incontable bien ordenado sin Reemplazo.

En Z solo (= ZF sin sustitución), podemos demostrar la existencia del conjunto $X$ de clases de equivalencia de ordenamientos de $\omega$ módulo de orden-isomorfismo. Es fácil demostrar que $X$ es incontable; la única tarea que queda es demostrar que $X$ está bien ordenado por " $[x]\triangleleft[y]$ si $x$ orden-incorpora como un segmento inicial de $y$ " (esta relación está claramente bien definida).

Sin embargo, vale la pena tener un poco de cuidado aquí: el orden lineal de $X$ depende de la capacidad de comparar ordenamientos de pozos, y esto se logra a través de la recursividad transfinita, pero a menudo los argumentos a través de la recursividad transfinita dependen del Reemplazo. Esta es una fuente razonable de preocupación, pero resulta que no es un problema aquí: como el "objetivo" de nuestra recursión ya es un conjunto, no necesitamos realmente el Reemplazo (ver el comentario de Eric más abajo).

Permítanme esbozar cómo podemos demostrar que $X$ está ordenada linealmente por $\triangleleft$ sin depender de la sustitución:

• Digamos que $\alpha:A\rightarrow B$ es un incrustación inicial del segmento (donde $A, B$ son órdenes lineales) si es preservador del orden y tiene rango un segmento inicial de $B$ (posiblemente todo el $B$ ). Podemos demostrar sin Reemplazo que si $A, B$ son ordenamientos buenos, entonces hay a lo sumo una incrustación de segmento inicial de $A$ a $B$ . (Piensa en el menor elemento del dominio en el que las dos incrustaciones discrepan...)

• Supongamos ahora que $A, B$ son ordenamientos de pozos de $\omega$ y no hay una incrustación de segmento inicial de $B$ en $A$ (es decir, $B\not\trianglelefteq A$ ); queremos demostrar que existe una incrustación de segmento inicial de $A$ en $B$ con rango a adecuado subconjunto de $B$ (así $A\triangleleft B$ ).

• Dejemos que $S$ sea el conjunto de $a\in A$ tal que existe una incrustación inicial de segmentos desde $(a)_A:=\{a'\in A: a'\le_Aa\}$ a $B$ . Cada $a\in S$ corresponde a un elemento único $\hat{a}$ en $B$ por la observación dos puntos anteriores; es fácil ver que el mapa (a priori parcial) $m:\alpha\mapsto\hat{\alpha}$ existe y es una incrustación de segmento inicial.

• Tenga en cuenta que $m$ no puede ser sobreyectiva; de lo contrario, la inversión de $m$ daría una incrustación de segmento inicial de $B$ en $A$ .

• Supongamos ahora que $dom(m)$ no es todo $A$ . Sea $s$ sea el $A$ -menor elemento de $A\setminus S$ y (por el punto anterior) que $t$ sea el $B$ -menor elemento de $B\setminus ran(m)$ . Entonces podemos ampliar $m$ a una incrustación parcial del segmento inicial estrictamente mayor enviando $s$ a $t$ , lo cual es una contradicción.

• Así que $dom(m)=A$ eso es, $A\triangleleft B$ .

Ahora sólo queda demostrar que $X$ no tiene $\triangleleft$ -secuencias descendentes, pero esto procede exactamente como de costumbre.

---

Así que la existencia de grandes ordinales es mucho más turbia que la existencia de grandes bien ordenados (de hecho, ZC ni siquiera demuestra que $\omega+\omega$ existe). Hay que pensar en los ordinales como "formas normales" de los ordenamientos: en general, necesitamos el reemplazo para demostrar que un ordenamiento arbitrario tiene una forma normal.

Answer 2

No es necesario mencionar los ordinales para construir un conjunto bien ordenado incontable. Digamos que $S$ es la familia de todos los pozos de $\Bbb N$ . Decimos que dos órdenes de pozos son equivalentes si son isomorfos, y consideramos el cociente $S/\sim$ . Ahora demuestre que dados dos elementos de $S/\sim$ uno de ellos es isomorfo a un segmento inicial del otro; utilice esto para definir un orden lineal en $S/\sim$ y resulta que $S/\sim$ es un conjunto incontable bien ordenado.

No voy a afirmar que eso no utiliza la sustitución, pero no veo cómo lo hace.

Answer 3

A pesar de las respuestas ya existentes, cabe mencionar que la respuesta a la pregunta "¿podemos demostrar que todo conjunto bien ordenado es isomorfo a un ordinal sin reemplazo?" es no, ya que existen modelos de ZFC-reemplazo(=ZC) en los que este teorema falla.

El ejemplo más fácil es probablemente $V_\lambda$ para un ordinal límite contable $\lambda>\omega$ . En efecto, para tal ordinal, $V_\lambda$ es un modelo de la teoría de conjuntos de Zermelo (y de la elección si hemos asumido la elección), pero no de la sustitución.

Además, los ordinales de $V_\lambda$ son precisamente los ordinales $<\lambda$ y para un contable $\lambda$ son todos contables (incluso en $V_\lambda$ es fácil comprobar que una biyección entre $\alpha<\lambda$ y $\omega$ está en $V_\lambda$ ). Por lo tanto, $V_\lambda$ es un modelo de Z y "no hay ordinales incontables".

Tomando $\lambda=\omega+\omega$ demuestra la afirmación de Noah Schweber de que ni siquiera podemos probar que $\omega+\omega$ existe sin reemplazo.

Sin embargo, la cuestión de si hay incontables conjuntos bien ordenados sin sustitución es más sutil.

La respuesta a esto utiliza el hecho de que podemos "modelar" $\omega_1$ incluso sin tener acceso a él, porque sabemos lo que es: es el conjunto de ordinales contables. Eso es lo que Noah Schweber y David C.Ulrich mostraron en sus respuestas (nótese que sus respuestas pueden extenderse fácilmente a un conjunto arbitrario $X$ mostrando la versión "débil" del teorema de Hartog: para cualquier conjunto $X$ hay un conjunto bien ordenado $O$ sin inyección $O\to X$ )

Answer 4

Como se ha explicado anteriormente, la construcción de Hartogs de 1915 muestra que Z (= ZF menos Reposición) demuestra que un ordenamiento del tipo $\omega_1$ (que no es más que una ordenación incontable cuyas iniciales propias son contables) existe. (De hecho, el ordenamiento es uno de los subconjuntos de $P(P(\omega))$ es decir, ordena bien conjuntos de reales).

Esta construcción puede ser iterada cualquier número finito de veces, demostrando en Z: para cada $n\in\omega$ existe una ordenación del tipo $\omega_n$ (es decir, ...). Sin embargo, sin Reemplazo, esto es lo máximo que se puede hacer, como se ilustra con un modelo natural $V_{\omega+\omega}$ que satiesfies GCH.