Order Theory 167

Lemma 125.1. If a partial order has no infinite decreasing sequence, then every nonmax-

imal element a has at least one successor, an element that is minimal amongst the elements

above a.

Proof. If a is not maximal, then there is an element b

0

above a. If this is not a successor

of a, then there must be some b

1

< b

0

, with b

1

still above a.Ifb

1

is not a successor, then

we can find b

2

< b

1

, but still above a. Since there is no decreasing sequence in the order,

this process must terminate at some stage, at which point we will have found a successor

of the point a, as desired.

Proof of theorem 125. Assume that ≤ is a linear order on an infinite set A, and that there

is no infinite descending sequence (for otherwise we are done). It follows that there must

be a least element a

0

in the order, for otherwise we could build a descending sequence by

choosing any b

0

, and then any b

1

< b

0

, and any b

2

< b

1

and so on, using the assumption

that none of these is minimal. By lemma 125.1, the element a

0

has a successor element a

1

.

This cannot be a maximal element, since a

0

was least and a

1

was next, and so by linearity

all the other infinitely many elements of A are above a

1

. So by the lemma again, a

1

has a

successor element, which we may call a

2

. This also is not maximal, and so has a successor

a

3

and so on. At each stage, we have finitely many points at the bottom of the order, but

since the order is infinite, the point a

n

is not maximal and so has a successor a

n+1

by the

lemma. So we have built an increasing sequence. Thus, every infinite linear order must

have either an infinite decreasing sequence or an infinite increasing sequence.

In exercise 14.9 the reader will consider whether we really need the linearity assumption

in theorem 125. Does every infinite partial order have an infinite increasing or infinite

decreasing sequence?

14.4 Isomorphisms of orders

We shall consider next an interesting order arising from the finite sets of natural numbers.

Let P

fin

(N) be the collection of all finite subsets of N, ordered by the inclusion relation ⊆.

This is a partial order. Can you draw a picture of it? Notice that the empty set ∅ is a least

element in this order, and then all the singleton sets {n} are minimal above the empty set,

with the doubleton sets {n, m} minimal above {n} and {m}, and so on. All the finite sets of

natural numbers arise in this order.

Let us use this order to illustrate the isomorphism concept in mathematics.

Definition 126. Two order relations

A, ≤

A

!

and

B, ≤

B

!

are isomorphic if there is a one-

to-one correspondence between A and B,anisomorphism, which is a bijective function

π : A → B that copies the ≤

A

structure of A to the ≤

B

structure of B, in the sense that

x ≤

A

y if and only if π(x) ≤

B

π(y).