[FOM] Corrected version of FTGI: Boolean Lattices for Logicians

[steve newberry]

                      BOOLEAN LATTICES FOR LOGICIANS
                         by  R. Stephen Newberry

I want to present a very elementary view of Boolean lattices, and
in particular, of Boolean POWERSET lattices, together with a few
points of interest to logicians. It will be a bit of a challenge
for me, because thirty-odd years ago, in one of the most
colossally foolish actions of a life not known for shrewd
decisions, I gave most of my math and logic books to Stanford
Philosophy Library, and they haven't been seen since. Woe! Woe!
Woe! So I'll be writing from forty year old memories and there
will almost certainly be some slippages.  I'll need the following
ASCII equivalents for set operators: '@' is read "is an element
of" [or "are elements of"]; 'sbst' is read "is a subset of" [or
"are subsets of"]; and '/' for negation of the two preceding set
operators.

It will also be quite a challenge to communicate the "visual"
concept of Boolean lattices without being able actually to draw
the pictures. I will instead attempt to *describe* the pictures in
a manner which I hope will enable the reader to use pencil and
paper to *draw* the first three or four lattices, and then to
"visualize" the recursively generated infinite sequence of
[finite] lattices, and finally to "visualize" the union of the
countable sequence of finite lattices to obtain an infinite
Boolean lattice. This has some rather direct relevance to
Predicative CLFO [Classical Logic of Finite Order].

The transition from classical Boolean to intuitionistic pseudo-
Boolean lattices is obtained by deleting the bottom ["empty-set"]
node. [The definitive treatise on the pseudo-Boolean lattices and
their relevance to intuitionistic logic is to be found in THE
MATHEMATICS OF METAMATHEMATICS, Rasiowa and Sikorski,  Warsaw
-- but it's a hard book to find! I would KILL to have my own
copy back again.]

=========================================================

Theorem: Every powerset lattice is a Boolean lattice.

Definition: A Boolean lattice is a lattice which is closed w.r.t.
the operations of meet, join and complement. [It is also complete,
complemented and distributive.]

The relevance to classical logic is most easily seen w.r.t.
Elementary Propositional Calculus, which is already generally
known to be a Boolean algebra: Complement corresponds to negation,
meet corresponds to conjunction, and join corresponds to
disjunction [or, as W.V.Quine would have it, 'alternation'] The
set-theoretical analogues are just what one would expect:
Complement corresponds to complement, meet corresponds to
intersection, and join corresponds to union.

=========================================================

Visualization: The number of nodes in a Boolean lattice is 2\n,
where n is the number of generators. For n=0 the lattice is
degenerate, and consists of a single point, which is associated
with the null set. [Draw a single point at the lower left-hand
side of the paper. Label this 'L/0'].

For n=1, draw a copy of L/0 and then draw another, second,
point about an inch above the first one, and connect them
with a vertical line.] Label this 'L/1', and attach a zero "0"
to the bottom node and a one "1" to the top node. All the
generators appear in the first level above the null set.

The definition by recursion:

                 L/(n+1) =df= L/n + L/n,

where this is understood to mean two copies of L/n, with the
second copy to the right and slightly higher on the page, so that
the *bottom* node of the second copy is horizontally aligned with
the next higher [layer of] node[s] in the left-hand copy, and '+'
means "connect the corresponding nodes with straight lines"
[edges]. Do this. The result in this case should be a diamond
or 4-sided parallelogram, leaning slightly towards the right.
Label this 'L/2', and number the nodes 0, 1, 2, 3; note that '3'
appears at the top node, '0' at the bottom, '1' and '2' appear at the
*mid-line* and we see that meet(1,2) = 0, join of (1,2) = 3, and 1, 2
are mutually complementary w.r.t 3. All the generators appear in
the first level above the null set.

Taking n=2, iterate the recursion to obtain L/3, which looks like
a cube drawn in perspective and label the nodes 0 through 7 [= 2\n
- 1],)with '0' at the bottom, '7' at the top, and two "layers" of
nodes, 1,2,3 and 4,5,6 .  Note that the complementary pairs are
(0,7), (1,6), (2,5), (3,4). The midline is unpopulated, as is the
case with all finite Boolean lattices of odd degree.

This relationship of complements persists, as can be seen in  L/4:
(2\4 -1) = 15; the layers are 1,2,3,4 and 5,6,7; 8,9,10 and
11,12,13,14 where the complementary triples 5,6,7 and 8,9,10 are
at the midline, and correspond to what, in the infinite case will
be referred to as the "flats" of limit-sets. The complementary
pairs are (0,15), (1,14), (2,13), (3,12), (4,11) and then at the
midline, (5,10), (6,9), (7,8). All the generators appear in the
first level above the null set.

[ I apologize for belaboring the obvious.]

FILTERS: If S is any non-void subset of a lattice L/(n+1), then
any set T of subsets of S  s.t. 0 /@ T and S @ T and whenever x,y
@ T then x & y [read "x meet y"] is also an element of T and
whenever x @ T and x sbst y then y @ T, such a set T is called a
*filter* [or "dual ideal"] of  S, which in this context will
always be L/n or L/(n+1).  All filters T have the FIP ["finite
intersection property"] that the intersection [or meet] of any
finite number of elements of T is non-void.  If a filter T' is
s.t. for all x sbst S either x @ T' or (S-x) @ T' then T' is an
ULTRAFILTER or MAXIMAL filter of S.

EXAMPLE: The second ["right-hand"] lattice L/n of the two lattices
in the recursion equation is a sublattice of the newly created
lattice, and is the ULTRAFILTER.of L/(n+1).[Trust but Verify]

As the recursion continues, the "shape" of the lattice above and
below the midline begins to [very roughly!] approximate a pair of
cones, with lower vertex = 0 and upper vertex = (2\n - 1). And, as
is in the nature of the generating process, all the generators
appear in the first level above the null set.

=========================================================

Taking "the limit" i.e., the union of the sequence L/n (n=0,1,2, ...)
as n "asymptotically approaches" omega, yields a Predicative
Powerset, that is the powerset of all predicatively definable
subsets of omega where the first-level nodes correspond to the
singleton sets of omega, the second-level nodes correspond to
unordered pair sets, the third-level nodes to the unordered
triples, and so on. The subsets of level n+1 (n>0) are joins
[unions] of subsets of lower levels. Call this lattice L/w (read
'w' as omega.)

The nodes of the lower cone correspond to the finite subsets of
omega, the nodes of the upper cone correspond to the co-finite
subsets of omega, and the nodes of the two complementary flats at
the midline correspond to the co-infinite limit-sets of paths
through the cones. This is where the "set of all primes" or the
"set of all composites" or the "set of all evens" or the "set of
all odds" &c., reside.

[If this picture does not come to you easily, it might be a good
idea to spend several minutes thinking about it ... ]

This representation of subsets of omega is not yet *quite*
complete, because the definition of this set is predicative, and
includes all and only the subsets which are predicatively
definable; and in fact *this powerset itself* is the union of
countably many finite sets, and hence is itself necessarily
countable. Missing from this Predicative Powerset are all and only
the **uncountably many** subsets which are definable only by
impredicative definitions. An example of such a set is the
Cantor diagonal set of all elements of omega which can be mapped
to subsets of which they are themselves NOT elements. The formal
definition of this set is *possible* in the Ramified Theory of
Types, but emerges as being of higher type-order than the class of
sets to which it must belong if it is to be regarded as having
been predicatively defined. [See Appendix I]

But I digress.

Setting aside, for the moment, the idea of the Predicative
Powerset of omega, let us regard the set S* of all wffs of
elementary propositional calculus: L/w is a pictorial
representation of S*. The first level represents all of the atomic
propositions, the second level represents the set of all
disjunctive literal pairs, the third level represents the set of
all disjunctive triples, &c., .

But note that dual-symmetry guarantees that there is a
representation of the complement of every such node as a DeMorgan
Dual, i.e., as a negated conjunction, "on the other side" of the
lattice. [In a finite lattice, subtract the numerical label of the
node from (2\n - 1), and look for that number.]

L/w is [or more precisely, contains] the diagram of every possible
well-formed formula of Elementary Propositional Calculus, and
hence, for any satisfiable [= non-contradictory] wff B of E.P.C.
there is an assignment of the literals [=atomic wffs or negated
atomic wffs] of B to the nodes of the sublattice L' of L/w which
is the ultrafilter of L/w, and L' can be regarded as an elementary
extension of every MODEL of every such formula. [Proof left as an
exercise for the reader.]

It will by now be apparent that Boolean lattices can be used to
develop 2-D pictorial representations of various aspects of
classical logics.  It should be noted that all recursively
decidable sentences of quantification theory can be reduced to
fully-instantiated quantifier-free form, at which point they
become isomorphic to sentences of Elementary Propositional
Calculus, in which the literals correspond to the propositional
variables, and the results of the previous paragraph apply.

=========================================================

My closing remark on the topic of Boolean lattices entails a brief
detour into what I call Paleolithic Model Theory:  This consists
primarily of the model-theoretic insights which follow from the
consideration of a PARTITION of all the cwffs of CLFO [Classical
Logic of Finite Order, AKA Theory of Types]. In this discussion, I
shall systematically abuse the word 'model(s)' by using it as an
abbreviation of "domain(s) of realization". I use the ASCII symbol
'@' as a substitute for the epsilon of membership.

The set of all cwffs of CLFO can be partitioned into two and
subsequently three [and more] blocks

                 **which are closed w.r.t.negation**.

The closure condition is fundamental, because it takes explicit
account of the dual-symmetries of classical logic. The blocks are
distinguished on the basis of whether [or not] one or both of the
elements possess models, and if so, upon the cardinality of such
models.

The initial, bi-partite, partition is the partition between the
ABSOLUTE and the CONTINGENT cwffs, where a cwff is *absolute*
iff it is either a contradiction or the negation of a contradiction
[i.e., a tautology], which is the *definition* of an *u-valid* cwff.
These cwffs live in a class called  'U', for Universal, since its
elements are either universally false or universally valid
[u-valid = syntactically provable  Note that I use HGM (Henkin
General Models) semantics.]  A cwff is *contingent* iff  it is not
absolute.  No absolute cwff can non-vacuously imply a contingent
cwff.

The contingent cwffs live in a class called  NK, which immediately
splits into the second and third blocks,  N  and K.  A cwff is an
element of  N  iff it is either an "axiom of infinity" [i.e., has
NO finite models, but is not contradictory] or is the negation of
such a cwff, which is the *definition* of an *n-valid* cwff.  B,~B
belong to  N  iff B is n-valid and ~B has no finite models.

    **Note that N contains all the true-but-unprovable cwffs.**

Finally, we have that  B,~B @ K  iff BOTH  B,~B  have finite
models, and I say that  B  is  k-valid iff the realization
[expansion] of B on a domain of  k  elements is a propositional
tautology.  If  B  is k- valid on at most finitely many finite
domains, then ~B is satisfiable on infinitely many finite domains,
and Dom(B) =df= the [set of] domain[s] of realization of B.

            Axiom of Dual-symmetry:  Dom(~B) = ~Dom(B) .

These two conditions describes the structure of the finite and co-
finite cones of the powerset lattice of omega.  [A "cone" in this
context is a class of paths through a Boolean lattice.]  If BOTH
B,~B have infinitely many finite models, as for example  "k is
prime", "k' is composite", then they describe the structure of the
*co-infinite* flats of the powerset lattice of omega, that is the
two complementary classes of limit-sets which can be thought of as
separating the upper and lower cones of the powerset lattice.  If
you visualize the lattice as composed of a pair of cones whose
vertices point in opposite directions and a pair of planes [flats]
which separate the cones, then the sets which are the limits of
the paths through the cones can be thought of as lying on the
flats.  Then, where the *terminal* nodes are the empty set and
omega, the set of non-terminal nodes of the lattice can be
bijectively mapped upon the classes of domain-equivalent cwffs of
the block K,  where  B, B' are domain-equivalent iff Dom(B) =
Dom(B').  [That may take a bit of chewing before you swallow it.]

There is a mature and well developed literature on the
relationship between ordinary [set-theoretical] model theory and
the class of sub-lattices known as *filters* [dual-ideals] and the
derivative structures of ultrafilters and ultraproducts, but
without my library I am not in a position to present a
bibliography.  I hope this brief introduction may serve to draw
the attention of at least a few FOM members to the subject.  It is
a very pretty subject, and as far as it goes, surprisingly
powerful.



APPENDIX I:

The Ramified Theory of Types differs from the Simple Theory of Types
only in the regard that types have ORDERS, and the Comprehension
Axiom enforces these orders as follows:  Where the Comprehension
Axiom is given as:

E/n(P)A/(j<n)(x/1, ... , x/k)[ P(x/1, ... , x/k) <=> R/n(x/1,... , x/k)]

and the quantifier is read as "There exists P of order n, s.t. for all x/i,
(1 =< i =< k) of order  j<n . . . ",  the subscripts  1, ... , k  merely
differentiate the arguments  x/i, and R is of arbitrary complexity except
that 'P' does not appear in R, AND

                 { max Ord(orders of non-quantified entities appearing in R)
Ord(R) =df= max { (or)
                 { 1 + max Ord(orders of quantified entities appearing in R)

and Ord(P) =df= Ord(R)

If the Order of R is set by the upper line [non-incremented] then
R is a predicative definition.  If the order of R is set by the
lower line [incremented] then the definition is impredicative, but
harmless, because P is now of higher type, and hence ineligible
for membership in a predicatively defined set and hence no
"vicious-circle" effect is possible.