Monotone function: examples

Here are some ex­am­ples of mono­tone func­tions.

A cun­ning plan

There’s a two-player game called 10 ques­tions, in which player A be­gins the game by stat­ing “I’m think­ing of an X”, where X can be re­placed with any noun of player A’s choos­ing.

Then player B asks player A a se­ries of ques­tions, which player A must an­swer with ei­ther truth­fully with “yes” or “no”. After ask­ing 10 ques­tions, player B is forced to guess what the ob­ject player A was think­ing of. Player B wins if the guess is cor­rect, and loses oth­er­wise. Player B may guess be­fore 10 turns have ex­pired, in which case the guess counts as one of their ques­tions.

Here is an ex­am­ple of a game of 10 ques­tions:

A: I’m think­ing of a food.

Ques­tion 1. B: Is it healthy? A: Yes.

Ques­tion 2. B: Is it crunchy? A: No.

Ques­tion 3. B: Must it be pre­pared be­fore it is eaten? A: No.

Ques­tion 4. B: Is yel­low? A: Yes.

Ques­tion 5. B: Is it a ba­nana? A: Yes.

Player B wins

Now sup­pose that you are play­ing 10 ques­tions as player B. Player A be­gins by stat­ing “I’m think­ing of a let­ter of the alpha­bet.” You im­me­di­ately think of a strat­egy that re­quires no more than 5 guesses: re­peat­edly ask “does it come af­ter \(\star\)?” where \(\star\) is near the mid­dle of the con­tigu­ous se­quence of let­ters that you have not yet elimi­nated. Ini­tially the con­tigu­ous se­quence of let­ters be­tween A and Z have not been elimi­nated.

Ques­tion 1. You: Does it come af­ter M? Player A: Yes.

At this point, the con­tigu­ous se­quence of 13 let­ters that have not been elimi­nated is N-Z, in­clu­sive.

Ques­tion 2. You: Does it come af­ter S? Player A: No.

At this point, the con­tigu­ous se­quence of 6 let­ters that have not been elimi­nated is N-S, in­clu­sive.

Ques­tion 3. You: Does it come af­ter P? Player A: Yes.

We’ve now nar­rowed it down to Q,R,and S.

Ques­tion 4. You: Does it come af­ter R? Player A: No.

Ques­tion 5. You: Does it come af­ter Q? Player A: No.

You: Is it Q? Player A: Yes.

You win

But what does this have to do with mono­tone func­tions? The let­ters of the alpha­bet form a poset \(Alph = \langle \{A,...,Z\}, \leq_{Alph} \rangle\) (in fact, a to­tally or­dered set) un­der the stan­dard alpha­betic or­der. Your strat­egy for play­ing 10 ques­tions can be viewed as prob­ing a mono­tone func­tion from \(Alph\) to the 2-el­e­ment poset 2 of a boolean val­ues, where \(false <{\textbf{2}} true\). Speci­fi­cally, the probed func­tion \(f : Alph \to \textbf{2}\) is defined such that \(f(\star) \doteq Q >_{Alph} \star\)

The mono­ton­ic­ity of \(f\) is cru­cial to be­ing able to elimi­nate pos­si­bil­ities at each step. If we probe \(f\) at a let­ter \(\star_1\) and ob­serve a false re­sult, then any let­ter \(\star_2\) less than \(\star_1\) must map to false as well: \(\star_2 \leq_{Alph} \star_1\) im­plies \(f(\star_2) \leq_{\textbf{2}} f(\star_1)\). Yes, we can demon­strate the afor­men­tioned mono­tone func­tion with a di­a­gram, but since its size is un­wieldy, it has been placed in the fol­low­ing hid­den text block.

Diagram of f

De­duc­tion systems

de­duc­tion sys­tems al­low one to in­fer new judg­ments from a set of known judg­ments. They are of­ten speci­fied as a set of rules, in which each rule is rep­re­sented as a hori­zon­tal bar with one or more premises ap­pear­ing above the bar and a con­clu­sion that can be de­duced from those premises ap­pear­ing be­low the bar.

A deduction system

The above rules form a frag­ment of propo­si­tional logic.\(\phi\) and \(\psi\) are used to de­note log­i­cal state­ments, called propo­si­tions.\(\wedge\) and \(\to\) are bi­nary log­i­cal op­er­a­tors, each of which maps a pair of propo­si­tions to a sin­gle propo­si­tion.\(\wedge\) is the and op­er­a­tor: if \(\phi\) and \(\psi\) are log­i­cal state­ments, then \(\phi \wedge \psi\) is the si­mul­ta­neous as­ser­tion of both \(\phi\) and \(\psi\). \(\to\) is the im­pli­ca­tion op­er­a­tor: \(\phi \to \psi\) as­serts that if we know \(\phi\) to be true, then we can con­clude \(\psi\) is true as well.

The left­most rule has two premises \(\phi\) and \(\psi\), and con­cludes from these premises the propo­si­tion \(\phi \wedge \psi\). In­vok­ing a rule to de­duce its con­clu­sion from its premises is called ap­ply­ing the rule. A tree of rule ap­pli­ca­tions is called a proof.

De­duc­tion sys­tems are of­ten viewed as proof lan­guages. How­ever, it can also be fruit­ful to view a de­duc­tion sys­tem as a func­tion which, given a set of in­put propo­si­tions, pro­duces the set of all propo­si­tions that can be con­cluded from ex­actly one rule ap­pli­ca­tion, us­ing the in­put propo­si­tions as premises. More con­cretely, let­ting \(X\) be the set of propo­si­tions, the above set of de­duc­tion rules cor­re­sponds to the fol­low­ing func­tion \(F : \mathcal P(X) \to \mathcal P(X)\).

\(F(A) = \\ ~~ \{ \phi \wedge \psi\mid\phi \in A, \psi \in A \} \cup \\ ~~ \{ \phi \mid \phi \wedge \psi \in A \} \cup \\ ~~ \{ \psi \mid \phi \wedge \psi \in A \} \cup \\ ~~ \{ \phi \mid \psi \in A, \psi \to \phi \in A \}\)

\(F\) is a mon­tone func­tion from the poset \(\langle \mathcal P(X), \subseteq \rangle\) to it­self. The rea­son that \(F\) is mono­tone is that larger in­put sets give us more ways to ap­ply the rules of our sys­tem, yield­ing larger out­puts.

In ad­di­tion to stan­dard log­i­cal no­tions, de­duc­tion sys­tems can be used to de­scribe type sys­tems, pro­gram log­ics, and op­er­a­tional se­man­tics.

Ad­di­tional material

If you still haven’t had enough mono­ton­ic­ity, might I recom­mend try­ing some of the ex­er­cises?


In­creas­ing functions

A mono­tone func­tion be­tween two to­tally or­dered sets is called in­creas­ing. For ex­am­ple, the graph of a mono­tone func­tion from the poset \(\langle \mathbb R, \le \rangle\) to it­self has an up­ward slope. Such func­tions can be searched effi­ciently us­ing the bi­nary search al­gorithm.