1
$\begingroup$

I've been trying to understand an analogue of Russell's paradox for categories (Please refer to this link for more details and preliminaries about my question: Russell Pardox for naive category theory)

I don't understand the first lemma, specifically how does the presence of M and N in $C_1$ results in any arbitrary category in $C_1$ being isomorphic to some category in $C_2$? I feel like something was skipped in the sketch which is needed to understand it. So, it will be great if someone could shine light on this missing thing.


(The relevant part of the text is also copied here.)

Just for reference, let me give some more details of my Russell paradox for naive category theory.

Setting:

We are working in a naive category theory setting, i.e., category theory where the foundation (set-theoretic or otherwise) has been left unspecified.

Definition. A category of categories is a category $\mathcal C$ such that
(i) each object of $\mathcal C$ is a category,
(ii) for any objects $A$ and $B$ of $\mathcal C$, the morphisms from $A$ to $B$ in $\mathcal C$ are exactly the functors from $A$ to $B$,
(iii) for any object $A$ of $\mathcal C$, the identity morphism $1_A$ at $A$ is the identity functor on $A$,
(iv) the composition law for morphisms of $\mathcal C$ is given by composition of functors.

Definition. A category $\mathcal C$ is universal if
(i) $\mathcal C$ is a category of categories, (ii) every category is isomorphic to some category which belongs to $\mathcal C$.

Theorem. There is no universal category.

Proof

In order to give the proof, we use the following definitions and lemmas.

Let $M$ be the category with exactly two objects $A$ and $B$ and exactly three morphisms $1_A$, $1_B$, and $f: A\to B$.

Let $N$ be the category with exactly three objects $A, B, C$ and exactly six morphisms $1_A, 1_B, 1_C, f: A \to B, g: B \to C, h: A \to C$.

Lemma. Let $\mathcal C_1$ and $\mathcal C_2$ be two isomorphic categories such that
(i) $\mathcal C_1$ is a category of categories,
(ii) $\mathcal C_2$ is a category of categories,
(iii) $\mathcal C_1$ contans categories that are isomorphic to $M$ and $N$.
Then every category belonging to $\mathcal C_1$ is isomorphic to some category belonging to $\mathcal C_2$, and vice versa.

Proof (sketch). If $C$ is any category belonging to $\mathcal C_1$, there is an obvious one-to-one correspondence between morphisms of $C$ and functors from $M$ into $C$, and compositions of such morphisms are picked out by functors from $N$ into $C$.
Thus the isomorphism types of categories belonging to $\mathcal C_1$ are determined by the isomorphism type of $\mathcal C_1$ itself.
Furthermore, the same goes for $\mathcal C_2$, because $\mathcal C_2$ also contains categories isomorphic to $M$ and $N$.
The lemma follows.

Definition. A category $\mathcal C$ is autistic if
(i) $\mathcal C$ is a catogory of categories,
(ii) $\mathcal C$ is isomorphic to some category which is an object of $\mathcal C$.
$\ $ A category $\mathcal C$ is pseudoautistic if it is isomorphic to some autistic category.

Lemma. Let $\mathcal C$ be a category of categories such that
(i) $\mathcal C$ is pseudoautistic,
(ii) $\mathcal C$ contains categories isomorphic to $M$ and $N$.
Then $\mathcal C$ is autistic.

Proof. This follows immediately from the previous lemma.


To prove the theorem, let $\mathcal C$ be a universal category.
Let $\mathcal D$ be the full subcategory of $\mathcal C$ consisting of all categories belonging to $\mathcal C$ which are not pseudoautistic.
Then $\mathcal D$ is again a category of categories.
Also, since $M$ and $N$ are not pseudoautistic, $\mathcal D$ contains categories isomorphic to $M$ and $N$.

Suppose first that $\mathcal D$ is autistic.
Then $\mathcal D$ is isomorphic to some category $E$ which belongs to $\mathcal D$.
Then $E$ is pseudoautistic. Hence, by definition of $\mathcal D$, $E$ does not belong to $\mathcal D$. This is a contradiction.
We have shown that d is not autistic.
It follows by the previous lemma that $\mathcal D$ is not pseudoautistic.
Since $\mathcal C$ is universal, $\mathcal D$ is isomorphic to some category $E$ which belongs to $\mathcal C$. Hence $E$ is not psuedoautistic. Hence $E$ belongs to $\mathcal D$.
Thus $\mathcal D$ is autistic. This is a contradiction.
The theorem is proved.

$\endgroup$
1
$\begingroup$

We write $\mathcal C(A,B)$ for the homset of arrows $A\to B$ in some category $\mathcal C$.

Let $\varphi:\mathcal C_1\to\mathcal C_2$ a category isomorphism.
Besides that functors from the two specific categories, 'the arrow' $M$ and 'the composition' $N$, encode the category structure, the main (implicit) statement is that $\varphi(M)$ must be isomorphic to $M$ and $\varphi(N)$ to $N$.

For any objects $C,X\in Ob\,\mathcal C_1$ we have $\ \mathcal C_1(X,C)\cong\mathcal C_2(\varphi(X),\,\varphi(C))$.
Moreover, if $C=X$, we get isomorphism of the endomorphism monoids.

Applying it to $X=C=M$ yields that $\varphi(M)$ has exactly 3 endofunctors, corresponding to the 3 endofunctors $M\to M$ (which themselves correspond to arrows of $M$), with the same monoid structure.
Note that a nontrivial category $C$ has at least one more endofunctors as objects because of the constant functors and the identity.
This itself shows that $\varphi(M)$ can have at most $2$ objects, and investigating endofunctors of categories with $1$ or $2$ objects leads to the more specific description of $\varphi(M)$.

Once $\varphi(M)\cong M$ is shown, based on this, one can also prove $\varphi(N)\cong N$, and then the rest follows.

$\endgroup$
  • $\begingroup$ Thank you for the hint, and for not spoiling the fun by giving the whole proof. At the moment, I am looking at endofunctors on categories with 1 object. $\endgroup$ – jaspreet Jul 22 at 16:07
  • 1
    $\begingroup$ I'm actually not sure that my proposed solution works, nevertheless it gives some taste of the problem. If also the one point trivial category $L$ was involved besides $M$ and $N$, then we would certainly get $\varphi(L)\cong L$ and thus $\varphi(M)$ must have exactly 2 objects.. $\endgroup$ – Berci Jul 22 at 22:55
  • $\begingroup$ I've made some progress (Please do see my posted documentation of it), but I don't quite clearly see any way forward. So, I'm to going to work on something else for a while in the hope that things will sort out with time. $\endgroup$ – jaspreet Sep 30 at 3:42
0
$\begingroup$

Partial Answer? Thanks to @Berci for his wonderful cues that I was able to discover following elementary insights.

Number of Objects and Constant Endofunctors

Number of objects of any non-empty category can be established by way of number of constant endofunctors on it because there exists a 1-1 to correspondence b/w them.

However, how can one distinguish constant endofunctors if one has just one category and its endofunctors? It turns out that following holds in the universe of categories: Let $C$ be any category. Then any functor $F:C\rightarrow D$ is a constant functor iff $\forall \alpha:C\rightarrow C$, $\ F\circ \alpha=F$.

A special bit

Consider the category $\varphi(M)$. It has exactly three endofunctors: one being identity and other two being constant at each of the two objects. It can be proven that if there exists no map b/w the two objects of $\varphi(M)$, then one is able to create another functor which switches the objects i.e. it takes the object to the other object and vice versa. This is a contradiction, therefore there must exist at least 1 map b/w the two objects.

At this point, I am stuck. Perhaps, I will come back to the question later. Or somebody else will point out what I have missed but was staring at my face.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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