* 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).