[FOM] RE: FOM FTGI Boolean Lattices

Vaughan Pratt pratt at cs.stanford.edu
Mon Apr 28 04:45:49 EDT 2003


>From: "Matt Insall" <montez at fidnet.com>
>Theorem:  Any boolean lattice is isomorphic to a boolean sublattice of some
>power set lattice.
>This theorem is Stone's Representation Theorem for boolean lattices,

Actually this is Birkhoff's representation theorem, namely 13.2 on page 444 of

	@Article(
Birk35,	Author="Birkhoff, G.",
	Title="On the structure of abstract algebras",
	Journal="Proc. Cambridge Phil. Soc",
	Volume=31, Pages="433-454", Year=1935)

A year later Stone tightened Birkhoff's result by giving a canonical such
representation, later understood in terms of the duality of Boolean algebras
(aka Boolean lattices) and Stone spaces (aka Boolean spaces) that Matt
mentioned, and moreover abstractly characterizing the spaces so obtained
as all and only the totally disconnected compact Hausdorff spaces.

Stone's result is nontrivial; however this nontriviality is not intrinsic to
finding a duality but rather the consequence of a dearth (in those days) of
mathematical structures available to serve as the dual of a Boolean algebra B.

Stone takes as the points of the Boolean space S dual to B the ultrafilters of
B, and as each of its basic open sets the set of ultrafilters containing any
given element b of B (i.e. one basic open set per element of B).  Since this
is not a standard mathematical object, he proceeds to generate a topology
on S (by closing under arbitrary union, noting that the basic open sets are
already closed under finite intersection, and for that matter finite union)
in order to produce a topological space, a standard kind of object.

The hard part of Stone's theorem can be traced to this last step, generating
the topology (by closing under arbitrary union).  If this step is simply
omitted, and one asks what sort of weird animal we have at this intermediate
stage, it is easily shown that we already have an object that is the exact
dual of B (in the categorical sense of duality) when the morphisms are
taken to be continuous functions as usual (inverse image of opens is open).
We simply ignore the fact that the "topology" is not closed under arbitrary
union at this stage.  The basic opens are in fact clopens (Boolean algebras
being complemented), and to dualize back to B one need merely take *all*
the opens, since they are all clopen at this stage.

The hard part of Stone's theorem is that, after generating the topology,
a function f:S->T is continuous iff it was continuous before generating
the topology.  That is, generating the topology does not make any continuous
function discontinuous or vice versa.  More details in Theorem 5 on p. 452 of

	@InProceedings(
Pr95c,	Author="Pratt, V.R.",
	Title="The {S}tone Gamut: A Coordinatization of Mathematics",
	BookTitle="Logic in Computer Science", Pages="444-454",
	Month="June", Publisher="IEEE Computer Society", Year="1995")

Vaughan Pratt




More information about the FOM mailing list