background image

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

1379

.

Formulate the duals of these sets.

Proposition

1380

.

Γ(

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

1396

(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

1381

.

up

Γ(Src

f,

Dst

f

)

f

= (up

f

)

Γ for every reloid

f

.

Conjecture

1382

.

F

(

B

)

up

A

X

is not a filter for some filter

X ∈

F

Γ(

A, B

)

for some sets

A

,

B

.

Remark

1383

.

About this conjecture see also:

http://goo.gl/DHyuuU

http://goo.gl/4a6wY6

Lemma

1384

.

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