3
$\begingroup$

Call a lattice negation $\neg$ proper de Morgan negation iff it satisfies the following conditions.

  • $\neg\neg a=a$.
  • $\neg(a\vee b)=\neg a\wedge\neg b$ and $\neg(a\wedge b)=\neg a\vee\neg b$.
  • $a\leqslant b\Leftrightarrow\neg b\leqslant\neg a$.
  • If $a\vee\neg a=\top$, then $a\in\{\top,\bot\}$.

Consider now the following lattice and call it $\mathbf{M}^{\omega\omega^*}_{\omega}$. In this lattice, there are $\omega$ chains each of which is order-isomorphic to $\omega+\omega^*$ with $\omega^*=\langle\ldots,n,\ldots,0\rangle$.

enter image description here

It seems that if $\neg\mathbf{i_j}=\mathbf{i_{-j}}$, the negation is a proper de Morgan one.

The question now is whether the following statement holds.

Let $\phi$ and $\chi$ be propositional formulas over $\{\neg,\wedge,\vee\}$. Define $v_{\mathfrak{L}}$ (a valuation) as a function from the set of propositional variables to the underlying set of lattice $\mathfrak{L}$ and extend it to complex formulas in a straightforward way.

Say that $\phi$ entails $\chi$ in $\mathfrak{L}$ ($\phi\vDash\chi$) iff for any $v_{\mathfrak{L}}$: $v_{\mathfrak{L}}(\phi)\leqslant v_{\mathfrak{L}}(\chi)$.

Then for any bounded lattice $\mathfrak{L}$ with a proper de Morgan negation the following holds $$\phi\nvDash_{\mathfrak{L}}\chi\Rightarrow\phi\nvDash_{\mathbf{M}^{\omega\omega^*}_{\omega}}\chi$$


At first, it seemed correct to me and I (unsuccessfully) tried to prove it as follows.

Consider a valuation $v$ in $\mathfrak{L}$ that refutes $\phi\vDash_{\mathfrak{L}}\chi$ and construct a valuation $v'$ in $\mathbf{M}^{\omega\omega^*}_{\omega}$ as follows.

  • If $v(p)=\top,\bot$, then $v'(p)=\top,\bot$, respectively.
  • If $v(p\vee q)=\top$, then $v'(p)$ and $v'(q)$ are incomparable w.r.t. order on $\mathbf{M}^{\omega\omega^*}_{\omega}$.
  • If $v(p)\leqslant v(q)$, then $v'(p)\leqslant v'(q)$.

And here begins the problem with the last case: $v(p)$ and $v(q)$ are incomparable in $\mathfrak{L}$ but $v(p\vee q)\neq\top$. It is impossible to find a valuation $v'$ on $\mathbf{M}^{\omega\omega^*}_{\omega}$ satisfying these conditions.

However, I don't understand whether it follows from here that the statement of the theorem fails.


As an aside, do I understand it correctly that in case the theorem is incorrect, it would likewise fail for the same lattice but with chains order-isomorphic to $\omega+1+\omega^*$, i.e. $\langle 1,\ldots,n,\ldots,0,\ldots,-n,\ldots,-1\rangle$?


Reposted from MSE: https://math.stackexchange.com/questions/3552688/a-canonical-bounded-lattice-with-proper-de-morgan-negation

$\endgroup$
6
$\begingroup$

Let $\phi=(p\vee(q\wedge r))\wedge (r\vee(p\wedge q))$ and let $\chi = (p\wedge (r\vee (p\wedge q)))\vee (r\wedge (p\vee (q\wedge r)))$. For your De Morgan lattice ${\bf M}$ we have $\phi\models_{\bf M} \chi$, but we have $\phi\not\models_{\bf L} \chi$ for the De Morgan lattice:

The complementation is defined by the self-duality that fixes $p$ and $r$.

This example is more complicated than Adam's example, but it has the property that it is purely about the underlying lattice.

The justification is this: Let ${\bf L}^*$ be ${\bf L}$ minus its top and bottom. ${\bf L}^*$ is the splitting lattice for the $p$-modular law, which is $\phi\leq \chi$. Any lattice either satisfies the $p$-modular law, or has a copy of ${\bf L}^*$ as a sublattice. Your lattice ${\bf M}$ doesn't have a sublattice isomorphic to ${\bf L}^*$, so it satisfies the $p$-modular law. On the other hand, ${\bf L}$ does not satisfy the $p$-modular law, as you can see by assigning to the variables $p, q, r$ the values indicated in the figure.

Notice that if ${\mathbf L}$ is any bounded lattice, then the ordinal sum ${\mathbf 1}+{\mathbf L}+{\mathbf L}^{\partial}+{\mathbf 1}$ has a proper De Morgan complementation satisfying all four bullet points of the problem. Any canonical example ${\mathbf M}$ would have to fail every lattice identity that failed this ordinal sum, hence every lattice identity that failed in ${\mathbf L}$. Since ${\mathbf L}$ is arbitrary, it follows that the underlying lattice of any canonical example would have to generate the variety of all lattices. Since your lattice is uniformly locally finite, it cannot generate the variety of all lattices.

$\endgroup$
3
$\begingroup$

The statement that you are trying to prove appears to be false. In your algebra the inequality $x \wedge (y \vee \neg y) \leq (x \wedge y) \vee (x \wedge \neg y)$ holds, but it does not hold in every lattice with a De Morgan negation. For a counter-example, consider the five-element diamond $M_3$ equipped with a De Morgan negation which has exactly one fixpoint.

Your condition that $a \vee \neg a = \top$ implies $a = \top$ or $a = \bot$ in fact has no effect on the consequence relation. This is because each lattice with a De Morgan negation can be embedded into a lattice with (in your terminology) a "proper" De Morgan negation just by adding a new top and bottom element to the lattice. The above counter-example can therefore be extended to a "proper" one.

(By the way, the proper spelling of the name is indeed "De Morgan" rather than "de Morgan".)

$\endgroup$
  • $\begingroup$ Thanks! Do I get it correctly that $x\wedge(y\vee\neg y)=(x\wedge y)\vee(x\wedge\neg y)$ holds if and only if the lattice does not have $x$, $y$, and $z$ pairwise incomparable w.r.t. $\leq$ such that $\neg y=z$ and $\neg z=y$? $\endgroup$ – Daniil Kozhemiachenko Feb 26 at 13:23
  • 2
    $\begingroup$ Not quite: you can find such $x$, $y$, $z$ in a large enough Boolean algebra. $\endgroup$ – Adam Přenosil Feb 26 at 18:06
  • $\begingroup$ I meant lattices with De Morgan, not Boolean negations, and without distributivity. Or will it also fail? $\endgroup$ – Daniil Kozhemiachenko Feb 26 at 19:11
  • 2
    $\begingroup$ You can embed a Boolean algebra into a non-distributive lattice with a De Morgan negation by adding some non-distributive lattice (say, $M_3$) with a De Morgan negation to the top and bottom of your lattice, if you want an example which is not distributive. $\endgroup$ – Adam Přenosil Feb 26 at 20:02

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.