4 EXTENDED INTRODUCTION

Fig. 1.4.

this approach let us consider the partial order shown in figure 1.2. It seems

incontrovertible that we should require any subset of a CFPO automat-

ically to be a CFPO, and once we are prepared to admit this, it follows

that the subset {00,01,02,03} should be a CFPO. Here though, if we

draw the resulting partial order, that is without the intermediate point 6,

as shown in figure 1.4, it is superficially much less evident that the partial

order should be counted as a CFPO. For {ao, 01,02,03,6} one can at least

fall back on the argument that the path from 00 to 02 by way of ai was

not the shortest, and should have gone via 6, thereby providing a plausible

reason for regarding it as cycle-free.

Since we take the view that any subset of a CFPO should also be

one, it follows that we must count the partial order shown in figure 1.4 as

such. To explain this coherently, we really have to show how to pass to an

appropriate larger partial order containing it, and this is done in general

by taking the Dedekind-MacNeille completion [19].

The version of the Dedekind-MacNeille completion adopted here is as

follows. For any subset X of a partially ordered set (M, ) let us write V ^

and f\ X for the sets of upper and lower bounds of X in M respectively.

We then say that / C M is a (Dedekind) ideal if J ^ 0 and V ^ ^ 0

and I = f\\J I. Notice that this automatically implies one of the usually

characteristic properties of ideals, namely downward closure: y x E I =

y E I (since any set of the form /\ Y fulfils this). The dual notion is that of

a Dedekind filter. F C M is a filter if F ^ 0 and /\ F ^ 0, and F = V A

F-

The intuition is that the ideals are the subsets of M which 'ought to

have' least upper bounds in M if M is to be regarded as complete. Writing

M-x

for the principal ideal {y G M : y x} (= f\{x}) we thus say that

M is Dedekind-complete if every Dedekind ideal has the form M-x for

some x E M. (We also write Mx for {y G M : y x} and Mx for

{yEM:y x}).

The definition of ideal also provides a natural method for constructing

a minimal Dedekind-complete partially ordered set

MD

extending M. For