background image

2.1. ORDER THEORY

20

. Let

A

be an atomic boolean lattice. Let

a

A

. Suppose

b

=

F

atoms

a

@

a

. If

x

atoms(

a

\

b

) then

x

v

a

\

b

and so

x

v

a

and hence

x

v

b

. But we

have

x

=

x

u

b

v

(

a

\

b

)

u

b

=

what contradicts to our supposition.

2.1.11. Kuratowski’s lemma.

Theorem

99

.

(Kuratowski lemma) Any chain in a poset is contained in a

maximal chain (if we order chains by inclusion).

I will skip the proof of Kuratowski lemma as this proof can be found in any set

theory or order theory reference.

2.1.12. Homomorphisms of posets and lattices.

Definition

100

.

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

101

.

Order embedding

is a monotone injective function whose in-

verse is also monotone.

Definition

102

.

Order isomorphism

is a surjective order embedding.

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

meets, etc.

Definition

103

.

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

104

.

1

. Join semilattice homomorphisms are monotone.

2

. Meet semilattice homomorphisms are monotone.

Definition

105

.

A

lattice homomorphism

is a function from a lattice to a

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

morphism.

Definition

106

.

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

F

S

=

F

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

107

.

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

108

.

A pair (

f

;

f

) of functions

f

:

A

B

and

f

:

B

A

is a

Galois connection iff both of the following:

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.

.