# To which extent is a thin category determined by its graph?

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.

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