2
$\begingroup$

Suppose we define Boolean algebra as the system of algebraic rules (logical equivalences) obeyed by AND, OR, NOT with AND, OR, NOT defined by the usual truth tables. We also have variables, which can represent TRUE or FALSE, and we have perentheses. Possibly when a real mathematician says "Boolean algebra" they mean something more general, but I am just a poor physicist, so please bear with me.

There are infinitely many equivalences between logical propositions. However, all of these can be generated by repeated application of finitely many "local" equivalences, such as distributivity, De Morgan's laws, etc. In Chapter 11 of "A survey of Modern Algebra" by Birkhoff and MacLane, there is an implicit proof of this by showing how one can repeatedly apply a finite list of local equivalences to transform any logic proposition into a canonical form that depends only on the truth table of the proposition.

My inclination is to say that this proves the "completeness" of the given set of axioms for Boolean algebra, but please correct me if I am inadvertently misusing technical terms. My question is: if I wanted to cite the original literature for the first proof that a set of axioms for Boolean algebra is complete (in the above sense), what would I cite? My attempts to dig this up myself by library research have so far failed, so any help is appreciated!

  • 0
    @Henning: I had a $f$eelin$g$ that I was $f$orgetting another meaning of "complete"... :-)2012-11-16

1 Answers 1

2

This question may be difficult to answer because, in the early days of the study of Boolean algebras, there may not have been a clear distinction between the syntactic notion of provability from a set of axioms and the semantic notion of truth for all values assigned to the variables. Until one sees that these are, a priori, distinct notions, one can't even imagine proving that, for a suitable choice of axioms, they coincide. My best guess is that Boole himself had a complete set of axioms for Boolean algebras but no proof (or even statement) that they are complete. On the other hand, I think that Emil Post proved the completeness of a deductive system for propositional logic in the early 1920's; that work is likely to be essentially equivalent to the completeness result that you asked about, but I don't know whether Post even mentioned Boolean algebras explicitly. Between Boole and Post (chronologically) there is the work of E. V. Huntington on axiomatization of Boolean algebras. (The reference that I found via Google is "Sets of independent postulates for the algebra of logic," Trans. Amer. Math. Soc. 5 (1904) 288-309.)