Boolean-valued model

Boolean-valued model

In mathematical logic, a Boolean-valued model is a generalization of the ordinary Tarskian notion of structure or model, in which the truth values of propositions are not limited to "true" and "false", but 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.

Definition

Fix a complete Boolean algebra "B""B" here is assumed to be "nondegenerate"; that is, 0 and 1 must be distinct elements of "B". Authors writing on Boolean-valued models typically take this requirement to be part of the definition of "Boolean algebra", but authors writing on Boolean algebras in general often do not.] and a first-order language "L", the latter consisting of a collection of constant symbols, function symbols, and relation symbols. A Boolean-valued model for "L" then consists of a universe "M", which is a set of elements (or "names"), 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,...,a"n"-1> of elements of "M", the model must assign an element of "M" to the term "f"(a0,...,a"n"-1).

Interpretation of the relation symbols, and of equality, is more complicated: To each pair "a", "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 "B". Similarly, for each "n"-ary relation symbol "R" of "L" and each "n"-tuple <a0,...,a"n"-1> of elements of "M", the model must assign an element of "B" to be the truth value ||"R"(a0,...,a"n"-1)||.

Interpretation of other formulas and sentences

Other formulas can be interpreted using 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 φ("x") and ψ("y","z") 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: phi(a)landpsi(b,c)is simply: ||phi(a)landpsi(b,c)||=||phi(a)|| land ||psi(b,c)||

For quantified formulas we need to use the completeness of the Boolean algebra "B". If φ("x") is a formula with free variable "x" (and possibly other free variables that we suppress), then: ||exists xphi(x)||=igvee_{ain M}||phi(a)||where the right-hand side is to be understood as the supremum in "B" of the set of all truth values ||φ("a")||, where "a" ranges over "M".

The truth value of a formula is sometimes referred to as its probability. It needs to be understood that these are not probabilities in the ordinary sense; 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". (Strictly speaking, "VB" is a proper class, so we need to reinterpret what it means to be a model appropriately.) Informally, we think of "VB" as something like "Boolean-valued sets"; in other words, a Boolean-valued set, rather than having sharply defined elements and not-elements, has objects with a certain "probability" of being elements of the set. Again, the "probability" is an element of "B", not a real number. Compare with the notion of a fuzzy set.

The ("probabilistic") elements of the Boolean-valued set, in turn, are also Boolean-valued sets, whose elements are also Boolean-valued sets, and so on. To get a non-circular definition of Boolean-valued set we need to build them up in a hierarchy. So for each ordinal α of "V" we define the set "VαB" by::"VαB" is the union of "VβB" for β<α if α is a limit ordinal (including 0). :"Vα+1B" is the set of all functions from "VαB" to "B". (Such a function represents a "probabilistic" subset of "VαB"; if "f" is such a function, then for any "x"∈"VαB", "f"("x") is the probability that "x" is in the set.)We define the class "VB" to be the union of all sets "VαB".

It is also possible to relativize this entire construction to some transitive model "M" of ZF (or sometimes a fragment thereof). In that case we construct the Boolean-valued model "M""B" by applying the above construction "inside" "M". The restriction to transitive models is not serious, as the Mostowski collapsing theorem implies that every reasonable (=well founded extensional) model is isomorphic to a transitive one. (If the model "M" is not transitive things get messier, as "M"'s interpretation of what it means to be a "function" or an "ordinal" may differ from the "external" interpretation.)

Next we need to define two "B"-valued relations of equality and membership on the set "VB". (A "B"-valued relation on "VB" is a function from "VB"×"VB" to "B".)To avoid confusion with the usual equality and membership, they are denoted by ||"x"="y"|| and
|"x"∈"y"|| for "x" and "y" in "VB". They are defined as follows::||"x"∈"y"|| is defined to be ∑"t"∈Dom("y") ||"x"="t"|| ∧ "y"("t")   ("x" is in "y" if it is equal to something in "y"):||"x"="y"|| is defined to be ||"x"⊆"y"||∧||y⊆"x"||   ("x" equals "y" if "x" and "y" are both subsets of each other"), where:||"x"⊆"y"|| is defined to be ∏"t"∈Dom("x") "x"("t")⇒||"t"∈"y"||   ("x" is a subset of "y" if all elements of "x" are in "y")

The symbols ∑ and ∏ mean that we take a least upper bound or greatest lower bound 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".

Finally we need to check that these two "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 value in "B", and we need to check that all the axioms for equality and all the axioms of ZF set theory (written without free variables) have value the element "true" of "B". This is straightforward, but takes a long time because there are many different axioms that need to be checked.

Relationship to forcing

To obtain independence results and for many other purposes, set theorists use a technique called forcing, originally developed by Paul Cohen but since then much elaborated. 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 (for interesting posets) it can be proved that there simply "is" no such generic subset of the poset. There are three usual ways of dealing with this:
* syntactic forcing A "forcing relation" pVdashphi is defined between elements "p" of the poset and formulas φ of the "forcing language". This relation is defined syntactically and has no semantics; that is, no model is ever produced. Rather, starting with the assumption that ZFC (or other axiomatization of set theory) proves the independent statement, one shows that ZFC must also be able to prove a contradiction. However, the forcing is "over "V"; that is, it is not necessary to start with a countable transitive model. See Kunen for an exposition.
* countable transitive models One starts with a countable transitive model "M" of as much of set theory as is needed for the desired purpose, and that contains the poset. Then there "do" exist filters on the poset that are generic "over M"; that is, that meet all dense open subsets of the poset that happen also to be elements of "M".
* fictional generic objects Commonly, set theorists will simply "pretend" that the poset has a subset that is generic over all of "V". This generic object, in nontrivial cases, cannot be an element of "V", and therefore "does not really exist". (Of course, it's a point of philosophical contention whether "any" sets "really exist", but that is outside the scope of the current discussion.) Perhaps surprisingly, with a little practice this method is useful and reliable, but many find it philosophically unsatisfying.

Boolean-valued models and syntactic forcing

The Boolean-valued model approach can be seen as a way of giving a semantics to syntactic forcing; the price paid is that the semantics is not 2-valued ("true or false"), 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 generated by "cones" (sets of the form {"q"|"q"≤"p"}, for fixed "p"). (Other approaches to constructing "B" are discussed below.)

Now the order on "B" (after removing the zero element) can replace "P" for forcing purposes, and we can interpret the forcing relation "semantically" by saying that, for "p" an element of "B" and φ a formula of the forcing language,:pVdashphiiff pleq||phi||where again ||φ|| is the truth value of φ in "V""B".

Thus 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. (The conditions that the model be countable and transitive simplify some technical problems, but are not essential.) Cohen's construction can be carried out using Boolean-valued models as follows.
* Construct a complete Boolean algebra "B" as the complete Boolean algebra "generated by" the poset "P".
* Construct an ultrafilter "U" on "B" (or equivalently a homomorphism from "B" to the Boolean algebra {true, false}) from the generic subset "G" of "P".
* Use the homomorphism from "B" to {true, false} to turn the Boolean-valued model "MB" of the section above into an ordinary model of ZF.

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"+ (the non-zero elements of "B") such that the image is dense, "e"("p")≤"e"("q") whenever "p"≤"q", and "e"("p")"e"("q")=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" (with underlying set "P", and a base given by the sets "U""p" of elements "q" with "q"≤"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 (the image of) "G". Given an ultrafilter "U" on a Boolean algebra, we get a homomorphism to {true, false}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 {true, false}. (Algebraists might prefer to use maximal ideals instead of ultrafilters: the complement of an ultrafilter is a maximal ideal, and conversely the complement of a maximal ideal is an ultrafilter.)

If "g" is a homomorphism from a Boolean algebra "B" to a Boolean algebra "C" and "MB" is any "B"-valued model of ZF (or of any other theory for that matter) 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 {true, false} we get a {true, false}-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 {true, false}-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".(The model of ZF constructed like this is not transitive. In practice one applies the Mostowski collapsing theorem to turn this into a transitive model.)

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.

Notes

References

* Bell, J. L. (1985) "Boolean-Valued Models and Independence Proofs in Set Theory", Oxford. ISBN 0-19-853241-5
*springer|id=b/b016990|first=V.N.|last= Grishin
*
*
* cite book|author=Kusraev, A. G. and S. S. Kutateladze|title=Boolean Valued Analysis
publisher=Kluwer Academic Publishers|year=1999|id=ISBN 0-7923-5921-6
Contains an account of Boolean-valued models and applications to Riesz spaces, Banach spaces and algebras.
* Contains an account of forcing and Boolean-valued models written for mathematicians who are not set theorists.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Boolean algebras canonically defined — Boolean algebras have been formally defined variously as a kind of lattice and as a kind of ring. This article presents them more neutrally but equally formally as simply the models of the equational theory of two values, and observes the… …   Wikipedia

  • Boolean algebra (introduction) — Boolean algebra, developed in 1854 by George Boole in his book An Investigation of the Laws of Thought , is a variant of ordinary algebra as taught in high school. Boolean algebra differs from ordinary algebra in three ways: in the values that… …   Wikipedia

  • Boolean logic — is a complete system for logical operations. It was named after George Boole, who first defined an algebraic system of logic in the mid 19th century. Boolean logic has many applications in electronics, computer hardware and software, and is the… …   Wikipedia

  • Boolean algebra — This article discusses the subject referred to as Boolean algebra. For the mathematical objects, see Boolean algebra (structure). Boolean algebra, as developed in 1854 by George Boole in his book An Investigation of the Laws of Thought,[1] is a… …   Wikipedia

  • Boolean algebra (logic) — For other uses, see Boolean algebra (disambiguation). Boolean algebra (or Boolean logic) is a logical calculus of truth values, developed by George Boole in the 1840s. It resembles the algebra of real numbers, but with the numeric operations of… …   Wikipedia

  • Boolean delay equation — As a novel type of semi discrete dynamical systems, Boolean Delay Equations (BDEs) are models with Boolean valued variables that evolve in continuous time. Since at the present time, most phenomena are too complex to be modeled by partial… …   Wikipedia

  • List of Boolean algebra topics — This is a list of topics around Boolean algebra and propositional logic. Contents 1 Articles with a wide scope and introductions 2 Boolean functions and connectives 3 Examples of Boolean algebras …   Wikipedia

  • Complete Boolean algebra — This article is about a type of mathematical structure. For complete sets of Boolean operators, see Functional completeness. In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum (least upper bound) …   Wikipedia

  • Dehaene-Changeux Model — The Dehaene Changeux Model (DCM), also known as the Global Neuronal Workspace or the Global Cognitive Workspace Model is a part of Bernard Baars s global workspace model for consciousness. It is a computer model of the neural correlates of… …   Wikipedia

  • Relational model — The relational model for database management is a database model based on first order predicate logic, first formulated and proposed in 1969 by Edgar Codd. [ Derivability, Redundancy, and Consistency of Relations Stored in Large Data Banks , E.F …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”