background image

2. If

a

u

b

exists then

y

v

a

u

b

,

y

v

a

^

y

v

b

.

2.1.4 Semilattices

Denition 2.41.

1. A

join-semilattice

is a poset

A

such that

a

t

b

is dened for every

a; b

2

A

.

2. A

meet-semilattice

is a poset

A

such that

a

u

b

is dened for every

a; b

2

A

.

Theorem 2.42.

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 rst 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

2

A

.

Taking into account the denition 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

2

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

a

/

b

i

a

u

b

is non-least, for every elements

a

,

b

of a meet-semilattice.

Obvious 2.44.

a

b

if

a

t

b

is the greatest element, for every elements

a

,

b

of a join-semilattice.

2.1.5 Lattices and complete lattices

Denition 2.45.

A

bounded

poset is a poset having both least and greatest elements.

Denition 2.46.

Lattice

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

Denition 2.47.

A

complete lattice

is a poset

A

such that for every

X

2

P

A

both

F

X

and

d

X

exist.

Obvious 2.48.

Every complete lattice is a lattice.

Proposition 2.49.

Every complete lattice is a bounded poset.

Proof.

F

;

is the least and

d

;

is the greatest element.

Theorem 2.50.

Let

A

be a poset.

1. If

F

X

is dened for every

X

2

P

A

, then

A

is a complete lattice.

2. If

d

X

is dened for every

X

2

P

A

, then

A

is a complete lattice.

Proof.

See [

26

or any lattice theory reference.

Obvious 2.51.

If

X

Y

for some

X ; Y

2

P

A

where

A

is a complete lattice, then

1.

F

X

v

F

Y

;

2.

d

X

w

d

Y

.

Proposition 2.52.

If

S

2

PP

A

then for every complete lattice

A

1.

F S

S

=

F

f

F

X

j

X

2

S

g

;

2.

d

S

S

=

d

f

d

X

j

X

2

S

g

.

20

Common knowledge, part 1