Talk:Boolean algebra

This is the talk page for Boolean algebra. If you came here following links from archived discussions, you may be looking for talk:Boolean algebra (structure).

About the completeness section

Hi Vaughan, could you explain your revert of my edit please? There are terminology problems (*) I'm aware about in my edit that I intended to fix. I agree that I should not have left unfixed this problem of terminology for more than a day long as I did but the rest seems not only correct to me but clearer and more informative than what was written before (up to the English maybe but I tried to reuse as much as possible existing text so that to minimize the risk of improper English turns of phrase). Note also that my edit is a consequence of the long confrontation of views we had on this talk page, so I'm waiting for explanations from you.

(*) This is about the use of expressions "syntactic completeness" and "semantic completeness". For the first one (the use of which actually derives from a discussion with Lambiam and you), I could not find an attested source of it in the sense I used it and I intended to renounce using this term (or using instead an informal terminology like "complete in a syntactic sense", or "complete in a deductive sense"). For the second one, it is not also semantic completeness in the usual sense since it is not about all models but only about a particular one and I was going to add parentheses around this term to emphasize it was not the usual sense (or again using something like "complete in a semantic sense"). [Added 20:42, 2 April 2011 (UTC): another possible source of confusion in my edit is the use of the term "equation" to mean "equation closed over the variables". In accordance with the terminology used in the article, using the term "law" would have been a better choice.]

--Hugo Herbelin (talk) 14:00, 2 April 2011 (UTC)

Hi Hugo. "Complete" in mathematics is used indiscriminately with many meanings. The section in question is about completeness of an axiomatization A of a theory T. This can be defined either as T ⊆ A⊢ (every theorem t of T is a syntactic consequence of A, meaning A⊢t, that is, t follows logically from A) or T ⊆ A⊧ (every theorem t of T is a semantic consequence of A, meaning A⊧t, t holds in every model of A, or equivalently that every model of A is a model of T). This notion of completeness of axiomatizations is independent of the logical framework, whether first order logic, various modal logics, universal Horn logic, equational logic, etc.

The point of this section is to announce that, having listed various logical laws, logical in the sense that they hold of, or are sound for, two-valued logic, we can now stop and say that they completely determine both what it is to be a Boolean law, namely any equational consequence of the listed laws, and what it is to be a Boolean algebra, namely any model of the listed laws. The section makes the further point that the Boolean laws when defined as the consequences of the listed laws coincide with the tautologies.

Your edit tacitly takes for granted that the axiomatization of the theory is now complete, and goes on to point out a property not of axiomatizations but of theories, namely the property of having no proper consistent extension. (In equational logic an inconsistent theory is one axiomatizable by x = y, equivalently one whose models have at most one element.)

(Incidentally such theories are not so rare. In general they arise as the coatoms in the lattice of extensions of any equational theory, equivalently the atoms of the lattice of subvarieties of the corresponding variety. Group theory for example has infinitely many such: to each prime p corresponds the theory of the cyclic group of that order, which is maximal or complete in this sense.)

It is always tempting to call a maximal something "complete," but since "axiomatization" and "theory" are so near each other conceptually, and since "complete" has a very standard meaning for the former, it may be preferable to use some other term than "complete" for this notion of a maximal theory. But even if one does overload the word in that way, that property of the theory of Boolean algebras is not the point of this section, which is about axiomatizations thereof, namely that we now have enough axioms.

Confusion has resulted from how I worded the section, constituting prima facie evidence that the wording is unclear. The goals I had in mind for that section were as follows.

1. State that we have now listed enough laws to constitute a definition of the subject, in two senses of "enough:" they define all remaining Boolean laws as their equational consequences, the theory, and they define what it is to be a Boolean algebra, the class.
2. Point out that the theory so defined coincides with the 0-1 tautologies, giving one sense in which our stopping point was not entirely arbitrary. (We could for example have stopped after completely axiomatizing Heyting algebras, assuming ¬ was replaced by →, which would omit excluded middle etc., in which case a different justification of that stopping point would be in order.)

With an incomplete list the theory would have been too small and the class too large.

To fix the confusion, one should first decide what the section should say, and then how it can be most clearly said. The further point that the theory happens to be maximal in the sense of admitting no proper consistent extension, like the theory of the group Z_p, could be added to this section, but to my thinking it would fit more naturally in a section devoted to properties of the theory in general. --Vaughan Pratt (talk) 22:16, 2 April 2011 (UTC)

Thanks for your answer. How can we proceed now?

Wording the section differently would indeed be appropriate. In particular the use of the word "incomplete" in "... set of laws would be incomplete in this sense ..." has nothing to do with any of the two definitions of completeness that you give above, since what it is about is just defining what a model of the axiomatization is (is that correct?).

Then, considering that soundness of equational reasoning is a standard and somehow trivial result of universal algebra, I can propose to rephrase the sentence "In the semantics sense, ... algebras" into "A Boolean algebra is any set with operations ∧, ∨, and ¬ that satisfies these laws or, equivalently, that satisfies the logical consequences of these laws." (However, since the subject is about Boolean algebra and not about universal algebra, I'm not fully sure that it is worth to point out explicitly this subtle difference between validating the axioms and validating the consequences of the axioms. What do you think?).

Then, we have to deal with three kinds of completeness:

1. The standard result of semantic completeness for equational theories
2. That adding new independent axioms make the theory inconsistent
3. The specific result of completeness wrt the two-element domain

In my opinion, the 2nd one and the 3rd one are the interesting ones for the article and are worth to be presented together. The 1st one is a standard result of equational theory, so I'm unsure it is worth to be presented, but I don't care to have it mentioned, even more that the 2nd result is, if I'm correct, a direct consequence of the 1st one (since the 1st one means in practice completeness wrt the term model), while the 3rd one needs the extra step of building a homomorphism from the term model to the two-element algebra (i.e. an ultrafilter, if I understood things correctly). Otherwise said, the 2nd result is more primitive to Boolean algebra than the 3rd one.

(Note that there is a 4th interesting completeness result, as discussed in Talk:Boolean algebra#Possible compromise, namely the completeness wrt to any Boolean algebra, but since the article is restricted to Boolean algebra over the two-element domain, it is irrelevant at this time.)

Then, how can we proceed? Do you agree that the 2nd result is more primitive to Boolean algebra than the 3rd one and that it is worth to be presented at least at the same level?

Next, do you want to edit the article yourself so that the 2nd kind of completeness result is mentioned (whatever the name is given to it) or do you want me to propose some new text?

(By the way, thanks for the Z_p example of a "non-consistently-quotientable" theory.) --Hugo Herbelin (talk) 22:24, 3 April 2011 (UTC)

Ok, I took a crack at clarifying things. Let me know how it reads now. I included your point about no proper consistent extension, but I think it's a bit out of place there and both it and the reasoning behind it might make more sense if deferred to where the notion of substitution instance and the meaning of "reduce" had been defined in the context of the equational reasoning that goes into the logical side of Boolean algebra. --Vaughan Pratt (talk) 00:27, 4 April 2011 (UTC)

Hi Vaughan, the new paragraph is maybe a bit better than before but, in my opinion, there are still some unclear points.

First, what the definition of "Boolean algebra" is is difficult to follow. At the beginning of Section "laws", it is said "Boolean algebra [is] any model of the Boolean laws" (where "Boolean laws" has been defined in the lede as "those equations that hold for all values of their variables"). In Section completeness, it is said "Boolean algebra can now be defined as any model of these axioms". I guess you mean "As a consequence, Boolean algebras can equivalently be defined as any model of these axioms". Indeed, the current wording is somehow confusing when put into correspondence with the sentence "Had we stopped listing laws too soon (...) there would have been models of the listed laws that were not Boolean algebras" since, when the two sentences are read together, one gets the feeling of a contradiction (i.e. if one admits that a B.a. is by definition a model of the axioms, then a B.a. has to remain a model of the axioms, whatever the axioms are). I would suggest to either suppress the "and moreover, there would have ..." sentence, or, to remind in the completeness section the initial definition of B.a. given at the beginning of Section laws.

Note by the way that the definition of Boolean algebras used in the article (i.e. the one at the beginning of Section "laws") does not match the one in Boolean algebra (structure). Maybe a way to address this mismatch is to remove the definition of Boolean algebras at the beginning of laws and to keep a definition only in the "Completeness" Section, saying, after the statement of logical completeness, that B.a., which are defined as models of the Boolean laws, can then equivalently be defined as models of the axioms (so that both definitions can at once be seen as equivalent).

About the last paragraph: I find your formulation a bit weak but I somehow agree that when Boolean algebra is defined from the two-valued semantics, as the article does, the maximality principle is not as striking as it would be if Boolean algebra had primarily been defined as an algebraic characterization of logical reasoning. Of course, I'm influenced by my background in proof theory, but let me digress a bit. Why after all wouldn't the "maximality property" be the primary property of classical logic, especially when compared to intuitionistic logic. I mean that, from a proof-theoretic point of view, there is not so much difference between intuitionistic and classical logic. After all, you can just reason through the Gödel–Gentzen negative translation and intuitionistic logic gets the same expressivity as classical logic. Similarly, if one reasons in the ¬-∧ fragment of propositional logic, there is no difference between reasoning intuitionistically or classically. So, why would we need a Boolean semantics after all, since we can reason classically-like in Heyting algebras too? From this point of view, what makes classical logic different from intuitionistic logic is not the extra power brought by excluded-middle (since it is enough to reason in a framework without ∨), but something that has to be found elsewhere. This is the observation that lets me wonder whether the main property of classical logic would not be after all that it arrives as the maximal completion of intuitionistic logic which in turn is the "real" logic acting behind the scene. Anyway, I will not fight against having the maximality property in another section, even if I think it has some explanatory value wrt why we "stop" exactly here in axiomatizing (classical) propositional calculus.

A minor point: I would not refer to a section by its number, if ever an editor adds or remove a section, this is liable to break the ordering without the editor being aware that something has been broken.

More generally, it seems to me that you're making a big deal of tackling Boolean algebra from a foundational perspective reconstructing carefully the syntax from the semantic. Somehow, I agree that this important but I still have doubts on whether this is the most relevant approach for Wikipedia. At the end, isn't the main property of Boolean algebra that there exists an equational system that exactly captures the valid laws of the basic operations over {0,1} and of the basic operations over sets? Is this that the reader will retain of the current article?

I'm afraid that, even if a big progress was made recently in having one single entry point to "Boolean algebra", the questions raised in On merging Boolean algebra (introduction) and Boolean logic and Proposal for the organization of a collection of BA-related articles about getting a consensus on the scope of this main entry point to the subject are still there. I'm getting a bit desperate.

By the way, I have a side question: was the original calculus by Boole about 0 and 1 or about an algebra of classes? --Hugo Herbelin (talk) 21:05, 4 April 2011 (UTC)

As far as reconciling the body with the lead, Tijfno098 seems to have taken over the latter so any concern that the lead is failing to summarize the body accurately needs to be taken up with him.

The question of where "Boolean algebra" should be officially defined as a model of the laws is a good one. Current candidates seem to be the beginning of the Laws section, the completeness section, and the section on Boolean algebras. The third seems the logical choice to me, in which case the two earlier ones should be clarified somehow as merely foreshadowing the official definition. Suggestions solicited.

Boolean algebra (structure) needs to be completely reworked in order to integrate with Boolean algebra as well as to absorb the structural facts from Boolean algebras canonically defined which go way beyond anything currently in Boolean algebra (structure). How it currently defines Boolean algebras is therefore completely irrelevant.

Point about section number noted. To be fixed.

Regarding syntax vs. semantics, see the article Algebra. Would you say it is about syntax or semantics? Whatever is making you "desperate" about Boolean algebra should make you equally desperate about Algebra.

Since Boole never did come up with a definitive system, it's hard to say exactly what he had in mind. However his 1854 book made it pretty clear that he could see a link between the Algebra of sets and that the only solutions in x to x² = x were 0 and 1. What he never did manage to see was that his interpretation of + made complete sense as addition mod 2. So I would say that Boole's understanding of his calculus was equally about 0 and 1 and an algebra of classes, but that he failed to see the connection with arithmetic mod 2. --Vaughan Pratt (talk) 06:48, 5 April 2011 (UTC)

For me, elementary algebra is definitively about syntax (even if the "user" has a model in mind). For the rest, I only have a distant view of what they cover. At first view, abstract algebra is about the properties of models, which somehow includes elaborating a syntax for classifying models. Universal algebra is mainly about the properties of congruences, then somehow about the syntax of congruences (as emphasized by the HSP combinators) with the quotients of the term model playing a central role. Category theory is somehow also about the syntax of models (taking composition, pairs, limits, ... as the syntactic operations). What is your own view?

I was not getting desperate about Boolean algebra. I was getting desperate about the possibility of eventually arriving to a Boolean algebra article that I could find at least as good as the algebra article for instance is about to be. But see new section.

PS: I appreciated your last edits to the article. --Hugo Herbelin (talk) 23:38, 5 April 2011 (UTC)

Glad you liked my edits, Hugo. :) On the question of elementary anything, elementary algebra is certainly a widely recognized concept. While it would be a little creative of Wikipedia to offer elementary Boolean algebra as its own topic (currently it just redirects to Boolean algebra), I don't see any harm in that, and it could be synonymous with Boolean logic as the purely syntactic side. Furthermore abstract algebra is aligned with Boolean algebra (structure) (which might read more smoothly as "Boolean algebraic structure" or better yet just "Boolean algebras" plural, which Wikipedia allows in such circumstances). Boolean algebra is aligned with Algebra, which covers both equally.

"Universal Algebra and Category Theory," UACT, is the title of a conference held in 1993 at MSRI Berkeley co-organized by UA's Ralph McKenzie and CT's Saunders Mac Lane. It was fascinating to see how ideologically far apart the two groups were, despite having abstraction as a potentially unifying common framework. (My talk there was on Chu spaces as a structure with the potential of bridging that gap.) The UA crowd took the binary relation of set membership as their foundation, mathematics' assembly language, very easy to pick up and use for simple things. The CT crowd took the binary operation of function composition as theirs, mathematics' functional programming, which takes a bit of getting used to at first. I've spent countless hours over the past 48 years programming in both paradigms, and my own experience has been that basing mathematics on sets is like building houses with bricks while basing it on functions is more like tilting up prefab walls, with the caveat that you shouldn't attempt the latter if you don't know what you're doing. Anyone can place one brick on another, which is why brick houses continue to be popular today. --Vaughan Pratt (talk) 05:16, 6 April 2011 (UTC)

Hello all, I find this article is generally written very well, but despite reading over and over again, the following makes no sense to me: "Boolean algebra has the interesting property that x = y can be proved from any non-tautology. This is because the substitution instance of any non-tautology obtained by instantiating its variables with constants 0 or 1 so as to witness its non-tautologyhood reduces by equational reasoning to 0 = 1. It follows that x = x∧1 = x∧0 = 0 = 1 = y∨1 = y∨0 = y." Can it be reworded or explained in more detail so that it makes sense to a casual reader like myself? I don't think if offers enough explanation, whereas the rest of the article seems to make perfect sense. 82.12.162.43 (talk) 01:37, 20 July 2011 (UTC)

"Prototypical" Boolean algebra

Is there any evidence that this is standard terminology? --Trovatore (talk) 18:48, 5 April 2011 (UTC)

A quick search on the web gives:

• "In previous section we went through concepts of binary vectors and sets as prototypical Boolean algebra models" [1]
• "The power set typeset structure of a set typeset structure endowed with the operations of union, intersection and complement is the prototypical example of a Boolean algebra" [2]

So, the answer seems to be no. --Hugo Herbelin (talk) 23:40, 5 April 2011 (UTC)

Vaughan will point out that those are just powers of the two-element one, which is of course true. But that's not my point exactly. In a textbook it would be fine to say we call this the prototypical Boolean algebra; in an encyclopedia article it strikes me as perhaps overly expository, and in addition a bit POV. --Trovatore (talk) 07:21, 6 April 2011 (UTC)

Well, maybe we could dispense with calling it anything. On the other hand it is the initial Boolean algebra, meaning the algebra of constant expressions. Since all expressions in 0 and 1 evaluate to 0 or 1, up to equivalence those are the only constant expressions (as distinct from ¬x which contains a variable). In contrast the initial ring is the integers since every integer can be expressed as a constant expression in 0 and 1, for example 0 - 1 - 1 = -2, 1+1+1 = 3, etc.

Another important property is that it is the unique subdirectly irreducible Boolean algebra, whence the laws of Boolean algebra are those of this algebra. In contrast the ring of integers, while initial, is not subdirectly irreducible, and furthermore the theory of the integers includes xy = yx which is not a theorem of ring theory, only of commutative ring theory. But of course "subdirectly irreducible" is too long a name while its usual contraction to SI is too cryptic. --Vaughan Pratt (talk) 23:55, 6 April 2011 (UTC)

Dispensing with calling it anything sounds like a good plan. I don't have time at the moment to follow up on the SI stuff; I'm quite willing to believe that it expresses an important property that should be mentioned somewhere, but maybe not at just that point of the text. --Trovatore (talk) 07:05, 7 April 2011 (UTC)

How far can we improve the article (and the topic)?

Now that a big step has been taken with having a main entry point to Boolean algebra, I would like to discuss in more details the layout of the Boolean algebra article and in particular, to defend the opinion that the Boolean algebra main article is at the head of sufficiently many different related subtopics to justify adopting the level of details of a summary article. In this direction, and contrary to what has been discussed up to now, I would recommend to keep the Boolean algebra (logic) article and to consider it as the main article about Boolean algebra over two elements, with the double objective of targetting the audience expecting such an article (as was suggested here and there in previous discussions) and of leaving room for a summary-style main Boolean algebra article. Adopting such a summary style for the main article is in my opinion the best way to progressively organize the topic into a consistent, redundancy-free, easily extensible, eventually-featured set of articles. Moreover, the large topic coverage provided by the current article is already an evidence that it aims at being a hat article for the topic, i.e. a summary article, what justifies to make the move. Then, taking into account the previous discussions and the current existing contents, my proposal for such a summary-style main article is the following:

• Hatnotes: to the mathematical objects Boolean algebra (structure) and to the two-valued Boolean algebra (Boolean algebra (logic) renamed into Boolean algebra (two-valued))
• Lede: definitively present Boolean algebra not only as "elementary algebra" (more or less as in [3]) but also and more generally as "algebra of two-valued propositional logic and field of sets" (e.g. as in [4] or [5], chapter 1)
• Section 1 History and motivations: Algebraization of logic, Boole, algebra of classes, mention and link to Boolean ring, Jevons, Schröder, Huntington, application to switching circuits, Shannon, switching algebras, similarities and differences with elementary algebra, the different notations, first-order logic out of the subject (or need for complete algebras?), ....
• Section 2 Laws: The standard basis, a list of axioms (monotone, nonmonotone), main completeness result with link to Boolean algebra (two-valued); pointing out finiteness of the axiomatization; short enumeration of the derived consequences such as De Morgan's laws (if not already in the list); definition of the underlying order; the duality principle, self-duality of negation; short sentence on the existence of other possible bases and axiomatization with link to a new specific subarticle on alternative axiomatizations.
• Section 3 Generalization and related topics: Short sentence for defining Boolean algebras as a model of semantic laws, or equivalently as a complemented distributive lattice with link to the main article and link to a (new) article on Examples of Boolean algebras; representation theorem with link to Stone's representation theorem for Boolean algebras. Short sentences to introduce and link to multi-valued logic, fuzzy logic, probabilistic logic; short sentence to introduce the "weaker" Heyting algebra, De Morgan algebra, emphasis of the maximality of Boolean algebra axioms.
• Section 4 Applications: Short sentences recalling the application to propositional logic, two-valued logic, providing links to digital logic, relational algebra, legal information retrieval, solid modeling, raster graphics, operator (programming), bitwise operation, ...

In particular, I propose to merge the following contents to specific relevant articles, what will be an opportunity to improve these other articles (not forgetting to put cross-references whenever it is relevant):

• Truth tables merged to Truth tables, Venn diagrams to Venn diagram, digital logic gates to logic gates
• All detailed examples of Boolean algebras merged with the examples of Boolean algebras canonically defined to a new subarticle Examples of Boolean algebras
• Section on Propositional logic merged to the various relevant corresponding articles about propositional logic
• Detailed paragraphs of Section Applications merged to relevant articles:

• Paragraph on machine code merged to operator (programming) or bitwise operation
• Paragraph on natural languages merged, maybe with First-order_logic#Formalizing_natural_languages, or to a new page.
• Paragraph on law moved to some article on law?
• Paragraph on raster graphics merged to raster graphics
• Paragraph on solid modeling merged to solid modeling
• Paragraph on boolean search maybe merged to Relational database or to Relational algebra

Of course, this is just a proposal but I really insist on the advantages of going towards a shorter and fully-webbed article. Merging the detailed content to specific articles will be an opportunity to enrich and improve the articles to which the contents will be merged and to reduce the redundancies in Wikipedia. Fully using the hypertext structure will also provide the ability to query the topic at different levels of detail, directly allowing the reader to focus on the parts he's interested in. I believe that everyone has to gain from such a move: Wikipedia as a whole, the readers, and the Boolean algebra task force itself, via the recognition it will get. --Hugo Herbelin (talk) 00:51, 6 April 2011 (UTC)

Hugo, you do realize that you're bucking the trend exemplified by the Algebra article, right?

You're proposing that "Boolean algebra" means "elementary Boolean algebra." Algebra is a big subject, with elementary algebra and algebraic structures as fundamental subtopics. The Boolean counterpart of these distinctions is arguably Boolean algebra, elementary Boolean algebra, and Boolean algebraic structures respectively.

What exactly is it about Boolean algebra that makes you feel it is different from algebra in general? Is it because algebra is studied by people with an average IQ of 110 because they're mathematically oriented while Boolean algebra is for those with an average IQ of 90 because they're just programmers or people with soldering irons who solder NAND gates together? Or is there something else to the difference? --Vaughan Pratt (talk) 05:49, 6 April 2011 (UTC)

Regarding your claim above, "not only as 'elementary algebra' (more or less as in [6])", allow me to quote from that Britannica article: "In a Boolean algebra a set of elements is closed under two commutative binary operations that can be described by any of various systems of postulates, all of which can be deduced from the basic postulates that an identity element exist for each operation, that each operation is distributive over the other, and that for every element in the set there is another element that combines with the first under either of the operations to yield the identity element of the other." Would you say this quote from Britannica supports or refutes your point of view? — Preceding unsigned comment added by Vaughan Pratt (talk) 06:16, April 6, 2011 (UTC)

(Not speaking for Hugo) it neither supports nor refutes it, because it's talking about a Boolean algebra, not about Boolean algebra. --Trovatore (talk) 07:10, 6 April 2011 (UTC)

Glad you picked up on that from the second paragraph of the Britannica article, Trovatore. Now here's the first paragraph of the same article. What would you say it's talking about? "Boolean algebra: a symbolic system of mathematical logic that represents relationships between entities -- either ideas or objects. The basic rules of this system were formulated in 1847 by George Boole of England and were subsequently refined by other mathematicians and applied to set theory. Today, Boolean algebra is of significance to the theory of probability, geometry of sets, and information theory. Furthermore, it constitutes the basis for the design of circuits used in electronic digital computers." --Vaughan Pratt (talk) 08:15, 6 April 2011 (UTC)

In the first para, it's talking about Boolean algebra. In the second, it's talking about a Boolean algebra. It would have been better if the transition had been better delineated, but it is what it is. --Trovatore (talk) 08:53, 6 April 2011 (UTC)

I think Vaughan misunderstood my sentence. I'm perfectly fine in taking "Boolean algebra" in the sense of a subject covering both elementary and abstract algebra (more precisely, I'm ok in taking it in any sense that would be the most generally accepted one). This is anyway not the point of my message and the reference to Britannica could be removed w/o changing my point. The point of my message is about advocating a summary-style model for the Boolean algebra article. This is here that I'm waiting for opinions from Vaughan and from the community of people concerned by these pages. --Hugo Herbelin (talk) 09:08, 6 April 2011 (UTC)

┌────────────────────────────────────────────────────────────────────────────────────────────────────┘Sorry, I was overreacting to some of the details of your proposed moves. I believe we're all pretty much in agreement that Boolean algebra should summarize the subject, expanding on the various subtopics with separate articles on each. The subject is certainly far too big to fit it all into Boolean algebra.

Obviously there's room for debate as to what should go in the summary. It seems to me that something informative needs to be said about each of the following, i.e. the article should not simply degenerate into a collection of links on the subtopics.

• Values (0-1, sets)
• Operations (and-or-not as basic, xor, implies as others)
• Laws (enough to illustrate concepts like completeness)
• Diagrams (Venn, digital logic schematics)
• Boolean algebras (definition, examples)
• Representation by fields of sets (algebra of sets)
• Relevance to propositional logic (algebra of truth values)

Some of the existing material on these topics can be shortened. (Though I do think there should be at least one example of a Boolean algebra that is not isomorphic to a power set. The top two candidates for that, both countable, would be finite and cofinite sets, which is atomic, and the Boolean operations, aka the free Boolean algebra on N, which is atomless because every operation can be conjoined with a new variable to produce something that is smaller but still nonzero. Boolean algebra (structure) can then pick it up from there and get into the meat of the subject. The latter algebra btw is interesting in its own right as the unique countable atomless Boolean algebra, closely resembling how the rationals form the unique unbounded countable dense linear order. It is conceivable that this resemblance was what got Stone thinking along topological lines about Stone duality.)

I'm not sure how urgent it is to give the uses in search queries and natural language; I'd be happy to move most of that out.

I would not object to speeding up the slower parts of the article provided we can point people to more introductory accounts of them. The current article reflects my response to criticism by StuRat that I was writing for Ph.D. mathematicians while he was writing for computer scientists. In particular the idea of operations that are like numerical operations but differ in some details (for example idempotence of conjunction which is false for multiplication as its numeric counterpart) seemed worth introducing slowly, but perhaps that need is better met by a separate slower-paced introductory article on the operations. Also dumping the abstract concept of a Boolean algebra on readers who've had no exposure to group theory or vector spaces seemed a bit fast, which is why I discussed the concrete examples (fields of sets) first and then drew the distinction between concrete and abstract in terms of the laws being provable for the concrete cases but imposed by fiat for the abstract definition of an arbitrary Boolean algebra. But again, perhaps that slow pedagogical approach is better suited to an introductory article for people with below-average background (if there is such a thing). I can see arguments either way, and don't want to argue strongly myself for any particular speed. The only things I do want to see kept in the article are some of the basic facts about each of the topics on my list above, enough to give the flavor of each topic and make it interesting without necessarily carrying on at length.

So treat Hugo's suggestions as being proactive, what to move, and mine as reactive, what to retain in Boolean algebra, and see if there are any unresolvable conflicts. --Vaughan Pratt (talk) 19:53, 6 April 2011 (UTC)

I'm glad to read that you are pretty much in agreement on seeing the Boolean algebra page a summary of the subject. I'm afraid we might however disagree 1) on the style which I think could be made more concise and less textbook (but maybe the best thing here is that I be bold and see then if an agreement can eventually be reached) 2) on which details to put in the summary and which other details to put in specialized articles.

I agree that the article must be made of fluent text and not just be a flat collection of links. My idea is that the history, motivations and laws section must be rather well detailed, but I'm unsure that the Boolean algebra needs more than a few paragraphs, whose role will be, not to explain the subtleties of Boolean algebras, but to summarize what is in Boolean algebra (structure).

As for the organization of the article, I finally think that the comparison with ordinary algebra is important but that it should not be mixed with the description of the laws, because it is not interesting for all readers. There are certainly readers that just want to read or check something in the laws section without having to be disturbed by slow-pace comparisons with ordinary algebra. So my recommendation is to have a proper subsection of the laws section dedicated to this comparison.

For examples of algebras as detailed as they currently are, I think they have to go to the structure page for the most striking ones (and the free algebra is accordingly of this kind) and to a specific page for the others (because there is a sufficiently large number of examples available to justify a page in the style of List of groups). In the main article, I think that only a reference to the free algebra should be given, without details on how it is built and how it looks like.

I don't think that "dumping the abstract concept of a Boolean algebra on readers who've had no exposure to group theory or vector spaces" is a bit fast. First, as said above, I think that readers wanted to know more about the algebras have to go to the structure page. Then, even on the structure page, I don't think that we have to target any kind of reader a priori (not a textbook). Moreover, the basic of Boolean algebras is somehow simple and can be understood without knowing anything in group theory and vector spaces. So I think the concepts have to be kept apart. Links to group theory and vector spaces will naturally appear as a consequence of connecting the study of the algebras to abstract algebra. We have no reason to make presuppositions on the knowledge of the readers. The readers can be any kind of readers.

Somehow, my feeling about StuRat is that what he had expected was precisely some kind of summary that you can read without having to understand the details. Then facing the introduction of details in what the first version of "Boolean logic" became, he saw these details as PhD-level content intrusion and started to fight against them. Of course we need details, but details can be organized in a hierarchic way so that several levels of reading are possible. Put in an other way, it is not to us to decide what is the right level of details needed to understand a subject, it is to the reader to decide to which level of details he is ready to go to understand the subject.

I'm a bit skeptical about insisting on Venn's diagrams, but I can conceive that it is important for some kinds of usage of Boolean algebra, if this is what you're thinking. I've also seen that Tijfo098 added a reference to satisfiability and I think this has indeed to be mentioned in a summary page. By the way, this is another reason to be synthetic in the summary. The article is aready 63kB long (19 printed pages) for a recommended size of 30kB-50kB (10 printed pages) and not all related topics worth to be mentioned are mentioned yet. --Hugo Herbelin (talk) 23:00, 8 April 2011 (UTC)

The point about the article being oversized by Wikipedia standards is a good one. At one time Britannica had a micropedia and a macropedia with the latter accommodating articles that could be considered "naturally large." I'd be fine with shrinking it to 50 kB. It's a very important subject however so I don't see it as urgent to shrink it much more than that.

StuRat's goal was well-intentioned, his problem was that he had no idea how to organize this sort of information. Starting an explanation with "Let X be a set" is hardly great pedagogy, and the rest of his "explanation" was even less coherent.

One thing I didn't understand was the following. "Moreover, the basic of Boolean algebras is somehow simple and can be understood without knowing anything in group theory and vector spaces. So I think the concepts have to be kept apart. Links to group theory and vector spaces will naturally appear as a consequence of connecting the study of the algebras to abstract algebra. We have no reason to make presuppositions on the knowledge of the readers. The readers can be any kind of readers." Care to expand on what you had in mind here, and what changes to the present article this would entail? --Vaughan Pratt (talk) 07:35, 11 April 2011 (UTC)

Hi Vaughan, I think I misunderstood your own sentence about group theory and vector spaces. I have no claim that it would be relevant to talk about this in the Boolean algebra article. I was reacting to what I thought was your intention to refer to group theory and vector spaces in the article. The current article does not have any such reference and it is good like this. In short, my sentence entails no changes to the present article. --Hugo Herbelin (talk) 09:06, 15 April 2011 (UTC)

Boole and Boolean Algebra

There is a mistake in the first line of the article. Boole did not introduce the concept of a Boolean algebra in his book(s). See Hailperin's study of Boole's algebras or Stanley Burris's article on the issue. 'Boolean algebra' was introduced by Jevons. http://www.math.uwaterloo.ca/~snburris/htdocs/MYWORKS/PREPRINTS/aboole.ps Minusia (talk) 23:13, 7 April 2011 (UTC)

The concept of a Boolean algebra was indeed not introduced by Boole in his 1854 book. But neither was it introduced by Jevons, and neither does the lead claim that either Boole or Jevons introduced it.

Incidentally Charles Peirce writing a little later was skeptical that Jevons had nailed the concept of Boolean algebra any better than Boole himself. The big picture was surprisingly slow to emerge. Moreover Burris's claim that Boole did not infer that 0 and 1 were the only solutions to A² = A is contradicted by a footnote in Boole's book cited earlier in this talk page where he states exactly that. --Vaughan Pratt (talk) 07:22, 11 April 2011 (UTC)

It looks like we have some history issues again, this time on behalf of Jevons [7]. I've added the book by T. Haliperin as further reading. It will probably be useful in dealing with stuff like this. (I didn't check out a copy just yet.) Tijfo098 (talk) 03:02, 11 April 2011 (UTC)

Somewhat surprisingly, chapter 1 of [8] ISBN 0691058539 also has detailed account of the birth of Boolean algebra including the contributions of Jeveons, etc. Tijfo098 (talk) 18:42, 11 April 2011 (UTC)

---

Back in 2000 Stan Burris wrote an unpublished, unreviewed, and uninformed article on Boole's contribution to Boolean algebra. He claimed that "the algebra of logic developed by Boole was not Boolean algebra." He further claimed that "Contrary to popular belief Boole did not work with a two-element Boolean algebra."

If Burris has read Boole's 1854 book it was not with any care or understanding. First, though Boole didn't say so explicitly it is clear that he knew how to express every n-ary Boolean operation, namely by writing it in full DNF where every disjunct contains all literals (so TRUE is expressed as the sum of all 2ⁿ possible conjunctions of n literals, with the negative literal x written (1-x)). In particular the disjunction of x and y requires three disjuncts, namely x(1-y), y(1-x), and xy. Boole expressed inclusive disjunction as the sum of all three, and exclusive disjunction as the sum of the first two. It is true that he did not realize the latter could be written more concisely as x+y, but that is not the same thing as claiming he invented something other than Boolean algebra.

Second, here's a direct quote from Boole 1854. "Let us conceive, then, of an Algebra in which the symbols x, y, z, &c. admit indifferently of the values 0 and 1, and of these values alone. The laws, the axioms, and the processes, of such an Algebra will be identical in their whole extent with the laws, the axioms, and the processes of an Algebra of Logic. Difference of interpretation will alone divide them. Upon this principal the method of the following work is established." By this he seems to be saying that the laws, axioms, and operations for 0-1 valued logic are identical to those of other logical values, perhaps including sets. To claim that Boole did not work with a two-element algebra is sheer ignorance.

The idea that Jevons invented Boolean algebra is just as absurd. Jevons was De Morgan's student, and his 1864 book religiously follows the conventions in De Morgan's 1858 paper "On the Syllogism III" (OtS3) in all respects except for a notational difference (that De Morgan took strong exception to incidentally), namely to replace De Morgan's notation (A,B) for the (inclusive) disjunction of A and B with the notation A+B. Jevons expressed De Morgan's laws in 1864 by saying that if C = A+B then c = ab, following De Morgan's convention of writing positive and negative literals in respectively upper and lower case. Compare this with what De Morgan wrote six years earlier in OtS3: "The contrary of an aggregate [disjunction] is the compound [conjunction] of the contraries of the aggregants: the contrary of a compound is the aggregate of the contraries of the components. Thus (A,B) and AB have ab and (a,b) for contraries." What has Jevons added to De Morgan here? And as you (Tijfno098) pointed out above, Boole himself wrote De Morgan's laws formally even before De Morgan did, albeit more clumsily because although the conjunction of x and y was simply xy he had to write their disjunction as x(1-y) + y(1-x) + xy.

Unless User:Minusia can defend his claims (the second is not even sourced) I propose to revert them. --Vaughan Pratt (talk) 01:05, 12 April 2011 (UTC)

I agree that reverting the lead to what it was before Minusia's edit is a good temporary solution. The good long term solution is to have a well-researched history section based on published and hopefully reliable wp:secondary sources. It will become more evident what to put in the lead with respect to priorities/contributions afterwards. The two books I found look promising, but I don't have a copy of either one just yet. Tijfo098 (talk) 02:00, 12 April 2011 (UTC)

Other less useful sources

FYI, Martin Davis has a short chapter (#2) on this in his book The Universal Computer, but it's not sufficiently detailed with respect to the contributions of the other guys (Jevons, Peirce etc.) It's a bit too hagiographic. Tijfo098 (talk) 02:08, 12 April 2011 (UTC)

It has an amusing part though:

“

At this time, Boole developed professional correspondences and friendships with a number of England's leading young mathematicians. And, in fact, it was a quarrel between the Scottish philosopher Sir William Hamilton and Boole's friend Augustus De Morgan that brought Boole's thoughts back to his long ago flash of insight that logical relationships might be expressible as a kind of algebra. Although Hamilton was an erudite scholar in aspects of metaphysics, he seems to have been something of a quarrelsome fool. Out of what can only have been his colossal ignorance of the subject, he published diatribes against mathematics as a subject. What had set him off was De Morgan's publication on logic that Hamilton claimed plagiarized what he thought of as his own great discovery in logic, what he called the "quantification of the predicate." We need waste no time trying to understand this idea or the fierce controversy it generated—it is of importance only because of the stimulus it provided to George Boole.

”

-- Tijfo098 (talk) 02:14, 12 April 2011 (UTC)

See #The_De_Morgan-Hamilton_duel below for more on this. --Vaughan Pratt (talk) 05:11, 12 April 2011 (UTC)

Early history outline

De Morgan, Jevons

FYI, T. Haliperin (ISBN 0444516115, Algebraical Logic 1685-1900 p. 346) considers De Morgan "The last great traditional logician" and says about his work: "Despite many insightful and forward-looking innovations the basic framework for De Morgan's logic was still the Aristotelian syllogism with its four categorical sentence forms, each with a copula connecting subject and predicate terms." However TH credits De Morgan with "his introduction of a universe [of discourse], arbitrarily specifiable, together with the removal of any distinction between a name and its contrary, either of which could be taken as the positive term." Interesting enough, De Morgan's student, Jevons, contributed to Boolean algebra by replacing Boole's (set) difference with negation along those lines. Tijfo098 (talk) 02:49, 12 April 2011 (UTC)

Could you cite a specific passage from Jevons 1864 that treats negation any differently from how De Morgan 1858 (On the Syllogism: III) treats it? --Vaughan Pratt (talk) 05:27, 12 April 2011 (UTC)

Also TH says this about De Morgan: 'Although he introduces a symbol U for "everything in the universe spoken of" and u for its contrary, denoting "nonexistence", De Morgan declines to use them in syllogistic inferences, considering them to be extreme cases which would only be of interest to mathematicians "on account of their analogy with the extreme cases which the entrance of zero and infinite magnitude oblige him to consider"'. Tijfo098 (talk) 02:52, 12 April 2011 (UTC)

Jevons is also credited (p. 367) with replacing + as xor (as Boole used/defined it) with the non-exclusive version, making it dual/symmetric to "and". Tijfo098 (talk) 02:59, 12 April 2011 (UTC)

From De Morgan's perspective all that his student Jevons had done was to change De Morgan's notation for disjunction from (A,B) to A+B. De Morgan objected strenuously to this change, perhaps in part because Boole was already using A+B with a different meaning, perhaps because De Morgan saw no reason to change his (A,B) notation. Today we write Boole's x+y as x⊕y and Jevons' A+B as A∨B (due to Russell). --Vaughan Pratt (talk) 05:27, 12 April 2011 (UTC)

However TH says on the next page that Jevons "By thus treating 0 as if it were, and yet were not, a term, Jevons fudges over the need for explaining what qualities it does have and what is meant by a combination of 0 with a genuine term." Tijfo098 (talk) 03:02, 12 April 2011 (UTC)

Perhaps a bigger complaint about Jevons is that he did not accept distributivity of disjunction over conjunction, showing that his understanding of Boolean algebra was incomplete. --Vaughan Pratt (talk) 05:27, 12 April 2011 (UTC)

Also, the next chapter in the Handbook (by Valencia) is more sympathetic to De Morgan, at least at the philosophical level by citing this: "We know that mathematicians care no more for logic than logicians for mathematics. The two eyes of exact science are mathematics and logic, the mathematical sect puts out the logical eye, the logical sect puts out the mathematical eye; each believing that it sees better with one eye than with two. [De Morgan, 1868, 71]". Tijfo098 (talk) 04:06, 12 April 2011 (UTC)

(I have to say that also applies to Wikipedia editors of today, to a certain extent.) Tijfo098 (talk) 04:07, 12 April 2011 (UTC)

I am sympathetic to Boole, De Morgan, Peirce, and Schroeder, all of whom made substantive contributions. Boole's priority and depth of understanding, even if not complete, fully justifies naming the subject for him. I would be very interested in any evidence that Jevons played any important role in the development of Boolean algebra. --Vaughan Pratt (talk) 05:27, 12 April 2011 (UTC)

Peirce

"A few years after Jevons' 1864 [book], but independently of it, C. S. Peirce's first paper in logic, 1867, likewise introduced a non-exclusive sum of terms in an algebraic context. However, unlike Jevons, Peirce adheres to the extensional point-of-view of Boole's calculus. Moreover, he retains its problematic features, i.e., undetermined and uninterpretable terms, which Jevons had eliminated. It is clear from Peirce's writings that he wanted his later work—in which among other changes these problematic features no longer appear—to supersede that of this fledgling paper. " Tijfo098 (talk) 03:06, 12 April 2011 (UTC)

It's a good question what Boole himself considered to be the interpretable terms. At some gut level he seems to be aware that x+y can be treated simply as disjunction when xy = 0, where the distinction between inclusive and exclusive disjunction does not arise. This seems to be what underlies his representation of inclusive disjunction as x(1-y) + y(1-x) + xy and exclusive disjunction as x(1-y) + y(1-x). If one follows that rule consistently, all n-ary Boolean operations are expressible, for example x→y as xy + y(1-x) + (1-x)(1-y). --Vaughan Pratt (talk) 05:39, 12 April 2011 (UTC)

Robert Grassmann

According to TH (p. 370-371), "Apparently Grassmann was unaware of any contemporary work in logic as he mentions only Lambert's Neues Organon of 1764 and Twesten's Logik of 1825." TH conclude with "Grassmann derives just about all the standard elementary results of Boolean algebra—not surprisingly since his algebra of concepts is just a Boolean algebra of (finitely many) atoms. Absent only is the recognition of the duality principle (but no one else had at this time), and the idea of the development of a Boolean function as a sum of constituents. If Die Begriffslehre oder Logik [1872] had appeared 25 years earlier conceivably we might all be referring to Robert-Grassmannian algebra instead of Boolean algebra. Indeed, it is a closer fit to Boolean algebra than is Boole's algebraic system." Tijfo098 (talk) 03:12, 12 April 2011 (UTC)

Robert Grassmann is a younger brother of Hermann Grassmann. The two used to collaborate a fair bit. Hermann is the inventor of linear algebra, though it had to be reinvented before his priority could be recognized: his book introducing the subject while both correct and remarkably insightful is pretty incomprehensible as written. --Vaughan Pratt (talk) 05:57, 12 April 2011 (UTC)

Schröder

TH (p. 371-372): "Schroder's 1877, Der Operationskreis des Logikkalkuls, opens with the expression of surprise at the lack of attention given to Boole's remarkable achievment, that of realizing the ideal of a calculus of logic which Leibniz had propounded. Schroder was unaware of Jevons 1864 and Peirce 1867 since he cites as the only works subsequent to Boole's, two short notes (Cayley, A. J. Ellis) and the independently arrived at treatment of Grassmann's, just described. The neglect of Boole's work is attributed to its imperfections." Tijfo098 (talk) 03:16, 12 April 2011 (UTC)

TH goes on: «Unlike Jevons with his "qualities" and Grassmann with his "Begriffe", Schroder is forthrightly extensional—classes are what logic calculus is about. And, unlike Peirce, the subject is not grounded on general algebraic notions with multiple interpretations, but on clearly defined operations on classes—class union symbolized by '+', intersection by 'x' and complementation by a subscript '1' (which in his 1890 becomes a short vertical line, presumable so as not to confuse it with the numeral).» (N.b. presumably this is the origin of ¬.) «Of historical interest is Schroder's calling attention to and establishing the duality principle for logic—that to each general valid formula another is obtained on interchange of '+' with 'x' and '1' with '0'. Intimation of this principle occurs in Peirce 1867 (which Schroder had not yet seen) which called attention to the double distributivity—of multiplication over addition and addition over multiplication.» I think I'm getting close to violating copyright here, so I'll stop, but the above are sufficient to write a semi-decent early history section. Tijfo098 (talk) 03:22, 12 April 2011 (UTC)

Valencia writes (p. 477): «We shall pay attention to the theory of logic he develops in [Schroder, [1877] 1966]. This elegant booklet is the third equational logic written after Boole. The resulting system is "the algebra of logic as we know it today " [Lewis, 1918, 111]. As we shall see, Schroder defines a structure with two binary operations, multiplication and addition, a unary one, negation, and two constants, 0 an 1 that satisfy all the axioms of a Boolean algebra. However, when preparing this work Schroder was not aware of Jevon's nor of Peirce's contributions to algebraic logic.» Tijfo098 (talk) 04:21, 12 April 2011 (UTC)

And on the next page: "Indeed, it has been claimed that the main influence on his work stems not even from Boole. The roots of his equational logic, is argued in [Peckhaus, 1997], lie in the symbolic logic of Robert Grassmann and the doctrine of forms of Herman Günther Grassmann and Herman Hankel. The same thesis is defended in [Peckhaus, 1996]." So, apparently this influence is a relatively recent discovery, which probably explains why Haliperin 1986 book makes no mention of R. Grassmann, but Haliperin had changed his mind by 2004 to argue for it forcefully. Tijfo098 (talk) 04:21, 12 April 2011 (UTC)

I've found Schrőder tremendously insightful, clear, and broad in his coverage. He's definitely one of my favorite 19th century algebraic logicians. --Vaughan Pratt (talk) 06:12, 12 April 2011 (UTC)

The De Morgan-Hamilton duel

In the earlier quote from Martin Davis, Martin omits De Morgan's contribution to turning this into a battle royal. The following is a very abridged summary of a much more complex soap opera, some of which I presented at a talk in Edinburgh in 1989 based on Peter Heath's introduction to On The Syllogism, and Other Logical Writings, an anthology in book form of De Morgan's contributions to logic.

In November 1846 De Morgan had written On the Syllogism: I. What set the battle off was Hamilton's strongly worded accusation that De Morgan had simply plagiarized his unpublished notes. De Morgan was a prickly but scrupulously honest character, a very bad combination when being so accused. De Morgan quickly persuaded Hamilton he'd gone too far, and Hamilton was ready to back down on his charge of willful plagiarism. However De Morgan demanded a full and public apology. Hamilton wasn't ready to back down that far, so De Morgan threw down the gauntlet and challenged Hamilton to a written duel in the Athenaeum, to which Hamilton agreed. The date at this point is around April 1847.

Hamilton's first shot in this duel was titled Letter to Augustus De Morgan, Esq and included all the prior correspondence. Hamilton replaced his charge of willful plagiarism with the only slightly weaker charge that De Morgan was laboring under the delusion that what he'd learned from Hamilton's notes was his own discovery. Hamilton argued that De Morgan had no way of independently figuring out any of what he'd claimed as his own prior to seeing Hamilton's notes.

De Morgan's first shot was Statement in Answer to an Assertion made by Sir William Hamilton. He argued that he had acted with complete propriety in sending Hamilton everything he was claiming as his prior to any attempt at publication, and that furthermore it contained much that was not in Hamilton's notes, for example a new syllogistic form allowing the inference from "most men have coats" and "most men have waistcoats" that some men must have both. He pointed out that Hamilton had only attempted to explain Aristotle's existing syllogisms and not to invent new ones.

Hamilton responded with a lengthy Postscript arguing that anything De Morgan might have added was based on a confused understanding of Aristotle. De Morgan replied briefly but angrily in the Athenaeum to this, Hamilton reciprocated a week later equally angrily, then at the beginning of June 1847 silence fell.

That autumn De Morgan published his book Formal Logic (originally intended to teach rigorous reasoning to his geometry students), on the very same day as Boole published his pamphlet The Mathematical Analysis of Logic while citing the battle as the inspiration for a renewal of his earlier interest in the algebra of logic. In November De Morgan sent a copy of his book to Hamilton, who returned it a week later.

This battle continued on until 1852, with De Morgan writing On the Syllogism: II in February 1850, then abated, in part because De Morgan, aware of Hamilton's failing health, appeared to find continued hostilities unchivalrous. When Hamilton died in 1856 De Morgan published a brief obituary in the Athenaeum, then returned to writing about syllogisms. On the Syllogism: III appeared in February 1858, where inter alia he introduces an explicit operation of disjunction and states De Morgan's laws. On the Syllogism: IV is dated November 1859 and gives the first treatment of relation algebra including the concept of residuation which he refers to as "Theorem K." --Vaughan Pratt (talk) 05:07, 12 April 2011 (UTC)

Introduction / obscure explanations

Using analogies to arithmetics for introduction is counterproductive and not helpful. The sections "Operations" and "Laws" are full of nonsense and misleading gibberish.

• Explaining conjunction on 0 and 1 by analogy to multiplication is nonsense because Boolean Algebra in general has more than 2 elements.
• Using the semi-analogy for disjunction which even needs a trick to work is even more nonsense.
• What is "ordinary algebra"?
• Splitting the laws into those that have arithmetic analogies and those that don't is absolutely not helpful in explaining the nature of Boolean Algebra. (A hint to this in a lecture helps to prevents confusion; referring to it throughout the introduction creates confusion.)
• Speaking of "additional laws" is playing on the confusion, because Boolean Algebra is in no way an extension of arithmetics.

To be revised substantially.