Skip to main content
added 6560 characters in body
Source Link
user46855
  • 2.2k
  • 18
  • 13

[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 particoularparticular it is generally not the Dedekind-McNeillMcNeille 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]

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 particoular it is generally not the Dedekind-McNeill 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).

[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]

Source Link
user46855
  • 2.2k
  • 18
  • 13

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

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 particoular it is generally not the Dedekind-McNeill 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).