Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I am working with "usual" category theory, maybe over ZFC, and I have a functor $F : Set \to Set$. I'd like to apply Yoneda lemma to $F$, i.e. obtain:

$$ [Set, Set](h_A, F) \cong F A $$

However, most of texts assume that the domain of $F$ should be a small category in order to apply it. I know this has to do with the size of $[Set, Set]$ and the existence of $h_A$. How could I fix my foundations so I can use Yoneda lemma like this? Or I'll never be able to do such thing?

share|improve this question
    
You don't give any indication of which area of mathematics this is, or in particular the properties of the functor $F$. If it comes from finitary algebra, so it preserves filtered colimits, then it suffices to consider finite sets as the domain, in which case the ordinary Yoneda Lemma is enough. –  Paul Taylor Nov 1 '13 at 15:20
1  
You have some flexibility here. It is likely that if you clarify what foundation you have or want for the functor $F$ in the first place, that will yield a suitable form of Yoneda. –  Colin McLarty Nov 1 '13 at 15:46
    
I didn't think of any property for $F$. I thought of a general answer, for any $F$, like "think there's a universe such that $Set$ is part of it and ..." or something. –  wrongfound Nov 1 '13 at 16:01
1  
I recently wrote an answer to a related question about the category of endofunctors of a model category. Once again there are set-theory issues because hom-sets are not small. The solution I proposed involved passing to a higher universe. Maybe this will be of interest: mathoverflow.net/questions/106924/… –  David White Nov 1 '13 at 16:11
    
The trick is to use as many Grothendieck universes as you need : $\mathcal{U_1}\subset \mathcal{U_2}\subset \dots$ and to see where your objects are in this hierarchy of universes. If the final object you are interested in belongs to $\mathcal{U}_1$, you win because it is an ordinary set. –  Philippe Gaucher Nov 3 '13 at 8:53
add comment

3 Answers 3

up vote 6 down vote accepted

Zhen Lin states one direction of the Yoneda Lemma: given $x\in F A$, the natural transformation $\theta_x:H_A\to F$ on $f:A\to B$ is $\theta(f)=F f\cdot x$. The other direction is that every $\theta:H_A\to F$ is of this form, where $x=\theta(\mathsf{id}_A)$. I leave it as an exercise to show that $\theta_x$ is natural and that this correspondence is bijective.

What I have just stated is the natural mathematical argument for the central idea of the Yoneda Lemma, albeit without the calculations required for the proofs. None of it has anything to do with Set Theory, whether that be ZFC, NBG or even NF.

This argument makes sense in a world in which objects and morphisms are things of a different sort from one another. Functors and natural transformations, on the other hand, are schemes or recipes that transform objects and morphisms into objects and morphisms. Functors and natural transformations are not themselves things.

We are quite used to this many-sorted language in algebra or first order logic. Even when the algebra itself has only one sort (if you don't know what I mean by that, I mean exactly the situation that you know), elements of the algebra, homomorphisms, predicates, ideals etc. belong to different sorts of the language in which we discuss them.

It was the innovation of Set Theory to reify schemes, i.e. turn them into things. In its unrestricted form, this innovation led to the famous antinomies or paradoxes, such as Russell's. The outcome of this was to develop restricted reification, such as Zermelo Set Theory.

Unfortunately, the mathematical community became addicted to Cantor's "paradise". So, even in disciplines such as Category Theory where we should have known better, we continue to find attempts at unrestricted reification such as Grothendieck Universes.

The disciplined alternative is the type-theoretic style, in which we nominate certain forms of reification, for example that of functions ($\lambda$-abstraction), and stick to just those (in the context of a particular discourse).

Now to reply to Michal Przybylek. I have just said and he agrees that "If people think that they need any kind of Set Theory to speak about Yoneda lemma, then they are wrong." However, far from being "philosophical" or "waving my hands", I have explained quite precisely what is the methodological set-up ("foundations" if you wish) behind the argument.

At least, I discussed the ordinary form of the argument. Of course, as mathematicians have always done extremely profitably with pre-existing arguments, one may re-interpret it in more exotic settings. Enriched, internal and locally cartesian closed categories are examples of such settings. Moreover they are also examples of desciplined restricted reification operations.

share|improve this answer
    
Paul, I don't understand your answer --- it's perhaps too philosophical for me. If people think that they need any kind of Set Theory to speak about Yoneda lemma, then they are wrong. But if you think that you can gain anything in mathematics by waving hands and being imprecise, then you are wrong too. In the context of enriched categories, Yoneda lemma works when you can define an internal object of natural transformations (and it is almost tautological then); otherwise, you have to state the Yoneda lemma on the sections of objects, which is almost never what we actually need. (cont) –  Michal R. Przybylek Nov 2 '13 at 8:42
    
Similarly, Yoneda lemma doesn't work in the context of internal categories, unless your ambient category is locally cartesian closed. –  Michal R. Przybylek Nov 2 '13 at 8:42
    
Paul, I still don't understand you. It seems to me that you are doing exactly the opposite to what you want to achieve. Let me rename the usual set-theoretic membership relation $\in$ to $e$. In your "Yoneda lemma" you may say something like (perhaps, you would prefer to express the below without using meta-set-theoretic notion): $$ \{x \colon x {\;e\;} FA\} \approx \{\theta \colon \textit{$\theta$ is a nat. tr. $h_A \rightarrow F$}\}$$ (cont) –  Michal R. Przybylek Nov 2 '13 at 11:50
    
This is the weak Yoneda lemma, which is not the same as Yoneda lemma unless you work in a kind of a Grothendieck universe (or a universe that says how internal $e$ interacts with external $\in$). That's what I called "comparing apples with apes". –  Michal R. Przybylek Nov 2 '13 at 11:51
    
The core of the question was whether you need set theory for the Yoneda lemma. I explained why you don't. Yes, there are lots of powerful corollaries (hence the name "lemma") and re-interpretations in different categorical and set-theoretic formulations, but I think they distract attention from the core point. –  Paul Taylor Nov 2 '13 at 12:31
add comment

You could use the usual device of assuming a Grothendieck universe: Mac Lane does this in [Categories for the working mathematician]. But actually you don't need that for the Yoneda lemma – you could just rephrase things so that there is no mention of the "illegal" category $[\mathbf{Set}, \mathbf{Set}]$. For instance:

For any functor $F : \mathbf{Set} \to \mathbf{Set}$, any set $A$, and any element $x$ of $F(A)$, there is a unique natural transformation $\theta_x : \mathbf{Set}(A, -) \Rightarrow F$ such that $(\theta_x)_A (\mathrm{id}_A) = x$.

Of course, logicians will point out that the above is really a "metatheorem" because functors $\mathbf{Set} \to \mathbf{Set}$ are not elements of the universe of discourse, but that's not really important. (Since you mention it, the "existence" of $\mathbf{Set}(A, -)$ is never a problem: it may not be an element of the universe, but what it does is perfectly well-defined.) One can avoid this particular issue of metatheorem vs theorem by switching from ZFC to NBG, but if you prefer to avoid having to think about fine distinctions like that at all, you should just bite the bullet and use a Grothendieck universe. (My preference nowadays is to assume a Grothendieck universe inside Mac Lane set theory.)

share|improve this answer
1  
When I saw the phrase Grothendieck Universe I was going to say "No, no, no, Das is nicht Mathematik, das ist Theologie" but then I saw that you had translated the gratuitous Set Theory out of it and stated the natural Category Theory instead. Either way it's still Abstract Nonsense: the question remains as to what sort of functors "wrongfound" had in mind, and the answer to that will lead to whatever real mathematics is needed. –  Paul Taylor Nov 1 '13 at 17:38
add comment

The problem is not whether you can use Yoneda lemma or not, but to associate a precise meaning to your sentences. As a rule of thumb, Yoneda lemma works whenever you can formally say what it actually means.

I do not agree with Zhen's answer which says that it is not really important that the objects are not inside the universe --- the truth is exactly the opposite --- it is the only issue here. In the usual ZFC formalization, objects $FA$ are real sets, whereas objects $\mathit{nat}(h_A, F)$ are not. Of course you can "lift" $FA$ to the meta-universe, but then you will compare apples with apes.

share|improve this answer
    
Of course, you can always just work in NF and the existence of the functors and natural transformations as objects of the universe is generally easy. Of course, then you deal with comparing apples to (smaller) singletons of apples... –  Malice Vidrine Nov 2 '13 at 0:18
2  
@MaliceVidrine, it is not a problem to formalize the above. The problem is that you have to formalize it somehow. –  Michal R. Przybylek Nov 2 '13 at 8:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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