Talk:Boolean algebras canonically defined

From Wikipedia, the free encyclopedia

Contents 1 Note moved from main page 2 Towards a genuine article 3 Wiki table "pipe" markup 4 Typographical Towers 5 References 5.1 Re: New references 6 Linear Thinking 7 Minimal negation operator 8 Bug workaround

[edit] Note moved from main page

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)

[edit] Towards a genuine article

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:

1. Universal algebra of boolean type?
2. Universal algebra of characteristic two?

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:

1. Boolean algebras (a more canonical definition)

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.

VP: Exactly right, though I'd call what I'm trying to do here canonical (in the sense of "least arbitrary") rather than universal ("broadly applicable"). Incidentally the categorical way of getting at the "graded operators" is to start from the category of finite power sets and all functions between them; what I've done amounts roughly to taking only the homsets with codomain 2¹, the power set of the singleton, and translating that subcategory into the language of naive set theory as expressed by the truth tables.

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:

• Canonical boolean algebra?

VP: Not bad. How about "Boolean algebras canonically"? Would parenthesizing "canonically" impact search for better or worse?

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)

VP: Oh, that's BAD (hmm, "Boolean algebra definition"?) How about "Boolean algebras canonically defined"? If you're ok with that could you please make the move since it looks like I'm not authorized to. If you think it makes sense to parenthesize the canonical bit then either "(canonical definition)" or "(canonically defined)" works for me. Or just "(definition)" if BAD appeals...I know the extant article defines "Boolean algebra" but I think this definition is better.

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: Ok, so let's go with "set {0, 1}" on the ground that the best definitions assume the least background.

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)

[edit] Wiki table "pipe" markup

The MediaWiki software provides a more streamlined way to write tables, if you like. Here's an example.

Binary Operations

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. --KSmrq^T 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)

Constants

	0f0	0f1
	0	1

Unary Operations

x0		1f0	1f1	1f2	1f3
0		0	1	0	1
1		0	0	1	1

--Vaughan Pratt 06:44, 9 August 2006 (UTC)

The software is quirky, but it is supposed to deal with nested tables. However, since some folks will be viewing this at 800×600 resolution, we should be kind and not create so wide a table. Here's a kind version.

The necessary magic is not at all obvious, and apparently not documented. Here's what it took to get this to work:

1. Each nested table starts at the beginning of a new line. (This much is documented.)
2. Each nested table ends at the beginning of a new line.
3. At the start of the first line, between the :: and the {| there can be no space.
4. The column separator indication ("|") must be used, and must begin a new line.
5. And even with all this the software seems to get confused about the indentation of material following the table. I isolated the table inside a <div> to fix that.

Obviously the colored borders and the border="1" on the outer table would be omitted in actual use; they just help show the structure of the example. --KSmrq^T 08:57, 9 August 2006 (UTC)

[edit] Typographical Towers

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)

When I was doing some housekeeping, I noticed that an exponent on an exponent was using a peculiar markup,

''a''^''b''^{^''c''}

I failed to see any reason for the extra complication, so performed the obvious simplification,

''a''^{''b''^''c''}

Yow! The results were unacceptable.

a^bc versus a^bc

And no wonder; the generated HTML markup is quite different.

<i>a</i>^<i>b</i>^{^<i>c</i>}

versus

<i>a</i>^<i>b</i><i>c</i>

Clearly the MediaWiki software has a bug; so I restored the weird markup.

I'd stay away from inline TeX images for this stuff; the baselines will be all wrong.

Jon, can you say what browser and OS you're using, and be more explicit about "really bad" (a screen capture, perhaps)? --KSmrq^T 00:03, 12 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)

[edit] References

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. --KSmrq^T 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)

[edit] Re: New references

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. --KSmrq^T 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:

• Charles Peirce (Bibliography)

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:

• Denning, P.J., Dennis, J.B., and Qualitz, J.E. (1978), Machines, Languages, and Computation, Prentice–Hall, Englewood Cliffs, NJ. See §6.4, "Ultimately Periodic Behavior".

JA: There's probably a newer edition. Jon Awbrey 12:48, 17 August 2006 (UTC)

[edit] Linear Thinking

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)

[edit] Minimal negation operator

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)

[edit] Bug workaround

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:

• Buggy: ''A''^{''B''^''C''}

  → A^BC

• Old fix: ''A''^''B''^{^''C''}

  → A^BC

• New fix: ''A''^{''B''<span>^''C''</span>}

  → A^BC

Since the use of the wrapper preserves the intended semantics in the markup, I've replaced all instances in the article (I hope!). --KSmrq^T 11:42, 17 September 2006 (UTC)