Talk:Free Boolean algebra

From Wikipedia, the free encyclopedia

	Philosophy Portal This article is within the scope of the WikiProject Philosophy, which collaborates on articles related to philosophy. To participate, you can edit this article or visit the project page for more details.
???	This article has not yet received a rating on the quality scale.
???	This article has not yet received an importance rating on the importance scale.
Additional information: Related task forces (core areas): Logic

[edit] Disputed

I disputed myself here because I'm not quite sure of this fact--is this really sufficient to characterize free BAs? It's not obvious that this condition implies that any permutation of the generators extends to an automorphism, which is surely a property we want. Can't find any clear references at the moment. --Trovatore 00:13, 2 November 2005 (UTC)

It sounds right, but (i) it's a new criteria to me and (ii) I haven't yet had my morning tea, so I will remove the tag once I have double-checked it. --- Charles Stewart 15:12, 2 November 2005 (UTC)

Thanks, I appreciate it. Looking at your changes so far, I'm a bit concerned by the change to "initial object". From my dimly remembered category theory I thought an initial object was just one from which there was an arrow to any other object in the category. If the arrows are just BA homomorphisms, that's not nearly strong enough. --Trovatore 16:13, 2 November 2005 (UTC)

No, you've forgotten the condition on cones, and isomorphism does follows from initiality. --- Charles Stewart 16:20, 2 November 2005 (UTC)

The "condition on cones" doesn't ring a bell. I'd ask you to explain it to me, but maybe it would be almost as easy, and much more useful, to add some text to the article about it? At the moment I don't know how to reconcile what's here with what's in the initial object article. --Trovatore 17:19, 2 November 2005 (UTC)

The discussion at initial object is fine. The point I was alluding to is that the initial object construction is a special case (indeed the simplest case) of a colimit, which tells us that not only is there always such an arrow, but that for every such arrow the cone diagram (actully cocone diagram, since we are doing colimits) commutes. In this case that is the same as saying that there is a unique arrow from the IO to every object, which is the same as saying that any two arrows from the any IO to another given object is equal. This is just what you need to prove 'equlity up to isomorphism', noting that the arrow from the any IO to itself must be the identity arrow. --- Charles Stewart 19:03, 2 November 2005 (UTC)

I'm afraid I'm just missing a lot of definitions here. But taking the part that I do sort of understand--OK, so what are the arrows, then? The free BA has lots of nontrivial automorphisms, so if has only one arrow to itself, then the arrows must be something other than what I would have thought (BA homomorphisms). Are you somehow distinguishing the generators and making them part of the definition of the category? --Trovatore 19:08, 2 November 2005 (UTC)

Now I'm confused. In which category are these non-equivalent automorphisms? --- Charles Stewart 19:22, 2 November 2005 (UTC)

Just plain Boolean algebras, with the arrows being homomorphisms. What do you mean by "non-equivalent"?

Maybe this works: "A free Boolean algebra on κ generators is an initial object in the category of Boolean algebras with κ distinguished points". The arrows would be BA homomorphisms that send the &alpha'th distinguished point to the αth distinguished point (the distinguished points don't have to be distinct, though they would turn out to be for the free object, of course). But this is getting extremely abstract--we need a more motivated introduction. --Trovatore 19:25, 2 November 2005 (UTC)

[edit] Initial objects

I think the main definition is wrong. In any category, Initial objects if they exist are unique (up to isomorphism). The only initial object in the category of non-trivial boolean rings is Z₂. --CSTAR 19:36, 2 November 2005 (UTC)

Quite so, and that is my fault and not Trovatore's so I should fix it. There is a category of algebras in which the initial algebra is the initial object, namely the Eilenberg-Moore category, but that category has more structure than the plain category of algebras. The wording I introduced was confused and clear evidence of insufficient tea. --- Charles Stewart 19:47, 2 November 2005 (UTC)

I'm still not sure I understand this. What's the Eilenberg-Moore category? Anyway does this addition make any difference, because free object still is defined as an initial object in a category which does not depend on the generators in any way. --CSTAR 20:32, 2 November 2005 (UTC)

It's one of the two canonical categories generated by a monad (the other being the Kleisli category of resultions, which is sort of a dual to the Eilenberg-Moore category), where the algebra is defined in a different way to the regular way that is due to Lawvere:

• The structure of the algebra is given by category and a monad T over that category, that is a functor equipped with two nat. trans. specifying its unit and product;
• The Eilbenberg-Moore category over this algebra has its objects given by a pair of (i) an object A from the base category, and (ii) any of those arrows f:TA --> A which satisfy certain conditions that show they behave reasonably around the conditions on unit and product for the monad.

There's much more machinery on this definition of algebra than the regular definition of algebra, but this Lawverian conception of algebra is very powerful and admits a lot of nice generalisations of the regular notion. Alternatively it's all the worst sort of generalised abstract nonsense. I used Lambek&Scott's "Intro to higher-order categorical logic" to check my defs, though they call monads triples there.--- Charles Stewart 16:02, 3 November 2005 (UTC)

Postscript: I didn't explain where the regular homs on algebras will occur. The arrows of the E-M category will not contain all the automorphisms of the BA: I'm not sure where you will find these, but maybe they will be the nat. trans. from the monad onto itself. I'll ask someone: I didn't find this explained in L&S.--- Charles Stewart 16:10, 3 November 2005 (UTC)

Yikes. That makes the characterization I proposed seem, I dunno ... Jurassic :)--CSTAR 01:34, 4 November 2005 (UTC)

Well... It certainly frightens computer scientists who are told that these constructions are the right way to describe input/output for functional programming languages. BTW, Chapter VI of Mac Lane's CftWM is all about the monad - algebra connection; the history there contradicts some of what I said: it turns out the E-M construction is originited later but pretty much independently of Lawvere's work, and it was a later researcher, Pareigis, who spelt out the connection. --- Charles Stewart 19:20, 4 November 2005 (UTC)

[edit] Converse follows

It can easily be shown that the free Boolean generated by S, (π, B) pi; is injective. The universal proerty is then clearly the unique extension property.--CSTAR 04:24, 3 November 2005 (UTC)

So what I'm concerned about is that there's no Schroeder-Berstein theorem for BAs--you can have injective homomorphisms both directions, but no isomorphism. In particular, we want every permutation of the generators (of the free BA) to extend uniquely to an automorphism, but how do we know it's not just an injective auto-homomorphism? --Trovatore 04:27, 3 November 2005 (UTC)

This should follow by applying the universal property. More generally, the universal property implies that the induced mappings are functorial.--CSTAR 04:30, 3 November 2005 (UTC)