background image

8.2. COMPOSITION OF RELOIDS

184

Obvious

996

.

(

RLD

(

A, B

)

,

Rel

(

A, B

)) is a powerset filtrator isomorphic to the

filtrator (

RLD

]

(

A, B

)

,

Rel

(

A, B

)). Thus

RLD

(

A, B

) is a special case of

RLD

]

(

A, B

).

8.2. Composition of reloids

Definition

997

.

Reloids

f

and

g

are

composable

when Dst

f

= Src

g

.

Definition

998

.

Composition

of (composable) reloids is defined by the formula

g

f

=

RLD

l

G

F

F

up

f, G

up

g

.

Obvious

999

.

Composition of reloids is a reloid.

Obvious

1000

.

RLD

g

◦ ↑

RLD

f

=

RLD

(

g

f

) for composable morphisms

f

,

g

of category

Rel

.

Theorem

1001

.

(

h

g

)

f

=

h

(

g

f

) for every composable reloids

f

,

g

,

h

.

Proof.

For two nonempty collections

A

and

B

of sets I will denote

A

B

⇔ ∀

K

A

L

B

:

L

K

∧ ∀

K

B

L

A

:

L

K.

It is easy to see that

is a transitive relation.

I will denote

B

A

=

n

L

K

K

A,L

B

o

.

Let first prove that for every nonempty collections of relations

A

,

B

,

C

A

B

A

C

B

C.

Suppose

A

B

and

P

A

C

that is

K

A

and

M

C

such that

P

=

K

M

.

K

0

B

:

K

0

K

because

A

B

. We have

P

0

=

K

0

M

B

C

. Obviously

P

0

P

. So for every

P

A

C

there exists

P

0

B

C

such that

P

0

P

; the vice

versa is analogous. So

A

C

B

C

.

up((

h

g

)

f

)

up(

h

g

)

up

f

, up(

h

g

)

(up

h

)

(up

g

). By proven above

up((

h

g

)

f

)

(up

h

)

(up

g

)

(up

f

).

Analogously up(

h

(

g

f

))

(up

h

)

(up

g

)

(up

f

).

So up(

h

(

g

f

))

up((

h

g

)

f

) what is possible only if up(

h

(

g

f

)) =

up((

h

g

)

f

). Thus (

h

g

)

f

=

h

(

g

f

).

Exercise

1002

.

Prove

f

n

◦ · · · ◦

f

0

=

d

RLD

n

F

n

◦···◦

F

0

F

i

up

f

i

o

for every composable

reloids

f

0

, . . . , f

n

where

n

is an integer, independently of the inserted parentheses.

(Hint: Use generalized filter bases.)

Theorem

1003

.

For every reloid

f

:

1

.

f

f

=

d

RLD

n

F

F

F

up

f

o

if Src

f

= Dst

f

;

2

.

f

1

f

=

d

RLD

n

F

1

F

F

up

f

o

;

3

.

f

f

1

=

d

RLD

n

F

F

1

F

up

f

o

.

Proof.

I will prove only

1

and

2

because

3

is analogous to

2

.

1

It’s enough to show that

F, G

up

f

H

up

f

:

H

H

v

G

F

. To

prove it take

H

=

F

u

G

.

2

It’s enough to show that

F, G

up

f

H

up

f

:

H

1

H

v

G

1

F

.

To prove it take

H

=

F

u

G

. Then

H

1

H

= (

F

u

G

)

1

(

F

u

G

)

v

G

1

F

.

Exercise

1004

.

Prove

f

n

=

d

RLD

n

F

n

F

up

f

o

for every endofuncoid

f

and pos-

itive integer

n

.