Physics Library
 An open source physics library
Encyclopedia | Forums | Docs | Random | Template Test |  
Login
create new user
Username:
Password:
forget your password?
Main Menu
Sections

Talkback

Downloads

Information
[parent] alternative definition of category (Definition)

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 1$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:

  • 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$.
  • 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)$
  • 3a For every $a \in M$, there exists an element $e \in M$ such that
    1. $(e,e) \in D$ and $e \circ e = e$
    2. $(a,e) \in D$ and $a \circ e = a$
    3. For all $x \in M$ such that $(x,e) \in D$, we have $x \circ e = x$.
  • 3a For every $a \in M$, there exists an element $e \in M$ such that
    1. $(e,e) \in D$ and $e \circ e = e$
    2. $(e,a) \in D$ and $e \circ a = a$
    3. 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:
  • 0. $(\forall a,b,c,d) ~ P(a,b,c) \land P(a,b,d) \Rightarrow c = d$.
  • 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))$
  • 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)$
  • 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)$
  • 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 ${\bf L}$ of morphisms which have $A$ as initial object, ${\bf L} = \cup_{B \in {\rm Ob}} {\rm Hom} (A,B)$, and the set ${\bf R}$ of morphisms which have $A$ as final object, ${\bf R} = \cup_{B \in {\rm Ob}} {\rm Hom} (B,A)$. Moreover, this pair of sets $({\bf L},{\bf 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 ${\bf L}$ and ${\bf R}$ of morphisms such that $x \in {\bf L}$ if and only if $x \circ y$ is defined for all $y \in {\bf R}$ and $x \in {\bf R}$ if and only if $y \circ x$ is defined for all $y \in {\bf L}$, then there exists an object $A$ which gives rise to ${\bf L}$ and ${\bf 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:

$\displaystyle \ell (a)$ $\displaystyle = \{ b \in M \mid (b,a) \in D \}$    
$\displaystyle r (a)$ $\displaystyle = \{ b \in M \mid (a,b) \in D \}$    
$\displaystyle {\cal L}$ $\displaystyle = \{ \ell (a) \mid a \in M \}$    
$\displaystyle {\cal R}$ $\displaystyle = \{ r (a) \mid a \in M \}$    

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$ and $(a,c) \in D$. If $d \in U$, then $(d,b) \in D$ 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)$. Likewise, switching the roles of $a$ and $b$ 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)$. Then $f \in S$ and $g \in R$. By the way we defined our pairs, $(g,f) \in D$, so $g \circ f$ is defined. Let $h$ be any element of $Q$. 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$ as well, it follows from axiom 2 that $(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$ 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$. Likewise, since ${\rm Hom} (E,A) \subset Q$ and ${\rm Hom} (F,B) \subset S$, it follows that ${\rm Hom} (E.A) \cap {\rm Hom} (F,B) = \emptyset$. 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]


Footnotes

... set1
For simplicity, we will only consider small categories here, avoiding logical complications related to proper classes.


"alternative definition of category" is owned by rspuzio. [ full author list (2) ]

View style:

See Also: categorical physics


This object's parent.

Cross-references: identity, predicate, composition, function, small categories, system, semigroups, objects, morphisms, category
There is 1 reference to this object.

This is version 2 of alternative definition of category, born on 2009-04-06, modified 2009-04-07.
Object id is 635, canonical name is AlternativeDefinitionOfCategory.
Accessed 451 times total.

Classification:
Physics Classification: 00. (GENERAL)
 02. (Mathematical methods in physics)
 03. (Quantum mechanics, field theories, and special relativity )
 03.65.Fd (Algebraic methods )
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:

No messages.

Testing some escape charachters for html category with a generator has an injective cogenerator" now escape ” with "