Suppose we have a complete lattice. Which additional axioms (e.g. distributivity axioms) are needed to obtain a Boolean lattice in which $\text{complement}(a) = \text{lub}\{b \;|\; b \wedge a = \text{bottom}\} = \text{glb} \{b \;|\; b \vee a = \text{top}\}$?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ What exactly do you mean by "axiom"? A first order sentence? A universally quantified equation? $\endgroup$– GoldsternCommented Dec 10, 2011 at 22:35
-
1$\begingroup$ @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. $\endgroup$– Andreas BlassCommented Dec 11, 2011 at 1:19
-
1$\begingroup$ @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? $\endgroup$– CSstudentCommented Dec 11, 2011 at 9:16
-
$\begingroup$ @Goldstern: I'll prefer a universally quantified equation. $\endgroup$– CSstudentCommented Dec 11, 2011 at 9:18
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
