y) = xx
(x + y) = xx + (-x) = 1
x
(-x) = 0
| This is a file in the archives of the Stanford Encyclopedia of Philosophy. |
|
version |
Stanford Encyclopedia of Philosophy |
content revised
|
and a unary operation
,
and elements 0, 1 of A such that the following laws hold:
commutative and associative laws for addition and multiplication,
distributive laws both for multiplication over addition and for
addition over multiplication, and the following special laws:
x + (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
x
x + (-x) = 1
x
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.
b 
I, then also
a I.
Although not immediately obvious, this is the same as the
ring-theoretic concept. There is a dual notion of a filter (with no
counterpart in rings in general). A filter is a subset F closed under
,
having 1 as a member, and such that if
a 
b F, then also
a F. An
ultrafilter on A is a filter F with the following properties:
0 
F, and
for any
a A,
either
a F
or
-a F. For
any
a A, let
S(a)= {F : F is an ultrafilter on A and
a F}.
Then S is an isomorphism onto a BA of
subsets of the set X of all ultrafilters on A. This
establishes the basic Stone representation theorem, and clarifies the
origin of BAs as concrete algebras of sets.
Moreover, the sets S(a) can be declared to be a base
for a topology on X, and this turns X into a totally
disconnected compact Hausdorff space. This establishes a one-one
correspondence between the class of BAs and the class
of such spaces. As a consequence, used very much in the theory of
BAs, many topological theorems and concepts have
consequences for BAs. If x is an element of
a BA, we let 0x = -x and
1x = x. If (x(0), … x(m - 1)) is a finite sequence of elements of a
BA A, then every element of the subalgebra of A
generated by {x(0), … ,
x(m - 1)} can be written as a sum of monomials
e(0)x(0)
… e(m -
1)x(m - 1) for e in some set of functions
mapping m = {0, … , m - 1} into 2 = {0, 1}.
This is an algebraic expression of the disjunctive normal form
theorem of sentential logic. A function f from a set
X of generators of a BA A into a BA B can
be extended to a homomorphism if and only if
e(0)x(0)
…
e(m - 1)x(m - 1) = 0 always implies that
e(0)f(x(0))
…
e(m -
1)f(x(m - 1)) = 0. This is Sikorski's
extension criterion. Every BA A can be
embedded in a complete BA B in such a way
that every element of B is the least upper bound of a set of
elements of A. B is unique up to
A-isomorphism, and is called the completion of A. If
f is a homomorphism from a BA A
into a complete BA B, and if A is a
subalgebra of C, then f can be extended to a
homomorphism of C into B. This is Sikorski's
extension theorem. Another general algebraic notion which applies to
Boolean algebras is the notion of a free algebra. This can be
concretely constructed for BAs. Namely, the free
BA on
is
the BA of closed-open subsets of the two element discrete space
raised to the
power.
. These
BAs are useful in the study of Lindenbaum-Tarski
algebras. Every countable BA is isomorphic to an
interval algebra, and thus a countable BA can be
described by indicating an ordered set such that it is isomorphic to
the corresponding interval algebra. b} for some a in
T. a
nonzero element of X. The
-weight of A is the smallest
cardinality of a dense subset of A. the
other. The supremum of cardinalities of subset X of A consisting of
pairwise incomparable elements is the incomparability
of A.-weight of A. Every interval
algebra has countable independence. A superatomic algebra does not
even have an infinite independent subset. Every tree algebra can be
embedded in an interval algebra. A BA with only the
identity automorphism is called rigid. There exist rigid complete
BAs, also rigid interval algebras and rigid tree
algebras.
and
equivalent
provided that T 
.
The equivalence class of a sentence
is denoted by
[]. Let A be the collection of all
equivalence classes under this equivalence relation. We can make
A into a BA by the following definitions,
which are easily justified:
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 
(3) linear orders A (4) abelian groups (Q + A)
, 
are ordinals and
is a limit ordinal:
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, = the set of all functions f such that the domain of f is a subset of V(B, V(B, = the union of all V(B,
||x = ||x = ||x = y|| = ||x || = -|| || = || || x
=
| J. Donald Monk monkd@euclid.colorado.edu |