PlanetMath: precategory

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (232)
Orphanage
Unclass'd
Unproven (519)
Corrections (23)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

precategory

(Definition)

A precategory $\mathcal{B}$ consists of the following

a class of objects, called objects of $\mathcal{B}$ , written $Ob(\mathcal{B})$
a set of elements, called arrows or morphisms, for each ordered pair of objects in $\mathcal{B}$ , usually written $\hom(A,B)$ . For any arrow $f\in\hom(A,B)$ , is called the domain of and is the codomain of . It is required that $\hom(A,B)\cap\hom(C,D)=\varnothing$ if $(A,B)\neq(C,D)$ .

If $Ob(\mathcal{B})$ is a set, then we say that $\mathcal{B}$ is small. A small precategory is just a directed pseudograph (a digraph allowing multiple edges between pairs of vertices), indeed, for the collection of all arrows in $\mathcal{B}$ is a set, written $Mor(\mathcal{B})$ . In addition, there are two functions

$\displaystyle \operatorname{dom},\operatorname{codom}:Mor(\mathcal{B})\to Obj(\mathcal{B})$

such that $\operatorname{dom}(f)$ is the domain of

and $\operatorname{codom}(f)$ is the codomain of

. Note that both $\operatorname{dom}$ and $\operatorname{codom}$ are well-defined functions because if $f\in \hom(A,B)\cap \hom(C,D)$ , then

and

, so that both $\operatorname{dom}$ and $\operatorname{codom}$ map

to unique objects

and

respectively.

With the realization that a precategory is essentially a directed graph, we may use the language of graph theory to define concepts such as paths and loops in a precategory. This will allow us to enlarge any precategory to a category. We will carry out the construction below.

Paths Defined

Let $\mathcal{B}$ be a precategory. A path

(in $\mathcal{B}$ ) is a finite sequence of arrows $f_1,\ldots,f_n$ such that the codomain of

is the domain of $f_{i+1}$ . Note that the definition here does not parallel the one given for a graph (as in graph theory), since we allow vertices (domains and codomains), as well as edges (arrows or morphisms) to coincide. The length of a path $p=(p_1,\ldots,p_n)$ is defined to be the non-negative integer

Given a path $p = (f_1,\ldots, f_n)$ , we may set the domain of , written $\operatorname{dom}(p)$ , to be $\operatorname{dom}(f_1)$ , and codomain of , written $\operatorname{codom}(p)$ , to be $\operatorname{codom}(f_n)$ . A loop is a path where $\operatorname{dom}(p)=\operatorname{codom}(p)$ .

Next, for each ordered pair of objects in a precategory $\mathcal{B}$ , the collection of paths with with domain and codomain is a set, and we denote it by $\operatorname{Hom}(A,B)$ .

Composition of Paths Defined

Now, let $f\in \operatorname{Hom}(A,B)$ and $g\in \operatorname{Hom}(B,C)$ . So $f=(f_1,\ldots,f_n)$ and $g=(g_1,\ldots,g_m)$ . Since $\operatorname{codom}(f_n)=B=\operatorname{dom}(g_1)$ , we can “concatenate” the two paths and form a new path

$\displaystyle (f_1,\ldots,f_n,g_1,\ldots,g_m),$

and we write $g\circ f$ for this new path. It is clear that $g\circ f\in \operatorname{Hom}(A,C)$ . It is also easy to see that $\circ$ is a function from $\operatorname{Hom}(A,B)\times \operatorname{Hom}(B,C)$ to $\operatorname{Hom}(A,C)$ , if we set $\circ(f,g):= g\circ f$ . As the “concatenation” operation is evidently associative, $(h\circ g)\circ f=h\circ (g\circ f)$ .

Empty Paths Defined

Finally, for each object

in $Ob(\mathcal{B})$ , we can artificially associate an empty path

with

, with the following properties

is a path with length 0
$\operatorname{dom}(1_A)=\operatorname{codom}(1_A):=A$ ; in other words, $1_A\in \operatorname{Hom}(A,A)$
for any $f\in\operatorname{Hom}(A,B)$ and $g\in\operatorname{Hom}(C,A)$ , $f\circ 1_A:=f$ and $1_A\circ g:=g$ .

The class of all paths, including every empty path for each object, in $\mathcal{B}$ is written $Path(\mathcal{B})$ .

Precategory Enlarged to a Category

So if we start out with a precategory $\mathcal{B}$ , we end up with a category $\mathcal{\overline{B}}$ such that

$Ob(\mathcal{\overline{B}})=Ob(\mathcal{B})$
$Mor(\mathcal{\overline{B}})=Path(\mathcal{B})$ , such that
- domain and codomain of each morphism are defined to be the domain and codomain of the underlying path
- for each ordered pair of objects in $\mathcal{\overline{B}}$ , the collection of morphisms with domain and codomain is a set, and is denoted by $\operatorname{Hom}(A,B)$
- for every triple of objects , a function $\circ$ is defined to be the “concatenation” of a path from to and a path from to
- the identity morphism each object is just the empty path associated with .

We may embed $\mathcal{B}$ in $\mathcal{\overline{B}}$ so that $\mathcal{B}$ is just a diagram of $\mathcal{\overline{B}}$ . Because of this, $\mathcal{B}$ is also known as a diagram scheme. $\mathcal{\overline{B}}$ , also written $F(\mathcal{B})$ , is known as the free category freely generated by $\mathcal{B}$ .

"precategory" is owned by CWoo.

(view preamble | get metadata)