background image

4.

8

a; b

2

A

: (

a

@

b

) 9

c

2

A

n f

0

g

: (

c

a

^

c

v

b

))

.

Proof.

(1)

,

(3)

,

(4).

Proved above.

(2)

)

(4).

Let our semilattice be atomically separable. Let

a

@

b

. Then atoms

a

atoms

b

and

so there exists

c

2

atoms

b

such that

c

2

/

atoms

a

.

c

=

/ 0

and

c

v

b

, from which (taking into

account that

c

is an atom)

c

v

b

and

c

u

a

= 0

. So our semilattice conforms to the formula (4).

(4)

)

(2).

Let formula (4) hold. Then for any elements

a

@

b

there exists

c

=

/ 0

such that

c

v

b

and

c

u

a

= 0

. Because

A

is atomic there exists atom

d

v

c

.

d

2

atoms

b

and

d

2

/

atoms

a

. So

atoms

a

=

/

atoms

b

and atoms

a

atoms

b

. Consequently atoms

a

atoms

b

.

Theorem 3.22.

Any atomistic meet-semilattice with least element is separable.

Proof.

From the above.

3.2 Free Stars

Denition 3.23.

An

upper set

is such a set

F

2

P

Z

that

8

X

2

F ; Y

2

Z

: (

Y

w

X

)

Y

2

F

)

:

Denition 3.24.

Let

A

be a poset.

Free stars

on

A

are such

S

2

P

A

that the least element (if

it exists) is not in

S

and for every

X ; Y

2

A

8

Z

2

A

: (

Z

w

X

^

Z

w

Y

)

Z

2

S

)

,

X

2

S

_

Y

2

S:

Proposition 3.25.

S

2

P

A

where

A

is a poset is a free star i all of the following:

1. The least element (if it exists) is not in

S

.

2.

8

Z

2

A

: (

Z

w

X

^

Z

w

Y

)

Z

2

S

)

)

X

2

S

_

Y

2

S

for every

X ; Y

2

A

.

3.

S

is an upper set.

Proof.

)

.

(1) and (2) are obvious. Let prove that

S

is an upper set. Let

X

2

S

and

X

v

Y

2

A

. Then

X

2

S

_

X

2

S

and thus

8

Z

2

A

: (

Z

w

X

^

Z

w

X

)

Z

2

S

)

that is

8

Z

2

A

: (

Z

w

X

)

Z

2

S

)

,

and so

Y

2

S

.

(

.

We need to prove that

8

Z

2

A

: (

Z

w

X

^

Z

w

Y

)

Z

2

S

)

(

X

2

S

_

Y

2

S:

Let

X

2

S

_

Y

2

S

. Then

Z

w

X

^

Z

w

Y

)

Z

2

S

for every

Z

2

A

because

S

is an upper set.

Proposition 3.26.

Let

A

be a join-semilattice.

S

2

P

A

is a free star i all of the following:

1. The least element (if it exists) is not in

S

.

2.

X

t

Y

2

S

)

X

2

S

_

Y

2

S

for every

X ; Y

2

A

.

3.

S

is an upper set.

Proof.

)

.

We need to prove only

X

t

Y

2

S

)

X

2

S

_

Y

2

S

. Let

X

t

Y

2

S

. Because

S

is an upper

set, we have

8

Z

2

A

: (

Z

w

X

t

Y

)

Z

2

S

)

and thus

8

Z

2

A

: (

Z

w

X

^

Z

w

Y

)

Z

2

S

)

from

which we conclude

X

2

S

_

Y

2

S

.

(

.

We need to prove

8

Z

2

A

: (

Z

w

X

^

Z

w

Y

)

Z

2

S

)

(

X

2

S

_

Y

2

S

.

But it trivially follows from that

S

is an upper set.

36

More on order theory