Demostrar que $\dim(X,\succsim)\leq|X^2|$ - Un punto de partida para un viaje hacia el fin de la teoría de la

Question

Durante la última semana seguí pensando en lo que parecía un problema fácil a primera vista.

Deje $(X,\succsim)$ ser un conjunto preordenado, y definir $\mathcal{L}(\succsim)$ como el conjunto de todas completar la pre-ordenes que se extienden $\succsim$. Definir $\dim(X,\succsim)$ como el menor entero positivo $k$ tal que $\succsim = R_1 \cap \cdots \cap R_k$ algunos $R_i \in \mathcal{L}(\succsim)$,$i=1,\cdots,k$.
Mostrar que $\dim(X,\succsim)\leq|X^2|$.

Con el fin de atacar el problema, primero de todo me echó un vistazo a $\dim(X,X^2)$ $\dim(X,\Delta_X)$ donde $\Delta_X$ es la relación diagonal. En esta pregunta tengo una opinión sobre mis conclusiones: de hecho,$\dim(X,X^2)=1$$\dim(X,\Delta_X)=2$. El caso interesante es $\dim(X,\Delta_X)$, debido a que este es el que me dio un poco de intuición sobre cómo atacar el problema que se me presente ahora.

Dado un $\Delta_X$,$\dim(X,\Delta_X)=2$, debido a que podemos imaginar todos los elementos de la diagonal de la relación (vamos a llamarlos $x_1,\cdots,x_n$) separados. Literalmente me imagine $n$ circuitos, uno para cada elemento, los cuales están relacionados. Este es un preorden. Con el fin de hacer el preorder de empezar a conectar con ellos. Ahora, podemos tener en la familia de completar la pre-ordenes que se extienden a la original preorder dos pre-ordenes:
- uno en el que todas las flechas se mueven de$x_1$$x_n$,
- y otra en la que las flechas se mueven en la dirección opuesta.
Aquí, la dirección de las flechas no es un problema tan grande, por lo que es, sin pérdida de generalidad. Curiosamente, si nos cruzan los dos pre-ordenes nos encontramos con el original de la preventa. Por lo tanto, $\dim(X,\Delta_X)=2$.

Centrándonos ahora en el problema original de $\dim(X,\succsim)\leq|X^2|$, creo que tengo dos problemas:

1) no estoy seguro de lo que la pregunta realmente es. De hecho, creo que - stricly hablando - la cuestión es que todo se trata de probar la (probablemente) trivial resultado que, en principio, $\dim(X,\succsim)$ no puede ser más grande que $|X^2|$. Así que debemos demostrarlo por la contradicción, que viene con el hecho de que $|X^2|$ representa el mayor número de conexiones que puede tener en un conjunto finito.
[No estoy seguro, si me expresado esta idea correctamente, así que siéntase libre de corregirme]
Sin embargo, otra posible forma de ver como este problema es que lo que realmente tenemos que probar es que el $|X^2|$ es el límite superior de $\dim(X,\succsim)$. Y aquí, parte de mis problemas graves...

2) ...porque no veo cómo puede ser que $\dim(X,\succsim)>2$. Este es el caso incluso si me encontré la descarga de la mayoría de los artículos escritos sobre el tema durante los últimos cincuenta años (sí, soy un poco perfeccionista, así que cuando no entiendo, me encuentro tratando de leer todo lo posible el papel sobre un tema... este también es el caso porque estoy básicamente autodidacta). Así, el punto aquí es que no puedo ver cómo $\dim(X,\succsim)>2$, porque puedo aplicar el procedimiento que se utiliza para venir para arriba con $\dim(X,\Delta_X)=2$ básicamente siempre. En otras palabras, siempre se puede encontrar una relación completa otro con algunas flechas, y otro que completa la misma relación con flechas de dirección opuesta, llegando a la intersección de los dos completa relación igual a la original, incompleta relación.

En fin, perdón por este largo post, para, probablemente, la pregunta fácil. Supongo que algunos de mis problemas pueden estar relacionados con mi idea de la extensión de un preorder o un poset. De todos modos, yo soy positivo el hecho de que con su ayuda lo voy a encontrar lo que mis problemas son todos acerca de.

Mirando hacia adelante a cualquier comentario.
Gracias de antemano.

PS: he añadido la etiqueta de "Teoría de grafos", porque traté de usar una gran cantidad de ese tipo de intuición para averiguar cuál es el problema, y estoy seguro de que de haber una retroalimentación desde ese punto de vista sobre esta cuestión puede ser muy útil (tanto desde el ámbito pedagógico y teórico de la perspectiva).

Editar:
He añadido la siguiente imagen para mostrar de lo que es el problema todavía tengo, más allá de la clase y completa Brian M. Scott respuesta.

Digamos que este es un diagrama de Hasse de un poset, así que vamos a tratar de centrarnos en la dimensión de posets en lugar de pre-ordenes, como en mi problema original. Con el fin de hacer de este poset completa, de modo que, para llegar con una extensión lineal de ella) puedo agregar una conexión que se mueve de $b$ a $c$ ($bRc$) y otro de $a$ a $c$ ($aRc$). Vamos a llamar a esta extensión lineal $R_1$. Ahora, vamos a venir para arriba con una nueva extensión lineal que se mueve desde el mismo diagrama de Hasse, pero que tiene conexiones que se mueven en direcciones opuestas (lo que significa que tenemos $cRa$$cRb$). Vamos a llamar a esta nueva extensión lineal $R_2$. Si nos cruzan las dos líneas de extensión que hemos construido, el resultado es el original poset.
Lo que me parece es que podemos llegar con este truco casi siempre... sin embargo, Brian M. Scott me señaló que tengo de ver esto no funciona, incluso de $n=4$ donde $n$ es la cardinalidad de la poset.

Exactamente, ¿qué me estoy perdiendo que debe ser muy obvio?
Estoy realmente lo siento por esta última edición y por esta pregunta tonta, pero no veo la manera de resolver este problema. Realmente muchas gracias por cualquier comentario.

Answer 1

Permítanme empezar por exhibir un orden parcial de la dimensión $n$ para un entero positivo arbitrario $n$. Deje $X=\{1,2,\dots,n\}$. Para $k\in X$ deje $S_k=\{k\}$$C_k=X\setminus\{k\}$, y vamos a $$\mathscr{X}=\{S_k:k\in X\}\cup\{C_k:k\in X\}\;;$$ I claim that $\langle\mathscr{X},\subseteq\rangle$ is a partial order of dimension $$n.

Si $n=1$,$\mathscr{X}=\big\{\{1\},\varnothing\big\}$, e $\langle\mathscr{X},\subseteq\rangle$ es ya claramente un orden lineal, por lo que podemos suponer que la $n>1$. Para $k\in X$ definir $\prec_k$ como sigue:

• si $i,j\in C_k$, $S_i\prec_k S_j$ fib $i<j$;
• si $i,j\in C_k$, $C_i\prec_k C_j$ fib $i<j$;
• si $i,j\in C_k$,$S_i\prec_k C_j$;
• si $i\in C_k$,$S_i\prec_k C_k$;
• si $i\in C_k$,$S_k\prec_k C_i$; y
• $C_k\prec_k S_k$.

De manera informal, $\prec_k$ órdenes de los conjuntos de $S_\ell$ $\ell\in C_k$ primer, en orden numérico por subíndice; estos son seguidos por $C_k$, que es seguido por $S_k$, que es seguido por los conjuntos de $C_\ell$ $\ell\in C_k$ en orden numérico por el subíndice. Es rutina para comprobar que $\prec_k$ es un estricto orden lineal en $\mathscr{X}$.

Supongamos que $A,B\in\mathscr{X}$ $A\prec_i B$ por cada $i\in X$. Deje $k,\ell\in X$; a continuación,$S_k\not\prec_k S_\ell$$C_k\not\prec_\ell C_\ell$. Por otra parte, $S_k\prec C_\ell$ fib $k\ne\ell$, e $C_k\prec_k S_\ell$ fib $k=\ell$. Supongamos que $A=C_k$ $B=S_k$ algunos $k\in X$. Por hipótesis de $n>1$, por lo que hay algunos $\ell\in X\setminus\{k\}$. Pero, a continuación,$A=C_k\not\prec_\ell S_k=B$, lo cual es imposible. Por lo tanto, no son distintos a $k,\ell\in X$ tal que $A=S_k$ $B=C_\ell$ y, por tanto,$A\subseteq B$.

Por el contrario, si $A,B\in\mathscr{X}$$A\subsetneqq B$, los hay de distintos $k,\ell\in X$ tal que $A=S_k$$B=C_\ell$, y es sencillo comprobar que $A\prec_i B$ todos los $i\in X$. Por lo tanto, la relación $\subseteq$ $\mathscr{X}$ es la intersección de los lineales de las órdenes de $\preceq_k$ $k\in X$ y por lo tanto de la dimensión en la mayoría de las $n$.

Para cada una de las $k\in X$ tenemos $S_k\nsubseteq C_k\nsubseteq S_k$. Si $\prec$ es cualquier estricto orden lineal en $\mathscr{X}$, $S_k\prec C_k$ o $C_k\prec S_k$. Por lo tanto, si $\subsetneqq$ es la intersección de una familia de $\{\prec_\alpha:\alpha\in A\}$ de los estrictamente lineal pedidos en $\mathscr{X}$, no deben ser diferenciadas $\alpha,\beta\in A$ tal que $S_k\prec_\alpha C_k$$C_k\prec_\beta S_k$. En particular, para cada una de las $k\in X$ debe haber un $\alpha\in A$ tal que $C_k\prec_\alpha S_k$.

Supongamos que $k,\ell\in X$$k\ne\ell$, y supongamos que $\prec$ es un estricto orden lineal se extiende $\subsetneqq$ $X$ tal que $C_k\prec S_k$$C_\ell\prec S_\ell$. Desde $S_k\subsetneqq C_\ell$$S_\ell\subsetneqq C_k$, debemos tener

$$C_k\prec S_k\prec C_\ell\prec S_\ell\prec C_k\;,$$

lo cual es absurdo. Por lo tanto, un estricto orden lineal $\prec$ extender $\subsetneqq$ $\mathscr{X}$ puede satisfacer $C_k\prec S_k$ a más de un $k\in X$, y de ello se desprende del párrafo anterior que tenemos que cruzan al menos $n$ estrictamente lineal pedidos en $\mathscr{X}$ conseguir $\subsetneqq$. Por lo tanto, la dimensión de la $\langle\mathscr{X},\subseteq\rangle$ es, precisamente,$n$.

(Con una ligera refinamiento de este argumento el que realmente se puede demostrar que para cualquier conjunto a $X$, la dimensión de la orden parcial $\langle\wp(X),\subseteq\rangle$$|X|$.)

---

Para el resultado real, vamos a $P=\{\langle x,y\rangle\in X\times X:x\not\succeq y\text{ and }y\not\succeq x\}$; claramente $|P|\le\left|X^2\right|$. Para cada una de las $p=\langle x,y\rangle\in P$ deje $\succeq_p$ ser un orden lineal en $X$ extender $\succeq$ que $x\succeq_p y$. Mostrar que

$$\succeq\;=\;\bigcap_{p\in P}\succeq_p\;.$$