Talk:Boolean algebra (structure)/Archive 3

DO NOT EDIT OR POST REPLIES TO THIS PAGE. THIS PAGE IS AN ARCHIVE.

This archive page covers approximately the dates from 13 June onwards.

Post replies to the main talk page, copying or summarizing the section you are replying to if necessary.

This archive is still active: please archive further talk page messages at the bottom of this page. When the page is full, please start a new archive and replace this message.

Revisiting naming

This was a hot issue in the past and seems to have cooled off a bit, so maybe it's time to look at it again in a more dispassionate way.

Background: There are two much-used senses of the phrase "Boolean algebra". In the sense used in the current Boolean algebra article, "Boolean algebra" is a count noun; a Boolean algebra is an algebraic structure of a certain kind. In this sense, "Boolean algebra" must always appear either with a determiner -- this Boolean algebra, some Boolean algebra, etc., or in the plural (Boolean algebras); there is no such thing as just Boolean algebra.

The older, and likely more common, use of "Boolean algebra" is as a mass noun, and refers to the collection of techniques used to manipulate algebraic expressions capable of representing propositions. It's somewhat unclear how this sense of the term is distinguished from the propositional calculus, but anyway we do make the distinction, whatever it is, and the article on this sense is currently at Boolean logic. The criteria for what is included in the latter article have never been clearly stated.

So, what's the problem? Basically, the problem is that users thinking of either sense have a reasonable expectation that Boolean algebra will go where they want it to. So, for example, every so often I have to revert an interwiki bot that has added a link to simple:Boolean algebra, which discusses what we're calling Boolean logic. And I just had to edit the George Boole article, where it says that he invented Boolean algebra, which of course he did, but the link needs to go to Boolean logic -- I don't think Boole would have recognized the notion of a Boolean algebra. And isn't it a bit strange, for a user clicking on that link, to see the title Boolean logic on the destination article?

As I say, I don't believe either meaning is primary. The mass-noun meaning is more used, but editors thinking of the count-noun meaning also have a reasonable expectation that a link should go somewhere sensible.

So my proposal is that Boolean algebra itself should be a disambig page. The count-noun sense should be moved to one of the ones we've discussed -- either Boolean algebra (algebraic structure), Boolean algebra (mathematical structure), or Boolean algebra (object). I think I like the last one best, because it generalizes (e.g. we could write a topology (object) article to fix another vexing ambiguity) but only slightly; this seems like a reasonable subject for a vote, given that it mostly comes down to aesthetic preference.

As for Boolean logic, it should be moved somewhere that has "Boolean algebra" in the title. Possibilities are Boolean algebra (logic) or Boolean algebra (logical calculus). --Trovatore 23:23, 13 June 2007 (UTC)

This makes sense to me and I have looked at some of the earlier discussions. I think Boolean algebra (logic) may be the obvious choice for the mass-noun sense, whereas there appears to be less consensus about the count noun sense: I would suggest Boolean algebra (lattice theory) (referring to the field in a standard way). Geometry guy 23:51, 13 June 2007 (UTC)

Hm, I sure wouldn't vote for the "lattice theory" option; I don't think of myself as doing lattice theory when working with Boolean algebras. I'd say it's overly specific, which is why I prefer the least specific option, Boolean algebra (object). --Trovatore 00:54, 14 June 2007 (UTC)

See Two-element Boolean algebra.  --Lambiam^Talk 00:05, 14 June 2007 (UTC)

What about it? It's not the same topic as Boolean-algebra-mass-noun; it's a particular Boolean-algebra-count-noun. --Trovatore 00:49, 14 June 2007 (UTC)

It is the underlying algebra when you're doing Boolean algebra, just like the field R underlies elementary algebra.  --Lambiam^Talk 09:11, 14 June 2007 (UTC)

Well, see, I disagree with that. There is no underlying structure when you're doing Boolean algebra (mass noun), or rather, any Boolean algebra will do just as well as any other. Of course there are first-order statements that will differentiate the two-element Boolean algebra from any other; say: "For every p, either p=0 or p=1", but this is a question you can't even ask when you're doing Boolean algebra (mass noun), because you don't have quantifiers or equality.

But even accepting your claim for the purpose of argument, it still doesn't solve the issue, because the two-element Boolean algebra would not be mass-noun Boolean algebra even if it were its underlying structure. Note that we have separate articles about real numbers and, as you said, elementary algebra, and they're quite different in character. What we need is a name for the analogous article to elementary algebra in this context. --16:57, 14 June 2007 (UTC)

Do you also dispute that the field R underlies elementary algebra?  --Lambiam^Talk 19:25, 14 June 2007 (UTC)

Well, yes, actually. But that's beside the point -- even if it did, you still wouldn't merge elementary algebra with real number. There's a need for an article about the subject (whatever its confines are exactly) that is typically called "Boolean algebra" as a mass noun, and two-element Boolean algebra is not that article. --Trovatore 19:47, 14 June 2007 (UTC)

Oh, and to be explicit, Boolean logic is that article, or at least is supposed to be. The Boolean logic article needs a clearer statement of its subject matter, and then needs to be more tightly focused around that subject matter, but that's the article we should start with. (To StuRat: Don't worry, I'm not talking about making it less accessible; the subject matter, once we figure out what it actually is, is inherently pretty accessible, so it should certainly be written that way. I just want a clearer demarcation of what it's actually about.) --Trovatore 19:52, 14 June 2007 (UTC)

(exdent) So in a sense there are two issues: (1) should Boolean logic be renamed to Boolean algebra (X) for some suitable disambiguating phrase X? and (2) what should go into that article. As to (1), I don't see a strong case for such a renaming, and also not for turning Boolean algebra into a dab page. A good This article is about ...; for ... see Boolean logic should be good enough (in my opinion). As to (2), I sure don't like the present article. I'd much prefer smething like (a) this is a calculus in which the variables represent values from a two-element universe, usually called 0 and 1 and equated with the truth values false and true; (2) the common operations correspond to the usual logical operations OR, AND and NOT, but are more commonly denoted as +, multiplication (using juxtaposition), and overbar; (3) here are the laws you can use on Boolean formulas; (4) simplifying Boolean formulas: examples, algorithms, complexity issues; (5) applications, e.g. Electrical Engineering, perhaps something Smullyanesque; (6) relation to Boolean algebra/Boolean ring.  --Lambiam^Talk 21:07, 14 June 2007 (UTC)

OK, so for (1) the case for the rename and dab page is that users repeatedly create links to Boolean algebra that they (quite reasonably!) expect will go to the mass-noun meaning that they're used to (and on the other side, mathematicians repeatedly, and reasonably, create links that they expect to go to the count-noun meaning). With a dab page, this will be more likely to be sorted out more quickly, as users following the link will realize that they need to disambiguate -- if they get dumped at the wrong page, instead, they may simply be confused. As for the rename of Boolean logic -- "Boolean algebra" is the common name, and we should use the common name when we can.

As to improving the current Boolean logic article -- I certainly think there is room for improvement. But I sharply disagree that specifying the two-element algebra as the canonical interpretation is an improvement. I don't think that's usually even true. If I had to pick a canonical structure, it would be the free Boolean algebra with as many generators as you have variables. Note that the "algebra of sets" interpretation is also discussed at Boolean logic, and probably should be, because it's probably part of the subject matter that most people think of as "Boolean algebra" as a mass noun, and this is yet another interpretation, distinct from both yours and mine. --Trovatore 21:25, 14 June 2007 (UTC)

I'm not convinced that "Boolean algebra" is a more common name than "Boolean logic". When in Boolean algebra/logic we consider the question: "What are the solutions of ${\overline {p\cdot q}}+r=0$?", what is the domain over which these variables range? Do you really need to consider the free Boolean algebra with three generators? I can simply see that ${\overline {1\cdot 1}}+0=0$, so a solution is given by p = 1, q = 1, r = 0. In the free algebra with generators p, q and r, the equation has no solutions.  --Lambiam^Talk 23:50, 14 June 2007 (UTC)

On "more common name" -- I really really think it is. Does anyone else doubt this?

As for solving Boolean equations for the values of variables -- really I never thought of this as part of Boolean algebra, though I suppose it could plausibly be argued. What we really need to do, I think, is to find out what standard references using the term (in the mass-noun sense) mean by it. I have no textbooks that use the term in that sense (I'd really prefer dead-tree sources over Web ones here). In addition, for historical context, we should find out what Boole's work looked like, though we don't necessarily need to adopt his notation for the rest of the article (for example I would much prefer writing the LHS of Lambiam's equation above as ¬(p ∧ q) ∨ r). --Trovatore 00:07, 15 June 2007 (UTC)

You can download the text of An Investigation of the Laws of Thought from here.  --Lambiam^Talk 01:00, 15 June 2007 (UTC)

OK, it's interesting. Still, the project to which Boole's book is relevant, namely how to improve the Boolean logic article, is not the main one I had in mind. What I'm trying to do here is converge on an agreement for the dab page and the naming of the two articles. --Trovatore 06:02, 15 June 2007 (UTC)

Google hit counts:

• about 189,000 for "boolean algebra" + circuit.
• about 197,000 for "boolean logic" + circuit.

While not conclusive for the use in general, "boolean logic" is at least about as common in the context of its applications. I tried to classify some samples of the hits for "boolean algebra" to see in what percentage it was used in the sense of abstract algebra, but that proved impossible since many uses were in fact ambiguous. It is not sufficient to see if the term is used as a mass noun. You'll find, for example, also Clifford algebra used as if it is a mass noun (e.g.: I am interested to see how Clifford Algebra can be used to solve problems within chemical engineering and physical chemistry; or: At the present time, the study of Clifford algebra and Clifford analysis has grown into a major research field), but nevertheless I don't think this is a different notion than treated in our Clifford algebra article requiring two articles Clifford algebra (count noun) and Clifford algebra (mass noun).

I'm actually getting a bit puzzled by what you see as the important difference between "Boolean algebra" (count noun) and "Boolean logic" (mass noun). For any algebra, you can form formulas using variables ranging over the carrier set and operators denoting operations from the algebra, and use the properties of that algebra to simplify formulas and prove equations. This is equally true for abstract and for concrete algebras. For example, in any ring, a(b+c) = ac + ab. This can be proved from the defining properties, and the obvious proof might be called an algebraic proof, and engaging in the necessary mathematical manipulations may be described as using algebra. To what extent is "using Boolean algebra" different: doing algebra while using the properties of the algebraic structures of the domain that make them Boolean algebras? The only sense that I'm aware of in which Boolean logic is special, is that the underlying algebra forming the domain is a concrete algebra with a two-element carrier set, and so p·q = 0 has four solutions, in all of which p = 0 ∨ q = 0. If we remove that assumption, I don't quite see the point.  --Lambiam^Talk 08:10, 15 June 2007 (UTC)

OK, let's put it this way. Yes, in any ring, a(b+c) = ac + ab. However that identity is not, in any nontrivial sense, ring theory. It would be mentioned in the ring article as one of the defining properties of a ring, and then pretty much dropped. In the elementary algebra article, though, one might use it to derive significantly more complicated identities -- which are also not, in any nontrivial sense, ring theory.

Similarly, the mass noun sense of "Boolean algebra" is about doing calculations (that is, deriving tautological equivalences) that are valid in a Boolean algebra (count noun). Any Boolean algebra, not just the one with a two-element universe.

The article on the mass noun sense could mention the axioms and then derive more complicated tautological equivalences from them. The article on the count noun sense will give the axioms and then pretty much drop them; deriving more complicated identities is not the point. The point is to study the structures themselves, not the equational logic of the structures.

Does that clarify the distinction I'm thinking of? --Trovatore 08:25, 15 June 2007 (UTC)

Oh, on rereading I notice that the b and c have switched places between the left-hand and right-hand side, so I'm wrong about it being appropriate for the ring article to give that identity as a defining property. Instead I'd say the ring article shouldn't mention it at all. But it would be defensible at elementary algebra. Hopefully this doesn't muddle my explanation too much. --Trovatore 08:43, 15 June 2007 (UTC)

My feeling is that the difference is ultimately only a gradual one: there is a continuum, at one extreme end of which very pure mathematicians invent and study algebraic structures in their own right for their private enjoyment and to satisfy their intellectual curiosity, while at the other extreme end very applied engineering types use algebraic structures that model properties of real-world systems as a tool to achieve design goals. Somewhere in the middle you may find, for example, mathematical physicists, who invent algebraic structures such as von Neumann algebras in order to describe laws of nature more conveniently. Kleene algebras is a good example of something studied at both ends: for their mathematical beauty, and as a tool in program construction. I can imagine a spin-off article Applications of Kleene algebra if a section on that takes up too much place in the main article, but no a priori need to delegate this to a separate article. Likewise, I feel that a merger of Boolean logic into Boolean algebra is quite defensible, and that arguments against this are largely pragmatic, such as the length of a combined article, or the effort exacted by having to address multiple audiences in one article.  --Lambiam^Talk 10:56, 15 June 2007 (UTC)

Pragmatism is key to the split. We found that, indeed, the two audiences and sets of editors had incompatible expectations. The split has worked well for content, but the naming remains slightly awkward. --KSmrq^T 18:48, 15 June 2007 (UTC)

I agree partly with KSmrq, but I want to emphasize to Lambiam that the distinction is not applications-based. It's a historically well-grounded, and in my view natural, content-based distinction.

The situation is that (what we can interpret as) the equational logic of Boolean algebras was developed first, before Boolean algebras were ever defined, and can be studied on its own without ever defining a Boolean algebra. This is the subject that most non-mathematicians expect to see when they come to an article called "Boolean algebra. It can be studied for its applications, or for its mathematical beauty, still without ever making reference to an algebraic structure.

On the other hand, at some point someone (I'd like to know who!) defined an algebraic structure, and called it, not unreasonably but perhaps unfortunately, a "Boolean algebra". When we talk about those structures, all the facts about the equational logic are just assumed. They're not the point (though it's interesting, and nontrivial, that all Boolean algebras have the same equational logic -- that's certainly not true for groups or rings or fields).

The article on the count-noun sense is parallel to the group article, and that's really the way I would like to see it developed: A little motivation, definition, examples, then on into structure (homomorphisms, atoms, atomlessness, ideals, completeness and countable completeness, stuff like that). The equational logic should not appear in the count-noun article, though the fact that it's completely axiomatized by the axioms very well might. The mass-noun article, on the other hand, should be mainly about the equational logic, and things that come out of it. --Trovatore 19:30, 15 June 2007 (UTC)

naming -- trying again

So the above section added tens of kbytes to this page but came to no conclusion, and we still have the problem. Let me re-summarize the problem and what I hope to get out of this discussion:

• Non-mathematicians, when they use the term "Boolean algebra", usually mean a system of manipulating variables representing truth values (or sometimes sets). This is the mass noun sense of the word. The emphasis is on the manipulations, not on any particular structure giving a semantics to the formalism. This is what the current Boolean logic article ought to be (it isn't, but that's beside the current point) -- though of course some simple semantics should also be discussed.
• On the other hand, mathematicians generally talk about this Boolean algebra, that Boolean algebra, the other Boolean algebra; these are algebraic structures, and this is the count noun sense. The emphasis in this article should be on the structures themselves; the algebraic manipulations are beside the point. This is what the current Boolean algebra article ought to be, though there's plenty that's missing (for example, not much is done with ideals, and what is there is too far down on the page; atoms are not mentioned at all).
• So (irrespective of how the articles themselves need to be improved, which is a side issue here), Boolean algebra ought to be a disambiguation page, because there are, and need to be, two quite distinct articles, and there are two groups that will naturally expect that when they link Boolean algebra, it will go to "their" article.
• So the current Boolean algebra needs to be moved, and Boolean logic should also probably be moved to something with "Boolean algebra" in the name.

That's the summary; here's what I want to get out of the discussion:

• Does anyone other than Lambiam disagree with the general thrust of the above?
• What do we use as the disambiguated names?
  • My vote is: Current Boolean algebra → Boolean algebra (object), second choice Boolean algebra (mathematical structure), third choice Boolean algebra (algebraic structure). Boolean logic → Boolean algebra (logical calculus), second choice Boolean algebra (logic).

--Trovatore 07:57, 20 June 2007 (UTC)

Both points of view sound reasonable to me (yours and Lambiam's)! I'm reminded of a married couple — I'm talking about the articles here, not the editors ;) — who are sometimes discussed together and sometimes as individuals. That suggests a compromise: Boolean algebra should be an overview of the subject, which links to articles on different aspects using {{main}}, including Boolean algebra (logic) and Boolean algebra (algebraic structure), but also several other pages in the List of Boolean algebra topics (e.g. Boolean algebras canonically defined, algebra of sets, two-element Boolean algebra).

Actually, when one notices that there is a Category:Boolean algebra, the case for this structure becomes rather compelling: the category needs a main article, and I don't think the main article should be a dab, nor should it focus on one major aspect of the subject at the expense of another.

However, as I mentioned at WT:WPM, I do think it is relevant that the current articles are not what they "ought" to be: if this compromise doesn't appeal, maybe some work on the content would help to clarify the issue. Geometry guy 12:46, 20 June 2007 (UTC)

So the problem (with your second paragraph), in my view, is that category:Boolean algebra is also poorly demarcated. It mixes doing Boolean algebra with studying Boolean algebras, and those two things are so different that I don't see a sensible "main" article combining them. --Trovatore 18:07, 20 June 2007 (UTC)

Don't you? Can you not see your conception fitting into such a framework? What about the History of Boolean algebra? That ought to refer to both aspects. Don't these ideas have a common inspiration? Studying Boolean algebras seems to me to be quite a specialist topic, and I imagine that Boolean algebras would form a relatively small part of such a main article, since there are so many other things to discuss within the general context of Boolean algebra. Geometry guy 18:32, 20 June 2007 (UTC)

So what that boils down to is that you think Boolean logic ought to be the "main article", perhaps slightly expanded to mention the algebraic structures in passing. I can see arguments for that point of view, but then you have the reverse problem with linking from the one that currently exists -- editors linking to Boolean algebra, intending the algebraic structure, wind up linking to the wrong article. --Trovatore 19:40, 20 June 2007 (UTC)

No it doesn't; "relatively small" is open to a great deal of interpretation, not just yours. A main article for a category should make readers with a particular interest crave more, and provide them with links to get more. The kind of detailed Boolean logic that you have in mind wouldn't feature either. Geometry guy 20:03, 20 June 2007 (UTC)

My point of view is that Boolean logic mainly concerns the trivial two-element algebra that is an example of a Boolean algebra, that larger finite Boolean algebras correspond to operations on bitvectors, etc., but that the algebraic study of Boolean algebras is often concerned with infinite objects that have little connection to calculation. I don't like the name Boolean algebra (object) because I don't think it clarifies that distinction at all. I prefer Boolean algebra (algebraic structure) and Boolean algebra (logical calculus), because I think it does. —David Eppstein 15:58, 20 June 2007 (UTC)

I'm OK with your names. I don't, however, agree that the Boolean logic article either does (currently), or should, primarily treat the two-element algebra. What it currently mainly treats is the algebra of subsets of a given set. I don't like that choice either; I think it should center on the calculus itself (that is, the manipulation of Boolean expressions), and then branch out from there into applications, which would necessarily include interpretations. I agree that the calculus should be motivated before it's presented, and the two-element algebra is probably the best choice to motivate it. --Trovatore 18:07, 20 June 2007 (UTC)

I think this is a good choice of names too. Note that if there were a main article, then Boolean algebra (logical calculus) could more easily center on the calculus itself. Geometry guy 18:32, 20 June 2007 (UTC)

I don't think the "main article" idea solves the basic problem, which is wikilinks that go to the wrong place. If there were a main article (whatever the content, which I have trouble visualizing) it wouldn't be the article people wanted when they link to Boolean algebra intending the algebraic structure. Of course, neither is the dab page, but with a dab page it's obvious to everyone following the link that something needs to be done about it. With the "main article", it isn't. --Trovatore 19:18, 20 June 2007 (UTC)

With dablinks at the top of the page, it does, and at least the article is useful, and maybe even educational, to all who find it. Geometry guy 19:28, 20 June 2007 (UTC)

I don't see how the dablinks make it obvious that something needs to be done about it. What you'll have is that editor A creates a link intending the algebraic structure, and editor B creates another link intending the logical calculus, and readers wind up at this neither-fish-nor-flesh article, skip over the stuff at the top, and say "Hunh?". I'm also frankly skeptical that such an article can be useful, given its poorly defined subject matter. --Trovatore 19:34, 20 June 2007 (UTC)

(unindent) I suspect you may be sceptical because your mind is made up. In which case, why waste other editors' time by asking for opinions? Were you hoping for a crowd to appear saying "Trovatore is obviously right, and Lambiam is obviously wrong"? I have attempted to find a compromise between two reasonable points of view, but your response has been to reassert your own view with greater strength. You seem surprised that it has been so difficult to find consensus for a solution to this issue: have you not wondered why? Geometry guy 20:03, 20 June 2007 (UTC)

I see what, to me, is an obvious problem, and I don't seem to be managing to communicate it. Yes, I do wonder why that is. Maybe you and Lambiam just don't find the "algebraic structure" sense very interesting? You're entitled to that view, of course, but it doesn't solve the problem that lots of articles link to it, and in that case an link that isn't to an article about "studying Boolean algebras", rather than "doing Boolean algebra", is not useful.

For me, "studying Boolean algebras" is much the more interesting topic, so the status quo is OK for me, except that every now and then I have to change an inappropriate link (and of course that the articles both need serious improvement). But I recognize that that isn't really fair to readers looking for, or editors meaning to link to, "doing Boolean algebra". I don't think the solution is to make it unfair the other direction. --Trovatore 20:23, 20 June 2007 (UTC)

Thanks for clarifying your point of view: I hadn't fully appreciated where you were coming from. In fact I do find Boolean algebras interesting (perhaps I also find them more interesting than Boolean algebra), so my comments about the topic being specialist do not reflect my personal taste. But I am further away, so I also see the "wikipedia point of view". And I see you do too, with your good faith desire to ensure that links to Boolean algebra take readers where they want to go. I have done my best here to contribute. I hope, at least on reflection, my comments have been helpful. Geometry guy 20:32, 20 June 2007 (UTC)

Lambiam's thought that the articles on the count noun and mass noun might better be combined has merit, and in fact was more or less how we attempted to handle this content originally. However as KSmrq pointed out above, that proved to be unworkable. This was partly due to the different world views of the editors involved, but as Trovatore correctly notes, this was mostly due to the significant differences between the uses of the two terms. Splitting the articles was a good move in my opinion. Geometry Guy's idea to keep the split, but instead of a dab page, write an overview article has more merit, but like Trovatore, I see potential difficulties in trying to write such a page. So I think Trovatore's proposed approach is the best course of action for the moment. As for the names of the articles I would vote for David Eppstein's preference: "Boolean algebra (algebraic structure)" and "Boolean algebra (logical calculus)". We can always try to write an overview article in the future. Paul August ☎ 20:54, 20 June 2007 (UTC)

(I note that in all this discussion there has been no mention of Vaughan Pratt's labor-of-love at Boolean algebras canonically defined. It's a fine article, by a distinguished author who is both mathematician and computer scientist.)

"I mentioned it, I mentioned it" screams four year old Geometry guy 22:36, 20 June 2007 (UTC) ;)

I apologize for the oversight; so you did — to deafening silence. :-) --KSmrq^T 05:54, 21 June 2007 (UTC)

See also this.  --Lambiam^Talk 08:32, 21 June 2007 (UTC)

Our first choice is either to rename or to do nothing. If we rename, we must choose names. Our second choice is to either make a bare disambig page, or to write a springboard article, or to do nothing.

I am sympathetic to the possibility of renaming. I'm not thrilled with the names offered. And I'm sympathetic to a springboard article, but am not inclined to write it.

None of the proposed renamings for Boolean logic suits me, nor do I like "Boolean algebra (object)". An honest dichotomy might be "(pure)" and "(applied)", though I know of no precedent. The name should highlight the thrust of the article. While it seems clear that the current Boolean algebra lies within abstract algebra, it seems harder to pin down Boolean logic. Is it not really "Boolean calculus", more than just logic? For example, constructive solid geometry uses Boolean operations on geometric sets; this is hardly logic! The same applies to search expressions. Logic is an important application, but does not deserve to capture the name.

In summary: Yes, the status quo is awkward; the worst problem is the name/expectation clash. I see no consensus (nor volunteer, apropos the springboard) for fixes. However, if we can settle on better names, I'd be content; ergo, I propose that — for now — we concentrate on that. --KSmrq^T 22:01, 20 June 2007 (UTC)

Yes let's. I could accept "Boolean algebra (Boolean calculus)". Paul August ☎ 22:12, 20 June 2007 (UTC)

There seems to be some consensus here for renaming, and the most popular titles appear to be Boolean algebra (algebraic structure) and Boolean algebra (logical calculus). This leaves Boolean algebra itself as a dab, but with the possibility that those with the energy for it (Lambiam? Yours truly? Perhaps others?) to expand such a dab to an overview of the subject and its history. Geometry guy 22:36, 20 June 2007 (UTC)

The problem with the last part of it is that it means Boolean algebra will link to something that's not a dab page, and also not the "algebraic structure" article. I don't like that at all. When editors link to Boolean algebra, intending the algebraic structure, it's a bad result if the link winds up at some general article that's not about the algebraic structure. It's not so bad if it winds up at a dab page, as that will eventually be fixed.

Maybe you could write such an article and call it overview of Boolean algebra or some such? I still don't know what it would really be about, but that would be for you to decide. --Trovatore 23:16, 20 June 2007 (UTC)

Maybe. I am trying to bridge the divide here, but Lambiam has not commented yet, and I don't know if all other contributors have read all of the prior discussion. So I think it is worth keeping an open mind for the moment. Geometry guy 23:34, 20 June 2007 (UTC)

By the way, I just saw your gracious remarks in the middle of the page; thank you for that. I think we're all working here in good faith; sometimes it gets a little emotional just because that's how human beings are. --Trovatore 23:29, 20 June 2007 (UTC)

You're welcome! I'm sorry for my partial misunderstanding of your point of view. Geometry guy 23:34, 20 June 2007 (UTC)

As Geometry Guy notes above there is "some consensus" for having "Boolean algebra" be a dab page and having the count noun be at "Boolean algebra (algebraic structure)" and the mass noun at "Boolean algebra (logical calculus)" (although KSmrq is not completely happy with the latter). In the interest of actually coming to some conclusion, I propose that we go ahead with this change since, while perhaps not perfect, such a change will be better than what we have now. Does anyone object to this? Paul August ☎ 23:12, 22 June 2007 (UTC)

I agree, although I would definitely like to leave open the idea that editors with some energy could expand the dab into an overview of the category (of course with dablinks at the top of such an article). Geometry guy 23:40, 22 June 2007 (UTC)

I suppose I'm not bitterly opposed to that, on the condition that the overview article begin with, not just dablinks, but a brief statement that there are two quite distinct senses of the term, and explaining what they are and where the links go. In other words, "dab plus", rather than an independent article containing dablinks. Otherwise my concern is that we're back to where we were before the split, with the overview article trying to incorporate both senses without ever explaining the distinction. That was definitely not a good place; the status quo is better than that. --Trovatore 01:29, 23 June 2007 (UTC)

I agree entirely. In fact I think an article on Boolean algebra would be a failure to the readership if it did not discuss the distinction emphatically and explicitly in the lead. I hope Lambiam will also accept a consensus/compromise along this line. Geometry guy 01:38, 23 June 2007 (UTC)

Alright, gosh darn it; I guess it's put-up-or-shut-up time. As Paul August surmises, I'm not thrilled with the "logical calculus" name. Give me 24 hours from the time of this post to come up with something better. If I have nothing to propose by then, then I won't oppose. --KSmrq^T 02:52, 23 June 2007 (UTC)

"Boolean algebra (symbolic logic)" perhaps?  --Lambiam^Talk 08:47, 23 June 2007 (UTC)

Ideally, I would prefer that the disambig phrase answer the question "what is it?" rather than "in what context is it to be interpreted?". That's what I like about the "logical calculus" formulation; it's the closest thing I can think of to what the mass-noun sense is. --Trovatore 17:35, 23 June 2007 (UTC)

Tough, isn't it, summarizing the distinction with a pair of parenthetical tags? Maybe "abstract" and "applied". I'm trying hard not to say "logic", because the applications include sets and signals and so on as well. I'm still thinking. --KSmrq^T 17:39, 23 June 2007 (UTC)

"Abstract" and "applied" is not the correct distinction. The logical calculus can be pretty abstract (say, if we let it get into the completeness and soundness theorems). And you yourself cited applications for the algebraic structure, in an earlier discussion (I never looked them up, but they were at least "applied" enough to appear under the IEEE name). --Trovatore 19:08, 23 June 2007 (UTC)

So far my best effort is "symbolic calculus". I'm going to look through "What links here" of Boolean logic for further inspiration. Everyone is welcome to play. --KSmrq^T 04:34, 24 June 2007 (UTC)

My survey of what links to "Boolean logic" is complete, with disconcerting results. All those pages really want logic (typically as in logic gates), not algebra. Most are articles related to computer circuits. I don't know what a survey of links to "Boolean algebra" will show; the theory of this proposed renaming seems to be that some of them don't really want an abstract algebra article. I'm not going to try to complete that new survey in the 24-hour window I gave myself, but I now think it's essential. Therefore, I propose that any renaming be postponed until we can establish the "facts on the ground". --KSmrq^T 07:15, 24 June 2007 (UTC)

A few things: first, the dab page and renaming of Boolean algebra needn't wait; we can make a dab page with a link to the current Boolean logic while we decide how the latter article should be renamed. Second, it's not so much about the current links to Boolean algebra (a lot of those, presumably, have been corrected, and anyway we could correct the rest) as about the fact that it's an ongoing problem.

Third, the current content of Boolean logic, and its current links, are not the controlling factor: We need to decide what article we want to have. As a programmer I say that it's a waste of time to write implementation code until the header files are in good shape -- that's unfortunately what's happened at Boolean logic. What to do about that is another question, of course. One possibility would be three steps: (1) move the current Boolean logic to the new name, (2) write a new article under the name Boolean logic from the perspective of logic gates, and (3) rework the moved article so that it fits the new title (that is, start with the symbolic calculus, then segue into applications and interpretations, somewhat de-emphasizing the "algebra of sets" material that currently overwhelms it). --Trovatore 07:27, 24 June 2007 (UTC)

What's the rush? It won't take that long to do the extra survey. I am now not convinced exactly what we ought to be doing. When I looked at those "logic" articles, I considered how they would read with the phrase "Boolean algebra"; almost universally that would have been awkward and unnatural. That fact, by itself, leads me to believe "Boolean logic" should stay where it is (and perhaps be rewritten); possibly so should "Boolean algebra". Only by looking for possible mistaken links to "Boolean algebra" can I see what, if anything, needs to be done. Meanwhile, do you have any way to document the "ongoing problem"? Even anecdotal evidence might be helpful. ("I've had to fix twenty links in the last six months.") I've had "Boolean algebra" on my watch list, and don't recall seeing much in the way of inappropriate edits from people who expect a different focus.

Wikipedia grows by random accretion, not plan, so we're constantly refactoring and rewriting and renaming. (Trying to stay at least one step ahead of the chaos?) I'm not ruling out a move and a dab page, but I'm now less certain what we need to accomplish. Maybe the dab notice at the top of "Boolean algebra" is working as well as an independent dab page (or dab article) would. If not, a survey of the links may help clarify the expectations of editors who are not intending abstract algebra, so we can better serve those editors (and our readers).

I do apologize for the delay; I, too, would like to get this settled. Still, I think the survey is necessary to "design the right headers" to use your programming metaphor. --KSmrq^T 08:20, 24 June 2007 (UTC)

The proposed divorce (following Geometry guy's married-couple metaphor) of Boolean logic and Boolean algebra has little do with "Boolean" and everything to do with "algebra." The articles on algebra at both Wikipedia and the Stanford Encyclopedia of Philosophy[1] (SEP) distinguish between elementary algebra and abstract algebra (aka modern algebra) at the outset. The Wikipedia article covers both in some detail and points to the subject articles for more detailed coverage of each; the SEP article is of necessity more self-contained since SEP has no separate articles for those constituent topics.

In the case of Boolean algebra one could leverage this standard terminology by splitting Boolean algebra into Elementary Boolean algebra and Abstract Boolean algebra. Now Boolean algebra is just one of many varieties of algebra, having as siblings group theory, ring theory, linear algebra, etc. Is there any precedent for repeating algebra's elementary/abstract split at each variety? Well, there is indeed a separate article for Elementary group theory (to my surprise), though none for Elementary ring theory. In the case of linear algebra the article Matrix (mathematics) might just as well have been titled Elementary linear algebra. One might also argue that Elementary algebra is really the elementary theory of fields over the reals (with the traditional scope of elementary algebra rounded out by passing to complex numbers and throwing in exponentiation).

The question here is whether Boolean algebra is more like ring theory or linear algebra? In the case of linear algebra a case can be made for the split based on the wider conceptual gap between matrices as tables of numbers vs. linear transformations as homomorphisms of algebras closed under linear combinations; anyone serious about teaching linear algebra to engineers, biologists, etc. is going to quickly lose most of their audience if they start out from the latter perspective.

I would think that Boolean algebras are more like rings than vector spaces in that regard. The algorithmic aspect of Boolean logic is covered under Boolean satisfiability problem (including Quantified Boolean Expressions (QBE) under the heading Extensions of SAT), while its logical aspects are covered under Propositional calculus (with the caveat that while two-valued or Boolean logic furnishes propositional logic with its standard model, that subject is more broadly construed to allow more general models such as Heyting algebras). About the only content to the present Boolean logic article not covered by these other articles is the point that the adjective "Boolean" connotes equational reasoning in preference to the Hilbert and Gentzen styles of reasoning traditionally associated with propositional calculus.

My vote would be for a single article on Boolean algebra covering the following points.

1. Boolean algebra is the equational theory of a two-element set, traditionally the set {0,1} or {false,true}, denoted 2 here.

2. The language of Boolean algebra consists of its operation symbols, called the Boolean operations. The Boolean operations are defined as the finitary operations on 2, namely all functions of the form f: 2ⁿ → 2 for integers n≥0 called the arity of the operation. There are two nullary (arity zero) operations or constants, namely 0 and 1. There are four unary operations, 16 binary, and in general 2²ⁿ n-ary operations.

(Asides. (a) Finitary is an essential defining characteristic of "Boolean algebra" in the strict sense of the term. Allowing higher arities takes one into such generalizations of Boolean algebra as sigma-algebras (countable arities), used in statistics and measure theory, and complete Boolean algebra (arbitrary arities), used in the algebra of sets. (b) The above defines a syntactic entity, namely an operation symbol, by identification with a semantic one, the corresponding operation over 2. An alternative that some may find clearer is to draw a harder line between syntax and semantics by starting out with two sets in bijection, of operation symbols and the corresponding operations over 2, treating the latter as one possible interpretation of the former. These can be collapsed to a single set, i.e. convert the bijection into identification, after becoming comfortable with the notions. The collapsing avoids the overhead of maintaining a separate set together with the bijection and associated terminology.)

3. A basis for Boolean algebra is any set of Boolean operations from which the remaining Boolean operations can be obtained by composition. The standard basis consists of conjunction, disjunction, and negation. The smallest basis, due to Henry Sheffer, consists of just NAND or Sheffer stroke. The ring basis, found by Marshall Stone, consists of conjunction and exclusive or; this basis makes a Boolean algebra a special kind of ring called a Boolean ring. Many other small bases are possible. The improper basis is the set of all Boolean operations itself.

4. A Boolean term is an expression built up from variables using Boolean operations, such as x, or x∧(y∨¬x). A Boolean equation is a pair of Boolean terms constituting the left hand side and the right hand side, conventionally separated by the equality symbol as in x∧y = y∧x. A Boolean identity is a Boolean equation which holds identically, meaning that its two sides have the same value for all valuations of (assignments of 0 or 1 to) the variables, for example x∨x = x, but not x∨y = x (counterexample: the valuation x = 0, y = 1, which also refutes x∧y = x∨y). The equational theory of Boolean algebras, more succinctly but less standardly Boolean logic, consists of all Boolean identities.

(At this point all material that one might have considered for a separate article on Elementary Boolean algebra or Boolean logic can go here. A few paragraphs should suffice, bringing in say Venn diagrams, truth tables, etc. Note that up to this point everything has been syntax with the exception of the semantic entity 2 and its finitary operations, whose role is really as much syntactic as semantic, cf. the axiomatization of Boolean logic in Boolean algebras canonically defined which turns each finitary operation into a purely syntactic equation which nevertheless has semantic content by amounting to a generic rule for evaluation in any Boolean algebra. Now one is ready to launch into Boolean algebras as objects.)

5. A Boolean algebra is any model of Boolean logic. It consists of a set B and, for each n-ary Boolean operation symbol f, an interpretation f_B: Bⁿ → B of f, that is, an n-ary operation on B. We require furthermore that these interpretations satisfy every Boolean identity, meaning that for all valuations in B of the variables appearing in the identity, the two sides of the identity must have the same value in B when the operation symbols are so interpreted. A Boolean algebra is uniquely determined by its operations in a given basis, the interpretations of the remaining Boolean operations then being obtainable by composition from the interpretations of the basis operations. Boolean algebras are standardly defined in this way using the standard basis; that is, a Boolean algebra is standardly defined as a set B and interpretations over B of conjunction, disjunction, and negation satisfying the relevant Boolean identities (those expressed using only those three operations).

6. An axiomatization of Boolean logic is any set of Boolean identities whose only models are Boolean algebras. Thus an axiomatization is any sufficient set of equations for the purpose of defining "Boolean algebra." Boolean logic is finitely axiomatizable, that is, has finite axiomatizations. Any finite axiomatization necessarily uses only finitely many Boolean operations, which as one might expect must form a basis from which the remaining Boolean operations may be obtained. Restricting to the standard basis, the standard axiomatization of Boolean algebra consists of the equations for a complemented distributive lattice. The ring basis is axiomatized by the equations for a Boolean ring, namely the ring axioms (treating conjunction as multiplication and exclusive or as addition) together with x² = x.

7. Examples. For any integer n≥0, the set of all 2ⁿ bit vectors of length n form a Boolean algebra under the usual bit vector operations AND, OR, and NOT (in the programming language C, x&y, x|y, ~x, good for bit vectors up to the word length of the computer). Any power set 2^X of an arbitrary set X under union, intersection, and complement forms a Boolean algebra, called a power algebra. Up to isomorphism, finite Boolean algebras, finite bit vector algebras, and finite power algebras are the same thing, whence the only finite Boolean algebras are those of cardinality a power of 2, with one Boolean algebra for each power. However there exist infinite Boolean algebras that are not isomorphic to any power algebra, though all Boolean algebras are isomorphic to some subalgebra of a power algebra (feel free to take examples verbatim from my article Boolean algebras canonically defined). Moreover Boolean algebras with the same number of elements need not be isomorphic, unlike the finite case. And Boolean algebras of all infinite cardinalities exist, again unlike the finite case.

Certainly there's much more that could be added to this; for example just as one can define abelian groups as Z-modules and vector spaces over a field k as k-modules, so can one define Boolean algebras as 2-modules (2 here being the Galois field GF(2)) with the caveat that linear transformations require an additional restriction that they preserve the all-ones vector, without which only the all-zeros vector would be preserved. One could also take things away from it in the interests of pedagogic simplicity, but this would need to be done carefully, just as an architect needs to exercise care in simplifying the foundations of a house---pull out a critical support and it becomes unclear how the structure is supposed to hold up. By all means improve on my exposition (less turgid, supply details I've glossed over, express using simpler or more familiar concepts, give truth tables, draw Venn diagrams, etc.), but I don't think much of it can be actually removed without obscuring what's going on. Vaughan Pratt 21:29, 1 July 2007 (UTC)

Hi Vaughan. You don't think that, linguistically, the distinction between "Boolean algebra" in point 1 (based on a two-element set) and "A Boolean algebra" in point 5 (based on a set of arbitrary cardinality) is sufficiently subtle that it is likely to lead unwary readers and editors astray? —David Eppstein 22:10, 1 July 2007 (UTC)

The subtlety is real, just as in the more general situation of algebra vs. an algebra. How would you propose to deal with the subtlety? You can't just ignore it and hope no one will be bothered by it. Vaughan Pratt 22:33, 1 July 2007 (UTC)

(Edit conflict) Vaughan, that sounds like a great outline for a course on the subject. With respect, I think it's both in practice completely unworkable, and the wrong way of categorizing content, as an encyclopedia article.

There are two basic reasons for separating the equational logic from the model theory. From my point of view, the more important of the two is just that it really is naturally a separate subject. The equational logic predates the model theory, and given the fact that it's exactly the same in all models, it's also not an interesting thing to talk about when you're discussing the model theory.

The other reason is practical, and that's the one that can't be got around no matter how you see the question philosophically. What most non-mathematicians are thinking of, when they use the term "Boolean algebra", is the equational logic and some simple applications thereof. They're not interested in the model theory at all (though some simple interpretations are discussed implicitly, along with the applications). So they need an article. And the algebraic structure also needs an article, where the equational logic is not extensively discussed (because otherwise there's way too much you have to wade through before you get to the good stuff).

I think we have a rough consensus on the two-article model, perhaps with a "dab plus" springboard at the Boolean algebra title, and I hope we can proceed with that. --Trovatore 22:16, 1 July 2007 (UTC)

Points 1-4 treat only the equational logic, I had hoped it was clear that the model theory didn't start until Point 5. Is not defining the equational theory as that of {0,1} simpler and more natural than listing a dozen or more equations? Vaughan Pratt 22:33, 1 July 2007 (UTC)

The fact that the model theory doesn't start till point 5 is one of the biggest reasons why we need a two-article model. If you're looking for that article, you don't want to read points 1 through 4. As to your second sentence, I don't see that as either-or. The axiomatization should be presented, and it should also be motivated, and the motivation using {0,1} or {T,F} is of course the natural one.

My main interest is in the model theory article, and my concern for it is that it not be bogged down with the equational logic. As to what happens with the equational logic article, I'm less particular, but I would stress keeping its natural audience in mind, which is a somewhat less technical one. --Trovatore 23:30, 1 July 2007 (UTC)

Oh, another point: Vaughan mentioned a "proposed" divorce. In fact, the divorce happened about a year ago, for irreconcilable differences -- take a look through the history of the talk page. There is no point in discussing getting back together again at this point, wouldn't work this time either, would just put the kiddies through more anguish and keep the principals from getting on with their lives. What we're talking about now is what name to use post-divorce, and a little about division of property. --Trovatore 00:24, 2 July 2007 (UTC)

Actually I'm fine with separate articles for the elementary and abstract subjects, for exactly your reason: the syntactic logician is happy to fix a standard model and play with its equations, the semanticist is happy to fix the theory and play with its models. My difficulty is with treating the difference between the equations and the models purely as disambiguation. The "ambiguity" between "Boolean algebra" and "a Boolean algebra" is not an ambiguity in the usual sense but a standard distinction in every equationally defined branch of algebra. It is always the case that there is a set of equations, and a class of models of that set. Calling this an ambiguity misrepresents the essential unity of the elementary and abstract sides of the subject, whether it be group theory, linear algebra, or Boolean algebra.

The issue of choice of basis for each of operations and equations aside, my points 1-4 simply define Boolean logic as the equational theory of the algebra of finitary operations on {0,1}. Point 5, the model theoretic half, is that a Boolean algebra is any model of Boolean logic. The rest is just details and elaboration. It seems to me that it would be helpful if this unity were expressed somewhere where it is not forced to seem specific to one or the other of the elementary and abstract branches of the subject. Vaughan Pratt 01:07, 2 July 2007 (UTC)

The study of Boolean algebras is not, in my experience, called "Boolean algebra". Boolean algebra, as a mass noun, means the equational logic; as a count noun, it means the structure that models that logic. I don't see any essential unity there; these are quite distinct subjects. It's also not an "elementary" versus "abstract" distinction (for example, the completeness and soundness theorems for propositional logic belong to the "equational logic" subject, and they are not all that elementary, and by most people's standards they are quite abstract).

So I really think it is an ambiguity. It's an unfortunate accident of language that the structure happened to get the same name as the equational logic in this case. That didn't happen for groups or rings or fields. There's a difference, of course, in that the equational logic of those structures varies from model to model, whereas for Boolean algebras it's categorical, but that's even more reason to consider the equational logic a separate subject. --Trovatore 04:25, 2 July 2007 (UTC)

There's quite a few that would disagree with you on "Boolean algebra" referring only to the syntactic side, e.g. Donald Monk's authoritative article http://plato.stanford.edu/entries/boolalg-math/, or http://mathworld.wolfram.com/BooleanAlgebra.html, or http://www.math.uwaterloo.ca/~snburris/htdocs/scav/boolean/boolean.html, or http://www.cacs.louisiana.edu/~mgr/404/burks/foldoc/84/13.htm, or http://publish.uwo.ca/~jbell/BOOLEarticle.pdf. All of them treat Boolean algebras as objects under the heading "Boolean algebra". The separation you want to make into two distinct subjects simply doesn't exist for those people, for whom equations and algebras are two sides of the same coin. Vaughan Pratt 08:00, 2 July 2007 (UTC)

Whether they're "two sides of the same coin" is a philosophical question we don't really have to settle. As a matter of language, even if a few people may use the mass noun to mean the study of the referent of the count noun, no one uses the mass noun to mean the same thing as the count noun. That's a sufficient ambiguity to justify the dab page. (By the way, the Monk entry does not seem to make that identification as far as I can tell.) --Trovatore 19:47, 2 July 2007 (UTC)

As a constructive change of pace I spent Monday pursuing my suggestion of an article on Elementary Boolean algebra, a link appearing a couple of times above that observant readers of this page will have noticed changed from red to blue this afternoon. It is very difficult to know what to write under that heading given the wide range of backgrounds of the potential readership of an elementary article---teachers are familiar with the experience of pitching their material too far above the class's background, but they're also familiar with the experience of students getting restless when it's pitched too low. While "X for dummies" might sell well in the bookstore, it doesn't go down so well as the topic of a lecture because students don't like to feel that they've somehow ended up in the class for special students. With that caveat, I hope there is at least some audience somewhere in the middle for what I wrote. If you see stuff that could be reorganized to reach a larger audience don't hesitate to suggest the changes to me, or (this being Wikipedia) pitch in and make the changes yourself. If you feel it is still way off from "elementary" don't feel shy about saying so (I know some who won't). Vaughan Pratt 07:13, 3 July 2007 (UTC)

I really feel that more forks is not what we need here. I think this should be merged into the "equational logic" article, wherever that winds up. This is not a criticism of the article itself. But we're not supposed to write separate articles on the same topic from different points of view. --Trovatore 07:19, 3 July 2007 (UTC)

Actually, it's better than the current Boolean logic, so maybe we should merge the other way, then move it to a more appropriate title. --Trovatore 07:22, 3 July 2007 (UTC)

Fine by me, I too am in favor of minimizing the number of articles on a given topic (as are some of the commentators on Elementary group theory). I was hoping to include some appropriate figures but they're a tad labor intensive, which merging might help with. Vaughan Pratt 08:23, 3 July 2007 (UTC)

Aren't we all in agreement?

I have just read through all this after a break I find myself agreeing with almost all of the above, and wondering why there is disagreement. I agree with Vaughan Pratt that the distinction between Boolean algebra (the equational logic) and a Boolean algebra (a model for this logic) is very similar to the distinction between algebra and an algebra. I agree with Trovatore that we need separate articles on the two subjects. I think Vaughan Pratt's overview of the topic of Boolean algebra is very nice, but agree with Trovatore that it is a complete course on Boolean algebra rather than a single encyclopedia article, and also that an article is needed that begins with the equational logic, with a disambiguation of this article from the algebraic structure.

But where is the contradiction here? I have already suggested that Category:Boolean algebra needs a main article which provides an overview of the category. The standard structure for such an article is an overview with links to subarticles. Such an article would begin with a {{dablink}} to the two meanings of Boolean algebra followed by an overview like the one proposed by Vaughan Pratt, but made encyclopedic by using summary style. This is not so different from the "dab-plus" favoured by Trovatore.

Trovatore suggested above that we do not need to settle the philosophical question whether the two meanings of Boolean algebra are two sides of the same coin. More than that: we must not settle it! There are clearly different points of view here (as these long discussions demonstrate) and we are obliged to present them both. Geometry guy 16:49, 5 July 2007 (UTC)

This all sounds basically right, but I have one concern, which is that the "dab plus" at Boolean algebra should not "look like a real article". The reason is that we can expect more links to be made to it on an ongoing basis, intending the algebraic structure (or perhaps the equational logic, for that matter), and I'd like it to be obvious to anyone following the link that the link needs to be changed. If that isn't obvious, then there's still a problem. --Trovatore 17:06, 5 July 2007 (UTC)

I reread the discussion again, and noticed your remark that you had not seen "Boolean algebra" used to describe the study of Boolean algebras. I'm sure you are right, but is the term "algebra" used to describe the study of algebras? Not really, and perhaps for the same reason: it is too imprecise. But Boolean algebras are still models for Boolean algebra.

I was more struck, however, by your comment that "What most non-mathematicians are thinking of, when they use the term "Boolean algebra", is the equational logic and some simple applications thereof." And probably quite a large proportion of mathematicians too!

This suggests to me that it might be more appropriate to use {{otheruses4}} to disambiguate the algebraic structure meaning: Boolean algebra could still be an overview, and it could still touch upon the model theory, but {{otheruses4}} could provide a standard and clear disambiguation to the mass noun sense. Just an alternative suggestion... Geometry guy 22:43, 5 July 2007 (UTC)

"Probably a large proportion of mathematicians too" -- yes, certainly. But that's because the term really is ambiguous, which is why I still think a straight disambig page is the best option. I'm against an overview that looks like a full article (at least, under the name "Boolean algebra"), because it will too often be inappropriately linked to, when the link really wants to go to one of the specific meanings. --Trovatore 22:48, 5 July 2007 (UTC)

If we are agreed on this, then a straight disambiguation page is not favoured by the Wikipedia disambiguation guidelines. If the term is ambiguous but one meaning is sought most of the time, then it is much better to use {{otheruses4}}, or a similar dablink, to disambiguate the less common usage. This solves the problem in my view. Geometry guy 23:11, 5 July 2007 (UTC)

"Most of the time", in my opinion, means "overwhelmingly most of the time". Here it's fairly balanced. --Trovatore 23:16, 5 July 2007 (UTC)

Actually there are two boundaries here: a simple one that we all understand between "algebra" and "an algebra", and a much deeper one between Boolean algebras that are power sets (the obvious example), and all other Boolean algebras. In the study of Boolean algebras, power sets don't come up at all because their structure is utterly trivial, in the same way that sets have trivial structure. Section 1 of Donald Monk's article "The mathematics of Boolean algebra", http://plato.stanford.edu/entries/boolalg-math/, at the Stanford Encyclopedia of Philosophy, briefly runs through the definitions and elementary properties of Boolean algebra, and sections 2-7 then launch immediately into a depth that has no counterpart for this subject anywhere on Wikipedia, whether in English, French, or Klingon.

You don't need a Ph.D. to absorb power sets as the basic examples of Boolean algebra, which can be dealt with in a few lines. There are also a few simple examples of countable Boolean algebras that are pretty easy to understand though they don't begin to scratch the surface of the real subject--I'm agnostic as to whether those should be in an elementary article.

Somewhere around that point I would be perfectly happy to end a general-purpose article on Boolean algebra with pointers to more serious articles on Boolean algebra(s) as those articles come to hand. The general-purpose article would be pretty much all about syntax and only briefly mention power sets (aka the set of all bit vectors of any given length including infinite length) somewhere as the trivial examples of Boolean algebras, leaving the real subject to other articles.

Given how little material lies between these two boundaries, the simplest approach to reducing these two boundaries to a single boundary is not to get worked up about whether power sets show up in both articles. It's too few lines to be worth arguing over. Vaughan Pratt 05:54, 6 July 2007 (UTC)

Yes, that's fine; I had the subject you mentioned categorized under "simple applications and interpretations of the equational logic", but sure, it's OK to mention it also in the structure article (in fact it would probably be hard to avoid). --Trovatore 06:11, 6 July 2007 (UTC)

Oh, except that I don't really believe in a "general-purpose article". I take it by that you mean what I'm calling the equational logic article. --Trovatore 07:38, 6 July 2007 (UTC)

Yes, that's what I mean. Boolean algebras start out very simply as power sets, but beyond that they get so esoteric so quickly that a "general-purpose article" may as well just focus on the syntax, which has a lot more accessible material than Boolean algebras. Group theory tends to be the other way round -- the syntax is boring (putting an equation in normal form is quick and easy, unlike Boolean algebra), while the semantics has a dazzling variety of easily understood finite and infinite groups serving combinatorics, crystallography, geometry, games (the group of positions of Instant Insanity, of Rubik's Cube, etc.), algebra (the group of automorphisms of an algebraic structure), and so on. A set of equations in group theory is interesting, but that's really about groups given that all groups are presentable as a set of generators and a set of relations. A finite set of equations in Boolean algebra is trivially reducible to one equation (reduce {a=b, c=d} to (a⊕b)∨(c⊕d) = 0), which is what makes single equations so complex and therefore interesting in Boolean algebra. Vaughan Pratt 06:30, 7 July 2007 (UTC)

Wikipédia en français

For what it's worth, the French Wikipedia has three pages:

• Algèbre de Boole, a disambiguation page;
• Algèbre de Boole (structure), on the algebraic structures;
• Algèbre de Boole (logique), on the mathematical area.

 --Lambiam^Talk 15:20, 26 June 2007 (UTC)

That's quite good, I think. How do people react to Boolean algebra (structure) and Boolean algebra (logic)? Simple and to the point. I know KSmrq doesn't like "logic" because the subject isn't purely logical, which is true, but only when you get to the applications. The underlying subject of the equational logic article really is logic. --Trovatore 00:32, 2 July 2007 (UTC)

I'd support KSmrq here, union and intersection being set operations rather than logical. Something like Elementary Boolean algebra would address that while being more in line with the nomenclature for both the group theory articles and the general algebra articles.

Incidentally one comment on the French articles is that the bulk of the structure article focuses on largely the same equations as the logic article. In fact there are really only three lines in the structure article having to do with structure: (a) the line at the beginning defining a Boolean algebra to be a set and operations having the following properties, (b) the line in the middle organizing the properties as those of a complemented bounded distributive lattice, and (c) the mention at the end of the two-element Boolean algebra as being the simplest example. If their structure article were absorbed into their (more substantive) logic article it would add three lines to the latter, hardly an occasion for a separate article. Hopefully the abstract Boolean algebra article contemplated for en.wikipedia will have something more substantive to say about Boolean algebras than just repeating the laws from the elementary Boolean algebra article.

Probably not so important but the French conception of Boolean algebras departs in minor but interesting details from the usual presentation in English texts. They appear to require top and bottom to be distinct (at least two elements), not an equational property. The signature is presented up front as (T, ⊥, ∨, ∧) rather than (∨, ∧, ¬), with some ambiguity about the status of ¬a in the complementation property: is it an element whose existence is asserted or does axiom 7 introduce ¬ as a unary operation; if the former, what of uniqueness (distributivity makes the complement of a unique but then they should say so), if the latter, is ¬ to be understood as also in the signature? And they retain "bounded" when speaking of complemented lattices (the custom is to drop it as being implied by "complemented" but one could imagine a case for keeping it). Vaughan Pratt 04:08, 2 July 2007 (UTC)

Hmm, the 1=0 question is, as you said, an interesting if minor point. I'm not sure I'd ever noticed that this is not an equational property. Bell does include 0≠1 in his definition in Boolean-Valued Models and Independence Proofs in Set Theory (which, by the way, I've found to be an invaluable reference for many things that don't appear to be strictly related to its official subject matter -- this applies with special force to the wonderful foreword by Dana Scott, which I'm starting to think of as the I Corinthians of set theory, so many excellently phrased insights in such a short space.)

I think 0≠1 is probably standard enough that we ought to include it as a requirement. Allowing {0} as a Boolean algebra is a bit like allowing {0} as a field, or 1 as a prime number (these last two are intimately related, because if {0} is a field, then it's a field of characteristic 1). References that fail to require 0≠1 may very likely simply have forgotten to think of it. If a reference can be found that explicitly admits {0} as a Boolean algebra, then we should mention that there are two possible conventions. --Trovatore 21:47, 6 July 2007 (UTC)

This is much like the debate that greatly exercised the attendants at the one and only "Universal Algebra and Category Theory" conference organized by Ralph McKenzie and Saunders Mac Lane and held at MSRI, Berkeley in 1993. The universal algebraists argued that all algebras should be nonempty on the grounds of (a) tradition and (b) the empty universe is inconsistent with first order logic (which turns out to hinge on whether "number of variables" is a property of individual sentences or whole theories---if the latter then the argument is easily shown to be bogus). The category theorists argued that empty algebras should be possible since otherwise it would mess up a whole raft of useful theorems, starting with the theorem that every variety has an initial object (the universal algebraists and the category theorists are in agreement that every variety whose signature has a constant symbol has an initial object, namely the singleton algebra, but those varieties without constant symbols, e.g. that of lattices, or of semigroups, have an initial object if and only if those crazy algebraists up there in Berkeley would stop objecting to empty algebras).

Among the advantages of allowing the singleton model of any equational theory are (i) the naive definition of "model of an equational theory" has no way of rejecting it other than by artificially introducing a non-equation, (ii) the set of all bit vectors of length n form a Boolean algebra even when n=0 (some people admittedly do get distressed at the idea that 0 is a number), (iii) the theorem that every variety has a final object remains true (why destroy perfectly good theorems with arbitrary requirements you haven't thought through and that serve no purpose?), and so on.

Sometimes people come up with the 0≠1 requirement off the top of their head because they're thinking subconsciously about free Boolean algebras at the time without realizing it. The cardinalities of the first few free Boolean algebras are 2, 4, 16, 256, …. The cardinalities of the first few Boolean algebras are 1, 2, 4, 8, 16, …. If you inadvertently stick in "free" and don't check past size 4, you'll think 1 shouldn't be there, an easy mistake to make.

Whether to allow the one-element field is a nice question. The problem is not that its characteristic is 1 (it can't be because 1 is not a prime, which is your point) but that it doesn't have a single characteristic---the characteristic of any finite field has to be a prime, but since the one-element field is of cardinality p⁰ for all primes p its characteristic can be any prime. The status of the one-element field in field theory is very much like that of 0 in the division lattice, which unlike all other natural numbers has all primes as divisors. While this makes it hard to write 0 as a product of primes, it is still a perfectly respectable element of the division lattice, which is a complete lattice if and only if you allow 0 to belong to it. The one-element field is a perfectly well-behaved field with regard to all laws except the arbitrarily imposed law 0≠1, which serves no useful purpose.

A good counterargument is that although fields don't form a homogeneous variety because of division by zero, they do however have two sorts, one sort of which omits zero. That sort forms a group under multiplication. If you disallow the empty group (as you should if you want groups to form a variety), that forces 1≠0. Now that argument I do like. Vaughan Pratt 07:44, 7 July 2007 (UTC)

The characteristic of the 1-element ring is 1, and calling it a field doesn't change that. Also, if we require that the non-zero elements form a group, then 0≠1 is automatic, and not at all arbitrary. (Edit conflict - Vaughan has now pointed this out himself.)

The clopen subsets of any topological space form a Boolean algebra. If the space is empty, this Boolean algebra has only one element.

So I don't think that allowing 1-element Boolean algebras is similar to allowing 1-element fields. The former appears to be useful, while the latter makes about as much sense as allowing 0-element groups. --Zundark 08:50, 7 July 2007 (UTC)

Actually, that "1 isn't a prime" was not my point. My point was that 1 has sometimes been considered a prime and sometimes not (today, of course, it's standardly not), and that this is really a matter of convention and convenience rather than something that has a right answer. (That's the way I usually feel about "degenerate case" situations.)

We could no doubt have a very interesting discussion on which way the convenience/elegance arrow tips in the case of Boolean algebras, but it's beyond our purview here; we're only supposed to report the standard agreement, if it can be determined. My sense is that {0} is not usually considered a Boolean algebra, but a quick Google search on "trivial Boolean algebra" suggests that it at least sometimes is so considered, so we should probably report both. However, I really do think 0&neq;1 is more standard, and the wording should probably reflect that -- e.g., keep the current wording (which refers to "two distinct elements 0 and 1") but note that some authors do not require them to be distinct, and that they use the phrase "non-trivial Boolean algebra" for the notion here reported. --Trovatore 09:33, 7 July 2007 (UTC)

I looked up the definition of "Boolean algebra" in 17 books to see which ruled the trivial Boolean algebra out and which allowed it in.

OUT:

Birkhoff and MacLane, A Survey of Modern Algebra (Macmillan 1941)

Halmos, Algebraic Logic (Chelsea 1962)

Halmos, Measure Theory (Van Nostrand 1974)

IN:

Birkhoff, Lattice Theory (AMS 1948)

Mac Lane & Birkhoff: Algebra (Macmillan 1967)

Sikorski, Boolean Algebras (Springer-Verlag 1969)

Henkin, Monk & Tarski, Cylindric Algebras I (North-Holland 1971)

Burris & Sankappanavar, A Course in Universal Algebra (Springer-Verlag 1981)

Johnstone, Stone Spaces (Cambridge University Press 1982)

Jacobson, Basic Algebra I (Freeman 1985)

Mac Lane, Mathematics: Form and Function (Springer-Verlag 1986)

McKenzie, McNulty & Taylor, Algebras, Lattices, Varieties I (Wadsworth 1987)

Koppelberg, Handbook of Boolean Algebras I (North-Holland 1989)

Vickers, Topology via Logic (Cambridge University Press 1989)

Dunn & Hardegree, Algebraic Methods in Philosophical Logic (Oxford University Press 2001)

Grätzer, General Lattice Theory (Birkhauser 2003)

Grätzer, The Congruences of a Finite Lattice (Birkhauser 2006)

Birkhoff appears to have switched between 1941 and 1948. Mac Lane's choice is perfectly correlated with how he spelled his surname: when the space went in, so did the trivial Boolean algebra. Halmos was widely read thanks to his easy style and so can be assumed to have been influential on this point; in "Measure Theory" he defines a Boolean algebra to be a Boolean ring that contains an element different from 0, offering no rationale for the distinction however.

Bottom line: Halmos followed, and stuck with, Birkhoff & MacLane's 1941 choice, but no one else (of the books I sampled) did, not even Birkhoff or Mac Lane whether acting separately or together. The reason is clear: it's as bad a choice as choosing to define sets to exclude the empty set. In contrast there are good arguments for ruling out the trivial field, and I withdraw what I wrote previously in support of that. Vaughan Pratt 22:29, 7 July 2007 (UTC)

Could you clarify whether the ones that you marked as "IN", made any remark that explicitly implied they accepted {0}? Such as listing possible cardinalities and including 1, say? I still think some of them may just have not noticed.

I think there are better reasons than you admit for excluding {0}. I think of elements of a Boolean algebra as "generalized truth values"; you can't really "generalize" to "true is false, black is white, freedom is slavery". And you can look at Boolean-valued models for any Boolean algebra B; while that's not very interesting unless B is atomless, it at least works -- but it doesn't work for the one-element algebra. --Trovatore 22:39, 7 July 2007 (UTC)

I've stayed away from this with my naive comment for some time, but here it is. Many formal systems are not provably consistent. For inconsistent systems, the Boolean algebra with 0=1 is a model. I think, in addition to the comments raised above, this justifies including it. Indeed "true" is "false" in an inconsistent system, and I suspect it would be a mistake to exclude inconsistent systems from the study of Boolean logic. Geometry guy 00:22, 8 July 2007 (UTC)

Not quite sure how you're using the word "model" here. An inconsistent theory has no model, in the standard usage of the word "model". --Trovatore 07:13, 8 July 2007 (UTC)

Good point. This brings up a difference between logic and algebra. In logic the truth values are part of the logic and never collapse, whence any theory that would imply they do is deemed not to have a model. In algebra however there are no inequations and the trivial algebra always satisfies every equation. With the logical notion of model it follows that no equational theory can be inconsistent in the sense of logic. Instead one says that a theory whose only model is the one-element algebra is inconsistent in the sense of algebra. This generalizes to categories: a poset is viewed as an inconsistent category in the sense that every nonempty homset is collapsed to a singleton. Vaughan Pratt 08:50, 8 July 2007 (UTC)

Geometry guy is exactly right about the inconsistent case. In the case of a single proposition the truth values are true or false. When you have more or fewer propositions than one, you end up with respectively more or fewer truth values than two. For 3 propositions you get 8 truth values, for zero propositions you get 1 truth value. Your argument that the latter identifies true and false (in the concrete sense of the possible truth values of a single proposition) does not follow when there are no propositions.

Forgetting about Boolean algebras for the moment, no one (to my knowledge) disputes the existence of the one-element algebra in all varieties. (Though as I mentioned earlier, remarkably enough it's a bone of considerable contention whether varieties with no constants include the empty algebra.) In the 1930s Birkhoff was one of the few people alert to the structure of varieties, but today the basic elements of that structure are common knowledge. Today (if not in the 1940s) Boolean algebras are considered to form a variety, and anyone wanting to buck that status has to say so very explicitly or be misunderstood.

In response to your request here are some extracts from the IN books. (My apologies for not giving more, but it’s tedious to look this stuff up.)

Birkhoff 1948: p.156 divides a proof of a lemma up into two cases one of which is for the trivial Boolean algebra.

Sikorski p.8: “A Boolean algebra is said to be degenerate if it contains only one element.”

Henkin p.162: “Note that {0} is a field of sets” (in the context of defining a Boolean set algebra as any field of sets).

Johnstone p.3: “On the other hand we don’t require the elements 0 and 1 to be distinct.”

Jacobson p.474: “The most important instances of Boolean algebras are the lattices of subsets of any set S.” (The empty set is a set, if Jacobson thought that the trivial Boolean algebra was not a Boolean algebra he’d have said “nonempty set S.” A number of other authors omit “nonempty” in similar statements.)

McKenzie p.17: “As an example take A to be the collection of all subsets of an arbitrary set X.” (“Arbitrary” always means “including the empty set and all infinite sets”.)

Koppelberg p.8: “It should be pointed out that the distinguished elements 0 and 1 of a Boolean algebra are not assumed to be distinct – see Example 1.5.” (Example 1.5 is the trivial Boolean algebra, as the power set of the empty set.)

Dunn p.303: “Note that for the purposes of the exercise a Boolean algebra is a non-degenerate one (i.e. one with more than a single element)” which they wouldn’t have needed to say if degenerate Boolean algebras didn’t exist. Elsewhere the context makes clear they don’t proscribe the one-element algebra. Vaughan Pratt 08:56, 8 July 2007 (UTC)

OK, so it certainly appears that we have references for both definitions. I checked Jech, by the way, and he says "at least two elements", and as I mentioned Bell assumes 0≠1. I can't seem to put my hands on either of my copies of Lang at the moment. So we need to mention both conventions. The only question is how to word it. Also articles that reference Boolean algebras should be given a once-over to see if they're assuming one convention or the other without mentioning it, in a way that could lead to confusion.

I hesitate to bring this up, but there is a page, Wikipedia:WikiProject Mathematics/Conventions, where we try to coordinate such things so that authors use consistent conventions across articles. The reason I hesitate to mention it is that there's a certain current of thought that this page could be used to make discussion of the convention issue unnecessary, at least in specialized articles, and I think that's completely wrong. Articles have to stand on their own, even if you don't follow links back to some central article. So if there's ever a chance of confusion in a specialized article mentioning Boolean algebras, we have to mention it there. Still, it might be a good idea for us all to start with the same notion. --Trovatore 19:44, 8 July 2007 (UTC)

To quote from that page, "It should not be assumed that the readers of articles are familiar with the conventions listed here. Therefore, when an article could be misunderstood if interpreted according to a convention that is reasonably current in the mathematical literature, the article should make a note of that fact in situ." In other words the page itself disclaims the current of thought you're hoping to nip in the bud. And appropriately so -- readers of math pages who dropped in at random can't be assumed to be on top of all those conventions, or even be aware that they exist. Standalone is good.

That said, it is better for articles to reflect the state of the art than to be crystal clear about obsolete standards. When conventions change, articles that insist on sticking with the old conventions do a disservice to those readers hoping for up to date information in Wikipedia. If the attempt to modernize "recursively enumerable" to "computably enumerable" has succeeded then article authors should go with that flow. If it is still on probation they should probably stick with the status quo for now. As far as the degenerate Boolean algebra is concerned, its admissibility succeeded decades ago, I can't think of any active lattice theorist or category theorist alive today who'd want to rule it out. I can poll the principal mailing lists (univ-alg@yahoo and categories@mta) to confirm (or refute) this if you want a better sense of that trend. Vaughan Pratt 08:58, 9 July 2007 (UTC)

Ah, but what about set theorists? When you have competing standards in different fields, the matter gets particularly delicate. --Trovatore 16:28, 9 July 2007 (UTC)

Excellent point. Applying it to this thread, even if a living algebraist can be found who still disallows the degenerate Boolean algebra, it would be even harder to find a living set theorist who disallows the power set of the empty set. --Vaughan Pratt 17:01, 9 July 2007 (UTC)

That's not the point. For set theorists, the killer app for Boolean algebras is Boolean-valued models. In fact that's the only context in which they ever come up for most set theorists (I'm an exception).

And making a Boolean-valued model with the trivial Boolean algebra is like forcing with the empty partial order. It's not that it's uninteresting, it's that it doesn't even work. You can't do it at all. --Trovatore 17:16, 9 July 2007 (UTC)

Sorry, I did indeed miss your point. Ok, so I can see that it would be convenient in defining "Boolean-valued model" not to have to say "non-degenerate." However I notice that the BVM definition given at the Encyclopaedia of Mathematics, http://eom.springer.de/B/b016990.htm, is not leaving that to chance where it explicitly says "non-degenerate". This seems less confusing than saying that "Boolean algebra" means something different in Boolean-valued models than it does in say computer aided design, where you might want to view the possible values on an n-wire bus as forming a Boolean algebra of size 2ⁿ even when n=0, a case that could usefully arise in various scenarios. --Vaughan Pratt 03:09, 10 July 2007 (UTC)

I haven't had the time to read through all of the above, but here is a quote from Eric Schechter, Handbook of Analysis and Its Foundations, Academic Press (1997) ISBN 0126227608. Chapter 13: "Boolean Algebras", p. 327:

To call {0} a Boolean lattice reflects a recent trend among algebraists. The older literature imposed the restriction 0 ≠ 1 in any Boolean lattice (and that additional restriction is still imposed by some mathematicians today). … However that restriction complicates the notation and the development of the theory, because with that restriction Boolean algebras and Boolean rings … do not form equational varieties."

Paul August ☎ 17:35, 9 July 2007 (UTC)

Excellent. This can be incorporated almost directly into the article, with source citation. May I assume Equational variety means the same as Variety (universal algebra)? If so, a redirect is in order.  --Lambiam^Talk 20:10, 9 July 2007 (UTC)

Done. ("Equational" is redundant and algebraists tend to avoid it, but that consideration hasn't had much impact on "free gift.")

Eric's reason is the same as mine in the paragraph preceding my list of nine quotes supporting the degenerate Boolean algebra. It didn't occur to me to look for support from an analysis text. --Vaughan Pratt 01:28, 10 July 2007 (UTC)

Based on the evidence presented here, I have no objection to changing our official definition to allow {0}, provided there's a reasonably prominent notice that the other convention exists. At Boolean-valued model I have kept the 0≠1 convention, because allowing {0} in that context is disastrous (and repeating "nontrivial complete Boolean algebra" could get tiresome), but added a footnote about it; interested parties are invited to comment on the wording of the footnote. --Trovatore 05:17, 10 July 2007 (UTC)