Functoriality of pullbacks of sets

Functoriality of pullbacks of sets

[Colin McLarty]

It seems to me that Peter Freyd remarked it is easy to define pullbacks in
ZF (maybe with with global choice?) so that pullback along one side is
functorial, but hard to make it functorial on both sides.  In other words
we can easily make base change functorial in the bases, but not easily make
it functorial in the bases at the same time as in the total spaces.

Can anyone direct me to a reference to that work?

thanks, Colin

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Re: Functoriality of pullbacks of sets

[pjf]

On 2014-05-18 10:59, Colin McLarty wrote:
> It seems to me that Peter Freyd remarked it is easy to define pullbacks
> in
> ZF (maybe with with global choice?) so that pullback along one side is
> functorial, but hard to make it functorial on both sides.  In other
> words
> we can easily make base change functorial in the bases, but not easily
> make
> it functorial in the bases at the same time as in the total spaces.
>
> Can anyone direct me to a reference to that work?
>
> thanks, Colin

The subject of "Tau-Categories" was first exposed in my 1974
mimeographed "Pamphlet," and more accessibly in my 1990 book with Andre
Scedrov, "Categories, Allegories" (often called  "Cats and Alligators")
starting at 1.49 (p54). Every category with finite limits is equivalent
to a
tau-category with a functorial choice of finite limits (and the
construction is choice-free).  There is, indeed, a necessary asymmetry:
we can have canonical pullbacks so that if both interior rectangles in
the diagram

       .-.-.
       | | |
       .-.-.

are canonical pullbacks then so is the exterior rectangle, but then it
will not be the case that such holds for the rectangles in diagrams of
the form

       .-.
       | |
       .-.
       | |
       .-.

(unless, of course, the category is just a semi-lattice).

By using tau-categories one can remove the use of the axiom of choice
from the constructions of various representation theorems for
categories. At the end of my of my 2003 Foreword to the
TAC "reprinting" of "Abelian Categories"
(http://www.tac.mta.ca/tac/reprints/articles/3/tr3.pdf)
I remarked on how one thus gains added "functoriality" for the theorems.

    Best thoughts,
      Peter






[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Re: Functoriality of pullbacks of sets

[Vaughan Pratt]

On 5/19/2014 7:03 AM, pjf wrote:
> Every category with finite limits is equivalent to a
> tau-category with a functorial choice of finite limits (and the
> construction is choice-free).

Why merely finite?  Didn't you show this for all \omega-polynomials
(i.e. less than \omega^\omega), or have I overlooked something?

Vaughan


[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Re: Functoriality of pullbacks of sets

[Robin Cockett]

Another quite independent way of showing that limits can be chosen
canonically relies on

(a) being able to move to an equivalent category in which products are
canonical.
(b) being able to move to an equivalent category which has a "canonical
inclusion system"

Step (b) has received attention as it is related to subtype systems for CS
applications.  Essentially in the equivalent category each equivalence
class of monics  has a canonically chosen one: these have been studied
by  Grigore
Rosu (who called them "Weak inclusion systems"), by Andree Ehresmann (who
called them ss-admissible systems).  Recently they were linked to
restriction categories by Hilberdink ("Inclusions for Partiality" to appear
in MSCS).  There is an axiom of choice free way of doing (b) -- which does,
however, heavily use equivalence classes.  One moves to the partial map
category, this is a restriction category. One then splits the restriction
idempotents: they already split but one uses the formal splittings to give
one a canonical inclusion system then one moves back to the total map
category and !!bingo!! one gets an equivalent category to the original with
a canonical inclusion system.

To get canonical limits of all stripes one then just needs products to be
canonical ....

Of course, obtaining canonical limits in this manner does NOT make pulling
back functorial.   However, what it does immediately do is to make pulling
back of inclusions canonical.

-robin


On Mon, May 19, 2014 at 10:54 PM, Vaughan Pratt <pratt@cs.stanford.edu>wrote:

>
> On 5/19/2014 7:03 AM, pjf wrote:
>
>> Every category with finite limits is equivalent to a
>> tau-category with a functorial choice of finite limits (and the
>> construction is choice-free).
>>
>
> Why merely finite?  Didn't you show this for all \omega-polynomials
> (i.e. less than \omega^\omega), or have I overlooked something?
>
> Vaughan
>
>

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Re: Functoriality of pullbacks of sets

[pjf]

On 2014-05-20 00:54, Vaughan Pratt wrote:
> On 5/19/2014 7:03 AM, pjf wrote:
>> Every category with finite limits is equivalent to a
>> tau-category with a functorial choice of finite limits (and the
>> construction is choice-free).
>
> Why merely finite?  Didn't you show this for all \omega-polynomials
> (i.e. less than \omega^\omega), or have I overlooked something?
>
> Vaughan


Vaughan,

\omega^\omega did play a role (40 years ago!) but not the one you
describe.

The full subcategory of (ZF) sets whose objects are the von Neumann
ordinals has an easy tau-structure. The canonical pullbacks, for
example, are those in which the order on the NW corner coincides with
the order that is lexicographically induced by the two maps therefrom.
(So, yes, products are strictly associative and a monic is an
"inclusion" if it's order-preserving.) In section 1.4(12) of "Cats &
Alligators" \omega^\omega appears as the set of objects of a full
subcategory denoted _P_.

    METATHEOREM. A equation is true for all tau-categories iff it
    is true for _P_.

Given a counterexample in an arbitrary tau-category to an equation in
the (essentially algebraic) theory of tau-categories the proof
constructs (yes, constructs) a counterexample in _P_.

     Best thoughts,
       Peter



[For admin and other information see: http://www.mta.ca/~cat-dist/ ]