 2.2. INTRO TO CATEGORY THEORY

32

Proof.

Let

g

and

h

be both inverses of

f

. Then

h

=

h

1

Dst

f

=

h

f

g

=

1

Src

f

g

=

g

.

Definition

176

.

A

groupoid

is a category all of whose morphisms are isomor-

phisms.

Definition

177

.

A morphism whose source is the same as destination is called

endomorphism

.

Definition

178

.

An

involution

or

involutive morphism

is an endomorphism

f

that

f

f

= 1

Ob

f

. In other words, an involution is such a self-inverse (that is

conforming to the formula

f

=

f

1

) isomorphism.

Definition

179

.

Functor

from category

C

to category

D

is a mapping

F

which

associates every object

X

of

C

with an object

F

(

X

) of

D

and every morphism

f

:

X

Y

of

C

with morphism

F

(

f

) :

F

(

X

)

F

(

Y

) of

D

, such that:

1

.

F

(

g

f

) =

F

(

g

)

F

(

f

) for every composable morphisms

f

,

g

of

C

;

2

.

F

(1

C
X

) = 1

D
F X

for every object

X

of

C

.

2.2.1. Some important examples of categories.

Exercise

180

.

Prove that the below examples of categories are really cate-

gories.

Definition

181

.

The category

Set

is:

Objects are small sets.

Morphisms from an object

A

to an object

B

are triples (

A, B, f

) where

f

is a function from

A

to

B

.

Composition of morphisms is defined by the formula: (

B, C, g

)

(

A, B, f

) = (

A, C, g

f

) where

g

f

is function composition.

Definition

182

.

The category

Rel

is:

Objects are small sets.

Morphisms from an object

A

to an object

B

are triples (

A, B, f

) where

f

is a binary relation between

A

and

B

.

Composition of morphisms is defined by the formula: (

B, C, g

)

(

A, B, f

) = (

A, C, g

f

) where

g

f

is relation composition.

I will denote GR(

A, B, f

) =

f

for any morphism (

A, B, f

) of either

Set

or

Rel

.

Definition

183

.

A

subcategory

of a category

C

is a category whose set of

objects is a subset of the set of objects of

C

and whose set of morphisms is a subset

of the set of morphisms of

C

.

Definition

184

.

Wide subcategory

of a category (

O

,

M

) is a category (

O

,

M

0

)

where

M ⊆ M

0

and the composition on (

O

,

M

0

) is a restriction of composition of

(

O

,

M

). (Similarly

wide sub-precategory

can be defined.)

2.2.2. Commutative diagrams.

Definition

185

.

A

finite path in directed multigraph

is a tuple

J

e

0

, . . . , e

n

K

of

edges (where

i

N

) such that Dst

e

i

= Src

e

i

+1

for every

i

= 0

, . . . , n

1.

Definition

186

.

The vertices of a finite path are Src

e

0

, Dst

e

0

= Src

e

1

,

Dst

e

1

= Src

e

2

, . . . , Dst

e

n

.

Definition

187

.

Composition of finite paths

J

e

0

, . . . , e

n

K

and

J

e

k

, . . . , e

m

K

(where Dst

e

n

= Src

e

k

) is the path

J

e

0

, . . . , e

n

, e

k

, . . . e

m

K

. (It is a path because

Dst

e

n

= Src

e

k

.)