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
    Commented 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$ Commented Jan 11, 2012 at 11:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .