background image

2.1. ORDER THEORY

26

(because

f

is monotone) and

x

v

gy

x

v

max

x

A

f x

v

y

f x

v

y.

So

f x

v

y

x

v

gy

that is

f

is the lower adjoint of

g

.

1

b

We have

g

(

b

) = max

x

A

f x

v

b

f gb

v

b

∧ ∀

x

A

: (

f x

v

b

x

v

gb

)

.

what is true by properties of adjoints.

Theorem

132

.

Let

f

be a function from a poset

A

to a poset

B

.

1

. If

f

is an upper adjoint,

f

preserves all existing infima in

A

.

2

. If

A

is a complete lattice and

f

preserves all infima, then

f

is an upper

adjoint of a function

B

A

.

3

. If

f

is a lower adjoint,

f

preserves all existing suprema in

A

.

4

. If

A

is a complete lattice and

f

preserves all suprema, then

f

is a lower

adjoint of a function

B

A

.

Proof.

We will prove only first two items because the rest items are similar.

1

Let

S

P

A

and

d

S

exists.

f

d

S

is a lower bound for

h

f

i

S

because

f

is order-preserving. If

a

is a lower bound for

h

f

i

S

then

x

S

:

a

v

f x

that

is

x

S

:

ga

v

x

where

g

is the lower adjoint of

f

. Thus

ga

v

d

S

and hence

f

d

S

w

a

. So

f

d

S

is the greatest lower bound for

h

f

i

S

.

2

Let

A

be a complete lattice and

f

preserves all infima. Let

g

(

a

) =

l

x

A

f x

w

a

.

Since

f

preserves infima, we have

f

(

g

(

a

)) =

l

f

(

x

)

x

A

, f x

w

a

w

a.

g

(

f

(

b

)) =

d

n

x

A

f x

w

f b

o

v

b

.

Obviously

f

is monotone and thus

g

is also monotone.

So

f

is the upper adjoint of

g

.

Corollary

133

.

Let

f

be a function from a complete lattice

A

to a poset

B

.

Then:

1

.

f

is an upper adjoint of a function

B

A

iff

f

preserves all infima in

A

.

2

.

f

is a lower adjoint of a function

B

A

iff

f

preserves all suprema in

A

.

2.1.13.1.

Order and composition of Galois connections.

Following [

32

we will

denote the set of Galois connection between posets

A

and

B

as

A

B

.

Definition

134

.

I will order Galois connections by the formula:

f

v

g

f

v

g

(where

f

v

g

⇔ ∀

x

A

:

f

x

v

g

x

).

Obvious

135

.

Galois connections

A

B

between two given posets form a poset.

Proposition

136

.

f

v

g

f

w

g

.