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?
Thanks in advance!
Answer
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
Proof: If there does not exist a $j$ such that $x_j
No comments:
Post a Comment