|
|
设$S=\{1,2,\cdots,m\}$, $a$与$b$是从$S$到$\Bbb R$的函数, $f$和$g$是从$S$到$S$的双射, 满足
i) 对任何$n∈S$有$a(n)<b(n)$.
ii) $a∘f$与$b∘g$是严格增的.
求证: 对任何$n∈S$有$a(f(n))<b(g(n))$.
$a(f(1))=\min a(S)<\min b(S)=b(g(1))$
对$n$归纳,假设$a(f(i))<b(g(i))$对任何$i=1,2,\cdots,n$而$a(f(n+1))≥b(g(n+1))$.
因为对任何$i∈S$有$a(i)<b(i)$且$a∘f$和$b∘g$是严格增的,所以
\begin{align*}
a(f(1))<a(f(2))<\cdots<a(f(n))&<b(g(n))\\
&<b(g(n+1))≤a(f(n+1))<a(f(n+2))<\cdots<a(f(m))
\end{align*}
所以$$\{f(1),f(2),\cdots,f(n)\}=\{i∈S:a(i)<b(g(n+1))\}\tag1$$
因为对任何$i∈S$有$a(i)<b(i)$且$b∘g$是严格增的,所以$a(g(i))<b(g(i))≤b(g(n+1))$对任何$i=1,2,\cdots,n+1$成立,所以
$$\{g(1),g(2),\cdots,g(n+1)\}\subseteq\{i∈S:a(i)<b(g(n+1))\}\tag2$$
由(1)与(2)得
$$\{g(1),g(2),\cdots,g(n+1)\}\subseteq\{f(1),f(2),\cdots,f(n)\}$$
左边比右边多1个元素.矛盾.
等价形式:矩阵按行、列排序 |
|
