FOM: Boolean algebra vs Boolean ring

[Vaughan Pratt]

From: Stephen G Simpson <simpson at math.psu.edu>
>Does it mean that you don't distinguish basic operations
>from derived ones?

When appropriate.  In the class notes for my course "Algebra for Computer
Scientists" I establish necessary and sufficient conditions for a Boolean
basis to be complete, where the distinction clearly matters.  But most
of the time it doesn't matter: an operation doesn't need to be given
explicitly in the signature in order to qualify as a Boolean operation.

In fact one definition I give of Boolean operation in my notes is
"finitary operation on the set {0,1}".  This captures the whole clone
(closed "nest" of operations as universal algebraists like to call the
closure of whatever basis with respect to composition) in one simple
definition, bypassing the more traditional but messy process of starting
with some arbitrarily chosen finite basis, building up the remaining
operations by composition, and verifying the independence of choice
of basis.

By taking the two-element Boolean algebra 2 to be {0,1} equipped with
the Boolean operations so defined, one can then define a Boolean algebra
to be any model of the equational theory of 2.  This is made precise by
taking the set of all Boolean operations as defined above as the index
set for the Boolean algebra signature, with the arity of the operation
symbol indexed by Boolean operation f being that of f.  (Important to
keep all the types straight here.)

Dropping "finitary" in this definition yields (as it turns out) the
notion of complete atomic Boolean algebra ("atomic" cannot be omitted).
CABA's form a variety if and only if one accepts the category theorists'
definition of variety, most slickly couched in terms of monads,
set theorists having thus far (to my knowledge) declined to accept
signatures that are proper classes.  The free CABA on (generated by) a
set of cardinality n has cardinality 2^2^n for all sets of generators,
and its structure is simply that of the double power set of that set.
So even though the CABA signature (and every basis for it) is a proper
class, its operations of arity any given cardinality have a very simple
description, namely as sets of subsets of that cardinal.

In the same vein the free complete semilattice on n has cardinality
2^n for all cardinals n, and the signature of CSLat again forms a proper
class, as does every basis for it.  (Digressing a bit, CSLat is self-dual:
the category CSLat^op is equivalent to CSLat, via the representation
of the dual of the complete semilattice S as the complete semilattice
consisting of all complete-semilattice homomorphisms from S to the
(unique) 2-element semilattice.  Try calculating these yourself in the
finite case for some 4-element and 5-element semilattices, and then
dualize those duals, it's really neat to see how you end up back where
you were!)

Another definition of Boolean algebra in the notes is "complemented
distributive lattice," where the appropriate basis for this definition
is that for lattices (AND, OR) together with complement.  When adding
complement one could drop one of AND or OR at the same time, but this
would be a pointless distraction.  The point is that the choice of basis
only matters for these secondary issues such as convenience and theorems
about bases.

>So you are saying that, according to Sikorski, U
>is one of the operations of a Boolean ring,

Yes.

>but not of an arbitrary ring?

This is a very good question whose answer nicely illustrates the
relationship between Boolean algebras and (general) rings with unit.

The Boolean ring clone is a quotient of the ring clone, namely that
induced by idempotence, AA=A.  This quotient is in the evident natural
(structure-preserving) bijection with the Boolean clone (which is what
Sikorski et al have in mind when they say that all Boolean rings are
Boolean algebras and conversely).  All its equivalence classes are
infinite (e.g. the class 0 consists of the even integers, 1 the odds),
including the class corresponding to U.  In this sense U is not so much
*one* of the operations of a Boolean ring as an infinite equivalence
class of them, which idempotence collapses to the one operation, namely U.

By the way I hope everyone knows that the free commutative ring with unit
on n generators consists of the polynomials with integer coefficients
and n variables.  If you drop "commutative" then you can still write
out your polynomials as a sum of monomials, but monomials are now finite
strings of variables rather than finite multisets since order matters.
Dropping "with unit" corresponds to excluding the empty monomial 1
(no constant term) from the free algebra.

I also hope people know that "clone" and "free algebra" are one and the
same notion, with both parametrized by the set of variables.  If your
textbook says otherwise it's due for an upgrade.

One caveat: I tend to make these things up as I go along in preference
to looking them up, which those of you who've read some of my earlier
postings will know leads to the occasional bug, usually when I'm on
someone else's turf and always to my enormous chagrin.

I think from these answers it should be clear what my answers to your
other questions would have been, but I won't mind if you want to ask
any of them again.

Vaughan Pratt