background image

2.1. ORDER THEORY

14

Definition

41

.

Upper bounds

of a set

X

is the set

n

y

A

x

X

:

y

w

x

o

.

The dual notion:

Definition

42

.

Lower bounds

of a set

X

is the set

n

y

A

x

X

:

y

v

x

o

.

Definition

43

.

Join

F

X

(also called

supremum

and denoted “sup

X

”) of a

set

X

is the least element of its upper bounds (if it exists).

Definition

44

.

Meet

d

X

(also called

infimum

and denoted “inf

X

”) of a set

X

is the greatest element of its lower bounds (if it exists).

We will write

b

=

F

X

when

b

A

is the join of

X

or say that

F

X

does not

exist if there are no such

b

A

. (And dually for meets.)

Exercise

45

.

Provide an example of

F

X /

X

for some set

X

on some poset.

I will denote meets and joins for a specific poset

A

as

d

A

and

F

A

.

Proposition

46

.

1

. If

b

is the greatest element of

X

then

F

X

=

b

.

2

. If

b

is the least element of

X

then

d

X

=

b

.

Proof.

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

Let

b

be the greatest element of

X

. Then upper bounds of

X

are

n

y

A

y

w

b

o

.

Obviously

b

is the least element of this set, that is the join.

Definition

47

.

Binary joins and meets

are defined by the formulas

x

t

y

=

G

{

x, y

}

and

x

t

y

=

l

{

x, y

}

.

Obvious

48

.

t

and

u

are symmetric operations (whenever these are defined

for given

x

and

y

).

Theorem

49

.

1

. If

F

X

exists then

y

w

F

X

⇔ ∀

x

X

:

y

w

x

.

2

. If

d

X

exists then

y

v

d

X

⇔ ∀

x

X

:

y

v

x

.

Proof.

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

y

w

F

X

y

is an upper bound for

X

⇔ ∀

x

X

:

y

w

x

.

Corollary

50

.

1

. If

a

t

b

exists then

y

w

a

t

b

y

w

a

y

w

b

.

2

. If

a

u

b

exists then

y

v

a

u

b

y

v

a

y

v

b

.

2.1.4. Semilattices.

Definition

51

.

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

52

.

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

)