I have a function f:Mk→R, where Mk⊂{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 Mk, that is:
∀(x1,…,xn),(y1,…,yn)∈Mk:(x1,…,xn)<(y1,…,yn)⇒f((x1,…,xn))<f((y1,…,yn))
Here, (x1,…,xn)<(y1,…,yn) holds iff xi≤yi∀1≤i≤n and ∃j:xj<yj.
My problem is that this seems to be undefined since no two distinct tuples can fulfill this.
Any tuple with xi<yi must have another element with xj>yj, because each tuple has exactly k entries that are 1?
Is strong monotonicity even defined in this case or is each function on Mk strongly monotone per default?
Thanks in advance!
Answer
Claim: Given two distinct n-tuples, x=(x1,…,xn) and y=(y1,…,yn), with exactly k entries equal to 1 and the rest 0, where 1≤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