background image

2.1. ORDER THEORY

21

2

.

x

v

f

f

x

since

f

x

v

f

x

;

f

f

y

v

y

since

f

y

v

f

y

.

1

Let

a, b

A

and

a

v

b

. Then

a

v

b

v

f

f

b

. So by definition

f

a

v

f

b

that is

f

is monotone. Analogously

f

is monotone.

.

f

x

v

y

f

f

x

v

f

y

x

v

f

y

. The other direction is analogous.

Theorem

109

.

1

.

f

f

f

=

f

.

2

.

f

f

f

=

f

.

Proof.

1

Let

x

A

. We have

x

v

f

f

x

; consequently

f

x

v

f

f

f

x

. On the

other hand,

f

f

f

x

v

f

x

. So

f

f

f

x

=

f

x

.

2

Similar.

Definition

110

.

A function

f

is called idempotent iff

f

(

f

(

X

)) =

f

(

X

) for

every argument

X

.

Proposition

111

.

f

f

and

f

f

are idempotent.

Proof.

f

f

is idempotent because

f

f

f

f

y

=

f

f

y

.

f

f

is similar.

Theorem

112

.

Each of two adjoints is uniquely determined by the other.

Proof.

Let

p

and

q

be both upper adjoints of

f

. We have for all

x

A

and

y

B

:

x

v

p

(

y

)

f

(

x

)

v

y

x

v

q

(

y

)

.

For

x

=

p

(

y

) we obtain

p

(

y

)

v

q

(

y

) and for

x

=

q

(

y

) we obtain

q

(

y

)

v

p

(

y

). So

q

(

y

) =

p

(

y

).

Theorem

113

.

Let

f

be a function from a poset

A

to a poset

B

.

1

. Both:

(a) If

f

is monotone and

g

(

b

) = max

n

x

A

f x

v

b

o

is defined for every

b

B

then

g

is the upper adjoint of

f

.

(b) If

g

:

B

A

is the upper adjoint of

f

then

g

(

b

) = max

n

x

A

f x

v

b

o

for

every

b

B

.

2

. Both:

(a) If

f

is monotone and

g

(

b

) = min

n

x

A

f x

w

b

o

is defined for every

b

B

then

g

is the lower adjoint of

f

.

(b) If

g

:

B

A

is the lower adjoint of

f

then

g

(

b

) = min

n

x

A

f x

w

b

o

for

every

b

B

.

Proof.

We will prove only the first as the second is its dual.

1

a

Let

g

(

b

) = max

n

x

A

f x

v

b

o

for every

b

B

. Then

x

v

gy

x

v

max

x

A

f x

v

y

f x

v

y

(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

.