Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 the following property is valid?

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

share|improve this question
    
Negation ($\lnot x≡(x\Rightarrow\bot)$ in a Heyting algebra, or indeed where it exists in a distributive lattice, always satisfies your first property. I would call a structure with your second property a Boolean algebra. By a de Morgan algebra I would undersand one that satisfies the displayed equation; Peter Johnstone has written several papers about them in topos theory. –  Paul Taylor May 4 '13 at 14:56
    
Some of the users of this site have a habit of closing or deleting questions that they consider to be undergraduate material. I disapprove of this habit, but would point out that this question is definitely a very easy one whose answer is likely to be found in any undergraduate textbook on logic. –  Paul Taylor May 4 '13 at 14:59

1 Answer 1

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.)

share|improve this answer
2  
An executive summary: for any De Morgan algebra $A$, $\sim$ is an isomorphism of $A$ and its dual. –  Emil Jeřábek Jan 11 '12 at 11:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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