PlanetPhysics/Alternative Definition of Category

The notion of category may be defined in a form which only involves morphisms and does not mention objects. This definition shows that categories are a generalization of semigroups in which the closure axiom has been weakened; rather than requiring that the product of two arbitrary elements of the system be defined as an element of the system, we only require the product to be defined in certain cases.

We define a category to be a set \footnote{ For simplicity, we will only consider small categories here, avoiding logical complications related to proper classes.} $M$ (whose elements we shall term morphisms ) and a function $\circ$ (which we shall term composition) from a subset $D$ of $M\times M$ to $M$ which satisfies the following properties:

 \item{\mathbf 1.} If $a,b,c,d$ are elements of $M$ such that $(a,c)\in D$ and $(a,d)\in D$ and $(b,c)\in D$, then $(b,d)\in D$. \item{\mathbf 2} If $a,b,c$ are elements of $M$ such that $(a,b)\in D$ and $(b,c)\in D$, then $(a\circ b,c)\in D$ and $(a,b\circ c)\in D$ and $(a\circ b)\circ c=a\circ (b\circ c)$ \item{\mathbf 3a} For every $a\in M$, there exists an element $e\in M$ such that   #

• $(e,e)\in D$ and $e\circ e=e$ #
• $(a,e)\in D$ and $a\circ e=a$ #
• For all $x\in M$ such that $(x,e)\in D$, we have $x\circ e=x$. \item{\mathbf 3a} For every $a\in M$, there exists an element $e\in M$ such that #
• $(e,e)\in D$ and $e\circ e=e$ #
• $(e,a)\in D$ and $e\circ a=a$ #
• For all $x\in M$ such that $(x,e)\in D$, we have $e\circ a=x$.

This definition may also be stated in terms of predicate calculus. Defining the three place predicate $P$ by $P(a,b,c)$ if and only if $(a,b)\in D$ and $a\circ b=c$, our axioms look as follows:

 \item{\mathbf 0.} $(\forall a,b,c,d)~P(a,b,c)\land P(a,b,d)\Rightarrow c=d$. \item{\mathbf 1.} $(\forall a,b,c,d)~((\exists e)~P(a,c,e))\land ((\exists e)~P(a,d,e))\land ((\exists e)~P(b,c,e))z\Rightarrow ((\exists e)~P(b,d,e))$ \item{\mathbf 2.} $(\forall a,b,c,d,e)~P(a,b,d)\land P(b,c,e)\Rightarrow (\exists f)~P(d,c,f)\land P(a,e,f)$ \item{\mathbf 3a.} $(\forall a)(\exists b)~P(b,b,b)\land P(b,a,a)\land ((\forall c,d)~P(b,c,d)\Rightarrow c=d)$ \item{\mathbf 3b.} $(\forall a)(\exists b)~P(b,b,b)\land P(a,b,a)\land ((\forall c,d)~P(c,b,d)\Rightarrow c=d)$

That a category defined in the usual way satisfies these properties is easily enough established. Given two morphisms $f$ and $g$, the composition $f\circ g$ is only defined if $f\in {\rm {Hom}}(B,C)$ and $g\in {\rm {Hom}}(A,B)$ for suitable objects $A,B,C$, i.e if the final object of $f$ equals the initial object of $g$. The three hypotheses of axiom 1 state that the initial object of $a$ equals the final objects of $c$ and $d$ and that the initial object of $b$ also equals the final object of $c$; hence the initial object of $b$ equals the final object of $d$ so we may compose $b$ with $d$. Axiom 2 states associativity of composition whilst axioms 3a and 3b follow from existence of identity elements.

To show that the new definition implies the old one is not so easy because we must first recover the objects of the category somehow. The observation which makes this possible is that to each object $A$ we may associate two sets: the set ${\mathbf {L} }$ of morphisms which have $A$ as initial object, ${\mathbf {L} }=\cup _{B\in {\rm {Ob}}}{\rm {Hom}}(A,B)$, and the set ${\mathbf {R} }$ of morphisms which have $A$ as final object, ${\mathbf {R} }=\cup _{B\in {\rm {Ob}}}{\rm {Hom}}(B,A)$. Moreover, this pair of sets $({\mathbf {L} },{\mathbf {R} })$ determines $A$ uniquely. In order for this observation to be useful for our purposes, we must somehow characterize these pairs of sets without reference to objects, which may be done by the further observation that, if we have two sets ${\mathbf {L} }$ and ${\mathbf {R} }$ of morphisms such that $x\in {\mathbf {L} }$ if and only if $x\circ y$ is defined for all $y\in {\mathbf {R} }$ and $x\in {\mathbf {R} }$ if and only if $y\circ x$ is defined for all $y\in {\mathbf {L} }$, then there exists an object $A$ which gives rise to ${\mathbf {L} }$ and ${\mathbf {R} }$ as above. This fact may be demonstrated easily enough from the usual definition of category. We will now reverse the procedure, using our axioms to show that such pairs behave as objects should, justifying defining objects as such pairs.

Returning to our new definition, let us now define $\ell \colon M\to {\cal {P}}(M)$, $r\colon m\to {\cal {P}}(M)$, ${\cal {L}}\subseteq {\cal {P}}(M)$, and ${\cal {R}}\subseteq {\cal {P}}(M)$ as follows:

${\begin{matrix}\ell (a)&=\{b\in M\mid (b,a)\in D\}\\r(a)&=\{b\in M\mid (a,b)\in D\}\\{\cal {L}}&=\{\ell (a)\mid a\in M\}\\{\cal {R}}&=\{r(a)\mid a\in M\}\end{matrix}}$

We now show that, if $U,V\in {\cal {L}}$ then either $U\cap V=\emptyset$ or $U=V$. Suppose that $U,V\in {\cal {L}}$ and $U\cap V\neq \emptyset$. Then there exists a morphism $a$ such that $a\in U$ and $a\in V$. By the definition of ${\cal {L}}$, there exist morphisms $b$ and $c$ such that $U=\ell (b)$ and $V=\ell (c)$. By definition of $\ell$, we have $(a,b)\in D<math>and$(a,c) \in D$.If$d \in U$,then$(d,b) \in D</math> so, by axiom 1, $(d,c)\in D$, i.e. $d\in \ell (c)=V$. Likewise, switching the roles of $U$ and $V$ we conclude that, if $d\in V$, then $d\in U$. Hence $U=V$.

Making an argument similar to that of last paragraph, but with $r$ instead of $\ell$ and ${\cal {R}}$ instead of ${\cal {L}}$, we also conclude that, if $U,V\in {\cal {R}}$ then either $U\cap V=\emptyset$ or $U=V$. Because of axiom 3a, we know that, for every $a\in M$, there exists $b\in M$ such that $a\in \ell (b)$ and, by axiom 3b, there exists $c\in M$ such that $a\in r(c)$. Hence, the sets ${\cal {L}}$ and ${\cal {R}}$ are each partitions of $M$.

Next, we show that, if $S\in {\cal {L}}$ and $a,b\in S$, then $r(a)=r(b)$. By definition, there exists a morphism $c$ such that $S=\ell (c)$, so $(a,c)\in D$ and $(b,c)\in D$. Now suppose that $d\in r(a)$. This means that $(a,d)\in D$. By axiom 1, we conclude that $(b,d)\in D$, so $d\in r(b)<math>.Likewise,switchingtherolesof$a$and$b</math> in the foregoing argument, we conclude that, if $d\in r(b)$, then $d\in r(a)$. Thus, $r(a)=r(b)$.

By a similar argument to that of the last paragraph, we may also show that, if $S\in {\cal {R}}$ and $a,b\in S$, then $\ell (a)=\ell (b)$. Taken together, these results tell us that there is a one-to-one correspondence between of ${\cal {L}}$ and ${\cal {R}}$ --- to each $S\in {\cal {L}}$, there exists exactly one $T\in {\cal {R}}$ such that $S\times T\in D$ and vice-versa. In light of this fact, we shall define and object of our category to be a pair $(P,Q)$ of subsets of $M$ such that $x\in P$ if and only if $(x,y)\in D$ for all $y\in Q$ and $y\in Q$ if and only if $(x,y)\in D$ for all $x\in Q$. Given two objects $A=(P,Q)$ and $B=(R,S)$, we define ${\rm {Hom}}(A,B)=P\cap S$. We now will verify that, with these definitions, our axioms reproduce the defining properties of the standard definition of category.

Suppose that $A=(P,Q)$ and $B=(R,S)$ and $C=(U,V)$ are objects according to the above definition and that $f\in {\rm {Hom}}(A,B)$ and $g\in {\rm {Hom}}(B,C)<math>.Then$f \in S$and$g \in R$.Bythewaywedefinedourpairs,$(g,f) \in D$,so$g \circ f$isdefined.Let$h$beanyelementof$Q</math>. Since $f\in P$, it follows that $(f,h)\in D$. Since $(g,f)\in D$ as well, it follows from axiom 2 that $(g\cdot f,h)\in D$, so $g\circ f\in P$. Let $k$ be any element of $U$. Since $g\in V$, it follows that $(k,g)\in D$. Since $(g,f)\in D<math>aswell,itfollowsfromaxiom2that$(k,g \circ f) \in D$,so$g \circ f \in V$.Hence,$g \circ f \in P \cap V = {\rm Hom} (A,C)$.Thus,$\circ</math> is defined as a function from ${\rm {Hom}}(A,B)\times {\rm {Hom}}(B,C)\to {\rm {Hom}}(A,C)$.

Next, suppose that $A=(P,Q)$ and $B=(R,S)$ are distinct objects. By the properties described earlier, $P\cap R=\emptyset$ and $Q\cap S=\emptyset$. Let $E$ and $F$ be two objects. Since ${\rm {Hom}}(A,E)\subset P$ and ${\rm {Hom}}(B,F)\subset R$, it follows that ${\rm {Hom}}(A,E)\cap {\rm {Hom}}(B,F)=\emptyset <math>.Likewise,since${\rm Hom} (E,A) \subset Q$and${\rm Hom} (F,B) \subset S$,itfollowsthat${\rm Hom} (E.A) \cap {\rm Hom} (F,B) = \emptyset</math>. Hence, it follows that, given four objects $A,B,E,F$, we have ${\rm {Hom}}(A,E)\cap {\rm {Hom}}(B,F)=\emptyset$ unless $A=B$ and $E=F$.

[more to come]