Talk:Boolean algebra/Archive 3

Archive 1

Archive 2

Archive 3

Archive 4

Archive 5

Why Wikipedia's treatment of Boolean algebra is a mess

Wikipedia's treatment of Boolean algebra is a mess, as a number of people have complained about above, for the simple reason that a single Wikipedia editor has been insisting for years that There is a genuine ambiguity between the "structure" usage and the "calculus" usage. But since the structure is nothing more than a model of the calculus, and the calculus is nothing more than the theory of the structures collectively, this is obviously inconsistent with Wikipedia's notion of a broad concept article. Boolean algebra as the algebra of the two-valued logic of sentential connectives is a single subject, and Wikipedia should treat it as such. Until this very simple fact is recognized, Wikipedia's treatment of Boolean algebra will remain a mess. --Vaughan Pratt (talk) 08:10, 19 March 2011 (UTC)

I propose that we initiate an RFC.   — C M B J   08:15, 19 March 2011 (UTC)

I would agree with that if we can't resolve this among ourselves. As I see it Trovatore is making the strawman argument that the mass-noun interpretation is formalist in nature. This is not supported by the content of Introduction to Boolean algebra, which treats values (certainly not formalist), operations (formalist only when their interpretation is ignored, which the article certainly does not do), laws (formalist when they are defined syntactically but not when defined semantically---the article gives equal time to both), and models (certainly not formalist, being the promised expansion of the section on values). Only if Trovatore persists with his strawman argument should an RFC be necessary. Which may come to pass given that Trovatore has had his heels dug in on his position for several years now. It would then be interesting to see how he defends his strawman argument. --Vaughan Pratt (talk) 05:18, 20 March 2011 (UTC)

I agree that it's a mess. Nevertheless it is indeed a genuine ambiguity, and I'm not the only one who thinks so.

Yes, certainly, one of the structures is just a model of the calculus. So what? A vector space is just a model of linear algebra, and we nevertheless have separate articles vector space and linear algebra. If they happened to have the same name, we would not merge the articles, nor would it make one of the topics primary. --Trovatore (talk) 08:31, 19 March 2011 (UTC)

Nor would it justify a dab page. I have no objection to having separate articles on the theory and its models when this seems appropriate. What does not seem appropriate is the implication made by a top-level dab page that the models are unrelated to the theory. They are part and parcel of the same subject, and if both the theory and the models happen to have the same name then that is not an ambiguity in the usual sense of the word, it is a reflection of the fact that the models are the models of the theory and that theory is the theory of those models. There should be a single article under that name that defines both the theory and its models as aspects of the same subject, develops both as appropriate for that article, and provides hatnotes and main-article links to related material appearing in other pages, including the separate articles that all of us agree are warranted. Given that you have to define the theory to define the model anyway, it seems weird to be putting the theory in one page while defining the models in terms of that theory in another page, and then creating the misleading impression that the two articles are unrelated in the sense understood at WP:DAB. Separate articles are fine but they should not be linked to by a dab page but by a page that talks about the common elements, in particular the operations and laws, which are the same for both. --Vaughan Pratt (talk) 02:08, 21 March 2011 (UTC)

Yes as I've said before, Trovatore is not alone in thinking that "Boolean algebra" is ambiguous. I do too. Paul August ☎ 19:22, 19 March 2011 (UTC)

This is consistent with your position that the Wikipedia articles Algebra of sets and Field of sets, both started in 2004, the former by you, are on different subjects. But Set algebra redirects to Field of sets rather than Algebra of sets, and I'm sorry but I fail to see the slightest difference between "Algebra of sets" and "set algebra" since both deal with a system of sets closed under union, intersection, and complement. The difference between Algebra of sets and Field of sets is not that they're about different subjects, they're about exactly the same subject. The main difference I can see between the the two articles is that they happen to be pitched to very different levels of mathematical sophistication. This seems to have more to do with the respective backgrounds of the responsible editors than any distinction between "algebra of sets" and "field of sets," which deal with exactly the same concept: a set of sets closed under the Boolean operations (as interpreted for sets). --Vaughan Pratt (talk) 04:56, 20 March 2011 (UTC)

I fell on this acknowledged "mess" just two weeks ago and I was terrified. After reading many parts of the (lengthy) discussions related to the current situation, my analysis is the following:

1. There is a acknowledged genuine concept of Boolean algebras (the structure), as just there are concepts of lattices, Heyting algebras, partial order sets, ... all used to characterize, compare, study various algebraic, ordering, topological properties of structures commonly found in mathematics. This is what the article Boolean algebra (structure) is about.
2. However, it does not seem fully clear what Boolean algebra exactly covers (or should cover).
3. It seems that everyone agrees that Boolean algebra at least covers the study of the equational properties of the two-element Boolean algebra, and in particular how to reason and compute over algebraic expressions taking values in the two-element Boolean algebra. This is what the article Boolean algebra (logic) is about.
4. The first problem arises when it comes to decide whether Boolean algebra covers not only the study of the two-element Boolean algebra (i.e. Boolean algebra (logic)) but also the study of the structure of any arbitrary Boolean algebras (i.e. Boolean algebra (structure)).
5. Trovatore says that Boolean algebra (in the sense described by Boolean algebra (logic)) is only about the calculus and in no way about the study of the inner structure of the variety of Boolean algebras. As a consequence, he defends that there is a genuine ambiguity between the calculus and the structure topics.
6. Vaughan Pratt defends that, because Boolean algebra is precisely about the (equational) theory of Boolean algebras, the Boolean algebras topic is a subconcept of the Boolean algebra topic.
7. I have no strong opinion on what is the best approach (i.e. on whether Boolean algebra is only about the calculus or if it has to be thought in a broader sense that also covers Boolean algebras). In particular, I decided last week to take the broad sense point of view for granted and proposed a short article going in this direction. Only Vaughan Pratt reacted to this proposal. He objected to my algebraically-minded ∨-∧-¬-based definition of Boolean algebras and advocated a semantically-minded definition as "models of the Boolean identities".
8. This shows that there is not only a divergence about what Boolean algebra should cover but also a divergence on how to define Boolean algebras.
9. At the current time, I'm not able to claim that I fully understand Vaughan's point of view. It seems to me that his point is that "we" shouldn't commit to a formulation of the "Boolean identities" using only ∨, ∧, and ¬ but that we should rather see Boolean identities at a more "semantical" level as the collection of identities expressible by means of any arbitrary n-ary Boolean function (including e.g. NAND, ternary conjunction, etc.). Is that a correct understanding? If it is a correct understanding, I actually do not see how to precisely formulate this view, since, in practice, we cannot avoid using a system of notations for representing Boolean functions and the most convenient one (if not the most canonical) is and remains the ∨-∧-¬ system. Moreover I don't see what it means to be a Boolean identity when Boolean functions with infinitely many arguments come into play.
10. In any case, my opinion is that the respect of the different existing views over Boolean algebras has to be addressed by any proposal aiming at unifying the structure and the calculus topics. This is not what Introduction to Boolean algebra (proposed to be the primary topic) currently does: Its primary focus is on the two-element Boolean algebra, with the structure view only showing up abruptly in Section 5. Up to now, I did not see how Vaughan plans to address without undue weight the existence of different views over Boolean algebras in front of his statement that there shouldn't be a disambiguation page.
11. Independently of the above questions, there were also questions about whether Boolean algebras is a minor topic (or subtopic). Some statistics have already been made and my understanding is that if the calculus is more popular (especially due to its use in computer science and electronics), the number of books about the structure is comparable to the number of books about the calculus. If this question is still a concern for some editors, precise statistics should be made. In any case, comparing the relative weight of the calculus and structure topics in external sources is independent of the question of whether there is an ambiguity between them or not.
12. The "mess" is not about the ambiguity, it is about the existence of 5 overlapping articles for defining what Boolean algebra is (plus a disambiguation page). --Hugo Herbelin (talk) 17:39, 19 March 2011 (UTC)

On your point 5: It is true that I have expressed the opinion that the mass-noun sense of Boolean algebra does not include a study of the structures, but I'm willing to be wrong about that. It is not the main point.

The main point is the one I expressed earlier in this section. We have — and I hope everyone agrees that we should have — separate vector space and linear algebra articles. They overlap, but their natural subject matter is quite different.

It's a historical accident that Boolean lattices share their most common name with mass-noun Boolean algebra, whereas vector spaces are not called linear algebra, or if you prefer, you can say the accident is the other way around. Supposing vector spaces happened to be called linear algebras, what would we do? I believe we would need a disambiguation page. --Trovatore (talk) 17:57, 19 March 2011 (UTC)

I agree with you, but having two distinct pages for the calculus and the structure does not mean that we cannot have a short capsule page about "Boolean algebra" that would define the broad sense, explain what the different focuses are, and link to the corresponding subpages (otherwise said, a synthetic directing page instead of a cold disambiguation page). In particular, you did not comment on my proposal above. __Hugo Herbelin (talk) 18:29, 19 March 2011 (UTC)

What is wrong with a straight disambig page? That's the usual solution when two major articles, each likely to be the thing looked for, share the same name. --Trovatore (talk) 18:30, 19 March 2011 (UTC)

Because they have something much stronger in common that just sharing the same name. Even the French disambiguation page that served as model, if I remember correctly, for the English one is clearer on the relation between the two topics. --Hugo Herbelin (talk) 18:40, 19 March 2011 (UTC)

Do you think there needs to be such a lead-in page above linear algebra and vector space? --Trovatore (talk) 18:43, 19 March 2011 (UTC)

Isn't linear algebra precisely, not a lead-in, but some kind of synthetic capsule page for all together vector space and the main other topics that are part of linear algebra? In the same way, couldn't the main Boolean algebra page be a synthetic capsule for all together the Boolean calculus, the Boolean structures, etc. Of course, this assumes that the term Boolean algebra is effectively and commonly used in a broad sense (as linear algebra is) and not only in the sense of Boolean algebra over the two-element Boolean algebra, a question to which I couldn't actually get a clear answer yet.

Also, because of the syntactic ambiguity between the mass noun and the count noun, the link to Boolean algebras would have to be available on such a page from the very beginning of the page, for instance by starting the lead with "Boolean algebra is both a mass noun and a count noun. As a count noun, a Boolean algebra is a kind of algebraic structure whose main examples are propositional logic and the algebra of sets (main page is Boolean algebra (structure)). As a mass noun, it is the branch of abstract algebra which studies these algebraic structures." or something like that. I agree that I'm speculating here, but since other editors expressed the idea that there is no ambiguity between the two topics, I'd like to consider how far the possibility of seeing the both of them as subtopics of a more general concept is feasible in practice. It might be the case also that I just misunderstood what Vaughan said and that for him the structure topic is reducible to the calculus topic, what would then be a denial of the significance of the structure topic. --Hugo Herbelin (talk) 23:44, 19 March 2011 (UTC)

No, I do not see linear algebra as a lead-in to vector space. I think the topics are of parallel importance. (Note by the way that vector space is currently a much better article than linear algebra; not that that really bears on what should be done, but evidently does indicate where authors saw fit to invest effort).

How should linear algebra be improved? To me, it would be natural to say more about eigenvalues and eigenvectors, singular-value decomposition, Hessenberg form of matrices, that sort of thing. It would not be particularly natural to say more about vector spaces there; that fits more at the vector space article.

I hope the analogy is clear to how I see the B.a. articles. --Trovatore (talk) 00:52, 20 March 2011 (UTC)

Now, as to point 12, yes, five is far too many. It does not follow that we need only one. I am for a two-article model. (Two main articles, that is — of course there can always be subsidiary articles on subtopics, as there already are on e.g. free Boolean algebras, on the structure side, and the Boolean satisfiability problem, which I believe Vaughan sees as being part of the subject of Boolean algebra — these are not really part of the problem.) --Trovatore (talk) 18:02, 19 March 2011 (UTC)

I agree also. I don't see how to avoid having eventually 2 defining articles + one main entry point page, the rest being made of subsidiary articles. --Hugo Herbelin (talk) 18:29, 19 March 2011 (UTC)

Had the algebraic structures of Boolean algebra been called "logical spaces" (by analogy with the vector spaces of linear algebra) there would be no debate because there would be no need for a dab page. The question we're having trouble agreeing on is whether referring to those structures as Boolean algebras requires a dab page. No one has proposed this need for the subject of relation algebra, for example, where the same ambiguity arises. More generally I interpret WP:DAB as wanting to avoid dab pages other than when a genuine ambiguity exists. Is it really a genuine ambiguity when both aspects of this subject are defined by the same set of laws? --Vaughan Pratt (talk) 01:06, 20 March 2011 (UTC)

Yes, it is a genuine ambiguity. Surely you don't assert that vector space means the same thing as linear algebra??? --Trovatore (talk) 01:09, 20 March 2011 (UTC)

Surely you don't assert that linear algebra and vector spaces are about different things? They're about the same thing, and had the subject been called "vector spaces" instead of "linear algebra" I find it hard to believe that anyone would seriously suggest the need for a dab page. As it is, I don't understand why "linear algebra" and "vector spaces" need distinct articles given that they're about the same thing. Had the vector space article not mentioned linear transformations I could see room for difference, but it has a section on it. The operations of a vector space are linear combinations, and the associated subject uses the same operations. Furthermore the same laws govern both. If that's a "genuine ambiguity" then the same reasoning would justify a huge proliferation of dab pages, since one can point to lots of distinct concepts in every article. If they're unrelated concepts then a dab page is warranted, but if they're simply aspects of the same topic, in this case sharing the same operations and the same laws, I don't see how that's in the spirit of [[WP:DAB]. --Vaughan Pratt (talk) 03:46, 20 March 2011 (UTC)

I think it is clear to most people what the difference between an article entitled vector space and one entitled linear algebra should be. The current vector space article, at a quick glance, looks excellent, and just about what I think it ought to be: A reasonably tidy explanation of the general concept, followed by lots of ways that the concept arises, and why it's important. These are not strictly limited to the language of linear algebra, but include other stuff like topology.

The linear algebra article, on the other hand, could use quite a bit of fleshing out. But in very different ways from the vector space article. I would say a lot more about eigenvalues and eigenvectors, singular value decomposition, matrix theory stuff. I hope the demarcation is generally clear. Roughly speaking (but only roughly speaking; please don't try to turn this into some mathematical definition) the vector space article is about the structures, whereas the linear algebra article is about the elements of the structures.

That's very closely analogous to how I see the two main articles that I think should be pointed to by the Boolean algebra disambiguation page. --Trovatore (talk) 04:04, 20 March 2011 (UTC)

As it happens the demarcation is not as clear as you claim. You say that eigenvalues, eigenvectors, and matrix belong in the linear algebra article, but those are all in the vector space article, in which "eigen" (for eigenvalue or eigenvector) occurs 23 times and "matri" (for matrix or matrices) occurs 27 times. It is clear that the editors responsible for linear algebra and vector spaces do not see the clear demarcation between these subjects that you do, and I wouldn't know where to draw the line myself since they're both about essentially the same subject. Likewise the very first section of Introduction to Boolean algebra is not about the calculus but about the values assumed by the variables, which always reside in a Boolean algebra; that short section covers all Boolean algebras while making the point that the two-element Boolean algebra plays a central role, much as the additive group of integers and its finite quotients play a central role for abelian groups. Just as modules over the ring Z can be identified with abelian groups, so can modules over the ring Z/2Z expanded with the constant 1 be identified with Boolean algebras, and the two-element Boolean algebra is central to the subject in many other ways as well, mathematically, pedagogically, and computationally. --Vaughan Pratt (talk) 04:37, 20 March 2011 (UTC)

I never claimed it was a razor-sharp demarcation. Nevertheless it appears very clear to me. There are things that naturally come up in an article called vector space, and others that come up naturally in one called linear algebra, and they overlap but are not the same. Both topics are worthy of an article. Does anyone but Vaughan disagree with me on this? --Trovatore (talk) 04:44, 20 March 2011 (UTC)

Linear algebra begins "Linear algebra is a branch of mathematics that studies vector spaces." The second paragraph of vector spaces begins "Vector spaces are the subject of linear algebra." That plus your claims that certain topics belong in one but not the other, which are refuted by those articles, shows that this distinction is in your own mind. The distinction may be in other peoples' minds as well, but unless some clear consensus emerges as to just where and how to draw that distinction, the evidence for your claimed "clear demarcation" is unconvincing. --Vaughan Pratt (talk) 05:29, 20 March 2011 (UTC)

What do other people think? To me it's clear; vector space is about the structures, linear algebra is what you do in the structures. --Trovatore (talk) 05:50, 20 March 2011 (UTC)

Obviously linear algebra (a field of study) and a vector space (a mathematical structure) are different things — just as topology and a topological space are different things. And all seem worthy of separate articles. Equally obvious, these things are intimately related with much overlap. Paul August ☎ 17:41, 20 March 2011 (UTC)

---

Hugo, let me respond to your points 9, 10, and 11. Point 11 incorrectly represents my position on what should go in the primary-topic article. First, Boolean operations with infinitely many arguments are not mentioned in any of the articles Boolean algebra (structure), Boolean algebra (logic), or Introduction to Boolean algebra --- in all of those articles, all Boolean operations are assumed to take only finitely many arguments.

Second, it is not mathematically important (though it is arguably culturally important) what basis, i.e. set of basic operations, one starts from, other than that it be complete. A basis is complete when every Boolean operation is representable as some term. For each finite n ≥ 0 the n-ary Boolean operations can be paired up in the usual way with the functions from 2ⁿ to 2, where 2 denotes the set {0,1}. In my reaction to your article I expressed no preference for how the Boolean operations are introduced. The article Boolean algebras canonically defined is so titled because it starts with the general concept of a Boolean operation without committing to a basis in the beginning, as appropriate for an article pitched at a relatively high level, and the axiom system in that article reflects this by consisting of three inference rules and a single axiom schema uniformly applicable to all Boolean operations. The article Introduction to Boolean algebra on the other hand, which Hans Adler, CMBJ and I had been proposing as the primary topic, starts from ∧, ∨, and ¬ as the basic operations for consistency with other introductions to the subject and then subsequently introduces the derived (non-basic) operations ⊕ (exclusive-or) and → (implication). I for one am therefore completely on board with having the primary topic start from the ∧ ∨ ¬ basis, since that's how it's currently presented in that article.

What I did react to about your article (apart from the historical remarks, which were not intended as an endorsement of any operation basis) was how the equational theory is presented, namely whether semantically (as the identically true equations) or syntactically (as the consequences of some set of basic equations constituting an axiomatization). However my reaction did not in the end take sides on that but instead offered justifications of both. On this point the proposed primary article is presently completely neutral: the two alternatives are introduced in the same sentence at Introduction_to_Boolean_algebra#Completeness, where the concept of completeness of a set of laws is introduced in as even-handed a way as I could. If people have a strong preference for one way over the other instead of presenting both in the same sentence I have no objection.

Regarding point 10 on "abruptness," I would have no objection to moving the section on diagrammatic representations to later in the article, or even a separate article, since it's a side issue, and likewise the duality principle subsection. This would move the definition of Boolean algebra up to immediately follow the section on completeness of a set of laws, which is the first point in that article or any other article on the topic where it is possible to define Boolean algebras. Even if one were to view the whole point of the primary topic as being solely to define the concept of Boolean algebra, that definition cannot come any earlier than some presentation of a complete set of laws. Your own definition of "Boolean algebra" is just as "abrupt:" you give a complete set of laws, and then "abruptly" define a Boolean algebra to be a model of that complete set. While I can't speak for Hans or CMBJ, I'm open to the question of when and how completeness should be addressed, whether syntactically, semantically, or both at once. However there is no other way of defining a Boolean algebra than to first give some complete set of laws.

How does point 11 bear on whether to have a dab page? WP:DAB does not impose any statistical test on the aspects of a broad concept article: some aspects may be more popular than others, but they're still aspects. --Vaughan Pratt (talk) 00:35, 20 March 2011 (UTC)

---

Vaughan, thanks for clarifying some of the points. I'm not sure I understand you completely, so, here are some extra remarks and asking for clarification.

• Does the Boolean algebras canonically defined article define Boolean operations "without committing to a basis"?

I don't agree: it starts from the (infinite) basis made of all truth tables. For sure, it is the largest and "most-semantical" basis we can think of, but it is a basis.

• About the single axiom schema uniformly applicable to all Boolean operations from Boolean algebras canonically defined:

I don't see why the theory made of this axiom scheme should be considered of a different nature than any other complete equational theory for Boolean algebras such as Peirce et al axioms for the {∧,∨,¬} basis. For sure, reasoning on the ^mf_i-basis makes that all axioms are uniformly described by a single scheme (A1) what makes this particular pair (basis,axioms) remarkable. Moreover it emphasizes the ability to adopt a very abstract approach for defining Boolean algebra what makes this pair (basis,axioms) twice remarkable. But from the point of view of defining Boolean algebras, isn't it just a pair (basis,axioms) among the others?

We apparently all agree that the pair ({∧,∨,¬},Peirce et al axioms) is most convenient in practice. So, from a presentational point of view, I would present the (^mf_i,A1) at the same level as the other remarkable pair made of Sheffer stroke and its single axiom, i.e. as one of the alternative presentations giving insights about what Boolean algebras are.

By the way, I would propose that we create a page about the bases, as it seems that there is quite a lot of material about that already, especially in Boolean algebras canonically defined.

• Just to be sure, do I understand correctly that when you are talking about the semantical definition of Boolean algebras, you mean a definition based on (^mf_i,A1)? If not, what is your definition? In Boolean algebras canonically defined, you say: "Boolean algebra is a set and a family of operations thereon interpreting the Boolean operation symbols and satisfying the same laws as the Boolean prototype" but this definition do first require to choose a pair (basis,axioms). Then, the basis and axioms to be understood here are the ^mf_i and A1, correct?
• In your 3rd paragraph above, I don't understand why you say that my presentation of the equational theory is "syntactic" rather than "semantical". Which sentence are you talking about? How would you reformulate this sentence so that it becomes "semantical"?
• About the paragraph Completeness of Introduction to Boolean algebra:

I'm sorry but I have some difficulties to understand what is meant in this paragraph. By definition, a Boolean algebra is a set with operations ∧, ∨, and ¬ satisfying the axioms, hence doesn't the "semantic sense" of completeness considered in the paragraph hold by definition?

Or is it meant that the equational theory of Boolean algebras is complete in the sense that whenever you add an equation that is not already derivable, then 0=1 gets provable?

As for what is called syntactic completeness, I don't understand why it is called syntactic. Isn't it just the completeness (no qualifier) of the equational theory wrt the two-element model? I.e., isn't it just the standard statement that the given syntax appropriately captures the semantics, as the next sentence seems also to say?

• By abruptness, I meant that up to Section 5, the topic is mainly presented as about the two-element Boolean algebra while I feel Section 5 as brutally changing the focus to the study of all Boolean algebras in general. I don't see such a brutal change of perspective in my text. Maybe "abrupt" is not the right term I wanted to use, "without continuity" or "without global unity" are maybe clearer. It might also be a subjective feeling and I would be curious to know the opinion of others.

As I already said, typical sentences that contributes for me to this lack of unity are: "Much of the subject can therefore be introduced without reference to any values besides 0 and 1" and "Boolean algebra deals with the values 0 and 1". The use of some computer-science connoted vocabulary such as "value" also contributes for me to withdraw the subject into an article about the two-element algebra.

• By the way, in calling the page Boolean algebras canonically defined, is there a reference to the notion of canonical generic algebra in universal algebra? If not, why did you call it canonical (no explanation is given)?
• Finally, coming to the main question, I still don't know what are your proposals for solving the Boolean algebra "mess". --Hugo Herbelin (talk) 17:22, 20 March 2011 (UTC)

---

Thanks for such a detailed response, Hugo, which is very helpful in getting us to common ground. You raise eight questions/issues, which I'll respond to in order. The first three are about Boolean algebras canonically defined which has no obvious bearing on the dab page question but I'll answer them anyway.

1. I fully agree that the set of all Boolean operations constitutes a basis, and moreover an infinite one. Another natural infinite basis would be complement together with all monotone Boolean operations. In practice finite bases are used, although my systematic naming system (which is really nothing more than naming each operation by its truth table) raises the possibility of an infinite basis that is nevertheless usable in practice, since it is easy to work with truth tables when organized systematically.
2. The axiom system A1 in Boolean algebras canonically defined is not part of the definition of "Boolean algebra," it is offered there simply as an interesting way of proving all identities when the basis consists of all Boolean operations: to prove s = t, simply apply A1 repeatedly to evaluate s and t and if they evaluate to the same "atom" then infer s = t. One difference from more conventional axiom systems is that axiom scheme A1 denotes an infinite set of equations, exactly one for every Boolean operation. Another difference is that the terms on the right hand side of the equation need a little decoding in order to express them as conventional terms. Other than those two things, yes the infinitely many instances of A1 constitute an (infinite) axiom system just like the others (and R1-R3 are common to all equational axiom systems and hence could be omitted as implicit). And yes one could define a Boolean algebra as any model of A1, but a syntactic definition like that would be much less natural than the semantic definition given in the article.
3. Axiom A1 plays no role in the definition of "Boolean algebra". In that article a Boolean algebra is defined as a structure with operations ⁿf_i as you say, but a law of Boolean algebra is simply any equation in those operations satisfied by the two-element Boolean algebra with those operations (namely all finitary operations on 2), and a Boolean algebra is any model of those laws. [End of answers about "canonically defined."]
4. An equational theory is presented syntactically when it is specified by a subset of the theory sufficient to generate the rest of the theory, namely as its deductive closure. It is presented semantically when it is specified as the theory of some class of structures, for example as the theory of the two-element Boolean algebra (as the only member of a singleton class). Your syntactic presentation is not a single sentence, it is a list of ten equations which you say is complete in the sense that it proves all tautologies. But if tautologies are the criterion for what you're willing to allow as the laws of Boolean algebra then wouldn't it be a lot simpler to take the laws to be the tautologies themselves, rather than writing down equations until you can show you have enough to prove every tautology? This avoids the long list, completeness becomes a triviality, and questions about why that axiomatization in particular and not something shorter don't come up. But as I said I didn't take sides on that and am not suggesting you change your definition since it is common practice even today to define a Boolean algebra to be a complemented distributive lattice (though I am looking forward to the day when people start to consider it an outmoded superstition).
5. Bear in mind that neither the concept of an axiom system, nor the term "tautology," nor the concept of a Boolean algebra has been defined up this point, all we've done so far is list some laws. Do we need to list some more or can we stop now? One criterion for stopping would be that we now have enough laws to prove everything we're interested in being able to prove. That's a syntactic criterion. The other criterion is that our laws are now sufficient to "bar all monsters" assuming we can recognize monsters somehow. That's a semantic criterion. The section in effect opts for the former by defining what we want to be able to prove as the tautologies; we can then define a monster to be any structure supplying a counterexample to some tautology. (Alternatively we could have defined a Boolean algebra to be a homomorphic image of a field of sets, an equivalent definition even without choice, and then defined the laws of Boolean algebra to be those satisfied by every Boolean algebra, not just the two-element one, but that's the same thing in this case.) However I can see that this could well be confusing given that the concept of a Boolean algebra is not defined immediately, so it might be clearer to just drop the semantic criterion. Thanks for raising this point.
6. The section Introduction_to_Boolean_algebra#Values takes the same position as Donald Monk (who has worked extensively on Boolean algebras during his half-century career) in his Stanford Encyclopedia article cited above, namely that Boolean algebra is the algebra of two values. This is also the position taken by Boole in his 1854 book, where he says "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." The intent of the Values section was to capture in less flowery language what Boole is saying there: the variables of Boolean algebra might be valued as sets, as Boole considers elsewhere in the book, or something else, but the laws will be the same as when the values are 0 and 1. The Values section does this in its second paragraph. If you feel that Boole expressed this more clearly than the Values section currently does I'd be happy to word it closer to what Boole wrote, or something more in accord with what you feel should be said in the first section concerning the values that Boolean variables can take on. Perhaps the two paragraphs of the Values section could be interchanged so it begins by saying that variables are valued in Boolean algebras, and then talks about why {0,1} plays the large role it does in the subject of Boolean algebras (but look at Monk's article again---he starts with two values and goes from there). Incidentally the notion of value of a variable does not come from computer science, it's been used in algebra for centuries and long predates abstract algebra which itself began a century before "variable" entered the programmer's lexicon. Variables have values in the Platonic understanding of mathematics where the subject is actually about something (namely some model) but not in the formalist understanding which is mere symbol crunching.
7. Originally Boolean algebras canonically defined was just a tentative article under a different name to try out some ideas. But people seemed to like the article, and Jon Awbrey brought up the question of what to call it, which was discussed at some length at Talk:Boolean_algebras_canonically_defined#Towards_a_genuine_article. As you'll see there I wasn't terribly interested in exactly what the article should be called, and I'm still not given that a reasonable eventual use of this article is to be cannibalized for one or more articles on advanced subtopics of the primary topic "Boolean algebra."
8. My proposal for solving the mess is to have an article about the subject of Boolean algebra that covers the main aspects that would be of interest to someone reading about the subject for the first time, with links to more specialized and/or advanced topics on the structures, Stone duality, axiom systems, diagrammatic representations, complexity, etc. Hans Adler was the first to propose, back in 2008, that Introduction to Boolean algebra was sufficiently non-introductory as to serve that role, and this seemed reasonable to me (though maybe the slower-paced parts could pick up the pace more, with details moved to their own articles when appropriate). Your article might be more suitable, but we're not in a position to judge candidates as long as Trovatore continues to insist that the only reasonable way to distinguish the subject of Boolean algebra from Boolean algebras is a dab page. His argument as far as I've been able to understand it is that "Boolean algebra" as a theory is so different from "Boolean algebra" as an object that they're not aspects of a single topic but different topics. But since even Trovatore agrees that a Boolean algebra is just a model of the theory, it's hard to imagine the editors who formulated the criteria in WP:DAB viewing the theory and its models as so different as to need a top-level dab page. While I don't like having to escalate such questions to an RFC as CMBJ suggested, if we can't agree on what WP:DAB implies for the question then we may have to take it to the WP:DAB editors for their more expert opinion. Trovatore's argument would be more compelling if he could offer an example of a dab page used at top level to disambiguate the models of some class from its theory. --Vaughan Pratt (talk) 00:53, 21 March 2011 (UTC)

Well, the organization of our articles should not depend on whether it requires a dab page; that's a navigational detail. There is no general "avoid dab pages if possible" rule.

So the question is whether there are two topics, neither subordinate to the other. It is clear to me that there are. Once that is decided, then the question is whether one of them is "primary", in which case there would be a hatnote to the other, or whether neither is, in which case you need a dab page. --Trovatore (talk) 02:18, 21 March 2011 (UTC)

---

Vaughan, I can unfortunately not give a detailed answer now as I have a busy week starting on, so I will just write a few short comments.

I don't think that the question of having or not a disambiguation page is a precondition to judge whether the "introduction" is liable to serve a the primary topic article.

My opinion is that the introduction currently commits too strongly to a "model of the two-element domain identities" view of Boolean algebras while in order to serve as a unifying page, it would have to at least equally support the "structure" point of view (I say at least, because I would not be surprised that the "structure" view be in fact the most general view about Boolean algebras). Such as it is written, I don't see how the introduction can be generally accepted as the main article, what makes the question of renouncing to a dab irrelevant at the current time. As suggested above, it might be useful to request comments from the outside, whatever the form this process takes.

I also think that there is no reason to have a separate article "canonically" about the structure beside the existing "structure" article. I consider their difference as basically a difference of point of view and that they ultimately have to be merged.

I'm learning a lot in trying to understand your view. I hope we will eventually be able to "get to common ground" and I'm glad that you share this hope too (I'm sorry to have to postpone the discussion for a few days). --Hugo Herbelin (talk) 11:29, 21 March 2011 (UTC)

Notes

Why two articles?

Trovatore feels that two articles on Boolean algebra are needed, with some indefinite number of further articles expanding on subtopics in these two articles.

"Main articles" on subtopics of a topic are not controversial, and I'm all for lots of articles on subtopics of the topic of Boolean algebra. What is under debate here is whether "Boolean algebra" has a root topic, or must begin with two root topics having no common ancestor.

I am unable to see any rational basis for the separation into two subjects that Trovatore is arguing for. In Trovatore's mind Boolean algebra is two subjects, in my mind it is one. Trovatore, please explain what fundamental distinction makes it impossible to combine your proposed two articles, each entitled to be titled "Boolean algebra" if it weren't for the other article, into one. After three years of debate on this difference between us I am still unable to see it. I have not seen a single compelling argument in defense of your position, all of them have been easily shot down. --Vaughan Pratt (talk) 06:00, 20 March 2011 (UTC)

If you can't see the difference between a vector space and linear algebra, I don't know if I can help you. I hope other people see it. Your position looks ideological to me. Some sort of Mac Lane/Lawvere kind of thing maybe? I haven't really read either of them enough to know whether that's close at all, but in any case it doesn't seem to be the dominant Gödel/Tarski paradigm that I assume most of us accept. --Trovatore (talk) 06:17, 20 March 2011 (UTC)

What we're debating is not whether there's a difference but whether the difference warrants a dab page disambiguating "Boolean algebra" as a theory and "Boolean algebra" as a model of that theory. The idea that theories have models is universal to mathematics and should not need a dab page to distinguish them when they're simply two aspects of the same topic. Any article on the count-noun depends on the theory for its very definition. My guess is that the editors of WP:DAB would not consider that difference worthy of a top level dab page, but if we can't agree on it ourselves the only solution will be to ask them. --Vaughan Pratt (talk) 01:00, 21 March 2011 (UTC)

Ah, you beat me here. I actually have a better answer than my somewhat irritated response above, which I may have pulled the trigger on too soon.

I think the real important reason is that (let's use the other case to start with, to avoid the linguistic repetition which may confuse the issue), vector spaces are the setting for linear algebra, but they are important outside of linear algebra. Therefore linear algebra is not really the broad topic.

Specifically, note that the vector space article spends a fair amount of time on Banach spaces. Banach spaces are vector spaces, so I think that's fine.

But Banach spaces are not linear algebra! They're functional analysis. At least, those are the categories I use, and I hardly think I'm alone.

Similarly, a lot of my research is on Boolean algebras, but the work itself is not Boolean algebra. The work is set theory. An article on the structures called Boolean algebras should not be limited to Boolean algebra.

(By the way, this resolves a doubt that I had had about whether there should be separate group theory and group (mathematics) articles. I had not previously thought that the argument was as strong there, because there's a good argument that linear algebra should focus on methods of calculation in vector spaces, but "group theory" is not generally thought to be about calculation inside groups. I am now clear that there should be, because the article about groups need not be limited to group theory.) --Trovatore (talk) 01:51, 21 March 2011 (UTC)

All this seems extremely reasonable. How is any of it an argument for "Boolean algebra" being a dab page, when it could just as well be an article on the operations and laws common to both the theory and the models, along with both meanings and how they stem from this common root, and links to the various articles on the topics you envisage and other topics besides, e.g. complexity, set theory, and so on? Making it a dab page creates the misleading impression that there is no common basis sufficient for an article, merely a need to list unrelated meanings of the term. --Vaughan Pratt (talk) 03:21, 21 March 2011 (UTC)

I'm glad you think it's reasonable. I'm not sure what part of the argument is missing. To flesh it out: There are two distinct topics, one analogous to vector space, which naturally includes topics that are not linear algebra, and one analogous to linear algebra, which obviously doesn't. If one of these is a "broad topic", arguably it would be the one analogous to vector space, because it includes things the other article doesn't, but I have no desire to take it that far.

Now, if the two articles would not naturally take the same name, there would be no reason to consider a dab page. But they do. That fact should be considered last; it's a navigational detail that should not influence the organization of the articles, but only their naming. (There is nothing wrong with having a disambig page; it's not like it should be considered a cost.) --Trovatore (talk) 04:39, 21 March 2011 (UTC)

Sorry, why should it be considered last? "Boolean algebra" is the subject of the Boolean tautologies in the operations ∧ ∨ ¬. These tautologies have models which not terribly surprisingly are called Boolean algebras, and are the objects of Boolean algebra as a theory. Conversely the tautologies have an equivalent definition as the equations holding of all Boolean algebras, i.e. each defines the other. One would only consider the connection last if it were merely a coincidence that these two concepts have the same name. If you were a marriage counselor instead of a mathematician you'd be judged a marriage wrecker by your fellow counselors, you're trying to force a dab page by denying all logical reasons to group Boolean algebras and Boolean algebra together when they define each other. Why are you so intent on there being a dab page when there are excellent reasons for a single article treating the clear connection between these two subjects? I just don't get it. --Vaughan Pratt (talk) 06:19, 21 March 2011 (UTC)

Do you understand why I think there should be separate vector space and linear algebra articles, neither subordinate to the other? The issues are the same, except for the accident of naming, or do you disagree with that? --Trovatore (talk) 06:22, 21 March 2011 (UTC)

I understand. However (a) I don't see any dab page there, and (b) if there were then given how intimately "linear algebra" and "vector spaces" are related I'd prefer to see such a dab page replaced with an article about that relationship. A dab page for "linear algebra" and "vector spaces" doesn't seem in the spirit of WP:DAB given that linear algebra claims to be "a branch of mathematics that studies vector spaces" while vector spaces claims to be "the subject of linear algebra." Why would you want to divorce these with a dab page when this is obviously a marriage made in mathematical heaven? This is not incompatible with separate main articles on the two subjects, just as couples don't need to be employed by the same company. --Vaughan Pratt (talk) 09:58, 21 March 2011 (UTC)

There isn't any dab page because they happen to have different names! This is entirely inessential. We should decide the organization of the articles completely without regard to whether that organization happens to require a dab page; that's a detail of navigation. --Trovatore (talk) 10:17, 21 March 2011 (UTC)

Now you're talking. While you've been insisting on a dab page some of us have been working on the appropriate organization of the articles. Care to take a break from whether a dab page is needed and join us in that discussion for a bit? --Vaughan Pratt (talk) 20:17, 21 March 2011 (UTC)

I have been arguing the appropriate organization of the articles. That has been my main point through this whole discussion! The dab page is merely a consequence of that. --Trovatore (talk) 21:50, 21 March 2011 (UTC)

The terms Abel's theorem, Abelian group, Admissible rule, Airy function, and Algebraic integer, to mention only a few, are genuinely ambiguous. Yet these are not disambiguation pages, but honest articles, with a hat note to other meanings of these terms. The topic dealt with at each of these articles is the primary meaning, the one you would generally expect to be the topic of an article with any of these titles. In such cases, we should not use a dab page, per WP:PRIMARYTOPIC. While the term "Boolean algebra" may be ambiguous (a non-count noun or a count noun), the primary meaning is quite clearly that of the non-count noun, as in "George Boole was a mathematician whose algebra of logic, now called Boolean algebra, is basic to the design of digital circuits." This is somewhat independent of the question whether we should have a separate article Boolean algebra (structure) for the count-noun meaning.  --Lambiam 14:34, 21 March 2011 (UTC)

Ok, we now have two arguments against a dab page. Lambiam's is that the mass-noun meaning is clearly the primary topic under "Boolean algebra," whence there should be a primary-topic article rather than a dab page. (Given that Trovatore has argued that the count-noun meaning is clearly the primary topic, the rest being trivial according to him, I would take that as a third argument against a dab page using the same logic as Lambiam's.)

My own argument is that Boolean algebras are the algebraic structures of Boolean algebra, and Boolean algebra is the subject of Boolean algebras. This connection is obscured by making a dab page to one article on Boolean algebra and a separate article on Boolean algebras. Such a dab page would imply that the two concepts have too little in common to make them the subject of a common page making the point italicized above. In fact quite a lot is common to both the mass-noun and the count-noun. You can't have either without the operations ∧ ∨ ¬, which are common to both. Furthermore you can't have either without the Boolean laws, regardless of whether presented as the tautologies or as the axioms of a complemented distributive lattice, which are also common to both. Those connections alone would already serve Wikipedia readers much better than a dab page, and they can be developed much further in the same page while continuing to be about both the mass-noun and the count-noun at the same time. A dab page can't do that; instead it forces those connections to be repeated in the two articles it points to. Is repeating those connections instead of putting them in a single article treating the mass-noun and the count-noun at the same time worth whatever is gained by a dab page? I just don't see any gain comparable to avoiding this repetition, which has the further downside of making Wikipedia look amateurish---people will ask why we didn't think to combine the overlapped material into one place.

Since we appear to be singularly unsuccessful in persuading Trovatore that there is anything at all wrong with his point of view, and he is equally unsuccessful in getting us to see why the obvious fact that mass-nouns aren't the same thing as count-nouns (which no one is disputing) justifies a dab page instead of an article, it's looking more and more likely that we'll have to start getting outside help in communicating the respective arguments of both sides to the opposite side. --Vaughan Pratt (talk) 20:17, 21 March 2011 (UTC)

Vaughan, do you similarly feel the lack of a lead-in article to vector space and linear algbra? Is there anything different about that case, other than the lack of a name to give to such an article? --Trovatore (talk) 21:50, 21 March 2011 (UTC)

More background

Once upon a time there was a WikiProject Logic/Boolean algebra task force, and in considering what needs to be done, and what the issues are beyond what is it already referred to above, it may also be helpful to review that task force's talk page.

Part of the problem (but of course not the whole problem) is ownership, to varying degrees, of articles related to this area. But as I see it, the crux of the issue is that we have not been able to reach agreement on identifying the primary audience of an introductory and elementary article (or the introductory and elementary part of a more comprehensive article) on "Boolean algebra". Are they "engineers who need to learn about this"? Or should we primarily aim at "a member of the 'general public', not being a member of any of the more special groups interested in Boolean logic"? Or can both audiences be served by one introductory article?

While I'm not per se opposed against an RFC, I am very sceptical about its chances of being effective unless we agree in advance what questions we should pose to this oracular device, questions that should have a clearly defined and limited set of possible answers.  --Lambiam 12:45, 21 March 2011 (UTC)

Couldn't agree more. This is why I've continued to discuss the question with Trovatore, in order to boil things down to (ideally) a single sentence in support of each side of whether "Boolean algebra" should be a dab page or a primary topic. My sentence would be that since a Boolean algebra is an algebraic structure satisfying the laws of Boolean algebra, this is sufficient to justify treating "Boolean algebra" as a primary topic with its own article (for which suitable candidates already exist), independently of whether there are additional articles separately on each of the structures and the laws (for which suitable candidates also already exist). When Trovatore is satisfied that he has the strongest case he can make, and remains convinced in the face of the counterarguments that a dab page is the best way of serving Wikipedia readers looking up "Boolean algebra," at that point we may be ready to declare a complete stalemate and solicit opinions from those with more experience in interpreting WP:PRIMARYTOPIC and with resolving stalemates of this kind amicably.

I also agree there are ownership problems related to Boolean algebra, involving somewhere between three and five pages and as many owners, but I'd like to see this dab page disagreement resolved one way or the other first. --Vaughan Pratt (talk) 19:16, 21 March 2011 (UTC)

The question of whether one of the two topics is primary, in the sense that you would have a hatnote to the other rather than a dab page, is somewhat separate from the question of whether there are two topics. I feel much more strongly about the second point than I do about the first. --Trovatore (talk) 21:52, 21 March 2011 (UTC)

I'm sorry I did not find Wikipedia_talk:WikiProject_Logic/Boolean_algebra_task_force earlier (I did not realize that the Boolean algebra task force page had a talk page actually). I thought that Vaughan decided to go for the introduction page mainly on his own, and the task force talk page shows that I was completely wrong.

Armed with this new encouraging view about the introduction, what is the residual room for manoeuvre in the article? For instance, will it definitively commit to the two-element structure (more particularly will the section on truth tables remain in Section operations or will it be delegated to the logic page, or at least will it be clearly presented as just an example of application of B.a. among others)? And will there be a hatnote linking to Boolean algebras so that those readers who are looking for the structure can find what they are exactly looking for easily? (and maybe a hatnote to Boolean logic too?) Is there some project to improve the global unity of the article and make it does not look too much as a superposition of different topics? More generally, how to contribute to the introduction page?

Quoting Lambiam: Identifying the primary audience: Are they (1) "engineers who need to learn about this"? Or should we primarily aim at (2) "a member of the 'general public', not being a member of any of the (3) more special groups interested in Boolean logic"? Or can both audiences be served by one introductory article? I would eliminate (1) which not only is not the goal of wikipedia afaik but would be quite restrictive as a main page. I would naively say that what should be targeted is (2) but all together with a clear and easy access to specialized pages for those groups (3) interested in either Boolean logic, Boolean algebra structures, or maybe also propositional logic. --Hugo Herbelin (talk) 23:22, 21 March 2011 (UTC)

I am not just sure what you are getting at here. I don't see any clear consensus at that page (note that it's been more or less inactive for some years) for whether there should be a separate introduction or not. However, if there were, it would surely not be "primary topic". --Trovatore (talk) 23:31, 21 March 2011 (UTC)

Draft for RFC

I've drafted an RFC on this consuming issue, which you all can admire/improve/edit relentlessly here. If users Trovatore and Vaughan Pratt can agree and sign off on the wording, I'll put it up below on this talk page.  --Lambiam 21:52, 21 March 2011 (UTC)

Without signing off on it (I gave it only a cursory reading) my initial impression is that it's fairly nice work, for the limited question of which, if either, of the two topics is primary. It would be just fine if everyone reading it were a mathematician. Maybe non-mathematicians will follow it; maybe not. I have trouble predicting that sort of thing, so maybe we should ask a couple of them? --Trovatore (talk) 22:05, 21 March 2011 (UTC)

Seems to be a fair an accurate presentation of the issue. (I've taken the liberty of moving this discudssion to its own section) Paul August ☎ 23:01, 21 March 2011 (UTC)

Isn't there a fourth alternative? I mean, there is something I still don't understand well in the current structure of the Boolean algebra pages, which is: is there a difference between Boolean algebra in general (including e.g. reasoning in an algebra of sets or in the Lindenbaum algebra) and Boolean algebra over the two-element (i.e. reasoning in the two-element domains, as we do for instance in electronics). If I'm asking, it is because I don't know the answer. Has someone an answer?

If I look at Boolean algebra (logic) it is clear that it is basically about bits. If I look at the introduction, the target is moving from day to day but it still looks like it is primarily about bits in spite of some occasional excursions to the general case.

So, isn't there a place for a fourth alternative which is having as primary topic neither the two-element calculus, nor the structures, but a true page about Boolean algebra in general? (in particular, it is not made clear in the rfc proposal if the case "primary meaning of a calculus" means "primary meaning of a calculus applicable to any Boolean algebra" or "primary meaning of a calculus over 0 and 1".)

Thanks in advance for any help. --Hugo Herbelin (talk) 23:52, 21 March 2011 (UTC)

I don't think any clear description of what "Boolean algebra in general" is has been given. Do we agree (Vaughan seemed to, if I understood him correctly) that not all study of Boolean algebras is in fact Boolean algebra? --Trovatore (talk) 00:04, 22 March 2011 (UTC)

By definition of "Boolean algebra" in the sense of structure, the "algebra of logic" calculus applies to any Boolean algebra – if it doesn't apply to some structure, then that structure is apparently not a Boolean algebra. I'm not sure what you mean by "calculus over 0 and 1". The calculus also allows variables, but 0 and 1 are the only constants in standard Boolean algebra. However, the two-valued Boolean algebra has a special position. Specifically, if you restrict yourself to only considering equations of two Boolean terms (built from variables and the operations and constants of the algebra, nothing else), then such an equation follows from the Boolean axioms precisely when it holds universally in the two-valued model. Moreover, no other such equations hold in any other non-trivial model. (In the trivial one-point model, 0 = 1 and all other equations hold.) See Introduction to Boolean algebra#The prototypical Boolean algebra and following sections.  --Lambiam 01:00, 22 March 2011 (UTC)

If I understood you correctly, we are drawing different conclusions from the very same observation. Let me rephrase what I understood to see if it is what you meant:

If you take an equation built from variables and the operations and constants of the algebra, nothing else (e.g. over variables, ∨, ∧, ¬, 0 and 1), then the following are equivalent:

1. this equation holds universally in the two-valued model (where the basis is interpreted in the standard way)
2. or, this equation holds universally in the algebra of subset of some given set (where the basis is also interpreted the standard way)
3. or, more generally, this equation holds universally in my favorite Boolean algebra.

Since, indeed, to say that another such equation holds in some other non-trivial model, you would have to consider equations that refer to objects that are not part of the theory you're talking about (for instance, on the subsets of {1,2,3}, you have the non-derivable equation {1,2} ∩ {2,3} = {2} but it is out of the set of equations we are talking about).

Then, relying on (1), Introduction to Boolean algebra#The prototypical Boolean algebra says that the two-element algebra is protypical. But the same reasoning could be done from (2) too which would lead to the statement that the algebra of subset of a given set is prototypical too. So, something is wrong here (by the way, the paragraph "This observation is easily proved as follows ..." in this same section is not clear as it seems to consider equations that are not part of the theory).

This is precisely the debate I have with Vaughan for a while and which leads for him to defend the point of view that Boolean algebras are just models of the Boolean identities while I defend the point of view that there is no reason to focus on a particular Boolean algebra and that Boolean algebras have primarily to be seen as models of an equational theory (only one of these models being the two-element domain).

I'm unfortunately not an expert in abstract algebra (and not either in Boolean algebra actually), if you could cite me an external reference that explains in which sense the two-element algebra could be thought as more prototypical than say, the subsets of {1,2,3}, I would be interested. --Hugo Herbelin (talk) 08:25, 22 March 2011 (UTC)

One more word... What is special about the two-element model is not that "The laws satisfied by all nondegenerate concrete Boolean algebras coincide with those satisfied by the [two-element] Boolean algebra" as the Introduction says but rather that the two-element domain 2 is the only domain of which the n-ary functions are fully characterized by the language and axioms of Boolean algebras, in the sense that for any Boolean algebra basis and axioms, there is an interpretation of the basis over 2 such that for every function from 2ⁿ to 2, there exists a unique representative of the function over the basis modulo the axioms.

Otherwise said, what any other (non-trivial) Boolean algebra A misses is not laws, as the introduction (wrongly) says, but functions, in the sense that for any interpretation of the basis, there are n-ary functions over A that cannot be expressed from the operations of the basis. --Hugo Herbelin (talk) 11:31, 22 March 2011 (UTC)

I didn't write these passages, and I'm not sure that the word "prototypical" is meant in another than an informal sense: two-valued logic is the original, and also the most common, application area of the calculus. The two-valued Boolean algebra is mathematically special in that it is the initial object in the category of Boolean algebras. If you want your favourite Boolean algebra to be considered prototypical, you need to identify it (up to isomorphism); for example, the Boolean algebra of the subsets of the set {1..42}.  --Lambiam 14:11, 22 March 2011 (UTC)

As I've written elsewhere on this page, my position is none of the ones on Lambiam's list. What I propose is something just as symmetric as Trovatore's dab page with respect to the two meanings of "Boolean algebra", but differing from it in being more than simply a list of links. Instead it is an article about the common elements of the two meanings. Those common elements are (i) the operations and (ii) the laws.

The subject of Boolean algebra is critically dependent on the operations, without which terms cannot be defined, and it is also dependent on the laws, which are part and parcel of the subject.

At the same time the concept of a Boolean algebra is equally dependent on the operations, without which there is no signature. And it is also dependent on the laws, since a Boolean algebra is a model of those laws and therefore remains undefined until the laws have been established.

So what I would propose is an expansion of Trovatore's proposed dab page with enough information about the common elements of "Boolean algebra" and "Boolean algebras" to permit a first-time Wikipedia visitor to the subject to get enough of an idea of what the subject is about in order to decide which if any meaning they are in search of. For many readers I would not be at all surprised if they benefited equally from both meanings, having never known either meaning before coming to Wikipedia.

If all the dab page contains is links to two articles, the reader wanting to find out what "Boolean algebra" refers to will pick one at random, and with 67% probability find that they then need to pick the other one. 33% will correctly pick what they need the first time, 33% will pick the wrong one and then realize they wanted the other, and 33% will want to understand both meanings before they can decide which one is what they really had in mind and therefore will need to try both (some of whom may turn out to just be interested in the complete story of both Boolean algebra and Boolean algebras). The latter two cases have to visit both links, which my arithmetic makes out to be 33% + 33% = 67%.

This seems less efficient than arriving at an article that gives the common elements of the two meanings and then explains each meaning in terms of those common elements, along with links to more detailed articles about each meaning. This allows the reader to make an informed choice as to whether they prefer one of those meanings over the other, so they can jump to the relevant article, or find both meanings equally interesting and want to dig deeper into the elements common to both, which can continue to be part of the article "Boolean algebra." --Vaughan Pratt (talk) 07:42, 22 March 2011 (UTC)

Do you also feel there needs to be an article about the common elements of linear algebra and vector spaces? --Trovatore (talk) 08:01, 22 March 2011 (UTC)

No, because there is no dab page where a reader has to pick at random. Someone who wants to learn about linear algebra will be told by that article. Someone who wants to learn about vector spaces will be told by that article. Someone who wants to learn about "Boolean algebra" in the absence of the information as to which is meant will need to backtrack until they find out which is meant. --Vaughan Pratt (talk) 08:22, 22 March 2011 (UTC)

OK, well this may be the heart of the disagreement. I consider it completely irrelevant whether there needs to be a dab page or not. We should decide on the organization of the articles without considering that. Then, and only then, we decide whether the collision of names requires a dab page, or a hatnote on one of the articles. --Trovatore (talk) 08:26, 22 March 2011 (UTC)

Yes, I already agreed with you about that above so this should not be in dispute. We're currently talking about the organization of articles under the heading of the ambiguous term "Boolean algebra," how are unambiguous terms like "linear algebra" and "vector space" relevant here? --Vaughan Pratt (talk) 08:37, 22 March 2011 (UTC)

I am saying that the collision of terms is irrelevant to what the organization should be. Figure out what are the natural topics to treat, and then figure out how readers get there. I do not see them as living comfortably in a single article. One is an object, and the other is a field of study! The sorts of articles you write on fields of study are entirely different from the ones you write on objects. --Trovatore (talk) 18:58, 22 March 2011 (UTC)

(to Vaughan) Is the treatment you prefer essentially different from the current treatment at Introduction to Boolean algebra (which, I'd say, goes somewhat beyond what one would expect to be covered in an introductory article)?  --Lambiam 08:05, 22 March 2011 (UTC)

Only in one respect: the first (very short) section is biased towards the count-noun and therefore needs to be moved elsewhere so that the sections on operations and laws come up first.

But you raise an interesting question as to how much should be in an introductory article. "More" could serve two competing goals: if used to cover more material it is less introductory, but if used to explain the basic material in more detail it is more introductory. By design Introduction to Boolean algebra starts with the latter (a fast article would not give so many presentations of the two-element Boolean algebra), but gradually drifts towards the latter (lots of stuff on diagrams, Boolean algebras, etc. etc.). There is much room for tuning this article to best serve these two competing objectives of clarity and coverage. --Vaughan Pratt (talk) 08:22, 22 March 2011 (UTC)

Well, then I disagree with you, since I firmly believe that the sense of "logic calculus" is the primary meaning, in the sense that that is what readers are most likely looking for; in fact, I am pretty sure the vast majority of readers searching for information on the topic are completely unaware that the term can also have this other meaning. I also don't see how one can write a good lead that treats both meanings on an equal footing – and don't forget that when there is a version you are happy with, other editors will come and change it one way or another, almost certainly skewing it in one or the other direction. But I have tried to amend the draft version to offer your preference as an option on an equal footing.  --Lambiam 10:00, 22 March 2011 (UTC)

Lambiam. I'm actually a counter-example to your assumption. I came on WP to find some information about Boolean algebras and it took me some while to understand that Boolean algebra had also another meaning and that what I was looking for in the jungle of Boolean algebra pages was at a page called Boolean algebra (structure) (by some unfortunate and extraordinary coincidence, I was looking at the page precisely at the time CMBJ replaced the dab by the introduction).

Maybe would have been it different if I had been educated in an English-speaking country, but in my case, when I first learned the English expression "Boolean algebra" (in the context of my professional job, at university), it was about the structure and not the calculus. --Hugo Herbelin (talk) 11:54, 22 March 2011 (UTC)

You would be a counterexample if my assumption had been that all readers searching for this term are searching for information about the calculus. I only stated that I expect this to be the case for the vast majority.  --Lambiam 13:34, 22 March 2011 (UTC)

To see what the primary meaning is, all you need to do is to google ["boolean algebra" -wikipedia] and look for the first 20 results or so; the vast majority is clearly about the calculus.  --Lambiam 14:42, 22 March 2011 (UTC)

Oh, don't worry, I'have no real stake in this. I just wanted to relativize things a bit. --Hugo Herbelin (talk) 17:27, 22 March 2011 (UTC) (slightly revised afterwards)

What I'm getting out of this discussion is a better sense of the importance of the two-element Boolean algebra. A computer is a perfect example of the calculus at work in the sense envisaged by Lambiam. But the implementation of the computer uses individual bits in a typical Boolean circuit.

This creates a nice opportunity to avoid seeming to pick favorites. "Boolean algebra is the algebra of propositional logic when the values of the propositions are limited to 0 or false and 1 or true with no intermediate value. Its terms are built from variables and the constants 0 and 1 using the operations x∧y of conjunction, x∨y of disjunction, and ¬x of negation or complement, for example x∨(x∧y). Its laws are those equations between terms that hold identically; for example x∨(x∧y) = x regardless of whether each variable has value 0 or 1 and hence is a law of Boolean algebra. And its models, called Boolean algebras, are those algebraic structures with operation symbols ∧, ∨, and ¬ interpreted in any way whatsoever provided only that that interpretation satisfies all those laws."

In nine words tThe first sentence avoids playing favorites by saying that Boolean algebra is an algebra, which is what Lambiam wants, for the purpose of two-valued logic (in contrast for example to intuititionistic logic which requires more than two values to give a counterexample to excluded middle and double negation laws), which in effect is speaking about the two-valued Boolean algebra. Hugh wants to make the point that the complemented distributive lattice axiomatization is complete, but what does completeness mean if not judged by the two-element Boolean algebra? There really is no way of getting around explaining Boolean algebra (assuming one is going to mention completeness up front when listing equations, as Hugh does) without getting involved from the beginning in both the subject as algebra and at least one Boolean algebra.

Computers aren't only about the two-element Boolean algebra however. A 32-bit ALU uses 32 bits in parallel for the L part, which gives a nice example of a Boolean algebra bigger than the two-valued or one-bit one. This example permits clarifying "excluded middle," which can be confusing at first when 01 seems to be intermediate between 00 and 11. "Excluded middle" does not mean excluding 01, rather it means x∨¬x = 1. In a two-bit ALU, 01 ∨ 10 = 11 in a Boolean algebra where 11 is the value of the constant 1. This gives a nice opportunity to distinguish between values and constants; perhaps this could be done earlier by consistently using different fonts for constants and values so that readers don't blur the notions together at any point. --Vaughan Pratt (talk) 18:38, 22 March 2011 (UTC)

Vaughan, you asked: "But what does completeness mean if not judged by the two-element Boolean algebra?" The point is that to judge completeness, you don't need a two-element algebra, you just need that the algebra contains at least the two elements 0 and 1 (what indeed it has). Let A be an arbitrary non-trivial Boolean algebra and let p = q be any true equation of A over ∧, ∨, ¬, 0, 1, x1, ... ,xn. There is no doubt that p = q is equivalent by equational reasoning to r = 1 where r is ¬p∨q ∧ p∨¬q. Let's reason by induction on n. If there is no variable, then, because 0∧0 = 1∧0 = 0∧1 = 0∨0 = ¬1 = 0 and 1∧1 = 1∨1 = 1∨0 = 0∨1 = ¬0 = 1 holds in any algebra, r is equationally provable to either 0 or 1, and since the algebra is non-trivial and the equation true, r is provably equal to 1. Now, if n>0, let's use equational reasoning to factor out x₁ in r. One obtains x₁-free expressions r₁ and r₂ such that r is provably equal to x₁∨r₁ ∧ ¬x₁∨r₂. Since the equation is true, by instantiating x₁ by the 1 of the algebra, one obtains that the equation r₂=1 is true and by instantiating x₁ by the 0 of the algebra, one obtains that the equation r₁=1 is true. By recursion, we can turn these equations into equational proofs of r₁=1 and r₂=1. It remains to build a proof of x₁∨r₁ ∧ ¬x₁∨r₂ = 1 from proofs of r₁=1 and r₂=1. I guess that you will agree that equational reasoning is provably compatible with the operations and that this last step is possible.

Otherwise said, completeness is not specific to the two-element domain and being true on the two-element domain is equivalent to being true on any domain. --Hugo Herbelin (talk) 22:41, 22 March 2011 (UTC)

Maybe I'm missing something obvious, but I don't see how what you have shown here, theoremhood of true equations of the specific form r = 1, has theoremhood of true equations in general as an easy consequence. It seems, though, that with some obvious modifications the inductive proof can be applied directly to the equation p = q.  --Lambiam 09:37, 24 March 2011 (UTC)

(ec)I agree with Lambiam about this. During my research for the BA task force I realised that the majority of books on Boolean algebra(s) isn't just about Boolean algebra in the sense of Boolean logic, but moreover it is explicitly directed to engineers. I think mathematicians are by far overrepresented among Wikipedia editors, and engineers are by far underrepresented, at least relative to each other. Or if they edit, I guess most of them edit topics unrelated to work and certainly not related to the foundations of their field.

Now I don't think there is much difference between "Boolean algebra" and "Boolean logic". Therefore a reasonable structure could be to have Boolean logic as a high-school level article for engineers, and Boolean algebra as a slightly more advanced article that covers Boolean algebras as well as Boolean logic as their equational theory.

Maybe I am wrong and "Boolean logic" and "Boolean algebra" cannot be used as synonyms in this way. But if I am right, then we could decide, here on Wikipedia, that we want to standardise our usage of these terms: We would be speaking about Boolean algebras, and their study in the most general sense, which would be (generalised) Boolean algebra. And their equational theory would be Boolean logic. Hans Adler 19:04, 22 March 2011 (UTC)

It may be the case that the article on the subject matter should be "primary" purely in the WP sense that it would be the one the search term goes directly to, with a hatnote to the other. I'm not that happy about it, because people who link the term Boolean algebra are likely to be mathematicians and are likely to be intending the structure, and because frankly I don't have much of a problem with writing mathematics articles for mathematicians. Call me an elitist if you like.

However that solution ("primary" article on the field of study, hatnote to the structures) is far better than writing a single article that conflates the two senses. That's just wrong. You write different articles on fields of study than you do on objects. --Trovatore (talk) 19:12, 22 March 2011 (UTC)

OK, so how about this:

Boolean algebra (main article) is the field of study that is concerned with true, false, and, or, not -- but interpreted as algebraic operations. The (equational) relations that hold between the various operations are studied in Boolean logic, and that article will have a lot of detail for beginners and for engineers. A mathematical structure that satisfies all the right equations is a Boolean algebra (structure).

Boolean algebra becomes the main article for the field. Boolean logic retains its function but is cleaned up. Boolean algebra (structure) unchanged. Hans Adler 19:35, 22 March 2011 (UTC)

Well, all the articles need cleanup, and they should be merged into two (or at most three, allowing space if necessary for a low-level "intro" article). I don't see any reason to have a separate Boolean logic from the field-of-study Boolean algebra article.

Note that I still prefer a disambig page; as I say it's awkward that math articles are likely to link Boolean algebra and it will be going to the wrong place most of the time. --Trovatore (talk) 19:42, 22 March 2011 (UTC)

Not if the first paragraph defines "a Boolean algebra" accurately while linking to Boolean algebra (structure). In the lead paragraph I proposed above, the operations and laws are defined and then "a Boolean algebra" is defined. If "a Boolean algebra" is what the reader wanted, they'll see that and the link in the first paragraph, click on that link, and in the same number of clicks as with a dab page they'll be where Trovatore wants them to be. Everyone else will learn what Boolean algebra is as a subject, and will also learn that there is such a thing as a Boolean algebra. My account does not conflate the notions of the algebra and an algebra, both are defined as notions with distinct meanings. --Vaughan Pratt (talk) 20:08, 22 March 2011 (UTC)

There is nothing wrong with the field-of-study article mentioning, and giving a definition of; I don't object to that at all. However it should not pretend to be the "first" article on the objects.

Boolean algebras are an object studied by people who aren't doing Boolean algebra. An article on the subject matter does not particularly serve those people. It's not about number of clicks. It needs to be understood that the structure article is logically of equal status to the field-of-study article; the latter is not an "ancestor" of the former. --Trovatore (talk) 20:16, 22 March 2011 (UTC)

I really don't understand what you are trying to achieve. Mathematicians are not going to be confused, ever, so long as what we come up with remotely makes sense. It's everybody else who are going to be terribly confused if they look for "Boolean algebra" and find an article that only makes sense for mathematicians. Or a disambiguation page that makes them wildly click around to find out whether the thing they want is a "structure" or a "calculus" (both words that won't make sense to them, and we are not going to put it in better words because that's just impossible).

And overall, Wikipedia doesn't have a consistent structure so that when you know all the articles in one topic you can guess the organisation of articles in a similar topic. To a large extent our organisation depends on accidents of language. That's one reason why different language versions organise articles differently. Encyclopedias grew out of dictionaries. Hans Adler 20:29, 22 March 2011 (UTC)

I fully agree with Hans. And I would go even further: equality is what I'm proposing, in case that's a real concern. When defining either Boolean algebra as a subject or Boolean algebras as structures, one must first talk about Boolean operations, and then about Boolean laws. What I'm proposing is an article that defines both the algebra and the structures in a single paragraph that also introduces the operations and the laws. Both are given as links to the main articles serving them, exactly as in a dab page. Making the connection between the two concepts is better than a plain dab page because it provides the same two links that the dab page would, but explains the similarities and differences between the two concepts so that readers who start out not knowing which meaning of "Boolean algebra" they wanted (having no familiarity with the concept) have more of a basis for making the right choice than a dab page would have offered them.

Furthermore some readers will still not know which they want after reading just that paragraph, and further treatment of both Boolean algebra the subject and Boolean algebras the objects can be offered to give them a fuller picture of both. Many readers may never want more than to understand what the two concepts are and what's the difference between them, and therefore won't need to follow either link. This approach does not give preference to either topic, any more than would choosing their order in the dab page give preference to the first one listed. --171.64.78.120 (talk) 20:41, 22 March 2011 (UTC) --- oops, --Vaughan Pratt (talk) 20:46, 22 March 2011 (UTC)

Lambiam, how is the 1st sense from your RfC draft different from propositional logic? I'm not well versed in these issues (compare to some of the others editing here), but the mapping between the two is also of interest, and covered in books like [1]. Tijfo098 (talk) 21:13, 24 March 2011 (UTC)

For one thing, proofs using the axioms of Boolean algebra use purely equational reasoning: substitution of equals for equals, plus reflexivity, symmetry, and transitivity of equality. All axioms and theorems are of the form Φ₁ = Φ₂, in which the Φ_i are terms built from variables and the Boolean operations and constants. Propositional logic, on the other hand, uses inference rules such as Modus Ponens, and does not have a concept of equality. However, there is a connection: the theorems Φ₁ = Φ₂ of Boolean algebra correspond precisely to the subset of theorems of (standard) propositional logic of the form Φ₁ ↔ Φ₂. So, interpreting provable equivalence as equality, propositions form a model of Boolean algebra. However, proofs in propositional logic look completely different from proofs in Boolean algebra. Also, while propositions are an important model, they are not the only model.  --Lambiam 22:31, 24 March 2011 (UTC)

So what you're describing at "1st sense" is basically the equational logic fragment of propositional logic? Is that even remarkable for an article? Tijfo098 (talk) 00:40, 25 March 2011 (UTC)

I'm not sure what you mean by "the equational logic" fragment of PL, since PL has no equations. My personal opinion whether something is remarkable or not is not relevant for the question whether we should have an article about Boole's "Calculus of Logic", historically the first formal system of mathematical logic, but somehow lots of books have been written about it,[2][3][4][5][6][7]..., many of which deal with applications, and various existing Wikipedia articles are devoted to it under a variety of titles: Boolean algebra (logic), Introduction to Boolean algebra, Boolean logic, comprising together more than 100,000 bytes – but with much conceptual duplication.  --Lambiam 01:13, 25 March 2011 (UTC)

Rephrased after I gave my logic a refresh. I can provide WP:RS for that statement, but I suspect it's not necessary in present company. Do you see why I'm baffled by the RfC choice (and the multitude of articles)? Tijfo098 (talk) 03:16, 25 March 2011 (UTC)

Unless you want to allow theories in uncountable languages, a concept many people are not familiar and comfortable with, I think you should write "every countable Boolean algebra", after which I don't particularly see the point of the statement. (At least one editor working in this area is an expert in counting uncountable Boolean algebras.) What I also don't understand is your use of the word "However"; if C is a logical consequence of A, then I wouldn't write: "A; however, C."  --Lambiam 07:21, 25 March 2011 (UTC)

Ok, I admit then that I probably don't understand these issues well enough to contribute non-noise to this debate, so I'm withdrawing from it. Good luck with the RfC. Tijfo098 (talk) 10:35, 25 March 2011 (UTC)

The way forward now

We are repeating the points and arguments made extensively before elsewhere on this page and other BA talk pages, and at the BATF talk page. I think everyone agrees (1) that there are several audiences with different needs, (2) that there is a lot of material that has to end up somewhere, (3) that it should be reasonably easy to navigate to such material for readers who come to the subject through a different entry point, but (4) that not all material should be included equally in all articles. Usually, we can solve such things by the usual Wikiprocess of gradually improving the articles. For Boolean algebra(s), however, that doesn't work because there is a mess of overlapping articles for which we can't even agree what the articles are supposed to be about. The way forward, now, is to reach a decision on at least one issue, one that should be relatively simple: the disposition of the page Boolean algebra. Since we (rather obviously) are not going to reach agreement here, I think an RFC is in order, and no one yet has argued against it (although I've expressed my conditional scepticism above). But most editors venting their opinions here have thus far not indicated that their preferred approach is represented in the draft I prepared, or, if not, made sure it is included. So is the consensus here that the main purpose of the page Boolean algebra is to offer a talk page forum on which we can argue to our hearts' content without ever reaching a conclusion?  --Lambiam 08:24, 25 March 2011 (UTC)

I am less concerned about what happens to the page Boolean algebra per se than I am about making a clear distinction between the object and the mass-noun sense. That's why, even though my first choice is to have Boolean algebra be a dab page, I offered to agree to make the mass-noun one be where you get to with the undisambiguated term, in exchange for the clear separation. --Trovatore (talk) 09:42, 25 March 2011 (UTC)

Yes, but that compromise does not work if another editor is also less concerned about what happens to this page, but only as long as it doesn't make a clear distinction. Apparently you can live with A1 and A3, and are opposed to A2. But what about our esteemed emeritus colleague from Stanford? I don't even know if he could live with any of the four listed alternatives.  --Lambiam 11:07, 25 March 2011 (UTC)

His most recent comments sounded to me as though he found my proposed compromise more or less acceptable. Look through the most recent ones and see of you don't get the same impression. --Trovatore (talk) 15:46, 25 March 2011 (UTC)

Well, then we don't need to have an RFC, since it that case, as far as I can see, the compromise is acceptable to everyone. So I'll revert then to the last version by CMBJ, and we can proceed from there.  --Lambiam 16:55, 25 March 2011 (UTC)

The last version by CMBJ is not the compromise, no. At least not by itself. We need lots of merging to get down to two articles, one on the field of study and one on the structures. From the field-of-study article there should be a hatnote to the structure article (not to Boolean algebra (disambiguation), which should probably go away). --17:01, 25 March 2011 (UTC)

I would say it's time to revert to the last version by CMBJ because it meets Trovatore's requirement that it make "a clear distinction between the object and the mass-noun sense." That move is the logical first step in cleaning up the mess, so it makes sense to make it now. Note incidentally that this step will not result in Boolean algebra becoming "the field-of-study article" that Trovatore keeps talking about since we don't yet have such a thing. When someone writes one, if ever, we can discuss whether that should be merged with or replace Boolean algebra, but for now the proposed revert will result in Boolean algebra defining both the field and the object in its first paragraph. --Vaughan Pratt (talk) 18:37, 25 March 2011 (UTC)

I think that Boolean algebra (logic) is perhaps slightly better suited, in its current state, to be the mass-noun article, but I don't see an awful lot to choose between them. The only real difference seems to be that B.a.(l) spends more time on applications. I think it should be merged into the current Boolean algebra, and then with the hatnote that is reasonably acceptable. Except of course that we still have to figure out what to do with Boolean ring, Boolean logic, and "canonically". --Trovatore (talk) 20:24, 25 March 2011 (UTC)

Possible compromise

Here is something I could probably live with, and seems to address a lot of other people's concerns. Let's see what people think.

• The field of study becomes "primary" in the purely WP sense of taking the undisambiguated name. It's not to be thought of as primary in a logical sense.
• A hatnote to be placed at the top, saying
  • This article is about the field of study. For the mathematical object, see Boolean algebra (structure)
• The field-of-study article may certainly (and probably should) treat the structures to some extent, along the lines that you would expect vector spaces to be treated at linear algebra, but should not pretend to be the "article of first resort" for the structures.
• Boolean logic and Boolean algebra (logic) (if the latter still exists) to be merged into the field-of-study article.
• Boolean ring and the "canonically" article to be merged into the structure article, but much reduced, or else treated later in the article than order-theoretic and model-theoretic aspects such as atomicity, freeness, completeness, saturation.
• In general, the structure article to emphasize aspects of the objects themselves, rather than their definitions or signature.

This preserves the parallelism with other articles and does not condition the organization itself on the linguistic accident. On the other hand, it addresses the perceived need to avoid confusing non-mathematicians, at the cost of having to police links from mathematics articles to make sure they point directly to the structure article if the structure is what is intended. --Trovatore (talk) 21:21, 22 March 2011 (UTC)

I think you're giving up more than you need to. Earlier you asked for equality and I proposed a way of getting equality that seemed to me to meet everyone's needs except those who insisted that one topic take priority over the other, which previously consisted of you and Lambiam. You wanted the structures to take priority while Lambiam wanted the subject to take priority. Your present idea of a "compromise" seems to be to capitulate completely and let the subject take priority by being the primary topic of the article "Boolean algebra." I was proposing something closer to your dab page concept that made the two topics equal while meeting the concerns Hans and I are raising about dab pages being confusing for newcomers, especially those who don't already understand the distinction between a theory and its models. --Vaughan Pratt (talk) 21:41, 22 March 2011 (UTC)

(None of what I'm suggesting is inconsistent with hatnotes, btw, any number of which are fine by me. I'm just pointing out that the article on Boolean algebra need not take a stand on which meaning is "primary." Maybe it should take a stand, but I'll let others argue that since I'm not the one who expressed a desire for strict equality, that was you and I was merely pointing out that it was possible to accommodate you. My only objection is having novices arrive at a dab page and be unable to decide which link to choose for lack of background.) --Vaughan Pratt (talk) 21:52, 22 March 2011 (UTC)

Well, the capitulation is only on the navigational question, which is less important to me than the organizational one. As I said, "primary" here is purely in the navigational sense. --Trovatore (talk) 22:15, 22 March 2011 (UTC)

I was going to write but you all were faster. I support the analysis of Hans and its suggestion of having 1) a page "Boolean logic" talking about two-valued Boolean algebra, targeting engineers and typically made from a simplification of the current logic page 2) a page "Boolean algebra (structure)" based on the current one, on the Boolean ring page and on the "canonically" page [late addition: actually, I'm not so sure about merging Boolean ring, unless maybe WP policy considers it is too short, I find that its motivation and positioning are clear and it does not seem to really overlap over B.a.] 3) a page on "Boolean algebra", field of study, approached from the mathematical point of view along lines we are currently discussing [Added 21:24, 24 March 2011 (UTC): at second thought, I'm not sure that the word "field of study" is appropriate here, the term "elementary algebra" looks to me closer to what "Boolean algebra" is].

Trovatore's proposal is good for me, and probably the most reasonable one. However, as said above, it seems to me clearer if we can get two Boolean algebra pages, targetting two kinds of audience (and hence to have two hatnotes on the WP-primary field-of-study article, one to the logic page and the other to the structure page). --Hugo Herbelin (talk) 22:26, 22 March 2011 (UTC)

Actually I think I would prefer to base the "structure" page more on the current Boolean algebra (structure), with "ring" and "canonically" merged into it (and cut down). I'm not saying the current one is in very good shape. But "canonically" spends too much time on definitions, and "ring" is again different mainly in the signature. I'd rather give a definition, not worry too much about whether it's the best, and get quickly into structural rather than logical issues. --Trovatore (talk) 03:50, 23 March 2011 (UTC)

Regardless of what an article titled "Boolean logic" might say or who it might serve (engineers, economists, peace corps volunteers, whatever), how do you propose to have an article titled "Boolean algebra" that states that its axiomatization of the concept is complete (as your sandbox article does) without talking about the two-element Boolean algebra? The two-element algebra is fundamental to the field of study, quite apart from any interest digital logic designers might have in it, starting with the concept of completeness but also in many other regards. --Vaughan Pratt (talk) 23:11, 22 March 2011 (UTC)

There are several questions. Regarding the result of completeness of the equational theory with respect to the semantics, my point is that it holds for all B.a. and the two-element domain is not special here (see message above at 22:41, 22 March UTC). Now, the question that I did not address in my proposal and that you're asking, I guess, is how do we motivate the definition of Boolean algebra(s), i.e. what are we trying to model with Boolean algebra(s)? I think we can say that the primary motivation is to modelize propositional logic. Then we can start having different points of view. We can think Platonistically and say that formulas are either true or false. This allows to justify the operations of Boolean algebra as a set of operations that is complete for describing all n-ary functions over true and false, and, in a second step, to justify the equational theory as a minimal set of equations needed to equate all syntactically-different algebraic representatives of a given n-ary function. Alternatively, we can think algebraically (i.e. without mentioning values at all) and take the connectives and the lattice order as granted (the lattice order is p⊢q where ⊢ is some system of proof e.g. sequent calculus). Then, the equations come as a characterization of the relation p⊢q and q⊢p. The advantage of the algebraic point of view is that it applies directly to non-classical logic, say intuitionistic logic, by considering instead Heyting algebras. It also scales easily to predicate logic, where we can take countable ∨ and ∧. (Whether the Platonistic point of view scales easily to predicate logic is unclear to me but you probably know this problematic quite well.). Then, I have nothing against talking about the two-element domain of course. What I would find biased is to commit to a view that reduces the study of Boolean algebra(s) to a study of the two-element Boolean algebra. So, this is still rough but I would typically suggest sentences like "Boolean algebra emerged as a model of equational reasoning over propositional logic. Its most common and motivating interpretation is as a two-value model with values true and false, but its scope extends in practice further, for instance as a model of reasoning over the fields of set, where it gets similar to the algebra of sets." --Hugo Herbelin (talk) 02:36, 23 March 2011 (UTC)

Sorry, not following. The completeness proof you give at 22:41 depends crucially on the two-element domain. What do you mean when you say it's "not special?" Without it how would you even define completeness, let alone prove it? The two-element domain is fundamental to Boolean algebra, for that reason as well as others, such as which Boolean algebras are the subdirect irreducibles (compare that with the subdirectly irreducible Heyting algebras, which are to intuitionistic logic as Boolean algebras are to classical logic). --Vaughan Pratt (talk) 06:24, 23 March 2011 (UTC)

Is it possible you two are using different notions of completeness – deductive versus semantic?  --Lambiam 09:32, 23 March 2011 (UTC)

No because it's a theorem of equational logic that they're the same thing, just defined in two different ways. Deductive completeness of the axioms for a complemented distributive lattice is the property that the congruence closure of the substitution instances of those ten equations is the set of all Boolean laws. Semantic completeness of those axioms is the property that every model of those ten equations is a model of the Boolean laws.

As I understand Hugh, he is defining the Boolean laws to be what I'll call the set BA of laws that hold of all Boolean algebras. I'm defining them to be the set B2 of laws that hold of the two-element Boolean algebra. Obviously BA is a subset of B2 (the more algebras, the fewer laws they all satisfy). Correct me if I'm wrong, Hugh, but I believe your notion of completeness of these laws is that B2 is a subset of BA, that is, every law holding of the two-element algebra holds of every Boolean algebra, however you're defining that notion (presumably as the class of models of the ten equations). If that weren't the case, some tautology of propositional calculus would be neither a syntactic nor a semantic consequence of the ten equations, in which case the propositional calculus motivation for BA would vanish because it would then be weaker than B2. But requiring BA to be the whole of B2 is an admission that the two-element Boolean algebra is the standard by which Boolean algebra axiomatizations are to be judged.

This is just one of several central roles played by this important Boolean algebra. Since it is by far the easiest Boolean algebra to understand, talking about all Boolean algebras before talking about that one is not well motivated either pedagogically (it's the simplest possible example and easily the most familiar one) or with regard to applications, among which propositional calculus and digital logic are two incredibly important ones. --Vaughan Pratt (talk) 00:09, 24 March 2011 (UTC)

You're talking about the field-of-study article, right? I'm against belaboring the two-element algebra in the structure article. Naturally it should be mentioned early, but I want to get quickly to structures that are actually interesting as structures. --Trovatore (talk) 01:13, 24 March 2011 (UTC)

The structure article should not need to say anything at all about the two-element Boolean algebra, other than perhaps to define a Boolean algebra as any model of the theory of the two-element Boolean algebra if you decide to do it that way instead of with one of the long-list-of-equations approaches, or to include it among the examples at the beginning depending on how self-contained the structure article needs to be, or to relate it to the concept of a field of sets. --Vaughan Pratt (talk) 01:52, 24 March 2011 (UTC)

But a good structure article might want to say what its subdirect irreducibles are, and what the initial algebra is. The 2-element Boolean algebra is both of these. Also the free algebra on one generator is structurally important, which in this case is the 4-element Boolean algebra. --Vaughan Pratt (talk) 01:57, 24 March 2011 (UTC)

I agree that this has to be part of the structure article. --Hugo Herbelin (talk) 16:41, 24 March 2011 (UTC)

Interesting as it is, it doesn't look as if the conversation is converging on a mutually acceptable compromise concerning the eventual disposition of the page Boolean algebra. Would it be possible for each of you to express your preferred approach concretely, in the form of a concise paragraph of text that does not require having to read all of the preceding debate to understand it – preferably in the style of the alternatives at User:Lambiam/DraftRFC?  --Lambiam 09:51, 24 March 2011 (UTC)

Here is a new attempt to clarify my view (the last paragraph summarizes the main lines of my preferred approach to a Boolean algebra article).

What I'm saying is that the set of laws that hold of any Boolean algebra is the same as the set of laws that hold of any other Boolen algebra. I have no need to define the Boolean laws to be the set of laws that hold of all Boolean algebras (what Vaughan calls BA a few comments above). I just need to define the set of laws, say B(A), that hold in Boolean algebra A and to observe that B(2) = B(4) = B(8) = B(subsets of X) = B(Lindenbaum algebra) = ... etc.

If I call Thms(Ax) the set of laws derivable from the 10 axioms, the equation B(A) = B(A') is a consequence of the property that B(A) = Thms(Ax) whatever the non-degenerated Boolean algebra A is. The property B(A) = Thms(Ax) comes in turn by application of soundness (for A) to what the article completeness calls deductive completeness, which in our case is (strictly speaking) that for any (closed) equation E not in Thm(Ax), the equation 0=1 belongs to Thm(Ax ∪ E).

The fact that Thms(Ax) = B(2) = B(4) = B(8) = B(subsets of X) = B(Lindenbaum algebra) = ... implies that it does not matter whether we define the Boolean laws to be the laws that hold of the two-element Boolean algebra, or to be the laws that hold of the subsets of say {1,6,23}, or to be the laws that hold in the Lindenbaum algebra, etc. Henceforth, whether we define them to be B(2) or B(Lindenbaum algebra) or simply to be Thm(Ax) is just a matter of point of view.

Then, for pedagogical purpose, I think that introducing the axioms in the context of the set-theoretic operations is as well intuitive as doing it in the context of truth tables, if not more, since it would precisely emphasize that Boolean algebra is about reasoning "algebraically", not about computing with truth tables. --Hugo Herbelin (talk) 16:38, 24 March 2011 (UTC)

Another possible approach that emphasizes the algebraic-reasoning aspect is to exhibit the superficial similarity with elementary algebra: start with a brief historical paragraph telling the reader that Boole himself used the notations + for disjunction and juxtaposition for conjunction, with laws such as x + y = y + x, xy = yx, and x(y + z) = xy + xz, all of which look familiar, but also, for example, x(x + y) = x = x + xy, while noting that in some application areas (particularly digital logic) these notations are still en vogue. Then give the axioms in modern notation using symbols 0, 1, ¬, ∧, ∨. Next, show two possible interpretations: two-valued logic (with application in digital logic), and subsets of some universe (with application in query languages).

The question remains: is that something for an article Introduction to Boolean algebra, or should that (also?) be done here, at Boolean algebra?

Somehow I cannot deduce what your preference is with respect to how the calculus is treated at the page Boolean algebra, in relation to how the structures are dealt with. Specifically, I don't see from what you write whether your preference fits one of the four alternatives on the DraftRFC page better than any of the others.  --Lambiam 17:58, 24 March 2011 (UTC)

Regarding DraftRFC, I don't think that the structure is the primary topic (because the calculus is more popular). I'm inclined to think that the calculus is not the primary topic either, because in terms of textbooks (e.g. on googlebooks or amazon) and in terms of Special:WhatLinksHere, they are roughly at the same order of magnitude (see also the discussion above). However, I did not make precise statistics.

Now, on the question of what the name "Boolean algebra" should link to, my position is more complex. Having a "cold", "soulless" disambiguation page as the current one is, is not very satisfactory in my view, because algebra and algebras have much more to say on what they share than just being listed as having the same name. So my position would be to

1. either have a "smart" disambiguation page, which at least explains in a few words how the two names relate (in the style of the French disambiguation page, but hopefully more interestingly),
2. or to have a page on the mathematical concept of Boolean algebra (mass noun) at a sufficient level of algebraic abstraction, even if an introductory one, so that "structurists" can recognize it really as a mathematical page about the algebra of Boolean algebras, in which case having just a hatnote to the structure (and another hatnote to the value-minded Boolean algebra (logic)) would be fine.

Above, "sufficient level of algebraic abstraction" has to be opposed to "value-minded". It is fine for me that Boolean algebra (logic) be "value-minded" (in the sense that it targets people using Boolean algebra over finite, 2ⁿ-value domains) but I don't consider that a page on the mathematical concept of Boolean algebra (mass noun) has to be such level. -- Hugo Herbelin (talk) 19:47, 24 March 2011 (UTC)

Regarding your short proposal "Another possible approach ..." above, that sounds acceptable to me for either the main "Boolean algebra" page (as in my point 2 above), or for some "Introduction to Boolean algebra" (in replacement of the current one), in case one decides to go for a more comprehensive or higher-level main "Boolean algebra" page (as in my point 2 again). --Hugo Herbelin (talk) 20:04, 24 March 2011 (UTC)

OK, let me state my position, I hope clearly. I want a clear two-article model, one on the field of study and one on the structures. In exchange for that I am willing to have the field of study be "primary" in the purely WP sense, with a hatnote on it to the structure article. I see no need for a third article. --Trovatore (talk) 21:06, 24 March 2011 (UTC)

But what would be the contents of the article which is not about the structure? Would it be closer to Boolean logic, to Boolean algebra (logic), to the introduction, ...? And what does cover the name "field of study" for you? For instance, do you consider Boolean algebra (logic) as an equivalent for Boolean algebras of what linear algebra is for vector spaces? --Hugo Herbelin (talk) 21:20, 24 March 2011 (UTC)

Oh, I'm not interested in debating the contents of the field-of-study article, just as long as it's clear that it's about the field of study, and not about the structures (it's certainly allowed to discuss the structures and probably should, but it's not about them). I'm not that interested in the field of study and will leave that to those who are. --Trovatore (talk) 21:32, 24 March 2011 (UTC)

Is there some reason to assume that most of the Handbook of Boolean Algebras is unfit for Wikipedia articles? And if not, how does Trovatore propose going about cramming it all into a mere two articles? The current problem is not proliferation of articles per se, but proliferation of articles with an unacceptable degree of overlap. If there were some requirement that n-valued logic be treated with exactly n articles I could understand Boolean algebra having to be treated with exactly two, but the other reasons for requiring this make even less sense. This two-article requirement is just another of Trovatore's many strawman arguments. --Vaughan Pratt (talk) 19:35, 25 March 2011 (UTC)

There can certainly be articles on more specific topics. I would be happy to see most of the Handbook of Set Theory covered in WP as well, but I wouldn't put it all in set theory.

That isn't the point. There is a clear rationale for two main articles, each of which in the absence of the other would simply be called "Boolean algebra". I prefer not to have three. --Trovatore (talk) 20:10, 25 March 2011 (UTC)

Yet another straw man: "two main articles". Who else has been advocating two main articles plus other additional articles? --Vaughan Pratt (talk) 04:21, 26 March 2011 (UTC)

Vaughan, I do not understand why you have chosen to take such an unpleasant approach at this moment. I thought we were vaguely converging. Again, I object to the term "strawman"; in this passage I am simply stating my position, not trying to characterize anyone else's position. --Trovatore (talk) 04:35, 26 March 2011 (UTC)