background image

2.1. ORDER THEORY

18

2.1.4. Semilattices.

Definition

57

.

1

. A

join-semilattice

is a poset

A

such that

a

t

b

is defined for every

a, b

A

.

2

. A

meet-semilattice

is a poset

A

such that

a

u

b

is defined for every

a, b

A

.

Theorem

58

.

1

. The operation

t

is associative for any join-semilattice.

2

. The operation

u

is associative for any meet-semilattice.

Proof.

I will prove only the first as the second follows by duality.

We need to prove (

a

t

b

)

t

c

=

a

t

(

b

t

c

) for every

a, b, c

A

.

Taking into account the definition of join, it is enough to prove that

x

w

(

a

t

b

)

t

c

x

w

a

t

(

b

t

c

)

for every

x

A

. Really, this follows from the chain of equivalences:

x

w

(

a

t

b

)

t

c

x

w

a

t

b

x

w

c

x

w

a

x

w

b

x

w

c

x

w

a

x

w

b

t

c

x

w

a

t

(

b

t

c

)

.

Obvious

59

.

a

6

b

iff

a

u

b

is non-least, for every elements

a

,

b

of a meet-

semilattice.

Obvious

60

.

a

b

iff

a

t

b

is the greatest element, for every elements

a

,

b

of

a join-semilattice.

2.1.5. Lattices and complete lattices.

Definition

61

.

A

bounded

poset is a poset having both least and greatest

elements.

Definition

62

.

Lattice

is a poset which is both join-semilattice and meet-

semilattice.

Definition

63

.

A

complete lattice

is a poset

A

such that for every

X

P

A

both

d

X

and

d

X

exist.

Obvious

64

.

Every complete lattice is a lattice.

Proposition

65

.

Every complete lattice is a bounded poset.

Proof.

d

is the least and

d

is the greatest element.

Theorem

66

.

Let

A

be a poset.

1

. If

d

X

is defined for every

X

P

A

, then

A

is a complete lattice.

2

. If

d

X

is defined for every

X

P

A

, then

A

is a complete lattice.

Proof.

See [

27

or any lattice theory reference.

Obvious

67

.

If

X

Y

for some

X, Y

P

A

where

A

is a complete lattice,

then

1

.

d

X

v

d

Y

;

2

.

d

X

w

d

Y

.

Proposition

68

.

If

S

PP

A

then for every complete lattice

A