Whitman's condition for lattice polynomials

214 Views Asked by At

Recall that Whitman's condition for a lattice $L$ (with join $\sqcup$ and meet $\sqcap$) says that given $a, b, c, d \in L$, it holds that $a \sqcap b \sqsubseteq c \sqcup d$ iff at least one of the following four conditions hold:

  1. $a \sqcap b \sqsubseteq c$
  2. $a \sqcap b \sqsubseteq d$
  3. $a \sqsubseteq c \sqcup d$
  4. $b \sqsubseteq c \sqcup d$.

Let $L_1 = (\lvert L_1 \rvert, \sqsubseteq)$ be a lattice satisfying Whitman's condition, and let $X$ be a finite set of variables.

Define a new lattice $L_2$ with elements $\lvert L_1 \rvert \cup X$, and inductively construct new elements named $\sqcup(a, b)$ and $\sqcap(a, b)$ where $a, b \in L_2$.

Define the evaluation of an element in $L_2$ wrt. a function $f: X \to L_1$ as

\begin{align*} \forall x \in X~.~\lbrack x \rbrack_f &= f(x)\\ \forall a \in L_1~.~\lbrack a \rbrack_f &= a \\ \forall a, b \in L_2~.~\lbrack \sqcup(a, b) \rbrack_f &= \lbrack a \rbrack_f \sqcup \lbrack b \rbrack_f \\ \forall a, b \in L_2~.~\lbrack \sqcap(a, b) \rbrack_f &= \lbrack a \rbrack_f \sqcap \lbrack b \rbrack_f \end{align*}

Now $L_2$ forms a lattice with the ordering $$ a \sqsubseteq b \iff \forall f: X \to L_1~.~ \lbrack a \rbrack_f \sqsubseteq \lbrack b \rbrack_f $$


Does $L_2$ satisfy Whitman's condition when $L_1$ does?

1

There are 1 best solutions below

0
On BEST ANSWER

No, $L_2$ will not necessarily satisfy Whitman's condition.

One thing that should be addressed first is that $L_2$ will generally not be a lattice as you've defined it -- the order you've defined is actually only a preorder, unless you identify elements $a, b \in L_2$ whenever $[a]_f = [b]_f$ for all $f : X \to L_1$ (so you effectively consider the elements of $L_2$ as functions $L_1^X \to L_1$). Assuming this identification, then you can check that under the resulting order, $L_2$ is a lattice such that for $a, b \in L_2$, $\sqcup(a, b)$ is actually their join in $L_2$, and $\sqcap(a, b)$ is actually their meet in $L_2$. Using this fact, I'll write $a \sqcup b$ for $\sqcup(a, b)$ and $a \sqcap b$ for $\sqcap(a, b)$ when $a, b \in L_2$.

Now take the example $L_1 = (\mathbb{R}, \leq)$, and $X = \{x\}$, so $L_1$ satisfies Whitman's condition. Then we can see that in $L_2$, $$(0 \sqcup x) \sqcap 1 \sqsubseteq 0 \sqcup (x \sqcap 1)$$ (in fact, once we make the identification described above, they are equal), but all four conditions fail, e.g. the conditions $$(0 \sqcup x) \sqsubseteq 0 \sqcup (x \sqcap 1)$$ $$(0 \sqcup x) \sqcap 1 \sqsubseteq 0 $$ both fail at the assignment $f(x) = 2$, and $$ 1 \sqsubseteq 0 \sqcup (x \sqcap 1)$$ $$(0 \sqcup x) \sqcap 1 \sqsubseteq (x \sqcap 1)$$ both fail at the assignment $f(x) = -1$.