we also write [a, b] for {x : b x a] when 6 a. A connecting set from a
to b in M is a finite sequence (ao, a i , . . . , an) such that a = ao, 6 = an, and
for each r n, ar and ar+i are comparable (either ar ar+i or ar+i a
A path from a to b is a set of the form Ao U Ai U At U ... U A
_i where
for some connecting set ao, ai, 02,..., an from a to 6, each Ar is a maximal
chain in [a
+i], and for distinct r,s, the only non-empty intersections
between lr and A$ are given by ^4r H -Ar+i = {ar+i}«
After these preliminaries we can now define what it means for a Dedekind-
complete partial order to be cycle-free. We say that (M, ) is a cycle-free
partial order if for every a and b in M there is a unique path in M from
a to 6. More generally, for any partial order (M, ), we say that it is a
cycle-free partial order if its Dedekind-completion (M
, ) is.
The fact that we have to pass to the completion of M in order to tell
whether or not it is a CFPO may seem rather unsatisfactory, but in our
view this gives the most workable and coherent definition, and from the
rather striking examples of CFPOs presented in this paper, most of which
are described very much in terms of the relationship between M and
the approach seems justified.
In [1] some discussion is given of 'acyclic' or 'cycle-free' partial orders.
An alternative definition is proposed, and it is suggested that the following
are desiderata for any such notion:
(1) subsets of acyclic partial orders should be acyclic;
(2) semilinear orders (both upper and lower) should be acyclic;
(3) the diagram representing such an order should be 'tree-like';
(4) the notion should be first-order expressible;
(5) the Dedekind-MacNeille completion of an acyclic partial order should
be acyclic.
Now it will be seen that some at least of these requirements are indeed
met by the notion we have introduced. Namely (5) precisely corresponds
to the way it has been defined. The facts that (2) and (3) apply to our
definition will be amply illustrated throughout the paper. Moreover it is
possible for us to demonstrate the truth of (1) as well, though it is perhaps
not immediately obvious. Undoubtedly it is requirement (4) which causes
the most trouble.
Now from the definition of CFPO given it is clear that any such partial
order must be connected, meaning that there is a path in the partial order
between any two points. It is hardly surprising that this prevents the notion
being first-order expressible. If however we relax this condition, and instead
(just temporarily) say that (M, ) is a: (not necessarily connected) CFPO
if for any two points there is at most one path between them, we obtain the
class of partial orderings which are disjoint unions of connected CFPOs
(and with no comparabilities between points in different components). In
[27] it is shown that this class is first-order axiomatizable, and this is
really the best that one can hope for. Moreover, an axiomatization using
Previous Page Next Page