Monotone function: exercises

Try these ex­er­cises and be­come a de­ity of mono­ton­ic­ity.

Mono­tone composition

Let \(P, Q\), and \(R\) be posets and let \(f : P \to Q\) and \(g : Q \to R\) be mono­tone func­tions. Prove that their com­po­si­tion \(g \circ f\) is a mono­tone func­tion from \(P\) to \(R\).

Evil twin

Let \(P\) and \(Q\) be posets. A func­tion \(f : P \to Q\) is called an­ti­tone if it re­verses or­der: that is, \(f\) is an­ti­tone when­ever \(p_1 \leq_P p_2\) im­plies \(f(p_1) \geq_Q f(p_2)\). Prove that the com­po­si­tion of two an­ti­tone func­tions is mono­tone.

Par­tial monotonicity

A two ar­gu­ment func­tion \(f : P \times A \to Q\) is called par­tially mono­tone in the 1st ar­gu­ment when­ever \(P\) and \(Q\) are posets and for all \(a \in A\), \(p_1 \leq_P p_2\) im­plies \(f(a, p_1) \leq_Q f(a, p_2)\). Like­wise a 2-ar­gu­ment func­tion \(f : A \times P \to Q\) is called par­tially mono­tone in the sec­ond ar­gu­ment when­ever \(P\) and \(Q\) are posets and for all \(a \in A\), \(p_1 \leq_P p_2\) im­plies \(f(p_1, a) \leq_Q f(p_2, a)\).

Let \(P, Q, R\), and \(S\) be posets, and let \(f : P \times Q \to R\) be a func­tion that is par­tially mono­tone in both of its ar­gu­ments. Fur­ther­more, let \(g_1 : S \to P\) and \(g_2 : S \to Q\) be mono­tone func­tions.

Prove that the func­tion \(h : S \to R\) defined as \(h(s) \doteq f(g_1(s), g_2(s))\) is mono­tone.

Brain storm

List all of the com­monly used two ar­gu­ment func­tions you can think of that are par­tially mono­tone in both ar­gu­ments. Also, list all of the com­monly used two ar­gu­ment func­tions you can think of that are par­tially mono­tone in one ar­gu­ment and par­tially an­ti­tone in the other.

Parents:

  • Monotone function

    An or­der-pre­serv­ing map be­tween posets.

    • Order theory

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