nLab
cyclic order

Cyclic orders

Idea

If a linear order is a way of arranging the elements of a set ‘on a line’ (with a direction), then a cyclic order is a way of arranging them ‘on a circle’ (with a chosen direction, say clockwise or counterclockwise).

Unlike a linear order (and most other things called ‘order’) which are defined as a sort of binary relation, a cyclic order is defined as a sort of ternary relation, since on a circle we can’t say “xx comes before (or after) yy” only “xx, yy, and zz come in clockwise (or counterclockwise) order.”

Definition

A cyclic relation on a set SS is a ternary relation RR on SS such that, if R(x,y,z)R(x,y,z) for any elements x,y,zx, y, z of SS, then R(y,z,x)R(y,z,x) (and hence also R(z,x,y)R(z,x,y)).

Then a cyclic order on SS is a cyclic relation RR that satisfies ternary versions of the properties of a linear order:

Actually, none of these order axioms (except for comparison) is really complete as stated; any cyclic permutation of the axiom should also be assumed. However, these permutations all follow automatically for a cyclic relation.

Note that for a constructive version, the set SS needs to be already equipped with a (tight) apartness relation for the connectedness axiom to make sense; unlike with a linear order, we can't recover the apartness relation from the cyclic order. For a similar reason, it's difficult to state antisymmetry correctly for a nonstrict (like a total order) version of a cyclic order.

As with a linear order, not all of these axioms are needed. In particular, using excluded middle, it's enough if a cyclic relation is transitive and satisfies

Monotone functions

An injective function f:STf:S\to T between cyclically ordered sets is strictly monotone if it preserves the ternary relation RR, i.e. if R S(x,y,z)R_S(x,y,z) implies R T(f(x),f(y),f(z))R_T(f(x),f(y),f(z)). This is the cyclic counterpart of a strictly monotone function between linear orders (one which preserves the relation <\lt). As in that case, irreflexivity then implies that ff is injective as long as SS has at least three distinct elements; but in general, this should be stated explicitly (and interpreted in the strongest sense for constructive mathematics).

We say that ff is merely monotone if it satisfies (either of) the following equivalent conditions:

This is the cyclic counterpart of a monotone function between linear orders (one which reflects the relation <\lt).

Remarks