The n-Category Café

Orthogonality between arrows

Definition. An object $B$ in a category $\mathbf{A}$ is said to be orthogonal to an arrow $k\colon A\to X$ (we say $k\perp B$) if the hom-functor $\mathbf{A}(-,B)$ sends $k$ to a bijection $\mathbf{A}(X,B)\to \mathbf{A}(A,B)$ between sets.

If $\mathbf{A}$ has a terminal object, then $k\perp B$ if and only if the terminal arrow $B\to 1$ has the so-called (unique) right lifting property against $k$: this means that for any choice of $f$ in the diagram $$\begin{array}{ccc} A &\stackrel{f}{\longrightarrow}& B \\ {}^k \downarrow && \downarrow \\ X & \longrightarrow & 1 \end{array}$$ there exists a unique arrow $a\colon X\to B$ making the upper triangle commute. Obviously, there is a dual notion of left lifting property.

Statement of the problem: the CFP and the OSP.

Now, a classical issue in elementary Category Theory is the so-called “orthogonal subcategory problem”:

Orthogonal Subcategory Problem (OSP). Given a class $\mathcal{H}$ of arrows in a category $\mathbf{A}$, when is the full subcategory ${\mathcal{H}}^\perp$ of all objects orthogonal to $\mathcal{H}$ a reflective subcategory (i.e., when there exists a left adjoint to the inclusion ${\mathcal{H}}^\perp\hookrightarrow \mathbf{A}$)? $\blacksquare$

There are lots of “protoypical” examples of the OSP in Algebra and Geometry: think for example to the case of sheaves of sets (on a given Grothendieck site) as a reflective subcategory among presheaves: the sheaf condition can be easily stated in terms of an orthogonality request: a presheaf $F$ on a site $(\mathbf{C},J)$ is a $J$-sheaf if and only if $$i_C\perp F \quad \forall C\in\mathbf{C}$$ for every covering sieve $i_C\colon S\to y_{\mathbf{C}}(C)=\mathbf{C}(-,C)$.

In fact this is not a case, since following a general tenet “(at least some) localizations are determined by an orthogonality class” (see for example the definition of $\mathcal{S}$-local object and the $n$Lab page about the OSP).

Freyd and Kelly were the first to point out that a solution for the OSP turns out to solve another fundamental question, which falls under the name of “continuous functor problem”:

Continuous Functor Problem (CFP). Given a category $\mathbf{C}$ and a class of diagrams (say $\Gamma$) in it, when is the category of all functors $\mathbf{C}\to \mathbf{D}$ which preserve limits of all $\Gamma$-shaped diagrams reflective in the category of functors $\mathbf{C}\to \mathbf{D}$? $\blacksquare$

(Important) Remark. Before going on, we must spend a word on the notion of continuity: Freyd and Kelly published an erratum shortly after the paper, to correct the “stupid mistake of supposing that the limit of a constant diagram is the constant itself”; counterexamples to this statement abound, and in fact it can be easily shown that the limit of the constant functor $\Delta(C)\colon \mathbf{J}\to\mathbf{C}$ is (whenever this copower exists) precisely $C^{\pi_0(\mathbf{J})}$, where $\pi_0(\mathbf{J})$ is the set of connected components of the category $\mathbf{J}$.

Once this is fixed, notice that the CFP arises in an extremely elementary way: for example,

1. An additive functor $F$ between abelian categories is left exact if and only if it commutes with finite limits, and
2. The above sheaf condition can be easily restated in the good old familiar continuity request on coverings of objects $C\in\mathbf{C}$.

This should give you evidence that the two problems are not unrelated:

Proposition. Given a class of diagrams $\Gamma$ in a small complete category $\mathbf{C}$, we get a family of natural transformations $$\mathcal{G}(\Gamma)=\Big\{ m_\gamma \colon \colim \mathbf{C}(\gamma,-) \to \mathbf{C}\big( \lim\; \gamma,- \big) \Big\}_{\gamma\in\Gamma}$$ and a functor $F\colon \mathbf{C}\to Set$ is $\Gamma$-continuous if and only if it is orthogonal to each arrow in $\mathcal{G}(\Gamma)$.

(This result is not in its full generality: see [FK], Prop. 1.3.1.)

Proof. The following diagram commutes, $$\begin{array}{ccc} Nat (colim\; \mathbf{C}(\gamma,-),F) &\leftarrow & Nat (\mathbf{C}(lim \;\gamma,-),F)\\ \wr\!| && \wr\!| \\ lim\; Nat (\mathbf{C}(\gamma,-),F) && F(lim\; \gamma)\\ \wr| && \downarrow \\ lim\; F\gamma &=& lim\; F\gamma \end{array}$$ and one of the two arrows is an isomorphism if and only if the other is. $\blacksquare$

OSP $\Rightarrow$ CFP: Strategy of the proof.

The strategy adopted by Freyd and Kelly to solve the OSP, is to find sufficient conditions on $\mathcal{H}$ so that Freyd’s Adjoint Functor Theorem applies to the inclusion $\mathcal{H}^\perp\hookrightarrow \mathbf{A}$ (in particular, since it can be shown that $\mathcal{H}^\perp$ is always complete, this boils down to find a solution set for $\mathcal{H}^\perp$ to apply Freyd Adjoint Functor Theorem).

These conditions are of 1+3 different types:

1. Cocompleteness;
2. The presence of a proper factorization system;
3. The presence of a generator;
4. A (global) boundedness condition (or equivalently, on the generator in the previous point).

Factorization systems

Notation. We denote $llp(\mathcal{H})$ (resp, $rlp(\mathcal{H})$) the (possibly large) class of all arrows left (resp, right) orthogonal to each arrow of the class $\mathcal{H}$.

In the previous notation, $k\perp B \iff k \in llp(B \to 1) \iff (B\to 1) \in rlp(k)$.

Definition. A prefactorization system on a category $\mathbf{A}$ consists of two classes of arrows $\mathbb{F}=(\mathcal{E},\mathcal{M})$ such that $\mathcal{E} = llp(\mathcal{M})$ and $\mathcal{M} = rlp(\mathcal{E})$.

A prefactorization system $\mathbb{F}$ on $\mathbf{A}$ is said proper if $\mathcal{E}\subset Epi$ and $\mathcal{M}\subset Mono$.

A factorization system (OFS, or simply FS) on a category $\mathbf{A}$ corresponds to the modern notion of orthogonal factorization system: a (proper) factorization on the category $\mathbf{A}$ is precisely a (proper) prefactorization $\mathbb{F}=(\mathcal{E},\mathcal{M})$ such that each $f\colon X\to Y$ can be written as a composition $X\stackrel{e}{\to}W\stackrel{m}{\to}Y$ with $e\in \mathcal{E}, m\in\mathcal{M}$.

Examples. 0. Any category $\mathbf{C}$ has two trivial factorization systems, namely $( Mor_\mathbf{C} , Iso_\mathbf{C} )$ and $( Iso_\mathbf{C} , Mor_\mathbf{C} )$, where $Iso_\mathbf{C}$ denotes the class of all isomorphisms, and $Mor_\mathbf{C}$ the class of all arrows in $\mathbf{C}$; 1. The category $Set$ has a factorization system $\mathbb{F}=(Epi,Mono)$ where $Epi$ denotes the class of surjective maps, and $Mono$ the class of injective maps. More generally, the category of models of any algebraic theory (monoids, (abelian) groups, …) has a proper FS $(Epi^\ast, Mono)$, where $Epi^\ast$ is the class of extremal epimorphisms (which may or may not coincide with plain epimorphisms); and for abelian categories, (elementary) toposes…

Generators

Definition. If $\mathbf{A}$ is a category with a proper factorization system $\mathbb{F}$, we say that a family of objects $\{q_i\colon B_i\to C\}_{i\in I}$ lies in $\mathcal{E}$ if there exists a unique $t\colon C\to X$ solving (all at once) the lifting problems $$\begin{array}{ccc} B_i & \stackrel{f_i}{\longrightarrow} & X \\ {}^{q_i} \downarrow && \downarrow^m\\ C & \longrightarrow & Y \end{array}$$ (one for each $i\in I$). If $\mathbf{A}$ has sufficiently large coproducts, this condition is obviously equivalent to ask that the arrow $\left(\bar q\colon \amalg_{i\in I} B_i\to C\right)\in\mathcal{E}$.

Definition. A generator in a category with a proper factorization system $\mathbb{F}=(\mathcal{E}, \mathcal{M})$ consists of a small full subcategory $\mathbf{G}\subseteq\mathbf{A}$ such that for any $A\in\mathbf{A}$ the family $\{G\to A\}_{G\in\mathbf{G}}$ lies in $\mathcal{E}$ in the former sense.

Remark. Mild completeness assumptions on $\mathbf{A}$ entail that

1. A generator separates objects, i.e. if $f\neq g$ then there exists an object $G\in\mathbf{G}$ and an arrow $G\to A$ such that $f k\neq g k$.
2. A small dense subcategory of $\mathbf{A}$ is a generator;
3. Any finitely complete category with a generator is well-powered.

For extremal FSs (in which the left/right class coincides with that of extremal epi/mono) the converse of 1,2 is also true, so as to recover the notion of generator as a “separator for objects”.

Boundedness

Notation. In this section $\mathbf{A}$ admits all limits and colimits whenever needed

Definition(s). An ordered set $J$ is said to be $\sigma$-directed (for a regular cardinal $\sigma$) if every subset of $J$ with less than $\sigma$ elements has an upper bound in $J$. A $\sigma$-directed family $\{C_j\to B\}_{j\in J}$ of subobjects of $B\in\mathbf{A}$ consists of a functor $J\to Sub_\mathbf{A}(B)$ from a $\sigma$-directed set to the posetal class of subobjects of $B$. The colimit of such a functor, denoted $\bigcup_{j\in J} C_j$ is called the $\sigma$-directed union of the family.

With these conventions, we say that an object $A\in\mathbf{A}$ is bounded by a regular cardinal $\sigma$ (called the bound of $A$) if every arrow $A\to \bigcup_{j\in J} C_j$ to a $\sigma$-directed union factors through one of the $C_j$. The category $\mathbf{A}$ is bounded if each $A\in\mathbf{A}$ is bounded by a regular cardinal $\sigma_A$ (possibly depending on $A$).

Example. In $\mathbf{A}= Set$ a set of cardinality $\le \sigma$ is $\sigma$-bounded.

Remark. $\sigma$-boundedness is obviously linked to local $\sigma$-presentability: [PK]’s locally $\sigma$-presentable categories are precisely those categories $\mathbf{A}$ which

• admit arbitrary colimits;
• admit a generator $\mathbf{G}$ each of which object is $\sigma$-presentable.

Examples. Examples of such structures/properties on categories abound:

1. Any abelian, $AB(5)$, bicomplete and bi-well-powered category $\mathbf{A}$, is bounded;
2. Given a regular cardinal $\sigma$, locally $\sigma$-presentable categories are $\sigma$-bounded, and admit a generator with respect to the proper FS $(Epi^\ast, Mono)$: sets, small categories, presheaf toposes and Grothendieck abelian categories all fall under this example. Less obviously, the converse implications is false: exhibiting a $\sigma$-bounded category with a generator which is not locally $\sigma$-presentable requires to accept the inexistence of measurable cardinals (see [FK], Example 5.2.3).

Solution of the OSP

Theorem (OS theorem). If $\mathbf{A}$ is complete, cocomplete, bounded and co-well-powered with a proper FS $\mathbb{F}=(\mathcal{E},\mathcal{M})$, and $\mathcal{H}$ is a class of arrows whose elements are “almost all” in $\mathcal{E}$, i.e. $\mathcal{H}=\mathcal{S}\cup \overline{\mathcal{E}}$ (we call these classes quasi-small with respect to $\mathcal{E}$), where

• $\mathcal{S}$ is a set;
• $\overline{\mathcal{E}}$ is possibly large but contained in $\mathcal{E}$.

Then $\mathcal{H}^\perp$ is a reflective subcategory. $\blacksquare$

Proof. [FK] performs a clever transfinite induction to generate a solution set for any object $A\in\mathbf{A}$: if $k\colon M\to N$ is the typical arrow in $\mathcal{S}$, we define

• (zero step) $\S_{0, A} = Quot_{\mathbf{A}}(A)$;
• (successor step) $\S_{\alpha+1, A} = \bigcup_L Quot_{\mathbf{A}}(L)$, where $L\in \Big\{ C\amalg \coprod_{M\to C}N\mid C\in \S_\alpha,\; (M\to N)\in \mathcal{S} \Big\}$
• (limit step) $\S_{\lambda, A} = \bigcup_W Quot_{\mathbf{A}}(W)$, where $W\in \Big\{ \coprod_{\alpha\lt \lambda} C_\alpha\mid C_\alpha\in \S_\alpha \Big\}$.

This is where boundedness comes into play: if $\sigma$ is the cardinal bounding $A$, then the induction stops at $\sigma$: $\S_{\sigma, A}\cap \mathcal{H}^\perp$ is the desired solution set for $A\in\mathbf{A}$, namely every arrow $f\colon A\to B$ whose codomain lies in $\mathcal{H}^\perp$ factors through some $X\in \S_{\sigma, A}\cap \mathcal{H}^\perp$.

Solution of the CFP

The procedure we adopted to reduce the CFP to the OSP (building $\mathcal{ G}(\Gamma)$) doesn’t take care of any size issue: to repair this deficiency we exploit the following

Lemma. Let $\mathbf{A}$ be cocomplete, endowed with a proper factorization system $\mathbb{F}$ and a generator $\mathbf{G}$. For any class $\Theta$ of natural transformations in $Fun(\mathbf{C}, Set)$ we denote $$\begin{array}{rl} \mathcal{H} &= \Big\{ \beta\otimes A\mid \beta\in\Theta,\; A\in\mathbf{A} \Big\} \\ \mathcal{H}_1 &= \Big\{ \beta\otimes G\mid \beta\in\Theta,\; G\in\mathbf{G} \Big\} \end{array}$$ Then there exists a class $\mathcal{W}$ contained in $\mathcal{E}$ such that $\mathcal{H}^\perp = (\mathcal{H}_1\cup \mathcal{W})^\perp$.

The particular shape of $\mathcal{H}$ is due to the procedure used in [FK] to reduce the CFP to the OSP. The $\otimes$ operation is a copower, in the obvious sense: given $\beta\colon \mathbf{C}\to Set$, $\beta\otimes A\colon F\otimes A\to G\otimes A$, where $F\otimes A\colon C\mapsto F C\otimes A = \coprod_{c\in F C}A$.

The key point of this result is that the class $\mathcal{H}_1$ is small (obviously) whenever $\Theta$ is, so we can conclude applying the OS theorem:

Theorem (CF theorem). Let $\mathbf{C}$ be a small category, and $\mathbf{D}$ a bicomplete, bounded, co-wellpowered category with a generator and a proper factorization $\mathbb{F}=(\mathcal{E},\mathcal{M})$. Let $\Gamma$ be a class of cylinders whose elements are almost all cones (this means that the collection of diagrams which are not cones is a set). Then the subcategory of $\Gamma$-continuous functors is reflective in $Fun(\mathbf{C},\mathbf{D})$. $\blacksquare$

The rough idea behind this result is the following: $\mathcal{H}^\perp$ can be written as $(\mathcal{H}_1\cup\Omega)^\perp$, and $\mathcal{H}_1$ itself can be split as a union $\mathcal{H}_1^M \cup \mathcal{H}_1^{E}$, where the two sub-classes consist of the $\mathcal {M}$-arrows and the $\mathcal{E}$-arrows of the various $h\in\mathcal{H}$. The assumptions made on $\Gamma$ and the presence of a generator on $\mathbf{A}$ entail that $\mathcal{H}_1^M$ is a set, so we can conclude.

The state of the art.

1. [FK]’s solution of the OSP can be generalized: [AHS] show that $\mathcal{H}^\perp$ is reflective in a category $\mathbf{A}$ with a proper FS $\mathbb{F}=(\mathcal{E},\mathcal{M})$ whenever the class $\mathcal{H}$ is quasi-presentable, namely it can be written as a union $\mathcal{H}_0\cup \mathcal{H}_e$, where $\mathcal{H}_e\subset \mathcal{E}$ and $\mathcal{H}_0$ is presentable (in a suitable sense).

2. The same paper offers a fairly deep point of view about the “weak analogue” of the OSP, which can be regarded as a generalization of the Small Object Argument (SOA) in Homotopical Algebra; if we build the class $\mathcal{H}^\square$ of arrows having a non-unique lifting property against each $h\in\mathcal{H}$, then we can only hope in a weak reflection, where the unit of the adjunction is only weakly universal. In a setting where “things are defined up to homotopy” this can still be enough, provided that we ensure the reflection maps satisfy some additional properties. The additional property requested in the SOA is that the weak reflection maps belong to the cellular closure of $\mathcal{H}$, i.e. they can be obtained as a transfinite composition of pushouts of maps in $\mathcal{H}$.

3. The theory of factorization systems is deeply intertwined with the SOA, too: in [SOA] R. Garner defines an “algebraic” Small Object Argument, exploiting a description of OFS and WFS as suitable pairs $(comonad, monad)$ over the category $\mathbf{A}^{\Delta^1}$. In this respect I think that the best person which can give us sensible references for this is our boss, since she wrote this paper.

References and suggested reading

[LPAC] Jiří Adámek, Jiří Rosický, Locally presentable and accessible categories, LMS Lecture Notes Series 189, Cambridge University Press, (1994).

[FK] Freyd, P. J., & Kelly, G. M. (1972). Categories of continuous functors, I. JPAA, 2(3), 169-191.

[SOA] R. Garner, Understanding the small object argument, Applied Categorical Structures 17 (2009), no. 3, pages 247-285.

[PK] P. Gabriel and F. Ulmer, Lokal präsentierbare Kategorien, Springer LNM 221, 1971.

[AHS] J. Adamek, M. Hebert, L. Sousa, The Orthogonal Subcategory Problem and the Small Object Argument, Applied Categorical Structures 17, 211-246.