1
$\begingroup$

This is a question from "Categories and computer science" by R F C Walters. I've spent longer than I should of on this question. The constraints imposed on the category are:

(i) every arrow has an inverse;

(ii) for each pair of objects, theres is an arrow from one to another;

(iii) for each object $A$ there are $n$ arrows with domain $A$.

and the goal is:

Show that the total number of endomorphisms (loops) is $n$

Progress: I think it's the case that

  1. As every arrow is an isomorphism, for any three objects $X, Y, Z$ and unique arrows $a_1, a_2$ from $X$ to $Y$, and arrow $b$ from $Y$ to $Z$, it has to be the case that $ba_1\neq ba_2$, because if $b$ is an isomorphism, it's mono, meaning $ba_1=ba_2 \implies a_1 = a_2$. This means there must be at least as many arrows from $X$ to $Z$ as there are arrows from $X$ to $Y$.
  2. You can show there must be at least as many arrows from $X$ to $Z$ as there are arrows from $Y$ to $Z$ by the same method as #1, but using the epi property of isomorphisms, in place of the mono.
  3. Replacing $Y$ in the above #2 with $X$ shows there must be at least as many arrows from $X$ to $Z$ as there are arrows from $X$ to itself (endomorphisms on $X$).
  4. Similarly to #3 Replacing $Z$ in point #1 with $X$ shows there must be at least as many arrows from endomorphisms on $X$ as there are arrows from $X$ to $Y$.
  5. Combining #3 and #4 gives the number of arrows from one object to another must be equal to the number of endomorphisms on the domain object
  6. And because each isomorphic arrow between two objects must have a unique arrow in the opposite direction as it's inverse, we know the number of arrows from one object to another is the same as the arrows in the oppisite direction.
  7. This means every pair of objects has the same number of arrows between them as endomorphisms on one object of the pair
  8. So each object has $n$ arrows with it as it's domain, and from #7 and that each pair of objects has atleast an arrow between them, the number of arrows going to each of the $o$ objects (including itself) in the category is the same. Giving $m$ arrows from the object to itself, for each of the o objects, for $m*o=n$ endomorphisms

The main reason I'm not convinced is the large number of steps compared to the other problems in the textbook, I'm convinced there must be a better way to the proof.

$\endgroup$
3
$\begingroup$

Your approach is pretty much right, and there's not really an obvious easier proof, but you can slim it down a little bit.

Take your category, and fix an object $X$. (Note that what the exercise is asking you to prove is not strictly true: the conditions hold for the empty category, but the conclusion does not. Thus our category needs to have at least one object, and we call it $X$.) Now there are in total $n$ arrows with domain $X$, that is to say, $$ \sum_{Y \in \mathrm{obj}} |\mathrm{Hom}(X, Y)| = n. $$ Now, for each $Y \in \mathrm{obj}$, I claim that $\mathrm{Hom}(X, Y)$ and $\mathrm{Hom}(Y, Y)$ have equally many elements. By the second condition, there is an arrow $f : X \to Y$, with inverse $f^{-1}: Y \to X$ by the first condition. But then we have a bijection $$ \begin{align} \alpha_f : \mathrm{Hom}(Y, Y) &\to \mathrm{Hom}(X, Y)\\ g &\mapsto g \circ f \end{align} $$ whose inverse is given by $$ \begin{align} \alpha_f : \mathrm{Hom}(X, Y) &\to \mathrm{Hom}(Y, Y)\\ h &\mapsto h \circ f^{-1}. \end{align} $$ Hence $|\mathrm{Hom}(X,Y)| = |\mathrm{Hom}(Y, Y)|$, and thus $$ n = \sum_{Y \in \mathrm{obj}} |\mathrm{Hom}(X, Y)| = \sum_{Y \in \mathrm{obj}} |\mathrm{Hom}(Y, Y)|, $$ which is what you wanted to prove.

$\endgroup$
  • $\begingroup$ This is much nicer in terms of size/notation - Thanks! $\endgroup$ – Aidan Connelly Jul 6 '18 at 12:32

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.