¿No existe una suryección que preserva el orden desde un conjunto de posturas a su red de conjuntos?

Question

Como en el título. Por "rejilla descendente", me refiero específicamente al conjunto de conjuntos inferiores del poset en cuestión, ordenado por inclusión de conjuntos.

Ni siquiera estoy seguro de cómo empezar. Parece cierto, porque parece una función de un conjunto a un subconjunto de su conjunto de potencia, y me sorprendería mucho que fuera suryente. Pero no estoy seguro de a dónde llevar esa corazonada. Estaría muy agradecido por cualquier ayuda que demuestre esta afirmación.

Gracias de antemano.

Answer 1

Mi propósito al publicar esta respuesta es presentar una versión ligeramente simplificada de la prueba en Respuesta de Eric Wofsey y una formulación algo más limpia del resultado, y situarlo en su contexto histórico dando referencias.

Tenga en cuenta que, si la ordenación de $P$ es trivial (no hay dos elementos comparables), entonces estamos diciendo que no hay ninguna suryección desde el conjunto $P$ a su conjunto de energía $\mathcal P(P).$ En otras palabras, este resultado es una generalización de Teorema de Cantor aunque la demostración es bastante diferente de la conocida demostración diagonal de ese teorema. Este teorema de Cantor generalizado fue demostrado originalmente por Gleason y Dilworth y generalizado por Davies, Hayes y Rousseau:

A. M. Gleason y R. P. Dilworth, A generalized Cantor theorem, Proc. Amer. Math. Soc. 13 (1962), 704-705.

Roy O. Davies, Allan Hayes y George Rousseau, Complete lattices and the generalized Cantor theorem, Proc. Amer. Math. Soc. 27 (1971), 253-258 .

Terminología. Una relación binaria $\le$ es un cuasi-ordenación (o "preordenación") si es reflexivo y transitivo. Un mapeo $f$ entre conjuntos cuasi-ordenados es isotone (o "preservación del orden") si $x\le y\implies f(x)\le f(y).$ Un subconjunto $D$ de un conjunto cuasi-ordenado $Q$ es un conjunto inferior (o "down-set") si, para todo $x,y\in Q,\ x\le y\in D \implies x\in D.$

La pregunta pide que se demuestre (esencialmente) lo siguiente:

Teorema. Si $Q$ es un conjunto cuasi-ordenado y $f:Q\to\mathcal P(Q)$ un mapeo isotono, entonces el rango de $f$ no puede contener todos los conjuntos inferiores de $Q.$

Obsérvese que el resultado puede replantearse de manera que no se refiera explícitamente al ordenamiento de $Q$ :

Teorema. Dado un conjunto $Q$ y un mapeo $f:Q\to\mathcal P(Q),$ podemos encontrar un conjunto $D\in\mathcal P(Q)\setminus\operatorname{range}(f)$ tal que para todo $x,y\in Q$ que tenemos: $f(x)\subseteq f(y),\ y\in D\implies x\in D.$

Prueba. Para cada ordinal $\alpha$ definir $$D_\alpha=\{x\in Q:f(x)\subseteq\bigcup_{\xi\lt\alpha}D_\xi\}.$$ Evidentemente, cada $D_\alpha$ satisface la condición: $f(x)\subseteq f(y),\ y\in D_\alpha\implies x\in D_\alpha.$ Todo lo que tenemos que hacer ahora es encontrar algún $D_\alpha$ que no está en el rango de $f.$ Claramente, $\beta\lt\alpha\implies D_\beta\subseteq D_\alpha,$ para que siempre tengamos $\bigcup_{\xi\lt\alpha}D_\xi\subseteq D_\alpha.$ Si la inclusión adecuada $\bigcup_{\xi\lt\alpha}D_\xi\subsetneqq D_\alpha$ celebrada por cada $\alpha,$ entonces $\alpha\mapsto D_\alpha$ sería una inyección de la clase de todos los ordinales en $\mathcal P(Q),$ contradictorio Teorema de Hartogs . Por lo tanto, existe un ordinal $\alpha$ tal que $$D_\alpha\subseteq\bigcup_{\xi\lt\alpha}D_\xi.$$ Teniendo en cuenta la menor $\alpha,$ Afirmo que $D_\alpha$ no está en el rango de $f.$

Supongamos para una contradicción que $D_\alpha=f(x)$ para algunos $x\in Q.$ Entonces $f(x)\subseteq\bigcup_{\xi\lt\alpha}D_\xi,$ así que $x\in D_\alpha,$ así que $x\in D_\beta$ para algunos $\beta\lt\alpha,$ y $f(x)\subseteq\bigcup_{\xi\lt\beta}D_\xi.$ Pero ahora tenemos $$D_\beta\subseteq D_\alpha=f(x)\subseteq\bigcup_{\xi\lt\beta}D_\xi,$$ así que $D_\beta\subseteq\bigcup_{\xi\lt\beta}D_\gamma$ y $\beta\lt\alpha,$ contradiciendo la minimidad de $\alpha.$

Answer 2

Esta es una forma de hacerlo. Supongamos que $P$ es un poset, $L$ es su entramado de conjuntos inferiores, y $f:P\to L$ es una suryección que preserva el orden. Permítanme primero esbozar el argumento de forma intuitiva; si quieren una prueba formal más breve, pueden saltar hasta el final. La idea es descartar inductivamente todos los posibles "tamaños" de $P$ . En primer lugar, ¿puede $P$ ¿está vacío? No, no puede, ya que $L$ siempre tiene al menos un elemento, concretamente el conjunto vacío. Por lo tanto, como $f$ es suryente, hay algún $p_0\in P$ tal que $f(p_0)=\emptyset$ .

OK, ahora puede $p_0$ sea el único elemento de $P$ ? No, porque una vez que sabemos $p_0\in P$ hay un segundo conjunto inferior en $L$ , a saber $\{q\in P:q\leq p_0\}$ . Así que vamos a elegir $p_1\in P$ tal que $f(p_1)=\{q\in P:q\leq p_0\}$ .

OK, ahora puede $p_0$ y $p_1$ sean los únicos elementos de $P$ ? Bien, considera el conjunto inferior $D_2=\{q\in P:q\leq p_0\text{ or }q\leq p_1\}$ . No podemos tener $f(p_0)=D_2$ ya que $D_2$ no está vacío. Y no podemos tener $f(p_1)=D_2$ ya que $f(p_1)=\{q\in P:q\leq p_0\}$ y $p_1\in D_2$ por lo que implicaría $p_1\leq p_0$ . Pero entonces desde $f$ es preservador del orden, tendríamos $f(p_1)\subseteq f(p_0)$ lo cual es imposible ya que $f(p_0)$ está vacío y $f(p_1)$ no lo es.

Tal vez hayamos terminado ahora: tal vez $P$ no tiene más elementos que $p_0$ , $p_1$ y $p_2$ . No: considere el conjunto inferior $D_3=\{q\in P:q\leq p_0\text{ or }q\leq p_1\text{ or }q\leq p_2\}$ . Puede demostrar que $D_3$ no puede ser igual a $f(p_0)$ , $f(p_1)$ o $f(p_2)$ , por lo que debe haber algún elemento nuevo $p_3\in P$ tal que $f(p_3)=D_3$ .

Y así sucesivamente. Repitiendo este procedimiento de forma inductiva, se pueden seguir obteniendo más y más elementos distintos de $P$ . Se puede continuar esto transfinitamente, para definir elementos distintos $p_\alpha$ para todos los ordinales $\alpha$ . Esto es imposible, ya que $P$ es un conjunto.

---

Bien, aquí está el argumento escrito de manera más formal. Construiremos una secuencia de elementos $p_\alpha\in P$ para cada ordinal $\alpha$ por recursión transfinita. Habiendo definido $p_\beta$ para todos $\beta<\alpha$ , dejemos que $D_\alpha=\{q\in P:q\leq p_\beta\text{ for some }\beta<\alpha\}$ (el conjunto inferior generado por el $p_\beta$ ). Dado que $f$ es suryente, existe algún $p\in P$ tal que $f(p)=D_\alpha$ . Definir $p_\alpha$ para ser un $p$ .

Afirmo que $p_\alpha\not\in D_\alpha$ para todos $\alpha$ . Podemos demostrarlo por inducción: supongamos que $p_\beta\not\in D_\beta$ para todos $\beta<\alpha$ pero $p_\alpha\in D_\alpha$ . Entonces $p_\alpha\leq p_\beta$ para algunos $\beta<\alpha$ . Desde $f$ es preservador del orden, esto significa que $f(p_\alpha)\subseteq f(p_\beta)$ . Por construcción, $f(p_\alpha)=D_\alpha$ para todos $\alpha$ Así que $D_\alpha\subseteq D_\beta$ . Pero $p_\beta\in D_\alpha$ , por lo que esto da $p_\beta\in D_\beta$ lo que contradice la hipótesis de la inducción.

Así, $p_\alpha\not\in D_\alpha$ para todos $\alpha$ . Pero $p_\beta\in D_\alpha$ para todos $\beta<\alpha$ y así $\beta<\alpha$ implica $p_\beta\neq p_\alpha$ . Así, $\alpha\mapsto p_\alpha$ es inyectiva. Esto es una contradicción, ya que $P$ es un conjunto y este mapa está definido para todos los ordinales.

(Nótese que este argumento utiliza el axioma de elección para escoger un $p_\alpha$ tal que $f(p_\alpha)=D_\alpha$ en cada paso. Sin embargo, se puede evitar el uso del axioma de elección haciendo todas las elecciones a la vez. Es decir, en lugar de elegir sólo un nuevo elemento $p_\alpha$ , dejemos que $P_\alpha$ sea el conjunto de todos los $p$ tal que $f(p)=D_\alpha$ . A continuación, es necesario definir $D_\alpha=\{q:q\leq p\text{ for some }\beta<\alpha\text{ and some }p\in P_\beta\}$ .)