3
$\begingroup$

Let $(P, \succeq)$ be a poset (you can assume $\succeq$ is not empty). I am interested in finding a poset $(X, \succeq^*)$ that embeds $(P, \succeq)$, and $\forall x,y \in X$ both of the following properties are satisfied:

  1. If $x\succ^* y$, then $\exists z\in X$ such that $x \succ^* z$, and $z$ and $y$ are not greater than or equal to the same non-zero element in $X$.
  2. If $S_{x,y}=\{z| x\succeq^* z \quad and \quad y \succeq^* z\}\neq \emptyset$, then $S_{x,y}$ has a greatest element.

If it's easier, you can strengthen the second property by requiring $x\wedge y$ to exist for every $x,y \in X$.

For example, a lattice constructed by the lower cones of the elements of $P$ (i.e., the canonical embedding in a Boolean algebra) satisfies the above. But is there another embedding that is perhaps smaller, in which the maximal elements of $(P, \succeq)$ continue to be maximal? Is it possible to construct the embedding in a single-shot (like the canonical Boolean embedding), rather than characterizing it through an algorithm whose outcome is not known at the outset?

I hope this question makes sense and thanks for your help!

Improve this question
$\endgroup$
4
  • $\begingroup$ Is there a reason you have used the top-down orientation for your orders $\succeq$ and $\succ^*$, rather than the bottom-up orientation $\preceq$, $\prec^*$, which is usually considered standard? $\endgroup$
    – Joel David Hamkins
    Commented Mar 3 at 15:28
  • 1
    $\begingroup$ @JoelDavidHamkins No particular reason really, but I guess the question is robust to the choice of orientation. $\endgroup$
    – Pedram
    Commented Mar 3 at 19:17
  • 1
    $\begingroup$ Right, of course it is invariant under that change. My view, however, is that it is something like a $d(n^x)/dn=xn^{x-1}$ situation. It is an aid to understanding when one simply follows the established notational conventions. Most people who study orders a lot systematically and consistently write it the other way. $\endgroup$
    – Joel David Hamkins
    Commented Mar 4 at 0:18
  • 1
    $\begingroup$ Yes, that makes sense. I never thought this could create any confusion, but thanks for enlightening me on that. $\endgroup$
    – Pedram
    Commented Mar 4 at 1:41

1 Answer 1

Reset to default
6
$\begingroup$

Let me describe a construction that meets your conditions. For this, let $(P,\succeq)$ be a poset (and always assume that $a\preceq b \Leftrightarrow b\succeq a$).

Stage 1. Let $(C,\succeq)$ be the Dedekind-MacNeille completion of $(P,\succeq)$, and let $h\colon P\to C\colon p\mapsto (p]$ be the order-embedding that takes an element $p\in P$ to its lower cone $(p] = \{x\in P\;|\;x\preceq p\}$.

Stage 2. Let $(D,\succeq)$ be the meet-subsemilattice $(C,\succeq)$ that is generated by the image $h(P)$. If this meet-semilattice has a least element, then label it $0$. If it does not have a least element, adjoin one and label it $0$.

At this point we have embedded $(P,\succeq)$ into a small meet-semilattice $(D,\succeq)$ with a zero element such that the maximal elements of $(P,\succeq)$ are mapped to the maximal elements of $(D,\succeq)$.

Stage 3. To each element of $d\in D$ that is not $0$ or an atom of $(D,\succeq)$ we shall adjoin a companion element $x_d$. Each new element $x_d$ will lie strictly below the element $d$ and also below any element $d'\in D$ for which $d'\succeq d$, $x_d$ will lie strictly above $0$, and $x_d$ will be incomparable with all other elements of $(D,\succeq)$. Let $(X,\succeq)$ be the poset obtained from $(D,\succeq)$ by adding all companion elements.

Stage 1 embeds $(P,\succeq)$ into a small complete lattice. Stage 2 ensures that Property 2 of the problem statement is satisfied. Stage 2 also ensures that maximal elements are preserved under the embedding. Stage 3 ensures that Property 1 of the problem statement is satisfied.

If you apply this construction to a chain $(P,\succeq)$ of some length $n>1$, the resulting $(X,\succeq)$ has size $2n-2$, which is much smaller than the size of the Boolean envelope of $P$. If you apply this construction to an antichain $(P,\succeq)$ of some length $n>1$, the resulting $(X,\succeq)$ has size $n+1$, which is also much smaller than the size of the Boolean envelope of $P$.

If $(P,\succeq)$ is a finite poset of order dimension $d$, then it can be shown that the order dimension of the poset $(X,\succeq)$ constructed above is at most $2d$. (To prove this for yourself, use the fact that the Dedekind-MacNeille completion does not increase order dimension, so the order dimension cannot increase during Stages 1 or 2.) It was proved by Hiraguchi in 1951 that $d\leq |P|/2$ holds for any finite poset. Thus, the order dimension of $(X,\succeq)$ is at most $2\cdot (|P|/2)=|P|$. On the other hand, the order dimension of the Boolean envelope of $(P,\succeq)$ is exactly $|P|$. This is another sense in which the poset $(X,\succeq)$ is smaller than or equal to the Boolean envelope

Improve this answer
$\endgroup$
3
  • $\begingroup$ I have a couple of clarifying questions (I'm new to some terminologies): 1) In stage 2, is $(D, \succeq)$ the smallest meet-subsemilattice of $(C, \succeq)$ that contains the elements of $\{h(x)|x\in P\}$? 2) Why do you add a 0 to D in stage 2? Is it to guarantee that for every $x, y \in X$, $x\wedge y$ exists in $X$? If so, wouldn't property 2 of my question (the original one, not the strengthening of it) be still satisfied even without adding a 0? Thanks! $\endgroup$
    – Pedram
    Commented Mar 5 at 20:31
  • $\begingroup$ If D doesn't have a 0, then stage 3 would create a companion element for every element of D since in the absence of 0, no element is an atom, either. Also, in the absence of 0, we can modify the requirement "$x_d$ is strictly above 0" to "$x_d$ is not the minimum element of the final set $X$", right? Or would this violate property 2? $\endgroup$
    – Pedram
    Commented Mar 5 at 21:25
  • $\begingroup$ I realized that adding 0 to 𝐷 will make 𝑋 smaller than what I described in my comment earlier. Is that why you added the 0? $\endgroup$
    – Pedram
    Commented Mar 5 at 22:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .