Order Theory 171

Proof. Let f (n) = sup

m≤n

f

m

(n). Thus, on input n, the value of f (n) is at least as big as

f

m

(n), for the finitely many f

m

with m ≤ n. It follows that for any particular fixed m,we

have f

m

(n) ≤ f (n) for all n ≥ m.Sof

m

≤

∗

f for every individual m, as claimed.

I would like to emphasize how strange and mind expanding this property is. Theorem 130

shows that every countable family in the eventual domination order is bounded. This is a

property that is not shared by many of the other natural orders with which you might be

familiar. For example, the natural orders on N, Q, and R do not have this property, since

we can easily find unbounded countable sets in these orders. What theorem 130 shows, in

contrast, is that it is not possible to construct a ladder of functions

f

0

≤

∗

f

1

≤

∗

f

2

≤

∗

f

3

≤

∗

···

that climbs cofinally or even unboundedly in the eventual domination order. Every such

attempt, no matter how high in the order or how fast the functions grow, will still admit an

upper bound, a function f : N → N eventually dominating every function f

n

in the ladder.

It is truly incredible.

Mathematical Habits

Respect isomorphisms. Identify the relevant mathematical structure and incorporate

it into your isomorphism concept. Having an isomorphic copy of your structure is just

as good, for any mathematical question about that structure, as the original structure.

Exercises

14.1 Prove that if a partial order has two or more minimal elements, then it has no least element.

14.2 Write up a careful proof of theorem 124.

14.3 Provide a partial order with a unique maximal element but no largest element.

14.4 Prove as mentioned in the chapter that the order definitions used in the interdefinability of

a partial order with its strict order are inverses of each other. In particular, make a clear

statement about what this means. Conclude that the partial orders and strict partial orders are

in a one-to-one correspondence.

14.5 Prove the remarks made in the chapter about partial preorders, namely, that there are two

different partial preorders ≤

1

, ≤

2

with the same corresponding strict order <

1

= <

2

. Conclude

that with preorders, the ≤ relation has more information.

14.6 Prove that a partial order  is linear if and only if its corresponding strict order ≺ is linear.

14.7 Prove that the isomorphism relation on partial orders is an equivalence relation.