3
$\begingroup$

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).
$\endgroup$

2 Answers 2

5
$\begingroup$

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.

Two infinite ladders and augmented bounds

$\endgroup$
2
$\begingroup$

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}$.

$\endgroup$

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.