background image

2.1. ORDER THEORY

17

Remark

42

.

Least and greatest elements of a set

X

is a trivial generalization

of the above defined least and greatest element for the entire poset.

Definition

43

.

A

minimal

element of a set

X

P

A

is such

a

A

that

@

x

X

:

a

A

x

.

A

maximal

element of a set

X

P

A

is such

a

A

that

@

x

X

:

a

@

x

.

Remark

44

.

Minimal element is not the same as minimum, and maximal

element is not the same as maximum.

Obvious

45

.

1

. The least element (if it exists) is a minimal element.

2

. The greatest element (if it exists) is a maximal element.

Exercise

46

.

Show that there may be more than one minimal and more than

one maximal element for some poset.

Definition

47

.

Upper bounds

of a set

X

is the set

n

y

A

x

X

:

y

w

x

o

.

The dual notion:

Definition

48

.

Lower bounds

of a set

X

is the set

n

y

A

x

X

:

y

v

x

o

.

Definition

49

.

Join

d

X

(also called

supremum

and denoted “sup

X

”) of a

set

X

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

Definition

50

.

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 also denote

d

i

X

f

(

i

) =

d

n

f

(

i

)

x

X

o

and

d

i

X

f

(

i

) =

d

n

f

(

i

)

x

X

o

.

We will write

b

=

d

X

when

b

A

is the join of

X

or say that

d

X

does not

exist if there are no such

b

A

. (And dually for meets.)

Exercise

51

.

Provide an example of

d

X /

X

for some set

X

on some poset.

Proposition

52

.

1

. If

b

is the greatest element of

X

then

d

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

53

.

Binary joins and meets

are defined by the formulas

x

t

y

=

l

{

x, y

}

and

x

t

y

=

l

{

x, y

}

.

Obvious

54

.

t

and

u

are symmetric operations (whenever these are defined

for given

x

and

y

).

Theorem

55

.

1

. If

d

X

exists then

y

w

d

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

d

X

y

is an upper bound for

X

⇔ ∀

x

X

:

y

w

x

.

Corollary

56

.

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

.

I will denote meets and joins for a specific poset

A

as

d

A

,

d

A

,

u

A

,

t

A

.