¿Es cada red el conjunto de puntos fijos de un endomorfismo de orden de ⋄ ^ n?

Question

(Preguntado por Nathaniel Hellerstein en la junta de preguntas y respuestas en JMM)

Sea lat la red de 4 elementos

  τ
 / \
ij
 \ /
  F

¿Es cada retícula isomorfa a la retícula de punto fijo de alguna función de conservación de orden de ⋄ ⁿ → ⋄ ⁿ ?

Answer 1

Para todos finito de celosías, la respuesta es Sí.

Más en general, para todos completa de celosías, la respuesta es Sí, y para todos los de la incompletitud de celosías, la respuesta es No.

(Completa = cada set tiene un LUB y GLB.)

Permítanme en primer lugar dar el resultado positivo. Supongamos que L es un completo entramado. Cada celosía es, naturalmente, un sub-orden del poder establecido celosía P(L), asociando a cada punto de b con cono inferior b* = { a en L | a <= b }. Este mapa es claramente orden de preservación. (Nota: no es un entramado de incrustación, sin embargo, ya que (b* v c*) es la unión de dos conos, en lugar de que el cono de (b v c). ) Por lo tanto, L es el fin-isomorfo al conjunto de la baja de los conos. Definir f:P(L) P(L) por

• f(A) = (sup a)*.

Es decir, f(a) es la parte inferior del cono de (sup a). Este es el más pequeño del cono inferior que contiene A. tenga en cuenta que (sup a) es un elemento de L, como L es completa. El mapa f es el fin de preservar, ya que si a es Un subconjunto de B, entonces sup a <= sup B.

Claramente, f(b*) = b* para cualquier b en L, puesto que b es el sup de b*. Por el contrario, si F(A) = A, entonces a = b* b = sup A. es decir, a es Un cono inferior. Por lo tanto, los puntos fijos de f son exactamente la parte inferior de los conos de L, que son de orden-isomorfo a L como se desee.

Por último, para hacer la conexión con su enrejado de Diamante, tenga en cuenta que P(L) es simplemente 2^L, una potencia de 2 elemento del álgebra Booleana. Desde el Diamante 2², podemos ver que P(L) como un poder de Diamante. (Añadir un muñeco de coordenadas si L es impar tamaño finito.)

Ahora, vamos a considerar el resultado negativo. Cada poder del Diamante es isomorfo como he mencionado antes a un juego de poder P(J) para algunos de J. Supongamos que f:P(J) P(J) es una orden-preservar el mapa de P(J) P(J). Afirmo que el conjunto de puntos fijos de f debe tener un elemento más pequeño. Para ver esto, vamos a B la intersección de todos los tales que f(a) subconjunto de A. Para cualquier dicho se sigue que B es subconjunto de A, entonces f(B) el subconjunto f(A), y, entonces f(B) subconjunto de B. por Lo tanto, B es el más pequeño con f(B) subconjunto de B. Pero desde la aplicación f da f(f(B)) subconjunto f(B), se sigue que f(B)=B, como se desee. Trabajando por encima de cualquier colección de puntos fijos, el mismo argumento muestra que la colección de puntos fijos es completa. Este establece:

Teorema. Una celosía es completo si y sólo si es isomorfo al conjunto de puntos fijos de una orden de preservación de la endomorfismo de un juego de poder de celosía P(J).

Tenga en cuenta que muchas de las rejillas no están completas. Por ejemplo, los enteros positivos, como Neel menciona en su respuesta. Así que estas celosías nunca son el conjunto de puntos fijos de una orden de preservación de la mapa en un juego de poder de las redes, y, en consecuencia, el mismo de los poderes de Diamante.

Answer 2

A menos que yo misundersand la notación muy mal, seguramente esta no es la verdadera. $\diamond$ es un número finito de celosía, y por lo que el punto fijo de celosía de cualquier $f : \diamond^n \to \diamond^n$ también debe ser finito, y por lo que debe tener un elemento maximal (la combinación de todos los elementos finitos). Ahora, el infinito vertical de celosía $(\mathbb{N}, \leq, \sqcap = \min, \sqcup = \max)$ no tiene elemento maximal, y por lo tanto no puede ser isomorfo al punto fijo de celosía de algunos $f : \diamond^n \to \diamond^n$.

EDIT: creo que me hice entender mal la notación -- quizá $i$ e $j$ no son constantes, sino variables que van más de algún conjunto ordenado $I$. Así que la cardinalidad de argumento todavía funciona, tomando el powerset de $\Sigma n:\mathbb{N}.\;\diamond^n \to \diamond^n$, lo que produce un entramado que tiene demasiados elementos en isomorfismo con el punto fijo de cualquier $f$.