Cyclic Order - Monotone Functions

Monotone Functions

The "cyclic order = arranging in a circle" idea works because any subset of a cycle is itself a cycle. In order to use this idea to impose cyclic orders on sets that are not actually subsets of the unit circle in the plane, it is necessary to consider functions between sets.

A function between two cyclically ordered sets, f : XY, is called a monotonic function or a homomorphism if it pulls back the ordering on Y: whenever, one has . Equivalently, f is monotone if whenever and f(a), f(b), and f(c) are all distinct, then . A typical example of a monotone function is the following function on the cycle with 6 elements:

f(0) = f(1) = 4,
f(2) = f(3) = 0,
f(4) = f(5) = 1.

A function is called an embedding if it is both monotone and injective. Equivalently, an embedding is a function that pushes forward the ordering on X: whenever, one has . As an important example, if X is a subset of a cyclically ordered set Y, and X is given its natural ordering, then the inclusion map i : XY is an embedding.

Generally, an injective function f from an unordered set X to a cycle Y induces a unique cyclic order on X that makes f an embedding.

Read more about this topic:  Cyclic Order

Famous quotes containing the word functions:

    Those things which now most engage the attention of men, as politics and the daily routine, are, it is true, vital functions of human society, but should be unconsciously performed, like the corresponding functions of the physical body.
    Henry David Thoreau (1817–1862)