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/ ]
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/ ]
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/ ]
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/ ]
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/ ]
participants (4)
-
Colin McLarty -
pjf -
Robin Cockett -
Vaughan Pratt