Minimal (semi)lattice containing a given poset

For a given poset, (I think that) it is easy to construct the minimal join-semilattice containing that poset. I wonder whether the minimal lattice containing that poset is also easy to construct. I can't even prove that it exists, but this is probably only due to the fact that I didn't specify what I mean by "minimal" here (because I don't know which definition would work for a lattice).

By "it is easy to construct the minimal join-semilattice...", I mean the following construction:

Let $P$ be a partially ordered set. For $X\subset P$, let $X^{u} := \{ p\in P : x \leq p \;\forall x \in X \}$. Let $J(P):=\{X\subset P:1\leq |X| < \infty\}$ and define a preorder $\leq_u$ on $J(P)$ via $X\leq_u Y$ iff $Y^u \subset X^u$. (It is easy to check that $\leq_u$ is reflexive and transitive.) Denote the quotient of $J(P)$ by the equivalence relation $\equiv_u$ associated to $\leq_u$ by $S:=J(P)/\!\!\equiv_u$ and let $j:J(P)\mapsto S$ denote the canonical projection to $S$. Then $S$ is a join-semilattice with $j(X)\lor j(Y)=j(X\cup Y)$, because we have $(X\cup Y)^u=X^u\cap Y^u$. I think I could also prove that it is the minimal join-semilattice containing (an isomorphic copy of) the poset $P$.

Edit The current answers and comments basically propose to start with any lattice containing the given poset, and then take the sublattice generated by the elements of the poset. Below, I sketched two lattices to explain why the problem is more complicated than that. The lattice on the left contains an order-embedding of the lattice on the right, but the sublattice of the left lattice generated by the elements of the right lattice is not isomorphic to the right lattice (because the meet of A and B is M instead of m).

  1        1
/ \      / \
A   B    A   B
\ /      \ /
M
|        m
m
/ \      / \
a   b    a   b
\ /      \ /
0        0


The above example is no counterexample to the "minimal" embedding using the Dedekind-MacNeille completion as starting point (as suggested by Joseph van Name). However, it should clarify that it isn't obvious that this construction really gives the minimal lattice.

-
The construction above looks like a subset of the Dedekind MacNeille completion. If you take a poset $P$, then take the Dedekind MacNeille completion $L$, and take the sublattice $A$ of $L$ generated by $P$. It seems like the lattice $A$ would be the smallest lattice that contains $P$ in some sense. – Joseph Van Name Nov 9 at 2:46
See Dedekind MacNeille completion on wikipedia: en.wikipedia.org/wiki/… – Joel David Hamkins Nov 9 at 4:00
@JosephVanName Of course the construction above has to be a subset of any embedding of the given poset, hence also a subset of the Dedekind MacNeille completion (because otherwise it wouldn't be minimal). But you are right that it is even a subsemilattice of $L$, hence the proposed construction really seems like the best candidate for the minimal lattice containing the given poset. I edited the question to explain why we still need to prove that this construction gives the minimal lattice. I actually thought about this construction before, but didn't manage to prove that it is really minimal. – Thomas Klimpel Nov 9 at 10:28

An order ideal in a poset is a down closed subset. There is an obvious notion of finitely generated order ideal. They form a join-semilattice with union. The map sending an element to its principal order ideal is well known to be the universal map to a join semilattice I believe. This map preserves meets but not joins.

The proof is fairly easy. The power set of your poset is the free semilattice on the underlying set of the poset. This maps onto your universal completion by sending each set to its join. In particular principal order ideals are sent to elements of your poset. But the universal property gives you a splitting of this projection by extending the map sending an element of the poset to its principal ideal. The image will be the finitely generated order ideals.

Added. The above proof only works when the poset is finite, but the result is true. The point is if $P$ is a poset and $f:P\to L$ is a poset map from $P$ to a join semilattice $L$, then the map from the free semilattice on the underlying set of $P$, which is the finitary power set of $P$, to $L$ that sends a finite set to its join has the property that the image of a finite set is determined by the maximal elements in the set, or equivalently, by the order ideal generated by the set. In other words, two finite subsets $X,Y$ of $P$ have the same image under the extension of $f$ to the free semilattice on $P$ iff they generate the same order ideal. It follows that the semilattice of finitely generated order ideals with union is the universal semilattice image of $P$.

-
 Is this a construction+proof for the minimal lattice, or only for the minimal semilattice? While trying to understand your proof, I run into trouble with the [free (semi)lattice](en.wikipedia.org/wiki/Free_lattice). Wikipedia says "The free semilattice is defined to consist of all of the finite subsets of X", while I think it should be "non-empty finite subsets". However, the principal order ideals need not be finite subsets, so I'm unsure how to rescue your proof. Also, I don't understand what Wikipedia means by "This construction may be promoted from semilattices to lattices" – Thomas Klimpel Nov 10 at 21:59 I found that chapter 6 of J. B. [Nation](math.hawaii.edu/~jb) Notes on Lattice Theory treats free lattices in detail. My conclusion is that the Wikipedia page of free lattices simply contains many errors, especially that the statement "This construction may be promoted from semilattices to lattices" is simply wrong. Hence, I also conclude that your proof is meant to cover only the case of the minimal semilattice. This leaves me wondering whether the minimal lattice containing a given poset exists at all... – Thomas Klimpel Nov 10 at 23:04 Sorry, my proof as written only works if the poset is finite (which I was somehow assuming because I only work with that case). Nonetheless, the claim is correct in the semilattice context and I will fix the proof. – Benjamin Steinberg Nov 11 at 0:51

The answer from Benjamin Steinberg basically constructs a semilattice $\mathcal{F}$ together with an order-embedding $i$ of $P$ in $\mathcal{F}$, such that each order-homomorphism $h_0$ from $P$ to a semilattice $L$ can be uniquely extended into a semilattice homomorphism $h$ from $\mathcal{F}$ to $L$ with $h_0=h\circ i$, as indicated by the following commutative diagram: $$\begin{matrix}P & \overset{i}{\longrightarrow} & \mathcal{F} \\ & \searrow^{h_0} & \downarrow^h \\ & & L \end{matrix}$$ However, the constructed semilattice $\mathcal{F}$ is a universal semilattice related to $P$ instead of a minimal semilattice containing $P$.

If we try to characterize the minimal semilattice in this way, then we have to construct a semilattice $\mathcal{M}$ together with an order-embedding $i$ of $P$ in $\mathcal{M}$, such that each order-embedding $j_0$ from $P$ to a semilattice $L$ can be "canonically" extended into an order-embedding $j$ from $\mathcal{M}$ to $L$ with $j_0=j\circ i$, as indicated by the following commutative diagram: $$\begin{matrix}P & \overset{i}{\longrightarrow} & \mathcal{M} \\ & \searrow^{j_0} & \downarrow^j \\ & & L \end{matrix}$$

This definition of minimal is actually slightly different from the definition given by Wikipedia for the Dedekind–MacNeille completion (which talks of a sublattice instead), but the example sketched in the question shows that the definition from Wikipedia doesn't work (even for complete lattices and the Dedekind–MacNeille completion):

The Dedekind–MacNeille completion is the smallest complete lattice with $P$ embedded in it, in the sense that, if $L$ is any lattice completion of $P$, then the Dedekind–MacNeille completion is a sublattice of $L$.

What I actually know how to prove is that there is a surjective semilattice homomorphism from $<j_0(P)>\subset L$ to $\mathcal{M}$, where $<j_0(P)>$ is the subsemilattice generated by $j_0(P)$. The axiom of choice can be used to construct the required order-embedding $j$ from this, but it should be even possible to avoid the axiom of choice by using a "canonical" choice instead.

Two problem remain: It's not obvious that the minimal semilattice according to this definition is unique up to order-isomorphism. And it's unclear whether the correspondingly defined minimal lattice always exist (and whether it would be unique).

-
 Ok, I had not interpreted minimal correctly. I thought you mean the universal map of a poset into a semilattice. Does canonical mean unique in your definition? – Benjamin Steinberg Nov 15 at 15:59 @BenjaminSteinberg It would be nice if "canonical" meant unique, but I know that it isn't always unique. When I say canonical, I think of something like always choosing the join of all possible "candidates" (from $L$), which would be possible if $L$ were a complete join-semilattice. That strategy won't work in my case, but I think that the opposite strategy should work and give an order-isomorphism as close to a semilattice-isomorphism as possible. – Thomas Klimpel Nov 15 at 18:46

Every separative partial order $P$ has a unique completion as a complete Boolean algebra, which is of course a complete complemented lattice, and that construction shares certain similarities with the construction you describe. So let me describe it.

Specifically, $P$ is separative if whenever $x\not\leq y$, there is $z\lt x$ such that $z$ and $y$ have no lower bound. This kind of partial order arises commonly in connection with the set-theoretic technique of forcing.

Every partial order $P$ carries the natural lower cone topology, which has as basic open sets $U_p=\{q\in P\mid q\leq p\}$. A set is open, therefore, when it is downward closed with respect to the order. (You were using upward closure, which is an equivalent dual notion, but in the forcing context, it is traditional to have the downward focus.)

The completion of $P$ can be constructed as the regular open algebra of $P$, that is, the collection $\mathbb{B}$ of all regular open subsets of $P$, where as set $A\subset P$ is regular open when it is equal to the interior of its closure.

The point is that the regular open algebra is a complete Boolean algebra, under the operations $$\bigwedge_i A_i = \bigcap_i A_i$$ $$\bigvee_i A_i = \text{int}(\text{cl}(\bigcup_i A_i))$$ $$\neg A=\text{int}(\text{cl}(P-A))$$ Furthermore, $P$ is dense in $\mathbb{B}$, via the association of every $p\in P$ with its lower cone $U_p$, which is regular open, since every nonempty open set contains lower cones.

Now, finally, although $\mathbb{B}$ will not generally be the smallest lattice or even the smallest Boolean algebra containing $P$, it is the smallest complete Boolean algebra containing $P$.

My point is that one may simply take the lattice generated by $P$ inside $\mathbb{B}$ to have a natural candidate for your minimal lattice of $P$.

(Note that when $P$ is not separative, the regular open algebra construction in effect performs the separative quotient, ignoring differences in points of $P$ that are not distinguished by regular open sets.)

-
 I left my brain in my other head tonight. Is this related to the Dedekind-MacNeille completion? Or is D-M just a lattice completion? Gerhard "Two Heads Not Always Better" Paseman, 2012.11.08 – Gerhard Paseman Nov 9 at 3:47 Sorry, I left my big screen in the other head too. It seems Joseph Van Name addresses the D-M aspect. Gerhard "One Screen Almost Never Enough" Paseman, 2012.11.08 – Gerhard Paseman Nov 9 at 3:50 Yes, Gerhard, it seems that the D-M completion may be better for the OP, since it doesn't seem to require the separative hypothesis. (I am simply much more familiar with the regular open algebra completion from its use in forcing.) – Joel David Hamkins Nov 9 at 4:09