# 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. ## 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. 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.

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.