Welcome to MathOverflow

Question

2

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}?

edited Dec 29 2011 at 11:18

Goldstern
5,250●1●12●27

asked Dec 10 2011 at 20:47

CSstudent
21●1

	What exactly do you mean by "axiom"? A first order sentence? A universally quantified equation? – Goldstern Dec 10 2011 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 2011 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 2011 at 9:16
	@Goldstern: I'll prefer a universally quantified equation. – CSstudent Dec 11 2011 at 9:18

Goldstern · Answer 1 · 2011-12-29 11:17:46Z UTC

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.

Extending a complete lattice to get a “nice” Boolean lattice

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.