7
$\begingroup$

This question was originally asked by Paul Slevin, but it was deleted before I had the chance to answer. It's actually quite subtle, so I thought it would be worth reposting it here.


Consider the following proposition: $\DeclareMathOperator{\mor}{mor}$

Proposition. Let $\mathcal{C}$ be a category. If $\mathcal{C}$ has limits indexed by diagrams of size $\left| \mor \mathcal{C} \right|$, then $\mathcal{C}$ must be a preorder.

This is easy to prove when $\mathcal{C}$ is a small category: assume, for a contradiction, that there are two distinct parallel arrows $f, g : A \to B$ in $\mathcal{C}$. Since $\mathcal{C}$ has large products, there exists an object $C$ in $\mathcal{C}$ equipped with a bijection $\textbf{Set}(\mor \mathcal{C}, \mathcal{C}(X, B)) \cong \mathcal{C}(X, C)$ that is natural in $X$. In particular, we have $\textbf{Set}(\mor \mathcal{C}, \mathcal{C}(A, B)) \cong \mathcal{C}(A, C) \subseteq \mor \mathcal{C}$ but the LHS has cardinality $\ge 2^{\left| \mor \mathcal{C} \right|}$, so this contradict's Cantor's theorem on powersets.

Question. How do I adapt this proof for the case where $\mor \mathcal{C}$ is a proper class? In class–set theories such as von Neumann–Bernays–Gödel or Morse–Kelley, it doesn't make sense to talk about the collection of all subclasses of a proper class, because any member of any class is a set, and even the collection of all maps $\mor \mathcal{C} \to \mathcal{C}(X, B)$ fails to be a class.

1 Answers 1

4

The case for a category with a set of morphisms has already been dealt with, so let $\mathcal{C}$ have a proper class of morphisms and class-indexed products. Assume for a contradiction that there are two distinct parallel arrows $f, g : A \to B$ in $\mathcal{C}$. Since $\mathcal{C}$ has large products, there exists an object $C$ in $\mathcal{C}$ and a map $\pi_\bullet : \mor \mathcal{C} \to \mathcal{C}(C, B)$ such that, for all maps $h_\bullet : \mor \mathcal{C} \to \mathcal{C}(X, B)$, there exists a unique morphism $\vec{h} : X \to C$ such that $\pi_i \circ \vec{h} = h_i$ for all $i$ in $\mor \mathcal{C}$. (This circumlocution is required because the collection of all maps $\mor \mathcal{C} \to \mathcal{C}(X, B)$ is too big to be a class in general.)

It is not hard to see that $\mathcal{C}(A, C)$ is too big to be a set, so by limitation of size, there is a bijection $\vec{k}_\bullet : \mor \mathcal{C} \to \mathcal{C}(A, C)$. However, consider the map $h_\bullet : \mor \mathcal{C} \to \mathcal{C}(A, B)$ defined as follows: $h_i = \begin{cases} f & \text{if } \pi_i \circ \vec{k}_i \ne f \\ g & \text{if } \pi_i \circ \vec{k}_i = f \end{cases}$ This is legitimate because we don't have to quantify over all classes to define $h_i$. By hypothesis there is a (unique) morphism $\vec{h} : A \to C$ such that $\pi_i \circ \vec{h} = h_i$, and $\vec{h} = \vec{k}_j$ for some $j$ in $\mor \mathcal{C}$. Yet, $\pi_j \circ \vec{h} = \begin{cases} f & \text{if } \pi_j \circ \vec{k}_j = \pi_j \circ \vec{h} \ne f\\ g & \text{if } \pi_j \circ \vec{k}_j = \pi_j \circ \vec{h} = f \end{cases}$ which is a contradiction. Hence we couldn't have had $f \ne g$ in the first place, so $\mathcal{C}$ is just a preorder.


Basically, the above argument internalises Cantor's proof that $2^\kappa \gneq \kappa$, without ever mentioning the collection of "all subclasses of a proper class" – we instead substitute $\mathcal{C}(A, C)$, which is "big" enough to make Cantor's proof go through. The reliance of the axiom of limitation of size can probably be removed – but then we have to work a bit harder to get a paradoxical surjection from $\mor \mathcal{C}$ to $\mathcal{C}(A, C)$.

On the other hand, the use of the law of excluded middle is essential here – for example, it is known that in the effective topos, the proposition is false.

  • 0
    Thanks for reposting the question. I deleted it because I felt that you had already given enough information in my previous question... but this is of course very helpful2012-09-26