166 Chapter 14
Welcome back. Did you prove it or find a counterexample? Let us see what we can do.
b
0
b
1
b
2
b
3
b
4
b
5
b
6
b
7
b
8
b
9
b
10
b
11
b
12
b
13
b
14
b
15
a
Suppose we have a partial order ≤ on a set A with a unique
minimal element a. So there is nothing below a. But if a
is not least, then there must be some element b
0
that is not
above a. So they must be incomparable. But since a is the
unique minimal element, then b
0
is not minimal, so there
must be some b
1
< b
0
. And similarly, b
1
is not minimal,
and so there is b
2
< b
1
and so on. In this way, we are led to
construct an infinite chain descending from b
0
.
But now, two observations are in order. First, the picture
here simply is a counterexample! That is, if we have an infi-
nite descending chain and one more point on the side, and no
other points at all, then that single point is a unique minimal
element, but it is not a least element.
The second observation is that the construction method shows that in any finite partial
order, every unique minimal element must be a least element, since in a finite order the
descending chain part will have to stop at some point, producing another minimal element
other than a. These observations essentially prove the following theorem, asserting that the
answer to the question above is yes in finite orders but no if infinite orders are allowed.
Theorem 124. In any finite partial order, an element is a unique minimal element if and
only if it is least. Meanwhile, there are infinite partial orders having unique minimal
elements that are not least.
The reader will write a careful proof of this theorem in exercise 14.2.
14.3 Linear orders
Let us now introduce some more vocabulary for discussing other kinds of features in an
order. A linear order is a partial order ≤ with the linearity property, which means that for
any a and b, we have either a ≤ b or b ≤ a. For example, the usual order ≤ on the integers
or the rationals or the real numbers is a linear order. A strict order < is said to be linear if
a < b or b < a or a = b for any a and b. The reader will prove in the exercises that a partial
order is linear if and only if its corresponding strict order is linear.
The subset relation ⊆ is not generally linear, for example, since we can have sets A and
B with A "⊆ B and B "⊆ A. For example, if A is the set of prime numbers and B is the set of
even numbers, then neither A nor B is a subset of the other.
Theorem 125. Every infinite linear order has an infinite increasing sequence or an infinite
decreasing sequence.
Let us first prove the following useful lemma.