I'm reading Abstract and Concrete Categories and am currently attempting to solve the very first exercise, which asks to show that a thin category is determined by its graph up to isomorphism.

Here, a category $\mathbf{A}$ is a quadruple $(\mathcal{O},\mathrm{hom},\mathrm{id},\circ)$, such that

  • $\mathcal{O}$ is a class of objects, alternatively denoted $\mathrm{Ob}(\mathbf{A})$,
  • $\mathrm{hom}\colon\mathcal{O}^2\rightarrow\mathcal{U}$ is a mapping, where each element of its image is called a hom-set (here, $\mathcal{U}$ is the universe, i.e. the class of all sets),
  • $\mathrm{id}\colon\mathcal{O}\rightarrow\mathrm{Mor}(\mathbf{A})\colon=\bigcup_{X\in\mathrm{hom}(\mathcal{O}^2)}X$ is a mapping that sends an $\mathbf{A}$-object $A$ to an identity morphism $\mathrm{id}_A\in\mathrm{hom}(A,A)$ and
  • $\circ\colon\mathrm{Mor}(\mathbf{A})\times\mathrm{Mor}(\mathbf{A})\leadsto\mathrm{Mor}(\mathbf{A})$ is a partial mapping that is defined on $(g,f)$ iff $f\in\mathrm{hom}(A,B)$ and $g\in\hom(B,C)$ for $A,B,C\in\mathrm{Ob}(\mathbf{A})$; in that case, $g\circ f\colon=\circ(g,f)\in\mathrm{hom}(A,C)$.

These are subject to the conditions that

  • composition is associative, i.e. $(h\circ g)\circ f=h\circ(g\circ f)$ whenever defined,
  • for any morphism $f\in\mathrm{hom}(A,B)$, we have $\mathrm{id}_B\circ f=f=f\circ\mathrm{id}_A$ and
  • hom-sets are disjoint.

A morphism $f\in\mathrm{Mor}(\mathbf{A})$ is by definition a member of a hom-set $\mathrm{hom}(A,B)$ with $A,B\in\mathrm{Ob}(\mathbf{A})$ and, by disjointedness of hom-sets, it is the member of exactly one hom-set. Thus, setting $\mathrm{dom}(f)=A$ and $\mathrm{cod}(f)=B$ produces two well-defined mappings $\mathrm{dom},\mathrm{cod}\colon\mathrm{Mor}(\mathbf{A})\rightarrow\mathrm{Ob}(\mathbf{A})$, giving what is called domain and codomain of a morphism respectively.

Furthermore, a large graph is defined as a quadruple $(V,E,d,c)$, where $V$ and $E$ are classes (called the class of vertices and edges respectively), and $d\colon E\rightarrow C$ and $c\colon E\rightarrow C$ are mappings giving what is called domain or codomain of each edge respectively. The graph $G(\mathbf{A})$ of a category $\mathbf{A}$ is the graph with $V=\mathrm{Ob}(\mathbf{A})$, $E=\mathrm{Mor}(\mathbf{A})$, $d=\mathrm{dom}$ and $c=\mathrm{cod}$.

A thin category is a category where any hom-set contains at most one element. Let $\mathbf{A}=(\mathcal{O},\mathrm{hom},\mathrm{id},\circ)$ and $\mathbf{A}^\prime=(\mathcal{O}^\prime,\mathrm{hom}^\prime,\mathrm{id}^\prime,\circ^\prime)$ be two thin categories such that $G(\mathbf{A})=G(\mathbf{A}^\prime)$. I.e. $$(\mathrm{Ob}(\mathbf{A}),\mathrm{Mor}(\mathbf{A}),\mathrm{dom},\mathrm{cod})=G(\mathbf{A})=G(\mathbf{A}^\prime)=(\mathrm{Ob}(\mathbf{A}^\prime),\mathrm{Mor}^\prime(\mathbf{A}),\mathrm{dom}^\prime,\mathrm {cod}^\prime),$$ where the $^\prime$ denotes being relative to the category $\mathbf{A}^\prime$. From this, it follows immediately by definition of a tuple that $\mathcal{O}=\mathrm{Ob}(\mathbf{A})=\mathrm{Ob}(\mathbf{A}^\prime)=\mathcal{O}^\prime$, $\mathrm{Mor}(\mathbf{A})=\mathrm{Mor}(\mathbf{A}^\prime)$, $\mathrm{dom}=\mathrm{dom}^\prime$ and $\mathrm{cod}=\mathrm{cod}^\prime$. Let $A,B\in\mathcal{O}=\mathcal{O}^\prime$. We then have by definition that $$\mathrm{hom}(A,B)=\mathrm{dom}^{-1}(\left\{A\right\})\cap\mathrm{cod}^{-1}(\left\{B\right\})=(\mathrm{dom}^\prime)^{-1}(\left\{A\right\})\cap(\mathrm{cod}^\prime)^{-1}(\left\{B\right\})=\mathrm{hom}^\prime(A,B).$$ Thus, $\mathrm{hom}=\mathrm{hom}^\prime$. Now let $A,B,C\in\mathcal{O}$, $f\in\mathrm{hom}(A,B)$ and $g\in\mathrm{hom}(B,C)$ be arbitrary. Then, $g\circ f\in\mathrm{hom}(A,C)$ exists, i.e. the hom-set $\mathrm{hom}(A,C)$ has at least on element, but, since $\mathbf{A}$ is thin, it contains at most one element, hence it has exactly one element. Since $\mathrm{Ob}(\mathbf{A})=\mathrm{Ob}(\mathbf{A}^\prime)$ and $\mathrm{Mor}(\mathbf{A})=\mathrm{Mor}(\mathbf{A}^\prime)$, we may regard $f,g$ as morphisms in $\mathbf{A}^\prime$ and thus $g\circ^\prime f$ exists. By nature of composition, we have $g\circ^\prime f\in\mathrm{hom}(A,C)$, but since this set has exactly one element, it follows that $g\circ f=g\circ^\prime f$ and, since $f,g$ were arbitrary, it follows that $\circ=\circ^\prime$.

Finally, let $A,B\in\mathrm{Ob}(\mathbf{A})$ and $f\in\mathrm{hom}(A,B)$ be arbitrary. By the previous result, it holds that $\mathrm{id}_B\circ^\prime f=\mathrm{id}_B\circ f=f$ and $f\circ^\prime\mathrm{id}_A=f\circ\mathrm{id}_A=f$. Hence, the identity morphisms in $\mathbf{A}$ are also identity morphisms in $\mathbf{A}^\prime$ and, by uniqueness of identities, it follows that $\mathrm{id}=\mathrm{id}^\prime$.

Finally, by the definition of a tuple, it follows that $\mathbf{A}=\mathbf{A}^\prime$.

Now, this doesn't only imply that a graph determines a thin category up to isomorphism (as was required to be shown), but it shows that a thin category is uniquely determined by its graph. This claim is clearly stronger than the initial one and since the proposed proof is pretty trivial, I suspect there must be an error as otherwise the way the exercise was stated seems off. My question now is where any error or potential misunderstanding lies.

  • 3
    $\begingroup$ There is no mistake. Indeed, thin categories are determined by their graphs up to equality (and, as a consequence, up to isomorphism). $\endgroup$ – Oskar Jan 3 at 0:15

Your Answer

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

Browse other questions tagged or ask your own question.