Celosía de Preorden

Question

He visto muchos ejemplos que definen un entramado sobre un conjunto parcialmente ordenado $(P, \sqsubseteq)$ junto con un límite inferior mayor $\sqcap$ un límite superior mínimo $\sqcup$ y un top $\top$ y el elemento inferior $\bot$ .

La relación $\sqsubseteq$ es un ordenamiento parcial, por lo que es reflexivo, transitivo y antisimétrico.

Tengo otro operador de pedidos $\preceq$ que sólo es reflexivo y transitivo. Por lo tanto, es un preordenar , $(Q, \preceq)$ .

1) ¿Puedo construir una celosía a partir del pre-pedido $(Q, \preceq)$ ? (suponiendo que tenga $\top$ , $\bot$ GLB y LUB)

2) ¿De qué propiedades del operador de ordenación depende la red?

Answer 1

Algunas sugerencias:

• Si tienes antisimetría, entonces tu preorden es en realidad un orden parcial y es fácil construir el entramado correspondiente.
• Si no hay antisimetría, entonces existe un par $a,b$ tal que $a \preceq b$ y $b \preceq a$ . ¿Cómo definiría usted $\{a,b\}$ ? De hecho $\preceq$ podría ser la relación completa $Q \times Q$ (es decir, es reflexivo y transitivo).
• Una forma es definir $x \sim y$ si y sólo si $x \preceq y \land y \preceq x$ . Entonces $\preceq$ indica una orden parcial en $Q/\sim$ y entonces puedes formar un entramado.
• Otra forma es modificar el preorden, por ejemplo, para $a\preceq b$ y $b\preceq a$ puede elegir cuál de $\{a,b\}$ será el límite superior. Sin embargo, hay que hacerlo de forma coherente. La mejor manera es construir un orden parcial a partir de su preorden:
  1. Definir $\sim$ como en el caso anterior.
  2. Dejemos que $\sqsubseteq$ sea cualquier total del pedido en $Q$ (de hecho sólo queremos el orden total dentro de cualquier clase de equivalencia de $\sim$ ).
  3. Set $f : Q \to (Q/\sim)\times Q$ a $$f(x) = \big\langle [x]_\sim, x \big\rangle.$$
  4. Crear un orden lexicográfico $\preceq_\mathsf{lex}$ en $(Q/\sim)\times Q$ de $(\preceq/\sim)$ y $\sqsubseteq$ .
  5. Definir $x \preceq_\mathsf{PO} y$ como $f(x) \preceq_\mathsf{lex} f(y)$ .
  6. Tenga en cuenta que $x \preceq_\mathsf{PO} y$ es una cosa diferente a $\preceq$ Por ejemplo, podría haber algunos problemas de exhaustividad, etc.

Espero que esto ayude $\ddot\smile$

Answer 2

Para 1)

Se puede ver un preorden como una categoría en la que hay como máximo una flecha entre dos objetos cualquiera. Equivalentemente, es una categoría enriquecida en la categoría monoidal $\textbf{2}$ (que a su vez es una orden parcial), que se parece a $0 \rightarrow 1$ donde el producto es $\wedge$ . Para que este preorden sea una "red" significaría que tiene todos los productos (GLB) y coproductos (LUB) finitos. Cada preorden es equivalente (como categoría) a un orden parcial; dado un preorden $(Q, \preceq)$ forman un orden parcial $(Q/\sim, \leq)$ , donde $a \sim b \iff a \preceq b$ y $b \preceq a$ . Como las equivalencias preservan los productos y coproductos, si $Q$ era un "entramado", entonces $Q/\sim$ será un entramado en el sentido habitual.

Answer 3

Finalización de Dedekind-MacNeille

Hay otra forma no mencionada de completar un preorden (o cualquier relación binaria) para formar una red. El ingrediente principal de esta construcción es la noción de conexión de Galois (antitono).

Definición: Supongamos que $(P, \leq)$ y $(Q, \sqsubseteq)$ son órdenes parciales. Entonces, un conexión antitono de Galois es un par de mapas $$ f_\ast: P \leftrightarrows Q: f^\ast $$ tal que $f_\ast(x) \sqsupseteq y$ si y sólo si $f^\ast(y) \geq x$ .

Dada una relación $R \subseteq X \times Y$ existe una conexión de Galois entre los conjuntos de potencias $2^X$ y $2^Y$ , $$ R_\ast: 2^X \leftrightarrows 2^Y: R^\ast $$ dado por $$ R_\ast(\sigma) = \{y \in Y: (x,y) \in R~\forall~x \in \sigma \}, $$ y $$ R^\ast(\tau) = \{x \in X: (x,y) \in R~\forall y \in \tau \}. $$

Entonces, se deduce (hay que trabajar un poco) que $$ L(X,Y,R):= \{ (\sigma, \tau): R_\ast(\sigma) \supseteq \tau~\text{iff}~R^\ast(\tau) \supseteq \sigma \} $$ es un entramado.

Como caso especial, si $\preceq\subseteq Q \times Q$ es un preorden, entonces $L(Q,Q,\preceq)$ es un entramado.

Dualidad de Birkhoff

Supongamos que $(Q, \preceq)$ es un finito preorden. Como ya se ha dicho, se puede "mod" por la relación $x \sim y$ si $x \preceq y$ y $y \preceq x$ para obtener un poset $(Q, \preceq_\sim)$ . Los conjuntos descendentes de este poset $\mathcal{D}(Q)$ forma un entramado distributivo completo bajo unión e intersección. (Recordemos, $D \subseteq Q$ está cerrado si $x \in D$ y $y \preceq_\sim x$ implica que $y \in D$ .)