(Asked by Nathaniel Hellerstein on the Q&A board at JMM)
Let ⋄ be the 4 element lattice
τ / \ i j \ / f
Is every lattice isomorphic to the fixed point lattice of some order-preserving function from ⋄^{n}→⋄^{n}?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this community(Asked by Nathaniel Hellerstein on the Q&A board at JMM)
Let ⋄ be the 4 element lattice
τ / \ i j \ / f
Is every lattice isomorphic to the fixed point lattice of some order-preserving function from ⋄^{n}→⋄^{n}?
For all finite lattices, the answer is Yes.
More generally, for all complete lattices, the answer is Yes, and for all incompleteness lattices, the answer is No.
(Complete = every set has a LUB and GLB.)
Let me first give the positive result. Suppose that L is a complete lattice. Every lattice is naturally a sub-order of the power-set lattice P(L), by associating each point b with it's lower cone b* = { a in L | a <= b }. This map is clearly order-preserving. (Note: it is not a lattice embedding, however, since (b* v c*) is the union of two cones, rather than the cone of (b v c). ) Thus, L is order-isomorphic to the set of lower cones. Define f:P(L) to P(L) by
That is, f(A) is the lower cone of (sup A). This is the smallest lower cone containing A. Note that (sup A) is an element of L, since L is complete. The map f is order preserving, since if A is a subset of B, then sup A <= sup B.
Clearly, f(b*) = b* for any b in L, since b is the sup of b*. Conversely, if F(A) = A, then A = b* for b = sup A. That is, A is a lower cone. Thus, the fixed points of f are exactly the lower cones of L, which are order-isomorphic to L, as desired.
Finally, to make the connection with your Diamond lattice, note that P(L) is simply 2^{L}, a power of the 2 element Boolean algebra. Since Diamond is 2^{2}, we can view P(L) as a power of Diamond. (Add a dummy coordinate if L is odd finite size.)
Now, let's consider the negative result. Every power of Diamond is isomorphic as I mentioned earlier to a power set P(J) for some set J. Suppose that f:P(J) to P(J) is an order-preserving map from P(J) to P(J). I claim that the set of fixed points of f must have a smallest element. To see this, let B be the intersection of all A such that f(A) subset A. For any such A it follows that B subset A, so f(B) subset f(A), and so f(B) subset B. So B is the smallest with f(B) subset B. But since applying f gives f(f(B)) subset f(B), it follows that f(B)=B, as desired. By working above any given collection of fixed points, the same argument shows that the collection of fixed points is complete. This establishes:
Theorem. A lattice is complete if and only if it is isomorphic to the set of fixed points of an order-preserving endomorphism of a power set lattice P(J).
Note that many lattices are not complete. For example, the positive integers, as Neel mentioned in his answer. So these lattices are never the set of fixed points of an order-preserving map on a power set lattice, and consequently the same for the powers of Diamond.
Unless I misundersand the notation very badly, this is surely not true. $\diamond$ is a finite lattice, and so the fixed point lattice of any $f : \diamond^n \to \diamond^n$ must also be finite, and so it must have a maximal element (the join of all the finite elements). Now, the infinite vertical lattice $(\mathbb{N}, \leq, \sqcap = \min, \sqcup = \max)$ has no maximal element, and so it can't be isomorphic to the fixed point lattice of some $f : \diamond^n \to \diamond^n$.
EDIT: I think I did misunderstand the notation -- maybe $i$ and $j$ aren't constants, but variables ranging over some ordered set $I$. So a cardinality argument still works, by taking the powerset of $\Sigma n:\mathbb{N}.\;\diamond^n \to \diamond^n$, which yields a lattice which has too many elements to be in isomorphism with the fixed point of any $f$.