background image

Theorem 7.13.

(

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

, 8

K

2

A

9

L

2

B

:

L

K

^ 8

K

2

B

9

L

2

A

:

L

K:

It is easy to see that

is a transitive relation.

I will denote

B

A

=

f

L

K

j

K

2

A; L

2

B

g

.

Let rst prove that for every nonempty collections of relations

A

,

B

,

C

A

B

)

A

C

B

C:

Suppose

A

B

and

P

2

A

C

that is

K

2

A

and

M

2

C

such that

P

=

K

M

.

9

K

0

2

B

:

K

0

K

because

A

B

. We have

P

0

=

K

0

M

2

B

C

. Obviously

P

0

P

. So for every

P

2

A

C

there

exists

P

0

2

B

C

such that

P

0

P

; the vice versa is analogous. So

A

C

B

C

.

GR

((

h

g

)

f

)

GR

(

h

g

)

GR

f

, GR

(

h

g

)

(

GR

h

)

(

GR

g

)

. By proven above

GR

((

h

g

)

f

)

(

GR

h

)

(

GR

g

)

(

GR

f

)

.

Analogously GR

(

h

(

g

f

))

(

GR

h

)

(

GR

g

)

(

GR

f

)

.

So GR

(

h

(

g

f

))

GR

((

h

g

)

f

)

what is possible only if GR

(

h

(

g

f

)) =

GR

((

h

g

)

f

)

.

Thus

(

h

g

)

f

=

h

(

g

f

)

.

Theorem 7.14.

For every reloid

f

:

1.

f

f

=

d

f"

RLD

(

F

F

)

j

F

2

xyGR

f

g

if Src

f

=

Dst

f

;

2.

f

¡

1

f

=

d

f"

RLD

(

F

¡

1

F

)

j

F

2

xyGR

f

g

;

3.

f

f

¡

1

=

d

f"

RLD

(

F

F

¡

1

)

j

F

2

xyGR

f

g

.

Proof.

I will prove only (1) and (2) because (3) is analogous to (2).

1. It's enough to show that

8

F ; G

2

xyGR

f

9

H

2

xyGR

f

:

H

H

v

G

F

. To prove it take

H

=

F

u

G

.

2. It's enough to show that

8

F ; G

2

xyGR

f

9

H

2

xyGR

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

.

Theorem 7.15.

For every sets

A

,

B

,

C

if

g; h

2

RLD

(

A

;

B

)

then

1.

f

(

g

t

h

) =

f

g

t

f

h

for every

f

2

RLD

(

B

;

C

)

;

2.

(

g

t

h

)

f

=

g

f

t

h

f

for every

f

2

RLD

(

C

;

A

)

.

Proof.

We'll prove only the rst as the second is dual.

By the innite distributivity law for lters we have

f

g

t

f

h

=

l

f"

RLD

(

F

G

)

j

F

2

xyGR

f ; G

2

xyGR

g

g t

l

f"

RLD

(

F

H

)

j

F

2

xyGR

f ; H

2

xyGR

h

g

=

l

f"

RLD

(

F

1

G

)

t "

RLD

(

F

2

H

)

j

F

1

; F

2

2

xyGR

f ; G

2

xyGR

g; H

2

xyGR

h

g

=

l

f"

RLD

((

F

1

G

)

t

(

F

2

H

))

j

F

1

; F

2

2

xyGR

f ; G

2

xyGR

g; H

2

xyGR

h

g

:

Obviously

l

f"

RLD

((

F

1

G

)

t

(

F

2

H

))

j

F

1

; F

2

2

xyGR

f ; G

2

xyGR

g; H

2

xyGR

h

g w

l

f"

RLD

(((

F

1

u

F

2

)

G

)

t

((

F

1

u

F

2

)

H

))

j

F

1

; F

2

2

xyGR

f ; G

2

xyGR

g; H

2

xyGR

h

g

=

l

f"

RLD

((

F

G

)

t

(

F

H

))

j

F

2

xyGR

f ; G

2

xyGR

g; H

2

xyGR

h

g

=

l

f"

RLD

(

F

(

G

t

H

))

j

F

2

xyGR

f ; G

2

xyGR

g; H

2

xyGR

h

g

:

Because

G

2

xyGR

g

^

H

2

xyGR

h

)

G

t

H

2

xyGR

(

g

t

h

)

we have

l

f"

RLD

(

F

(

G

t

H

))

j

F

2

xyGR

f ; G

2

xyGR

g; H

2

xyGR

h

g w

l

f"

RLD

(

F

K

)

j

F

2

xyGR

f ; K

2

xyGR

(

g

t

h

)

g

=

f

(

g

t

h

)

:

122

Reloids