11
$\begingroup$

I am wondering if the category of small categories $\mathbf{Cat}$ is known to (not) have the Cantor–Schröder–Bernstein property? That is, for any two categories $\mathcal{C}$ and $\mathcal{D}$, does the statement that there exist embedding functors (monomorphisms in $\mathbf{Cat}$) $\mathcal{F}: \mathcal{C} \rightarrow \mathcal{D}$ and $\mathcal{G}: \mathcal{D} \rightarrow \mathcal{C}$ imply that $\mathcal{C} \cong \mathcal{D}$?

If not, what can we say about the validity of the following weaker statement?

For any two categories $\mathcal{C}$ and $\mathcal{D}$, the statement that there exist embedding functors $\mathcal{F}_1: \mathcal{C} \rightarrow \mathcal{D}$ and $\mathcal{F}_2: \mathcal{D} \rightarrow \mathcal{C}$ implies that there exists bimorphisms (epic embedding functors) in $\mathbf{Cat}$ $\mathcal{G}_1: \mathcal{C} \rightarrow \mathcal{D}$ and $\mathcal{G}_2: \mathcal{D} \rightarrow \mathcal{C}$.

Thank you in advance for your help!

$\endgroup$
6
  • 11
    $\begingroup$ Can't one take the standard violations of CSB for orders, say, and translate this to categories? For example, the orders $\langle\mathbb{Q},<\rangle$ and $\langle\mathbb{Q}^{\geq 0},<\rangle$ each order-embed into each other, but are not isomorphic. Viewing these orders as categories would seem to produce a similar counterexample of your desired form. $\endgroup$ Commented Aug 15, 2023 at 19:19
  • $\begingroup$ @JoelDavidHamkins Precisely how do you view ordered sets as categories? What are the morphisms? $\endgroup$ Commented Aug 15, 2023 at 19:26
  • 8
    $\begingroup$ The objects are the elements of the order, and whenever $x< y$, then there is precisely one morphism from $x$ to $y$, plus the identity morphisms. $\endgroup$ Commented Aug 15, 2023 at 19:29
  • $\begingroup$ Ok, so as I thought. I see how this might produce counterexamples. Embeddings should not be too hard to construct. However, how can we prove there is no biomorphic functor $\mathcal{F}: (\mathbb{Q}, \geq ) \rightarrow (\mathbb{Q}^{\geq 0}, \geq )$ or, for that matter, maybe $\mathcal{F}: (\mathbb{Q}^{\geq 0}, \geq ) \rightarrow (\mathbb{Q}, \geq )$? $\endgroup$ Commented Aug 15, 2023 at 19:33
  • 2
    $\begingroup$ The latter order has a minimal element, which gives an initial object in the category, but the former does not. (but I don't know anything about biomorphic, sorry...) $\endgroup$ Commented Aug 15, 2023 at 19:35

2 Answers 2

20
$\begingroup$

One can take some of the standard violations of CSB with other kinds of mathematical structures and transfer them to categories.

For example, with linear orders, we have the two linear orders $$\langle\mathbb{Q},\leq\rangle\qquad \langle\mathbb{Q}^{\geq 0},\leq\rangle,$$ which each order-embed into each other, but they are not isomorphic, since the latter has a minimal element and the former does not.

But any linear order can be viewed as a category, where one takes the nodes of the order as objects, and whenever $x\leq y$ there is a unique morphism from $x$ to $y$, which is the identity morphism when $x=y$.

The order embeddings give rise to embedding functors in each direction for the categories, but these two categories are not isomorphic, since the latter one has an initial object, but the former does not.

This example answers directly the first part of the question. But actually it answers also the second part of the question, as explained in Peter's comment.

$\endgroup$
7
  • 1
    $\begingroup$ Sure, I did this. $\endgroup$ Commented Aug 15, 2023 at 19:45
  • 6
    $\begingroup$ @TianVlašić: In fact, Joel’s counterexample answers both parts of your question: these two orders are not connected by a bimorphism in $\mathrm{Cat}\newcommand{\Q}{\mathbb{Q}}$. The easiest way to see this is probably just by hand. First, for any $f : \Q_{\geq 0} \to \Q$, take two maps $g,g':\Q \to \Q$ which agree above $f(0)$ but differ below it; these show $f$ cannot be epi. Conversely, any epi $e : \Q \to \Q_{\geq 0}$ must hit $0$, by a similar argument; then taking some preimage $x$ of $0$, and some $x' < x$, the maps $1 \to \Q$ picking out $x$ and $x'$ show $e$ is not monic. $\endgroup$ Commented Aug 15, 2023 at 19:58
  • 3
    $\begingroup$ [cont’d] If you already know how to recognise epis/monics the category of preorders (or posets, or linear orders) then you can skip the details of my previous comment, by noting that the functors from these categories to $\mathrm{Cat}$ are faithful functors, so they reflect monos/epis, and hence any bimorphism between these orders as categories would be a bimorphism between them as orders. $\endgroup$ Commented Aug 15, 2023 at 20:02
  • 1
    $\begingroup$ @user2275150: Presumably that the restrictions of $g, g'$ to the set $\{q \in \mathbb Q:q \geq f(0)\}$ agree (but the values on rationals less than $f(0)$ are not the same). $\endgroup$
    – jdc
    Commented Aug 15, 2023 at 22:09
  • 2
    $\begingroup$ @TianVlašić: Given a map $f \newcommand{\Q}{\mathbb{Q}} : \Q_{\geq 0} \to \Q$ (a functor between them as categories, or equivalently, a monotone map of orders), clearly the image of $f$ must lie within $\Q_{\geq f(0)} \subsetneq \Q$. We expect this to mean that $f$ can’t be epi; and to justify this expectation, take $g, g'$ to be any maps/functors out of $\Q$ that agree on all arguments $x \geq f(0)$ but differ on some $x < f(0)$, e.g. $g = \mathrm{id} : \Q \to \Q$, and $g'(x) = x$ for $x \geq f(0)$ but $g'(x) = x-1$ for $x < f(0)$. Then $gf = g'f$ but $g \neq g'$, so $f$ is not epi. $\endgroup$ Commented Aug 16, 2023 at 8:21
3
$\begingroup$

This is simply a summary that includes all the details.

$\mathbf{Pos}$ usually denotes the category of partially ordered sets as objects and monotone functions as morphisms. For any partially ordered set $(A, \leq)$, we may consider its associated categorification $\mathcal{C}(A, \leq)$ (this is simply viewing $(A, \leq)$ as a category).

There is a natural functor $U: \mathbf{Pos} \rightarrow \mathbf{Cat}$ defined such that, for every partially ordered set $X$, $U(X)=\mathcal{C}(X)$ and such that, for every morphism $f$, $U(f)$ is the unique functor for which the object component of $U(f)$ equals $f$.

@Joel David Hamkins has directly answered the first part of my question by providing a simple counterexample which shows that $\mathbf{Cat}$ does not have the Cantor-Schroder-Bernstein property.

In his answer, Joel considered $(\mathbb{Q}_{\geq 0}, \leq )$ and $(\mathbb{Q}, \leq )$. Given two morphisms $f_1 : (\mathbb{Q}_{\geq 0}, \leq ) \rightarrow (\mathbb{Q}, \leq )$ and $f_2: (\mathbb{Q}, \leq ) \rightarrow (\mathbb{Q}_{\geq 0}, \leq )$ in $\mathbf{Pos}$ (monotone maps), $U(f_1): \mathcal{C}(\mathbb{Q}_{\geq 0}, \leq ) \rightarrow \mathcal{C}(\mathbb{Q}, \leq )$ and $U(f_2): \mathcal{C}(\mathbb{Q}, \leq ) \rightarrow \mathcal{C}(\mathbb{Q}_{\geq 0}, \leq )$ are easily seen to be monomorphisms in $\mathbf{Cat}$ (these functors are injective on objects since any monotone map is injective and are faithful vacuously). However, it doesn't hold that $\mathcal{C}(\mathbb{Q}_{\geq 0}, \leq ) \cong \mathcal{C}(\mathbb{Q}, \leq )$ since $\mathcal{C}(\mathbb{Q}_{\geq 0}, \leq )$ has an initial object and $\mathcal{C}(\mathbb{Q}, \leq )$ does not.

As was mentioned by @Peter LeFanu Lumsdaine in the comments, it turns out that Joel's counterexample can be extended to completely answer my question. Namely, $U$ is a faithful functor. Thus, to show that there are no bimorphisms from $\mathcal{C}(\mathbb{Q}_{\geq 0}, \leq )$ to $\mathcal{C}(\mathbb{Q}, \leq )$ in $\mathbf{Cat}$, we only need to show that there is no bimorphism from $(\mathbb{Q}_{\geq 0}, \leq )$ to $(\mathbb{Q}, \leq )$ in $\mathbf{Pos}$.

Peter defined, for every morphism $g : (\mathbb{Q}_{\geq 0}, \leq ) \rightarrow (\mathbb{Q}, \leq )$ in $\mathbf{Pos}$, a morphism $\tilde{g} : (\mathbb{Q}, \leq ) \rightarrow (\mathbb{Q}, \leq )$ defined by the rule

\begin{equation*} \forall x \in \mathbb{Q}: \tilde{g}(x)=\left\{\begin{matrix} x, & x \geq g(0)\\ x-1, & x < g(0) \end{matrix}\right. . \end{equation*}

It holds that $\tilde{g} \circ g=g$. Thus, $g$ is not an epimorphism and is thus not a bimorphism. We conclude that there exists no bimorphism in $\mathbf{Pos}$ from $(\mathbb{Q}_{\geq 0}, \leq )$ to $(\mathbb{Q}, \leq )$.

$\endgroup$
2
  • 8
    $\begingroup$ I think the usual etiquette would say that it is more appropriate to accept @JoelDavidHamkins's answer than your summary of it. $\endgroup$
    – LSpice
    Commented Aug 17, 2023 at 21:19
  • 1
    $\begingroup$ @LSpice The post summarizes both Joel's answer and Peter's comments. But, I agree. Thank you for this! $\endgroup$ Commented Aug 17, 2023 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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