Do hom-sets really live in the category Set? In familiar introductory books on category theory, one of the first examples of a category given is Set. And what category is that? 
Typically no explanation is given at this stage. But of course which category we are dealing with depends on our set theory. For an NF-iste, the category of NFsets has very different properties from the usual category Set (for a start NFsets is not cartesian closed). But fair enough, in an intro book you aren't going to mention that in Ch. 1! The charitable reading is that authors are relying on their readers to think of Set as comprising the sets they already know and love from their standard intro set-theory course. Which are pure sets of the cumulative hierarchy -- pure in that there are no urlements, no memberless entities in the universe of sets other than the empty sets.
OK, then: in the absence of special explicit signals to the contrary, it seems we might reasonably take Set to be a category of pure sets of the usual hierarchy. What else?
But then what are we to make of e.g. the usual presentation of the Yoneda embedding as $\mathcal{Y}\colon \mathscr{C} \to [\mathscr{C}^{op}, \mathbf{Set}]$. Putting it this way assumes that hom-collections $\mathscr{C}(A, B)$ for $A, B \in \mathscr{C}$ actually live in $\mathbf{Set}$. And since such a hom-collection is a set of $\mathscr{C}$-arrows, that assumes that the $\mathscr{C}$-arrows must live in the world of pure sets too. [We may want the relevant hom-collections to be set-sized in the Yoneda embedding case -- but being no bigger than set-sized is one thing, living in the universe of pure sets is something else!]
But do we really want to assume that arrows are always pure sets? Isn't category theory supposed to be a story about how different bits of the mathematical universe hang together which doesn't presuppose some over-arching, all-in, set-theoretic reductionism, and so in particular doesn't presuppose that all morphisms are pure sets??
Now, the foundational sections you often early in category theory often worry away about questions of size (sets vs classes etc.). But the present worry is orthogonal to all that, and is in a way more basic. If we think of the denizens of different bits of the mathematical universe (different categories) as sui generis, so arrows in e.g. a poset category or the free monoid on one generator are different kinds of beasts to pure sets, then a corresponding collection of arrows (hom-set) surely can't be thought of as belonging to $\mathbf{Set}$ (as opposed, perhaps, to being fully faithfully mappable into that world). 
I guess there must be good discussions of this sort of thing in the literature somewhere, and I'm no doubt showing my ignorance by asking where! But, please, any pointers would be most gratefully received. 
(Cross-post at MathOverflow: https://mathoverflow.net/questions/194551/do-hom-sets-really-live-in-the-category-set) 
 A: The general definition of a category has nothing to do with sets, let alone classes. A category is just a bunch of objects $A,B,C,\dotsc$ and a bunch of morphisms $f : A \to B$, $g : B \to C,\,\dotsc$ equipped with some operations and some laws. It does not matter what "bunch" aka "collection" means, but only how to manipulate these things. The axioms can be formalized within first-order logic (similar to, and independent from, set theory):
Consider the first-order language $\{M,O,c,s,t,i\}$, where $M,O$ are two sorts, $c$ is a ternary predicate symbol on $M$, $s,t : M \to O$ are two function symbols, and $i : O \to M$ is a function symbol. Add the following axioms:


*

*$\forall_M f,g( s(f)=t(g) \rightarrow \exists_M h ! (c(f,g,h)))$

*$\forall_M f,g,h (c(f,g,h) \rightarrow (s(h)=s(g) \wedge t(h)=t(f) \wedge s(f)=t(g)))$

*$\forall_M f,g,h,u,v,w (c(f,g,u) \wedge c(u,h,v) \wedge c(g,h,w) \rightarrow c(f,w,v))$

*$\forall_O A (s(i(A))=A \wedge t(i(A))=A)$

*$\forall_M f (c(f,i(s(f)),f) \wedge c(i(t(f)),f,f))$


Exercise. Translate these axioms into your "usual" language.
This theory is called $\mathsf{ETAC}$, the elementary theory of an abstract category. Models of $\mathsf{ETAC}$ are, by definition, categories (or small categories, but this distinction is not relevant at this point). There are various extensions of this theory with which you can speak of functors, natural transformations, colimits and alike. All this is completely independent from sets.
As soon as we want to talk about Hom-sets, for example in the Yoneda embedding, what we actually need first is the concept of an enriched category, which can be formalized in first-order logic (including the underlying definition of a monoidal category). Lawvere's theory $\mathsf{ETCS}$, the elementary theory of the category of sets, is a first-order axiomatization of the category of sets, so we should add this theory whenever needed. In order to obtain equiconsistency with $\mathsf{ZFC}$, one has to add the replacement axiom $R$, but it seems that large parts of mathematics can work without it. The corresponding sort of category will be denoted by $\mathsf{Set}$. Then, the notion of a locally small category is that of a $\mathsf{Set}$-enriched category. When defined that way, this is not a category with an additional property, but rather a category with an additional structure! To each pair of objects $A,B$ we want to have an object $\hom(A,B)$ of $\mathsf{Set}$, among other things, such that certain axioms hold. Meanwhile I think that the Yoneda embedding is actually more natural for arbitrary enriched categories. We don't need $\mathsf{Set}$-enriched categories.
