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 : X → Y, 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 : X → Y 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:
“One of the most highly valued functions of used parents these days is to be the villains of their children’s lives, the people the child blames for any shortcomings or disappointments. But if your identity comes from your parents’ failings, then you remain forever a member of the child generation, stuck and unable to move on to an adulthood in which you identify yourself in terms of what you do, not what has been done to you.”
—Frank Pittman (20th century)