background image

2.1. ORDER THEORY

24

2.1.12. Homomorphisms of posets and lattices.

Definition

112

.

A

monotone

function (also called

order homomorphism

) from

a poset

A

to a poset

B

is such a function

f

that

x

v

y

f x

v

f y

for every

x, y

A

.

Definition

113

.

A

antitone

function (also called

antitone order homomor-

phism

) from a poset

A

to a poset

B

is such a function

f

that

x

v

y

f x

w

f y

for

every

x, y

A

.

Definition

114

.

Order embedding

is a function

f

from poset

A

to a poset

B

such that

x

v

y

f x

v

f y

for every

x, y

A

.

Proposition

115

.

Every order embedding is injective.

Proof.

f x

=

f y

implies

x

v

y

and

y

v

x

.

Obvious

116

.

Every order embedding is an order homomorphism.

Definition

117

.

Antitone order embedding

is a function

f

from poset

A

to a

poset

B

such that

x

v

y

f x

w

f y

for every

x, y

A

.

Obvious

118

.

Antitone order embedding is an order embedding between a

poset and a dual of (another) poset.

Definition

119

.

Order isomorphism

is a surjective order embedding.

Order isomorphism preserves properties of posets, such as order, joins and

meets, etc.

Definition

120

.

Antitone order isomorphism

is a surjective antitone order

embedding.

Definition

121

.

1

.

Join semilattice homomorphism

is a function

f

from a join semilattice

A

to a join semilattice

B

, such that

f

(

x

t

y

) =

f x

t

f y

for every

x, y

A

.

2

.

Meet semilattice homomorphism

is a function

f

from a meet semilattice

A

to a meet semilattice

B

, such that

f

(

x

u

y

) =

f x

u

f y

for every

x, y

A

.

Obvious

122

.

1

. Join semilattice homomorphisms are monotone.

2

. Meet semilattice homomorphisms are monotone.

Definition

123

.

A

lattice homomorphism

is a function from a lattice to a

lattice, which is both join semilattice homomorphism and meet semilattice homo-

morphism.

Definition

124

.

Complete lattice homomorphism

from a complete lattice

A

to a complete lattice

B

is a function f from

A

to

B

which preserves all meets and

joins, that is

f

d

S

=

d

h

f

i

S

and

f

d

S

=

d

h

f

i

S

for every

S

P

A

.

2.1.13. Galois connections.

See [

3

,

12

for more detailed treatment of Ga-

lois connections.

Definition

125

.

Let

A

and

B

be two posets. A

Galois connection

between

A

and

B

is a pair of functions

f

= (

f

, f

) with

f

:

A

B

and

f

:

B

A

such

that:

x

A

, y

B

: (

f

x

v

y

x

v

f

y

)

.

f

is called

the upper adjoint

of

f

and

f

is called

the lower adjoint

of

f

.

Theorem

126

.

A pair (

f

, f

) of functions

f

:

A

B

and

f

:

B

A

is a

Galois connection iff both of the following: