Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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? –  Kevin H. Lin Jan 14 '10 at 10:46
    
It's supposed to be a diamond. –  Reid Barton Jan 14 '10 at 10:56
    
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? –  David Speyer Jan 14 '10 at 12:15
1  
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. –  Reid Barton Jan 14 '10 at 12:39
1  
Should we expect the Joint Meetings User to be accepting any answers? –  Joel David Hamkins Jan 16 '10 at 4:38
show 5 more comments

2 Answers

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.

share|improve this answer
1  
This question and answer are related to the question asked at: mathoverflow.net/questions/11435#11451 –  Joel David Hamkins Jan 14 '10 at 15:43
add comment

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

share|improve this answer
2  
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. –  Reid Barton Jan 14 '10 at 10:58
    
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. –  Neel Krishnaswami Jan 14 '10 at 13:53
    
Neel, it turns out that you are right, the fixed points must have a largest element, even when n is infinite! –  Joel David Hamkins Jan 15 '10 at 4:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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