From mboxrd@z Thu Jan  1 00:00:00 1970
X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/2273
Path: news.gmane.org!not-for-mail
From: Vaughan Pratt <pratt@CS.Stanford.EDU>
Newsgroups: gmane.science.mathematics.categories
Subject: Re: Query (Q-algebras)
Date: Thu, 08 May 2003 12:05:50 -0700
Message-ID: <E19DrRz-00074B-00@mailserv.mta.ca>
References: <pratt@CS.Stanford.EDU>
NNTP-Posting-Host: main.gmane.org
X-Trace: ger.gmane.org 1241018541 3348 80.91.229.2 (29 Apr 2009 15:22:21 GMT)
X-Complaints-To: usenet@ger.gmane.org
NNTP-Posting-Date: Wed, 29 Apr 2009 15:22:21 +0000 (UTC)
To: categories@mta.ca
Original-X-From: rrosebru@mta.ca Thu May  8 16:53:33 2003 -0300
Return-path: <cat-dist@mta.ca>
Envelope-to: categories-list@mta.ca
Delivery-date: Thu, 08 May 2003 16:53:33 -0300
Original-Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
	id 19DrRz-00074B-00
	for categories-list@mta.ca; Thu, 08 May 2003 16:53:07 -0300
In-Reply-To: Message from Vaughan Pratt <pratt@CS.Stanford.EDU>
   of "Wed, 07 May 2003 11:55:08 PDT." <200305071855.LAA22674@coraki.Stanford.EDU>
Original-Sender: cat-dist@mta.ca
Precedence: bulk
X-Keywords: 
X-UID: 8
Original-Lines: 30
Xref: news.gmane.org gmane.science.mathematics.categories:2273
Archived-At: <http://permalink.gmane.org/gmane.science.mathematics.categories/2273>



>(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