Addendum

Addendum

[Peter Freyd]

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.

Re: Addendum

[Vaughan Pratt]

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

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

Re: Addendum

[Vaughan Pratt]

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

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

Re: Addendum

[Vaughan Pratt]

> 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

Re: Addendum

[Dr. P.T. Johnstone]

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

Doesn't sound very functorial to me.

Peter Johnstone

Addendum

[Peter Freyd]

I wrote:

  [I]n the category  of  N-sets (sets with a distinguished self-map)
  let  A  be the two-element set in which the distinguished self-map
  has a unique fixed point....A^A, the object of self-maps of  A,
  falls apart as a coproduct (disjoint union) of continuously many
  N-sets. Hence if one takes the set of equivalence classes of  A^A,
  where the equivalence relation is the double-negation of equality,
  one obtains a discrete set (it has trivial N-action) whose
  cardinality is the continuum.

It's more complicated. One obtains a disjoint union of "cycles", that
is, objects of the form  Z/nZ  where the distinguished self-map is
addition by  1. For each  n > 0  there are only a finite number of
copies of  Z/nZ. The number of copies of  Z = Z/0Z  is uncountable.

Postscript:

The sequence of numbers of copies of each finite cycle is, of course,
guaranteed to be in Neil Sloan's "On-Line Encyclopedia of Integer
Sequences", but we didn't have that. Instead in 1.925 of Cats &
Alligators we gave a ridiculous -- but both correct and unimprovable
-- formula for that finite number. Preceding it was a sentence that
begins "Bearing in mind that, as far as we know, this is computation
for its own sake". Anyway, you can find the same formula at

      mathworld.wolfram.com/IrreduciblePolynomial.html

under the name  L_q(n)  (with  q = 2).

With the exception of the zero'th value (in our case it's
2^{\Aleph_0}, for Lyndon words it's 1) here's what Sloan has to say:


ID Number: A001037 (Formerly M0116 and N0046)
URL:       http://www.research.att.com/projects/OEIS?Anum=A001037
Sequence:  1,2,1,2,3,6,9,18,30,56,99,186,335,630,1161,2182,4080,7710,
           14532,27594,52377,99858,190557,364722,698870,1342176,
           2580795,4971008,9586395,18512790,35790267,69273666,
           134215680,260300986,505286415,981706806
Name: Degree n irreducible polynomials over GF(2); n-bead necklaces
           with beads of 2 colors when turning over is not allowed and
           with primitive period n; binary Lyndon words of length n.
Comments:  Also dimensions of free Lie algebras - see A059966, which is
           essentially the same sequence.
References E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p.
              84.
           R. Church, Tables of irreducible polynomials for the first
              four prime moduli, Annals Math., 36 (1935), 198-209.
           E. N. Gilbert and J. Riordan, Symmetry types of periodic
              sequences, Illinois J. Math., 5 (1961), 657-665.
           M. A. Harrison, On the classification of Boolean functions
              by the general linear and affine groups, J. Soc. Indust.
              Appl. Math. 12 (1964) 285-299.
           M. Lothaire, Combinatorics on Words. Addison-Wesley,
              Reading, MA, 1983, p. 79.
           G. Melancon, Factorizing infinite words using Maple,
              MapleTech journal, vol 4, no. 1, 1997, pp. 34-42, esp.
              p. 36.
           M. R. Nester, (1999). Mathematical investigations of some
              plant interaction designs. PhD Thesis. University of
              Queensland, Brisbane, Australia.
           G. Viennot, Algebres de Lie Libres et Monoides Libres,
              Lecture Notes in Mathematics 691, Springer verlag 1978.