Monotone function

Let \(\langle P, \leq_P \rangle\) and \(\langle Q, \leq_Q \rangle\) be posets. Then a func­tion \(\phi : P \rightarrow Q\) is said to be mono­tone (al­ter­na­tively, or­der-pre­serv­ing) if for all \(s, t \in P\), \(s \le_P t\) im­plies \(\phi(s) \le_Q \phi(t)\).

Pos­i­tive example

A simple monotone map phi

com­ment: dot source:

di­graph G { node = 0.1, height = 0.1 rankdir = BT; rank = same; com­pound = true; font­name=”MathJax_Main”;

sub­graph cluster_P { node style=filled,color=white; edge = “none”; style = filled; color = light­grey; font­color = black; la­bel = “P”; la­bel­loc = b; b → a; c → a;

} sub­graph cluster_Q { node style=filled; edge = “none”; color = black; font­color = black; la­bel= “Q”; la­bel­loc = b; u → t; } edge = blue, style = dashed font­color = blue; la­bel = “φ”;
la­bel­loc = t; b → t = false; a → t = false; c → u = false; }

<div>

Here is an ex­am­ple of a mono­tone map \(\phi\) from a poset \(P\) to an­other poset \(Q\). Since \(\le_P\) has two com­pa­rable pairs of el­e­ments, \((c,a)\) and \((b,a)\), there are two con­straints that \(\phi\) must satisfy to be con­sid­ered mono­tone. Since \(c \leq_P a\), we need \(\phi(c) = u \leq_Q t = \phi(a)\). This is, in fact, the case. Also, since \(b \leq_P a\), we need \(\phi(b) = t \leq_Q t = \phi(a)\). This is also true.

Nega­tive example

A simple, non-monotone map

com­ment: dot source:

di­graph G { node = 0.1, height = 0.1 rankdir = BT; rank = same; com­pound = true; font­name=”MathJax_Main”;

sub­graph cluster_P { node style=filled,color=white; edge = “none”; style = filled; color = light­grey; font­color = black; la­bel = “P”; la­bel­loc = b; a → b; }

sub­graph cluster_Q { node style=filled; edge = “none”; color = black; font­color = black; la­bel= “Q”; la­bel­loc = b; w → u; w → v; u → t; v → t; } edge = blue, style = dashed font­color = blue; la­bel = “φ”;
la­bel­loc = t; b → u = false; a → v = false; } <div>

Here is an ex­am­ple of an­other map \(\phi\) be­tween two other posets \(P\) and \(Q\). This map is not mono­tone, be­cause \(a \leq_P b\) while \(\phi(a) = v \parallel_Q u = \phi(b)\).

Ad­di­tional material

For some ex­am­ples of mon­tone func­tions and their ap­pli­ca­tions, see Mono­tone func­tion: ex­am­ples. To test your knowl­edge of mono­tone func­tions, head on over to Mono­tone func­tion: ex­er­cises.

Children:

Parents:

  • Order theory

    The study of bi­nary re­la­tions that are re­flex­ive, tran­si­tive, and an­ti­sym­metic.