Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
When you say that a set of axioms is complete you mean to say that there is no claim which is neither provable nor disprovable from the axioms. When you say that a Boolean algebra is complete you mean that the Boolean-induced order defines a complete lattice (supremum and infimum are well-defined and exist for every set). Which one do you mean? –  Asaf Karagila Nov 16 '12 at 19:41
    
@AsafKaragila: To me he seems to mean that a particular proof system for propositional calculus is complete, which is to claim that every tautology has a proof. And the proof system he has in mind is equational rewriting using some finite set of algebraic identities such as $(A\land B)\lor C = (A\lor C)\land(B\lor C)$. –  Henning Makholm Nov 16 '12 at 19:46
    
@Henning: yes that is what I meant –  StephenJ Nov 16 '12 at 19:56
    
@Henning: I had a feeling that I was forgetting another meaning of "complete"... :-) –  Asaf Karagila Nov 16 '12 at 21:24

1 Answer 1

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.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.