Boolean Algebra
Math is math and logic is logic, and ne'er the twain shall meet?
-------------------------------------------------------------------------------------
------------------------------------------------
Algebras in the Scheme of Things
Among other things, mathematicians analyze problems, build models, and solve equations. They also like to organize systems, or theories. One is what we call algebra.
So what is algebra? Specificaly, what is Boolean Algebra? (vs. ordinary algebra)
You can think of algebra as different classes of domestic pets. Then Boolean algebra, as a particular class, might be like the various breeds of dogs. So there are several varieties of Boolean algebra, just as there are different kinds of dogs.
Now let's take a look at some of the dogs ... I mean Boolean algebras!
The main idea is that elements of a set of elements are to be operated on, and there are operators to do the operating. Dogs have fleas and you have to dig them out. But that's true of every system -- all animals have fleas. So we have to be more specific about the elements and about the operators.
The main thing to understand is that the elements might be structured simply as a list. You define the class by saying what or who the members are. In school algebra, for instance, the elements are numbers. And the operators are addition, subtraction, multiplication, and division.
Similarly, the elements in Boolean algebra are symbols that might be interpreted as sets, or as ordinary statements (sentences). The operators define ways to combine the elements.
The elements and operators could be organized in different ways. One way is to list them. But listing doesn't satisfy mathematician -- it's to0 simplistic! Lists aren't very elegant, and definitely not compact. Nor do they reveal the underlying structure. It's the organization as a theory that discloses the key ideas uniting elements, and this is what the mathematician is after. This also creates problems, unfortunately, but more about that here.
To have a Boolean algebra you need two operators with certain properties, and you need special elements, like 0 or 1, that satisfy certain other properties. You also need a special member, a', for each member, a, that defines what's called the complement of the member, a. With these in your pocket, you have the makings for a proper algebra.
Example of a Boolean Algebra
I'm not making up anything new, so let me just copy what's already been well said by Robert Stoll in his neat book, Sets, Logic, and Axiomatic Theories. In the chapter on varieties of Boolean algebra he writes about one version. G. Spencer Brown has a different version, which is also worth studying. Anyway, Stoll's approach is as follows (except for a slight change in the format and a bit of color that I've added to highlight the main objects):
We shall say that
b is a Boolean algebra iff [if and only if] b is an ordered triple<B,
È, Ç >,where B is a set,
È is a binary operation (called union or join) in B, Ç is a binary operation (called intersection or meet) in B, and the following axioms are satisfied:(i) Each operation is
associative: for all a, b, c Î Ba
È (b È c) = (a È b) È c and a Ç (b Ç c) = (a Ç b) Ç c(ii) Each operation is
commutative: for all a, b Î B(a
È b) = (b È a) and (a Ç b) = (b Ç a)(iii) Each operation
distributes over the other: for all a, b, c Î Ba
È (b Ç c) = (a È b) Ç (a È c)a
Ç (b È c) = (a Ç b) È (a Ç c)(iv) There exist distinct members 0 and 1 of B such that:
(a
È 0) = a and (a Ç 1) = a, for all a Î B(v) For each element a of B and each pair 0,1 satisfying (iv), there exists an element a' of B such that:
a
È a' = 1 and a Ç a' = 0.From these axioms, the remaining formulas of the system, called theorems, are to be deduced. Deduction of the theorems is carried out by applying substitution and replacement rules to the "variables" of the axioms and of any theorems that have already been derived from the axioms. The deduction is often referred to as calculation, and so the system that provides the rules for the deductions is called a calculus. Included among the elements are the complex forms that have already been combined in accordance with the rules of deduction.
----------------------------------------------
It is instructive to contrast Boolean algebras with other math systems, such as groups. An illustration will reinforce the use of axioms. Accordingly, the following formal definition of a group is taken from B L van der Waerden's book, Modern Algebra.
A non-empty set G of any sort of elements (such as numbers) is said to be a group if the following four postulates are fulfilled:
1. A rule of combination is given which associates with every pair of elements a, b of G a third element of the same set, which most frequently is called a product of a and b and which is denoted by ab or a*b (the product may depend on the order in which the factors are arranged; ab may or may not be equal to ba.).
2. The associative law: If a, b, c are any elements of G, then
ab*c = a*bc.
3. There exists (at least) one element e of G, called the (left) identity, such that
ea = a
for every element a of G.4. If a is an element of G, there exists (at least) one element a-1 in G, called the (left) inverse of a, such that
a-1a = e
.A group is called Abelian if ab is always equal to ba (commutative law).
When the elements of the group are interpreted as numbers, and the operator, *, is taken to be multiplication, the group is a multiplicative group. In that case, e is the number 1. Note that the number 0, on the other hand, can't be a member of the group, because there is no inverse to zero. That is, 1/0 is meaningless.
---------------------------------------------
Is there anything you recognized in Algebras in the Scheme of Things? If so, I'd be surprised, because of the system formality. But most of the stuff isn't really new; the formal statements (axioms) are just expressions that characterize operations you perform almost without thinking when you add or subtract and multiply or divide numbers. Unfortunately, though, axiom 5 is an exception, and numbers don't quite seem to fit when you try to interpret it that way.
Levels of Discussion
The first thing you need to notice about dealing with math systems, generally, is that there are various levels of discussion -- levels that can be listed as follows:
.....
level 3
level 2
level 1
What often makes it difficult for non-mathematicians is that discussion of the systems tends to shift subtly from one level to another almost without notice. Each level has a specific reference, so you have to become sensitive to the changes in order to understand what's going on. To get started on the right track, then, let's make a comparison.
Suppose the system under discussion is baseball. So, at the ground level, or level 1, you have the actual game, with players running around, hitting the ball, throwing the ball, catching it, and things like that.
Now let's say the game is over and your team is in the locker room, talking about how you played -- discussing your mistakes and what you should have done and the things that were done right. This would be a level 2 discussion, and your attention would be on the level 1 actions.
Taking this one step further, suppose a training specialist is on hand and attention now shifts to how you actually talked about the good and bad parts of the way you played and how you might improve on expressing the feedback. This is a level 3 discussion, and your attention is on the elements of level 2. To emphasize the shift, you might even speak in a foreign language, like French, say, even though we don't normally do that.
The same kind of thing happens in talking about math systems. At level 1 you have the basic activity, which is the actual process of proving theorems from the axioms. This is sometimes referred to as the system arithmetic or the primary arithmetic. (See G. Spencer Brown.) At this level you are performing the defining operations of the system, whatever they might be.
At the next level, typically, and at times practically in the next breath, you're talking about the process of proving theorems from axioms. This is usually the level we refer to as algebra, and it provides a structure for organizing the statements in the basic "arithmetic." The structure has the form of special statements in the arithmetic that serve as axioms from which the remaining statements of the arithmetic are to be derived. You would have a different formal algebra if you used a different set of statements for the axioms.
Standing over the algebra, next, is the level that talks about the algebra that was set up to deal with the arithmetic. The main topics for discussion at this level are whether the axioms are consistent, complete, and independent.
Postulates are said to be consistent if they don't lead to contradictory statements. They are complete if they are sufficient to generate all of the true statements of the system. And they are independent if they can't be reduced and still generate all the statements of the system. Click
here for more detail. have to be careful to keep track of the discussion.
Significance of Consistency and Completeness
Consistency and completeness are important to us because they characterize the utility of the models we apply to the real world, such as when we devise simulations. Having models that are either inconsistent or incomplete goes against our expectation about the real world. As Casti says, we don't believe that, for example, water flows both downhill and uphill at the same time; in this respect it's consistent. (Not even quantum physicists believe water flows both ways, despite the weird quantum theory.) We also don't believe the world isn't complete, in the sense that things don't happen without a reason, which is to say that every effect has a cause.
----------------------------------------------
No interpretation is necessary to have a viable system. But systems aren't generally constructed in a vacuum -- they usually have a practical starting point. Even exceptions, like Fibonacci numbers, eventually acquire applications. We can interpret the algebra in several ways. The symbols in the system under discussion are:
One way is to think of the elements as sets. The operators would then correspond to the union and intersection of the sets. The special members 0 and 1 would then be the null set and the universal set, respectively. And the set, a', would be the complement of the set, a.
------------------------------------------