There are several different signatures and conventions used for Boolean algebras:
- 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.
- 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:
- 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).
Read more about this topic: List Of First-order Theories