This article is rated B-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
This is a tentative article to try out some ideas about Boolean algebras. The existing article is already very good so this one may be useful only as a source of ideas and alternative perspectives. --Vaughan Pratt 20:40, 7 August 2006 (UTC)
The article on Boolean algebras defines Boolean algebras formally from the point of view of lattice theory. Ring theory being no less a valid point of view, as explained below, the question arises as to whether Boolean algebras even have a "neutral" point of view from which they can be explained. Category theory partially solves this with an account that is neutral between lattice theory and ring theory, but now from the point of view of category theory whose neutrality has yet to be generally accepted. We solve this here by translating the category theoretic account into ordinary algebra; since Boolean algebra is a part of algebra one cannot get much more neutral than this.
In more detail, Boolean algebras have traditionally been defined analogously to other structures such as groups, rings, vector spaces, and lattices. These others all have characteristic operations and equational axioms, with no reason to suppose that there might be better operations or equations on which to base the definition. In particular when we count the number of binary operations assumed by each definition, groups always employ one binary operation while rings and lattices always use two. In contrast, although Boolean algebras are traditionally defined in terms of the two lattice operations of join (disjunction) and meet (conjunction), they can be defined equally rigorously in terms of a single binary operation, Sheffer stroke, NAND or ¬(x∧y).
One might acknowledge this alternative choice of operations while continuing to defend the essence of Boolean algebras as being lattices at heart. In fact a Boolean algebra is exactly a lattice that is both distributive and complemented. Marshall Stone [1936], in the course of pointing out the analogy between lattices and rings while writing his celebrated paper on the duality of Boolean algebras and Stone spaces, noticed that, for lattices that are Boolean algebras, this was more than just an analogy. When the definition is based on exclusive-or instead of inclusive-or while retaining conjunction, a Boolean algebra is seen in fact to be a ring. This leads to the definition of a Boolean algebra as simply any ring satisfying x2 = x, called a Boolean ring.
So while a Boolean algebra is fundamentally a lattice, it is at least as fundamentally a ring. The question then arises as to whether the concept is one that has a multiplicity of equally good definitions, or whether there is some underlying common essence to all these definitions.
William Lawvere [1963] introduced the notion of (finitary) algebraic theory as a category with (finite) products, whose equations are represented as the commutative diagrams therein, and whose models are the product-preserving set-valued functors therefrom. Since functors preserve commutativity of diagrams, these models satisfy those equations. In this framework Boolean logic as the equational theory of Boolean algebras can be defined as the category of finite power sets and their functions. A Boolean algebra is then any model of that category in Lawvere's sense. An advantage of this definition is that it is unbiased: not only does it not express any preference for lattices or rings, it does not even mention either concept.
The present article amounts to a translation of Lawvere's categorical definition into the more widely used language of ordinary algebra. In this translation a Boolean algebra becomes any model of the finitary equational theory of two values. This definition requires operations to be finitary, but imposes no other restriction and hence implicitly equips the algebra of two values with all possible finitary operations. The equational theory of Boolean algebras resides in the composition law of the category representing the Lawvere-style theory, which we translate into a more conventional equational axiom system, with a single axiom schema expressing the composition of that category in lieu of the more customary finite list of axioms. This schema makes explicit the neutrality implicit in Lawvere's axiomatization: no Boolean operation is given preferential treatment because the axiom schema is instantiated with one axiom per Boolean operation. Vaughan Pratt 22:53, 8 July 2007 (UTC)
JA: Vaughan, by way of making a maintainable article out of this essay, can you think of a distinctive name for this angle on boolean algebras? Just on quick scan it seems to be something like a universal algebra approach to boolean algebra? Jon Awbrey 12:04, 8 August 2006 (UTC)
JA: Other possibilities:
Or something like that. Jon Awbrey 18:06, 8 August 2006 (UTC)
VP: First, thanks very much for all the cleaning up, Jon!
Good question about the name. Neither of these titles express the intent of the article, which was not to impose a UA slant (if I've overdone that I should tone it down, e.g. by removing the dependence on direct products) but rather to give a more canonical definition of Boolean algebra than the existing definitions, which build in arbitrary assumptions about both the choice of operations and the choice of axioms. My definition of a Boolean algebra as any algebra that looks, swims, and quacks like the algebra of all finitary operations on the set {0,1} picks neither particular operations nor particular axioms. What would you call that? How about:
Incidentally what's the origin of the term "Boolean domain" for a two-element set, and which communities use it today? Dijkstra used it in EWD 1070 in 1989, are there any earlier occurrences? The reason a mathematician would not say "Boolean domain {0,1}" in place of "set {0,1}" is because "set" already hits that nail on the head and the reader might therefore infer from the longer name that something other than an ordinary set was intended. --Vaughan Pratt 23:00, 8 August 2006 (UTC)
JA: The UA came to mind more because of the graded series of operators than the direct products. I took you to be trying to get at the invariant mathematical objects in a categorically universal way rather than getting tangled up in the non-invariances of syntax and axioms.
JA: Was hoping for something a bit more catchy than "Boolean algebras (a more canonical definition)", though, as we try to keep our disambiguators short. We are lazy typers hereabouts. How about:
JA: "Canonical boolean algebra" (CBA) too backword for you? How about "Boolean algebras canonically presented" (BACP)? If it were me I go for "known" just to get BACK. Jon Awbrey 16:46, 9 August 2006 (UTC)
JA: Not sure where I picked up boolean domain for a generic 2-element set. It may have been the use of phrases like information domain by Dana Scott, et al. Seems like I use that word partly to connote a category-theoretic object that will have all sorts of arrows in and out of it, or when I think of a particular set as the cornerstone of a whole bunch of extra construction. Just my sense of it. Jon Awbrey 02:50, 9 August 2006 (UTC)
VP: Jon, I just noticed your change from Boolean to boolean. Would you mind restoring the caps? Boolean is very standard (just checked half a dozen books now and every one used Boolean). Even the main article Boolean algebra uses Boolean.
JA: Regional dialect, I guess. Will change back later tonight. Jon Awbrey 16:46, 9 August 2006 (UTC)
The MediaWiki software provides a more streamlined way to write tables, if you like. Here's an example.
x0 | x1 | 2f0 | 2f1 | 2f2 | 2f3 | 2f4 | 2f5 | 2f6 | 2f7 | 2f8 | 2f9 | 2f10 | 2f11 | 2f12 | 2f13 | 2f14 | 2f15 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | |
1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | |
0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | |
1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
In proper HTML 4.01 (or XHTML 1.1) there is a much nicer way to ask for all the columns to have a common width, but here I did it the hard way. --KSmrqT 00:34, 9 August 2006 (UTC)
VP: Ok, that looks cool. Here are the other two tables done in that style. But how do I get them all on the same line as in the original? Putting them in another layer of {| |} seemed not to work, nor did putting them in table.../table (seems {|...|} can't be a table entry)
0f0 | 0f1 | |
0 | 1 |
x0 | 1f0 | 1f1 | 1f2 | 1f3 | |
---|---|---|---|---|---|
0 | 0 | 1 | 0 | 1 | |
1 | 0 | 0 | 1 | 1 |
--Vaughan Pratt 06:44, 9 August 2006 (UTC)
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
::
and the {|
there can be no space.|
") must be used, and must begin a new line.<div>
to fix that.border="1"
on the outer table would be omitted in actual use; they just help show the structure of the example. --KSmrqT 08:57, 9 August 2006 (UTC)JA: The exponentiation towers are looking really bad on my browser. When things stabilize, I might try TeXing a few things to see if it's any better. Jon Awbrey 15:04, 11 August 2006 (UTC)
VP: Right, when I first ran into this MediaWiki bug I solved it at first by texifying it. But the resulting fonts aren't a good match, so I experimented a bit and found that MediaWiki could cope with multiple sup's as long as they were consecutive. Vaughan Pratt 14:23, 14 August 2006 (UTC)
VP: Just tried it in IE and noticed that the line following a tower is jammed up against its predecessor, not good. Doesn't happen with Firefox. Vaughan Pratt 16:59, 14 August 2006 (UTC)
Jon, I appreciate that use of citation templates is a personal choice. Since I created the References section in the first place, I would suppose that my choice would take precedence over yours. But your reversion lost much more than that, because I had added ISSN links, page numbers, URL and format info, and so on. I have reverted back to my choice, but I will defer to Vaughan as to which we should use.
This gives me an opportunity to say two things. I'm enjoying watching the article evolve, and I extend thanks to Vaughan for writing it. Also, I had to guess that the references I cite are the ones intended; Vaughan, please drop a note here if I'm wrong. --KSmrqT 04:05, 15 August 2006 (UTC)
VP: The Lawvere citation should be to one that treats algebraic theories as functors from small categories with products. Not sure which that is (his thesis?), but it's not the metric spaces paper. I'll ask Bill.
JA: From WP:CITE:
Templates
The use of Citation templates is not required by WP:CITE and is neither encouraged nor discouraged by any other Wikipedia citation guidelines. They may be used at the discretion of individual editors, subject to agreement with the other editors on the article. Some editors find them helpful, while other editors find them annoying, particularly when used inline in the text. Because they are optional, editors should not change articles from one style to the other without consensus.
JA: Jon Awbrey 04:08, 15 August 2006 (UTC)
There were numerous mistakes and missing data in the new references, which I have attempted to correct/add. Please check carefully for sanity. I have made the Boole reference a reprint with scholarly commentary; I hope that's OK. The Schröder volumes were reprinted by Chelsea (now owned by AMS), but I cite the original; in neither case could I find an ISBN; and it is not clear if a specific paper, or volume, or part, or year is intended. Unfortunately, the AMS Chelsea site does not list Schröder as currently available. In my younger days I was spoiled by access to great university libraries, but these days we rely on Internet resources, so I have included a link for the Lawvere dissertation (which includes much supplementary material). Also, much as I personally appreciate having classic references, I think it would be a kindness to our readers to provide some more accessible references as well, if possible. --KSmrqT 07:00, 17 August 2006 (UTC)
JA: Not sure what paper of Peirce is intended, or if it matters, but here's a bib, still in progress, if that helps:
JA: Jon Awbrey 07:06, 17 August 2006 (UTC)
JA: My old automata theory textbook gives a good basic account of ultimately periodic languages or sequences:
JA: There's probably a newer edition. Jon Awbrey 12:48, 17 August 2006 (UTC)
JA: We need to be careful about the use of the word linear in this context. I think it's best to save it for the algebraic sense of linear, as in the 2^n linear functions h : B^n -> B, B = {0, 1}. These are just all the different sums under the exclusive disjunction (+), with (n choose k) sums of rank k. For example, the rank 0 sum is 0, the rank 1 sums are x_1, …, x_n, the rank 2 sums are all of the form x_i + x_j, and so on up to the rank n sum x_1 + x_2 + … + x_(n-1) + x_n. If we save linear for that sense, then we need another word for the sense in a phrase like "An alternative to this linear disposition of the Boolean operations …". If I read that right, anyway. Jon Awbrey 01:32, 17 August 2006 (UTC)
VP: I changed linear to sequential, which means essentially the same thing in this context but without the algebraic connotation that might bother some. Vaughan Pratt 05:58, 31 December 2006 (UTC)
JA: This is a critter that goes back to Leibniz, I think. In some dialects of graph theory it's called the link operator. It's a discrete analogue of the point-deleted neighborhood in calculus. I used to call it the boundary operator, because that's what it looks like in venn diagrams, and I think that there's an official name for it in co/homology theory, but I've forgotten what little I knew of that.
JA: If you are thinking of a n-cube (incubus) as your favorite graph, then each point of the cube can be represented as a conjunction of n posited or negated variables. So the all 1's node is the product of all positives x_1 x_2 … x_[n-1] x_n and the all 0's node is the product of all negatives (x_1)(x_2) … (x_[n-1])(x_n), here using parentheses for negation a la Peirce. These are called singular propositions (or singular boolean functions) because the fibre of truth under such a function is a single point of the cube. To be continued … Jon Awbrey 17:08, 17 August 2006 (UTC)
JA: Let's say that p is a product of literals, that is, a conjunction of posited or negated basis elements. Then p = e_1 e_2 … e_[n-1] e_n, where e_j = x_j or e_j = (x_j) = ¬x_j, for each j = 1 to n. Then the fibre of 1 under p, that is, (p^(-1))(1) is a single node of the n-cube.
JA: Given p as above, and representing the boundary operator or minimal negation operator (mno) of rank n by a bracket of the form "( , …, )", the proposition (e_1, e_2, …, e_[n-1], e_n) is true on the nodes adjacent to the node where p is true, and false everywhere else on the cube. Jon Awbrey 19:00, 17 August 2006 (UTC)
JA: For example, let's take the case where n = 3. Then the minimal negation opus , which we will eventually get so lax as to write "(p, q, r)" when there is minimal risk of misinterpretation, has the following venn diagram:
o-------------------------------------------------o | | | | | o-------------o | | / \ | | / \ | | / \ | | / \ | | o o | | | P | | | | | | | | | | | o---o---------o o---------o---o | | / \`````````\ /`````````/ \ | | / \`````````o`````````/ \ | | / \```````/ \```````/ \ | | / \`````/ \`````/ \ | | o o---o-----o---o o | | | |`````| | | | | |`````| | | | | Q |`````| R | | | o o`````o o | | \ \```/ / | | \ \`/ / | | \ o / | | \ / \ / | | o-------------o o-------------o | | | | | o-------------------------------------------------o Figure 1. (p, q, r)
JA: Back in a flash ... Jon Awbrey 13:18, 18 August 2006 (UTC)
JA: (Some flashes are slower than others.) For a contrasting example, consider the boolean function expressed by the form , whose venn diagram is as follows:
o-------------------------------------------------o | | | | | o-------------o | | /```````````````\ | | /`````````````````\ | | /```````````````````\ | | /`````````````````````\ | | o```````````````````````o | | |`````````` P ``````````| | | |```````````````````````| | | |```````````````````````| | | o---o---------o```o---------o---o | | /`````\ \`/ /`````\ | | /```````\ o /```````\ | | /`````````\ / \ /`````````\ | | /```````````\ / \ /```````````\ | | o`````````````o---o-----o---o`````````````o | | |`````````````````| |`````````````````| | | |`````````````````| |`````````````````| | | |``````` Q ```````| |``````` R ```````| | | o`````````````````o o`````````````````o | | \`````````````````\ /`````````````````/ | | \`````````````````\ /`````````````````/ | | \`````````````````o`````````````````/ | | \```````````````/ \```````````````/ | | o-------------o o-------------o | | | | | o-------------------------------------------------o Figure 2. ((p),(q),(r))
JA: TGIF! Jon Awbrey 21:32, 18 August 2006 (UTC)
JA: NB. I've rewritten the above material a little more cleanly and added it to the article on the minimal negation operator. Jon Awbrey 05:24, 22 August 2006 (UTC)
Someone found a better way to work around the bug the WikiMedia software has with nested superscripts or subscripts. The trick is to use a <span>
wrapper. Compare:
''A''<sup>''B''<sup>''C''</sup></sup>
''A''<sup>''B''</sup><sup><sup>''C''</sup></sup>
''A''<sup>''B''<span><sup>''C''</sup></span></sup>
Since the use of the wrapper preserves the intended semantics in the markup, I've replaced all instances in the article (I hope!). --KSmrqT 11:42, 17 September 2006 (UTC)
The article states "The free countably generated, countably distributive sigma-algebra has the same nice structure as free CABAs, being the power set algebra 22N". What is the proof of this? It would seem to me that its cardinality must instead only be 2N, along the lines of the proof that there are only 2N Borel sets of reals. -Chinju (talk) 08:56, 15 November 2008 (UTC)
I just wanted to say that I like this article. Very rich in information and well formulated. Thanks to the creators for this tremendous piece of work! 82.82.87.235 (talk) 01:11, 10 July 2009 (UTC)
In the article is said: Such an algebra can be defined equivalently as a complete Boolean algebra that is atomic, meaning that every element is a sup of some set of atoms.
In Lattice_(order) article atomic and atomistic are defined as:
So in our article it should be atomistic instead of atomic, shouldn't it? Is it an error?
VictorPorton (talk) 23:52, 26 November 2009 (UTC)
Small thing: Could the definition of an atom of a Boolean algebra be included in the definition part? It is written further down, but in a "by the way" way, which took me a while to find. Thanks for a great page! - K
I understand the rationale that there are multiple ways of presenting/discussing/teaching Boolean Algebras (meaning the mathematical structures).
I don't understand how this very clunkily-named article is anything other than an impermissible violation of the WP policy against content-forking. — Preceding unsigned comment added by 12.87.204.66 (talk) 19:08, 30 October 2021 (UTC)