MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose one has an inclusion $\iota : D \hookrightarrow S$ where $D$ is a finite distributive lattice and $S$ is a finite join-semilattice.

If $\iota$ preserves all meets and joins one can show that $|J(D)| \leq |J(S)|$ i.e. $D$ has no more join-irreducibles than $S$.

Does this also hold if $\iota$ only preserves finite joins?

I only know that it is true in the special cases where $S$ is a distributive lattice or $S \cong S^{op}$ is order-dual.

share|cite|improve this question
If S had empty joins and i preserved meets then you get the inequality you want. I am skeptical joins work. – Benjamin Steinberg Feb 8 '13 at 1:33
up vote 1 down vote accepted

Well, I proved that it is true with a friend yesterday, so I'll include it here.

Recall that we have an inclusion $\iota : D \hookrightarrow S$ where $S$ is a finite join-semilattice and $D$ is a finite distributive lattice. More explicitly: $S$ has all finite joins, so it is a complete lattice with a top and bottom element and furthermore $D$ has a top and bottom too.

In the case where $\iota$ preserves all meets then the same function defines a meet-semilattice morphism $\iota : D^{op} \hookrightarrow S^{op}$, so by duality we have the surjection $\iota' : S \twoheadrightarrow D$, hence $|J(D)| \leq |J(S)|$ because join-irreducibles (we exclude zero) in join-semilattices form the minimal generating set.

But the question was whether the same is true when $\iota$ preserves all joins.

First recall that in any finite distributive lattice $D$, the cardinality $|J(D)|$ is the size of the maximal chain in $D$ (counting the edges). Since we have an embedding $\iota : D \hookrightarrow S$, it follows that $S$'s maximal chain has size more than or equal to $n = |J(D)|$. For a contradiction assume that $|J(S)| < n$. Then $S$ is generated by $n-1$ elements, so we have a join-semilattice morphism $f : 2^{n-1} \twoheadrightarrow S$. By duality there is an embedding $f' : S^{op} \hookrightarrow (2^{n-1})^{op}$, hence $S^{op}$'s maximal chain has size at most $n-1$, as does its order-dual $S$, this being a contradiction.

share|cite|improve this answer
Nice. Having the domain be distributive really helps. – Benjamin Steinberg Feb 9 '13 at 15:59
@Benjamin Steinberg: Cheers. Perhaps you can see a pattern emerging regarding my other question that you answered i.e. I am searching for various conditions that imply a subalgebra has no more generators. By the way, the motivation is automata theory e.g. the above result can be used to identify a class of regular languages that have a canonical state-minimal nondeterministic acceptor. – Rob Myers Feb 9 '13 at 16:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.