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.

  • $\begingroup$ If S had empty joins and i preserved meets then you get the inequality you want. I am skeptical joins work. $\endgroup$ – Benjamin Steinberg Feb 8 '13 at 1:33

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.

  • $\begingroup$ Nice. Having the domain be distributive really helps. $\endgroup$ – Benjamin Steinberg Feb 9 '13 at 15:59
  • $\begingroup$ @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. $\endgroup$ – Rob Myers Feb 9 '13 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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