List of First-order Theories - Boolean Algebras

There are several different signatures and conventions used for Boolean algebras:

1. The signature has 2 constants, 0 and 1, and two binary functions ∧ and ∨ ("and" and "or"), and one unary function ¬ ("not"). This is a little confusing as the functions use the same symbols as the propositional functions of first-order logic.
2. In set theory, a common convention is that the language has 2 constants, 0 and 1, and two binary functions · and +, and one unary function −. The three functions have the same interpretation as the functions in the first convention. Unfortunately, this convention clashes badly with the next convention:
3. In algebra, the usual convention is that the language has 2 constants, 0 and 1, and two binary functions · and +. The function · has the same meaning as ∧, but a+b means a∨b∧¬(a∧b). The reason for this is that the axioms for a Boolean algebra are then just the axioms for a ring with 1 plus ∀x x2 = x. Unfortunately this clashes with the standard convention in set theory given above.

The axioms are:

• The axioms for a distributive lattice (see above)
• ∀a∀b a∧¬a = 0, ∀a∀b a∨¬a = 1 (properties of negation)
• Some authors add the extra axiom ¬0=1, to exclude the trivial algebra with one element.

Tarski proved that the theory of Boolean algebras is decidable.

We write x ≤ y as an abbreviation for x ∧ y = x, and atom(x) as an abbreviation for ¬x = 0 ∧ ∀y y≤x → y = 0 ∨ y = x, read as "x is an atom", in other words a non-zero element with nothing between it and 0. Here are some first-order properties of Boolean algebras:

• Atomic: ∀x x=0 ∨ ∃y y≤x ∧ atom(y)
• Atomless: ∀x ¬atom(x)

The theory of atomless Boolean algebras is ω-categorical and complete.

For any Boolean algebra B, there are several invariants defined as follows.

• the ideal I(B) consists of elements that are the sum of an atomic and an atomless element.
• The quotient algebras Bi of B are defined inductively by B0=B, Bk+1 = Bk/I(Bk).
• The invariant m(B) is the smallest integer such that Bm+1 is trivial, or ∞ if no such integer exists.
• If m(B) is finite, the invariant n(B) is the number of atoms of Bm(B) if this number is finite, or ∞ if this number is infinite.
• The invariant l(B) is 0 if Bm(B) is atomic or if m(B) is ∞, and 1 otherwise.

Then two Boolean algebras are elementarily equivalent if and only if their invariants l, m, and n are the same. In other words, the values of these invariants classify the possible completions of the theory of Boolean algebras. So the possible complete theories are:

• The trivial algebra (if this is allowed; sometimes 0≠1 is included as an axiom.)
• The theory with m=∞
• The theories with m a natural number, n a natural number or ∞, and l = 0 or 1 (with l = 0 if n=0).