nLab cyclic order

Redirected from "cyclic ordering".
Cyclic orders

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:

  • Cyclic irreflexivity: If R(x,y,z)R(x,y,z), then yzy \ne z.
  • Cyclic asymmetry: If R(x,y,z)R(x,y,z) and R(x,z,w)R(x,z,w), then ywy \ne w.
  • Cyclic transitivity: If R(x,y,z)R(x,y,z) and R(x,z,w)R(x,z,w), then R(x,y,w)R(x,y,w).
  • Cyclic comparison: If R(x,y,z)R(x,y,z), then for any ww, R(x,y,w)R(x,y,w) or R(x,w,z)R(x,w,z) or R(w,y,z)R(w,y,z).
  • Cyclic connectedness: If xyx \ne y, xzx \ne z, and yzy \ne z, then R(x,y,z)R(x,y,z) or R(x,z,y)R(x,z,y).

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

  • Cyclic trichotomy: For all x,y,zx, y, z, (x=yx = y or x=zx = z or y=zy = z) xor R(x,y,z)R(x,y,z) xor R(x,z,y)R(x,z,y).

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:

  • ff reflects the ternary relation RR, i.e. if R T(f(x),f(y),f(z))R_T(f(x),f(y),f(z)) then R S(x,y,z)R_S(x,y,z).
  • ff preserves the ternary relation RR for elements with pairwise distinct images, i.e. if R S(x,y,z)R_S(x,y,z) holds and f(x)f(x), f(y)f(y), and f(z)f(z) are pairwise distinct, then R T(f(x),f(y),f(z))R_T(f(x),f(y),f(z)).

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

Remarks

  • One would like the cycle category Λ\Lambda to be the category of finite inhabited cyclically ordered sets and monotone functions, just as the simplex category Δ\Delta is the category of finite inhabited linearly ordered sets and monotone functions. However, this seems to fail for the 00-cycle, which has a nontrivial loop and is therefore not terminal (unlike the cyclically ordered singleton, which is terminal).

References

Last revised on September 26, 2024 at 14:16:26. See the history of this page for a list of all contributions to it.