# Is the first-order theory of complete atomic Boolean algebras finitely axiomatizable?

A complete atomic Boolean algebra is one that is isomorphic to a power set algebra, that is, a power set along with the operations of union, intersection, complement, the empty set, and the universal set. Is the first-order theory of the class of complete atomic Boolean algebras finitely axiomatizable? I conjecture that it is, and in fact all you need besides the Boolean algebra axioms is an axiom stating that it is atomic. Is this true? If not, what other axioms do you need?

• That's not the definition of "complete Boolean algebra." A complete Boolean algebra is one in which every set (of arbitrary cardinality) has a greatest lower bound and a least upper bound. In particular, complete Boolean algebras don't have to be atomic. Commented Jun 12, 2020 at 5:16
• user107952, please clarify two points. (1) By "complete Boolean algebra" do you mean (a) complete atomic Boolean algebra (which is isomorphic to a power set algebra), or do you mean (b) any complete Boolean algebra? I'll put the second question in a second comment.
– bof
Commented Jun 12, 2020 at 6:44
• user107952: Let $K$ be the class of Boolean algebras you're talking about. Let $\Sigma=Th(K)$ be the first-order theory of $K$, i.e., the set of all sentences holding true in all members of $K$. When you asked if the first-order theory of $K$ is finitely axiomatizable, did you mean (c) is the first-order theory of $K$ axiomatizable, i.e., is there a sentence $\alpha$ such that the theory $\Sigma$ is the set of all logical consequences of $\alpha$? Or did you really mean to ask (d) is there a sentence $\alpha$ such that $Mod(\alpha)=K$?
– bof
Commented Jun 12, 2020 at 6:51
• @bof I mean a complete atomic boolean algebra. I meant your (c). I know that complete atomic boolean algebras are not an elementary class. Commented Jun 12, 2020 at 19:13
• I believe the (first order) theory of complete atomic BAs is the same as the theory of atomic BAs, which is of course finitely axiomatizable. In fact I believe all infinite atomic BAs are elementarily equivalent. A back and forth argument (game) should work to prove that.
– bof
Commented Jun 12, 2020 at 19:52

Yes, the first-order theory of complete atomic Boolean algebras (BAs) is finitely axiomatizable, since it is equal to the theory of atomic BAs, as suggested by bof in the comments. So this theory is axiomatized by the finitely many axioms for BAs, together with the additional axiom: $$\forall x\, (x = \bot \lor \exists y\, (y \leq x\land \forall z\, (z \leq y\rightarrow (z = y\lor z = \bot)))).$$

To prove this, we need to show that every atomic BA is elementarily equivalent to a complete atomic BA. This is trivial for finite atomic BAs, since every finite BA is complete. So it remains to show that every infinite atomic BA is elementarily equivalent to a complete atomic BA. This follows from the fact that the theory of infinite atomic BAs is complete, so any infinite atomic BA is elementarily equivalent to any infinite complete atomic BA, such as $$\mathcal{P}(\omega)$$.

As bof also suggested in the comments, you can prove that the theory of infinite atomic BAs is complete using a back and forth argument / Ehrenfeucht–Fraïssé game. Instead of outlining this argument, I'll just tell you about a much more general theorem: Tarski's complete elementary invariants for Boolean algebras.

Let $$B$$ be a BA. We say an element $$x\in B$$ is atomic if for all $$y\leq x$$ with $$y\neq \bot$$, there exists an atom $$z\leq y$$. And we say an element $$x\in B$$ is atomless if there is no atom $$z \leq x$$. Let $$I(B)$$ be the ideal generated by the atomic and atomless elements. That is, $$I(B) = \{y\vee z\mid \text{y is atomic and z is atomless}\}.$$ Now define a sequence of BAs by induction: $$B^{(0)} = B$$ and $$B^{(n+1)} = B^{(n)}/I(B^{(n)})$$. Tarski's first invariant $$n$$ is the minimum natural number such that $$B^{(n)}$$ is the trivial algebra or $$\infty$$ if there is no such $$n$$.

If $$n = 0$$ (i.e. $$B$$ is already trivial) or $$n = \infty$$, then this is the only invariant. Otherwise, $$B^{(n)}$$ is trivial, but $$B^{(n-1)}$$ is non-trivial, and we define two more invariants by looking at $$B^{(n-1)}$$. Tarski's second invariant is just the question of whether $$B^{(n-1)}$$ is atomic, and Tarski's third invariant is the number of atoms in $$B^{(n-1)}$$, which could be any natural number or $$\infty$$ if there are infinitely many.

So for example, any infinite atomic BA has invariants $$(1,\text{atomic},\infty)$$. A finite BA has invariants $$0$$ if it is trivial or $$(1,\text{atomic},n)$$ if it has $$n$$ atoms. Any atomless BA has invariants $$(1,\text{not atomic},0)$$.

Now the theorem is that two BAs are elementarily equivalent if and only if they have the same Tarski invariants. The classic reference for this is

Tarski, A., "Arithmetical classes and types of Boolean algebras," Bulletin of the American Mathematical Society, vol. 55 (1949), p. 63.

But I couldn't easily find a copy of this paper online. You can also find a proof in the Handbook of Boolean Algebras, Volume 1, where Section 18 (the first half of Chapter 7) is devoted to the proof.

Since you're interested in the quesiton of finite axiomatization: By looking at the form of the axiomatization of the Tarski invariants, it follows that a completion of the theory of BAs is finitely axiomatizable if and only if none of its invariants are $$\infty$$.

• If Tarski 1949 is on just one page of the Bulletin then it's probably just an abstract. A detailed proof was published by Ershov in Russian, probably that was the first published proof of Tarski's result.
– bof
Commented Jun 14, 2020 at 3:14
• @bof I don't think that it's true that every BA is elementarily equivalent to a complete BA. In a complete BA, you can take the join of all the atoms, and its complement is atomless. So the FO theory of complete BAs is the theory of BAs with first Tarski invariant $0$ or $1$ (which is indeed finitely axiomatizable). Commented Jun 14, 2020 at 4:34
• Duh. Brain malfunction. What I mean to say was that every Boolean algebra in which the join of all the atoms exists (what I called "separable" BA in my comment way back) is elementarily equivalent to a complete BA.
– bof
Commented Jun 14, 2020 at 4:43
• @bof Yep, I agree with that. Commented Jun 14, 2020 at 4:47
• The Ershov reference is: Yu. L. Ershov, Decidability of the elementary theory of relatively complemented distributive lattices and the theory of filters, Algebra i Logika Sem. 3 (1964), 17-38 (Russian). I suppose that is cited in the Handbook of Boolean Algebra. I should get myself a copy of that, next time I win the lottery.
– bof
Commented Jun 14, 2020 at 5:05