background image

2.1. ORDER THEORY

25

1

.

f

and

f

are monotone.

2

.

x

v

f

f

x

and

f

f

y

v

y

for every

x

A

and

y

B

.

Proof.

.

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

127

.

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

128

.

A function

f

is called

idempotent

iff

f

(

f

(

X

)) =

f

(

X

) for

every argument

X

.

Proposition

129

.

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

130

.

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

131

.

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