12
$\begingroup$

I asked this some days ago over at math.se, and while the question got 10 upvotes, I didn't get too many answers. Although it is a "soft question", maybe the general issue is interesting enough to raise again here in the hope of more answers.

The Church/Turing Thesis that we all know and love asserts that every algorithmically computable function (in an informally characterized sense) is in fact recursive/Turing computable/lambda computable. A certain intuitive concept, the Thesis claims, in fact picks out the same functions as certain (provably equivalent) sharply defined concepts.

Evidence? Two sorts: (1) "quasi-empirical", i.e. no unarguable clear exceptions have been found, (2) conceptual, as in for example Turing's own efforts to show that when we reflect on what we mean by algorithmic computation we get down to the sort of operations that a Turing machine can emulate.

OK, now compare. The "Eilenberg/Mac Lane Thesis" in one version (but does anyone call it that??) is that if an isomorphism between widgets and wombats is intuitively "natural" (i.e. doesn't depend on arbitrary choices of co-ordinates, or the like) then it can be regimented as an natural isomorphism between suitable functors in the official category-theoretic sense. A certain intuitive concept, the Thesis claims, in fact picks out the same isomorphisms as a certain sharply defined concept.

Evidence? We'd expect two sorts. (1*) "quasi-empirical", i.e. no clear exceptions. (2*) conceptual ...

Two main questions:

(A) But are there no exceptions? Or (to take the perhaps more likely direction of failure) are there well known cases where we can say "Hey, this is the sort of isomorphism whose intuitive naturalness was surely of the kind that Eilenberg/Mac Lane were trying to chraracterize, back in the day: but actually, you can't shoehorn this case into the framework of their theory of natural isomorphisms."

(B) Assuming the Thesis isn't defeated by counter-example (or is true for some nice class of cases), what are the best efforts at trying to show that, conceptually, it "ought" to be true (when it is)?

And then I suppose that there is a supplementary question arising of category theoretic etiquette:

(C) Assuming again the Thesis isn't obviously defeated by counter-example, is it secure enough for it now to be acceptable to slide without further argument from showing that there is an isomorphism between widgets and wombats constructed in an intuitively "natural", unarbitrary, way to announcing that there is therefore a natural isomorphism here?

$\endgroup$
  • 10
    $\begingroup$ There are plenty of "natural" constructions in mathematics that are not functorial (or natural) with respect to the usual notion of morphism of the objects involved (for a simple example, consider the construction that takes a set $X$ and give the set of $2$-element subsets of $X$). What is much more robust (and I would even say without exception) is that any "natural" construction is functorial/natural with respect to isomorphisms. $\endgroup$ – Eric Wofsey Jul 14 '15 at 7:49
  • 2
    $\begingroup$ The contrapositive is false: there are natural morphisms that are defined by first choosing some arbitrary information which turns out to be irrelevant (e.g. picking a basis for a vector space, and then the result is independent of the choice). Also, don't just think of natural isomorphisms, since the important examples E&MacL started from were not (maps between cohomology theories, for instance Cech for different covers) $\endgroup$ – David Roberts Jul 14 '15 at 8:20
  • $\begingroup$ Yes, I know that E & MacL were after a general story about natural transformations: I thought, rightly or wrong, it would be helpful here to narrow the question by focusing on isomorphisms. $\endgroup$ – Peter Smith Jul 14 '15 at 8:36
  • 2
    $\begingroup$ However, the definition of a 'canonical' morphism is a bit more vague, and possibly is encoded in the idea of being natural with respect to isomorphisms only. This is perhaps what you were after? See ncatlab.org/nlab/show/core-natural+transformation for discussion, and the MO question mathoverflow.net/questions/19644/… $\endgroup$ – David Roberts Jul 14 '15 at 9:29
  • 1
    $\begingroup$ I'm just writing to say I think this is a very interesting question. I don't find myself on mathOverflow that often, so if someone answers this, could somebody alert me? $\endgroup$ – Emily Riehl Aug 12 '15 at 20:58
4
$\begingroup$

There is probably no definite answer to this question. But let me propose a few ideas:

1) this kind of general "thesis" only makes sense for naturality with respect to isomorphisms:

There is plenty of examples of perfectly natural and canonical construction (in a naive sense) that are not functorial with respect to arbitrary morphisms:

The center of a group or an algebra, the group of automorphism of some object etc... are example of construction that are functorial only with respect to isomorphisms.

For example of a natural transformation which is only functorial on isomorphims not an isomorphism, consider the category $P$ of partially ordered set and monotone map between them. Consider the functors, $F:P \rightarrow sets$ the functor that forget the ordering, and $B: P \rightarrow Set$ that send any poset to $\{0,1\}$ you can then define a map from $F(p) \rightarrow B(p) = \{0,1\}$ for any posets $p$ as the map which send any element to $1$ if it is a maximal element and $0$ otherwise. It is not functorial with respect to arbitrary morphism but is functorial with respect to isomorphisms.

2) I think there is actually reasonable hopes to be able to give a formal statement and a prof of the isomorphisms part of the thesis: one can imagine purely categorical (and somehow tautological) argument for that of course, or just the philosophical stand that "if a construction does not depends on any choice it cannot distinguishes isomorphic structures", even better I like to take "functorial with respect to isomorphism" as the definition of "canonical".

But what I had in mind here is the Univalence axiom and the developement of category theory with homotopy type theory as it is developed in the Hott book, which I think goes a lot further along those ideas:

To sum things up, in this formalism every category is 'forced'* to satisfied a version of the univalence axiom (for any two object of the category the type of isomorphism between them is equal to the type of equality between two such object). For such categories one has the functoriality along isomorphism of any possible construction (because it boils down to functoriality along equality which is tautological...). So in some sense one can say that any construction that is natural enough to be performed within a version of type theory consistant with univalence should satisfies this Eilenberg-MacLane thesis with respect to isomorphism.

Of course it is not currently well understood to what extent one can develop ordinary mathematics in a way compatible to univalence but it is hoped that this is possible, and that would be in my opinion one of the best possible answer to this question.

*: by 'forced' I mean that they only call categories those which satisfies this univalence axiom. Classical construction on categories generally preserve this property and most usual categories satisfies it. Moreover any category can be replaced by an equivalent categories satisfying this axioms by looking at the essential image of its Yoneda embeddings.

$\endgroup$
3
$\begingroup$

The following shows that (A) is in some sense trivially true. Suppose $\mathbb{C}$ and $\mathbb{D}$ are categories and that $(\alpha_X : A_X \to B_X)_{X \in \mathbb{C}}$ is a family of morphisms in $\mathbb{D}$. I hope you would agree that this situation is even more general than the one you describe (since after all one can take $\mathbb{C}$ to be set considered as a category). If $\mathbb{S}$ is the subcategory of $\mathbb{C}$ whose objects are the same as $\mathbb{C}$ and whose morphisms are only identity morphisms, then there are two functors $F, G : \mathbb{S} \to \mathbb{D}$ and a natural transformation such that $F(X) = A_X$, $G(X)=B_X$ and $\theta_X = \alpha_X$.

On the other hand the following is sort of a "counter example" to (A): Let $\mathbb{C}$ be the category of groups to each group $G$ we can associate two groups $G/Z(G)$ and $\text{Inn}(G)$ the quotient of $G$ by its center and the group of inner automorphisms, respectively. It is well-known that these two groups are isomorphic. Both these assigments seem to be natural however there doesn't seem to be any natural way of making them into functors $\mathbb{C}$ to $\mathbb{C}$. In particular the natural way one might try to make $G/Z(G)$ into a functor would be so that the canonical morphism $G\to G/Z(G)$ is a natural transformation. This is impossible since it would imply that the center can be made into a functor (see center is not a functor). If we restrict the domain category to the category of groups and surjective group homorphisms, then this passage works. Let us consider now the other assignment (i.e. $G$ maps to $\text{Inn}(G)$). Suppose that $f:G\to H$ is a group homorphism and $\theta : G\to G$ is an inner automorphism (i.e. there exists $g$ in $G$ such that for all $x$ in $G$, $\theta(x)=gxg^{-1}$). One might be tempted to try and define $\text{Inn}(f)(\theta)$ to be the inner automorphism defined by $\text{Inn}(f)(\theta)(y) = f(g)yf(g)^{-1}$. However this does not always determine a group homorphism (i.e. is not always "well defined") unless $f$ is surjective.

I hope that from the above you see that your question is perhaps more about when it is that some construction determines a functor in the expected way. This seems to be a difficult question.

$\endgroup$
  • 2
    $\begingroup$ The two construction are functorial on isomorphisms and the isomorphism between then is a natural transformation in this sense. But of course this kind of general principle only apply to isomorphism... $\endgroup$ – Simon Henry Oct 8 '15 at 8:47
  • $\begingroup$ @SimonHenry nice observation which leads to another tautological answer to the original question, this time positive. Going a little bit further, if we remove non-identity morphisms from a given category, any construction becomes natural. $\endgroup$ – Fernando Muro Oct 8 '15 at 9:06
  • $\begingroup$ I would like to support @user80028's view that the good question is about trying to understand what kind of construction is functorial. There is a clear example with 2-category theory: if C is a category, an internal category to C is just a left exact functor from the sketch of an (internal) category to C. Now, an internal functor between these categories is just a natural transformation between the previous functors. $\endgroup$ – sure Oct 8 '15 at 10:23
  • $\begingroup$ Yet, the internal natural transformations are not natural (as far as I know, even if you try to code them as modifications between 2-cats). So while the category of internal categories in C forms a 2-category, it seems that there is no functorial way to see them as a representation of a syntactic 2-category. Thus, the isomorphism of internal functors is not functorial, and therefore not natural. $\endgroup$ – sure Oct 8 '15 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.