7
$\begingroup$

In a nutshell, the question is: is it true that any explicit (not involving axiom of choice) pointwise transformation between sufficiently complicated functors is natural almost everywhere?


Let $C$ be a sufficiently big category. It should be big enough that it would be impossible to explicitly describe all its objects and morphisms. For concreteness we assume $C=Set$, but it could also be any topos over $Set$ or algebraic category over $Set$ or even something more general. Note that in this case for any cardinality $\aleph$ there is a possibly large class of objects with this cardinality, even if $\aleph$ is finite. Even if $\aleph = 1$ there is a class of such sets, since for any $x:Set$ we have $\{x\} : Set$. Let $F,G: C\to Set$ be two functors, which we could even assume representable.

By a pointwise transformation I mean a function $x:C \mapsto \mu_x : (Fx \to Gx)$. It is natural if it satisfies the usual identities and unnatural if some identities fail. The folk lore is that defining any transformation between so complicated functors is hard enough that we can't accidentally write out an unnatural one, i.e. if you manage to define some transformation then it should be natural. This obviously fails if $C$ is not complicated enough. For example, if $C$ would have a finite set of objects, then we could just explicitly pick $\mu_x$ without regard to morphisms. Similarly, if $Ob \ C$ is countable, then some induction will usually define unnatural transformation.

If we believe in the axiom of choice for classes then unnatural transformations are easy to define: apply choice to the epimorphism $\left( \coprod_x (Fx \to Gx)\right) \to Ob \ C$. However, such transformations are generally useless, since there extremely little we can say about them. I am interested in explicitly defined transformations. The simplest way is just not to assume choice, the more preferable one is to use some sort of type theory (e.g. Martin-Löf one), which doesn't allow arbitrary choice for all types. Almost all examples of unnatural transformations that I can think of use choice in one way or another.

  • Any category is equivalent to its skeleton, which could have a countable set of objects, however such equivalence requires choice, thus we cannot hope to push $F,G: C\to Set$ to $\hat F, \hat G: \mathrm{sk}\ C \to Set$, choose $\hat F \to \hat G$ unnaturally by induction and lift it to $C$.
  • A particular case of the previous exaample is $C=FinSet$.There is a function $C\to \mathbb{N}$ mapping $x \mapsto \# x$. We could give an "inverse" by mapping $n: \mathbb N \to [n]: FinSet$, where $[n]$ is the standard set with $n$ elements, but this doesn't define an equivalence in the absence of choice, thus we can't define $\mu_x$ unnaturally.
  • Essentially all examples from this question arise either for finite-object $C$ or for some arbitrary choice of equivalence with skeleton. Consider the following examples:

  • Eric Wofsey gives the following example: consider the categories of $k$-vector spaces $Vect$ and $k$-affine spaces $Aff$, where an affine space is a $V$-torsor for $V: Vect$: a pair $(V:Vect, X: Set)$ with free and transitive $V$-action on $X$. We have $U: Aff \to Vect$ sending each affine space to its structure group $V$ and $F: Vect \to Aff$ which maps $V: Vect$ to $V$ considered as $V$-torsor. Both of these functors are defined naturally and explicitly. We have a natural isomorphism $UF \simeq 1_{Vect}$ and an unnatural isomorphism $UF \simeq 1_{Aff}$: while any $(V,X): Aff$ is isomorphic to $(V,V):Aff$, such an isomorphism requires a choice of point $x_0 : X$. The only way to choose a point simultaneously in all $A: Aff$ seems to involve the axiom of choice for classes.

  • The same problem exists with unnaturalness of universal coefficient splitting: the splitting of $$0 \to \mathrm{Ext}^1_R ( H_{i-1}(X,G), G) \to H^i (X,G) \to \mathrm{Hom}_R ( H_i (X,G), G) \to 0$$ even if $H_i$ is free requires both a choice of basis in $H_i$ and a choice of lifting to $H^i$ for the dual basis.

One class of explicit examples that I can think of goes as follows: split $C$ into finitely many full subcategories $C_i$ (i.e. $Ob\ C = \coprod_i Ob\ C_i$), then choose a different natural transformation for each $C_i$. For example we could consider $F\equiv Set(A,\cdot), G\equiv Set(B,\cdot): Set \to Set$, choose $f: A\to B$, $g: A\to A$, split $Set$ into $C_1 := \{x:Set \vert x = [2] \}$ and $C_2 := \{x:Set \vert x \ne [2] \}$. Define $\mu\vert_{C_1} : F\vert_{C_1} \to G\vert_{C_1}$ as $Set(f,\cdot)$ and $\mu\vert_{C_2} : F\vert_{C_2} \to G\vert_{C_2}$ as $Set(fg,\cdot)$. Together they glue to unnatural $\mu: F \to G$.

The previous example could be generalized to a countable number of $C_i$ with $\mu\vert_{C_i} := Set( f \circ g^{i-1} , \cdot)$. Note that such $\mu$ is still natural almost everywhere. I am uncertain what "natural almost everywhere" could mean in full generality, but an ad-hoc definition could be: there is a set $B$ and a function $\pi: Ob\ C \to B$ such that isomorphic objects map to the same element, and the unnatural transformation $\mu$ is constructed as a coproduct of natural $\mu_i: F\vert_{C_i} \to G\vert_{C_i}$ for $i: B$, where $C_i$ are full subcategories with $Ob\ C_i := \{x: C \vert \pi(x)=i \}$.

I feel as if any definable pointwise transformation would be natural almost everywhere, but I can't see how could one even hope to prove it. In particular, unnatural transformations should be defined by explicit case analysis, thus if we give a definition uniformly (in some sense) over $x: C$ then it will automatically be natural. Can this intuition be made explicit?

Thus I seek either for an unnatural transformation not involving choice and not natural almost everywhere or for some proof (or way to proof) that it does not exist.

$\endgroup$
  • 5
    $\begingroup$ I have trouble seeing how this is a well-posed question. You could always artificially avoid using the axiom of choice by building the choices into the structure of objects but making the morphisms ignore that extra structure. To be more specific, you could modify the example with affine spaces by taking $\mathsf{Aff}'$ to be category whose objects are affine spaces with a basepoint and morphisms are just affine (not necessarily based) maps. Then the definition of an unnatural transformation doesn't require AC. $\endgroup$ – Karol Szumiło Apr 10 '15 at 15:51
  • 5
    $\begingroup$ You seem in your question to presume that uses of AC are inherently non-definable. But this is not a correct intuition. In fact, the way that we first came to know that AC is consistent is through Godel's constructible universe $L$, where there is a definable well-ordering of the universe. Thus, one can use AC in this universe and still have a definable function. Worse, there are other models of ZFC and even GBC in which every set and class is definable without parameters. So using AC in such a model cannot produce a non-definable class. My view is that the question has a problem at its core. $\endgroup$ – Joel David Hamkins Apr 10 '15 at 16:45
  • 4
    $\begingroup$ My point was that you will not be able to prove that definable maps are natural, because there are models of set theory in which ALL maps (of any kind, from any set or class to another), including those coming from AC, are definable. $\endgroup$ – Joel David Hamkins Apr 10 '15 at 16:58
  • 4
    $\begingroup$ I figure that my example is "cheated" and not what you want, but my point is that you haven't specified how exactly you want to prohibit an example like that. In particular, I don't understand your objection that "the categories are different". The way you posed your question I am free to choose the categories how I want. And I chose $\mathsf{Aff}'$ rather than $\mathsf{Aff}$. $\endgroup$ – Karol Szumiło Apr 10 '15 at 18:10
  • 5
    $\begingroup$ The most natural example (I can think of) of a category where morphisms ignore much of the structure would be the category of metric spaces and continuous maps. Without being aware of the concept of topological spaces we wouldn't be able to recognize how much structure is ignored here. How could we ever be confident that something like that doesn't happen in other examples? $\endgroup$ – Karol Szumiło Apr 11 '15 at 11:10
9
$\begingroup$

Maybe Shelah, Hodges, Naturality and Definability II (http://arxiv.org/abs/math/0102060) is relevant:

In two papers we noted that in common practice many algebraic constructions are defined only 'up to isomorphism' rather than explicitly. We mentioned some questions raised by this fact, and we gave some partial answers. The present paper provides much fuller answers, though some questions remain open. Our main result says that there is a transitive model of Zermelo-Fraenkel set theory with choice (ZFC) in which every fully definable construction is `weakly natural' (a weakening of the notion of a natural transformation). A corollary is that there are models of ZFC in which some well-known constructions, such as algebraic closure of fields, are not explicitly definable. We also show that there is no model of ZFC in which the explicitly definable constructions are precisely the natural ones.

(Make this into a comment)

$\endgroup$
  • 1
    $\begingroup$ Actually, it looks very relevant. No need to hide it in the comment tread. $\endgroup$ – Anton Fetisov Apr 11 '15 at 2:16
  • $\begingroup$ There is also Shelah, Hodges, Naturality and Definability I by same authors which is clearer I think (but maybe does less). Could you expand a bit on how it is relevant? $\endgroup$ – user70198 Apr 11 '15 at 23:13

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.