$f:P(X)\to X$ propiedad

Question

Para cualquier conjunto no vacío $X$ y cualquier función de $f:P(X)\to X$, existen diferentes $A,B\subseteq X$ tal que $A\subseteq B$$f(A)=f(B)$.

Un intento es tratar de encontrar una cadena a s.t. $|X|<|A|\leq |P(X)|$ desde aquí

Gracias.

Answer 1

El argumento para esto es originalmente debido a Zermelo. Acaba de construir la cadena de forma inductiva: Iniciar con $f(\emptyset)=x_0$; en general, dada $A_\beta=\{x_\alpha\mid \alpha<\beta\}$, vamos a $x_\beta$$f(A_\beta)$. Eventualmente llegar a una repetición, es decir, $x_\alpha=x_\beta$ algunos $\alpha<\beta$, y hemos terminado. Que hay una repetición puede ser visto como una consecuencia de Hartogs del resultado que para cualquier conjunto a $X$ hay un primer ordinal que no puede ser embebido en $X$. Ver aquí (sección 4) para obtener más detalles.

Tenga en cuenta que nosotros no hicimos uso de la opción en cualquier lugar. De hecho, esto demuestra que basta disponer de $f$ definido en $\mathcal W(X)$, la colección de solicitar los subconjuntos de a $X$, y así se demuestra en $\mathsf{ZF}$ que este conjunto es estrictamente mayor que $X$, un resultado originalmente debido a Tarski. (En particular, en Solovay del modelo, o en virtud de la determinación, hay más numerables de conjuntos de reales que no son reales, aunque no es un bijection entre el$\mathbb R^\omega$$\mathbb R$.)

---

En el espíritu de la otra respuesta, permítanme esbozar un mayor resultado, de

Stevo Todorcevic. Partición de las relaciones de conjuntos parcialmente ordenados, Acta Math., 155 (1-2), (1985), 1-25. MR0793235 (87d:03126):

Como Stevo indica, el resultado es debido a Galvin (inédito) en virtud de la elección. Stevo la prueba de obras en $\mathsf{ZF}$.

Teorema ($\mathsf{ZF}$). Para cualquier (ordenada) el cardenal $\kappa\ge\omega$ y cualquier $\alpha<\kappa^+$ si $f:\mathcal P(\kappa)\to\kappa$, entonces no es un $\subseteq$-cadena de orden tipo de $\alpha$ de los subconjuntos de a $\kappa$ que es constante en $f$.

Stevo la prueba se basa en las ideas de Kurepa. La notación a continuación se Stevo. Es un poco desafortunado, ya que estos "incrustaciones" no tiene que ser inyectiva.

Deje ${\mathcal A}=(A,R)$ ${\mathcal B}=(B,S)$ dos estructuras donde $R,S$ son relaciones binarias. A continuación, ${\mathcal A}$ ${\mathcal B}$-integrable, en símbolos $$ {\mathcal A}\hookrightarrow{\mathcal B},$$ iff there is a map $f:A\to B$ (an embedding) such that whenever $\ne b$ are elements of $$ with $\mathrel{R}b$, we have $f(a)\ne f(b)$ and $f(a)\mathrel{S}f(b)$. We write $f:{\mathcal Un}\hookrightarrow {\mathcal B}$ to indicate that $f$ es una incrustación.

Deje ${\mathcal A}=(A,R)$ ser un conjunto equipado con una relación binaria. Definir $\sigma{\mathcal A}=(\sigma A,{\subseteq})$, donde $$ \begin{array}{rl} \sigma A&=\{s\mid\mbox{ There is an }\alpha\in\mathsf{ORD}\,(s:\alpha\hookrightarrow{\mathcal A})\}\\ &=\{s\mid\mbox{ There is an }\alpha\in\mathsf{ORD}\,(s:\alpha\to A\mbox{ is injective }\mathrel{\&}\forall\xi<\eta<\alpha\,(s(\xi)\mathrel{R}s(\eta)))\}. \end{array} $$

El siguiente es sencillo. Sólo estamos interesados aquí en el caso de que $r=1$ y todos los $\varphi_i$ son idénticas.

Lema 1. Si $P,Q$ son posets y $P\hookrightarrow Q$, entonces para todos los $r$$0<r\in\omega$$I$, y todas las secuencias $(\varphi_i\mid i\in I)$ de la orden-tipos de lineal órdenes, tenemos $$ P\to(\varphi_i)^r_{i\in I}\Longrightarrow Q\to(\varphi_i)^r_{i\in I}. $$

(La prueba es la natural, modulo de notación, por lo que sugiero mirar el Hajnal-Larson encuesta, Partición de relaciones:

Dado $f:[Q]^r\to I$$g:P\hookrightarrow Q$, definir $h:[P]^r\to I$ por $$ h(\langle a_1,\dots,a_r\rangle)=f(\langle g(a_1),\dots,g(a_r)\rangle), $$ señalando que esto tiene sentido ya que los $a_1<_P a_2<_P\dots<_P a_r$ implica $g(a_1)<_Q g(a_2)<_Q\dots<_Q g(a_r)$ desde $g$ es una incrustación.

Desde $P\to(\varphi_i)^r_{i\in I}$, podemos encontrar $i\in I$ $H\in[P]^{\varphi_i}$ tal que $h''[H]^r=\{i\}$. Pero, a continuación,$g''H\in[Q]^{\varphi_i}$, de nuevo por virtud de $g$ ser una incrustación de objetos (e $\varphi_i$ siendo el tipo de un lineal de orden), y $$ f''[g''H]^r=h''[H]^r=\{i\}, $$ by definition of $h$.

Esto demuestra que $Q\to(\varphi_i)^r_{i\in I}$.)

La importancia aquí es que el teorema queremos demostrar es que, en la partición de cálculo de notación, que si $\kappa\ge\omega$ es un cardenal, a continuación, $(\mathcal P(\kappa),\subseteq)\to(\alpha)^1_\kappa$ todos los $\alpha<\kappa^+$.

En primer lugar, dado un conjunto $A$, $$ S(A)=\{\tau\mid\mbox{ There is an }\alpha\in\mathsf{ORD}\,(\tau:\alpha\to A\mbox{ is injective})\}, $$ considerado como una estructura con la relación binaria $\subseteq$.

Tenga en cuenta que$(S(A),\subseteq)=\sigma(A,A^2)$, $S(A)\hookrightarrow\mathcal W(A)$ donde $\mathcal W(A)$ es la colección de subconjuntos de a $A$ que están bien solicitar, de nuevo, visto como una estructura con relación binaria $\subseteq$ (la incrustación de ser el mapa de envío de cada una de las $\tau$ a su gama).

Hartogs del teorema generaliza a

Lema 2. $\sigma\mathcal A\not\hookrightarrow\mathcal A$ cualquier $\mathcal A$.

(Para ver esto, observe que si $f:\sigma A\hookrightarrow A$, entonces el mapa de $s$ dado de forma recursiva por $s(\alpha)=f(s\upharpoonright\alpha)$ inyecta el ordinales en $A$.)

Corolario. Si $\kappa\ge\omega$$\alpha<\kappa^+$, luego $$ S(\kappa)\to(\alpha)^1_\kappa. $$

Todorcevic indica en su documento que esto es debido a la Fuente para $\kappa=\omega$, y Galvin en general, pero asumiendo $\mathsf{AC}$, ambos inéditos.

Procedemos a probar el corolario: Desde $S(\kappa)=\sigma(\kappa,\kappa\times\kappa)$, no $f:S(\kappa)\to\kappa$ es una incrustación de objetos (por el Lema 2), por lo que hay $\tau\subsetneq\mu$ tal que $f(\tau)=f(\mu)$, ya que trivialmente $(f(\tau),f(\mu))\in\kappa\times\kappa$.

Considere la posibilidad de $g:S(\kappa)\to\kappa$, fix $\alpha<\kappa^+$, y supongamos que no es $g$-monocromática de la cadena en $S(\kappa)$ tipo $\alpha$. Deje $\varphi:\alpha\to\kappa$ ser inyectiva, y deje $\langle\cdot,\cdot\rangle:\kappa\times\kappa\to\kappa$ ser un bijection. Deje $f:S(\kappa)\to\kappa$ sea la función dada por $$ f(\tau)=\langle g(\tau),\varphi(o(\tau))\rangle, $$ where $o(\tau)$ is the order-type of $\tau$ in $\{\mu\sqsubseteq\tau\mid f(\mu)=g(\tau)\}$, where $\sqsubseteq$ es la inicial del segmento relación.

Hemos terminado, porque $f$ es $1$-$1$, contradiciendo el primer párrafo.

Y también esto concluye la prueba del teorema, por el Lema 1, debido a que $S(\kappa)\hookrightarrow\mathcal W(\kappa)=\mathcal P(\kappa)$.

(La escritura hasta arriba proviene de un libro en el que estoy trabajando. Cualquier comentario o sugerencia, por supuesto, alienta y apreciada. Permítanme añadir que Stevo los resultados de este trabajo han demostrado ser clave en la teoría de la partición de cálculo de la no-especial posets $\mathbb P$, aquellos para los que $\mathbb P\to(\omega)^1_\omega$ mantiene.)

Answer 2

Actualización: un mayor resultado

La pregunta pide una prueba de que el hecho de que una función $f:P(X)\to X$ es constante en algunos $2$-elemento de la cadena. Una prueba simple de hecho de que se proporciona en Andrés Caicedo de la respuesta. Aquí está una mayor participación del argumento que demuestra que, en el caso de que $|X|=\kappa$ es regular el cardenal, el resultado más fuerte que $f$ es constante en algunos cadena de orden tipo de $\kappa+1$. Sin pérdida de generalidad podemos suponer que la $X=\kappa$.

Teorema. Si $\kappa$ es regular infinito cardinal, entonces para cualquier función de $f:P(\kappa)\to\kappa$ hay una cadena de $\mathcal C\subseteq P(\kappa)$ de tipo de orden $\kappa+1$ tal que $f$ es constante en $\mathcal C$.

Prueba. Para $\kappa=\omega$ esto se deduce del hecho de que $P(\omega)$ contiene una cadena que es el fin-isomorfo a la línea real. A partir de ahora supondremos que $\kappa$ es un incontable regular el cardenal. Vamos a una función de $f:P(\kappa)\to\kappa$ ser dado. Elija una función de $\varphi:\kappa\to\kappa$ tal que $|\{\alpha\in\kappa:\varphi(\alpha)=\xi\}|=\kappa$ por cada $\xi\in\kappa$.

Construimos una secuencia $(A_\alpha:\alpha\lt\kappa)$ de los subconjuntos de a $\kappa$ por inducción transfinita, de la siguiente manera. Supongamos que $\alpha\lt\kappa$, $A_\beta$ ya ha sido definida para todos los números ordinales $\beta\lt\alpha$. Definimos $A_\alpha$, de modo que se cumplan las siguientes condiciones:

(1) $\bigcup_{\beta\lt\alpha}A_\beta\subseteq A_\alpha\subseteq\kappa$;
(2) $A_\alpha\setminus\bigcup_{\beta\lt\alpha}A_\beta$ es un subconjunto no vacío de el intervalo abierto $(\alpha,\kappa)$;
(3) $A_\alpha$ es no estacionaria (o "thin") subconjunto de $\kappa$;
(4) y, si es posible, $f(A_\alpha)=\varphi(\alpha)$.

Es decir, en el paso $\alpha$ elegimos un conjunto $A_\alpha$ que cumpla con las condiciones (1)-(4) si un conjunto existe; de lo contrario, elegimos $A_\alpha$ satisfactorio (1)-(3).

Por último, vamos a $A=\bigcup_{\alpha\lt\kappa}A_\alpha$. Yo reclamo que $A$ es no estacionaria. Para ver esto, es posible definir una función $\rho:A\to\kappa$ mediante el establecimiento $\rho(\xi)=\min\{\alpha:\xi\in A_\alpha\}$, es decir, $\rho(\xi)$ es el índice de el paso donde $\xi$ fue añadido a $A$. Se sigue de (2) $\rho$ es regresivo de la función, es decir, $\rho(\xi)\lt\xi$ todos los $\xi\in A$. Si fuese estacionaria, entonces por Fodor lema $\rho$ sería constante en algunas conjunto estacionario; se sigue de (3) que eso no suceda.

Ahora es fácil ver que la sustitución de cualquier $A_\alpha$ $A$ satisfacen las condiciones (1)-(3), así como la satisfacción (4) siempre $\varphi(\alpha)=f(A)$.

Deje $\mathcal C=\{A_\alpha:\alpha\lt\kappa,\varphi(\alpha)=f(A)\}\cup\{A\}$; a continuación, $\mathcal C$ es una cadena en la $P(\kappa)$ de tipo de orden $\kappa_1$, e $f$ es constante en $\mathcal C$.