2
$\begingroup$

Let $X$ be a finite set. $\mathcal{P}(X)$ denotes the set of all subsets of $X$.

Let $\Gamma$ be a sub-lattice of $\mathcal{P}(X)$, i.e. $\Gamma$ is a collection of subsets of $X$ closed under union and intersection. Suppose $\Gamma$ non-empty and $\Gamma$ not made only of the empty set.

Set $$n:=n(\Gamma):=\min\{m\geq1\,|\, \Gamma\text{ contains at least one set of cardinality }m\}$$ and suppose $n\geq2$. I would like to find a lattice $\Gamma'$ isomorphic to $\Gamma$, but with $n(\Gamma')=1$.

With this purpose I thought to define a map $\Phi\!:\Gamma\to\Phi(\Gamma)=:\Gamma'$ doing the following operations:

  • from each set $A\in\Gamma$ with cardinality $|A|=n$, choose $n-1$ elements and delete them; (Notice that all these sets $A$'s are pairwise disjoint, by the minimality of $n$ and since $\Gamma$ is closed under intersection)
  • call $Y$ the set of all deleted elements;
  • from each set $B\in\Gamma$ with cardinality $|B|>n$, delete the elements of $Y$.

Clearly in this way one obtains $\Gamma'\subseteq\mathcal{P}(X')$, where $X':=X\smallsetminus Y$, and $n(\Gamma')=1$. My questions are:

  • is $\Gamma'$ a sub-lattice of $\mathcal P(X')$ ?
  • is the map $\Phi$ an isomorphism of lattices (i.e. $\Phi$ bijection, $\Phi(A\cup B)=\Phi(A)\cup\Phi(B)\,$, $\,\Phi(A\cap B)=\Phi(A)\cap\Phi(B)\,$) ?

Edit. It is trivial that $\Phi$ is surjective (by definition of $\Gamma'$). It seems also clear that $\Phi$ is an homomorphism of lattices: it suffices to write $\Phi(A)=A\smallsetminus Y$ and apply elementary facts of set theory. Therefore the only thing that remains to prove it that $\Phi$ is injective.

$\endgroup$
7
  • 1
    $\begingroup$ So you are given a finite distributive lattice $\Gamma$ and you want to find a pair ($X',\Gamma')$ such that $\Gamma$ is isomorphic to $\Gamma'$ and $\Gamma'$ is a sublattice of ${\mathcal P}(X)$, containing at least one singleton, right? $\endgroup$ Commented May 18, 2014 at 20:22
  • $\begingroup$ exactly! (I think you wrote $\mathcal P (X)$ instead of $\mathcal P (X')$) $\endgroup$
    – user118866
    Commented May 18, 2014 at 21:22
  • $\begingroup$ This forum is not the right place for this question. To help you with thinking about this, ask yourself how many sets A of cardinality n are in the lattice Gamma? $\endgroup$
    – The Masked Avenger
    Commented May 18, 2014 at 23:19
  • 2
    $\begingroup$ This is not set theory, please do not keep adding the tag. From the set-theory description: "This tag is for set theory topics typically studied at the advanced undergraduate or graduate level. More elementary questions should use the tag elementary-set-theory instead. These include cofinality, axioms of ZFC, axiom of choice, forcing, set-theoretic independence, large cardinals, models of set theory, ultrafilters, ultrapowers, constructible universe, inner model theory, definability, infinite combinatorics, transfinite hierarchies; etc." $\endgroup$ Commented May 19, 2014 at 1:40
  • 1
    $\begingroup$ OK, I missed the "finite" part. $\endgroup$
    – GEdgar
    Commented May 19, 2014 at 16:10

1 Answer 1

5
$\begingroup$

Tiny answer: Yes.

Short answer: use Birkhoff's representation theorem.

Long answer: Since $\Gamma$ is a sublattice of $\mathcal P(X)$, it is a distributive lattice. The proof of the Birkhoff's representation theorem basically says that the categories of finite distributive lattices and finite posets are dually equivalent. When you follow Birkhoff's construction from distributive lattices to posets and then back, you obtain a corrolary:

Corollary Every finite distributive lattice is isomorphic to a lattice of sets, with lattice operations $\cup,\cap$.

This corollary is sometimes called Birkhoff's representation theorem. Moreover, it turns out that the Birkhoff's construction gives you exactly what you need.

Let me show how this thing works. Assume that you are given a finite poset $P$. Call a subset $A$ of $P$ a downset if it has the following property: if $x\in A$ and $y\leq x$, then $y\in A$. Write $J(P)$ for the set of all downsets of $P$. Clearly, a $J(P)$ is closed with respect to both $\cup$ and $\cap$, so $J(P)$ is a distributive lattice. The bounds of this lattice are $\emptyset$ and $P$.

For the opposite direction, suppose you are given a distributive lattice $\Gamma$. Call an element $a$ join-irreducible if $b\vee c=a$ implies $a\in\{b,c\}$. Write $A(\Gamma)$ for the set of all nonzero join irreducible elements. ($0$ is always join-irreducible, but we have to throw it out because it would spoil the fun). It is easy to spot the elements of $A(\Gamma)$ if you draw the Hasse diagram of $\Gamma$: they are the elements of $\Gamma$ that cover exactly one element. If $\Gamma$ is a Boolean algebra, $A(\Gamma)$ are the atoms of $\Gamma$. If $\Gamma$ is a chain, then $A(\Gamma)=\Gamma\setminus\{0\}$. When you equip the set $A(\Gamma)$ with the partial order inherited from $\Gamma$, you obtain a finite poset.

And now the coolest part: for every finite poset $P$, $A(J(P))\simeq P$ and, for every finite distributive lattice $\Gamma$, $J(A(\Gamma))\simeq\Gamma$. The second isomorphism gives you the Birkhoff's representation theorem. I think this is really nice.

Back to your question: the set $A(\Gamma)$ is your $X'$ and $J(A(\Gamma))$. To see that the set system $J(A(\Gamma))$ contains a singleton, observe that the finite poset $A(\Gamma)$ must contain a minimal element $m$ and then $\{m\}\in J(A(\Gamma))$.

Example of $\Gamma$, $A(\Gamma)$ and $J(A(\Gamma))$.

$\Gamma$ $J(A(\Gamma))$ enter image description here

Let me tell you a couple more facts:

  • Both $J$ and $A$ are object parts of certain functors between categories of finite posets and finite distributive lattices. They establish a natural duality of categories.
  • This duality generalizes to the infinite case to a duality between distributive lattices and certain partially ordered topological spaces, this is called Priestley duality.
  • Restricting to Boolean algebras, Priestley duality gives us Stone duality theorem for Boolean algebras.
$\endgroup$
7
  • $\begingroup$ Thank you for the answer. I'm not familiar with lattice theory, so I don't understand a lot of terminology that you use. I'll try to understand your answer, but briefly are you saying that the answer is positive? $\endgroup$
    – user118866
    Commented May 19, 2014 at 16:10
  • $\begingroup$ Another question, that I'll probably need: if $\Gamma=\mathcal P(X)$ is it true that $|I(\Gamma)|\leq |X|$ ? $\endgroup$
    – user118866
    Commented May 19, 2014 at 17:01
  • $\begingroup$ I hope it is better now. I was lazy, because Monday. $\endgroup$ Commented May 19, 2014 at 19:47
  • $\begingroup$ Thank you very much for this detailed answer! It is really clear! Can you say also if it is true that the number of non-zero join-irreducible elements of $\Gamma$ is smaller or equal to that the cardinality of $X$? If you want I posted a new question here math.stackexchange.com/questions/801833/… .I'm asking this because in the construction suggested by my question you would get $|X'|\leq|X|$. $\endgroup$
    – user118866
    Commented May 19, 2014 at 22:04
  • 1
    $\begingroup$ @user118866 Yes it is true. It follows by duality: since $\Gamma$ embeds into $\mathcal P(X)$, so the dual map $X\to A(\Gamma)$ must be onto. So $|A(\Gamma)|\leq |X|$. $\endgroup$ Commented May 19, 2014 at 22:06

You must log in to answer this question.

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