Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

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.

share|improve this answer
    
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 helpful –  Paul Slevin Sep 26 '12 at 19:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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