background image

2.1. ORDER THEORY

16

Proposition

24

.

There exist no more than one least element and no more

than one greatest element (for a given poset).

Proof.

By antisymmetry.

Definition

25

.

The

dual

order for

v

is

w

.

Obvious

26

.

Dual of a partial order is a partial order.

Definition

27

.

The

dual

poset for a poset (

A,

v

) is the poset (

A,

w

).

I will denote dual of a poset

A

as (dual

A

) and dual of an element

a

A

(that

is the same element in the dual poset) as (dual

a

).

Below we will sometimes use

duality

that is replacement of the partial order and

all related operations and relations with their duals. In other words, it is enough

to prove a theorem for an order

v

and the similar theorem for

w

follows by duality.

Definition

28

.

A subset

P

of a poset

A

is called

bounded above

if there exists

t

A

such that

x

P

:

t

w

x

.

Bounded below

is defined dually.

2.1.1.1.

Intersecting and joining elements.

Let

A

be a poset.

Definition

29

.

Call elements

a

and

b

of

A

intersecting

, denoted

a

6

b

, when

there exists a non-least element

c

such that

c

v

a

c

v

b

.

Definition

30

.

a

b

def

=

¬

(

a

6

b

).

Obvious

31

.

a

0

6

b

0

a

1

w

a

0

b

1

w

b

0

a

1

6

b

1

.

Definition

32

.

I call elements

a

and

b

of

A

joining

and denote

a

b

when

there is no a non-greatest element

c

such that

c

w

a

c

w

b

.

Definition

33

.

a

6≡

b

def

=

¬

(

a

b

).

Obvious

34

.

Intersecting is the dual of non-joining.

Obvious

35

.

a

0

b

0

a

1

w

a

0

b

1

w

b

0

a

1

b

1

.

2.1.2. Linear order.

Definition

36

.

A poset

A

is called

linearly ordered set

(or what is the same,

totally ordered set

) if

a

w

b

b

w

a

for every

a, b

A

.

Example

37

.

The set of real numbers with the customary order is a linearly

ordered set.

Definition

38

.

A set

X

P

A

where

A

is a poset is called

chain

if

A

restricted

to

X

is a total order.

2.1.3. Meets and joins.

Let

A

be a poset.

Definition

39

.

Given a set

X

P

A

the

least element

(also called

minimum

and denoted min

X

) of

X

us such

a

X

that

x

X

:

a

v

x

.

Least element does not necessarily exists. But if it exists:

Proposition

40

.

For a given

X

P

A

there exist no more than one least

element.

Proof.

It follows from anti-symmetry.

Greatest element

is the dual of least element:

Definition

41

.

Given a set

X

P

A

the

greatest element

(also called

maxi-

mum

and denoted max

X

) of

X

us such

a

X

that

x

X

:

a

w

x

.