Talk:Boolean algebra/Archive 2
![]() | 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. |
Archive 1 | Archive 2 | Archive 3 | Archive 4 | Archive 5 |
merge tag
I'm against making the intro article the primary topic. It's probably true that it's closest to what the majority of users who type Boolean algebra in the search box are looking for. But that's only half the issue; the other half is links. Most links to the term are going to be looking for the structure. So I think the only reasonable compromise is to have the disambig be the page with the Boolean algebra name. --Trovatore (talk) 00:50, 12 July 2010 (UTC)
- By now pretty much all Boolean algebra links that really should point to Boolean algebra (structure) and that are being used with any frequency should have been fixed accordingly by their users. Hence I would imagine that the remaining Boolean algebra links either aren't looking for the structure or aren't used enough to serve as a reason for preserving the status quo.
- My proposal is to model the dab structure of Boolean algebra on that of Algebra, which has a hatnote to Algebra (disambiguation) and which explains in the lead that algebra splits up into elementary algebra and abstract algebra. Since the need for Boolean algebra (disambiguation) arises for exactly the same reason as for Algebra (disambiguation), it seems to me that it should be handled exactly the same way.
- Just as Section 4 of Algebra treats abstract algebra, so does section 5 of Boolean algebra treat Boolean algebras as structures. I don't see any serious difference here.
- In any event Boolean algebra (introduction) is not really "introductory" in the Wikipedia sense of being "accessible and non-technical" -- while it tries hard to be accessible it's nevertheless technical. The lead could do with a couple more paragraphs however, which I'd be happy to write. --Vaughan Pratt (talk) 18:00, 6 August 2010 (UTC)
- I support the proposal. The mathematical part of Wikipedia is not just for the experts. Boolean algebras (i.e. the structures) are a relatively obscure mathematical topic, especially when you compare it to the immense popularity of Boolean algebra = Boolean logic. As to incoming links, it's enough to have a sentence in the lead such as "There are also mathematical objects called Boolean algebras", and a short section about them in the article. Such links should be fixed anyway. We shouldn't make things more confusing for the general reader for so little benefit to the experts. Hans Adler 12:08, 6 September 2010 (UTC)
- Formally, Boolean logic is obviously the correct topic for the title Boolean algebra, per WP:PRIMARYTOPIC. Hans Adler 12:14, 6 September 2010 (UTC)
- I think that's excessive populism. One of the great strengths of Wikipedia is the coverage of mathematical topics. The most natural way the phrase Boolean algebra will appear in a mathematics article is in relation to the structures. --Trovatore (talk) 20:41, 6 September 2010 (UTC)
- I couldn't disagree more strongly:
- Boolean algebras are a relatively obscure topic even within mathematics. Many mathematicians will know precisely what Boolean algebra is (because they learned about it in school, or because they are teaching it at school or at a higher institution to engineers), but only be able to have an educated guess at what a Boolean algebra is.
- I am convinced that the way the term "Boolean algebra" is used in [[[De Morgan's laws]] and Combinational logic is more typical even for the way mathematicians use it.
- From a higher POV, Boolean algebra may be best understood as the algebra of Boolean algebras. But for most of the audience of our Boolean algebra article(s) this is not a reasonable approach because they won't understand it, while they are perfectly able to understand Boolean algebra itself. In fact, most readers of our Boolean algebra articles will be in a state of unconscious incompetence w.r.t. to Boolean algebra (structure).
- Let's look at the page views in September so far:
- Boolean algebra (structure) – 1500. (The page views for the redirects are negligible.)
- Boolean logic – 6000.
- Boolean algebra (logic) – 4500.
- If we take into account that many readers will follow links to homonyms even if they are not interested in them, it seems clear that the situation is really more strongly in favour of Boolean algebra = Boolean logic (the topic of Boolean algebra (logic) and the content fork owned by StuRat).
- If I do an Amazon search for "Boolean algebra", I get several books on Boolean logic and applications before the book by Halmos and Givant turns up. Among all books with "Boolean algebra[s]" in the title, 8+6+7+7+7+3 refer to Boolean algebra in the sense of algebra as a subject, and 3+6+3+4+0+2 refer to the structures. (I went through the search results for "Boolean algebra" page by page and stopped when things became too dubious. The results for "Boolean algebras" are virtually the same.) Hans Adler 11:11, 7 September 2010 (UTC)
- Agreed. Six months later, how do you stand on this now? --Vaughan Pratt (talk) 07:51, 19 March 2011 (UTC)
- I couldn't disagree more strongly:
I think that the current structure of boolean algebra/logic articles crucially needs to be improved. I was looking for a page describing the structure and, starting from the Boolean algebra page, I finally ended following several links (Boolean logic, Boolean algebra (logic), Boolean algebra (structure)), all speaking roughly about the same thing but with no clear connections between them, while the only article that was at the end answering my initial expectations was the Boolean algebra (structure) page.
The main cause of confusion seems indeed in the ambiguity of the word algebra, that might either denote a structure in general, or say, a calculus, i.e. a concrete way to do some (formal or concrete) computations in some particular instance of Boolean algebra (in practise the two-value Boolean algebra, or Boolean logic). Finally, articles talking about the structure are Boolean algebra (structure), Boolean ring, Two-element Boolean algebra, while articles primarily talking about the logic are Boolean logic, Boolean algebra (logic).
Two articles try to cover both views, including the main one Boolean algebra but in my opinion, this adds confusion by forcing the readers interested in only one aspect to try to catch the inner structure of the whole article while if he had conversely be interested in both aspects, he just would have to follow new links. Besides the main article whose sections 1-4 and 8 are about the logic and sections 5 and 6 about the structure, the other article that mixes both views is Boolean algebras canonically defined which intends to be synthetic but which says (in my opinion unappropriatedly, if not wrongly) Boolean algebras are models of the equational theory of the two values 0 and 1, and which stamps the two-value Boolean algebra as the Boolean prototype what seems a bit exaggerated (after all, the Boolean algebra of sets is, I think, at least as prototypical as {0,1}).
Then, my feeling is that we should make a clearer distinction between the "structure" and the "logic" and avoid trying to propose some unique synthesis of the different views which might at the end please only a few people.
In particular, facing the proposal that "Boolean logic, Boolean algebra (logic) and Boolean algebra (structure) be merged into Boolean algebra, my answer is on the contrary that Boolean algebra should be split into two parts, the first part, Sections 1 to 4 and 8, merged (as far as possible) with (at least one and ideally both) of the articles Boolean logic, Boolean algebra (logic), and the second part, Sections 5 and 6, be merged into Boolean algebra (structure).
I think I would prefer to have the main title "Boolean algebra" bound to a disambiguation page making explicit that Boolean algebra has two meanings, and that the Boolean algebra (logic) article focuses on the two-value instance of the Boolean algebra (structure) article (with this respect, I think that the French Boolean Algebra disambiguation page for instance is clearer). In particular, I think it is an error to continue to present the logic and the structure as unrelated topics.
Otherwise, keeping the current Boolean algebra as the main page (which basically means putting the focus on the logic view) seems to me acceptable to the condition that the lead explicitly says: "this article is mainly about the two-value Boolean algebra, see Boolean algebra (structure) for the general notion of Boolean algebra".
Somehow, it is also a pity that the same list of axioms occur in many places without being connected between them. In particular, I think that the link to Boolean algebra (structure) should be given as early as the Section laws of the page Boolean algebra (and not only in section Boolean algebras (section)). This remark applies to other pages too:
- In Section Laws of Boolean algebra (logic), there should be a link to Boolean algebra (structure).
- Instead of For other uses, see Boolean algebra (disambiguation), the lead of Boolean algebra (logic) should also say something like "this article is mainly about the two-value Boolean algebra, see Boolean algebra (structure) for the general notion of Boolean algebra".
- The lead of Boolean algebra (structure) should not say For an introduction to the subject, see Introduction to Boolean algebra. For the elementary syntax and axiomatics of the subject, see Boolean algebra (logic). For an alternative presentation, see Boolean algebras canonically defined. but rather This article is about Boolean algebra as an algebraic structure, for the two-value Boolean algebra, see Boolean algebra (logic).
- In the body of Boolean algebra (structure), when it comes to the example of a two-value Boolean algebra, it should give a link to Boolean algebra (logic).
- ...
I might have overlooked the possible existence of several views as part of the Boolean algebra (logic) topic. Then it might be possible that several Boolean logic pages are needed (?). Hugo Herbelin (talk) 05:30, 6 March 2011 (UTC)
- The merge appears to have been performed out of process, just recently (more precisely, I think the "Intro" article was cut-paste moved to Boolean algebra). I have reverted. Many of your remarks above make sense only in the context of the "Intro" content being at Boolean algebra, where in my view it does not belong. --Trovatore (talk) 10:38, 6 March 2011 (UTC)
Certainly some articles could be merged or split, but one may not disrupt edit histories. A disambiguation page should be moved, if necessary, not overwritten by an article. Incnis Mrsi (talk) 11:26, 6 March 2011 (UTC)
- So, I'm a bit confused now on where to continue the discussion. Several moves by CMBJ happened in the last 24 hours (including this talk page which I don't know if it is intended to be about Introduction to Boolean algebra or about Boolean algebra, or if it will remain a merge of both talk pages).
- Anayway, whatever will be done, my feeling is that by small efforts in the leads of the "Boolean algebra/logic" articles (such as suggested above) one can cheaply improve the overall layout and mutual dependencies between these pages, leaving opportunities for possible merges in a second step. Hugo Herbelin (talk) 14:29, 6 March 2011 (UTC)
- I stumbled upon this series while taking a business call and shortly thereafter acted prematurely without fully reviewing the talk page. As for my motives, frankly, I've been a contributor here for at least seven years now and I have never before encountered a more disorienting set of articles. It is truly a crying shame that an article on a topic of this importance—especially, one with content of this high a calibre—is so inaccessible that it is far more intimidating than an esoteric scientific journal. And though I'm clearly no longer in the position to be making demands, it is my position that we need to address the approachability of these topics in the immediate future, whether it be by mergers or by the composition of new content. — C M B J 07:54, 7 March 2011 (UTC)
- I agree that it's a mess. It's been a mess for years. But the fix is not to denigrate the "structure" concept! The structures are the most interesting things to mathematicians; the other meaning is basically a synonym for the propositional calculus, which is almost a triviality.
- I am of the opinion that Boolean algebra must remain a disambig page. After that, yes, there's a huge amount of cleanup to do, which should include some merging. I think there is room for either two or three articles -- one on the structures, one on the calculus, and possibly one on the calculus from an introductory level. --Trovatore (talk) 10:03, 7 March 2011 (UTC)
- I stumbled upon this series while taking a business call and shortly thereafter acted prematurely without fully reviewing the talk page. As for my motives, frankly, I've been a contributor here for at least seven years now and I have never before encountered a more disorienting set of articles. It is truly a crying shame that an article on a topic of this importance—especially, one with content of this high a calibre—is so inaccessible that it is far more intimidating than an esoteric scientific journal. And though I'm clearly no longer in the position to be making demands, it is my position that we need to address the approachability of these topics in the immediate future, whether it be by mergers or by the composition of new content. — C M B J 07:54, 7 March 2011 (UTC)
- So long as it remains a disambiguation page, [at the very least a sizable minority of] readers will continue to be dismayed. Consider the following:
- Genetics -> Introduction to genetics
- Quantum mechanics -> Introduction to quantum mechanics
- Special relativity -> Introduction to special relativity
- General relativity -> Introduction to general relativity
- Evolution -> Introduction to evolution
- Virus -> Introduction to viruses
- M-theory -> Introduction to M-theory
- Entropy -> Introduction to entropy
- This is the article structure that we use throughout the project. Readers expect it. And there's nothing that precludes us from doing the same thing here. — C M B J 10:52, 7 March 2011 (UTC)
- I don't think you quite appreciate the situation. None of those other cases are parallel, because none of those other terms are ambiguous. Well, OK, some of them are ambiguous, but not with the same severity — they have a clear primary topic.
- Here there is no primary topic. There is a genuine ambiguity between the "structure" usage and the "calculus" usage. That's what disambig pages are for. --Trovatore (talk) 11:15, 7 March 2011 (UTC)
- I realize now that the difference between structure and calculus usage is of utmost importance, but how is Boolean algebra any more ambiguous than Introduction to Boolean algebra? The latter contains the former in verbatim. — C M B J 11:23, 7 March 2011 (UTC)
- The phrasing introduction to Boolean algebra makes it clear that Boolean algebra is being used as a mass noun. The structure sense is a count noun. It wouldn't be grammatical to say introduction to Boolean algebra in that sense — it'd be like saying introduction to car. --Trovatore (talk) 11:25, 7 March 2011 (UTC)
- That makes excellent sense, but you're making the false assumption that a reader knows the definition—or has ever even heard—of either term. Suppose the following were true:
- There's almost no way that any reader would fail to differentiate between these two subjects with those names, especially when considering that Boolean algebra's header would contain an explicit description of the structure form with an accompanying link to Boolean lattice and vice versa. — C M B J 12:02, 7 March 2011 (UTC)
- The phrasing introduction to Boolean algebra makes it clear that Boolean algebra is being used as a mass noun. The structure sense is a count noun. It wouldn't be grammatical to say introduction to Boolean algebra in that sense — it'd be like saying introduction to car. --Trovatore (talk) 11:25, 7 March 2011 (UTC)
- I realize now that the difference between structure and calculus usage is of utmost importance, but how is Boolean algebra any more ambiguous than Introduction to Boolean algebra? The latter contains the former in verbatim. — C M B J 11:23, 7 March 2011 (UTC)
- So long as it remains a disambiguation page, [at the very least a sizable minority of] readers will continue to be dismayed. Consider the following:
- The problem is that Boolean algebra (structure) is not a natural search term or link. Because the structures are so important to mathematicians, the direct search or link should go to a disambig page, to make sure that the situation is noticed and the correct link can be found. --Trovatore (talk) 20:38, 7 March 2011 (UTC)
- (Oh, and secondarily, I'm against having the structure article at Boolean lattice, per WP:COMMONNAME.) --Trovatore (talk) 20:39, 7 March 2011 (UTC)
- How would the situation go unnoticed on a main page like this? — C M B J 00:45, 8 March 2011 (UTC)
- I'm against making the calculus the "primary topic". I think the structures are just as important. --Trovatore (talk) 01:10, 8 March 2011 (UTC)
- I made a tentative Boolean algebra disambiguation page. I did not take a stand on the quality of the corresponding pages nor on the overlap between articles. It is just at this time an attempt to set up a layout every everyone could agree on. Do you think we can elaborate on this? Or how would you write yourself either a disambiguation page or an appropriate lead to whatever article Boolean algebra would link to. Hugo Herbelin (talk) 12:20, 8 March 2011 (UTC)
- Your draft makes no sense. In the real world there is no difference between Boolean algebra (as opposed to Boolean algebras) in mathematics and Boolean algebra in computer science and electronics.
- Anyway, you are totally addressing the wrong problem. The problem with the Boolean algebra articles comes mostly from a specific Wikipedia editor who owns the article Boolean logic. That's why there are so many articles: Each time someone tried to fix the severe original research problems with that article, that editor became active again, and either made a deep revert (causing someone to copy the previous version elsewhere as a new article) or copied his version to a new POV fork.
- Boolean algebra (singular only) is also, perhaps even better, known as Boolean logic, so that would be the obvious name, leaving Boolean algebra free for the article on Boolean algebras, and we would have a clear structure. But this requires dealing with the problem. You are only adding even more confusion and thereby make it even harder to solve the problem.
- For a past attempt to clean up this mess, to which a lot of productive editors contributed countless hours, see WT:BATF. To get an idea of how we got into this mess, see Talk:Boolean logic/Archive 4 and note that the discussions there involve two Wikipedians who have biographies in the main space here (Vaughan Pratt and David Eppstein) as well as several other mathematicians (some mathematical logicians, such as me or CBM), but also an anonymous user who thinks he is an expert because he has taught the subject to a mixed bunch of people including adults with brain damage (no joke), who believes that set theory including the "element of" relation is a part of Boolean algebra, and who absolutely insists on starting the article with "Boolean logic is a complete system for logical operations" (presumably without knowing what that means) while insisting that several fairly elementary and crucial concepts be left out completely because they are, supposedly, "PhD level".
- Please, help us solve the problem if you want, but don't make it worse. One user of that type is more than enough. Hans Adler 16:34, 8 March 2011 (UTC)
- To be fair to my dear old frenemy StuRat, the fault for the existence of so many articles is not exclusively his. There are at least three articles on the structures — Boolean algebra (structure), Boolean ring, and Boolean algebras canonically defined — and they should all be merged. Still, this is an isolated sub-problem that can be solved independently of the more general problem. --Trovatore (talk) 20:28, 8 March 2011 (UTC)
- To Hans Adler: I'd be happy to see eventually the Boolean algebra problem be solved (if I ended in this discussion it is precisely because I stumbled on this unacceptable "mess"). Thanks for pointing to WT:BATF and Talk:Boolean logic/Archive 4 which is what I was looking for to explain the situation. I read a few bits of the discussion and what I retain is that there were a collaborative work involving StuRat and Vaughan Pratt on a new introductory page, that StuRat expected it to be what he calls general audience, that he was never satisfied with the new page, while on the other side, the page he made could hardly be considered rigorous enough from a mathematical or encyclopedic point of view. As far as I could see, the discussion stopped in Feb 2008 without any solution being found, and, since then, StuRat did not really contributed neither to the Boolean logic nor to the discussion. Is that correct? If yes, can we really continue considering the Boolean Logic page as a single-editor page? Would it make sense for instance to start fixing the inaccuracies and inconsistencies, explaining the unexplained terms, making it a more consistent page and finally renaming it into say, Boolean algebras concepts pervading in computer engineering or whatever? Once the problem of Boolean logic solved (which is obviously not the only problem, as Trovatore says), what would be the next step?
- Coming back to my point (and I don't know if this point was addressed or not in the discussions), one thing I found confusing in all of Boolean logic, Introduction to Boolean algebra, Boolean algebra (logic), and, to some smaller extent in Boolean algebras canonically defined, is that they were not fully clear on whether Boolean algebra (mass noun) was about the two-valued Boolean algebra (explicit requirement in these pages of having two values, use of truth tables, ...) or about reasoning and computing in Boolean algebras in general (references to Venn diagrams, sets, bit vectors, ...). Wouldn't it be clearer to have an article dedicated to the two-valued algebra and another one that non-ambiguously considers the two-valued algebra as just one particular example of what Boolean algebra is about? Hugo Herbelin (talk) 23:45, 8 March 2011 (UTC)
- On that point, the purpose of the second paragraph of Introduction_to_Boolean_algebra#Values was to be "fully clear" on the distinguished place occupied by the two-valued Boolean algebra among its cohorts. I would therefore greatly appreciate any suggestions for that section that would further clarify (a) why the two-element algebra plays such a central role in the subject and (b) what else could usefully be added to that short section. While it could be stated explicitly that the two-element algebra generates the whole variety (which is implicit in the more elementary "obeys exactly the same laws"), and furthermore is the variety's only SI (less obvious), those and other related structural facts would be more appropriately addressed in the main article Boolean algebra (structure) (which currently they aren't).
- More generally, the whole article was intended to be as clear as possible, subject to limitations of space, about Boolean algebra in general, as appropriate for a general introduction to the subject.
- I would also say that Introduction to Boolean algebra is not introductory from Wikipedia's standpoint, whose "Introductory article" tag presumes that introductions are nontechnical. Since the article is about as technical as it can get without becoming inaccessible for a first-time reader of the subject, I would think that unless Wikipedia changes their position on this, the "Introduction to" part of the title is inappropriate for a Wikipedia article. I was not aware of this when I titled it "Boolean algebra (introduction)" and would argue today that it should play a role for Wikipedia analogous to that of the article Quantum mechanics, which is not a dab page but instead contains nine references to "Main articles" and in that sense could therefore be considered introductory by some standards if not Wikipedia's. Relativity on the other hand is a dab page, appropriate given that it has a much wider range of meanings than either "quantum mechanics" or "Boolean algebra."
- Lastly, I would be very surprised if my first attempt at a Wikipedia article on Boolean algebras, Boolean algebras canonically defined, turned out to be accessible to the typical reader wondering what Boolean algebra was all about. While I'm pleased to hear that some people seem to like it, I would guess that they're at the more mathematical end of the spectrum that Trovatore seems to be aiming to serve. While this is obviously where my own head is at (else how could I have written that article?) I don't infer from this that everyone wondering what Boolean algebra is all about is coming at the subject with that background or from that perspective. --Vaughan Pratt (talk) 18:17, 10 March 2011 (UTC)
- To be fair to my dear old frenemy StuRat, the fault for the existence of so many articles is not exclusively his. There are at least three articles on the structures — Boolean algebra (structure), Boolean ring, and Boolean algebras canonically defined — and they should all be merged. Still, this is an isolated sub-problem that can be solved independently of the more general problem. --Trovatore (talk) 20:28, 8 March 2011 (UTC)
- How would the situation go unnoticed on a main page like this? — C M B J 00:45, 8 March 2011 (UTC)
- (Oh, and secondarily, I'm against having the structure article at Boolean lattice, per WP:COMMONNAME.) --Trovatore (talk) 20:39, 7 March 2011 (UTC)
Some background re the proposed merge
I wrote the bulk of Boolean algebras canonically defined, Boolean algebra (logic), and Introduction to Boolean algebra, mea culpa. The first, begun in August 2006, was intended to motivate the concept by defining Boolean algebra as the equational theory of the finitary operations on two elements. This is how theoretical computer scientists tend to view it, as opposed to defining it in terms of a particular basis of operations such as AND, OR, NOT as customary in logic, or AND and XOR (Boolean rings) as preferred by some algebraists such as Halmos.
In hindsight one problem I saw with that article was that it was pitched at much too high a level. This prompted me to try again with the second article in mid-2007, which I envisaged as a suitable replacement for StuRat's "Boolean logic" article. I originally titled it "Elementary Boolean algebra," where "elementary" was intended not in the sense of "easy" but rather as in Elementary algebra. With that meaning of "elementary" in mind I limited the article to values, operations, and laws, with next to nothing about Boolean algebras as the models of those laws. On 17 July 2007 I merged "Elementary Boolean algebra" into Boolean logic as a replacement for StuRat's article. Three days later Trovatore moved it to its present location at Boolean algebra (logic), which was fine by me. On 24 September 2007 StuRat restored his original article under its original name of "Boolean logic," ignoring objections by Lambiam and others on the ground that "discussing it among PhDs will yeild the same PhD-only article as before." Three days later StuRat moved it to "Boolean logic (computer science)" so as to make "clear this article is by and for computer science and electronics applications, and a general audiences, not mathematicians." (I was surprised to learn that I'm a mathematician with no CS or electronics background.)
But again in hindsight I felt that my second attempt still did not go far enough to be considered "introductory." So six months later, starting 25 January 2008, I tried yet again with the third article, initially titled Boolean algebra (introduction). On 19 September 2009 Gary King moved it to its present location at Introduction to Boolean algebra, also fine by me.
So that's the history of those three articles. How do I see them now?
So far no one's complained about the first article. However it's not clear to me at this point what purpose it serves on Wikipedia, so if anyone does want to complain about it please don't hesitate on my account.
It seems to me that my second attempt, Boolean algebra (logic), is completely subsumed by my introductory article, with the additional advantage of explaining the material more systematically and hopefully also more clearly. Hence I would have no objection to simply replacing the second by the third.
However I can imagine Trovatore complaining about doing so on the ground that the third article oversteps the mandate of the second by venturing into the territory of Boolean algebras plural, the subject matter of Boolean algebra (structure).
Trovatore's suggestion of making "Boolean algebra" a dab page pointing to the logic and structure articles therefore makes sense, provided the part about Boolean algebras was removed from Introduction to Boolean algebra.
However Wikipedia offers the hatnote concept as an alternative to the dab page concept. The idea is that for some subjects there is a primary article with one or more hatnotes at the top pointing to secondary articles. I would think it reasonable to make what is now called Introduction to Boolean algebra the primary article, with a hatnote to Boolean algebra (structure) for those readers who want to learn about Boolean algebras plural. With that organization it would not seem so urgent to remove the material on Boolean algebras from the main article, which could treat that subject at an introductory level while leaving the more advanced material for the main article on Boolean algebras. Not everyone who wants to know what a Boolean algebra is needs to read an advanced article on the subject.
(Incidentally Wikipedia does permit plural titles in justifiable situations. "Boolean algebras" is arguably a legitimate alternative to the more awkward "Boolean algebra (structure)". However that's independent of the above.) --Vaughan Pratt (talk) 20:01, 9 March 2011 (UTC)
- I'm against making the introduction the primary article. The natural link from mathematics articles is to the structures. Yes, it can be cleaned up later, but I don't think it's justifiable to downgrade the structure concept in that way. So I think the dab page is the only real option.
- As I implied above, I think Boolean algebra (structure), Boolean algebras canonically defined, and Boolean ring, should all be merged into a single article, which I think should keep the name Boolean algebra (structure). As an aside, there needs to be much more in that article about the actual structure (atomless, free, complete, that sort of thing — haven't read the article recently so I'm not sure how much is there).
- Boolean logic and Boolean algebra (logic) should be merged, if they aren't already.
- Whether there's room for a separate "Introduction" article I'm not sure. The calculus sense of Boolean algebra is already so trivial; why do you need an introduction to a triviality? I think a single article can be written on the calculus that at least starts out accessible to everyone. --Trovatore (talk) 20:29, 9 March 2011 (UTC)
- Trovatore, you raise several interesting questions here. First, in what way do you see "downgrading the structure concept" happening? The proposal to merge some of the other articles didn't seem to entail any interference with the structure article.
- Second, in what sense is elementary Boolean algebra (with "elementary" as in Elementary algebra) trivial? Intensive research into elementary Boolean algebra over the past four decades has been unable to decide whether Boolean theoremhood can be decided in polynomial time, or even whether every Boolean theorem has a polynomial-sized proof. And even those questions we can answer are not always trivial, for example could you yourself easily prove Emil Post's beautiful theorem characterizing exactly which sets of Boolean operations form a complete basis?
- Third, is it really true that those coming to Wikipedia to learn about Boolean algebra do so in order to find out what a Boolean algebra is? There are some who consider themselves qualified to write about Boolean algebra who have not even heard of Boolean algebras, for example the author of Boolean logic who complained here that "phrases like 'algebras' and 'maths' sound like poor grammar here (like 'sheeps' would sound to others)." Granted that those you're working with may view Boolean-valued set theory as the primary substantive application of Boolean algebra (and I'm not unsympathetic to that point of view having given four talks myself at the recent BLAST series of conferences, e.g. [1] and [2]), but what about the even larger communities working in digital design, or automated theorem proving, or software and hardware verification, or computational complexity, who rarely if ever need infinite Boolean algebras?
- With the experience of Boolean algebras canonically defined and Boolean algebra (logic) behind me, I designed Introduction to Boolean algebra to be suitable as the "article of first resort" for those coming to Wikipedia to learn about the subject called "Boolean algebra." You appear to be claiming that the material treated in that article is too trivial to serve that role. Who else feels that way about Introduction to Boolean algebra? (Note that I'm not the one who added the tag claiming the article was "non-technical," I thought it was reasonably technical, am I that badly calibrated?) --Vaughan Pratt (talk) 16:50, 10 March 2011 (UTC)
Is the difference between algebra and an algebraic structure an ambiguity?
I thought it might be helpful to extract this particular question from the others being debated above in order to focus exclusively on it. A negative answer would tend to undermine Trovatore's argument that Boolean algebra needs a dab page on the ground that the theory and the class refer to different things.
The last sentence of the Wikipedia article on Algebra says "Addition and multiplication can be generalized and their precise definitions lead to structures such as groups, rings and fields, studied in the area of mathematics called abstract algebra." This doesn't sound to me like an ambiguity in the usual sense of that word. Rather, to every equational theory we can associate the class of all models of that theory, which (in the case of finitary operations) Garrett Birkhoff showed in the 1930s was closed under homomorphic images (i.e. quotients), subalgebras, and direct products. He furthermore showed that every class enjoying those three closure properties, today called a variety, arose as the class of all models of some equational theory. That is, there is a bijection between equational theories and varieties. What Trovatore is proposing to call an ambiguity is nothing more than one of many such unambiguously defined pairings.
The Stanford Encyclopedia of Philosophy makes the point in the fourth paragraph that the "general methods [of algebra], if not always its specific operations and laws, are equally applicable to other numeric domains [besides reals and complex numbers]" and "are also applicable to many nonnumeric domains." It takes the viewpoint that algebra is usually understood to be about values in some domain, calling such a domain an algebraic structure or algebra. Two paragraphs later it says "Whereas elementary algebra is conducted in a fixed algebra, abstract or modern algebra treats classes of algebras having certain properties in common, typically those expressible as equations." Another two paragraphs later it says "Groups, rings and fields only scratch the surface of abstract algebra. Vector spaces and more generally modules are restricted forms of rings in which the operands of multiplication are required to be a scalar and a vector. Monoids generalize groups by dropping inverse; for example the natural numbers form a monoid but not a group for want of negation. Boolean algebras abstract the algebra of sets. Lattices generalize Boolean algebras by dropping complement and the distributivity laws." (Full disclosure: I'm quoting myself here.) I don't see much ambiguity here.
A nonmathematical counterpart of this situation would be the recent occupancy of the White House. While it is ambiguous to refer to Clinton, Bush, or Obama when it's unclear whether the male or female partner is intended, it is unambiguous to refer to the Clintons, the Bushes, or the Obamas. I would say that the latter usage is much the same with equational theories when paired with their associated varieties: Boolean algebra is defined by one set of operations and laws, commutative algebra by another, regardless of whether we're talking about the defining set of equations (the theory) or the class of their models, which by Birkhoff's HSP theorem is equally definitive.
There is an Algebra (disambiguation) page, but it is linked to by hatnotes at both Algebra and Commutative algebra, neither of which sees fit to be a dab page for any reason, least of all the reason that Trovatore gives, which is equally applicable to every algebraic class. --Vaughan Pratt (talk) 20:13, 10 March 2011 (UTC)
- Boolean algebra as a mass noun is not really the study of Boolean algebras. Technically speaking it's just their equational theory. In practice I think it's less than that. (To respond to your question in the section above, these questions about complexity theory and so on have moved on a bit from what I think of as "Boolean algebra" in the mass sense.
- I think the concept of a Boolean algebra is on the level of the concept of a group or a ring or a field, all of which are disambiguation pages (admittedly, they have a lot more meanings). I don't like the idea of subordinating that concept to one that's basically just symbol manipulation, and of a quite simple sort. --Trovatore (talk) 21:47, 10 March 2011 (UTC)
- As far as I can see there is an agreement about considering "Boolean algebra" as "the general methods of Boolean algebras". As far as WP is concerned, it seems to me that the question is: Shouldn't the pages Boolean algebra (logic) and Introduction to Boolean algebra be unspecific to the
two-valuedtwo-element Boolean algebra in order to be qualified as articles about "the general methods of Boolean algebras"?. - I have another question: Is Boolean logic a synonym of Boolean algebra and if yes, can an expert explain in which contexts one does use Boolean logic, and in which other contexts one does use Boolean algebra? Thanks in advance. Hugo Herbelin (talk) 00:39, 11 March 2011 (UTC)
- No, I don't agree to the first part of that. "Boolean algebra" as a mass noun is only the equational stuff about Boolean algebras. It doesn't include, say, stuff about atomicity or atomlessness, or completeness, or freeness. --Trovatore (talk) 00:57, 11 March 2011 (UTC)
- Regarding whether "Boolean logic" means something other than Boolean algebra, I'm not aware of any consistently drawn distinction. The article Tutorial: Boolean Logic could just as well have been titled "Boolean algebra."
- Regarding specificity of the two-element Boolean algebra, as pointed out in Introduction_to_Boolean_algebra#Representable_Boolean_algebras, every Boolean algebra is representable, meaning it is isomorphic to a set of (possibly infinite) bit vectors closed under the usual Boolean operations, aka a field of sets. Since Boolean operations on bit vectors are computed bitwise using the truth tables for the two-element algebra, this gives a sense in which the two-element algebra is fully general for the subject of Boolean algebras as structures. I'd be happy to make this clearer in Introduction to Boolean algebra if you have suggestions for doing so. --Vaughan Pratt (talk) 09:00, 11 March 2011 (UTC)
- Well, that's a little like saying that R is "fully general" for manifolds. I think you're hiding an awful lot of interesting stuff in the "set of" part. The Stone representation doesn't give you anything close to the most natural way of thinking about any interesting Boolean algebra. --Trovatore (talk) 09:21, 11 March 2011 (UTC)
- 1. How does your analogy with manifolds work? What are the operations on a manifold that are realized coordinatewise as operations on R?
- 2. The theorem that every Boolean algebra is representable as a field of sets is due to Birkhoff in 1935. Stone's insightful contribution in 1936 was to equip the field of sets with a totally disconnected compact Hausdorff topology in a way that identified up to isomorphism the Boolean algebra it came from.
- 3. What's an example of a "natural way of thinking about" a Boolean algebra that does not have a precise (and sometimes even more natural) counterpart in Stone's topological representation? --Vaughan Pratt (talk) 10:24, 11 March 2011 (UTC)
- Well, that's a little like saying that R is "fully general" for manifolds. I think you're hiding an awful lot of interesting stuff in the "set of" part. The Stone representation doesn't give you anything close to the most natural way of thinking about any interesting Boolean algebra. --Trovatore (talk) 09:21, 11 March 2011 (UTC)
- As far as I can see there is an agreement about considering "Boolean algebra" as "the general methods of Boolean algebras". As far as WP is concerned, it seems to me that the question is: Shouldn't the pages Boolean algebra (logic) and Introduction to Boolean algebra be unspecific to the
- For 1, oh, of course it's not coordinatewise. The point is that any manifold (for certain values of that term) is diffeomorphic to a subset of R^n, and all its structure comes from R^n. It's just as reductive to say that if you know about R then you know everything about manifolds, as it is to say that if you know about the two-element Boolean algebra then you know everything about Boolean algebras. The interesting things about Boolean algebras don't go coordinatewise, either. (As a very simple example, there's no way of talking about atomicity coordinatewise.)
- Sure there's a way: when representing a Boolean algebra as the clopens of a Stone space, the atomic Boolean algebras are just those for which every open subset of the Stone space contains a singleton open. --Vaughan Pratt (talk) 22:11, 11 March 2011 (UTC)
- That isn't "coordinatewise". --Trovatore (talk) 22:15, 11 March 2011 (UTC)
- Not sure what you mean by "not coordinatewise." If I say that a representation is atomic when it contains every unit bit vector, is that coordinatewise? (A unit vector is 1 at one bit position and 0 elsewhere.) --Vaughan Pratt (talk) 05:14, 12 March 2011 (UTC)
- That isn't "coordinatewise". --Trovatore (talk) 22:15, 11 March 2011 (UTC)
- Going back to your analogy with manifolds, when we take 2 to be the two-element ring (which happens to be a field incidentally, as well as a Boolean ring aka Boolean algebra), SP(2) = HSP(2) = the variety of Boolean algebras. For your analogy to work, when we take R to be the ring of reals (which happens to be a field incidentally), we would have to have SP(R) = HSP(R) = the variety of manifolds. Are any of these true? --Vaughan Pratt (talk) 05:43, 12 March 2011 (UTC)
- I'm not familiar with your SP and HSP notation. The point, however, is very simple, and doesn't need to be cluttered up with any of that. Yes, every Boolean algebra is isomorphic to a substructure of a product of the two-element Boolean algebra. Exactly as every manifold is isomorphic to a substructure of a product of R. To elide the "substructure of" part, as though it didn't matter, is very misleading. That's the whole point. --Trovatore (talk) 06:21, 12 March 2011 (UTC)
- HSP is a very simple concept described at Birkhoff's_HSP_theorem#Birkhoff's_theorem. Without it one cannot claim that SP(R) defines manifolds in the way that SP(2) defines Boolean algebras. In fact it's not remotely true: a manifold immersed in n dimensional Euclidean space is far from being simply a set of n-tuples of reals closed coordinatewise under the real operations, for which SP(R) is merely shorthand (how is that "clutter"?). If it were, manifolds could be taught at the same level of mathematical sophistication assumed for Introduction to Boolean algebra, allowing Manifold#Mathematical_definition to be greatly simplified. --Vaughan Pratt (talk) 20:33, 12 March 2011 (UTC)
- I think you're overinterpreting a technical result. Yes, Boolean algebras can be represented that way. No, it is not particularly revelatory of the interesting things about them. --Trovatore (talk) 21:33, 12 March 2011 (UTC)
- What I'm claiming is that, up to isomorphism, Boolean algebras and sets of tuples of bits closed under the Boolean operations are the same thing. Moreover the n bits representing an element of an n-dimensional (2^n element) Boolean algebra (which is all that most users outside mathematics ever encounter) are independent of each other, whence each bit can be considered in isolation, whence the initial focus on the two-element Boolean algebra. None of this is true for manifolds immersed in n-dimensional Euclidean space; if it were, in particular if manifolds were the same thing up to isomorphism as substructures of a power of R, manifolds could be taught at a much earlier stage. Moreover none of this contradicts your point, with which I fully agree, that there are many very interesting things that can be said about infinite Boolean algebras. --Vaughan Pratt (talk) 05:23, 13 March 2011 (UTC)
- I think you're overinterpreting a technical result. Yes, Boolean algebras can be represented that way. No, it is not particularly revelatory of the interesting things about them. --Trovatore (talk) 21:33, 12 March 2011 (UTC)
- HSP is a very simple concept described at Birkhoff's_HSP_theorem#Birkhoff's_theorem. Without it one cannot claim that SP(R) defines manifolds in the way that SP(2) defines Boolean algebras. In fact it's not remotely true: a manifold immersed in n dimensional Euclidean space is far from being simply a set of n-tuples of reals closed coordinatewise under the real operations, for which SP(R) is merely shorthand (how is that "clutter"?). If it were, manifolds could be taught at the same level of mathematical sophistication assumed for Introduction to Boolean algebra, allowing Manifold#Mathematical_definition to be greatly simplified. --Vaughan Pratt (talk) 20:33, 12 March 2011 (UTC)
- I'm not familiar with your SP and HSP notation. The point, however, is very simple, and doesn't need to be cluttered up with any of that. Yes, every Boolean algebra is isomorphic to a substructure of a product of the two-element Boolean algebra. Exactly as every manifold is isomorphic to a substructure of a product of R. To elide the "substructure of" part, as though it didn't matter, is very misleading. That's the whole point. --Trovatore (talk) 06:21, 12 March 2011 (UTC)
- Sure there's a way: when representing a Boolean algebra as the clopens of a Stone space, the atomic Boolean algebras are just those for which every open subset of the Stone space contains a singleton open. --Vaughan Pratt (talk) 22:11, 11 March 2011 (UTC)
- For number 3, let's look at what is in some sense the simplest interesting Boolean algebra, namely P(omega)/Fin. Surely you're not going to claim that its Stone representation is as natural as just looking at subsets of the naturals and modding out by the finite sets? --Trovatore (talk) 20:11, 11 March 2011 (UTC)
- Actually it's even more natural: by Stone duality the Stone space for P(omega)/Fin is simply a subspace of the Stone space for P(omega), no modding out needed. P(omega)/Fin is represented by the clopens of that subspace. --Vaughan Pratt (talk) 22:11, 11 March 2011 (UTC)
- Oh, come on. You can't possibly believe that's more natural. You have to artificially go up two types! (I think it's two; haven't thought it out in detail.) Modding out is much more natural. --Trovatore (talk) 22:15, 11 March 2011 (UTC)
- Spoken like a Boolean algebraist. Just as quantum mechanics can be expressed in terms of either waves or particles, so can Boolean algebra be conducted either algebraically (your m.o.) or geometrically (the m.o. of those who work with Stone spaces). To go from one to the other and then back requires as you say two types, one for each direction. However there is no need to go back and forth, just stick with whichever works for you since the two viewpoints, Boolean algebras and Stone spaces, are entirely equivalent (more precisely, dual). Algebraists are obliged to view P(omega)/Fin as consisting of congruence classes of sets of natural numbers (classes of sets, ugh). Geometers need merely erase the unwanted points of the corresponding Stone space, much simpler. --Vaughan Pratt (talk) 05:14, 12 March 2011 (UTC)
- You've obviously never worked with the gadget. Suppose you want to find out whether there is a countably infinite set of pairwise incompatible elements that have a least upper bound. Save time, there isn't. How do you go about it? Well, you take representatives for the elements (it's really not necessary to think of equivalence classes; the objects are simply sets of naturals, except you have to be careful about identity), observe they can be chosen to be disjoint, and given a putative least upper bound, leave out one extra element of each representative, to get a lower upper bound.
- You only have to deal with two very familiar types, namely naturals and sets of naturals. On the other hand, to work in the Stone topology, you have naturals, sets of naturals, ultrafilters on the naturals (i.e. sets of sets of naturals), and clopen sets of those, in a fairly weird topology (e.g. I think there are no convergent sequences except the eventually constant ones?). That's a lot to keep track of, for no clear gain. The representability is a nice thing to know, of course, but I've never actually run across a genuine application for it. --Trovatore (talk) 06:14, 12 March 2011 (UTC)
- I leave it to you to judge whether the theorem proved in this 1978 paper is a "genuine application." Its first paragraph concludes:
- We complete the proof of the following theorem, begun by Parovicenko [in 1963].
- THEOREM. CH is equivalent to the statement that every Parovicenko space is homeomorphic to βω − ω.
- [We leave the translation of this theorem in Boolean algebraic language to the reader.]
- We complete the proof of the following theorem, begun by Parovicenko [in 1963].
- Judging from the remark in square brackets, by 1978 it was apparently deemed unnecessary to do the translation for the reader. Were you aware of this equivalence with CH, and if so why do you suppose van Douwen and van Mill chose to prove it on the Stone space side of the duality instead of what you claim is the easier Boolean algebra side?
- Personally I see it not so much as a "genuine application" as simply the modern way of working with Boolean algebras following the revolution wrought by Stone. --Vaughan Pratt (talk) 20:33, 12 March 2011 (UTC)
- I was not aware of that result, no. CH has a lot of equivalents in a lot of fields; the result itself seems to be largely about objects in higher types so it's not too surprising. But frankly it's implausible to think that anyone working with the structural details of a fairly tractable object like P(omega)/Fin, where the elements are basically just sets of naturals (equivalence classes are a red herring; in practice you work mostly with representatives) would find it advantageous to climb the ladder all the way to clopen sets of ultrafilters in P(omega), just to make the partial order agree with set inclusion. --Trovatore (talk) 21:37, 12 March 2011 (UTC)
- While the equivalence with CH is interesting in its own right, the more important point of Parovicenko's 1963 theorem is to use geometry to reduce the high type of the algebraic characterization of P(omega)/Fin. The latter when done constructively (nonconstructively "picking representatives" does not constitute a definition) makes P(omega)/Fin a set of sets of sets of numbers. Parovicenko gave an equivalent characterization as simply a set of points topologized as per the article Parovicenko space.
- Granted the algebraic characterization of βω − ω as the set of ultrafilters of P(omega)/Fin (aka the free ultrafilters of P(omega)) makes it a set of sets of sets of numbers, the same high type as P(omega)/Fin itself, but its geometric characterization as the unique (up to homeomorphism under CH) Parovicenko space makes it simply an axiomatically defined space of points. This considerable simplification is what I was referring to by the "revolution wrought by Stone." The effectiveness of Stone duality is easily underestimated.
- For considerably more details on P(omega)/Fin, βω − ω, and their axiomatic characterization, see Chapter 2 Section 5.5 starting on p.78 of Handbook of Boolean Algebras (ed. Donald Monk), Vol. 1 by Sabine Koppelberg. --Vaughan Pratt (talk) 04:28, 13 March 2011 (UTC)
- Would be interesting to read that (I don't have the HBA at hand unfortunately). But I think it's bizarre that you claim this duality reduces the type. The elements of P(omega)/Fin, as you work with them in practice, are simply sets of naturals, and please stop missing the point here as I think it must be clear to you what I mean (you don't need to pick specific representatives; you just use any old representative and then be careful about what information about it you use). In practice these are much easier to work with than clopen sets of ultrafilters (I missed where you got rid of the "clopen sets of" part, but maybe there's a way; I still don't see the gain, as even an individual ultrafilter is more complicated than a set of naturals). Maybe you can axiomatize it instead, but there is really no need, as the reasoning about sets of naturals is so concrete. --Trovatore (talk) 06:05, 13 March 2011 (UTC)
- I was not aware of that result, no. CH has a lot of equivalents in a lot of fields; the result itself seems to be largely about objects in higher types so it's not too surprising. But frankly it's implausible to think that anyone working with the structural details of a fairly tractable object like P(omega)/Fin, where the elements are basically just sets of naturals (equivalence classes are a red herring; in practice you work mostly with representatives) would find it advantageous to climb the ladder all the way to clopen sets of ultrafilters in P(omega), just to make the partial order agree with set inclusion. --Trovatore (talk) 21:37, 12 March 2011 (UTC)
- I leave it to you to judge whether the theorem proved in this 1978 paper is a "genuine application." Its first paragraph concludes:
- Spoken like a Boolean algebraist. Just as quantum mechanics can be expressed in terms of either waves or particles, so can Boolean algebra be conducted either algebraically (your m.o.) or geometrically (the m.o. of those who work with Stone spaces). To go from one to the other and then back requires as you say two types, one for each direction. However there is no need to go back and forth, just stick with whichever works for you since the two viewpoints, Boolean algebras and Stone spaces, are entirely equivalent (more precisely, dual). Algebraists are obliged to view P(omega)/Fin as consisting of congruence classes of sets of natural numbers (classes of sets, ugh). Geometers need merely erase the unwanted points of the corresponding Stone space, much simpler. --Vaughan Pratt (talk) 05:14, 12 March 2011 (UTC)
- Oh, come on. You can't possibly believe that's more natural. You have to artificially go up two types! (I think it's two; haven't thought it out in detail.) Modding out is much more natural. --Trovatore (talk) 22:15, 11 March 2011 (UTC)
- Actually it's even more natural: by Stone duality the Stone space for P(omega)/Fin is simply a subspace of the Stone space for P(omega), no modding out needed. P(omega)/Fin is represented by the clopens of that subspace. --Vaughan Pratt (talk) 22:11, 11 March 2011 (UTC)
- Vaughan Pratt, and Hugo Herbelin seem to be saying that the term Boolean algebra is used in relation to Boolean algebras in the same way the terms group theory and ring theory are used in relation to groups and rings. But I'm not aware of such usage. Can anyone point to sources for this? Paul August ☎ 02:13, 11 March 2011 (UTC)
- Here are a few examples of such usage.
- Boolean algebra at the Encylopaedia Britannica, which talks about both the subject and the objects.
- The Mathematics of Boolean Algebra (Donald Monk's article at the Stanford Encyclopedia of Philosophy) which focuses mainly on the objects.
- The article Boolean algebra by Koehler begins with "Boolean Algebra is both a formalization of the algebraic aspects of logic, and the customary language of logic used by the designers of computers. A Boolean Algebra is defined as: [axioms for a complemented distributive lattice]"
- Eric Weisstein's article titled "Boolean algebra" at http://mathworld.wolfram.com/BooleanAlgebra.html talks about both Boolean algebras and syntactic issues such as Huntington's basis and Robbins axiom.
- The class notes Boolean Algebra begins "A Boolean Algebra is a mathematical system consisting of..."
- The class notes Boolean Algebra begins "A Boolean algebra is a set with two binary operations, ..."
- The German Wikipedia article does not make [Boolesche Algebra] a dab page, and treats both the subject and the objects.
- It is hard to separate syntax and semantics when the set of terms in n variables, a syntactic notion, forms the Boolean algebra with 22n elements, namely the free Boolean algebra on n generators, a semantic notion.
- The idea that Boolean algebra is a symbolic concept is a formalist interpretation of the concept. From a Platonic standpoint Boolean variables denote values in some ambient Boolean algebra. Personally when I do algebra I'm a Platonist, formalists who are able to treat algebra as pure symbol pushing are above my pay grade except in simple situations. --Vaughan Pratt (talk) 09:00, 11 March 2011 (UTC)
- Clearly some people have used it that way; I don't think this usage is really standard. To me Boolean algebra as a mass noun just means the calculus. I'm certainly no formalist! That's just my understanding of what the phrase means. --Trovatore (talk) 09:10, 11 March 2011 (UTC)
- Source? Someone claiming that "Boolean algebra" excludes "Boolean algebras," for example? --Vaughan Pratt (talk) 09:49, 11 March 2011 (UTC)
- Clearly some people have used it that way; I don't think this usage is really standard. To me Boolean algebra as a mass noun just means the calculus. I'm certainly no formalist! That's just my understanding of what the phrase means. --Trovatore (talk) 09:10, 11 March 2011 (UTC)
- Thanks, that helps. Paul August ☎ 12:42, 11 March 2011 (UTC)
- Here are a few examples of such usage.
I'm now confused. Among the references given by Vaughan Pratt only the first and third one (Encyclopedia Britannica and Koelher) use the term Boolean algebra (mass noun) (I except the second one which is not clear on whether algebra is in the sense of "study of the rules of" or of "structure"). Moreover, none of the references say that "Boolean algebra deals with the values 0 and 1" as one can read in Introduction to Boolean algebra nor define the Boolean algebra operations from truth tables as one can read too in Introduction to Boolean algebra. Where does such a presentation of Boolean algebra come from?
- I thought Monk made it clear what he intended by "Boolean algebra" in his first sentence, "Boolean algebra is the algebra of two-valued logic." As I say in the paragraph below starting "In the spirit of making the subject as accessible as possible" I mean exactly the same thing by it, no more and no less. Monk's article also addresses your question whether any of these references mention two values---whether they're called 0 and 1 (binary) or false and true (logic) or out and in (set membership) is an application-dependent detail. Weisstein's article says "In modern times, Boolean algebra and Boolean functions are therefore indispensable in the design of computer chips and integrated circuits." and later talks about Huntington's basis and Robbins' axiom. The class notes are neither dictionary nor encyclopedia entries whence had they intended their title to denote the object they would have followed the usual custom of using the plural form in the title (one speaks of "groups rings and fields" rather than "group ring and field", and most books about the structures per se use the plural form for their title). The second paragraph of Rinn's class notes starts out with "One interpretation of Boolean algebra", making it clear he is not speaking there of Boolean algebras per se. The German article says "Die boolesche Algebra ist nach George Boole benannt" (Boolean algebra is named after George Boole). I picked these seven references because I understood them to be about the subject of Boolean algebra, independently of how they balanced syntax (the laws of Boolean algebra) and semantics (the models of those laws).
In Introduction to Boolean algebra, there is footnote referring to Halmos for having expressed that "Much of the subject can therefore be introduced without reference to any values besides 0 and 1". Can the reference be made more precise?
- From the preface to the revised version of Halmos's Lectures (recently completed posthumously by Steven Givant---the reference should be updated to reflect this):
- "Outside the realm of mathematics, Boolean algebra has found applications in such diverse areas as anthropology, biology, chemistry, ecology, economics, sociology, and especially computer science and philosophy. For example, in computer science, Boolean algebra is used in electronic circuit design (gating networks), programming languages, databases, and complexity theory."
- With the exception of the few philosophers who work explicitly with Boolean algebras as structures in connection with foundations of mathematics, the few database theorists who have used cylindric algebras, and the heavily algebraic direction taken by some recent work on the constraint satisfaction problem, pretty much all applications in those areas limit themselves to the two-valued model. (I myself applied Boolean algebra to digital hardware, circuit complexity, automated theorem proving, and program verification for over a decade without once encountering or needing the concept of a Boolean algebra having more than two values; the need did not arise until I started using algebraic instead of syntactic methods to simplify proofs of completeness for axiomatizations of program logics, which generated puzzled looks from my colleagues familiar only with the two-element Boolean algebra.) Outside mathematics, almost all users of Boolean algebra understand it intuitively as the algebra of two values, and work with it formally as such.
- Furthermore this intuition has a formal basis, unique to Boolean algebra among commonly encountered algebraic classes, in the theorem that every Boolean algebra is isomorphic to a field of sets, equivalently to a set of bit vectors closed under bitwise AND and NOT. Informally, in each bit position one finds an independently operating copy of the two-element Boolean algebra; formally, every Boolean algebra is isomorphic to a subalgebra (S) of a direct product (P) of copies of the two-element algebra, i.e. SP(2) generates the whole variety when ordinarily HSP (H for "homomorphic image" adds closure under quotients) is needed. Boolean algebra is special in that regard: closely related subjects such as commutative algebra (commutative rings), relation algebra (the De Morgan-Peirce-Schroeder-Tarski-Jonsson extension of Boolean algebra as an algebra of unary relations to accommodate binary relations), and Heyting algebra (the intuitionistic counterpart of Boolean algebra) all require HSP rather than SP to generate their respective varieties from finitely many examples. In particular intuitionistic logic cannot be understood as the logic of n values for any finite n. Whatever Trovatore had in mind with his analogy with manifolds was surely not that. --Vaughan Pratt (talk) 20:12, 11 March 2011 (UTC)
To Paul August: I didn't understand neither Vaughan nor Trovatore considering Boolean algebra being an equivalent for Boolean algebras of what group theory and field theory are for groups and fields respectively but rather as the equivalent for Boolean algebras of what elementary algebra is to rings or fields, i.e. as the equational reasoning in Boolean algebras (might Vaughan Pratt and Trovatore correct me if my understanding is wrong). Hugo Herbelin (talk) 13:45, 11 March 2011 (UTC)
- Well certainly Trovatore wasn't saying that Boolean algebra is to Boolean algebras as group theory is to groups, rather he seems to be denying that, to wit: "Boolean algebra as a mass noun is not really the study of Boolean algebras." Paul August ☎ 14:41, 11 March 2011 (UTC)
- My sentence was probably not clear. I meant the same as you regarding Trovatore: My understanding of what Vaughan and Trovatore are saying was that they both do not consider Boolean algebra to be an equivalent for Boolean algebras of what group theory and field theory are for groups and fields respectively. I understand that they rather see them both as the equivalent for Boolean algebras of what elementary algebra is to rings or fields, i.e. as the equational reasoning in Boolean algebras. In the case of Vaughan, I actually maybe overinterpreted his viewpoint and I recognize that it is more a feeling obtained from the reading of the articles he started and from his highlighting of expressions such as "its general methods, if not always its specific operations and laws, ...", "about values in some domain", "equations" than an explicit affirmation from him. Actually, the best thing is probably that he say himself if he recognizes himself into "Boolean algebra is the elementary algebra of Boolean algebras". Hugo Herbelin (talk) 17:03, 11 March 2011 (UTC)
- In the spirit of making the subject as accessible as possible without losing rigor, I would say that Boolean algebra is the algebra of two values, call them 0 and 1 for definiteness. Its operations are the finitary operations on the set {0,1}; for convenience one picks finitely many of these, e.g. AND-OR-NOT-0 (the lattice basis) or AND-XOR-1 (the ring basis), and obtains the remainder by composition. (It is a theorem that every finitary operation on {0,1}, meaning a function from {0,1}n to {0,1} for some n ≥ 0, can be obtained from either of these bases.) Its laws are the valid or identically true equations between terms built from variables using the operations. Its models are those algebraic structures equipped with operations that satisfy those laws, called Boolean algebras.
- There are many equivalent ways of presenting this subject, some starting from (finitely many of) the laws expressed in terms of (finitely many of) the operations, some from (finitely many of) the models. All of these presentations are of the same subject, Boolean algebra, and it is a nice question as to which starting point is best. However the idea that the subject of Boolean algebra excludes its models is no more natural than considering the subject of commutative algebra to exclude commutative rings or the subject of relation algebra to exclude relation algebras. Personally I'm interested in all aspects of Boolean algebra, especially its proof theory, its computational complexity, and Stone duality, but I would guess more than 90% of the many users of Boolean algebra outside mathematics would be better served by the material in sections 1 to 4 of Introduction to Boolean algebra, since they are unlikely to ever need an infinite Boolean algebra, with most being content with the two-element one. --Vaughan Pratt (talk) 21:37, 11 March 2011 (UTC)
- And I would add that Donald Monk agrees with me on the above in his opening "Boolean algebra is the algebra of two-valued logic" in his SEP article on Boolean algebra. --Vaughan Pratt (talk) 06:25, 13 March 2011 (UTC)
- I see nothing controversial in the claim that Boolean algebra (mass noun) is the algebra of two-valued logic. I might have said the same thing. I don't see how that relates to the question of ambiguity. I'm quite certain that Monk would not say that a Boolean algebra is the algebra of two-valued logic; that just doesn't make sense. --Trovatore (talk) 06:39, 13 March 2011 (UTC)
- I'm quite certain of that too. So given that we're in agreement on this, can I finally, pretty please, etc. etc. etc., move Introduction to Boolean algebra to Boolean algebra? This would be an enormous relief for me given the amount of time I've put into writing these articles and the amount of time you've put into blocking them, not to mention blocking other articles by me.
- When it reaches the point that more than 50% of my time is spent on fighting people who fight my many many contributions to Wikipedia, I will retire from attempting to improve Wikipedia. This encyclopedia is getting bogged down by having more protesters than contributors! If the protesters knew half as much as the contributors this would be understandable but they never do, they just seem to protest from force of habit. Neo-Luddism will be the death of Wikipedia. --Vaughan Pratt (talk) 07:19, 13 March 2011 (UTC)
- What? No, I don't agree with that at all. We agree on what the mass-noun sense means, more or less, but Boolean algebra is still ambiguous with the count-noun sense. It is still my position that Boolean algebra should be a disambig page. --Trovatore (talk) 07:32, 13 March 2011 (UTC)
- I see nothing controversial in the claim that Boolean algebra (mass noun) is the algebra of two-valued logic. I might have said the same thing. I don't see how that relates to the question of ambiguity. I'm quite certain that Monk would not say that a Boolean algebra is the algebra of two-valued logic; that just doesn't make sense. --Trovatore (talk) 06:39, 13 March 2011 (UTC)
- My sentence was probably not clear. I meant the same as you regarding Trovatore: My understanding of what Vaughan and Trovatore are saying was that they both do not consider Boolean algebra to be an equivalent for Boolean algebras of what group theory and field theory are for groups and fields respectively. I understand that they rather see them both as the equivalent for Boolean algebras of what elementary algebra is to rings or fields, i.e. as the equational reasoning in Boolean algebras. In the case of Vaughan, I actually maybe overinterpreted his viewpoint and I recognize that it is more a feeling obtained from the reading of the articles he started and from his highlighting of expressions such as "its general methods, if not always its specific operations and laws, ...", "about values in some domain", "equations" than an explicit affirmation from him. Actually, the best thing is probably that he say himself if he recognizes himself into "Boolean algebra is the elementary algebra of Boolean algebras". Hugo Herbelin (talk) 17:03, 11 March 2011 (UTC)
- Ok, so no change from our regular holdout Trovatore on that point. (Why do you do this, Trovatore?) Who else besides Trovatore feels that the subject of Boolean algebra is so ambiguous that it needs a dab page instead of simply an article explaining what Boolean algebra is all about? Is group theory ambiguous? What about commutative algebra or relation algebra, or ring theory, or linear algebra, are they so ambiguous they need dab pages? What is so special about Boolean algebra that makes it any different from all these other subjects? I don't see anything, do you? (We know Trovatore's answer already. It would be nice if Trovatore would write an article for a change instead of simply blocking progress.) --Vaughan Pratt (talk) 07:59, 13 March 2011 (UTC)
- I find that characterization rather offensive. I am not "blocking progress". I don't think your proposed change is progress. Of course none of group theory, ring theory, or linear algebra are ambiguous; none of them has a count-noun sense and therefore none of them is parallel. Relation algebra might be parallel but I don't really know anything about it so I'll stay out of that one. --Trovatore (talk) 08:08, 13 March 2011 (UTC)
- Well, since I was offended by your "You've obviously never worked with the gadget", can we call it quits? (You don't seem to understand the "gadget" terribly well yourself.) Since besides relation algebra you left out commutative algebra does this mean you don't really know anything about that either? Basically it seems we're down to your statement I don't think your proposed change is progress which so far you haven't supported terribly well, instead displaying your complete ignorance of SP and HSP and your limited grasp of P(omega)/Fin. I wouldn't criticize in this way were you not standing so resolutely in the path of a huge amount of work on my part, thereby wasting the huge number of man-hours I've invested in this project so far. --Vaughan Pratt (talk) 08:32, 13 March 2011 (UTC)
- Vaughan, the point is terribly simple. Boolean algebra has two main senses, one being a mass noun and one being a count noun. I think they are of sufficiently comparable importance that neither should be "primary topic". All this other stuff is noise. --Trovatore (talk) 08:37, 13 March 2011 (UTC)
- (I note as an aside that, when I first arrived on the scene, the count noun was the subject of the article. If I recall correctly, I was the one who argued for the disambig page, giving the mass-noun sense equal status. I still think that's correct, but I'm against going to the other extreme by preferring the mass noun over the count noun.) --Trovatore (talk) 08:42, 13 March 2011 (UTC)
- For what it's worth, I apologize for the "never worked with" remark. I still find it difficult to believe that you can seriously maintain that it's easier to work with the Stone representation than the simple representatives, given that you have, but as I say that's just noise and (interesting as it is) doesn't bear on the point here. --Trovatore (talk) 08:55, 13 March 2011 (UTC)
- Apology accepted and I withdraw my counterfire. I can appreciate your difficulty since the duality mirror is not easy to pass through---I recall having a hard time with Albert Meyer in 1979 about this. Albert seemed to view first order logic and propositional calculus as unrelated subjects and I wasn't much help back then in explaining the connection even though it seemed perfectly obvious to me.
- It's too bad they didn't call vector spaces linear algebras. They do talk about commutative algebras and relation algebras and Boolean algebras though, so at least we have those to refer to as count nouns. As far as I'm concerned the subject of commutative algebra includes commutative algebras, and the subject of relation algebra includes relation algebras, and the subject of Boolean algebra includes Boolean algebras. I can see a point in having a dab page for "Drill" as a tool for drilling holes vs. "Drill" as a kind of canvas, and "Count" (and "Countess") as a society rank vs. "count" as a numerical concept, and "Straw" as dried hay vs "straw" as something to drink through, but I'm really sorry that I'm unable to see any point in having a dab page for "relation algebra" as a mass noun vs a count noun, or likewise for "commutative algebra" or "Boolean algebra." What kind of ambiguity is that? --Vaughan Pratt (talk) 09:20, 13 March 2011 (UTC)
- It is a linguistic ambiguity. You keep drawing in all this mathematics, and interesting as it is, it's beside the point, because it's a natural-language ambiguity that I'm focusing on rather than a mathematical one.
- A Boolean algebra is not Boolean algebra. I don't mind if Boolean algebras are treated somewhere in the mass-noun article, presumably rather late in the article. But I think there should be a stand-alone article on the object, and I think that topic is important enough to share equal billing with the mass-noun sense, even if the latter at some point mentions the object. --Trovatore (talk) 09:33, 13 March 2011 (UTC)
- For whatever my opinion may be worth, I find myself agreeing with Trovatore that, while there are several ways we might skin this cat, having Boolean algebra be a dab page seems the most appropriate. And I apologize if I'm being dense, but I don't really understand how doing that interferes in any way with the work done by Vaughan Pratt. Paul August ☎ 18:46, 13 March 2011 (UTC)
- Thanks, Paul. Right, I hope I didn't give the impression I didn't think Vaughan's "Introduction" article is valuable. I think there should be one article on the mass-noun sense, and Vaughan's "Intro" article is probably the one the other stuff should be merged into. (I would also be OK with two mass-noun articles, one at a more introductory level than the other, but that would be second choice.) --Trovatore (talk) 19:03, 13 March 2011 (UTC)
- For whatever my opinion may be worth, I find myself agreeing with Trovatore that, while there are several ways we might skin this cat, having Boolean algebra be a dab page seems the most appropriate. And I apologize if I'm being dense, but I don't really understand how doing that interferes in any way with the work done by Vaughan Pratt. Paul August ☎ 18:46, 13 March 2011 (UTC)
- Vaughan, the point is terribly simple. Boolean algebra has two main senses, one being a mass noun and one being a count noun. I think they are of sufficiently comparable importance that neither should be "primary topic". All this other stuff is noise. --Trovatore (talk) 08:37, 13 March 2011 (UTC)
- Well, since I was offended by your "You've obviously never worked with the gadget", can we call it quits? (You don't seem to understand the "gadget" terribly well yourself.) Since besides relation algebra you left out commutative algebra does this mean you don't really know anything about that either? Basically it seems we're down to your statement I don't think your proposed change is progress which so far you haven't supported terribly well, instead displaying your complete ignorance of SP and HSP and your limited grasp of P(omega)/Fin. I wouldn't criticize in this way were you not standing so resolutely in the path of a huge amount of work on my part, thereby wasting the huge number of man-hours I've invested in this project so far. --Vaughan Pratt (talk) 08:32, 13 March 2011 (UTC)
- I find that characterization rather offensive. I am not "blocking progress". I don't think your proposed change is progress. Of course none of group theory, ring theory, or linear algebra are ambiguous; none of them has a count-noun sense and therefore none of them is parallel. Relation algebra might be parallel but I don't really know anything about it so I'll stay out of that one. --Trovatore (talk) 08:08, 13 March 2011 (UTC)
- As Vaughan Pratt asks the opinion of others, I have to say that I'm on the same line as Trovatore regarding the two following points:
- Stone's representation theorem does not justify to define Boolean algebras as subalgebras of a direct product of the two-element Boolean algebra.
- The case is even worth than for geometry where probably few people, and at least not WP, would think about renouncing to define geometry from axioms (even among computer scientists as some algorithms are better dealt by algebraic means than with Cartesian coordinates).
- The case here is worth than in geometry because the representation theorem is far from a trivial construction, it assumes (a weak form) of the axiom choice, meaning in particular that the algebra has to be well-ordered (to construct an ultrafilter) and in particular that its representation will depend on the exact order chosen. Even though it is unique up to isomorphic, I would bet that there is one different Stone construction for each different ultrafilter (I'm not a specialist of the representation theorem and I base by bet on the fact that this is what happens in Gödel's completeness theorem: the model built depends on the exact ordering of formulas chosen).
- In short, my position is clear: Stone's representation is a wonderful theorem, and a source of different intuitions about Boolean algebras. But the study of Boolean algebras can in no way be reduced to what Vaughan calls SP(2).
- Moreover, in all sources cited by Vaughan, I could not see one adopting a so drastic approach in presenting Boolean algebras.
- The current version of Introduction to Boolean algebra is not a fair account of Boolean algebras with this respect (i.e. it reduces Boolean algebra to Boolean algebra of the two-element Boolean algebra, what makes it de facto a different topic than the one of Boolean algebras). — Preceding unsigned comment added by Hugo Herbelin (talk • contribs) 19:53, 13 March 2011 (UTC)
- Hugo, if you see any sentence in Introduction to Boolean algebra that could be considered objectionable by your criteria I'd appreciate your pointing it out so I can fix it. As far as I know every mathematical statement in the article is correct. (But you're right that the section on representability should mention the need for Choice in the theorem there, which I will fix.)
- Nowhere does the article suggest defining a Boolean algebra to be a field of sets. The first paragraph of the section on Laws says "Such purposes [for the laws] include the definition of a Boolean algebra as any model of the Boolean laws." And the section on Boolean algebras begins with "Whereas the foregoing has addressed the subject of Boolean algebra including its laws, this section deals with mathematical objects called Boolean algebras as the algebraic structures satisfying those laws" and then goes on to give various examples of Boolean algebras in order to get people used to seeing Boolean algebras bigger than 2 before giving the general abstract definition. (Many digital designers wanting to learn about Boolean algebras are likely to be unfamiliar with the concept of an abstractly defined algebraic structure, justifying a gentler approach than one might take with someone who had studied group theory.) Furthermore there are many axiomatic definitions of Boolean algebra, which the article devotes a separate section to.
- The article does not justify {0,1} as the prototypical Boolean algebra in terms of representability of Boolean algebra but in terms of the laws of Boolean algebra, which are exactly those satisfied by the two-element algebra. It also occupies a canonical position among Boolean algebras as the initial Boolean algebra (though I considered that too advanced for this article, leaving it for Boolean algebras canonically defined#Boolean homomorphisms). (The ring of integers is likewise the canonical commutative ring for the same reason, initiality; however one might not want to call it prototypical because unlike the situation with Boolean algebras other than the one-element one there exist commutative rings of any desired cardinality satisfying equations that do not hold of the initial commutative ring, e.g. Zn for any n.) Also {0,1} is the only set such that the n-ary operations on it are precisely the Boolean operations---there are 16 binary operations on {0,1}, namely the 16 binary Boolean operations, whereas there are 19,683 binary operations on {0,1,2} (but that was another fact I decided to leave to Boolean algebras canonically defined). --Vaughan Pratt (talk) 21:26, 13 March 2011 (UTC)
- Forgot to mention Donald Monk's opening in his SEP article: "Boolean algebra is the algebra of two-valued logic." Monk has been working in the area for the 50 years since getting his Ph.D. in 1961 under Alfred Tarski, is the editor of "Handbook of Boolean Algebra," and continues to attend conferences on the subject (he attended BLAST'2010 in Boulder for example, where the B in BLAST stands for Boolean algebra. --Vaughan Pratt (talk) 21:33, 13 March 2011 (UTC)
- Thanks for stepping in here, Paul and Hugo, I was hoping someone else besides us two would say something. Regarding dab pages, WP:DAB describes three scenarios for handling ambiguity: (i) a dab page, (ii) a primary topic with a hatnote to a dab page, and (iii) a primary topic with a hatnote to the one other meaning in which case WP:DAB says no dab page is needed. It then gives two sections worth of guidelines on how to decide which of these to use. I would be interested to hear your interpretation of how these guidelines apply in the present case, taking into account that "Boolean algebra" is a broadly based subject with several aspects including its values (i.e. the elements of a Boolean algebra), its operations, its laws, its models (Boolean algebras), its axiomatization, and its relevance to propositional logic (and perhaps also its complexity: length of proofs of Boolean theorems, size of Boolean formulas and Boolean circuits, time required to test satisfiability of Boolean formulas, etc.). Bear in mind that a dab page adds the burden of going through an intermediary page to get to the main article, which is the only reason I'm aware of that WP:DAB offers options (ii) and (iii). --Vaughan Pratt (talk) 20:14, 13 March 2011 (UTC)
- In my view there are (at least) two different (though related) things to which the term "Boolean algebra" might refer and neither of these is, quoting from WP:DAB, "much more likely than any other, and more likely than all the others combined—to be the subject being sought when a reader enters that ambiguous term in the Search box" and thus neither ought to be the primary topic. Paul August ☎ 21:14, 13 March 2011 (UTC)
- Another guideline is "Where the primary topic of a term is a general topic that can be divided into subtopics ... the unqualified title should contain an article about the general topic rather than a disambiguation page." The values, operations, laws, and models of Boolean algebra are all subtopics of the general topic of Boolean algebra. Are you proposing that the models of Boolean algebra are not a subtopic of the topic of Boolean algebra? --Vaughan Pratt (talk) 21:46, 13 March 2011 (UTC)
- My claim (not speaking for Paul) is that Boolean algebra (mass noun) is not the primary topic. Therefore that clause does not apply at all. As I've said before, the models are not part of "Boolean algebra" (mass noun) as I use the term, but I recognize that some others use it differently, even if I wish they wouldn't. But even if the mass noun article is to treat the models, it still doesn't change anything unless the mass noun should be the primary topic in the first place. --Trovatore (talk) 21:52, 13 March 2011 (UTC)
- Another guideline is "Where the primary topic of a term is a general topic that can be divided into subtopics ... the unqualified title should contain an article about the general topic rather than a disambiguation page." The values, operations, laws, and models of Boolean algebra are all subtopics of the general topic of Boolean algebra. Are you proposing that the models of Boolean algebra are not a subtopic of the topic of Boolean algebra? --Vaughan Pratt (talk) 21:46, 13 March 2011 (UTC)
- Trovatore, this debate between you and me on the question of whether "Boolean algebra" is a subject in its own right with various aspects, or needs a dab page, has been ongoing for at least three years. I quit fighting you on this back then when it became clear you were unwilling to compromise in any way on this question, and turned my attention to questions where I was more likely to be able to make worthwhile progress.
- My position on this has always been that the subject of Boolean algebra has a number of aspects including its values, its operations, its laws, its models, its axiomatizations, its complexity, and so on. According to WP:DAB such a subject with multiple aspects should be an article rather than a dab page.
- Your research on the other hand has focused so single-mindedly on the models of Boolean algebra, one of the several aspects of this subject, that you've become convinced that it's the only nontrivial part of the subject. This brings to mind Caligula's argument that he had so distanced himself from ordinary Romans as to have become a god.
- One counterargument would be that the first of the seven Millennium Prize Problems is the P versus NP problem. The official statement of the problem was given by Stephen Cook, namely as to whether the Boolean satisfiability problem can be solved in polynomial time. This is an aspect of the general subject of Boolean algebra when construed more broadly than you have been willing to do up to this point.
- Another counterargument would be that the models of Boolean algebra have no nontrivial finite models. In contrast finite groups, and more generally finite model theory, are very interesting subjects. What is interesting about finite Boolean algebras?
- Third counterargument: does "Boolean algebra" as you prefer to think of this subject have an open problem that any serious mathematician alive today has any interest in that is as remotely interesting as the Millennium Prize Problems? --Vaughan Pratt (talk) 06:54, 19 March 2011 (UTC)
- In my view there are (at least) two different (though related) things to which the term "Boolean algebra" might refer and neither of these is, quoting from WP:DAB, "much more likely than any other, and more likely than all the others combined—to be the subject being sought when a reader enters that ambiguous term in the Search box" and thus neither ought to be the primary topic. Paul August ☎ 21:14, 13 March 2011 (UTC)
Some thoughts about a main page
At some time, a need had emerged to have an article that covers all aspects of Boolean algebra (mass noun) and introduction to Boolean algebra was such an attempt.
However, looking at introduction to Boolean algebra, I had the impression that it was more like a superposition of contents about, first the calculus approach of Boolean algebra, then the structure approach of Boolean algebra, than a unified view of Boolean algebra: Sections 1 to 4 are about the calculus; then, abruptly, from Section 5, the perspective changes, the term "algebra" is taken in its count noun sense and the article starts to be about the structure; finally, in Section 8, the article is back on applications of the calculus.
At some time, I thought that this was inherent to the subject, i.e. that the two approaches (the calculus/finitary one and the structure/not-necessarily-finitary one) were two independent fields having their own problematics and methods and that it was illusory, even if they were talking about the very same equational theory of Boolean algebra, to unify them in a common article.
After some further thought, I started to imagine that finally, it might be possible to consider Boolean algebra as applicable to all Boolean algebras and not only to the finitary ones, as the current articles suggest it is.
So, remembering the wish of StuRat to have a "general audience" introductory page to Boolean algebra (which, based on the content of StuRat's own article, was actually not excluding infinite Boolean algebras), I decided to write a very short article giving excerpts of the main ideas about Boolean algebra while taking benefit of the hypertextual structure of WP do delegate as much as possible technical contents to more detailed pages. I put this proposal at User:Hugo Herbelin/BA.
This proposal has of course not a content as detailed as Boolean algebra (logic) and Introduction to Boolean algebra have, but my objective is nevertheless that it conveys the very same basic ideas while limiting as much as possible personal views.
On the other side, by keeping the article short and easy to read, I hope to be in the right direction to answer StuRat's general audience requirement, but without the naive "clumsiness" of his own attempt.
At the same time, I tried to write the lead so that the page could serve as a disambiguation page if ever. Please Trovatore let me know if this approach would be ok to you.
My background is proof theory and programming languages and I have no claim to be a specialist of Boolean algebra(s) and no claim either to have the most adequate overview of all what connects to Boolean algebra. So I'm ready to hear any comments from both experts and less experts on: Whether going in this direction (i.e. towards a main page short but yet large spectrum, general audience, and not committing to a point of view) is worth to be continued, and if yes, how to improve in this direction?
Note that I'm not an English native speaker and I'm afraid that some sentences are not turned as smoothly as an English native speaker would do. There is "Meta" section ready to add comments. Note also that the plan is to add figures (truth table, logic gates, Venn diagrams) but this remains to be done. Hugo Herbelin (talk) 23:31, 13 March 2011 (UTC)
Hugo, since you're writing what is largely an article from an historical perspective, some remarks on the history would be in order. (Since they're a bit long I've used a bar in lieu of indenting.)
1. The 1848 paper of Boole that you cite gives the axioms not for a complemented distributive lattice as you state but for a Boolean ring (law (3), xn = x). Boole defines logical negation as 1 - x rather than as complement (y is a complement of x when x∨y = 1 and x∧y = 0) though fails to notice that one consequence of (3) is that subtraction becomes the same operation as addition making x + 1 an equally good definition of logical negation. This in turn would have shown him that x + x = 0. At the end of the first section he expresses XOR as x(1 - y) + y(1 - x) which he could have expanded to x + y - (xy + xy), which with the further knowledge that x + x = 0 would have told him that XOR was simply addition in his system.
2. Disjunction does not appear in any form in Boole's 1848 paper, but it does appear in Chapter IV-6 of his 1854 book An Investigation of the Laws of Thought in the form xy + x(1-y) + y(1-x) (which he does not bother to simplify to the more natural x + y - xy that we would write it as today, or x + y + xy if we dispense with the redundant subtraction symbol). However he does not propose any symbol for disjunction, leaving the concept in the form xy + x(1-y) + y(1-x). The earliest mathematical notation for disjunction I'm aware of is De Morgan's (A,B), with AB denoting conjunction, in his 1858 paper "On the Syllogism: III." (The symbol ∨ is due to Russell half a century later.) De Morgan has no symbol for negation but instead implicitly exploits what we now call De Morgan duality to push negations down to the literals, using upper and lower case for respectively positive and negative literals. Like Boole, De Morgan has no notion of tautology as an identically true proposition and hence no concept of completeness. De Morgan's "On the Syllogism: IV" extends this framework to relation algebra, with his "Theorem K" amounting to what we would consider residuation today.
3. The axioms for a complemented distributive lattice that you give came later with the lattice-based approach (begun by De Morgan in 1858 but lacking complement as an operation per se) developed by Peirce, Schroeder, Peano, Jevons, etc. The completeness of that axiomatization was first (to my knowledge) proved by Emil Post in 1921. Completeness of Boole's axioms was first proved (at least implicitly) by Ivan Zhegalkin in 1927, who was the first to realize that the law x2 = x was sufficient on its own to define Boolean algebra in Boole's setting of commutative rings (not that Boole had the explicit concept of a ring but those were the axioms Boole was assuming).
4. What Boole did observe, in Chapter II-15 of his 1854 book, was that the law x2 = x admitted 0 and 1 as its only solutions, and wrote "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." Which would have panned out beautifully had only he realized that the correct "difference of interpretation" made subtraction the same operation as addition. (Ironic given that he certainly knew about arithmetic mod 2, it just didn't occur to him to use it.) Instead, in the last footnote of Chapter III, he says "[1 + x] is not interpretable, because we cannot conceive of the addition of any class x to the universe 1." On that basis he then abandons the law x3 = x that he'd accepted earlier in his 1848 paper on the ground that, when written as x(1 - x)(1 + x) = 0, it "admits of no interpretation analogous to that of the equation x2 = x." The existence of supposedly meaningless terms in his language then created a barrier to defining the concept of the set of all tautologies, since he lacked a way of identifying the meaningful terms. It is clear from all this that although addition had to be interpreted differently from integer addition, as Boole states explicitly, it did not occur to him that the appropriate interpretation was as addition mod 2. The mystery of how to interpret Boole's system consistently was (to my knowledge) only sorted out 63 years later by Zhegalkin, and independently in the West (communication with Russia being almost nonexistent in those days) a further 9 years later by Marshall Stone. By that time the complemented distributive lattice axiomatization of Peirce et al had become thoroughly entrenched as the definitive framework for Boolean algebra, as faithfully reflected in your account of Boolean algebra, which is a bit old-fashioned by modern standards. --Vaughan Pratt (talk) 17:24, 14 March 2011 (UTC)
- That's very interesting. From reading through the paragraphs of The Calculus of Logic, it became clear that the system I credited to Boole was not his word but finding more references (on the web) was difficult (I did not go further than Michael Schroeder's brief history). I now edited User:Hugo Herbelin/BA and removed the direct credit to Boole.
- Somehow, the purpose of my proposal is not a priori to be historical. If some history bits could be given, that would be perfect, but the point is certainly not to provide with an exhaustive historical account (what could be on another hand the purpose of a very interesting dedicated article).
- I don't know if I have to comment on the struk out "a bit old-fashioned by modern standards" but I would certainly be delighted to know more about what you mean. Hugo Herbelin (talk) 20:04, 14 March 2011 (UTC)
- I guess it reflects my background, where the emphasis has always been on satisfiability, since tautologies/identities can be obtained simply as the negations of the unsatisfiable Boolean terms/equations. But even the theorems of Boolean algebra are naturally understood semantically as the identically true equations, without worrying too much about which axiom system they might have come from if any. For those familiar with these concepts, Boolean algebras can be defined in a single sentence, namely as the models of the Boolean identities.
- The reason I struck the last remark out was because even today people continue to define them as either complemented distributive lattices or Boolean rings, the existence of the simple identity-based definition notwithstanding. Furthermore each such definition furnishes useful insights. For example Stone duality extends to distributive lattices, with complementedness corresponding to the dual Priestley space having the discrete partial order, i.e. a T1 (and hence T2) space. From this we obtain an easily described method for canonically extending a distributive lattice L to a Boolean algebra B: dualize L to S, form S' from S by stripping off the partial order, which creates a map f: S' --> S, and dualize back carrying S back to L, S' to B, and f to the desired embedding of L in B (by duality). This sort of thing shows the benefit of having multiple definitions each serving different purposes. --Vaughan Pratt (talk) 23:46, 14 March 2011 (UTC)
- Thanks, I think I understand better and better your view. This gives some hints on how to rename Boolean algebras canonically defined so that it smoothlier integrate to the global picture (maybe calling it "Boolean algebra (Boolean functions model)" or something like that so as to give a better immediate feeling of what it is about). What do you think? --Hugo Herbelin (talk) 11:15, 16 March 2011 (UTC)
- (Sorry, I had to attend to other business for a few days.) I fully agree, and would like to integrate some aspects of the "canonically defined" article into the structures article. (My one-axiom-schema axiomatization A1+(R1..R3) is too far out of "left field" to qualify for that, and in any event is irrelevant to the structures.) --Vaughan Pratt (talk) 07:20, 19 March 2011 (UTC)
- I think the "canonically" article should probably be merged into the "structure" article, because it's really about the structures. I think it should be shortened quite a bit in the process, though. Vaughan seems to care a great deal about the definition of the things. Personally I don't think that's such a terribly interesting aspect of them. I'm more interested in their, well, model theory I guess you'd say. From that standpoint the two-element B.a. is not so very fundamental, because its model-theoretic aspects are trivial. --Trovatore (talk) 18:44, 16 March 2011 (UTC)
- Regarding triviality, why are you singling out the two-element BA? Isn't every power set algebra a trivial Boolean algebra? The only interesting Boolean algebras from a model theoretic standpoint are those that are not isomorphic to a power set algebra. --Vaughan Pratt (talk) 07:20, 19 March 2011 (UTC)
- I singled it out because you did. I agree that all powerset algebras are trivial as BAs. --08:44, 19 March 2011 (UTC)
- Regarding triviality, why are you singling out the two-element BA? Isn't every power set algebra a trivial Boolean algebra? The only interesting Boolean algebras from a model theoretic standpoint are those that are not isomorphic to a power set algebra. --Vaughan Pratt (talk) 07:20, 19 March 2011 (UTC)
- Merging the "canonically" article into the "structure" article would certainly be the most reasonable thing to do from the point of view of organizing the B.a. pages into an intelligible structure, but the way the canonical article is written makes it almost impossible to do it just right now. Currently, the canonical article looks more like a textbook article than like an encyclopedic article in the sense that it redefines and explains almost everything it is using instead of relying on the corresponding appropriate pages of WP. Let's just consider the first sentences:
- Just as group theory deals with groups, and linear algebra with vector spaces: this is more or less the first things one learns by clicking at abstract algebra.
- Common to Boolean algebras, groups, and vector spaces is the notion of an algebraic structure, a set closed under zero or more operations satisfying certain equations: idem, this is known from the article algebraic structures via the page abstract algebra that those readers who didn't know what abstract algebra is had already clicked on.
- Just as there are basic examples of groups, such as the group Z of integers and the permutation group Sn of permutations of n objects, there are also basic examples of Boolean algebra such as the following...: idem, the only sentence relevant to Boolean algebras here is The basic examples of Boolean algebras are....
- Actually, the more I'm thinking about the article, the more I'm thinking that a better place for it would be on Wikibooks as a Boolean functions model-minded introduction to Boolean algebras. Vaughan, what do you think? --Hugo Herbelin (talk) 22:07, 17 March 2011 (UTC) (slightly revised at 23:38 (UTC))
- On the other side, if one tries to extract from the "canonically" article the exact contents about the structure that is not in the "structure" article, this contents is so rich, especially regarding the list of examples, that it would make the example section in "structure" almost the size of a stand-alone article. So maybe, first thing to do is to create an "Examples of Boolean algebras" article (in the style of Examples of groups) that collects the various examples to be already found in the different B.a. pages? --Hugo Herbelin (talk) 23:38, 17 March 2011 (UTC)
- Agreed. This would be very reasonable to do, and I would have no objection if someone wanted to tease out the structure-relevant parts of "canonically defined" and incorporate them into some other article. I would do so myself except that currently I have several projects people have been bugging me to complete, so I have to prioritize all this accordingly. --Vaughan Pratt (talk) 07:20, 19 March 2011 (UTC)
- Thanks, I think I understand better and better your view. This gives some hints on how to rename Boolean algebras canonically defined so that it smoothlier integrate to the global picture (maybe calling it "Boolean algebra (Boolean functions model)" or something like that so as to give a better immediate feeling of what it is about). What do you think? --Hugo Herbelin (talk) 11:15, 16 March 2011 (UTC)
- Incidentally thanks very much for the pointer to Michael Schroeder's article, which I hadn't seen before. While I knew about both De Morgan's and Boole's technical backgrounds I did not know their family backgrounds, which were fascinating. Schroeder's analysis of Boole's system is spot on except in one small detail just before the conclusion: he claims that x+x=0 --> x=0 holds in a Boolean ring but this is clearly false since x+x=0 for all x including x=1. --Vaughan Pratt (talk) 00:43, 15 March 2011 (UTC)
- Indeed, you're perfectly right. --Hugo Herbelin (talk) 11:15, 16 March 2011 (UTC)