background image

2.1. ORDER THEORY

21

2.1.8. Boolean lattices.

Definition

84

.

A

boolean lattice

is a complemented distributive lattice.

The most important example of a boolean lattice is

P

A

where

A

is a set,

ordered by set inclusion.

Theorem

85

.

(

De Morgan

’s laws) For every elements

a

,

b

of a boolean lattice

1

.

a

t

b

= ¯

a

u

¯

b

;

2

.

a

u

b

= ¯

a

t

b

.

Proof.

We will prove only the first as the second is dual.

It is enough to prove that

a

t

b

is a complement of ¯

a

u

¯

b

. Really:

(

a

t

b

)

u

a

u

¯

b

)

v

a

u

a

u

¯

b

) = (

a

u

¯

a

)

u

¯

b

=

⊥ u

¯

b

=

;

(

a

t

b

)

t

a

u

¯

b

) = ((

a

t

b

)

t

¯

a

)

u

((

a

t

b

)

t

¯

b

)

w

(

a

t

¯

a

)

u

(

b

t

¯

b

) =

> u >

=

>

.

Thus (

a

t

b

)

u

a

u

¯

b

) =

and (

a

t

b

)

t

a

u

¯

b

) =

>

.

Definition

86

.

A complete lattice

A

is

join infinite distributive

when

x

u

d

S

=

d

h

x

ui

S

; a complete lattice

A

is

meet infinite distributive

when

x

t

d

S

=

d

h

x

ti

S

for all

x

A

and

S

P

A

.

Definition

87

.

Infinite distributive complete lattice

is a complete lattice which

is both join infinite distributive and meet infinite distributive.

Theorem

88

.

For every boolean lattice

A

,

x

A

and

S

P

A

we have:

1

.

d

h

x

ui

S

is defined and

x

u

d

S

=

d

h

x

ui

S

whenever

d

S

is defined.

2

.

d

h

x

ti

S

is defined and

x

t

d

S

=

d

h

x

ti

S

whenever

d

S

is defined.

Proof.

We will prove only the first, as the other is dual.

We need to prove that

x

u

d

S

is the least upper bound of

h

x

ui

S

.

That

x

u

d

S

is an upper bound of

h

x

ui

S

is obvious.

Now let

u

be any upper bound of

h

x

ui

S

, that is

x

u

y

v

u

for all

y

S

. Then

y

=

y

u

(

x

t

¯

x

) = (

y

u

x

)

t

(

y

u

¯

x

)

v

u

t

¯

x,

and so

d

S

v

u

t

¯

x

. Thus

x

u

l

S

v

x

u

(

u

t

¯

x

) = (

x

u

u

)

t

(

x

u

¯

x

) = (

x

u

u

)

t ⊥

=

x

u

u

v

u,

that is

x

u

d

S

is the least upper bound of

h

x

ui

S

.

Corollary

89

.

Every complete boolean lattice is both join infinite distributive

and meet infinite distributive.

Theorem

90

.

(infinite

De Morgan

’s laws) For every subset

S

of a complete

boolean lattice

1

.

d

S

=

d

x

S

¯

x

;

2

.

d

S

=

d

x

S

¯

x

.

Proof.

It’s enough to prove that

d

S

is a complement of

d

x

S

¯

x

(the second

follows from duality). Really, using the previous theorem:

l

S

t

l

x

S

¯

x

=

l

x

S

D

l

S

t

E

¯

x

=

l

d

S

t

¯

x

x

S

w

l

x

t

¯

x

x

S

=

>

;

l

S

u

l

x

S

¯

x

=

l

y

S

*

l

x

S

¯

x

u

+

y

=

l

d

x

S

¯

x

u

y

y

S

v

l

¯

y

u

y

y

S

=

.

So

d

S

t

d

x

S

¯

x

=

>

and

d

S

u

d

x

S

¯

x

=

.