# Monotone Function on n-tuples

I have a function $f: M_k \to R$, where $M_k \subset \{0,1\}^n$ is the set of all n-tuples with exactly $k$ entries that are $1$ while the rest is $0$.

I wish to show that $f$ is strong monotonically increasing in $M_k$, that is:

$\forall (x_1, \dots, x_n),(y_1, \dots, y_n) \in M_k:\\ (x_1, \dots, x_n) <(y_1, \dots, y_n) \Rightarrow f((x_1, \dots, x_n)) < f((y_1, \dots, y_n))$

Here, $(x_1, \dots, x_n) < (y_1, \dots, y_n)$ holds iff $x_i \leq y_i \; \forall 1 \leq i \leq n$ and $\exists j: x_j < y_j$.

My problem is that this seems to be undefined since no two distinct tuples can fulfill this.

Any tuple with $x_i < y_i$ must have another element with $x_j > y_j$, because each tuple has exactly $k$ entries that are 1?

Is strong monotonicity even defined in this case or is each function on $M_k$ strongly monotone per default?

• In your criterion for tuple inequalities, is $1<i$ a typo, or do you mean to exclude the first element from consideration? Jun 25 '18 at 14:03
• Yeah, I would agree with your assessment: you have to rob Peter to pay Paul, so to speak, since you must have exactly $k\;1$'s in your tuple. Given your definition of monotonicity, it is vacuously satisfied for every possible $f$; every possible $f$ is therefore strongly monotonic. Not sure this says anything useful, though. Jun 25 '18 at 14:16
Claim: Given two distinct $n$-tuples, $\mathbf{x}=(x_1,\dots,x_n)$ and $\mathbf{y}=(y_1,\dots,y_n),$ with exactly $k$ entries equal to $1$ and the rest $0,$ where $1\le k< n,$ and given the definition $$(u_1,\dots,u_n)<(v_1,\dots,v_n) \iff [(\forall\,i)(1\le i\le n)(u_i\le v_i)\;\land\;(\exists\,j)(u_j<v_j)],$$ it follows that $(x_1,\dots,x_n)\not<(y_1,\dots,y_n).$
Proof: If there does not exist a $j$ such that $x_j<y_j,$ we are done. Suppose, therefore, that there does exist a $j$ such that $x_j<y_j$. It follows from the definition of the $n$-tuples under consideration that $x_j=0$ and $y_j=1$. If we consider the non-$j$ entries, there must be exactly $k$ of them in $\mathbf{x}$ that are $1$, and $k-1$ of them in $\mathbf{y}$ that are $1$. By the Pigeonhole Principle, there must be at least one number, $\ell,$ such that $1\le\ell\le n,$ with $j\not=\ell,$ such that $x_{\ell}=1$ and $y_{\ell}=0.$ But then $x_{\ell}>y_{\ell},$ making the condition $(\forall\,i)(1\le i\le n)(x_i\le y_i)$ false. Hence, $\mathbf{x}\not<\mathbf{y}.$