4
$\begingroup$

Let $(X,\succeq)$ be a poset. I have the following two questions:

  1. Is it true that there exists a finite complemented distributive lattice (a Boolean lattice) $(S, \succeq^*)$ such that $X\subseteq S$ and $\succeq^*$ agrees with $\succeq$ over $X$? If not, are there conditions on $(X,\succeq)$ that guarantee this?

  2. If the answer to question 1 is true, then is it true that $(S, \succeq^*)$ is "unique" conditional on the cardinality of $S$? That is, if $(S_1, \succeq^*_{1})$ and $(S_2, \succeq^*_{2})$ satisfy the conditions described in question 1 above and $\lvert S_1\rvert=\lvert S_2\rvert$, then $(S_1, \succeq^*_{1})$ is isomorphic to $(S_2, \succeq^*_{2})$? If not, are there any uniqueness results along these lines?

I'm not a mathematician, but this question has come up in my research. Sorry if this is obvious, and thank you for your help!

Improve this question
$\endgroup$
1
  • 6
    $\begingroup$ Let $P$ be a poset. Associate to any $p \in P$ the subset $S_p := \{q\in P\colon q \leq p\}$. Then the induced subposet of the Boolean lattice of subsets of $P$ given by the subsets $S_p$ for $p \in P$ is isomorphic to $P$. $\endgroup$
    – Sam Hopkins
    Commented Jul 13, 2023 at 2:46

2 Answers 2

Reset to default
6
$\begingroup$

As Sam mentioned in the comments, the answer to question 1 is yes. One can map every condition $p$ in the partial order to the lower cone, the set $S_p=\{q\in P\mid q\leq p\}$ of conditions below $p$. It is clear that $q\leq p\iff S_q\subset S_p$, and so this maps $P$ into the powerset algebra, which is a Boolean algebra. This idea works for any poset, whether finite or infinite.

Meanwhile, the answer to question 2 is no for infinite cardinalities. The particular Boolean algebra that we had used was atomic, but we may find a larger Boolean algebra of the same infinite cardinality by embedding that Boolean algebra inside an atomless algebra. Simply view every atom as sitting atop a copy of the countable atomless algebra, and then generate the corresponding Boolean algebra. This will have the same infinite cardinality, while still accepting an embedded copy of $P$, but this larger Boolean algebra, being atomless, is not isomorphic to the earlier one, which is.

For finite cardinalities, however, of course the answer to question 2 is yes, since every finite Boolean algebra is isomorphic to a finite powerset algebra, and so if two of them have the same size (must be $2^n$), then they are isomorphic.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ The title of the question uses the word “finite” twice. $\endgroup$
    – Sam Hopkins
    Commented Jul 13, 2023 at 14:50
  • $\begingroup$ Yes, I noticed that. The body of the question does not, however, and in my view the infinitary version of the question is more interesting. $\endgroup$
    – Joel David Hamkins
    Commented Jul 13, 2023 at 15:15
  • 1
    $\begingroup$ Thank you both very much. I did want the embedding poset to be finite. But the infinite case was interesting too. I can make the question more interesting in another way: What is the minimum cardinality of the boolean algebra that embeds the original poset? Are there properties of the original poset that determine the cardinality of the smallest Boolean algebra that contains it? $\endgroup$
    – Pedram
    Commented Jul 13, 2023 at 16:19
  • 1
    $\begingroup$ Every point in a poset is the lub of its lower cone---that's why the lower cone trick works. My idea was that sometimes a smaller set of nodes works, and we restrict the lower cone to those objects. $\endgroup$
    – Joel David Hamkins
    Commented Jul 13, 2023 at 17:26
  • 1
    $\begingroup$ One more speculative comment: I would argue that this canonical embedding of a poset into the Boolean lattice of subsets of its elements is very spiritually similar to the canonical embedding of a group into the symmetric group on its elements ("Cayley's theorem"). I wonder if there is some abstract (categorical?) embedding result that includes both of these as special cases, and which singles out Boolean subset lattices and symmetric groups as special among posets/groups in some way. $\endgroup$
    – Sam Hopkins
    Commented Jul 14, 2023 at 21:36
2
$\begingroup$

I know this question has been answered, but, regarding the further question about the minimal representation of a finite lattice as a collection of sets, I thought it was worthwhile to mention the work of G. Markowsky, specifically his paper "The Factorization and Representation of Lattices," Trans. AMS 1975 (https://doi.org/10.2307/1997078). There he explains how to use sets of join- and meet-irreducibles to represent a finite lattice. This is not guaranteed to give the smallest representation, but it will be smaller than using the whole lattice. Note that similar ideas to those of Markowsky were developed later in the field of "Formal Context Analysis" (https://en.wikipedia.org/wiki/Formal_concept_analysis).

Improve this answer
$\endgroup$

You must log in to answer this question.

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