background image

Proof.

By the theorem 81 (used that it is a boolean lattice) we have

X ∈

GR

f

GR

f

Q

i

n

atoms

X

i

and thus (6). From this also follows uniqueness.

It is left to prove that there exists a completary staroid

f

such that

f

is a continuation of

δ

.

Consider the relation

f

defined by the formula

X

f

δ

Q

i

n

atoms

A

i

X

i

.

I

0

I

1

f

δ

Q

i

n

atoms

A

i

(

I

0

i

I

1

i

)

∅ ⇔

δ

Q

i

n

(

atoms

A

i

I

0

i

atoms

A

i

I

1

i

)

.

Thus by the lemma

I

0

I

1

f

⇔ ∃

c

∈ {

0

,

1

}

n

:

δ

Q

i

n

atoms

A

i

I

c

(

i

)

∅ ⇔ ∃

c

∈ {

0

,

1

}

n

:

(

λi

n

:

I

c

(

i

)

i

)

f

. Trivially if

i

n

:

X

i

= 0

then

X

f

. So

f

is a completary staroid.

Let

a

Q

atoms

F

(

A

i

)

.

The reverse of (5) is obvious. So we have

a

δ

⇔ ∀

A

a

:

δ

Q

i

n

atoms

A

i

A

i

∅ ⇔ ∀

A

a

:

A

f

⇔ ∀

A

a

:

A

f

a

f

a

f

. Thus

f

is a continuation of

δ

.

Theorem 132.

Let

R

is a set of staroids of the form

λi

n

:

F

(

A

i

)

where every

A

i

is a boolean

lattice. If

x

Q

i

n

atoms

F

(

A

i

)

then

x

GR

d

R

⇔ ∀

f

R

:

x

f

.

Proof.

Let denote

x

δ

⇔ ∀

f

R

:

x

f

for every

x

Q

i

n

atoms

F

(

A

i

)

. For every

a

Q

i

n

atoms

F

(

A

i

)

X

a

:

δ

Q

i

n

atoms

A

i

X

i

∅ ⇔ ∀

X

a

x

Q

i

n

atoms

A

i

X

i

:

x

δ

⇔ ∀

X

a

x

Q

i

n

atoms

A

i

X

i

f

R

:

x

f

⇒ ∀

X

a, f

R

x

Q

i

n

atoms

A

i

X

i

:

x

f

⇒ ∀

X

a, f

R

:

X

f

⇔ ∀

f

R

:

a

f

⇔ ∀

f

R

:

a

f

a

δ

.

So by the previous theorem

δ

can be contimued till

p

for some staroid

p

of the form

λi

n

:

P

(

i

)

.

Let’s prove

p

=

d

R

.

x

p

x

δ

x

f

for every

f

R

and

x

Q

i

n

atoms

F

(

A

i

)

. Thus

p

f

. Consequently

f

R

:

p

f

.

Suppose that

q

is a staroid of the form

λi

n

:

P

(

A

i

)

such that

f

R

:

q

f

. Then for every

x

Q

i

n

atoms

F

(

A

i

)

we have

x

q

⇒ ∀

f

R

:

x

f

x

δ

x

p

. So

q

p

that is

q

p

.

We have proved

p

=

d

R

. It’s remained to prove that

x

p

⇔ ∀

f

R

:

x

f

for every

x

Q

i

n

atoms

F

(

A

i

)

. Really,

x

p

x

δ

⇔ ∀

f

R

:

x

f

.

11.4 Star composition of binary relations

First define

star composition

for an

n

-ary relation

a

and an

n

-indexed family

f

of binary relations

as an

n

-ary relation complying with the formulas:

Obj

StarComp

(

a

;

f

)

=

{∗}

n

;

L

StarComp

(

a

;

f

)

⇔ ∃

y

a

i

n

:

y

i

f

i

L

i

where

is a unique object of the semigroup of small binary relations considered as a category.

Proposition 133.

b

StarComp

(

a

;

f

)

⇔ ∃

x

a, y

b

j

n

:

x

j

f

j

y

j

.

Proof.

We need to prove that

b

StarComp

(

a

;

f

)

a

StarComp

(

b

;

f

)

.

b

StarComp

(

a

;

f

)

⇔ ∃

y

Q

A

: (

y

b

y

StarComp

(

a

;

f

))

⇔ ∃

x

Q

A

: (

y

b

∧ ∃

x

a

j

n

:

x

j

f

j

x

j

)

⇔ ∃

x

Q

A

, x

a

: (

y

b

∧ ∀

j

n

:

x

j

f

j

y

j

)

⇔ ∃

x

a, y

b

j

n

:

x

j

f

j

y

j

.

Theorem 134.

The semigroup of small binary relations considered as a category together with

the set of of all

n

-ary relations (for every small

n

) and the above defined star-composition form a

category with star-morphisms.

Proof.

We need to prove:

1. StarComp

(

StarComp

(

m

;

f

);

g

) =

StarComp

(

m

;

λi

n

:

g

i

f

i

);

2. StarComp

(

m

;

λi

arity

m

:

id

Obj

m

i

) =

m

;

3.

b

StarComp

(

a

;

f

)

a

StarComp

(

b

;

f

)

(the rest is obvious).

20

Section 11