Boolean-valued model


In mathematical logic, a Boolean-valued model is a generalization of the ordinary Tarskian notion of structure from model theory. In a Boolean-valued model, the truth values of propositions are not limited to "true" and "false", but instead take values in some fixed complete Boolean algebra.
Boolean-valued models were introduced by Dana Scott, Robert M. Solovay, and Petr Vopěnka in the 1960s in order to help understand Paul Cohen's method of forcing. They are also related to Heyting algebra semantics in intuitionistic logic.

Definition

Fix a complete Boolean algebra B and a first-order language L; the signature of L will consist of a collection of constant symbols, function symbols, and relation symbols.
A Boolean-valued model for the language L consists of a universe M, which is a set of elements, together with interpretations for the symbols. Specifically, the model must assign to each constant symbol of L an element of M, and to each n-ary function symbol f of L and each n-tuple <a0,...,an-1> of elements of M, the model must assign an element of M to the term f.
Interpretation of the atomic formulas of L is more complicated. To each pair a and b of elements of M, the model must assign a truth value ||a = b|| to the expression a = b; this truth value is taken from the Boolean algebra B. Similarly, for each n-ary relation symbol R of L and each n-tuple <a0,...,an-1> of elements of M, the model must assign an element of B to be the truth value ||R||.

Interpretation of other formulas and sentences

The truth values of the atomic formulas can be used to reconstruct the truth values of more complicated formulas, using the structure of the Boolean algebra. For propositional connectives, this is easy; one simply applies the corresponding Boolean operators to the truth values of the subformulae. For example, if φ and ψ are formulas with one and two free variables, respectively, and if a, b, c are elements of the model's universe to be substituted for x, y, and z, then the truth value of
is simply
The completeness of the Boolean algebra is required to define truth values for quantified formulas. If φ is a formula with free variable x, then
where the right-hand side is to be understood as the supremum in B of the set of all truth values ||φ|| as a ranges over M.
The truth value of a formula is sometimes referred to as its probability. However, these are not probabilities in the ordinary sense, because they are not real numbers, but rather elements of the complete Boolean algebra B.

Boolean-valued models of set theory

Given a complete Boolean algebra B there is a Boolean-valued model denoted by VB, which is the Boolean-valued analogue of the von Neumann universe V. Informally, the elements of VB are "Boolean-valued sets". Given an ordinary set A, every set either is or is not a member; but given a Boolean-valued set, every set has a certain, fixed "probability" of being a member of A. Again, the "probability" is an element of B, not a real number. The concept of Boolean-valued sets resembles, but is not the same as, the notion of a fuzzy set.
The elements of the Boolean-valued set, in turn, are also Boolean-valued sets, whose elements are also Boolean-valued sets, and so on. In order to obtain a non-circular definition of Boolean-valued set, they are defined inductively in a hierarchy similar to the cumulative hierarchy. For each ordinal α of V, the set VBα is defined as follows.
The class VB is defined to be the union of all sets VBα.
It is also possible to relativize this entire construction to some transitive model M of ZF. The Boolean-valued model MB is obtained by applying the above construction inside M. The restriction to transitive models is not serious, as the Mostowski collapsing theorem implies that every "reasonable" model is isomorphic to a transitive one.
Once the elements of VB have been defined as above, it is necessary to define B-valued relations of equality and membership on VB. Here a B-valued relation on VB is a function from VB × VB to B. To avoid confusion with the usual equality and membership, these are denoted by ||x = y|| and ||x ∈ y|| for x and y in VB. They are defined as follows:
The symbols ∑ and ∏ denote the least upper bound and greatest lower bound operations, respectively, in the complete Boolean algebra B. At first sight the definitions above appear to be circular: || ∈ || depends on || = ||, which depends on || ⊆ ||, which depends on || ∈ ||. However, a close examination shows that the definition of || ∈ || only depends on || ∈ || for elements of smaller rank, so || ∈ || and || = || are well defined functions from VB×VB to B.
It can be shown that the B-valued relations || ∈ || and || = || on VB make VB into a Boolean-valued model of set theory. Each sentence of first-order set theory with no free variables has a truth value in B; it must be shown that the axioms for equality and all the axioms of ZF set theory have truth value 1. This proof is straightforward, but it is long because there are many different axioms that need to be checked.

Relationship to forcing

Set theorists use a technique called forcing
to obtain independence results and to construct models of set theory for other purposes. The method was originally developed by Paul Cohen but has been greatly extended since then. In one form, forcing "adds to the universe" a generic subset of a poset, the poset being designed to impose interesting properties on the newly added object. The wrinkle is that it can be proved that there simply is no such generic subset of the poset. There are three usual ways of dealing with this:
Boolean-valued models can be used to give semantics to syntactic forcing; the price paid is that the semantics is not 2-valued, but assigns truth values from some complete Boolean algebra. Given a forcing poset P, there is a corresponding complete Boolean algebra B, often obtained as the collection of regular open subsets of P, where the topology on P is defined by declaring all lower sets open.
Now the order on B can replace P for forcing purposes, and the forcing relation can be interpreted semantically by saying that, for p an element of B and φ a formula of the forcing language,
where ||φ|| is the truth value of φ in VB.
This approach succeeds in assigning a semantics to forcing over V without resorting to fictional generic objects. The disadvantages are that the semantics is not 2-valued, and that the combinatorics of B are often more complicated than those of the underlying poset P.

Boolean-valued models and generic objects over countable transitive models

One interpretation of forcing starts with a countable transitive model M of ZF set theory, a partially ordered set P, and a "generic" subset G of P, and constructs a new model of ZF set theory from these objects. Cohen's construction can be carried out using Boolean-valued models as follows.
We now explain these steps in more detail.
For any poset P there is a complete Boolean algebra B and a map e from P to B+ such that the image is dense, e≤e whenever p≤q, and ee=0 whenever p and q are incompatible. This Boolean algebra is unique up to isomorphism. It can be constructed as the algebra of regular open sets in the topological space of P.
The map from the poset P to the complete Boolean algebra B is not injective in general. The map is injective if and only if P has the following property: if every r≤p is compatible with q, then p≤q.
The ultrafilter U on B is defined to be the set of elements b of B that are greater than some element of G. Given an ultrafilter U on a Boolean algebra, we get a homomorphism to
by mapping U to true and its complement to false. Conversely, given such a homomorphism, the inverse image of true is an ultrafilter, so ultrafilters are essentially the same as homomorphisms to.
If g is a homomorphism from a Boolean algebra B to a Boolean algebra C and MB is any
B-valued model of ZF we can turn MB into a C -valued model by applying the homomorphism g to the value of all formulas. In particular if C is we get a -valued model. This is almost the same as an ordinary model: in fact we get an ordinary model on the set of equivalence classes under || = || of a -valued model. So we get an ordinary model of ZF set theory by starting from M, a Boolean algebra B, and an ultrafilter U on B.
We have seen that forcing can be done using Boolean-valued models, by constructing a Boolean algebra with ultrafilter from a poset with a generic subset. It is also possible to go back the other way: given a Boolean algebra B, we can form a poset P of all the nonzero elements of B, and a generic ultrafilter on B restricts to a generic set on P. So the techniques of forcing and Boolean-valued models are essentially equivalent.