This is a file in the archives of the Stanford Encyclopedia of Philosophy. |
how to cite |
Stanford Encyclopedia of Philosophy |
content revised
|
x + (x y) = xThese laws are better understood in terms of the basic example of a BA, consisting of a collection A of subsets of a set X closed under the operations of union, intersection, complementation with respect to X, with members and X. One can easily derive many elementary laws from these axioms, keeping in mind this example for motivation. Any BA has a natural partial order defined upon it by saying that x y if and only if x + y = y. This corresponds in our main example to . Of special importance is the two-element BA, formed by taking the set X to have just one element. An important elementary result is that an equation holds in all BAs if and only if it holds in the two-element BA. Next, we define x y = (x - y) + (y - x). Then A together with and , along with 0 and 1, forms a ring with identity in which every element is idempotent. Conversely, given such a ring, with addition and multiplication, define x + y = x y (x y) and - x = 1 x. This makes the ring into a BA. These two processes are inverses of one another, and show that the theory of Boolean algebras and of rings with identity in which every element is idempotent are definitionally equivalent. This puts the theory of BAs into a standard object of research in algebra. An atom in a BA is a nonzero element a such that there is no element b with 0 < b < a. A BA is atomic if every nonzero element of the BA is above an atom. Finite BAs are atomic, but so are many infinite BAs. Under the partial order above, x + y is the least upper bound of x and y, and x y is the greatest lower bound of x and y. We can generalize this: X is the least upper bound of a set X of elements, and X is the greatest lower bound of a set X of elements. These do not exist for all sets in all Boolean algebras; if they do always exist, the Boolean algebra is said to be complete.
x (x + y) = x
x + (-x) = 1
x (-x) = 0
Every BA is isomorphic to a Lindenbaum-Tarski algebra. However, one of the most important uses of these classical Lindenbaum-Tarski algebras is to describe them for important theories (usually decidable theories). For countable languages this can be done by describing their isomorphic interval algebras. Generally this gives a thorough knowledge of the theory. Some examples are:
[] + [] = [ ] [] [] = [ ] -[] = [ ] 0 = [F] 1 = [T]
Theory Isomorphic to interval algebra on (1) essentially undecidable theory Q, the rationals (2) BAs , square of the positive integers, ordered lexicographically (3) linear orders A Q ordered antilexicographically, where A is to the power in its usual order (4) abelian groups (Q + A) Q
The B-valued universe is the proper class V(B) which is the union of all of these Vs. Next, one defines by a rather complicated transfinite recursion over well-founded sets the value of a set-theoretic formula with elements of the Boolean valued universe assigned to its free variables
V(B, 0) = V(B, + 1) = the set of all functions f such that the domain of f is a subset of V(B, ) and the range of f is a subset of B V(B, ) = the union of all V(B, ) for < .
||x y|| = {(||x =t|| y(t)) : t domain(y)} ||x y|| = {-x(t) + ||t y|| : t domain(x)} ||x = y|| = ||x y|| ||y x|| || || = -|| || || || = || || + || || || x (x)|| = {|| (a)|| : a V(B)}
First published: July 5, 2002
Content last modified: July 5, 2002