Subject: categories: Addendum

From: Peter Freyd <[email-masked]>
Date: Sat, 15 Jan 2000 13:07:11 -0500 (EST)

Sorry for the clutter. I forgot a counterexample. Yes, it is
possible for  (X*X)*X  to have a final coalgebra but not  X*X.  On the
discrete category with two objects, A  and  B, let the bifunctor be
defined by:
               * | A  B
               --+------
               A | B  A
               B | A  A

The unique cubical coalgebra is  A  but there is no square coalgebra.

What I don't have is a counterexample with an _associative_ bifunctor.

---

From: Vaughan Pratt <[email-masked]>
Date: Sun, 16 Jan 2000 22:37:40 -0800

>What I don't have is a counterexample with an _associative_ bifunctor.

How about the positive integers with * as sum, with 1->3 as the only
nonidentity arrow?  The unique cubical coalgebra is  1  but there is no
square coalgebra.

Vaughan

---

From: Vaughan Pratt <[email-masked]>
Date: Mon, 17 Jan 2000 13:18:18 -0800

>nonidentity arrow?  The unique cubical coalgebra is  1  but there is no

Oops, that gets associativity at the cost of * no longer being a functor
(pointed out to me by Peter Selinger).

Ok, let me dig myself in deeper by making my example more complicated.
Instead of 1->3, put an arrow from i to j whenever i <= j <= 2i.
Now every i is a square coalgebra but no i is a cubical coalgebra.

Now adjoin a new object oo (infinity), with x+oo = oo+x = oo for all x,
and the identity at oo as the only new arrow.  oo is both a square *and*
a cubical coalgebra.  Since it is disconnected from the other square
coalgebras there can't be a final such.  But oo is the only cubical
coalgebra, with only one self-map, making it a final cubical coalgebra.

Vaughan

---

From: "Dr. P.T. Johnstone" <[email-masked]>
Date: Tue, 18 Jan 100 09:49:42 +0000 (GMT)

> nonidentity arrow?  The unique cubical coalgebra is  1  but there is no

Doesn't sound very functorial to me.

Peter Johnstone

---

From: Vaughan Pratt <[email-masked]>
Date: Tue, 18 Jan 2000 11:47:41 -0800

> Instead of 1->3, put an arrow from i to j whenever i <= j <= 2i.

I keep forgetting to make a list of what to remember.  Peter Johnstone
kindly put me out of my misery on this noncategory.

Since I don't seem to be having much luck making the example more
complicated, maybe making it simpler might work.

The ring of integers mod 3 is a one-object monoidal category in the
usual way, with multiplication as composition and addition as the monoid.

Every arrow is clearly both a square coalgebra and a cubical coalgebra,
i.e. we have three of each.

Claim: There are no final square coalgebras, but 1 and 2 are final
cubical coalgebras.

Proof.  Square coalgebra homomorphisms f from 2x to x (as square
coalgebras) are those that satisfy xf = (2f)(2x).  But 2x2 = 1 (mod
3) so every f solves this.  Hence there are three square coalgebra
homomorphisms from 2x to x, whence no x is a final square coalgebra.

Cubical coalgebra homomorphisms f from y to x (as cubical coalgebras)
must satisfy xf = (3f)y = 0.  But for x other than 0, f = 0 is the only
solution.  So the two nonzero cubical coalgebras are final.

The same example (unless I've forgottten yet another thing) solves the
corresponding problem for initial algebras.

Vaughan