This is an excerpt from my book-in-progress on diverse elementary topics in logic, from the chapter on model theory. My view is that Boolean-valued models should be elevated to the status of a standard core topic of elementary model theory, adjacent to the ultrapower construction. The theory of Boolean-valued models is both beautiful and accessible, both generalizing and explaining the ultrapower method, while also partaking of deeper philosophical issues concerning multi-valued truth.
Boolean-valued models
Let us extend our familiar model concept from classical predicate logic to the comparatively fantastic realm of multi-valued predicate logic. We seek a multi-valued-truth concept of model, with a domain of individuals of some kind and interpretations for the relations, functions, and constants from a first-order language, but in which the truths of the model are not necessarily black and white, but exhibit their truth values in a given multi-valued logic. Let us focus especially on the case of Boolean-valued models, using a complete Boolean algebra , since this case has been particularly well developed and successful; the set-theoretic method of forcing, for example, amounts to using -valued models of set theory with carefully chosen complete Boolean algebras and has been used impressively to establish a sweeping set-theoretic independence phenomenon, showing that numerous set-theoretic principles such as the axiom of choice and the continuum hypothesis are independent of the other axioms of set theory.
The main idea of Boolean-valued models, however, is applicable with any theory, not just set theory, and there are Boolean-valued graphs, Boolean-valued orders, Boolean-valued groups, rings, and fields. So let us develop a little of this theory, keeping in mind that the basic construction and ideas also often work fruitfully with other multi-valued logics, not just Boolean algebras.
Definition of Boolean-valued models
We defined in an earlier section what it means to be a model in classical first-order predicate logic—one specifies the domain of the model, a set of individuals that will constitute the universe of the model over which all the quantifiers will range, and then provides interpretations on that domain for each relation symbol, function symbol, and constant symbol in the language. For each relation symbol , for example, and any suitable tuple of individuals from the domain, one specifies whether is to hold or fail in the model.
The main idea for defining what it means to be a model in multi-valued predicate logic is to replace these classical yes-or-no atomic truths with multi-valued atomic truth assertions. Specifically, for any Boolean algebra , a -valued model in the language consists of a domain , whose elements are called names, and an assignment of -valued truth values for all the simple atomic formulas using parameters from that domain: The double-bracketed expressions here denote an element of the Boolean algebra —one thinks of as the -truth value of in the model, and the model is defined by specifying these values for the simple atomic formulas.
We shall insist in any Boolean-valued model that the atomic truth values obey the laws of equality: And if the language includes functions symbols, then we also insist on the functionality axioms: These requirements assert respectively in the Boolean-valued context that the equality axiom holds for function application, that the function takes on some value, and that the function takes on at most one value. In effect, the Boolean-valued model treatment of functions regards them as as defined by their graph relations, and these functionality axioms ensure that the relation has the features that would be expected of such a graph relation.
In summary, a -valued model is a domain of names together with -valued truth assignments for the simple atomic assertions about those names, which obey the equality and functionality axioms.
Boolean-valued equality
The nature of equality in the Boolean-valued setting offers an interesting departure from the usual classical treatment that is worth discussing explicitly. Namely, in classical predicate logic with equality, distinct elements of the domain are taken to represent distinct individuals in the model—the assertion is true in the model only when and are identical as elements of the domain. In the Boolean-valued setting, however, we want to relax this in order to allow equality assertions to have an intermediate Boolean value. For this reason, distinct elements of the domain can no longer be taken to represent definitely distinct individuals, since the equality assertion might have some nonzero or intermediate degree of truth. The elements of the domain of a Boolean-valued model are allowed in effect a bit of indecision or indeterminacy about who they are and whether they might be identical. This is why we think of the elements of the domain as names for individuals, rather than as the individuals themselves. Two different names can have an intermediate truth-value possibility of naming the same or different individuals.
Extending to Boolean-valued truth
By definition, every -valued model provides -valued truth assertions for the simple atomic formulas. We now extend these Boolean-valued truth assignments to all assertions of the language through the following natural recursion: On the right-hand side, we make the logical calculations in each case using the operations of the Boolean algebra . In the existential case, the supremum may range over an infinite set of Boolean values, if the domain of the model is infinite, and so this supremum might not be realized as an element of , if it is not complete. This is precisely why one commonly considers -valued models especially in the case of a complete Boolean algebra —the completeness of ensures that this supremum exists and so the recursion has a solution.
The reader may check by induction on that the general equality axiom now has Boolean value one. The Boolean-valued structure is full if for every formula in and in , there is some such that . That is, a model is full when it is rich enough with names that the Boolean value of every existential statement is realized by a particular witness, reducing the infinitary supremum in the recursive definition to a single largest element.
A simple example
For every natural number let be the graph on vertices forming an -cycle with edge relation . So we have a triangle , a square , a pentagon , and so on. Let be the power set of these indices, which forms a complete Boolean algebra. We define a -valued graph model as follows. We take as names the sequences with for every .
We define the equality and edge relations on these names as follows: Thus, two names are equal exactly to extent that they have the same coordinates, and two names are connected by the edge relation exactly to the extent to that this is true on the coordinates. It is now easy to verify the equality axioms, since is true to at least the extent that , , and are true, since if , , and in , then also . So this is a -valued graph model.
So we have a Boolean-valued graph. Is it connected? Does that question make sense? Of course, we don’t have an actual graph here, but only a -valued graph, and so in principle we only know how to compute the Boolean value of statements that are expressible in the language of graph theory. Since connectivity is not formally expressible, except in the bounded finite cases, this question might not be sensible.
Let me argue that it is indeterminate whether this graph is a complete graph with every pair of distinct nodes connected by an edge. After all, is the complete graph on three vertices, and it will follow from the theorem below that the Boolean value of the statement contains the element and therefore this Boolean value is not zero. Meanwhile, the assertion that the graph is not complete, however, also gets a nonzero Boolean value, since every except has distinct nodes with no edge between them. In a robust sense, the graph-theoretic truths of combine the truths of all the various graphs .
Note also that as increases, the graphs have nodes that are increasingly far apart. Fix any name and choose such that the distance between and in is not bounded by any particular uniform bound. In , it follows that and have no particular definite finite distance, and this can be viewed as a sense in which is not connected.
A combination of many models
Let us flesh out the previous example with a more general analysis. Suppose we have a family of models in a common language . Let be the power set of the set of indices , a complete Boolean algebra. We define a -valued model as follows. The set of names will be precisely the product of the models , which is to say, the -tuples with for every , and the simple atomic truth values are defined like this: One can now prove the equality and functionality axioms, and so this is a -valued model.
Theorem. The Boolean-valued model described above is full, and Boolean-valued truth can be computed coordinatewise:
Proof. We prove this by induction on , for assertions using only simple atomic formulas, , , and . The simple atomic case is part of what it means to be a Boolean-valued model. If the theorem is true for , then it will be true for , since negation in is complementation in , as follows: If the theorem is true for and , then it will be true for as follows: For the quantifier case , choose for which , if possible. It follows that and from this it follows that , since whenever succeeds as a witness then so also will . Consequently, the model is full, and we see that as desired.
Boolean ultrapowers
Every Boolean-valued model can be transformed into a classical model, a -valued model, by means of a simple quotient construction. Suppose that is a -valued model for some Boolean algebra and that is an ultrafilter on the Boolean algebra.
Define an equivalence relation on the set of names by The quotient structure will consist of equivalence classes of names by this equivalence relation. We define the atomic truths of the quotient structure similarly by reference to whether these truths hold with a value in . Namely, For function symbols , we define These definitions are well-defined modulo precisely because of the equality axiom properties of the Boolean-valued model . For example, if , then , but by the equality axiom, and so if is in , then so will be .
We defined atomic truth in the quotient structure by reference to the truth value being -large. In fact, this reduction will continue for all truth assertions in the quotient structure, which we prove as follows.
Theorem. (Łoś theorem for Boolean ultrapowers) Suppose that is a full -valued model for a Boolean algebra , and that is an ultrafilter. Then a statement is true in the Boolean quotient structure if and only if the Boolean value of the statement is in .
Proof. We prove this by induction on . The simple atomic case holds by the definition of the quotient structure. Boolean connectives , follow easily using that is a filter and that it is an ultrafilter. Consider the quantifier case , where by induction the theorem holds for itself. If the quotient structure satisfies the existential , then there is a name for which it satisfies , and so by induction , in which case also , since this latter Boolean value is at least as great as the former. Conversely, if , then by fullness this existential Boolean value is realized by some name , and so , which by induction implies that the quotient satisfies and consequently also , as desired.
Note how fullness was used in the existential case of the inductive argument.
I’d like to write about the situation that occurs in set theory when a forcing extension arises over a ground model in two different ways simultaneously, using generic filters over two different forcing notions and . The general fact, stated in theorem 1, is that in this case, the two forcing notions are actually isomorphic on a cone , with the isomorphism carrying the one generic filter to the other. In other words, below these respective conditions and , the forcing notions and the respective generic filters are not actually different.
I have always assumed that this fact was part of the classical forcing folklore results, but it doesn’t seem to be mentioned explicitly in the usual forcing literature (it appears as lemma 25.5 in Jech’s book), and so I am writing an account of it here. Victoria Gitman and I have need of it in a current joint project. (Bob Solovay mentions in the comments below that the result is due to him, and provides a possible 1975 reference.)
Theorem 1. If , where and are -generic filters on the complete Boolean algebras and , respectively, then there are conditions and such that is isomorphic to by an isomorphism carrying to .
The proof will also establish the following related result, concerning the situation where one extension is merely contained in the other.
Theorem 2. If , where and are -generic filters on the complete Boolean algebras and , respectively, then there are conditions and such that is isomorphic to a complete subalgebra of .
By , where is a condition in (that is, a nonzero element of ), what I mean is the Boolean algebra consisting of the interval in , using relative complement as the negation of . This is the complete Boolean algebra that arises when forcing with the conditions in below .
Proof: In order to prove theorem 2, let me assume at first only that . It follows that for some -name , and we may choose a condition forcing that is a -generic filter on .
I claim that there is some such that every has . Note that every has by the truth lemma, since , and so for . If forces that every in the generic filter has that property, then indeed every has as claimed.
In other words, from the perspective of the forcing, every has a nonzero possibility to be in .
Define by Using the fact that forces that is a filter, it is straightforward to verify that
, since if and , then .
, since .
, since .
Thus, is a Boolean algebra embedding of into .
Let me argue that this embedding is a complete embedding. Suppose that for some subset with . Since is -generic, it follows that just in case meets . Thus, , and so , and so is complete, as desired. This proves theorem 2.
To prove theorem 1, let me now assume fully that . In this case, there is a name for which . By strengthening , we may assume without loss that also forces that, that is, that forces , where is the canonical -name for the generic object, and is the -name of the -name . Let us also strengthen to ensure that forces is -generic for . For define as above, which provides a complete embedding of to . I shall now argue that this embedding is dense below . Suppose that in . Since forces and also , it must also force that there is some in that forces via over that . So there must really be some forcing . So , which forces , will also force , and so , which means in . Thus, the range of on is dense below , and so is a complete dense embedding of to . Since these are complete Boolean algebras, this means that is actually an isomorphism of with , as desired.
Finally, note that if below , then since , it follows that , which is to say , and so carries to on these cones. So is the isomorphism stated in theorem 1.QED
Finally, I note that one cannot get rid of the need to restrict to cones, since it could be that and are the lottery sums of a common forcing notion, giving rise to , together with totally different non-isomorphic forcing notions below some other incompatible conditions. So we cannot expect to prove that , and are content to get merely that , an isomorphism below respective conditions.