Finding the atoms and elements of a Lindenbaum–Tarski algebra

Question

Let B be the Lindenbaum–Tarski algebra with three variables $p,q,r$

(1) Find all the atoms of $B$.

(2) How many elements of does $B$ have?

So I think I know what an atom is, but I'm still not sure where to start with this question. Any help is appreciated.

Answer 1

Consider the sentential language $\mathcal L = \{ p,q,r, \lnot, \land, \lor, \rightarrow \}$.

If we set :

$\alpha^* = [\alpha] =$ the equivalence classes of formulas $\beta : \beta \equiv \alpha$

we have :

$0 = \bot =$ the equivalence classes of formulas $\beta : \beta \equiv p \land \lnot p$

and :

$1 = \top =$ the equivalence classes of formulas $\beta : \beta \equiv p \lor \lnot p$.

We have :

$\alpha^* \le \beta^*$ iff $\vDash \alpha \rightarrow \beta$

and finally we have that:

$\alpha^*$ is an atom iff $\alpha^* \ne 0$ and for every $\beta$, if $\beta^* \le \alpha^*$, then either $\beta^* = \alpha^*$ or $\beta^* = 0$.

---

For 1, consider $\alpha := (p \land q \land r)$; $\alpha^* \ne 0$ because $\alpha$ is satisfiable by the valuation $v_0$ such that $v_0(p)=v_0(q)=v_0(r)=1$.

In oder to show that $\alpha^*$ is an atom, we have to prove that, for every $\beta$ such that $\beta \rightarrow \alpha$ and $\beta$ is satisfiable (i.e. not $\beta \equiv \bot$), then $\beta \equiv \alpha$.

We want that : $\vDash \beta \rightarrow \alpha$.

This means that at most $v_0(\beta)=1$ for $v_0(p)=v_0(q)=v_0(r)=1$ (otherwise we will have a row in the truth table for $\beta \rightarrow \alpha$ with $\beta$ true and $\alpha$ false, contrary to assumption).

But we need that at least $v_0(\beta)=1$ for $v_0(p)=v_0(q)=v_0(r)=1$, otherwise $\beta \equiv \bot$.

This means that $v_0(\beta)=1$ exactly when $v_0(p)=v_0(q)=v_0(r)=1$, i.e. $\beta \equiv (p \land q \land r)$, i.e.

$\beta \equiv \alpha$.

With $n$ sentential letters, we have $2^n$ atoms; thus, in this example we have $8$ atoms : $(p \land q \land r), (p \land q \land \lnot r), (p \land \lnot q \land r), \ldots$.

---

---

Note

A Lindenbaum–Tarski algebra is atomless only if has countable many sentential letters.

In this case, the above proof can be adapted to find, for a formula $\alpha$ whatever, a formula $\beta$ not equivalent to $\alpha$ such that $\vDash \beta \rightarrow \alpha$.

If $\alpha$ contains $n$ sentential letters : $p_1,\ldots,p_n$ , it is enough to choose a $p_k$ not included in that list (we can always find one; for example : $p_{n+1}$) and consider the formula $\beta := \alpha \land p_k$.

It is easy to show that : $\vDash \beta \rightarrow \alpha$ and $\nvDash \alpha \rightarrow \beta$