5
$\begingroup$

(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?

$\endgroup$
10
  • $\begingroup$ Whatever symbol it is you're using to denote the lattice, I'm seeing a little dot. Is that what it's supposed to be? I assume not. Am I missing some fonts or something? $\endgroup$ Jan 14, 2010 at 10:46
  • $\begingroup$ It's supposed to be a diamond. $\endgroup$ Jan 14, 2010 at 10:56
  • $\begingroup$ I would guess that the inequalities are meant to read vertically, and i and j are incomparable. So this would read better as f \leq i,j \leq \tau. Because \tau and f, standing for true and false, are the middle elements, and because why would it be called a diamond if we had i \leq j? $\endgroup$ Jan 14, 2010 at 12:15
  • 1
    $\begingroup$ That's how I read it too, but the only weird thing is that ⋄ is itself I x I where I is the lattice with two elements, and so in the question we could replace ⋄ by I. $\endgroup$ Jan 14, 2010 at 12:39
  • 1
    $\begingroup$ Should we expect the Joint Meetings User to be accepting any answers? $\endgroup$ Jan 16, 2010 at 4:38

2 Answers 2

5
$\begingroup$

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

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

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 2L, a power of the 2 element Boolean algebra. Since Diamond is 22, 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.

$\endgroup$
1
0
$\begingroup$

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$.

$\endgroup$
3
  • 2
    $\begingroup$ Are you requiring n to be finite, but trying to get every lattice? I think it's more likely that the asker intended "Is every finite lattice isomorphic...", or maybe to allow n to be any cardinal. $\endgroup$ Jan 14, 2010 at 10:58
  • $\begingroup$ I just read $n$ to be a natural number without thinking about very much it -- both of your suggestions make a lot of sense to me. $\endgroup$ Jan 14, 2010 at 13:53
  • $\begingroup$ Neel, it turns out that you are right, the fixed points must have a largest element, even when n is infinite! $\endgroup$ Jan 15, 2010 at 4:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.