Minimal (semi)lattice containing a given poset

Question

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.

Answer 1

Gratzer's book (2011 edition) about lattice has details about the existence of the (semi)lattice freely generated by a poset $P$ in a given (quasi)variety of (semi)lattices (possibly with suitable additional oparations, for example boolean algebras).

One takes the elements of $P$ as generators, and the relations are the $x\leq y$ valid in $P$ (they are equivalent to [semi]lattice equations).

The universal property is easily obtained: each isotone map of $P$ towards a object $L$ in the quasivariety uniquely factorizes: first the natural isotone map from $P$ to the free object $L(P)$, then a (unique) homomorphism from $L(P)$ to $L$.

To see that the natural isotone map from $P$ to $L(P)$ is injective, it sufficies to see that one isotone map from $P$ to a $L$ is injective, and this follows from Birkhoff transform (embedding of $P$ in its lattice of order ideals, i.e. categorical equivalence between posets, Alexandroff discrete T$_0$ topological spaces, algebraic and dually algebraic distributive lattices). Provided that the given quasivariety contains all distributive lattices (or complete atomic boolean algebras, since Birkhoff transform naturally embeds also in them), but this is usually obvious (the only variety of lattices that does not include all distributive lattices is the trivial variety of one-element lattices).

[Really the natural map is a poset embedding (also the inverse from the image of $P$ to $P$ is isotone). This can be seen along the preceding lines, or one can see Gratzer's book where one finds much more general results about free embeddings of partial lattices in lattices.]

Taking as $P$ the anti-chain with $n>2$ elements one sees that $L(P)$ is the free object (in the quasivariety) on $n$-generators; in particular it is generally not the Dedekind-McNeille completion of $P$ (which is the projective line with $n$ points, hence $2$-distributive, a quite strong lattice identity). If you look at the directions of the arrows for the universal property of the Dedekind-McNeille completion (among all completions) and for the above $L(P)$ you will find this non-coincidence unsurprising (and you will find another example where lattices have too many kinds of useful morphisms to look at them with only one category).

[The last paragraph is not quite correct. I wanted to express the fact that the relation between the cut completion and the freely generated lattice resembles the relation between the one-point (minimal) compactificication and the universal (maximal) Stone compactification. However I partly messed up the reasons for this (it is a question of different arrows, but not of direction). A better analysis follows]

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$

Thank you for the pointer to your extra-question formalization of "minimal".

For a poset $P$, you essentially consider the class of all posets $Q$ that have $P$ as sub-poset, and the following preorder: $Q\preceq Q'$ iff there is a poset embedding of $Q$ in $Q'$ that fixes each element of $P$.

I see no reasons for $Q\preceq Q'\preceq Q$ to imply that $Q,Q'$ are isomorphic extensions of $P$ (i.e. I see no reasons for the composition of the two embeddings to be the identity also outside $P$).

When considering the subclass of join-semilattices (or lattices, or meet-semilattices; also complete lattices can be considered) $Q$, you are searching minimum (not only minimal!) elements for the preorder on the subclass; lacking antisymmetry, there might be non-isomorphic minima.

{\em{When $P$ is finite then the Dedekind - McNeille completion is minimal: as lattice, as join semilattice, as meet semilattice.}}

{\em{When $P$ is generic then the Dedekind - McNeille completion is minimal as complete lattice.}}

The elements of such completion (Dedekind cuts) are pairs $(A,B)$ of subsets of $P$ such that: (1) $A$ is the set of elements $a$ of $P$ such that $a\leq b$ for each $b$ in $B$; (2) $B$ is the set of elements $b$ of $P$ such that $a\leq b$ for each $a$ in $A$.

The ordering on such pairs is inclusion between the first components, or equivalently dual inclusion between the second components.

Equivalently: the binary relation $\leq$ between $P$ and $P$ has an associated Galois connection; the $A$ are the closed sets in the first component, and the $B$ the corresponding closed sets in the second component.

In any join-semilattice $Q$ extending $P$, the elements Sup$A$ exist in $Q$ since $A$ is finite; dually, Inf$B$ exist in meet-semilattice extensions of $P$.

Using the map ``from $A$ to Sup$A$'',one order-embeds the Dedekind - McNeille completion of $P$ in any join-semilattice extension $Q$ of $P$:

the map ``fixes'' $P$ (if $A$ is the interval $(p]$ ending in $p$ then Sup$A$ is $p$); the map is isotone (if $A$ is contained in $A'$ then Sup$A$ is contained in Sup$A'$); conversely, if Sup$A$ is contained in Sup$A'$ then the interval [Sup$A$) (i.e. the set $B_Q$ of elements in $Q$ which contain each $a$ in $A$) contains $B'_Q$; hence $B=B_Q\cap P$ contains $B'=B'_Q\cap P$, hence $A$ is contained in $A'$.

The same argument also gives two order embeddings of the Dedekind - McNeille completion of a possibly infinite $P$ in any complete (semi)lattice $Q$ extending $P$. These two embeddings coincide iff each element of $Q$ is both sup and inf of (different) subsets of $P$, i.e. iff $Q$ is the Dedekind - McNeille completion of $P$. You can easily see the two embeddings in the specific example embedded in your question.

[Joseph Van Name has already given elsewhere very similar arguments]

{\em{This minimum is unique up to isomorphisms (as poset extension of the finite poset $P$).}}

For a finite $P$, let $Q$ a minimum poset extension of $P$ among semilattices; this minimum conditions implies that $Q$ is poset embedded, respecting $P$, in the Dedekind - McNeille completion of $P$.

Since $P$ is finite, also its Dedekind - McNeille completion is finite, hence also is the subposet $Q$.

One has two finite sets ($Q$ and the Dedekind - McNeille completion of $P$) each with a injective map in the other; they must have the same cardinality and the poset embeddings of one in the other must be surjective, hence isomorphisms.

For a infinite $P$, even when each cut $(A,B)$ is finitely generated ($B$ is the polar of a finite subset of $A$ and $A$ is the polar of a finite subset of $B$), the preceding argument fails since inside the cut completion of $Q$ one can have Sup$A$ strictly less than Inf$B$, so Sup of finite subsets of $A$ containing the generators need not coincide. In fact one has:

{\em{when $P$ is a countably infinite antichain, then $P$ has no minimal lattice or semilattice extension}}

Consider as $P$ the antichain $a_0,a_1,a_2,\dots$ and the join semilattice $Q$ obtained by adding a chain of distinct elements $b_n$ as sup of $a_0,a_1,\dots,a_n$. [One can draw a picture with the $a$ on a horizontal line and the $b$ on a vertical line].

This already shows that the obvious candidate (the join semilattice $Q'$ generated by $P$ in its cut completion, i.e. the antichain with a maximum element added) is not minimal since it cannot be embedded in $Q$ (in $Q$ no element contains infinitely many elements of $P$).

Conversely, $Q$ is not embeddable in $Q'$ since $Q$ has more than one element outside $P$ and $Q'$ has only one. Really, this shows that no embedding in $Q'$ exists for a poset with at least two elements outside $P$, and since $Q'$ is the only join semilattice with only one element outside $P$ the thesis follows.

[One could consider a modified definition of minimal in a given class: a extension of $P$ in the class such that no proper sub-extension is again in the class. The cut completion, in the above cases where it is the absolute minimum, is also the unique minimal in such cases. I see no reasons for a arbitrary extension in one of the three wanted classes to contain a sub-extension which is minimal: the above $Q$ is a join-semilattice extending the antichian $P$, but one can leave only a infinite subsequence of the $b_i$ and again have a join-semilattice extension (but not a sub-semilattice of $Q$), so $Q$ contains no minimal extension. On the other hand $Q'$ is clearly minimal in this modified sense]

Answer 2

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

Answer 3

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

Answer 4

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