How to find the Universal Category $\mathbf A$

Question

We say that a category $\mathbf A$ is fully embeddable into $\mathbf B$ if there exists a full embedding $\mathbf A\rightarrow \mathbf B$.

Then we know that each category of the form $\mathbf A\mathbf l\mathbf g(\Omega)$ is fully embeddable into each of the following constructs:

$1)$ $ \mathbf S \mathbf g\mathbf r$,

$2)$ $ \mathbf R \mathbf e\mathbf l$,

$3)$ $ \mathbf A \mathbf l \mathbf g(1,1)$, i.e., the construct of unary algebras on two operations.

But does there exist a category $\mathbf A$ such that every category (not quasicategories) can be fully embedded into $\mathbf A$?

Answer 1

Here is a construction of a "universally-embedding locally small category", assuming we are in a context (such as NBG) with the axiom of choice and where all proper classes have the same size (hence can be well-ordered with order-type $\mathrm{Ord}$, the proper class of (small) ordinals). In a universe-based approach to size, R. Street has used the term "moderate" for a category whose size is no larger than that of the universe; thus this can be interpreted in such a context as a universally-embedding locally small moderate category.

Define a transfinite sequence of small categories $W : \mathrm{Ord} \to \mathrm{Cat}$ by transfinite induction as follows. At limit steps, take colimits (including $W_0 = \emptyset$). At a successor step, suppose $n$ is an ordinal and $W_n$ is defined, and let $S_n$ be a set of representatives of isomorphism classes of spans $B \leftarrow A \to W_n$, where $A\to W_n$ is a full subcategory inclusion, $A\to B$ is a fully faithful inclusion that misses exactly one object, and the objects and arrows of $B$ have cardinality $<\aleph_n$. The cardinality restriction ensures that $S_n$ is indeed a set rather than a proper class. Now let $W_{n+1}$ be the pushout in $\mathrm{Cat}$:

$$ \begin{array}{ccc} \coprod_{s\in S_n} A_s & \to & \coprod_{s\in S_n } B_s \\ \downarrow && \downarrow \\ W_n & \to & W_{n+1} \end{array} $$

I claim that $W_n \to W_{n+1}$ is fully faithful, as are each of the functors $B_s \to W_{n+1}$. This follows by observing that $W_{n+1}$ can equivalently be constructed as a small transfinite composite of pushouts, if we well-order $S_n$:

$$\begin{array}{ccccccccccccccc} & & A_{s_0} & \to & B_{s_0} &&&& A_{s_1} & \to & B_{s_1} \\ & \swarrow &&&& \searrow && \swarrow &&&& \searrow\\ W_n &&& \longrightarrow &&& W_{n,1} &&& \longrightarrow &&& W_{n,2} &\to & \dots \end{array}$$

and the fact that fully faithful inclusions are closed under pushouts and transfinite composites.

Now let $W_\infty$ be the transfinite composite of the sequence $W : \mathrm{Ord} \to \mathrm{Cat}$. Since this is a large colimit, $W_\infty$ is a large category. But since it is a transfinite composite of fully faithful inclusions of small categories, $W_\infty$ is locally small, and moreover each inclusion $W_n \to W_\infty$ is fully faithful.

I claim that $W_\infty$ is a universally-embedding locally small category. Suppose $C$ is a locally small category. Well-order its objects as $\{c_n\}_{n\in \mathrm{Ord}}$ (here is where we use the fact that all proper classes have the same size), and let $C_n$ be the (small!) full subcategory of $C$ on the objects $\{c_k\}_{k<n}$. Then $C$ is the transfinite composite of the $C_n$'s, so by transfinite induction it suffices to show that any full embedding of $C_n$ into $W_\infty$ can be extended to $C_{n+1}$.

Since $C_n$ is small, there exists an ordinal $m$ such that the embedding $C_n \to W_\infty$ factors through $W_m$. Moreover, by enlarging $m$ if necessary we may assume that $C_{n+1}$ has cardinality $<\aleph_m$. Therefore, the span $C_{n+1}\leftarrow C_n \to W_m$ is isomorphic to some span $B \leftarrow A \to W_m$ in $S_m$, and therefore the composite $C_n \to W_{m} \to W_{m+1}$ extends to a full embedding of $C_{n+1}$ (the embedding $B\to W_{n+1}$ arising from the definition of the latter as a pushout). This completes the proof.

Of course, this construction is rather tautological and not very interesting, at least not compared to the more contentful embedding theorems about algebraic categories mentioned in the question. However, it does show that such a category exists.

Answer 2

It depends on precisely how you are choosing to deal with size distinctions in the definition of category. For universe-based approaches, the answer is “no, there is universal category”. For the class-/set-based approach, I don’t know what the answer is.

1. If you are taking a universes-based approach, i.e. fixing some universe (e.g. a Grothendieck universe $U$ or an inaccessible cardinal $\alpha$) and calling sets in this universe “small”, and defining a category to have an arbitrary set of objects but small hom-sets, then no, there is no universal category. A “universal category” would have to contain an embedded copy of every ordinal; that would force an injection from every set into its set of objects. But that’s impossible, if its objects are to form a set, since for any set $X$, its power-set $\mathcal{P(X)}$ doesn’t embed into $X$.

2. If you are taking a universes-based approach as above and taking category to mean small category, then again no, there is no universal category, essentially by the same argument. It would have to contain an embedded copy of every small ordinal, hence an injection from every small set, so since small sets are closed under taking power-sets, its objects can’t form a small set.

3. If you are taking the approach that a category may have a proper class of objects, and that only the individual hom-sets are required to be sets, then I’m not sure whether there can exist a universal category.