Distintos ordenamientos del mismo conjunto

Question

Una fácil consecuencia de la Erdős-Dushnik-Miller teorema $\kappa\to(\kappa,\omega)^2$ es la siguiente, que se denotan $(*)$ (aparece como un ejercicio de Kunen del libro, es probable que se menciona explícitamente antes por Dushnik-Miller o Erdős, pero no he encontrado una referencia):

Si $X$ es infinito y $<_1$ e $<_2$ son dos órdenes de $X$, luego hay un subconjunto $Y$ de % de $X$ con $|Y|=|X|$ donde $<_1$ e $<_2$ coinciden.

La prueba utiliza elección, pero se sigue que tiene en ZF: bien Podemos suponer $X$ es un ordinal $\kappa$, por lo que podemos código de $<_1$ e $<_2$ con un conjunto $A\subseteq \kappa^2$, y argumentar en $L[A]$, que es un modelo de elección.

Esta prueba siempre ha mirado extraño para mí. Recuerdo que hace un par de años hablando de esto con Clinton Conley, y creo que hemos encontrado una combinatoria argumento, pero no recuerdo cómo fue, así que no estoy seguro.

Lo que yo estoy pidiendo, a continuación, es para un combinatoria prueba de $(*)$ en ZF.

(`Combinatoria" puede significar varias cosas, lo que sobre todo me refiero a que no metamathematics aparecen en la prueba.)

Tal vez hay algún tipo de argumento inductivo (I vagamente recordar que es lo que había), pero creo que no puede ser completamente sencillo. Por ejemplo, $X=\omega_1$ podría tener cofinality $\omega$, así que la solución obvia puede ejecutar fuera de la habitación antes de $\omega_1$ pasos.

Answer 1

Clinton Conley ha encontrado un buen argumento que resuelve el problema. Me atrevería a decir que incluso en la presencia de elección, es más bonito que el enfoque estándar, y evita tener que separar el argumento de los casos, dependiendo del cofinality del cardenal en cuestión. Clinton y tengo curiosidad si la "König lema"-como la declaración de abajo ha sido explícitamente mencionado anteriormente. Los punteros son bienvenidos.

He aquí un esbozo de su argumento. Estoy publicando con su permiso, pero culpar a mí de todos los errores:

---

Debemos establecer en primer lugar un lexema acerca parcial de las órdenes en un conjunto ordenado $X$. Un orden parcial $\preceq$ a $X$ es bien fundada si cualquier subconjunto no vacío de $X$ tiene un $\preceq$-mínimo elemento. Para cualquier bien fundado de orden parcial que se puede asociar con un ordinal valores de rango de la función en $X$ por $$ {\rm rank}_\preceq(x) = \sup\{{\rm rank}_\preceq(y) +1\mid y \prec x\}. $$

Lema (König?). Supongamos que $\preceq$ es un bien fundado de orden parcial en un conjunto ordenado $X$. Supongamos, además, que $\kappa$ es un infinito aleph, tal que para cada una de las $\alpha \lt \kappa$ el conjunto $X_\alpha = \{x \in X \mid {\rm rank}_\preceq(x) = \alpha\}$ es finito y no vacío. Luego hay un $\preceq$-de la cadena de $A \subseteq X$ de tipo de orden $\kappa$.

Prueba.

Primero nos podar. Para cada una de las $\alpha \lt \kappa$ definir el conjunto $Y_\alpha$ por $$ Y_\alpha = \{x \in X_\alpha\mid \forall \alpha\lt\beta\lt\kappa\exists y \in X_\beta (x \prec y)\}. $$ That is, $Y_\alpha$ is the set of $x \in X\alpha$ with extensions to each $X\beta$, for $\beta$ strictly between $\alpha$ and $\kappa$. Each $Y_\alpha$ is nonempty since each $X\alpha$ is finite and ${\rm cof}(\kappa)$ es infinito.

La reclamación. Cada una de las $\preceq$-de la cadena de $A_\alpha \subseteq \bigcup_{\beta \lt \alpha} Y_\beta$ de tipo de orden $\alpha$ puede ser extendido a un $\preceq$-de la cadena de $A_{\alpha+1} \subseteq \bigcup_{\beta \lt \alpha+1} Y_\beta$ de tipo de orden $\alpha+1$.

La prueba de la reclamación.

Este es inmediata cuando el $\alpha$ es un sucesor $\beta + 1$, ya que por la poda tenemos $$Y_\beta \subseteq \{x\mid \exists y \in Y_{\beta+1}\ x \prec y\}.$$ When $\alfa$ is a limit, there is some element $x \in Y_\alpha$ above cofinally many elements of $A_\alpha$, since $Y_\alpha$ is finite and ${\rm cof}(\alpha)$ is infinite. Clearly $A_{\alpha+1} = A_\alpha \cup \{x\}$ is as desired. $\Caja$

A partir de la afirmación de que podemos construir un $\preceq$-cadena de orden tipo de $\kappa$ simplemente siguiendo la "izquierda" (con respeto para el bien de la orden de $X$) rama. Explícitamente, para cada una de las $\alpha \lt \kappa$ deje $A_\alpha$ ser el único de la izquierda de la cadena de orden tipo de $\alpha$ en $\bigcup_{\beta \lt \alpha} Y_\alpha$, que existe en sucesores por la sobre demanda y en los límites de tomar los sindicatos. Finalmente, el conjunto de $A = \bigcup_{\alpha \lt \kappa} A_\alpha$. $\Box$

Desde el lema, el resultado sigue fácilmente.

La proposición. Supongamos que $R_0$ e $R_1$ son dos órdenes de un conjunto infinito $X$. A continuación, hay algunos $A \subseteq X$ tal que ${}|A| = |X|$ e $R_0\upharpoonright A^2 = R_1\upharpoonright A^2$.

Prueba.

Deje $\kappa$ ser el (único) de aleph equinumerous con $X$. Se define un orden parcial $\preceq$ a $X$ por $$x \preceq y \Longleftrightarrow (x \mathrel{R_0} y \land x \mathrel{R_1} y). $$ Podemos comprobar que este bien fundada de orden parcial satisface las hipótesis del lema.

Ciertamente, $X$ es bien ordenado. Además, cada conjunto $X_\alpha = \{x \in X \mid {\rm rank}_\preceq(x) = \alpha\}$ es finito; de hecho, tenemos algo aún más fuerte.

La reclamación. Cada conjunto cuyos elementos son pares $\preceq$-incomparable es finito.

Prueba.

Supongamos hacia una contradicción que había un conjunto infinito $A$ de pares $\preceq$-incomparable elementos. A continuación, $A$ contiene un $R_0$-aumento de la $\omega$-secuencia. Pero eso sería una $R_1$-disminución de $\omega$-secuencia! $\Box$

Por último, comprobamos que cada una de las $X_\alpha$ es no vacío para $\alpha \lt \kappa$. Pero si $X_\alpha=\emptyset$, podríamos escribir $X = \bigcup_{\beta \lt \alpha} X_\beta$. Desde cada una de las $X_\beta$ es finito, el uso de $R_0$ podemos bien el fin de cada una de las $X_\beta$ en el tipo de la orden menos de $\omega$, y, por tanto, bien el fin de $X$ en el tipo de orden que en la mayoría de las $\omega \cdot \alpha \lt \kappa$, lo que contradice nuestra selección de $\kappa$.

El lema, a continuación, nos concede una $\preceq$-de la cadena de $A \subseteq X$ de tipo de orden $\kappa$, y sin duda esta $A$ satisface la conclusión de la proposición. $\Box$

---

Permítanme concluir señalando que este argumento no acaba de dar el Erdős-Dushnik-teorema de Miller, ya que se requiere que los $\preceq$ es un bien fundado de orden parcial, no sólo un bien fundado relación. Dado $f:[\kappa]^2\to2$, lo natural hubiera sido establecer $x\prec y$ fib $x\lt y$ e $f(x,y)=0$. Pero $\prec$ no es transitiva! (Por cierto, este no parece un obstáculo serio, y espero que una variante del argumento anterior para dar una combinatoria de ZF prueba de este resultado así.)

Answer 2

Solo una pequeña actualización sobre esta pregunta. El argumento en la respuesta de Andrés en realidad da el siguiente hecho (en principio más fuerte pero quién sabe) en ZF: cualquier función con valor ordinal en un conjunto bien ordenado$X$ no disminuye en un subconjunto equinumeroso con$X$. Esto no parece particularmente revolucionario. No veo una adaptación del argumento que proporcione el teorema completo de EDM en el entorno sin opciones.

Answer 3

Hace un par de años he resuelto el Kunen ejercicio junto con Anush Tserunyan (como yo y Clinton en el tiempo, un estudiante de postgrado de la UCLA). No éramos conscientes de Dushnik-Miller, así que nos dio la siguiente prueba directa del ejercicio. Edit: Como Andrés señaló, este argumento no responde a la pregunta: esto solo demuestra que en los casos de $|X|$ es regular o el límite de regular los cardenales (que siempre, sólo pueden ser el caso de que $|X|$ es contable).

Primero podemos reducir el problema a algo un poco más fácil para el estado. Deje $\kappa=|X|$. A continuación, $<_1$ tiene un segmento inicial de la orden de tipo $\kappa$, por lo que mediante la restricción de $X$ a este segmento inicial podemos suponer que la $<_1$, es habitual el bien de la orden en $\kappa$. Además, se puede también restringir $<_2$ a un segmento inicial en orden de tipo $\kappa$. Por lo tanto vemos que es suficiente para probar:

(a) Cuando se $\kappa$ es un cardenal, $f:\kappa\rightarrow\kappa$ es bijective hay un conjunto $A\subseteq\kappa$ del tamaño de la $\kappa$ en que $f$ es estrictamente creciente (en el orden habitual en los ordinales).

De hecho, por la identificación de la variedad de $f$ con un ordinal, y de nuevo la restricción a un segmento inicial de ordertype $\kappa$ vemos que (a) es equivalente a la siguiente:

(b) Siempre que $\kappa$ es un cardenal, y $\lambda$ es un ordinal, y $f:\kappa\rightarrow\lambda$ es inyectiva hay un conjunto $A\subseteq\kappa$ del tamaño de la $\kappa$ en que $f$ es estrictamente creciente.

Demostrar (a) al $\kappa$ es regular, es un sencillo de la recursión transfinita. Vamos a decir $\kappa$ es singular, y de hecho voy a explicar el caso de $\kappa=\aleph_\omega$ (el argumento se generaliza más alto por escrito $\kappa$ como límite de regular los cardenales por encima de la cofinality de $\kappa$).

Deje $f:\kappa\rightarrow\kappa$. La idea es construir $A_1,A_2,\ldots$ con $A_n$ de ordertype $\aleph_n$, $A_n$ < $A_{n+1}$, y los valores de $f$ toma en $A_{n+1}$ estrictamente mayor que aquellos que se tarda en $A_n$. Usamos (b) para esto. Considere la posibilidad de $f_1$ la restricción de $f$ a $\aleph_1$. Por (b) $A_1\subseteq\aleph_1$ en que $f_1$ es cada vez mayor. Deje $\gamma_1=\sup f[A_1]$. Desde $\gamma_1$ ha cofinality $\omega_1$, $\gamma_1<\aleph_\omega$. Deje $X_1=\kappa\setminus(\aleph_1\cup\{\alpha<\kappa:f(\alpha)<\gamma)\})$. A continuación, $X_1$ todavía tiene cardinalidad $\kappa$, y podemos extraer $A_2$ a partir de la misma manera que se hizo para $A_1$. Continúe haciendo esto, y al final vamos a $A$ ser la unión de la $A_n$.

Answer 4

Soy reacia a intentar esto, así que Si esto no tiene sentido, o no está de acuerdo con lo que está buscando, lo siento.

En primer lugar, vamos a $R_1, R_2 \subset \kappa\times\kappa$, ser los dos órdenes de $\kappa$ estamos considerando. Entonces, como $\kappa \times \kappa$ tiene un buen orden $\lt_O$ a que tipo de orden con $\kappa$ a través de algunos isomorfismo $P:\kappa \times \kappa \rightarrow \kappa$, para cada una de las $(\alpha,\beta)\in \kappa \times \kappa$:

$\gamma = max(\alpha,\beta) \implies P((\alpha,\beta)) = P(\alpha,\beta) \in P''((\gamma+1)\times(\gamma+1)).$

(Esta es una modificación de la clasificación global de la Teoría de conjuntos y La Continuidad Hyp. por R. M. Smullyan y M. Montaje, p. 119).

Este orden se define como sigue: $(\alpha,\beta)\lt_O(\gamma,\delta)$ fib uno de los siguientes sostiene

• $max(\alpha,\beta) \lt max(\gamma,\delta)$, o
• $max(\alpha,\beta) = max(\gamma,\delta)$, e $\alpha \lt \gamma$, o
• $max(\alpha,\beta) = max(\gamma,\delta)$, e $\beta \lt \delta$

Como tal, se puede formar la siguiente construcción: Vamos a $r^k_0=min_{\lt_O} (R_k)$ e de $\alpha \lt \kappa$ definir $r^k_\alpha = min_{\lt_O} (R_k \backslash \{r^k_\gamma :\gamma \lt \alpha\} )$ para $k=1,2.$

Siguiente junto con la respuesta de, Alessandro Sisto, podemos definir la secuencia de $u_\alpha$

$u_\alpha = min\{ \beta \in P''(\alpha+1)\times(\alpha+1): \forall \gamma \lt \alpha ( P^{-1}(u_{\gamma}) \lt_O r^1_{\beta} \text{ and } P^{-1}(u_\gamma) \lt_O r^2_\beta) \}.$

A continuación, $u_\alpha$ será definida para cada $\alpha \lt \kappa$, y así de preformación de la misma bits que Alessandro hizo, con $y_\alpha = min \{ \beta \in \kappa: \exists \gamma \lt \alpha( (\eta,\beta) = P^{-1}(y_\gamma)) \}$ deberían producir el resultado.

Answer 5

Aquí es un dibujo rápido (probablemente se puede hacer mucho más limpio). El uso de un argumento inductivo no debería ser difícil de reducir a estudiar el caso de que $(X,<_1)$ es isomorfo a un cardenal, decir $\kappa$. Para mayor comodidad, vamos a identificar las $(\kappa,<)$ e $(X,<_1)$. Vamos ahora a construir $Y$ el uso de la inducción transfinita. Deje $X'\subseteq X$ ser el segmento inicial de $X$ (con respecto al $<_2$) que, dotado con el fin de $<_2$, es isomorfo a $\kappa$. Para $\alpha<k$ definir $$y_\alpha=\min\{\beta\in X': \forall \alpha'<\alpha\; \beta> y_{\alpha'}\textrm{\ and\ }\beta>_2 y_{\alpha'}\}.$$ El conjunto anterior es no vacío, y por lo $y_\alpha$ está bien definida, debido a que $|\{\gamma\in X':\exists \alpha'<\alpha\; \gamma\leq y_{\alpha'}\}|<k$ también $|\{\gamma\in X':\exists \alpha'<\alpha\; \gamma\leq_2 y_{\alpha'}\}|<k$ (esto depende de la $\{y_{\alpha'}\}_{\alpha'<\alpha}$ no se cofinal en $(k,<)$ e $(X',<_2)$), por lo que su complementa en $X'$ se cruzan. El conjunto $Y=\{y_\alpha\}_{\alpha<k}$ es lo que estábamos buscando.