background image

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 dened by the formula:

(

B

;

C

;

g

)

(

A

;

B

;

f

) = (

A

;

C

;

g

f

)

where

g

f

is function composition.

Denition 2.137.

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 dened 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

f

of either Set or Rel.

Denition 2.138.

A morphism whose source is the same as destination is called

endomorphism

.

Denition 2.139.

Wide subcategory

of a category

(

O

;

M

)

is a category

(

O

;

M

0

)

where

M

0

 M

and the composition on

(

O

;

M

0

)

is a restriction of composition of

(

O

;

M

)

. (Similarly

wide sub-

precategory

can be dened.)

2.3 Intro to group theory

Denition 2.140.

A

semigroup

is a pair of a set

G

and an associative binary operation on

G

.

Denition 2.141.

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

2

G

.

2. There exists an element

e

(

identity

) of

G

such that

f

e

=

e

f

=

f

for every

f

2

G

.

3. For every element

f

there exists an element

f

¡

1

such that

f

f

¡

1

=

f

¡

1

f

=

e

.

Obvious 2.142.

Every group is a semigroup.

Proposition 2.143.

In every group there exist exactly one identity element.

Proof.

If

p

and

q

are both identities, then

p

=

p

q

=

q

.

Proposition 2.144.

Every group element has exactly one inverse.

Proof.

Let

p

and

q

be both inverses of

f

2

G

. Then

f

p

=

p

f

=

e

and

f

q

=

q

f

=

e

. Then

p

=

p

e

=

p

f

q

=

e

q

=

q

.

Proposition 2.145.

(

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

.

Denition 2.146.

A

permutation group

on a set

D

is a group whose elements are functions on

D

and whose composition is function composition.

Obvious 2.147.

Elements of a permutation group are bijections.

Denition 2.148.

A

transitive

permutation group on a set

D

is such a permutation group

G

on

D

that for every

x; y

2

D

there exists

r

2

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.

2.3 Intro to group theory

31