CYCLE-FREE PARTIAL ORDERS 5

the domain of

MD

we take the family of all ideals of M, turn

MD

into

a partial order by using inclusion as the relation, and identify M with a

subset of

MD

via the map which sends x to

M-x

for each x G M'. It is

then fairly easy to verify that

MD

is a Dedekind-complete partial order

containing M, and is the minimal one in a natural sense made precise later.

The above construction of the Dedekind-MacNeille completion MD of

an arbitrary partial order M is a natural generalization of the construction

of the Dedekind-completion of a linear order. For in a linear order, an

ideal is precisely the same as a left Dedekind cut J such that if I is not

principal, then neither is the filter M — I. (The condition J = f\\JI

neatly sidesteps the usual problem over double representation of x £ M

in the completion, as either {y £ M : y x} or {y £ M : y ar}, -

the latter is the option preferred). We remark that it is equally possible to

define Dedekind-completeness, and to construct the Dedekind-completion,

by use of filters, as is done in [29] for instance. Use of ideals has the slight

advantage that the ordering is inclusion rather than reverse inclusion.

In the example given in figure 1.4 we can now identify 5 ideals, namely

{«o},{a2},{ao,ai,a2},{ao,a3,a2}, - which are all principal, and {0,0,0,2},

which is not. This illustrates that the completion of this partially ordered

set is precisely equal to {00,01,02,03,6}, as given in figure 1.2.

By contrast we remark that the '6-crown' illustrated in figure 1.5 in

which oo 01,05, 02 01,03, 04 03,05 are the only non-trivial compa-

rabilities is already Dedekind-complete. For instance {00,02} is no longer

an ideal in this case, since A V{aofl2} = A{ a i) = { a o,oi,a

2

} / {ao,a2}.

This gives an explanation as to why we might want to count the '4-crown'

of figure 1.4 as a CFPO, but not the 6-crown, (which was initially a stum-

bling block in this work).

Now let us work with a Dedekind-complete partial order (M, ). We

write [a, b] for an interval {x : a x 6} and since we do not always wish

to be specific about which of two comparable elements a and 6 is the greater

o2

Fig. 1.5.