# "Pseudo-Boolean" lattice (almost every element has several complements)

If $$(L,\leq)$$ is a lattice with bottom element $$0$$ and top element $$1$$ and $$x\in L$$ we say that $$y$$ is a complement of $$x$$ if $$x\vee y = 1$$ and $$x\wedge y = 0$$.

Is there a lattice $$(L,\leq)$$ with more than $$2$$ elements and the following properties?

1. Every element of $$L\setminus\{0,1\}$$ has at least $$2$$ complements, and
2. for every $$a\in L\setminus\{0,1\}$$ there is $$b\in L$$ such that $$a \vee b \notin \{b,1\}$$ and $$a\wedge b \notin \{b,0\}$$ (implying in particular that $$a,b$$ are incomparable).

Among finite lattices, no. A finite lattice (with more than 2 elements) has atoms. Let $$a$$ be an atom. Condition 2 says there must be an incomparable $$b$$ that meets $$a$$ above bottom, which is clearly impossible.

Among infinite lattices, yes. Consider the following lattice, consisting of two slanted infinite ladders, and augmented bottom and top elements. If $$a$$ is in the left ladder (say), it has infinitely many complements in the right ladder, satisfying condition 1. Also, there is an element $$b$$ in the same ladder (pictured), which is incomparable with $$a$$, joins below $$1$$, and meets above $$0$$, satisfying condition 2. One can ensure property $$2$$ simply by taking reduced products.

Suppose that $$I$$ is an index set and $$L_{i}$$ is a lattice for each $$i\in I$$ such that each $$x\in L_{i}$$ has at least 2 complements.

Then suppose that $$\mathcal{F}$$ is a filter on $$I$$ such that $$P(I)/\mathcal{F}$$ is atomless (i.e. where $$\mathcal{F}$$ is nowhere an ultrafilter). Then I claim that the reduced product $$\prod_{i\in I}L_{i}/\mathcal{F}$$ satisfies properties 1 and 2. Let $$[(x_{i})_{i\in I}]_{\mathcal{F}}\in\prod_{i\in I}L_{i}/\mathcal{F}$$.

Observe that every element of $$\prod_{i\in I}L_{i}/\mathcal{F}$$ has at least two complements. In fact, the formula $$\forall x\exists y,z,x\wedge y=0\,\text{ and }\,x\vee y=1\,\text{ and }\,x\wedge z=0\,\text{ and }\,x\vee z=1$$ is a Horn sentence, and Horn formulae are always preserved by taking reduced products.

One can show that for each $$\mathbf{x}\in\prod_{i\in I}L_{i}/\mathcal{F}$$ with $$\mathbf{x}\not\in\{0,1\}$$, there is some $$\mathbf{y}\in\prod_{i\in I}\{0,1\}/\mathcal{F}$$ with $$\mathbf{x}\vee\mathbf{y}\neq 1,\mathbf{x}\wedge\mathbf{y}\neq 1$$ and where $$\mathbf{x},\mathbf{y}$$ are incomparable.

Automated counterexamples

This counterexample can be produced algorithmically.

The Feferman-Vaught theorem is a result that allows one to compute the truth value of a sentence $$\phi$$ in a reduced power $$\mathcal{A}^{I}/\mathcal{F}$$ as long as one is able to compute the truth value of sentences in $$P(I)/\mathcal{F}$$ and $$\mathcal{A}$$. In particular, since the theory of atomless Boolean algebras is $$\omega$$-categorical and hence complete, if $$P(I)/\mathcal{F},P(J)/\mathcal{F}$$ are atomless, then $$\mathcal{A}^{I}/\mathcal{F}$$ and $$\mathcal{A}^{J}/\mathcal{G}$$ are elementarily equivalent. Furthermore, if $$\mathcal{A}$$ is finite and $$P(I)/\mathcal{F}$$ is atomless and infinite and $$\phi$$ is a first order sentence, then the question of whether $$\mathcal{A}^{I}/\mathcal{F}\models\phi$$ is decidable and independent of $$I,\mathcal{F}$$.