[FOM] RE: FOM FTGI Boolean Lattices

[Matt Insall]

Harvey has asked that a thread be begun that treats Fundamental Topics of a
General Interest, and Steve Newberry brought up the topic of Boolean
Lattices.  Here, I intend to contribute to this thread and topic some more
material of a general interest to fom.  I shall try to include some relevant
references, although some of them may be dated.  (I can provide some other
references as well, if there is interest in such lists of articles and books
that relate to lattices and logic.)

Matt Insall

++++++++++++++++++++++++++++Boolean Lattices+++++++++++++++++++++++++++

By a _lattice_ we mean a structure \L=(L,m,j), where L is a set, and m and j
are binary operations on L, satisfying the following properties (we use
infix notation):

Idempotence:     x m x = x, and x j x = x

Commutativity:   x m y = y m x, and x j y = y j x

Associativity:  (x m y) m z = x m (y m z), and (x j y) j z = x j (y j z)

Absorption:     (x m y) j x = x, and (x j y) m x = x

(The operation m is called the _meet_ operation, and the operation j is the
_join_ operation.)

In a lattice, an ordering relation (i.e. a reflexive, transitive and
antisymmetric relation) \le is definable in terms of meet [join] by the
following formula:

(x \le y) iff (x m y = x)        [(x \le y) iff (x j y = y)].

The pair (L,\le) is a _lattice-ordered set_, meaning that in addition to the
properties of reflexivity, transitivity and antisymmetry, the relation \le
satisfies the following properties:

FLUB:  For any pair x, y in L, there is a _least upper bound_ in (L,\le) for
the set {x,y}, namely an element z such that x \le z and y \le z, and such
that for each w in L such that x \le w and y \le w, z \le w.

FGLB:  For any pair x, y in L, there is a _greatest lower bound_ in (L,\le)
for the set {x,y}, namely an element z such that z \le x and z \le y, and
such that for each w in L such that w \le x and w \le y, w \le z.

There is an alternative approach to lattice theory that considers
lattice-ordered sets first, and then proves that every lattice-ordered set
arises naturally from a lattice structure on the same set.  There is some
nice category theory to be enjoyed here, but I will leave that for others to
discuss, if they wish.

A lattice is a _boolean lattice_ if and only if it satisfies also the
following properties:

Bounded Below:  The ordered set (L,\le) has a least element, denoted 0, such
that for any x in L, 0 \le x.

Bounded Above:  The ordered set (L, \le) has a greatest element, denoted 1,
such that for any x in L, x \le 1.

Distributive:  For any x, y and z in L, (x m y) j z = (x j z) m (y j z), and
[equivalently] (x j y) m z = (x m z) j (y m z).

Complemented:  For any x in L, there is a (unique) x' in L such that x m x'
= 0 and x j x' = 1.


As Steve Newberry pointed out, every power set lattice is a boolean lattice.
The converse is false, as is shown by considering the finite-cofinite
lattice on a denumerable set.  We use the set N of nonnegative integers for
the denumerable set.  A subset of N is co-finite if its complement is a
finite set.  The boolean sublattice of P(N) that is generated by the finite
and co-finite sets is a denumerable boolean lattice, and as such, cannot be
(isomorphic to) a power set of any set, since all power sets are either
finite or uncountable.  However, in the finite case, the converse does hold:

Theorem:  Any finite boolean lattice is isomorphic to a power set boolean
lattice.

(Aside:  This and similar results about finite boolean lattices can be used,
along with nonstandard methods, to prove various results about infinite
boolean lattices.  See the references at the end for more along these
lines.)

One may wonder how close we can get to a converse of the result that every
power set lattice is a boolean lattice, in the general case.  It turns out
that we need not look too far.

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, and its
proof leads naturally to the interaction of topology and lattice theory, in
that a certain class of topological spaces, called _boolean spaces_, grew
out of the representation theory for these structures.

Steve Newberry pointed out that there is a rich theory of special
sublattices, called _filters_, of boolean lattices that plays a role in the
model theory of classical first-order predicate calculus.  This same theory
of filters, and especially of the maximal filters, or _ultrafilters_, plays
a special role in Stone's representation theory.  Briefly, the points of the
Stone Space of a boolean lattice are the ultrafilters of the original
boolean lattice, and this Stone Space of the given boolean lattice \L is a
boolean space (a compact hausdorff space with a base of clopen sets), where
the basic open neighborhoods are given as the sets of ultrafilters in \L of
the form V_a, for a in L, where

V_a = {u | u is an ultrafilter and a is in u}.

This leads to a categorical co-equivalence between boolean lattices
(actually boolean algebras) and boolean spaces.

One way that filters connect boolean lattices to model theory is through
ultraproducts.  Given an indexed family {\A_i | i in I} of structures for a
fixed relational language, and given an ultrafilter u on the set I (meaning
u is an ultrafilter in the power set lattice P(I)), one may construct a new
structure \A in a manner similar to the direct product, but differing in the
sense that the elements of \A are not the I-tuples (a_i)_{i in I}, but the
equivalence classes of such tuples under the equivalence relation induced by
the ultrafilter:

(a_i)_{i in I} ~u (b_i)_{i in I}   if and only if   {i in I | a_i = b_i} is
in u.

Similarly, the relations in \A are defined modulo the ultrafilter u:

Rabc... means {i in I | R_ia_ib_ic_i...} is in u.

An important theorem in this area is a theorem of \Lo"s (pronounced
``wash''; I apologize for not getting the right diacritical marks in ascii),
which I will state somewhat informally.

Theorem:  A statement of the given language holds in the ultraproduct \A if
and only if it holds in almost every (modulo u) factor of the ultraproduct,
i.e. if and only if the set of indices on which the given statement holds in
the corresponding factor is a member of u.


This theorem provides a foundation for the transfer principle of nonstandard
analysis (and nonstandard methods in general).


There are several topics we have not touched upon here, including (but not
limited to) homomorphisms and monotone mappings, fixed-point theorems, etc.
It would be interesting to see some discussion on these and their
relationships to fom.



Bibliography

[BeSl]    J.L. Bell and A.B. Slomson, Models and Ultraproducts:  An
Introduction.  North-Holland, Amsterdam.  1971.
[BuSa]    S. Burris and H.P. Sankappanavar, A Course in Universal Algebra.
Springer-Verlag, NY.  1981.
[DaPr]    B.A. Davey and H.A. Priestley, Introduction to Lattices and Order.
Cambridge University Press, Cambridge.  1990.
[GeInKa]  M. Gehrke, M. Insall, K. Kaiser, ``Some Nonstandard Methods
Applied to Distributive Lattices''.  In Zeitschr. f. Math. und Grundlagen
der Math. 36 (1990), 123-131.
[Sch1]    J. Schmid, ``Completing Boolean Algebras by Nonstandard Methods''.
In Zeitschr. f. Math. und Grundlagen der Math. 20 (1974), 47-48.
[Sch2]    J. Schmid, ``Nonstandard Constructions for Join-Extensions of
Lattices''.  In Houston J. Math. 3 (1977), 423-439.
[St]      M.H. Stone, ``The Theory of Representations for Boolean
Algebras''.  In Trans. Amer. Math. Soc. 40 (1936), 37-111.
[We]      E. Weisstein, MathWorld.  (definition of ultraproduct)
http://mathworld.wolfram.com/Ultraproduct.html