Its easy to find boolean lattices $A$ and $B$ together with a function $f : A \rightarrow B$ such that $f$ preserves both top and bottom elements, as well as binary meets, but not complements.

Example. Let $A$ and $B$ denote the four and two element boolean lattices respectively, and let $f$ map every element of $A$ to $\bot_B,$ except for $\top_A$ which is mapped to $\top_B$.

Note however that the function $f : A \rightarrow B$ defined above does not preserve joins; in particular, letting $a$ and $a'$ denote the two "middle" elements of $A$, we have the following.

  • $f(a \vee a') = f(\top_A) = \top_B$
  • $f(a) \vee f(a') = \bot_B \vee \bot_B = \bot_B$

Question. What's an example of boolean lattices $A$ and $B$ together with a function $f : A \rightarrow B$ subject to the following constraints?

  1. $f$ preserves top and bottom elements
  2. $f$ preserves binary meets and joins
  3. $f$ does not preserve all complements

There is no such function. Given a boolean algebra, observe that $\lnot a$ is the unique element satisfying $a \land \lnot a = \bot$ and $a \lor \lnot a = \top$; thus, any function that preserves $\bot$, $\top$, $\lor$, and $\land$ must also preserve $\lnot$.


Zhen Lin already answered, but I thought I'd augment. If $A$ and $B$ are two Boolean algebras and $f:A\rightarrow B$ is a lattice homomorphism then the following are equivalent:

  1. $f(0)=0$ and $f(1)=1$
  2. $f(\neg a)=\neg f(a)$ for all $a\in A$

The proof is straight-forward. Assuming 1. we get: $$0=f(0)=f(a\wedge\neg a)=f(a)\wedge f(\neg a)$$ $$1=f(1)=f(a\vee\neg a)=f(a)\vee f(\neg a)$$

Thus $f(\neg a)$ is a complement for $f(a)$ for all $a\in A$. Since complements in a Boolean lattice are unique $f(\neg a)=\neg f(a)$ for all $a\in A$.

Assuming 2. we have for any $a\in A$ that $$0=f(a)\wedge\neg f(a)=f(a\wedge\neg a)=f(0)$$ $$1=f(a)\vee\neg f(a)=f(a\vee\neg a)=f(1)$$

So in order to find a lattice homomorphism which doesn't preserve complements, it would necessarily (and sufficiently) not fix one of $0$ or $1$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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