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

Suppose we have a complete lattice. Which additional axioms (e.g. distributivity axioms) are needed to obtain a Boolean lattice in which complement(a) = lub{b | b /\ a = bottom} = glb{b | b / a = top}?

share|improve this question
    
What exactly do you mean by "axiom"? A first order sentence? A universally quantified equation? –  Goldstern Dec 10 '11 at 22:35
    
@CSstudent: The equations about complement(a) are automatically true in any Boolean lattice. Did you perhaps mean that some of the ingredients in these equations should be interpreted in the given lattice rather than in the desired Boolean lattice? If so, which ingredients? If not, how should the Boolean lattice be related to the given one? Depending on what the question is supposed to mean, it might be useful to point out that the sublattices of Boolean lattices are exactly the distributive lattices. –  Andreas Blass Dec 11 '11 at 1:19
    
@Andreas: Thanks, all the ingredients of the Boolean lattice should be interpreted in the given lattice. Alternatively, I can formulate the question as: Given a complete lattice, under which condition is lub{b | b /\ a = bottom} = glb{b | b \/ a = top}? With an added distributivity axiom, i.e. a /\ (b \/ c) = (a /\ b) \/ (a /\ c) the lattice becomes Boolean. Is this enough to make the desired equation hold? –  CSstudent Dec 11 '11 at 9:16
    
@Goldstern: I'll prefer a universally quantified equation. –  CSstudent Dec 11 '11 at 9:18
add comment

1 Answer 1

Since you are asking about universally quantified equations, there is only the trivial answer: $x=y$.

Theorem: Assume that $\varphi$ is a (finite or infinite) list of universally quantified equations (sometimes called "laws" or "identities") such that every complete lattice satisfying $\varphi$ will have complements. Then there is no nontrivial lattice satisfying $\varphi$, or in other words, the equations $\varphi$ imply $(\forall x,y): x=y$.

Proof: From a nontrivial lattice satisfying $\varphi$ I will construct a complete lattice satisfying $\varphi$ which is not Boolean.

All the following lattices will satisfy $\varphi$:

(a) Some nontrivial lattice with at least 2 points $p < q$.

(b) The 2-point Boolean lattice containing only $p < q$. (A sublattice of (a)).

(c) $\{p,q\}^2$, a 4-element Boolean lattice.

(d) $\{(p,p), (p,q), (q,q)\}$, a sublattice of (c). This is a 3-element chain.

The lattice in (d) is complete, satisfies $\varphi$, but is not Boolean.

share|improve this answer
add comment

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.