Let and be posets. Then a function is said to be monotone (alternatively, order-preserving) if for all , implies .
Positive example
dot source:
digraph G { node = 0.1, height = 0.1 rankdir = BT; rank = same; compound = true; fontname="MathJax_Main";
subgraph cluster_P { node [style=filled,color=white]; edge = "none"; style = filled; color = lightgrey; fontcolor = black; label = "P"; labelloc = b; b -> a; c -> a;
}
subgraph cluster_Q {
node [style=filled];
edge = "none";
color = black;
fontcolor = black;
label= "Q";
labelloc = b;
u -> t;
}
edge = blue, style = dashed
fontcolor = blue;
label = "φ";
labelloc = t;
b -> t = false;
a -> t = false;
c -> u = false;
}
Here is an example of a monotone map from a poset to another poset . Since has two comparable pairs of elements, and , there are two constraints that must satisfy to be considered monotone. Since , we need . This is, in fact, the case. Also, since , we need . This is also true.
Negative example
dot source:
digraph G { node = 0.1, height = 0.1 rankdir = BT; rank = same; compound = true; fontname="MathJax_Main";
subgraph cluster_P { node [style=filled,color=white]; edge = "none"; style = filled; color = lightgrey; fontcolor = black; label = "P"; labelloc = b; a -> b; }
subgraph cluster_Q {
node [style=filled];
edge = "none";
color = black;
fontcolor = black;
label= "Q";
labelloc = b;
w -> u;
w -> v;
u -> t;
v -> t;
}
edge = blue, style = dashed
fontcolor = blue;
label = "φ";
labelloc = t;
b -> u = false;
a -> v = false;
}
Here is an example of another map between two other posets and . This map is not monotone, because while .
Additional material
For some examples of montone functions and their applications, see Monotone function: examples. To test your knowledge of monotone functions, head on over to Monotone function: exercises.