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.
Previous Page Next Page