Tuesday, 18 February 2014

posets - Does ⋄ generate all De Morgan algebras?

(Asked by Nathaniel Hellerstein on the Q&A board at JMM)



This question is about De Morgan algebras (see also Wikipedia), which are something like Boolean algebras, but with a different weaker sense of the complement ∼. Namely, a De Morgan algebra is a bounded distributive lattice with an involution ∼ satisfying de Morgans laws.



Let ⋄ be the four element De Morgan algebra that is not a Boolean algebra, pictured below.




1

i j

0


where ∼0 = 1, ∼1 = 0, but ∼i = i and ∼j = j, so i and j and self-dual with respect to ∼. This algebra seems to express one of the fundamental differences between De Morgan algebras and Boolean algebras.



Question. Does the algebra ⋄ generate all De Morgan algebras, in the sense that every De Morgan algebra is a subalgebra of a homomorphic image of a product of ⋄?



Please see the related Birkhoff's HSP Theorem in universal algebra, concerning varieties of algebras closed under H, S, and P (homomorphic image, subalgebra and product).



(Edit: I edited the question to express the question as I understood it. I'm not sure whether the OP intended SHP as stated or HSP, which would conform with Birkhoff's theorem. Probably it was intended to take the variety generated by ⋄, that is, close {⋄} under H, S and P. The question then is whether this is equal to the class of all De Morgan algebras. Please revert if my edits are off-base.-JDH]



The ⋄ algebra can also be defined in terms of the usual 2 element Boolean algebra { f, τ } by using pairs denoted a/b, with the ∧ and ∨ operations defined coordinate-wise, but where, as mentioned by Dorais, the operation ∼ exchanges coordinates in addition to negating them, making for a "twisted square".




1 = τ/τ

i = τ/f j = f/τ

0 = f/f



~(a/b)=(~b/~a)
(a/b)∧(c/d) = (a∧c)/(b∧d)
(a/b)∨(c/d) = (a∨c)/(b∨d)


No comments:

Post a Comment