[FOM] FTGI Powerset [Boolean] Lattices

[steve newberry]

BOOLEAN LATTICES FOR LOGICIANS

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]. 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 sbst y sbst T 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 of 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 will reward you to spend a 
few minutes in contemplation.]

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 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. [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 3-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**. [This is 
axiomatic.] 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].  A cwff is 
*contingent* iff it is not absolute. No absolute cwff can non-vacuously 
materially 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. 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. Dom(B) =df= the [set of] domain[s] of 
realization of B and Dom(~B) = ~Dom(B) [Axiom of Dual-symmetry].  [I follow 
the terminology of Henkin General Models, HGM.]

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 the universe, 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/n(x/1, ... , x/k)[ P(x/1, ... , x/k) <=> R/n(x/1, ... , x/k)]

and the subscripts 'n' encode the type-order, 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.