Talk:Boolean algebra/Archive 4

This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

I've put up a proposal on the BATF talk page here.  --Lambiam 20:48, 25 March 2011 (UTC)

Hum Lambiam, did you really get a consensus before taking action? Anyway, in the meantime, I made a summary of the situation, as I see it at User:Hugo Herbelin/BAsummary. Lambiam's proposal is Proposal 3 as I understand it, my preferred proposal is Proposal 1 (with variants B1, S1, L2, I1, D1), Proposal 2bis was supported by Trovatore but is now abandoned for Proposal 2. This is not as detailed as what is on the task force page in terms of the inner contents of the articles but it is hopefully more precise in the different existing opinions (including mine!) and in the exact organization plans. Do you think it is worth to put it on the task force page? --Hugo Herbelin (talk) 22:25, 25 March 2011 (UTC)

Yes, I thought a clear majority was OK with A3, while a sizable group, probably also a majority, was strongly opposed to A1. But if you think otherwise, hold a poll between these two alternatives. I myself was not happy with the Draft RFC, because having four alternatives makes it hard to achieve a meaningful result.

Likewise, I feel your collection of proposals-cum-variants is too complicated as it is, and, moreover, unnecessarily so. There is no difference in mathematical substance between your 2.1 and 2.2; the only difference might be the depth of treatment and the choice of examples given the intended audience. But we can hardly tell the reader, "if you're an electrical engineer you shouldn't be reading this".

In spite of the name, as I read Boolean algebras canonically defined, it tells us as much or more about Boolean algebra than about Boolean algebras, and might in fact have been called "Boolean algebra canonically defined". If it is merged, my preference would be to merge it to Boolean algebra and not Boolean algebra (structure).  --Lambiam 23:18, 25 March 2011 (UTC)

"Every paragraph, every sentence in fact, of Boolean algebras canonically defined is there for one purpose only: to define, explain and understand Boolean algebras canonically. Let me know of any sentence in that article that you believe this to be false of and I will try to clarify the article so that readers don't get the mistaken impression that the article is about anything except Boolean algebras themselves. When I wrote that article I had no objects in mind except Boolean algebras. --Vaughan Pratt (talk) 02:18, 26 March 2011 (UTC)

Responding just to your last point, merging "canonically" into "field of study": Might be good. I hadn't looked at it in some time. At a brief glance it seems to me that it would be unwieldy to merge it into the structure article. If I could figure out what it's really about, which I don't have time to do right now, I might have some better suggestion. --Trovatore (talk) 23:36, 25 March 2011 (UTC)

What it's really "about" is the mathematical content of what it means to be a Boolean algebra. There's a ton of definitions of "Boolean algebra," all of which are obviously not canonical, which means that they're not insightful: each of them is just one of thousands of arbitrarily chosen possible points of view. Boolean algebras canonically defined is exactly that: it is the translation into ordinary algebraic language of the Lawvere conception of an algebraic theory and its models, instantiated for Boolean algebras. Now that is canonical. --Vaughan Pratt (talk) 02:18, 26 March 2011 (UTC)

I humbly suggest that most mathematicians do not agree with Lawverian ideology (not that I'm very clear on just what it is, but I'm pretty clear that not too many working mathematicians worry about it much), though certainly they will take from him anything they find useful. That makes the article basically an expression of a minority POV. I take back my suggestion that it should be merged anywhere. Probably there should be some reference to it from the main structure article. Also it needs a better title. --Trovatore (talk) 02:36, 26 March 2011 (UTC)

Vaughan, please.... don't remember that it is on Wikipedia that you're contributing! We expect more from you than just exposing your views, however instructive they can be. --Hugo Herbelin (talk) 03:33, 26 March 2011 (UTC)

All guidance as to what I should do with my views is gratefully accepted. I am open to all opinions on the canonicality of a given perspective on Boolean algebra. Please tell me (a) which are the canonical Boolean operations, and (b) which are the canonical equations defining what it is to be a Boolean algebra. Lawvere has one view on this that is obviously canonical to me since all other proposals I've seen are obviously not canonical. However if you have a view that you can argue is at least as canonical as Lawvere's if not more so then I'm completely open to adopting it in place of Lawvere's view. (Note that I've translated Lawvere's categorical account of his view into ordinary algebraic language, so the objection that category theory is inferior to algebra, which I'm neither agreeing nor disagreeing with, is irrelevant here.)

Trovatore, do you have any objection to being quoted on this masterpiece by you: "Most mathematicians do not agree with Lawverian ideology (not that I'm very clear on just what it is)"?

With much the same logic you could say, "Most veterinarians do not agree that Schroedinger's cat could be both dead and alive, not I'm very clear on quantum mechanics." Has it never occurred to you that the mathematics we take for granted today could well have been considered "ideology" by 17th century mathematicians? --Vaughan Pratt (talk)

Canonical is informal concept, right? So, translated in a common language (those of Boolean operations, if seen from the point of view of the two-element domain - or connectives, if seen from the point of view of propositional logic), the question is whether taking as primitive the (maximally expanded) disjunctive normal forms (what your "canonical" representation is, after all, up to duality), is more canonical, than, say, taking Sheffer's stroke or taking the standard 0, 1, ∨, ∧, ¬ set? All the three of them are canonical to some respect. The first one has the canonicity of normal forms, the second one of generating all connectives in a single one, the third one of capturing separately and minimally each elementary "logical" substance involved in the concept of connective.

Then, for the equations, the question of canonicity makes sense only once you have fixed the basis, right? In the case of disjunctive normal forms, I consider that your axiom scheme A1 as canonical (but you actually do not have many choices, so it has to be canonical). For the Sheffer's stroke, I have no idea of the equational theories of it. For the 0, 1, ∨, ∧, ¬ basis, I did not really think to the question of a canonical equational theory, but for sure, if I had to define the laws, I would do it from the underlying order (greatest element, lowest element, glb, lub, complements, distributivity) what I find express at best the essential meaning of the connectives and their property of distributing over logical sequents.

Actually, I do not even argue against your claim that your construction has some canonicity. I argue against using a language which contributes to hide the relations existing between the different views. For instance, if you had said from the very beginning that when expressed in the language of bases, your construction is made of DNF, and that the axiom scheme A1 is a cut elimination distributivity rule for DNF, the merge with Boolean algebra (structure) could have probably been done much earlier than these days. [Re-edited 01:16, 27 March 2011 (UTC)]

Regarding your first question, I have no problem in that you have views, on the contrary (I do have views too). But our own views are (fortunately) not the only views and I truly believe that the strength of Wikipedia is that it can provide at the very same place different views of a topic, something that you cannot find in one-person written texts. --Hugo Herbelin (talk) 05:32, 26 March 2011 (UTC)

To Lambiam: I'm actually ok with your move to A3 but I don't think that it solves anything about the proliferation of articles and I'm afraid we'll have to keep fighting so that a concrete proposal on the organization of the existing pages be accepted.

I'm not a supporter of 2.1 but

Introduction to Boolean algebra

is a supporter of 2.1 too when it says "Boolean algebra deals with the values 0 and 1" and when it defines semantically the operations from truth tables (can you cite me an external reference about Boolean algebra which is not strictly about meaning 2.1 and that proceeds like that?). That's why I have to consider 2.1 in the proposal.

About engineers. I did not say they don't have to read things about 2.2 or about 1. If I mentioned engineers, it was to bounce on comment from Hans Adler above at 19:04, 22 March 2011.

About "canonically", that's indeed a possibility to consider.

(Did you see this author at [1] who apparently copy-pasted WP in a book!) --Hugo Herbelin (talk) 23:56, 25 March 2011 (UTC)

Engineers who find Boolean algebra too slow for their taste probably didn't need to go to Wikipedia to learn about Boolean algebras. I would be very interested in feedback from those who find it too fast, or too unclear, so that it can be further clarified. As it stands it is the result of three iterations of simplification of Wikipedia articles on a subject that the author has been teaching at Stanford since 1981. That doesn't mean it's crystal clear, but hopefully at least each iteration has been getting clearer. If further iterations can lead to further improvements in clarity I am all for making those improvements! --Vaughan Pratt (talk) 04:19, 26 March 2011 (UTC)

While still trying to answer the question I asked at 23:52, 21 March 2011 above, it seems that textbooks (when looked at google books) more generally adopt definition 2.2 while course notes (when found at google) more often adopt definition 2.1. Am I the only one here in seeing a difference between 2.1 and 2.2? I'm getting perplex. --Hugo Herbelin (talk) 05:40, 26 March 2011 (UTC)

Most people are only interested in finite Boolean algebras, which can be treated as finite bit vectors. Therefore they can conflate 2.1 and 2.2 without causing any confusion. Hans Adler 09:23, 26 March 2011 (UTC)

OK, since having the same article for 2.1 and 2.2 is a clear majority, this is fine for me. Then, I guess I have to feel free to edit

being bold recommendation). Thanks for your answer. --Hugo Herbelin (talk

) 00:56, 27 March 2011 (UTC)

A side remark before it gets too late: when CMBJ moved the Introduction to the main page, it actually copied the page and this disrupted the history, statistics, etc. Wouldn't it be better to have a redirect? --Hugo Herbelin (talk) 00:58, 27 March 2011 (UTC)

I think Boole discovered the algebras (see many refs I gave at

I would simplify it; it isn't necessary to say so much. How about just This article discusses the subject referred to as Boolean algebra. For the mathematical objects, see Boolean algebra (structure). --Trovatore (talk) 19:08, 27 March 2011 (UTC)

What about This article is about the elementary algebra of the algebraic structures called Boolean algebras. For the algebraic structures themselves, see Boolean algebra (structure).? The point is to enforce the relation between the two articles. The "algebraic structure" echoes to the lead of the structure article. The "elementary algebra" echoes to the lead of the "Boolean algebra" article. --Hugo Herbelin (talk) 19:52, 27 March 2011 (UTC)

I don't think that version will be understandable by anyone who doesn't already know what the structures are. —David Eppstein (talk) 20:18, 27 March 2011 (UTC)

I agree. I think it's important to remember that hatnotes are not intended to instruct. They're just to help readers get to the article they're looking for. Less is more. --Trovatore (talk) 20:43, 27 March 2011 (UTC)

OK, I see your point. --Hugo Herbelin (talk) 20:54, 27 March 2011 (UTC)

My sense is that the consensus is to accept that

It shouldn't have been put in the merge tag. Section 5 of this article begins with "Main article: Boolean algebra (structure)" with the understanding that Boolean algebra touches on each of the various subtopics of the topic but does not accord any of them "Main article" treatment. (For example if you google for "algebra", the first sentence of the first result (Algebra) ends in the words "algebraic structures" but Algebra is not the main article on Algebraic structures.)

Right now the organization of Boolean algebra (structure) makes it little more than a placeholder for the real "Main article" on the subject, which can reprise the treatment in Boolean algebra at a pace appropriate to a serious article on the subject and then get on with the more serious stuff that Trovatore is hoping to see go in it. Those arriving at Boolean algebra (structure) who need a gentler introduction can be redirected with a hatnote to the effect "For a more introductory treatment of Boolean algebras as mathematical objects see Boolean_algebra#Boolean_algebras." Hopefully the latter is about as gentle as one can get.

WP:OR. (David Eppstein, any opinion?) --Vaughan Pratt (talk

) 22:20, 27 March 2011 (UTC)

No, I think that's the wrong question. The right division is between the field of study on the one hand, and the objects on the other. They are not in fact "really the same thing"; how can a field of study be the same thing as a mathematical object?

Dividing articles by "level" is occasionally necessary, but it's a last resort in my opinion. I don't think it's needed here, as it's quite possible to give an accessible introduction to the field-of-study article, which is the one that the less-mathematically-sophisticated audiences will be wanting. --Trovatore (talk) 01:39, 25 March 2011 (UTC)

(Oh, possibly I misinterpreted you — sure, I agree that whether they're, say, rings or lattices or whatever is not the main question. In my proposal, all the articles on the objects should be merged into one. The other article is not about the objects, but about the field of study.) --Trovatore (talk) 01:58, 25 March 2011 (UTC)

An article that concerns the "field of study" of the mathematical objects is unlikely to help the CS freshmen. —David Eppstein (talk) 02:50, 25 March 2011 (UTC)

I largely agree with David Eppstein here. I think we need at most two articles. One article Boolean algebra (countable) to include the standard model (non-countable), and an introductory one, say

Introduction to Boolean algebra which would be intuitive (I have yet to find a good book to suggest for this; perhaps Schaum's outline 1st chapter, see link further down). I don't think a "field of study" article that Trovatore mentioned is needed. Besides, a more correct name for that would be "theory of Boolean algebras" [2]; do we really need that one given what it contains? Tijfo098 (talk

) 03:33, 25 March 2011 (UTC)

Not sure I explained myself. The "field of study" is not the study of the objects per se, although it may include it. It is an error to identify the field of study with the two-element algebra (I assume that's what you mean by "the standard model") although that algebra does have a distinguished role.

The field of study is what most non-mathematicians probably think of when they hear the term Boolean algebra. It's not an object. It's something that people do. Does that clarify the distinction? --Trovatore (talk) 03:39, 25 March 2011 (UTC)

I agree with Hans Adler, CMBJ, Lambiam, David Eppstein, and Tijfo098, whose reasoning I understand. I disagree with Trovatore, whose reasoning I don't understand. After trying to follow his many arguments over the past three years opposing Hans Adler's proposal at

WP:OWN, and that if he does not stand down the matter should be escalated appropriately. --Vaughan Pratt (talk

) 18:57, 25 March 2011 (UTC)

To reiterate an analogy that we've talked about a lot in the foregoing, but which David Eppstein and Tijfo098 may not have seen — Boolean algebra (field of study) is to linear algebra as Boolean algebra (structure) is to vector space. --Trovatore (talk) 03:45, 25 March 2011 (UTC)

Or perhaps, more clearly, as group theory vs. group (mathematics). But I don't see that needed here. Are there "boolean algebra theory" conferences/journals? Tijfo098 (talk) 03:57, 25 March 2011 (UTC)

The "B" in the recent conferences BLAST 2008, 2009, and 2010 stands for "Boolean algebras." I can vouch for all three at first hand, even gave four talks at them (though none explicitly on Boolean algebras). I would expect those who did speak about Boolean algebras would be surprised to learn that their research was not within the field of Boolean algebra. Students of matrix algebra who are exposed to its abstract formulation for the first time are less likely to consider linear algebra and vector spaces as different subjects than as synonyms for a way of making matrix algebra difficult. Likewise Boolean algebra and Boolean algebras are synonyms for a way of making propositional calculus difficult. --Vaughan Pratt (talk) 05:16, 28 March 2011 (UTC)

Not quite analogous. Group theory is the study of groups. Boolean algebra (as a field of study) is not really the study of Boolean algebras. Oh, it may include that, as an advanced topic. But more basically, it's the study of what happens in a Boolean algebra.

(In terms of the analogy, linear algebra, at a basic level, is not so much the study of vector spaces as it is the study of vectors.)

That's why I think the field-of-study article can be made quite accessible, at least in its lead and early sections. The structure article, not so much. --Trovatore (talk) 04:02, 25 March 2011 (UTC)

Ok, think you're simply using the wrong terminology "field of study" (wrong relative to everyone else on this page). Do you see included in this "field of study" article basics such as Schaum's 1st chapter (instead of starting witch chapter 3, as the structure/math-majors article would)? If so, you're really talking about an introduction that first explains "what happens", and towards the end may have a section on the more advanced topic of Boolean algebra as structure with a {{main}} to the other article etc. (And I do see our article on Linear algebra as qualifying for Category:Introductions wrt vector space, and linear algebra books in general are that way, e.g. Lang's has "vector spaces" as 1st chapter, and it's of course suitable for undergrads, whereas Grillet's abstract algebra presents vector spaces as a section in the chapter on modules, and this book is aimed at grad students.) Tijfo098 (talk) 04:17, 25 March 2011 (UTC)

I think everyone understood the terminology field of study in the discussion above. Please, let's not have to hash that out again; if you understand what I mean, then please you and David just adopt that terminology for the purposes of this discussion.

The field of study article will of course start out at a more elementary level than the structure article, but that is not the fundamental distinction between them. --Trovatore (talk) 04:25, 25 March 2011 (UTC)

My point is that neither of these addresses the need for an article that talks about Boolean algebra analogously to high school algebra: as something that has a very concrete set of exactly two values, a concrete set of arithmetic-like operations to perform on these values, some simple rules for rearranging formulas with two-valued variables, and something about alternative representations of those formulas as truth tables or circuits. Something at the level that a non-mathematically sophisiticated beginning university student could be expected to understand, and that someone doing computer programming involving Boolean variables should be expected to know. Currently,

For background I wrote

Introduction to Boolean algebra into Boolean algebra when that comes to pass. As it is there is way too much overlap between my second and third articles. Furthermore the third article goes into much more detail about Boolean algebras than the second, which I have no problem with unless people feel it would make Boolean algebra unnecessarily long. --Vaughan Pratt (talk

) 19:08, 25 March 2011 (UTC)

Oh, I think the field-of-study article does in fact address that need. (I'm not necessarily talking about any existing field-of-study article. What I want to do is get a clear understanding of the top-level organization, separate from any existing text.)

Still not sure I got my point across — the field-of-study is not primarily the study of Boolean algebras. It's closer to the study of the things you're talking about. If you're interested in Boolean algebras, you're more likely to want the structure article. But the distinction is not "level" per se. --Trovatore (talk) 04:31, 25 March 2011 (UTC)

Trovatore, I think what you are saying is that vector spaces are essential to linear algebra, and from this perspective linear algebra then is an application of vector spaces, much like digital logic design (sorry no good article on the wiki) is an application of Boolean algebra. (DLD does not include physical engineering issues, but only the logical aspects of designing digital electronics) Tijfo098 (talk) 04:29, 25 March 2011 (UTC)

Actually you can do a lot of linear algebra without ever mentioning vector spaces, just like you can do a lot of Boolean algebra (field of study) without ever mentioning a Boolean algebra (the structure). --Trovatore (talk) 04:35, 25 March 2011 (UTC)

Ok, let's try to be more pragmatic here: which of the existing articles do you think is closest to your "field of study" article? Tijfo098 (talk) 06:33, 25 March 2011 (UTC)

I'd prefer not to get into the existing articles. The history is long and unpleasant. Let's figure out first where we want to be, then figure out how to get there. --Trovatore (talk) 07:33, 25 March 2011 (UTC)

I couldn't figure out how to use this as a ref, but it's worth reading:

• ISBN 9780521592710
  .

--Tijfo098 (talk) 14:56, 28 March 2011 (UTC)

Thanks, Tijfo098. After reading that, one has to wonder whether Jaynes was aware that {00,01,10,11} ordered bitwise (as a diamond) formed a Boolean algebra and hence a Heyting algebra, but that when ordered numerically (as a chain) it formed a Heyting algebra but not a Boolean algebra. This set can therefore be considered as the elements of two distinct four-valued logics, one classical and the other intuitionistic.

"we recongnize the broader meaning, but just find no reason to avail ourselves to it." Tijfo098 (talk) 07:22, 29 March 2011 (UTC)

I'm about to merge

Why would you do that ? Has such a consensus been reached ? And what article is now going to be "by non-mathematicians, for non-mathematicians". That is, designed for those using the basic computer, database, and electronics applications, who aren't interested in the deeper mathematically theory ? (Boolean algebra seems deficient in concrete examples, for instance.) StuRat (talk) 00:48, 29 March 2011 (UTC)

Don't get me wrong, StuRat, I'm all for "Boolean algebra for dummies" as a Wikipedia article. However the reasoning you give that it must therefore be by dummies is not in line with industry practice in that approach to pedagogy.

There is also the question of just how many such articles Wikipedia can accommodate, since we already have as contenders Algebra of sets and Laws of Form. If the latter were just a book review I wouldn't include it, but its Section 5 goes way beyond any review. --Vaughan Pratt (talk) 06:21, 29 March 2011 (UTC)

Laws of Form is crackpot magnet (on Wikipedia and outside); the best we can do is limit the number of links to it from irrelevant contexts like this page. Tijfo098 (talk) 07:27, 29 March 2011 (UTC)

I started a thread at

CBM · talk

) 00:51, 29 March 2011 (UTC)

Which may may well be the case. However while I've been happy to write articles for Wikipedia in the past, if it is standard practice on Wikipedia to revert the contributions of subject experts willing to contribute entire articles on the subject of their expertise then I'll be happy to return to writing peer reviewed articles for professionally edited journals instead of wasting my time writing articles for Wikipedia that simply get reverted without discussion by those with less experience in the area. --Vaughan Pratt (talk) 04:52, 26 March 2011 (UTC)

It fits with the standard

WP:TECHNICAL

, "It is particularly important for the first section (the 'lead' section, above the table of contents) to be accessible to a broad readership." Looking at the two versions, I find neither convincing. The older one-paragraph version is too brief and less informative than what we have room for. Vaughan's version is too long and too technical.

Here is my test: the vellum test. Imagine we decide to present a version of Wikipedia to Jimmy Wales, lovingly calligraphed on the finest vellum. Because of budget and time restrictions (consider how long it takes to rear a sufficient number of calves), we cannot copy the encyclopedia in its entirety. Not only do we select only the most important articles (which naturally includes Boolean algebra), we furthermore only copy the article leads – typically consisting of three, at most four, relatively short paragraphs, and able to stand on their own.

My interpretation of

WP:LEDE is: write the lead as if you know it is going to replace the whole article. So how much do readers take away from the article if they have only read the lead? How well would they be able to answer a pop quiz question, "What is Boolean algebra?" Would they then say, "Oh, it is, erm..., an equationally defined algebraic framework"?  --Lambiam

08:24, 26 March 2011 (UTC)

I agree with Lambiam and David Epstein that on balance the old lede is better than the new one proposed by Vaughan Pratt. Paul August ☎ 14:00, 26 March 2011 (UTC)

Actually, I think that as article leads both are unsatisfactory. Surely, for the gift to Mr. Wales we can do better than this one paragraph of the old lead. The new lead was copied from

Introduction to Boolean algebra, and also there it is more technical (for a lead) than desirable.  --Lambiam

16:23, 26 March 2011 (UTC)

Ok, so the old (= current) lead is too short while the longer (reverted) one is too long and technical. We can easily shorten the longer one by deleting the second and third paragraphs, which don't directly address the requirement that the lead summarize the main points of the article but rather just give interesting background and motivation, which are not

WP:LEDE

requirements.

As far as "less technical" is concerned, how about the following?

• "In mathematics, logic, philosophy, and computer science, Boolean algebra is the algebra of two-valued logic with operations ∧, ∨, and ¬ and constants 0 and 1. Its laws consist of those equations that hold for all values of their variables, for example x∨(x∧y) = x. A Boolean algebra is any model of those laws. Boolean algebra can be understood as an algebraic formulation of propositional calculus by analogy with elementary algebra but with truth values in place of numbers."

As precedent for "two-valued logic" we have Don Monk's SEP article which begins "Boolean algebra is the algebra of two-valued logic with only sentential connectives, or equivalently of algebras of sets under union and complementation." (Monk has written some 70 journal articles on Boolean algebra and is also the main editor of the Handbook of Boolean Algebras.) The key difference between classical and intuitionistic logic is that the former is based on two-valued logic, the same thing that distinguishes Boolean algebra from Heyting algebra as their respective algebraic formulations.

Since the article treats only the lattice basis ∧, ∨, ¬, 0, 1 and does not mention the ring basis ⊕, 0, ∧, 1 anywhere, there is no need for the lead to depart from this by mentioning the possibility of other bases, which can be addressed in more advanced articles.

While one could nitpick the technical accuracy of any proposed lead for ever, most improvements in technical accuracy are likely to be at the cost of accessibility and/or length (spare those calves!) and we will end up never finding the right middle ground between

WP:TECHNICAL. This is not to say such improvements are impossible but only that they should be made with these guidelines kept clearly in mind. If length is a concern then every extra word needs to pay its way. --Vaughan Pratt (talk

) 22:51, 26 March 2011 (UTC)

Looking at the existing lead, what I proposed above leaves out some parts that seem reasonable. Any objections to replacing the last sentence of the suggested lead above with the following as the lead's second paragraph?

• "Boolean algebra was developed by
  Peirce, and Schröder. It can be understood as an algebraic formulation of propositional calculus by analogy with elementary algebra but with truth values
  in place of numbers. Applications include mathematical logic, digital logic, computer programming, set theory, and statistics. "

Absent further comments on this proposed lead I'll replace the existing lead with this one on Tuesday. Neither it nor anything else on Wikipedia is cast in concrete, but in this case if you take exception to it once it's been installed, please fix it incrementally rather than simply reverting it or rewriting it from scratch. --Vaughan Pratt (talk) 04:38, 28 March 2011 (UTC)

I would roughly speaking reverse the order of the two paragraphs you mention. --Trovatore (talk) 04:49, 28 March 2011 (UTC)

Not a bad idea, particularly since it fits with David Eppstein's position that Boolean algebra should ease the reader into the subject. I've been taking the strict academic position that an encyclopedia article should begin with "In subject(s) xyz," followed by a concise self-contained definition of its subject that can be further clarified later on. However I can see where many first-time visitors to the subject might find a paragraph of more user-friendly prose less prickly. What do others think? Should the article start with the cold and geeky "In the beginning was the truth value," or the more warm and fuzzy "In the beginning was George Boole"? --Vaughan Pratt (talk) 05:51, 28 March 2011 (UTC)

Keeping only the first part of Monk's sentence is overly restrictive. Where does it appear in the proposed lead that Boolean algebra is "equivalently [the algebra] of algebras of sets under union and complementation"?

Also, to avoid unnecessary historical details in the lead, I suggest to replace "developed by George Boole" by "named after George Boole" to that the details about De Morgan, Peirce and Schröder can be left to an historical section. --Hugo Herbelin (talk) 10:32, 28 March 2011 (UTC)

I'm also working on the lead, and I'll post it later today. An article like this should have a 4-paragraph lead, which should also explain why bunch of things redirect (or will redirect) here. Tijfo098 (talk) 08:47, 28 March 2011 (UTC)

I had to fix

Ok, posted. Improve as you like. Note however that Pierce and De Morgan contributed to relation algebra, but not much to Boolean algebra. The source I cited probably knew this well. Tijfo098 (talk) 14:22, 28 March 2011 (UTC)

I would say De Morgan's biggest contributions, in On the Syllogism III, were De Morgan's laws, which he used to avoid Boole's logical negation 1-x as a distinct operation (he used positive and negative literals instead), and the introduction of disjunction to the language. This was after Boole but before Peirce. Boole was content to express disjunction as the ring expression x(1-y) + y(1-x) + xy and not abbreviate it to anything (not even to x + y - xy which would have worked), nor even to give it a one-word name like "disjunction" (De Morgan called it "aggregation"). I'll comment on Peirce's contributions later. --Vaughan Pratt (talk) 20:36, 28 March 2011 (UTC)

Thanks, but for the sake of not crossing

WP:RS in this matter, you should first write that outside Wikipedia so we can cite it here. This may seem a little silly when it's about pure math (ask User talk:Gill110951), but less so when it comes to drawing conclusions about the history of mathematics in a particular topic. Tijfo098 (talk

) 02:23, 29 March 2011 (UTC)

If you like I could write a paper proving that De Morgan invented De Morgan's laws, but what are my odds of getting it past peer review? De Morgan's laws are a fundamental aspect of Boolean algebra. Not only did Boole not think of them, they allowed De Morgan to give a complete basis for the Boolean operations, which Boole "proved" was impossible.

You seem to be holding me to a double standard here: you object to my including De Morgan as one of the "perfecters" of Boolean algebra for lack of any source while offering your own unsourced list. Everyone's heard of De Morgan's laws for Boolean algebra, in fact there's a Wikipedia article on them! Not quite so many have heard of Peirce's law perhaps, though the Wikipedia article on that law should alone establish Peirce as a pioneer in the subject, quite apart from a considerable body of work on other aspects of Boolean algebra.

Jevons, Schroeder, and Huntington all came later, too late to get Jevons' law or Schroeder's law or Huntington's law named after them since the real pioneers had taken all the good laws by then. What exactly was your argument again for excluding the real pioneers in the development of Boolean algebra? --Vaughan Pratt (talk) 04:34, 29 March 2011 (UTC)

I'm sorry to disappoint you, but De Morgan did not invent/discover De Morgan's laws. See [3] and verso. This is why you need to cite sources for historical assessments like this. See also Stigler's law of eponymy. Tijfo098 (talk) 05:23, 29 March 2011 (UTC)

And if you click on the article footnote following "my" list, you will see the source is: [4]. Tijfo098 (talk) 05:47, 29 March 2011 (UTC)

Oops, sorry, I managed to overlook your source at the end of the sentence. If the history books also say Peirce did not invent Peirce's law I'll be even more mortified. ;) Serves me right for only reading the original sources (Boole, De Morgan, Peirce) instead of the history books.

But while I've never published a history article per se on Boolean algebra, my article on the origins of the calculus of binary relations appears in the LICS'92 conference proceedings. This calculus has two parts, logical and relative, corresponding to respectively unary and binary relations. De Morgan and Peirce both worked on both parts, and it is unfair to dismiss them as not having contributed to the logical or Boolean part merely on the ground that they contributed to the relative part.

Regarding De Morgan's role, Section 4 of my paper analyzes his Theorem K in detail and concludes that he deserves more credit than Tarski was willing to allow him in 1941, making the point that different readers of the same original source can view it in quite different lights. Theorem K appeared in "On the Syllogism IV" in 1860; De Morgan's earlier work on the logical aspect in isolation was in "On the Syllogism III" which I felt at the time was outside the scope of my article but in retrospect probably should have said more about.

In the interest of keeping the lead short I won't continue to push for the inclusion of De Morgan and Peirce there. It does however strike me as unfair to those two pioneers to have Jevons, Schroeder, and Huntington put in the lead ahead of them on the basis of a sentence by Mike Dunn and Gary Hardegree. --Vaughan Pratt (talk) 22:37, 29 March 2011 (UTC)

The relevance of Peirce's law (which he did discover) to the development of abstract BAs is not immediately apparent to me. I do not insist on those three guys that Dunn & H list as being the only ones worth naming (and they don't insist either when they say "and many others"). My naming of only those three in the lead was quick & dirty job, based on the most reliable source that I could find in a few minutes. After this issue became a debate, I checked Dunn & H's home pages however, and they seem quite qualified to makes those assessments based on their lists of publications. I've added at Boolean algebra (structure) that Whitehead gave the 1st axiomatization of BAs (from another source), because that was an obvious gap there. I don't have a lot of interest in this topic, but this article needs a good history section. Perhaps, that should be written first and then it will become more apparent who to list in the lead. Respectfully, Tijfo098 (talk) 02:29, 30 March 2011 (UTC)

So you're saying Peirce's law is a counterexample to Stigler's law? :)

Dunn and Hardegree most certainly are qualified, sorry if I seemed to be implying otherwise. Mike and I met at a conference in 1979 where we were both giving algebraic logic talks. A decade later we both found ourselves working on residuation, though we never got around to publishing a joint paper. We've put each other up (put up with each other?) on respective visits to Stanford and IU. I'd say we were both about equally qualified to read and interpret the original writings of Boole, De Morgan, and Peirce in the light of algebraic logic as understood today.

When I run across discrepancies between what historians say about seminal papers and what those papers say themselves, my inclination is to side with the latter (unless the historian is refuting priority with an earlier source). My 1992 paper cited above, which was an invited paper published in a conference proceedings and hence presumably citable by Wikipedia, was based not on what historians wrote about De Morgan and Peirce but on closely reading and interpreting "On the Syllogism III and IV" and Peirce's logic papers in "Writings of Charles S. Peirce: A Chronological Edition," spread over all six volumes. The relative (binary relation) half of my paper is not relevant to Boolean algebra but the logical (unary relation) half is, being precisely the logic of Boolean algebra.

Overall, if I had to choose, I would say the omission of Peirce in favor of later writers is a greater injustice than that of De Morgan, because Peirce unlike De Morgan followed Boole's equational approach (albeit with + interpreted as disjunction) and also wrote considerably more of substance on the subject than De Morgan. --Vaughan Pratt (talk) 07:05, 30 March 2011 (UTC)

Frankly, I don't see where in your paper you make the points about De Morgan & Pierce's contributions to BAs that you make here, so I won't add that myself to the article, but I won't object if you or someone else does. Presumably, what you are saying is that by their work on relation algebra they implicitly contributed to BAs as a special case, much like the iterated value method of Bellman was later found to have been a special case of work by Shapley on a more general problem. But since we're talking axiomatization here, and not findings some algorithm, it's less clear to me whether such particularization counts as contribution. Should we list everyone that contributed to the development of Heyting algebras, Kleene algebras (first kind there), De Morgan algebras, and Ockham algebras as well here as having indirectly contributed to BAs? (Because it's a special case of all of those too.) That is debatable methinks, but I've already debated this for far longer that I think it's worth it, so I'm not going to object if someone else sees this as important and adds it to the article. Tijfo098 (talk) 07:58, 30 March 2011 (UTC)

I agree I don't make a strong argument in my paper, which focused on the relatives since I considered the logical part too well known to treat. Better sources on Peirce's contributions to Boole's system would be Peirce's own work, all appearing in the above-mentioned Writings, starting in 1867 with his "On an Improvement in Boole's Calculus of Logic," and half a dozen or more later papers. Probably simplest just to cite the 6 volumes as a single citation, since his papers on "Boolian algebra" as he called it are scattered through them. "Should we list everyone?" I'd be happy to stop with those who'd written about Boole's system prior to 1870, which would be De Morgan, Peirce, and Jevons. Huntington wasn't even born then. It would be fair to include Schroeder though since he was so thorough. --Vaughan Pratt (talk) 19:17, 30 March 2011 (UTC)

I emailed Mike to ask him about his and Gary's historical remarks. He replied as follows, and added that he had no objection to being quoted on Wikipedia.

• You mention wondering about our statement "Boole and his followers tended to favor exclusive disjunction..." and ask "which followers," saying that "the nearest followers I can think of are De Morgan and Peirce, both of whom favored inclusive disjunction as the binary operation companion to conjunction." Gary and I might well have been too quick and maybe a bit legalistic with our phrase "and followers." Frankly I don't think of De Morgan and Peirce as "followers" in the sense that we likely had in mind. I think of them as pioneers in their own right with Boolean (propositional ) logic being just a piece of what they were about and true extenders of Boole's work. Among true "followers" I do recall that Venn followed Peirce in the preference for exclusive disjunction.

As my kids would put it, "What he said." My inclination is to replace Huntington with De Morgan and Peirce while keeping Jevons and Schroeder. Longer term would be some history of the 19th century contributors. --Vaughan Pratt (talk) 05:52, 31 March 2011 (UTC)

Hi, Tijfo098, (I'm writing here, because I could not access your talk page; this message can be deleted once you read it). I've seen you added a merge-from template to the page. Indeed, this is very useful since we easily get confused with all these discussion pages around. By the way, that would be very useful also for people wanting to know about the archive to have at the head of this talk page a list of links to all the relevant discussions that are disseminated here and there:

I'm not sure why Tijfo098 CMBJ or whoever didn't replace the text of

Introduction to Boolean algebra with a redirect to Boolean algebra. The lead of the former is different but I don't believe there's any reason to keep it (I think I'm basically its sole author so no one else should be complaining). --Vaughan Pratt (talk

) 20:43, 30 March 2011 (UTC)

Ok, I've turned it into a redirect now. Tijfo098 (talk) 05:34, 31 March 2011 (UTC)

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

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,

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)

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" [5]
• "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" [6]

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)

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

• Hatnotes: to the mathematical objects
  Boolean algebra (logic) renamed into Boolean algebra (two-valued)
  )
• Lede: definitively present Boolean algebra not only as "elementary algebra" (more or less as in [7]) but also and more generally as "algebra of two-valued propositional logic and field of sets" (e.g. as in [8] or [9], 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
  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
  operator (programming), bitwise operation
  , ...

• Truth tables merged 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
• Detailed paragraphs of Section Applications merged to relevant articles:

• Paragraph on
  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

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

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 [10])", 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

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)

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 [11]. 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 [12]

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)

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:

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