(So if Z is 3 then there are 27 = 3^3 "Boolean" operations in place of the familiar 4 = 2^2.)
There should have been a "unary" in there of course. Another question about these Q-algebras that Oswald Wyler was asking about: what is a necessary and sufficient condition for a complete basis for finitary Q-algebras (the theory of Boolean algebras rather than CABAs) having any given Z? For Z = 2 one answer (at least for the version of the problem which only considers nonzeroary operations) is that for each of the following properties the basis must contain a counterexample to that property. Necessity follows because each property is preserved under composition; sufficiency takes more work. * selfdual (e.g. xy+yz+zx = (x+y)(y+z)(z+x)) * monotone * affine (expressible as the XOR of its arguments, optionally plus 1) * strict (maps the all-zeros input to zero) * costrict (maps the all-ones input to one) (NAND violates all five at once.) Is there a fixed number of such properties that works for all finite cardinalities of Z, or must the number of properties of this kind grow with Z? Vaughan Pratt
Hi Vaughan, Regarding these and similar questions, I suggest looking at the following two gems: A. L. Foster, Gerneralized "Boolean" theory of universal algebras, Part II. Identities and subdirect sums of functionally complete algebras, Math. Zeit. 59, 1953, 191-199. T.-K. Hu, Stone duality for primal algebra theory, Math. Zeit. 110, 1060, 180-198. Ernie Manes ----- Original Message ----- From: "Vaughan Pratt" <pratt@cs.stanford.edu> To: <categories@mta.ca> Sent: Thursday, May 08, 2003 3:05 PM Subject: categories: Re: Query (Q-algebras)
(So if Z is 3 then there are 27 = 3^3 "Boolean" operations in place of the familiar 4 = 2^2.)
There should have been a "unary" in there of course.
Another question about these Q-algebras that Oswald Wyler was asking about: what is a necessary and sufficient condition for a complete basis for finitary Q-algebras (the theory of Boolean algebras rather than CABAs) having any given Z? For Z = 2 one answer (at least for the version of the problem which only considers nonzeroary operations) is that for each of
following properties the basis must contain a counterexample to that
Necessity follows because each property is preserved under composition; sufficiency takes more work.
* selfdual (e.g. xy+yz+zx = (x+y)(y+z)(z+x)) * monotone * affine (expressible as the XOR of its arguments, optionally plus 1) * strict (maps the all-zeros input to zero) * costrict (maps the all-ones input to one)
(NAND violates all five at once.) Is there a fixed number of such
that works for all finite cardinalities of Z, or must the number of
the property. properties properties
of this kind grow with Z?
Vaughan Pratt
participants (2)
-
Ernie Manes -
Vaughan Pratt