Read an Excerpt
CHAPTER 1
Boolean Rings
An element p of a ring is idempotent if p2 = p. A Boolean ring is a ring with unit in which every element is idempotent. Warning: a ring with unit is by definition a ring with a distinguished element 1 that acts as a multiplicative identity and that is distinct from the additive identity 0. The effect of the last proviso is to exclude from consideration the trivial ring consisting of 0 alone. The phrase "with unit" is sometimes omitted from the definition of a Boolean ring; in that case our present concept is called a "Boolean ring with unit."
Every Boolean ring contains 0 and 1; the simplest Boolean ring contains nothing else. Indeed, the ring of integers modulo 2 is a Boolean ring. This particular Boolean ring will be denoted throughout by the same symbol as the ordinary integer 2. The notation is not commonly used, but it is very convenient. It is in accordance with von Neumann's definition of ordinal number, with sound general principles of notational economy, and (in logical expressions such as "two-valued") with idiomatic linguistic usage.
A non-trivial and natural example of a Boolean ring is the set 2X of all functions from an arbitrary non-empty set X into 2. The elements of 2X will be called 2-valued functions on X. The distinguished elements and operations in 2X are defined pointwise. This means that 0 and 1 in 2X are the functions defined, for each x in X, by
0(x) = 0 and 1(x) = 1,
and, if p and q are 2-valued functions on X, then the functions p + q and pq are defined by
(p + q)(x) = p(x) + q(x) and (pq)(x) = p(x)q(x).
These equations make sense; their right sides refer to elements of 2. The assumption that X ≠ Ø is needed to guarantee that 0 and 1 are distinct.
For another example of a Boolean ring let A be the set of all idempotent elements in a commutative (!) ring R with unit, with addition redefined so that the new sum of p and q in A is p + q - 2pq. The distinguished elements of A are the same as those of R, and multiplication in A is just the restriction of multiplication in R. The verification that A becomes a Boolean ring this way is an amusing exercise in ring axiomatics. Commutativity is used repeatedly; it is needed, for instance, to prove that A is closed under multiplication.
The main condition in the definition of a Boolean ring (idempotence) has quite a strong influence on the structure of such rings. Two of its most surprising consequences are that (1) a Boolean ring A has characteristic 2 (that is, p + p = 0 for every p in A), and (2) a Boolean ring is commutative. For the proof, compute (p + q)2, and use idempotence to conclude that pq + qp =0. This result implies the two assertions, one after another, as follows. Put p = q and use idempotence to get (1); since (1) implies that every element is equal to its own negative, the fact that pq = -pq yields (2).
Since, as we now know, subtraction in Boolean rings is the same as addition, it is never necessary to use the minus sign for additive inverses, and we shall never again do so. A little later we shall meet another natural use for it.
Exercises
(1) Prove that every Boolean ring without a unit can be embedded into a Boolean ring with a unit. To what extent is this extension procedure unique?
(2) Can every Boolean ring with unit be obtained by adjoining a unit to a Boolean ring without a unit?
(3) A Boolean group is an (additive) abelian group in which every element has order two (that is, p + p = 0 for all p). Is every Boolean group the additive group of some Boolean ring?
§ 2. Boolean algebras
Let X be an arbitrary non-empty set and let P (X) (the power set of X) be the class of all subsets of X. There is a way of introducing a Boolean structure into P (X), as follows. The distinguished elements are defined by
0 = Ø and 1 = X,
and, if P and Q are subsets of X, then, by definition,
[MATHEMATICAL EXPRESSION OMITTED]
The symbols [union], [intersection] and ' refer, of course, to the ordinary set-theoretic concepts of union, intersection, and complement. The easiest way to verify that the result is indeed a Boolean ring is to establish a one-to-one correspondence between P (X) and 2X so that the elements and operations here defined correspond exactly to the distinguished elements and operations of 2X. The 2-valued function p corresponding to a subset P of X is just its characteristic function, that is, the function defined for each x in X by
[MATHEMATICAL EXPRESSION OMITTED]
Observe that the Boolean sum P + Q is what is usually known in set theory as the symmetric difference of P and Q.
Motivated by this set-theoretic example, we can introduce into every Boolean ring operations very much like the settheoretic ones; all we need to do is to write
(1) p ^ q = pq,
(2) p V q = p + q + pq,
(3) p' = 1 + p.
Meet, join, and complement, respectively, are among the several possible widely adopted names of these operation It should come as no surprise that plus and times can be recaptured from meet, join, and complement; indeed
(4) pq = p ^ q,
(5) p + q = (p ^ q') V (p' ^ q).
From this it follows that it must be possible to use meet, join, and complement (and, of course, 0 and 1) as the primitive terms of an axiomatization of Boolean rings, and, indeed, this can be done in many ways.
In principle the task is an easy one. All we have to do is express each of the defining conditions (axioms) of a Boolean ring in terms of meet, join, and complement, and then use the resulting conditions, or some others strong enough to imply them, as axioms. Here is a wastefully large set of conditions, more than strong enough for the purpose.
(6) 0' = 1 1' = 0
(7) p ^ 0 = 0 p V 1 = 1
(8) p ^ 1 = p p V 0 = p
(9) p ^ p' = 0 p V p' = 1
(10) p" = p
(11) p ^ p = p P V P = P
(12) (p ^ q)' = p' V q' (p V q)' = p' ^ q'
(13) p ^ q = q ^ p p v q = q V p
(14) p ^ (q ^ r) = (p ^ q) ^ r p V (q V r) = (p V q) V r
(15) p ^ (q V r) = (p ^ q) V (p ^ r) p V (q ^ r) = (p V q) ^ (p V r)
The problem of selecting small subsets of this set of conditions that are strong enough to imply them all is one of dull axiomatics. For the sake of the record: one solution of the problem is given by the pairs of conditions (8), (9), the commutative laws (13), and the distributive laws (15). To prove that these four pairs imply all the other conditions, and, in particular, to prove that they imply the De Morgan laws (12) and the associative laws (14), involves some nontrivial trickery.
The customary succinct way of summarizing the preceding discussion motivates the following definition. Let us call a Boolean algebra a set A together with two distinct distinguished elements 0 and 1, two binary operations ^ and V, and a unary operation ', satisfying the identities (6)-(15). The succinct summary says that every Boolean ring is a Boolean algebra, and vice versa. A somewhat more precise statement is somewhat clumsier. It says that if the Boolean operations (meet, join, and complement) are defined in a Boolean ring A by (1)-(3), then A becomes a Boolean algebra; and, backwards, if the ring operations are defined in a Boolean algebra A by (4) and (5), then A becomes a Boolean ring. In these notes we shall use the two terms (Boolean ring and Boolean algebra) almost as if they were synonymous, selecting on each occasion the one that seems intuitively more appropriate. Since our motivation comes from set theory, we shall speak of Boolean algebras much more often than of Boolean rings.
Here is a comment on notation, inspired by the associative laws (14). It is an elementary consequence of those laws that if p1? ..., pn are elements of a Boolean algebra, then p1 V ... V pn makes sense. The point is, of course, that since such joins are independent of how they are bracketed, it is not necessary to indicate any bracketing at all. The element p1 V ... V pn may alternatively be denoted by Vni=1pi, or, in case no confusion is possible, simply by Vi Pi.
If we make simultaneous use of both the commutative and the associative laws, we can derive a slight but useful generalization of the preceding comment. If E is a non-empty finite subset of a Boolean algebra, then the set E has a uniquely determined join, independent of any order or bracketing that may be used in writing it down. (In case E is a singleton, it is natural to identify that join with the unique element in E.) We shall denote the join of E by V E.
Both the preceding comments apply to meets as well as to joins. The corresponding symbols are, of course, Λni=1pi, or Λi pi, and Λ E.
The point of view of Boolean algebras makes it possible to give a simple and natural description of an example that would be quite awkward to treat from the point of view of Boolean rings. Let m be an integer greater than 1, and let A be the set of all positive integral divisors of m. Define the Boolean structure of A by the equations
[MATHEMATICAL EXPRESSION OMITTED]
It turns out that, with the distinguished elements and operations so defined, A forms a Boolean algebra if and only if m is square-free (that is, m is not divisible by the square of any prime). Query: what are the number-theoretic expressions of the ring operations in this Boolean algebra? And, while we are on the subject, what are the expressions for the Boolean operations in the Boolean ring A consisting of the idempotent elements of an arbitrary commutative ring R with unit? (See §1.) The answer to this question is slightly different from (l)-(3); those equations give the answer in terms of the ring operations in A, and what is wanted is an answer in terms of the ring operations in R.
A technical reason for preferring the language of Boolean algebras to that of Boolean rings is the so-called principle of duality. The principle consists in observing that if 0 and 1 are interchanged in the identities (6)-(15), and if, at the same time, Λ and V are interchanged, then those identities are merely permuted among themselves. It follows that the same is true for all the consequences of those identities. The general theorems about Boolean algebras, and, for that matter, their proofs also, come in dual pairs. A practical consequence of this principle, often exploited in what follows, is that in the theory of Boolean algebras it is sufficient to state and to prove only half the theorems; the other half come gratis from the principle of duality.
A slight misunderstanding can arise about the meaning of duality, and often does. It is well worth while to clear it up once and for all, especially since the clarification is quite amusing in its own right. If an experienced Boolean algebraist is asked for the dual of a Boolean polynomial, such as say p V q, his answer might be p Λ q one day and p'Λ q' another day; the answer p' V q' is less likely but not impossible. (The definition of Boolean polynomials is the same as that of ordinary polynomials, except that the admissible operations are not addition and multiplication but meet, join, and complement.) What is needed here is some careful terminological distinction. Let us restrict attention to the completely typical case of a polynomial f(p, q) in two variables. The complement of f(p, q) is by definition (f(p, q))', abbreviated f'(p, q); the dual of f(p, q) is f'(p', q'); the contradual of f(p, q) is f(p', q'). What goes on here is that the group acting, in an obvious way, is not the group of order two, but the Klein four-group. This comment was made by Gottschalk (J.S.L., vol. 18) who describes the situation by speaking of the principle of quaternality.
A word of warning: the word "duality" is frequently used in contexts startlingly different from each other and from the one we met above. This is true even within the theory of Boolean algebras, where, for instance, a topological duality theory turns out to play a much more important role than the elementary algebraic one. If the context alone is not sufficient to indicate the intended meaning, great care must be exercised to avoid confusion.
Exercises
(1) The four pairs of identities (8), (9), (13), and (15) constitute a set of axioms for Boolean algebras; are they an independent set?
(2) Prove that the following identities constitute a set of axioms for Boolean algebras: V is commutative and associative, and (p' V q')' V (p' V q)' = p
(3) Prove that the following identities constitute a set of axioms for Boolean algebras: p" = p, p V (q V q') = p, and p V (q V r)' = ((q' V p)' V (r' V p)')'.
(4) Prove that the commutative and associative laws for V, together with the requirement that (for all p, q, and r) p V q' = r V r' if and only if p V q = p, constitute a set of axioms for Boolean algebras.
§3. Fields of sets
To form P (X) is not the only natural way to make a Boolean algebra out of a non-empty set X. A more general way is to consider an arbitrary non-empty subclass A of P (X) such that if P and Q are in A, then P [intersection] Q, P [union] Q, and P' are also in A. Since A contains at least one element, it follows that A contains Ø and X (cf. (2.9)), and hence that A is a Boolean algebra. Every Boolean algebra obtained in this way is called a field (of sets). There is usually no danger in denoting a field of sets by the same symbol as the class of sets that go to make it up. This does not, however, justify the conclusion (it is false) that settheoretic intersection, union, and complement are the only possible operations that convert a class of sets into a Boolean algebra.
A subset P of a set X is cofinite (in X) if its complement P' is finite. The class A of all those subsets of a nonempty set X that are either finite or cofinite is a field of subsets of X. If X itself is finite, then A is simply P (X); if X is infinite, then A is a new example of a Boolean algebra.
The preceding construction can be generalized. Call a subset P of X cocountable (in X) if its complement X' is countable. The class of all those subsets of X that are either countable or cocountable is a field of subsets of X. Different description of the same field: the class of all those subsets P of X for which the cardinal number of either P of P' is less than or equal to NO. A further generalization is obtained by using an arbitrary cardinal number in place of NO.
(Continues…)
Excerpted from "Lectures On Boolean Algebras"
by .
Copyright © 2018 Paul R. Halmos.
Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
