background image

2. Similar.

Denition 2.100.

A function

f

is called

idempotent

i

f

(

f

(

X

)) =

f

(

X

)

for every argument

X

.

Proposition 2.101.

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 2.102.

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

2

A

and

y

2

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 2.103.

Let

f

be a function from a poset

A

to a poset

B

.

1. Both:

1. If

f

is monotone and

g

(

b

) =

max

f

x

2

A

j

fx

v

b

g

is dened for every

b

2

B

then

g

is the upper adjoint of

f

.

2. If

g

:

B

!

A

is the upper adjoint of

f

then

g

(

b

) =

max

f

x

2

A

j

fx

v

b

g

for every

b

2

B

.

2. Both:

1. If

f

is monotone and

g

(

b

) =

min

f

x

2

A

j

fx

w

b

g

is dened for every

b

2

B

then

g

is

the lower adjoint of

f

.

2. If

g

:

B

!

A

is the lower adjoint of

f

then

g

(

b

) =

min

f

x

2

A

j

fx

w

b

g

for every

b

2

B

.

Proof.

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

1. Let

g

(

b

) =

max

f

x

2

A

j

fx

v

b

g

for every

b

2

B

. Then

x

v

gy

,

x

v

max

f

x

2

A

j

fx

v

y

g )

fx

v

y

(because

f

is monotone) and

x

v

gy

,

x

v

max

f

x

2

A

j

fx

v

y

g (

fx

v

y:

So

fx

v

y

,

x

v

gy

that is

f

is the lower adjoint of

g

.

2. We have

g

(

b

) =

max

f

x

2

A

j

fx

v

b

g ,

fgb

v

b

^ 8

x

2

A

: (

fx

v

b

)

x

v

gb

)

what is true by properties of adjoints.

Theorem 2.104.

Let

f

be a function from a poset

A

to a poset

B

.

1. If

f

is an upper adjoint,

f

preserves all existing inma in

A

.

2. If

A

is a complete lattice and

f

preserves all inma, 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 rst two items because the rest items are similar.

1. Let

S

2

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

8

x

2

S

:

a

v

fx

that is

8

x

2

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

.

26

Common knowledge, part 1