
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 orderpreservingly 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 orderpreserving 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.

answered Sep 29 '10 at 1:59

