Proving that a poset is a lattice - MathOverflow

Proving that a poset is a lattice

2010-09-28T17:19:24Z

I discovered experimentally that a certain finite poset (sorry, I cannot give its definition here) seems to be in fact a (non-distributive, non-graded) lattice. The covering relations are reasonably simple, but it seems not so easy to find out whether one element is smaller than the other, let alone find the meet (or join) of two elements. However, it is (relatively) easy to see that the poset has a minimum and a maximum.

I wonder whether there are standard techniques for proving that a poset is a lattice, that do not need knowledge about how the meet of two elements looks like. (In fact, any example would be very helpful.)

Some more hints:

I don't see a way to embed the poset in a larger lattice...
the poset is (in general) not self-dual, but the dual poset is itself a member of the set of posets I am looking at.
to get an idea, here is a picture of one example (produced by sage-combinat and dot2tex)

Answer by Tony Huynh for Proving that a poset is a lattice

2010-09-28T17:50:22Z

If you have a handle on the join operator, then you can try to show that your poset is a complete join semi-lattice. This shows that your poset is also a complete meet semi-lattice, and hence a complete lattice.

This is certainly way more useful in the infinite setting, but the point is you only have to do half the work. For example let $L$ be the poset of subspaces of a vector space $V$ (ordered by inclusion). It is almost trivial that the intersection of an arbitrary collection of subspaces is a subspace. So, $L$ is a complete meet semi-lattice and hence a lattice.

Answer by Sebastian for Proving that a poset is a lattice

2010-09-28T18:08:30Z

What do you mean by "it seems not so easy to find out whether one element is smaller than the other"? In what way is this information not directly provided by the order relation that comes with the poset?

(this would normally be a comment and not an answer, but I cannot leave comments yet)

Answer by David Speyer for Proving that a poset is a lattice

2010-09-28T18:42:47Z

I have often found the following lemma of Bjorner, Eidelman and Ziegler to be useful:

Let $P$ be a bounded poset of finite rank such that, for any $x$ and $y$ in $P$, if $x$ and $y$ both cover an element $z$, then the join $x \vee y$ exists. Then $P$ is a lattice.

See Lemma 2.1 "Hyperplane arrangements with a lattice of regions", Discrete and Computational Geometry, Volume 5, Number 1, 263--288.

The hypothesis that $P$ is bounded means that $P$ has a minimal and maximal element. In fact, this hypothesis is slightly stronger than necessary: One can show that if $P$ has a minimal element and the other hypotheses hold then $P$ has a maximal element.

Answer by Joel David Hamkins for Proving that a poset is a lattice

2010-09-29T01:59:10Z

Since you seem at heart to be asking a question about how to compute things with your partial order, let me offer several observations from the perspective of computability theory and computable model theory. I recognize, however, that you may find this perspective unhelpful, and in this case I apologize.

First, the order relation in any lattice is computable from either the join or meet operations, since $x\leq y$ if and only if $x\wedge y = x$ if and only if $x\vee y = y$. Thus, the order relation can be no harder to compute than the lub and glb's.
Second, the converse is not generally true in infinite lattices, and one cannot generally expect to compute the meet and join operations nor the cover relation from the order relation itself. For example, there is a lattice order on the natural numbers whose order relation is a computable relation, but whose meet function and cover relation is not computable. To construct this example, one arranges a lattice of height $4$ in which a Turing machine program $e$ has meet $0$ with a fixed element $1$ if program $e$ does not halt on trivial input, but otherwise the meet is a code for the halting computation. In this way, the order relation is computable in the sense that given $x$ and $y$ one can compute whether $x\leq y$, but there is in general no way to compute $x\wedge y$, since from this function one could solve the halting problem. Similarly, program $e$ covers $0$ if and only if $e$ does not halt, so the covering relation is also not decidable. Such a kind of model arises commonly in the subject known as computable model theory.
Third, you mentioned that your order is finite, but any finite structure is of course computable. That is, whatever your relation and operations are, they are definitely computable functions. From this perspective, the exact content of your question becomes somewhat murky, and one would request a greater clarity about what you are asking. It sounds like you might have a uniform presentation of infinitely many different partial orders, and you want to know whether you can compute whether the $n^{\rm th}$ such order is a lattice, or how to uniformly compute the relations or the meets and joins. In this case, we would need more details about what the orders are. For example, one can easily construct examples of an infinite sequence of partial orders, whose order relations are uniformly computable, but the question of whether the $n^{\rm th}$ order is a lattice is undecidable. In contrast, if the $n^{\rm th}$ order is necessarily a finite order of computable size, then this question is always decidable by brute force searching.
Fourth, you mention that the covering relation is easy. In this case, the order relation should be low degree polynomial time computable (in the size of the order), since one can first compute the covering relation of all pairs, and then successively compute the relation as the transitive closure of this relation.
Finally, fifth, in response to item 1, every partial $(P,\leq)$ embeds order-preservingly into a lattice, since one may consider the set of downward closed subsets of $P$. This collection is closed under unions and intersections, and if one identifies a point in $P$ with its lower cone, then one obtains an order-preserving map into a lattice. This embedding preserves meets when they exist, since the intersection of the cone below $x$ and the cone below $y$ is the cone below $x\wedge y$, when this meet exists. But unions will not generally preserve $\vee$ for this map. There are other possible completions that are appropriate when the lattice exhibits certain other nice properties. For example, when the lattice minus its minimal element is separative, then it has a completion as a complete Boolean algebra, the regular open algebra.