 2.3. INTRO TO GROUP THEORY

27

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

148

.

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

.

I will denote

h

f

i

=

h

GR

f

i

and [

f

]

=[GR

f

]

for any morphism (

A

;

B

;

f

) of

either

Set

or

Rel

.

Definition

149

.

A morphism whose source is the same as destination is called

endomorphism

.

Definition

150

.

FiXme

: Definition of

subcategory

Wide subcategory

of a cate-

gory (

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.3. Intro to group theory

Definition

151

.

A semigroup is a pair of a set

G

and an associative binary

operation on

G

.

Definition

152

.

A group is a pair of a set

G

and a binary operation

·

on

G

such that:

1

. (

h

·

g

)

·

f

=

h

·

(

g

·

f

) for every

f, g, h

G

.

2

. There exists an element

e

(

identity

) of

G

such that

f

·

e

=

e

·

f

=

f

for

every

f

G

.

3

. For every element

f

there exists an element

f

1

such that

f

·

f

1

=

f

1

·

f

=

e

.

Obvious

153

.

Every group is a semigroup.

Proposition

154

.

In every group there exist exactly one identity element.

Proof.

If

p

and

q

are both identities, then

p

=

p

·

q

=

q

.

Proposition

155

.

Every group element has exactly one inverse.

Proof.

Let

p

and

q

be both inverses of

f

G

. Then

f

·

p

=

p

·

f

=

e

and

f

·

q

=

q

·

f

=

e

. Then

p

=

p

·

e

=

p

·

f

·

q

=

e

·

q

=

q

.

Proposition

156

.

(

g

·

f

)

1

=

f

1

·

g

1

for every group elements

f

and

g

.

Proof.

(

f

1

·

g

1

)

·

(

g

·

f

) =

f

1

·

g

1

·

g

·

f

=

f

1

·

e

·

f

=

f

1

·

f

=

e

. Similarly

(

g

·

f

)

·

(

f

1

·

g

1

) =

e

. So

f

1

·

g

1

is the inverse of

g

·

f

.

Definition

157

.

A

permutation group

on a set

D

is a group whose elements

are functions on

D

and whose composition is function composition.

Obvious

158

.

Elements of a permutation group are bijections.

Definition

159

.

A

transitive

permutation group on a set

D

is such a per-

mutation group

G

on

D

that for every

x, y

D

there exists

r

G

such that

y

=

r

(

x

).

A groupoid with single (arbitrarily chosen) object corresponds to every group.

The morphisms of this category are elements of the group and the composition of

morphisms is the group operation.