2
$\begingroup$

Recall that an algebra $(A,\sim)$ is a De Morgan algebra if $A$ is a bounded distributive lattice and $\sim$ is a unary operation which satisfies:

${\sim} (x\vee y)={\sim} x\wedge {\sim} y$ and ${\sim\sim} x=x$.

When is the following property valid?

$${\sim}\bigwedge_{i\in I} x_i=\bigvee_{i\in I} {\sim} x_i$$

$\endgroup$
1
  • $\begingroup$ @PaulTaylor Would you seriously call the set $\{0,\ldots,n\}$ with $\land$ and $\lor$ being binary min and max, and $\sim$ being $k \mapsto n-k$, a “Boolean algebra”? It satisfies the equations in this question, but I would find it exceedingly strange to call it a “Boolean algebra” as it doesn't satisfy $x \land {\sim x} = 0$. $\endgroup$
    – Gro-Tsen
    Dec 23, 2023 at 15:10

1 Answer 1

5
$\begingroup$

I claim that the property is true in every de Morgan algebra, whenever the expressions in it make sense (on either side). The issue about making sense is that when $I$ is infinite, the expression $\bigwedge_{i\in I}x_i$ refers to the greatest lower bound of the set of $x_i$ for $i\in I$, and in general there may be no such element of the algebra that is such a greatest lower bound. It is a kind of completeness property to assert that there is such an element as $\bigwedge_{i\in I}x_i$.

But I claim that in any de Morgan algebra in which $\bigwedge_{i\in I}x_i$ exists, then your equation is satisfied. $${\sim}\Bigl(\bigwedge_{i\in I}x_i\Bigr)=\bigvee_{i\in I}{\sim} x_i$$ To see this, observe first that $\sim$ must be order-reversing: if $x\leq y$ in the lattice, then this means $x\wedge y=x$, which implies ${\sim}(x\wedge y)={\sim} x\vee{\sim} y={\sim} x$, which means ${\sim} y\leq {\sim} x$.

Now, if $x=\bigwedge_{i\in I} x_i$ exists, then $x$ is the greatest lower bound of the $x_i$. In particular, $x\leq x_i$ and so ${\sim} x_i\leq {\sim} x$ and so $\bigvee_i {\sim} x_i\leq {\sim} x$ for every $i\in I$. But also, any other upper bound $y$ of the ${\sim} x_i$ would have ${\sim} y$ as a lower bound of the $x_i$, which would lead by the definition of $x$ to ${\sim} y\leq x$ and so ${\sim} x\leq {\sim\sim} y=y$. Thus, ${\sim} x$ is a least upper bound of ${\sim} x_i$ for $i\in I$ and so your equation $${\sim}\Bigl(\bigwedge_{i\in I}x_i\Bigr)=\bigvee_{i\in I}{\sim} x_i$$ is true whenever it makes sense. (A similar argument works when the other side is defined.)

$\endgroup$
1
  • 3
    $\begingroup$ An executive summary: for any De Morgan algebra $A$, $\sim$ is an isomorphism of $A$ and its dual. $\endgroup$ Jan 11, 2012 at 11:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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