2
$\begingroup$

Let $\mathcal{C}$ be a collection of subsets of $[n]$ that is closed under taking unions (including taking the union of the empty set which is the empty set). Then $(\mathcal{C},\subseteq)$ is a lattice. But is the converse true? In other words, given any lattice is there a union closed family of subsets of $[n]$ (for some $n$) whose members obey the order of the lattice?

I looked at all the lattices with up to 6 points and haven't found a counter-example but I can't come up with any algorithm that would prove the statement.

P.S. I do know that the converse is true for distributive lattices. Also, I am only considering finite lattices.

$\endgroup$
2
  • $\begingroup$ Are you only considering finite lattices? $\endgroup$
    – Carl Schildkraut
    May 24, 2022 at 18:49
  • $\begingroup$ Yes. Thank you. Here, all lattices are finite. $\endgroup$
    – geoffrey
    May 24, 2022 at 18:50

1 Answer 1

Reset to default
3
$\begingroup$

The converse is true.

If $L$ is a lattice and $x\in L$, define $A_x = \{z\in L\;|\;z\not\geq x\}$. The function $A\colon L\to {\mathcal P}(L)\colon x\mapsto A_x$ is a join-embedding of $(L,\vee)$ into $({\mathcal P}(L),\cup)$. The collection $\{A_x\;|\;x\in L\}$ is therefore a union-closed set of subsets of $L$ which, when ordered by inclusion, forms a lattice isomorphic to $L$.

$\endgroup$
1
  • $\begingroup$ And more generally, every poset can be embedded into a power-set lattice. The embedding can be made to preserve all existing joins or all existing meets, but not both, in general. $\endgroup$
    – amrsa
    May 27, 2022 at 10:03

You must log in to answer this question.

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