background image

Denition 2.29.

A

minimal

element of a set

X

2

P

A

is such

a

2

A

that

@

x

2

X

: (

a

w

x

^

x

=

/

a

)

.

A

maximal

element of a set

X

2

P

A

is such

a

2

A

that

@

x

2

X

: (

a

v

x

^

x

=

/

a

)

.

Remark 2.30.

Minimal element is not the same as minimum, and maximal element is not the

same as maximum.

Obvious 2.31.

1. The least element (if it exists) is a minimal element.
2. The greatest element (if it exists) is a maximal element.

Exercise 2.1.

Show that there may be more than one minimal and more than one maximal element for some

poset.

Denition 2.32.

Upper bounds

of a set

X

is the set

f

y

2

A

j 8

x

2

X

:

y

w

x

g

.

The dual notion:

Denition 2.33.

Lower bounds

of a set

X

is the set

f

y

2

A

j 8

x

2

X

:

y

v

x

g

.

Denition 2.34.

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

Denition 2.35.

Meet

d

X

(also called

inmum

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

2

A

is the join of

X

or say that

F

X

does not exist if there are

no such

b

2

A

. (And dually for meets.)

Exercise 2.2.

Provide an example of

F

X

2

/

X

for some set

X

on some poset.

I will denote meets and joins for a specic poset

A

as

d

A

and

F

A

.

Proposition 2.36.

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 rst as the second is dual.

Let

b

be the greatest element of

X

. Then upper bounds of

X

are

f

y

2

A

j

y

w

b

g

. Obviously

b

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

Denition 2.37.

Binary joins and meets

are dened by the formulas

x

t

y

=

G

f

x; y

g

and

x

u

y

=

l

f

x; y

g

:

Obvious 2.38.

t

and

u

are symmetric operations (whenever these are dened for given

x

and

y

).

Theorem 2.39.

1. If

F

X

exists then

y

w

F

X

, 8

x

2

X

:

y

w

x

.

2. If

d

X

exists then

y

v

d

X

, 8

x

2

X

:

y

v

x

.

Proof.

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

y

w

F

X

,

y

is an upper bound for

X

, 8

x

2

X

:

y

w

x

.

Corollary 2.40.

1. If

a

t

b

exists then

y

w

a

t

b

,

y

w

a

^

y

w

b

.

2.1 Order theory

19