-1
$\begingroup$

If we consider $\omega^\omega$ as a lattice with component-wise join and meet, is there a finite distributive lattice $L$ so that there is no injective lattice homomorphism $f:L\to\omega^\omega$?

$\endgroup$
3
$\begingroup$

I believe that by $\omega^\omega$ the original poster means the poset of order-preserving maps from the chain (=totally-ordered set) $\omega$ to itself. The answer is still "no," if my proof is correct. (It is 2:09 a.m., when all conjectures are true.)

Firstly, for any $n<\omega$, $\bf{(n+1)}^\bf n$ is a sublattice of $\omega^\omega$---$\bf m$ is the chain $\{0,1,\dots,m-1\}$---via the mapping that sends $f:\bf n\to\bf{n+1}$ to a function $\bar f$ extending $f$ such that $\bar f(k)=n+1$ for $k\ge n$. So we only have to show that every finite Boolean lattice is a sublattice of a lattice of the form $\bf{(n+1)}^\bf n$.

In fact, I will show that, for $n\ge2$, $\bf 1\oplus \bf2^{n}\oplus\bf 1$ ($\oplus$ denotes ordinal sum) is a {0,1}-sublattice of $\bf{(n+1)}^\bf n$, (i.e., there is a one-to-one lattice homomorphism that preserves the top and bottom elements). Using Priestley duality in the finite case [Theorem 5.19(i) in Davey and Priestley, Introduction to Lattices and Order, second edition], we just need to show that $\bf{1}$ $\oplus$ $\overline{n}\oplus\bf1$ ($\bar n$ is the $n$-element antichain) is an image of $\bf n\times\bf n$ via an order-preserving map $g$.

The poset $\bf n\times\bf n$ has an $n$-element maximal antichain $\{(0,n-1),(1,n-2),\dots,(n-1,0)\}$. Define $g$ as follows: for $x\in\bf n\times\bf n$, if $x$ is in the antichain, then $g(x)=x$; if $x$ is strictly above an element of the antichain, then $g(x)=(n-1,n-1)$; otherwise, $g(x)=(0,0)$.

$\endgroup$
6
$\begingroup$

By $\omega^\omega$ do you mean sequences $(a_1,a_2,\dots)$ of positive integers? The elements with $a_i=1,2$ for $1\leq i\leq n$ and $a_i=1$ for $i>n$ form a boolean sublattice $B_n$ of rank $n$, and every finite distributive lattice of height $n$ is isomorphic to a sublattice of $B_n$.

$\endgroup$
  • $\begingroup$ $\omega=\{0,1,2,\dots\}$ so $a_i$ are nonnegative $\endgroup$ – Bjørn Kjos-Hanssen Apr 6 '15 at 19:11
5
$\begingroup$

No, any finite distributive lattice is isomorphic to (hence can be identified with) a collection of finite sets (closed under $\cap$ and $\cup$) ordered by inclusion. Let $1_A$ be the characteristic function (indicator function) of the finite set $A\subseteq\omega$. Then $A\mapsto 1_A$ is your desired injective lattice homomorphism.

$\endgroup$
  • $\begingroup$ Bjørn, I think that you essentially said what Richard said just before you. Anyway, the theorem about representation of distributive lattices as lattices of sets, with their set-theoretic operations, is as classical as possible. The embedding is an instant corollary. $\endgroup$ – Włodzimierz Holsztyński Apr 12 '15 at 8:25
  • $\begingroup$ Agreed @WłodzimierzHolsztyński, although apparently it was in the same minute, and the seconds are not recorded. $\endgroup$ – Bjørn Kjos-Hanssen Apr 12 '15 at 8:46
  • $\begingroup$ Bjørn, that's why I said just :-) $\endgroup$ – Włodzimierz Holsztyński Apr 12 '15 at 18:17

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.