background image

20. ALTERNATIVE REPRESENTATIONS OF BINARY RELATIONS

314

it becomes obvious.

Claim: Ψ

2

maps binary relations between

A

and

B

into pointfree funcoids be-

tween

P

A

and

P

B

.

Proof: We need to prove that

f

= (

P

A,

P

B,

h

f

i

,

f

1

) is a pointfree funcoids

that is

Y

6 h

f

i

X

X

6

f

1

Y

. Really, for every

X

T

A

,

Y

T

B

Y

6 h

f

i

X

Y

6 h

r

i

X

Y

6 h

r

i

X

X

6

r

1

Y

X

6

r

1

Y

X

6

f

1

Y.

Claim: Ψ

1

2

maps pointfree funcoids between

P

A

and

P

B

into binary relations

between

A

and

B

.

Proof: Suppose

f

pFCD

(

T

A,

T

B

) and prove that the relation defined by the

formula Ψ

1

2

exists. To prove it, it’s enough to show that

y

∈ h

f

i{

x

} ⇔

x

f

1

{

y

}

. Really,

y

∈ h

f

i{

x

} ⇔ {

y

} 6 h

f

i{

x

} ⇔ {

x

} 6

f

1

{

y

} ⇔

x

f

1

{

y

}

.

Claim: Ψ

3

maps pointfree funcoids between

P

A

and

P

B

into antitone Galois

connections between

P

A

and

P

B

.

Proof: Because Ψ

3

= Ψ

1

1

Ψ

1

2

.

Claim: Ψ

1

3

maps antitone Galois connections between

P

A

and

P

B

into pointfree

funcoids between

P

A

and

P

B

.

Proof: Because Ψ

1

3

= Ψ

2

Ψ

1

.

Claim: Ψ

2

and Ψ

1

2

are mutually inverse.

Proof: Let

r

0

P

(

A

×

B

) and

f

pFCD

(

T

A,

T

B

) corresponds to

r

0

by the

formula Ψ

2

; let

r

1

P

(

A

×

B

) corresponds to

f

by the formula Ψ

1

2

. Then

r

0

=

r

1

because

(

x, y

)

r

0

y

∈ h

r

0

i

{

x

} ⇔

y

∈ h

f

i{

x

} ⇔

(

x, y

)

r

1

.

Let now

f

0

pFCD

(

T

A,

T

B

) and

r

P

(

A

×

B

) corresponds to

f

0

by the

formula Ψ

1

2

; let

f

1

pFCD

(

T

A,

T

B

) corresponds to

r

by the formula Ψ

2

. Then

(

x, y

)

r

y

∈ h

f

0

i{

x

}

and

h

f

1

i

=

h

r

i

; thus

y

∈ h

f

1

i{

x

} ⇔

y

∈ h

r

i

{

x

} ⇔

(

x, y

)

r

y

∈ h

f

0

i{

x

}

.

So

h

f

0

i

=

h

f

1

i

. Similarly

f

1

0

=

f

1

1

.

Claim: Ψ

1

and Ψ

1

1

are mutually inverse.

Proof: Let

r

0

P

(

A

×

B

) and

f

T

A

T

B

corresponds to

r

0

by the formula Ψ

1

1

;

let

r

1

P

(

A

×

B

) corresponds to

f

by the formula Ψ

1

. Then

r

0

=

r

1

because

(

x, y

)

r

1

y

f

0

{

x

} ⇔

y

y

B

x r

0

y

x r

0

y.

Let now

f

0

T

A

T

B

and

r

P

(

A

×

B

) corresponds to

f

0

by the formula Ψ

1

;

let

f

1

T

A

T

B

corresponds to

r

by the formula Ψ

1

1

. Then

f

0

=

f

1

because

f

10

X

=

y

B

x

X

:

x r y

=

y

B

x

X

:

y

f

00

{

x

}

=

l

x

X

f

00

{

x

}

= (obvious

142

=

f

00

X.

Claim: Ψ

3

and Ψ

1

3

are mutually inverse.

Proof: Because Ψ

1

3

= Ψ

2

Ψ

1

and Ψ

3

= Ψ

1

1

Ψ

1

2

and that Ψ

1

2

is the inverse of

Ψ

2

and Ψ

1

3

is the inverse of Ψ

3

were proved above.

Now switch to the lower “triangle”: