 16.3. BEFORE THE DIAGRAM

260

3

4

.

[

X

S

(

X

×

Y

X

) =

[

X

S

X

×

[

R

Y

X

X

S

P

Y

X

=

[

X

S

X

×

[

(

Y

0

R

Y

X

X

S

Y

0

Y

X

)!

=

[

X

S

X

×

[

(

Y

0

R

Y

X

X

S

(

X, Y

0

)

σ

)!

=

[

(

X,Y

)

σ

(

X

×

Y

)

where

σ

is a relation between

S

and

R

Y

X

X

S

, and (

X, Y

0

)

σ

Y

0

Y

X

.

5

1

Obvious.

3

5

Let

Q

=

S

X

S

(

X

×

Y

X

) =

S

i

=0

,...,n

1

(

X

i

×

Y

i

) for a partition

S

=

{

X

0

, . . . , X

n

1

}

of

A

. Then

Q

=

T

i

=0

,...,n

1

X

i

×

Y

i

X

i

×

B

.

Exercise

1382

.

Formulate the duals of these sets.

Proposition

1383

.

Γ(

A, B

) is a boolean lattice, a sublattice of the lattice

P

(

A

×

B

).

Proof.

That it’s a sublattice is obvious. That it has complement, is also

obvious. Distributivity follows from distributivity of

P

(

A

×

B

).

16.3. Before the diagram

Next we will prove the below theorem

1399

(the theorem with a diagram).

First we will present parts of this theorem as several lemmas, and then then state

a statement about the diagram which concisely summarizes the lemmas (and their

easy consequences).

Below for simplicity we will equate reloids with their graphs (that is with filters

on binary cartesian products).

Obvious

1384

.

up

Γ(Src

f,

Dst

f

)

f

= (up

f

)

Γ for every reloid

f

.

Conjecture

1385

.

F

(

B

)

up

A

X

is not a filter for some filter

X ∈

F

Γ(

A, B

)

for some sets

A

,

B

.

Remark

1386

.

About this conjecture see also:

http://goo.gl/DHyuuU

http://goo.gl/4a6wY6

Lemma

1387

.

Let

A

,

B

be sets. The following are mutually inverse order

isomorphisms between

F

Γ(

A, B

) and

FCD

(

A, B

):

1

.

A 7→

d

FCD

up

A

;

2

.

f

7→

up

Γ(

A,B

)

f

.

Proof.

Let’s prove that up

Γ(

A,B

)

f

is a filter for every funcoid

f

. We need to

prove that

P

Q

up

f

whenever

P

=

\

i

=0

,...,n

1

X

i

×

Y

i

X

i

×

B

and

Q

=

\

j

=0

,...,m

1

X

0

j

×

Y

0

j

X

0

j

×

B

.

This follows from

P

up

f

⇔ ∀

i

0

, . . . , n

1 :

h

f

i

X

i

Y

i

and likewise for

Q

,

so having

h

f

i

(

X

i

X

0

j

)

Y

i

Y

0

j

for every

i

= 0

, . . . , n

1 and

j

= 0

, . . . , m

1.

From this it follows

((

X

i

X

0

j

)

×

(

Y

i

Y

0

j

))

X

i

X

0

j

×

B

f