[PRL] isomorphic fixed points

Mitchell Wand wand at ccs.neu.edu
Sun Nov 6 22:20:00 EST 2005


Riccardo Pucella wrote:

>>>    Once one accepts that isomorphism is a poor notion of
>>> equivalence, one might find this very troubling for category
>>> theory.  If objects are so frequently isomorphic, are not the
>>> results of category theory somewhat vacuous?  We are talk about
>>> lists, and Nats etc as if they were different "objects", but in
>>> the end, they all seem to be isomorphic!  I think the answer to
>>> this is to remember that what are important are the arrows and not
>>>the objects.
>>>      
>>>
>>Category theorists seldom concern themselves with isomorphism of
>>objects.  Natural isomorphism of functors is more important, both
>>for category theory and for computer science.
>>    
>>
>
>Indeed. In fact, most things of interest in category theory are constructed
>up-to-isomorphism, meaning that the same result will be obtained if we
>start from isomorphic objects. Isomorphism is an equivalence to get rid of
>irrelevant details. Most set-theoretic constructions do not depend at all
>on the elements of the set. 
>
>
>If you have a set-theoretic construction that does depend on the elements
>of the set, chances are you are using additional structure on the set (if
>only at the level of the elements of the set), and this structure should be
>reflected by the category (different objects, or different arrows). 
>
>
>(I recognize that Peter was saying all along that isomorphism is not the
>right form of equivalence to consider. All I am saying is that the use of
>sets as an example of this point is a bit of a red herring, since people
>talk about sets when they often have something with more structure in
>mind.)
>
>
> Cheers, 
> Riccardo
>
>
>  
>
I was not at the talk, either.  The real question is "isomorphic in what 
sense"?  Isomorphism in the category of sets means nothing more nor less 
than "has the same cardinality".  Consider two directed graphs:

Nodes_G = {a, b}   Edges_G = {(a,a), (b,b)}
Nodes_H = {a, b}   Edges_H = {(a,b), (b,a)}

These guys have the same number of nodes and the same number of edges, 
so (given suitable coding) they are isomorphic in the category of sets.  
But they are certainly NOT isomorphic in the category of directed 
graphs-- there is no bijection  f  from Nodes_G to Nodes_H that 
preserves the property of  "being connected by an edge", ie

    for all x, y in Edges_G,  
      (f(x),f(y)) in Edges_H iff (x,y) in Edges_G

In other words there is no isomorphism that preserves the graph structure.

On the other hand, consider

Nodes_G = {a, b}   Edges_G = {(a,a), (b,b)}
Nodes_J = {c,d}     Edges_J = {(c,c), (d,d)}

These two ARE isomorphic in the category of directed graphs (indeed, 
there are two such isomorphisms), because the map you are thinking of 
preserves the graph structure in the sense given above.

The moral of the story is that it's either meaningless or useless to 
talk about things being isomorphic unless you are explicit about the 
properties that are to be preserved by the isomorphism.  Most often this 
means specifying the category in which the isomorphism is to be found.  
And, as Riccardo points out, the category of Sets is almost always not 
what you meant.

Hope that's helpful.

--Mitch

-------------- next part --------------
HTML attachment scrubbed and removed


More information about the PRL mailing list