Re: associative product in Set

[Vaughan Pratt <pratt@cs.stanford.edu>]

>Is there a binary product in the category of sets and functions that is
>"strictly associative", i.e.
>
>A x (B x C) = (A x B) x C   and
>the associativity isomorphisms are equal to the identity?

Categorically speaking this question is undecidable.  The question has
different answers for equivalent copies of Set.

Isbell points out (reported in CTWM, end of VII-1) that if Set (or any
subcategory thereof containing a countably infinite set) is skeletal,
on-the-nose associativity is impossible.

Stacy Finkelstein in her thesis (or at least in a talk on Tau Categories
that I recall as being based on her thesis) gave a subcategory of Set
consisting of ordinals up to w^w and their (order-ignoring) functions
with an on-the-nose product.

In the course of the discussion following my question of 3/11/96 to this
list about the relative ease of defining set membership and composition
in terms of each other, I posted a similar construction (on 3/14/96) for
the whole of Set (more precisely, for a subcategory of Set consisting of
those sets that can be well-ordered, more precisely yet Ord(inals) and
their (order-ignoring) functions).  (I learned about Stacy's construction
shortly thereafter.)

These latter versions of Set are of course not skeletal by virtue of
distinct ordinals (w, w+1, etc.) being isomorphic, necessary by Isbell's
observation.

Whereas my set-membership question and its subsequent lengthy discussion
were I gather appreciated by many, the reactions to the on-the-nose
product I posted as part of it varied from indifference to outright
hostility.  On reflection these reactions, coming from category theorists,
are entirely consistent with the categorical undecidability of whether
Set admits on-the-nose product.

Vaughan Pratt