- Trivial answers 1
- Important answer 2
- Example of a non-trivial Boolean center 2
- Generalization of this answer 2
- Non-trivial Boolean families 3
- Analysis, and generalization 3
- Non-minimal augmentation of Boolean lattices 5
- Discussion : what about logic ? 6
Appendix and Bibliographical Note 7
The question re classical vis-a-vis subclassical logic
After the initial astonishment that self-contradictions need not be logical black holes, there is a big question: how can classical reasoning find a place in a subclassical logic, such as the minimal subclassical logic FDE?
Classical propositional logic is, in a fairly straightforward sense, the theory of Boolean algebras. In the same sense we can say that the logic of tautological entailment, aka FDE, is the theory of De Morgan algebras.
In previous posts I have also explored the use of De Morgan algebras for truthmakers of imperatives and for the logic of intension and comprehension. So FDE’s algebraic counterpart has some application beyond FDE.
How, and to what extent, can the sub-classical logic FDE accommodate classical logic, or classical theories, as a special case? A corresponding question for algebraic logic is how, or to what extent, Boolean algebras are to be found inside De Morgan algebras.
Terminology. Unless otherwise indicated I will restrict the discussion to bounded De Morgan algebras, that is, ones with top (T) and bottom (⊥), these are distinct elements and ¬T = ⊥. If L is a De Morgan lattice, an element e of L is normal iff e ≠¬e, and L is normal iff all its elements are normal. Both sorts of algebras are examples of distributive lattices. From here on I will use “lattice” rather than “algebra”.
1 Trivial answers
There are some simple, trivial answers first of all, and then two answers that look more important.
First, a Boolean lattice is a De Morgan lattice in which, for each element e, (e v ¬e ) = T (the top), or equivalently, (e ∧¬e) = ⊥ (the bottom).
Secondly, in a De Morgan lattice, the set {T, ⊥} is a Boolean lattice.
Thirdly, if L is De Morgan lattice and its element e is normal, then the quadruple {(e v ¬ e), e, ¬e, (e ∧ ¬e)} is a Boolean sub lattice of L.
2 Important answer
More important is this: If L is a De Morgan lattice then B(L) = {x in L: (x v ¬ x) = T} is closed under ∧, v, and ¬ and is therefore a sub-lattice of L. It is a Boolean lattice: the Boolean Center of L.
3 Example of non-trivial Boolean center
Mighty Mo:
Figure 1 The eight-element De Morgan lattice Mo
The Boolean Center B(Mo) = {+3, +0, -0, -3}.
4 Generalization of this answer
My aim here is to display Boolean lattices that ‘live’ inside De Morgan lattices. My general term for them will be Boolean families. They will not all be of the type, and I hope that their variety will itself offer us some insight.
The fact that a De Morgan lattice has a Boolean center can be generalized:
Suppose element e is such that (e v ¬e) is normal, and define B(e) = {x in L: (x v ¬ x) = (e v ¬e)}. Then (see Appendix for proof) B(e) is a Boolean family, with top = (e v ¬e) and bottom = (e ∧ ¬e).
5 Non-trivial Boolean families
The big question: are there examples of non-trivial Boolean families distinct from the Boolean center?
We can construct some examples by adding ‘alien’ points to a Boolean lattice. For example this, which I will just call L1.
Figure 2 L1, augmented B3
This lattice L1 is made up from the three-atom Boolean lattice B3 by adding an extra top and bottom. This sort of addition to a lattice I will call augmentation, and I will call L1 augmented B3. For the involution we keep the Boolean complement in B3, and extend this operation by adding that T = ¬ ⊥ , and ⊥ = ¬T.
L1 is distributive, hence a De Morgan lattice (proof in Appendix). The clue to the proof is that for all elements e of L1, T ∧ e = e and T v e = T.
The Boolean center B(L1) = {T, ⊥} is trivial, and the sublattice B3 is a non-trivial Boolean family.
6 Analysis of this example, and generalization
In the above reasoning nothing hinged on the character of B3, taken as example. Augmenting any Boolean lattice B in this way will result in a De Morgan lattice with trivial Boolean center and B as a Boolean sublattice. But this still does not go very far. For the concept of Boolean families in De Morgan lattices to be possibly significant requires at least that there is a large variety of non- or not-nearly trivial examples.
To have a large class of examples with more than such a single central Boolean sublattice, we have to look for a construction to produce them. And this we can do by ‘multiplying’ lattices. I will illustrate this with B3, and then generalize.
B3 as a product lattice
The Boolean lattice B3 is the product B1 x B2 of the one-atom and two-atom Boolean lattices. The product of lattices L and L’ is defined to be the lattice whose elements are the pairs <x,y> with x in L and y in L’, and with operations defined pointwise. That is:
<x,y> v <z,w> = <x v z, y v w>
<x,y> ∧ <z,w>= <x ∧ z, y ∧ w>
¬<x, y> = < ¬x, ¬y>
<x,y> ≤ <z,w> iff <x,y> ∧ <z,w> = <x, y>, iff x ≤ z, and y ≤ w
Any such product of Boolean lattices is a Boolean lattice.
Figure 3. B3 as a product algebra.
It looks a bit like ordinary multiplication: B1 has 2 elements, B2 has 4 elements, 2 x 4 = 8, the number of elements of their product B3.
Inspecting the diagram, and momentarily ignoring the involution, we can see that B3 has two sublattices, that are each isomorphic to B2. (The definition of ‘sublattice’ refers only to the lattice operations ∧ and v.) That is to say, the components of the product construction show up as copies in the product. And that is also the case once we take the involution into account, given a careful understanding of this ‘copy’ relation.
The way we find these sublattices: choose one element in B1 to keep fixed and let the second element vary over B2:
sublattice B3(1) has elements T2, T1, T ⎯ 1, T0
sublattice B3(2) has elements ⊥2, ⊥1, ⊥⎯ 1, ⊥0
Sublattices so selected will be disjoint, for in one the elements have T as first element and in the other the elements have ⊥ as first element.
These sublattices are intervals in B3, e.g. B3(1) = {x in B3: T0 ≤ x ≤ T2}.
What about the involution? The restriction of the operator ¬ on B3 to interval B3(1) is not well-defined, for in B3, ¬ T2 is not in B3(1), it is ¬ T2 = ⊥0 which is in B3(2).
However, there is a unique extension to a Boolean complement on B3(1): start with what we have from B3, namely that ¬T1 = T ⎯1 and ¬ (T ⎯1) = T1, then add that ¬T2 = T0 and ¬T0 = T2 (“relative complement”; cf. remark about Theorem 10 on Birkhoff page 16, about relative complements in distributive lattices). It is this relatively complemented interval that is the exact copy of B2, which is a different example of a Boolean family.
(Looking back to section 5, we can now see that the example there was a simple one, where the restriction of the lattice’s involution, to the relevant sublattice, was well-defined on that sub lattice.)
Thus if we have a product of many Boolean algebras, that product will contain many Boolean families:
If L1, L2, …, LN, are Boolean lattices and L = L1 x L2 x … x LN, then L has disjoint Boolean families isomorphic to L1, L2, …, LN
For example, if e1, e2, …, eN are elements of L1, L2, …, LN respectively, then the set of elements S(k) = {<e1, e2, …, ek-1, x, ek+1, …eN>: x in Lk} form a sublattice of L that is (with the relative complement on S(k) defined as above) isomorphic to Lk. (See Halmos, page 116, about the projection of L onto Lk, for precision.)
And if we then augment that product L, in the way we formed L1, we arrive at a non-Boolean De Morgan lattice, augmented L. The result contains many Boolean families, but (e ∧ ¬e) is in general not the bottom, so it lends itself to adventures in sub classical logic.
But we need to turn now to a less trivial form of augmentation.
7 Non-minimal augmentation of Boolean lattices
A product of distributive lattices is distributive (by a part of the argument that a product of Boolean lattices is Boolean).
The product of De Morgan lattices is a De Morgan lattice. To establish that, we need now only to check that the point-wise defined operation ¬ on the product is an involution (see Appendix for the proof).
So suppose we have, as above, a Boolean lattice product B, that has many Boolean families, and we form its product with some other, non-trivial non-Boolean De Morgan lattice, of any complexity.
The result is then a non-trivial non-Boolean De Morgan lattice with many Boolean families.
8 Discussion: what about logic?
The basic sub-classical logic FDE has as non-logical signs only ¬ , v, and ∧. That is not enough to have Boolean aspects of De Morgan lattices reflected in the syntax.
For example, the equation (a v ¬ a) = (b v ¬ b) defines an equivalence relation between the propositions (a, b). But the definition involves identity of propositions, which for sentences corresponds to a necessary equivalence. To express this, a modal connective, say <=>, could be introduced, in order to identify a fragment of the language suitable for formulating classical theories.
There is much to speculate.
APPENDIX
[1] Define, for any De Morgan lattice L, B(e) = {x in L: (x v ¬ x) = (e v ¬e)}.
Theorem. If L is a De Morgan lattice and its element (e v ¬e) is normal, then B(e) is a Boolean sublattice of L.
First, all elements of B(e) are normal. For (e v ¬e) is normal, and if x is not normal then (x v ¬x) = x.
For B(e) to be a sublattice with involution of L it suffices that B(e) is closed under under the operations ∧, v, and ¬ on L.
Define t = (e v ¬e). If d and f are in B(e) then
- ¬d is also in B(e), for ¬d v ¬ ¬d = d v ¬d = t
- (d v f) is also in B(e) because
[(d v f) v ¬(d v f) ] = [(¬ d ∧ ¬f) v (d v f)]
= [(¬ d v d v f)] ∧ (¬f v d v f)]
= t ∧ t
(d ∧ f) is also in B(e) because
[(d ∧ f) v ¬(d ∧ f) ] = [(d ∧ f) v (¬ d v ¬f)]
= [(d v ¬ d v ¬ f)] ∧ (f v ¬ d v ¬ f)]
= t ∧ t
So B(e) is a sublattice of L, and hence distributive. It has involution ¬, its top is t and bottom ¬t. So B(e) is a bounded De Morgan lattice. B(e) is Boolean, because all its elements x are such that (x v ¬ x) = t.
B(T) is the Boolean center of the lattice.
[2] Theorem. The lattice L1, the augmented lattice B3, is a De Morgan lattice.
(a) The operation ¬ extended from B3 to L1 by adding that T = ¬ ⊥ , and ⊥ = ¬T, is an involution. The addition cannot yield exceptions: each element e of L1 is such that ⊥ ≤ e ≤ T, which is equivalent to, for all elements e of L1, ¬ T ≤ ¬ e ≤ ¬⊥.
(b) To prove that L1 is distributive, we note that, for all elements e of L1,
T ∧ e = e and T v e = T.
⊥ ∧ e = ⊥ and ⊥ v e = e.
To prove: If x, y, z are elements of L1 then x ∧ (y v z) = (x ∧ y) v (x ∧ z).
- clearly, that is so when x, y, z all belong to B3
- T ∧ (y v z) = (y v z) and (T ∧ y) v (T ∧ z) = y v z
- x ∧ (T v z) = (x ∧ T) = x and (x ∧ T) v (x ∧ z) = x v (x ∧ z) = x
- ⊥ ∧ (y v z) = (⊥ ∧ y) v (⊥ ∧ z) = ⊥
- x ∧ (⊥ v z) = (x ∧ ⊥) v (x ∧ z) = ⊥ v (x ∧ z) = x ∧ z
The remaining cases are similar.
[3] Theorem. A product of De Morgan lattices is a De Morgan lattice.
The product of any distributive lattices is a distributive lattice (Birkhoff 1967: 12)
To establish that the product of De Morgan lattices is a De Morgan lattice, we need then only to check that the point-wise defined operation ¬ on the product is an involution.
Let L1 and L2 be De Morgan lattices and L3 = L1 x L2. Define ¬<x. y> = <¬x, ¬y>
- ¬¬<x,y> = ¬<¬x, ¬y> = <¬ ¬x, ¬ ¬y> = <x, y>
- suppose <x, y> ≤ <z, w>. Then, x ≤ z and y ≤ w, and therefore ¬ z ≤ ¬ x and ¬ w ≤ ¬ y. So ¬<z, w> ≤ ¬<x, y>
Bibliographical note.
For the relation between FDE and De Morgan lattices see section 18 (by Michael Dunn) of Anderson, A. R. and N. D. Belnap (1975) Entailment: The Logic of Relevance and Necessity. Princeton.
For distributive lattices in general and relative complementation see Birkhoff, Garrett (1967) Lattice Theory. (3rd ed.). American Mathematical Society and Grätzer, George (2009/1971) Lattice Theory: First Concepts and Distributive Lattices. Dover.
For products of Boolean lattices see section 26 of Halmos, P. R. (2018/1963) Lectures on Boolean Algebras. Dover.
Bas van Fraassen's philosophy blog 