* Query @ 2003-05-05 17:46 ` Oswald Wyler 2003-05-07 18:55 ` Query (Q-algebras) Vaughan Pratt 0 siblings, 1 reply; 4+ messages in thread From: Oswald Wyler @ 2003-05-05 17:46 UTC (permalink / raw) To: categories For every set Z, there is a self-adjoint contravariant functor Q=ENS(--,Z), with unit/counit h:Id-->Q^op Q given by (h_X)(x)(f)=f(x). Let Q-alg denote the category of algebras for the monad induced by this self-adjunction. If Z is not empty or a singleton, then the comparison functor ENS^op-->Q-alg is an equivalence by results of M. Sobral. If Z has two members, then Q-alg is isomorphic to CaBool, the category of complete atomic Boolean algebras. What is known about Q-alg if Z has more than two members (beyond the fact that Q-alg and CaBool are equivalent)? ^ permalink raw reply [flat|nested] 4+ messages in thread
* re: Query (Q-algebras) 2003-05-05 17:46 ` Query Oswald Wyler @ 2003-05-07 18:55 ` Vaughan Pratt 2003-05-08 19:05 ` Vaughan Pratt 0 siblings, 1 reply; 4+ messages in thread From: Vaughan Pratt @ 2003-05-07 18:55 UTC (permalink / raw) To: categories The operations of Q-alg are the functions between the powers of the set Z, forming the (Lawvere) theory T of Q-algebras, which are product-preserving functors from T to Set. (So if Z is 3 then there are 27 = 3^3 "Boolean" operations in place of the familiar 4 = 2^2.) With all powers Q-algebras are equivalent to CABAs, with only finite powers and finite-product-preserving functors they are equivalent to Boolean algebras. A natural next question would be, what is obtained when T is taken to be Set itself, in each of the cases when the functors T->Set are required to preserve all limits, and just the discrete ones? Vaughan Pratt >From: Oswald Wyler <owyler@suscom-maine.net> >For every set Z, there is a self-adjoint contravariant functor Q=ENS(--,Z), >with unit/counit h:Id-->Q^op Q given by (h_X)(x)(f)=f(x). Let Q-alg denote >the category of algebras for the monad induced by this self-adjunction. >If Z is not empty or a singleton, then the comparison functor ENS^op-->Q-alg >is an equivalence by results of M. Sobral. If Z has two members, then Q-alg >is isomorphic to CaBool, the category of complete atomic Boolean algebras. >What is known about Q-alg if Z has more than two members (beyond the fact >that Q-alg and CaBool are equivalent)? ^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: Query (Q-algebras) 2003-05-07 18:55 ` Query (Q-algebras) Vaughan Pratt @ 2003-05-08 19:05 ` Vaughan Pratt 2003-05-09 11:24 ` Ernie Manes 0 siblings, 1 reply; 4+ messages in thread From: Vaughan Pratt @ 2003-05-08 19:05 UTC (permalink / raw) To: categories >(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 ^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: Query (Q-algebras) 2003-05-08 19:05 ` Vaughan Pratt @ 2003-05-09 11:24 ` Ernie Manes 0 siblings, 0 replies; 4+ messages in thread From: Ernie Manes @ 2003-05-09 11:24 UTC (permalink / raw) To: categories 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 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 > > ^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2003-05-09 11:24 UTC | newest] Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- [not found] <owyler@suscom-maine.net> 2003-05-05 17:46 ` Query Oswald Wyler 2003-05-07 18:55 ` Query (Q-algebras) Vaughan Pratt 2003-05-08 19:05 ` Vaughan Pratt 2003-05-09 11:24 ` Ernie Manes
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).