You are currently browsing the tag archive for the ‘completeness theorem’ tag.

Last time in this series on Stone duality, we observed a perfect duality between finite Boolean algebras and finite sets, which we called “baby Stone duality”:

- Every finite Boolean algebra is obtained from a finite set by taking its power set (or set of functions from to , with the Boolean algebra structure it inherits “pointwise” from ). The set may be defined to be , the set of Boolean algebra homomorphisms from to .
- Conversely, every finite set is obtained from the Boolean algebra by taking its “hom-set” .

More precisely, there are natural isomorphisms

in the categories of finite Boolean algebras and of finite sets, respectively. In the language of category theory, this says that these categories are (equivalent to) one another’s opposite — something I’ve been meaning to explain in more detail, and I promise to get to that, soon! In any case, this duality says (among other things) that finite Boolean algebras, no matter how abstractly presented, can be represented concretely as power sets.

Today I’d like to apply this representation to *free* Boolean algebras (on finitely many generators). What is a free Boolean algebra? Again, the proper context for discussing this is category theory, but we can at least convey the idea: given a finite set of letters , consider the Boolean algebra whose elements are logical equivalence classes of formulas you can build up from the letters using the Boolean connectives (and the Boolean constants ), where two formulas are defined to be *logically equivalent* if and can be inferred purely on the basis of the Boolean algebra axioms. This is an excellent example of a very abstract description of a Boolean algebra: syntactically, there are infinitely many formulas you can build up, and the logical equivalence classes are also infinite and somewhat hard to visualize, but the mess can be brought under control using Stone duality, as we now show.

First let me cut to the chase, and describe the key property of free Boolean algebras. Let be any Boolean algebra; it could be a power set, the lattice of regular open sets in a topology, or whatever, and think of a function from the set of letters to as *modeling* or interpreting the atomic formulas as elements of . The **essential property** of the free Boolean algebra is that we can extend this interpretation in a unique way to a Boolean algebra map . The way this works is that we map a formula like to the obvious formula . This is well-defined on logical equivalence classes of formulas because if in , i.e., if the equality is derivable just from the Boolean algebra axioms, then of course holds in as the Boolean algebra axioms hold in . Thus, there is a natural bijective correspondence between functions and Boolean algebra maps ; to get back from a Boolean algebra map to the function , simply compose the Boolean algebra map with the function which interprets elements of as equivalence classes of atomic formulas in .

To get a better grip on , let me pass to the Boolean ring picture (which, as we saw last time, is equivalent to the Boolean algebra picture). Here the primitive operations are addition and multiplication, so in this picture we build up “formulas” from letters using these operations (e.g., and the like). In other words, the elements of can be considered as “polynomials” in the variables . Actually, there are some simplifying features of this polynomial algebra; for one thing, in Boolean rings we have idempotence. This means that for , and so a monomial term like reduces to its *support* . Since each letter appears in a support with exponent 0 or 1, it follows that there are possible supports or Boolean monomials, where denotes the cardinality of .

Idempotence also implies, as we saw last time, that for all elements , so that our polynomials = -linear combinations of monomials are really -linear combinations of Boolean monomials or supports. In other words, each element of is uniquely a linear combination

where

i.e., the set of supports forms a basis of as a -vector space. Hence the cardinality of the free Boolean ring is .

**Remark**: This gives an algorithm for checking logical equivalence of two Boolean algebra formulas: convert the formulas into Boolean ring expressions, and using distributivity, idempotence, etc., write out these expressions as Boolean polynomials = -linear combinations of supports. The Boolean algebra formulas are equivalent if and only if the corresponding Boolean polynomials are equal.

But there is another way of understanding free Boolean algebras, via baby Stone duality. Namely, we have the power set representation

where is the set of Boolean algebra maps . However, the freeness property says that these maps are in bijection with functions . What are these functions? They are just truth-value assignments for the elements (atomic formulas, or variables) ; there are again many of these. This leads to the method of **truth tables**: each formula induces (in one-one fashion) a function

which takes a Boolean algebra map , aka a truth-value assignment for the variables , to the element of obtained by instantiating the assigned truth values for the variables and evaluating the resulting Boolean expression for in . (In terms of power sets,

identifies each equivalence class of formulas with the set of truth-value assignments of variables which render the formula “true” in .) The fact that the representation is injective means precisely that if formulas are inequivalent, then there is a truth-value assignment which renders one of them “true” and the other “false”, hence that they are distinguishable by truth tables.

- Remark: This is an instance of what is known as a
*completeness theorem*in logic. On the syntactic side, we have a notion of provability of formulas (that is logically equivalent to , or in if this is derivable from the Boolean algebra axioms). On the semantic side, each Boolean algebra homomorphism can be regarded as a*model*of in which each formula becomes true or false under . The method of truth tables then says that there are enough models or truth-value assignments to detect provability of formulas, i.e., is provable if it is true when interpreted in any model . This is precisely what is meant by a completeness theorem.

There are still other ways of thinking about this. Let be a Boolean algebra map, aka a model of . This model is completely determined by

- The maximal ideal in the Boolean ring , or
- The maximal filter or ultrafilter in .

Now, as we saw last time, in the case of finite Boolean algebras, each (maximal) ideal is principal: is of the form for some . Dually, each (ultra)filter is principal: is of the form for some . The maximality of the ultrafilter means that there is no nonzero element in smaller than ; we say that is an *atom* in (NB: not to be confused with atomic formula!). So, we can also say

- A model of a finite Boolean algebra is specified by a unique atom of .

Thus, baby Stone duality asserts a Boolean algebra isomorphism

Let’s give an example: consider the free Boolean algebra on three elements . If you like, draw a Venn diagram generated by three planar regions labeled by . The atoms or smallest nonzero elements of the free Boolean algebra are then represented by the regions demarcated by the Venn diagram. That is, the disjoint regions are labeled by the eight atoms

According to baby Stone duality, any element in the free Boolean algebra (with elements) is uniquely expressible as a disjoint union of these atoms. Another way of saying this is that the atoms form a basis (alternative to Boolean monomials) of the free Boolean algebra as -vector space. For example, as an exercise one may calculate

The unique expression of an element (where is given by a Boolean formula) as a -linear combination of atoms is called the **disjunctive normal form** of the formula. So yet another way of deciding when two Boolean formulas are logically equivalent is to put them both in disjunctive normal form and check whether the resulting expressions are the same. (It’s basically the same idea as checking equality of Boolean polynomials, except we are using a different vector space basis.)

All of the above applies not just to free (finite) Boolean algebras, but to general finite Boolean algebras. So, suppose you have a Boolean algebra which is generated by finitely many elements . *Generated* means that every element in can be expressed as a Boolean combination of the generating elements. In other words, “generated” means that if we consider the inclusion function , then the unique Boolean algebra map which extends the inclusion is a *surjection*. Thinking of as a Boolean ring map, we have an ideal , and because is a surjection, it induces a ring isomorphism

The elements of can be thought of as equivalence classes of formulas which become *false* in under the interpretation . Or, we could just as well (and it may be more natural to) consider instead the *filter* of formulas in which become *true* under the interpretation . In any event, what we have is a propositional language consisting of classes of formulas, and a filter consisting of formulas, which can be thought of as theorems of . Often one may find a filter described as the smallest filter which contains certain chosen elements, which one could then call *axioms* of .

In summary, any *propositional theory* (which by definition consists of a set of propositional variables together with a filter of the free Boolean algebra, whose elements are called *theorems* of the theory) yields a Boolean algebra , where dividing out by means we take equivalence classes of elements of under the equivalence relation defined by the condition “ belongs to “. The partial order on equivalence classes [] is defined by [] [] iff belongs to . The Boolean algebra defined in this way is called the *Lindenbaum algebra* of the propositional theory.

Conversely, any Boolean algebra with a specified set of generators can be thought of as the Lindenbaum algebra of the propositional theory obtained by taking the as propositional variables, together with the filter obtained from the induced Boolean algebra map . A *model* of the theory should be a Boolean algebra map which interprets the formulas of as true or false, but in such a way that the theorems of the theory (the elements of the filter) are all interpreted as “true”. In other words, a model is the same thing as a Boolean algebra map

i.e., we may identify a model of a propositional theory with a Boolean algebra map out of its Lindenbaum algebra.

So the set of models is the set , and now baby Stone duality, which gives a canonical isomorphism

implies the following

**Completeness theorem**: If a formula of a finite propositional theory is “true” when interpreted under any model of the theory, then the formula is provable (is a theorem of the theory).

**Proof**: Let be the Lindenbaum algebra of the theory, and let be the class of formulas provably equivalent to a given formula under the theory. The Boolean algebra isomorphism takes an element to the map . If for all models , i.e., if , then . But then [] , i.e., , the filter of provable formulas.

In summary, we have developed a rich vocabulary in which Boolean algebras are essentially the same things as propositional theories, and where models are in natural bijection with maximal ideals in the Boolean ring, or ultrafilters in the Boolean algebra, or [in the finite case] atoms in the Boolean algebra. But as we will soon see, ultrafilters have a significance far beyond their application in the realm of Boolean algebras; in particular, they crop up in general studies of topology and convergence. This is in fact a vital clue; the key point is that the set of models or ultrafilters carries a canonical topology, and the interaction between Boolean algebras and topological spaces is what Stone duality is all about.

## Recent Comments