\(\LARGE^\star\;\textbf{从1-1对应 }f:\mathbb{N}\to\mathbb{Q}^+\textbf{ 说起}\)

elim

定义\(\small f:\mathbb{N}^+\to\mathbb{Q}^+\) 如下: \(\scriptsize f(1)=1,\,f(2)=2.\;\)设\(f(n)\,\small( n< 2k)\) 已确定
则定义 \({\small f(2k+v)=}\begin{cases}{\large\frac{m}{m+n}},& v=0;\\{\large\frac{m+n}{n}},& v=1.\end{cases}\scriptsize\;(m,n\in\mathbb{N}^+,\,\gcd(m,n)=1,\,f(k)={\frac{m}{n}}.)\)
从这个递归定义不难看出 \(f\) 是单射. 以下证明 \(f\) 是漫射：
令 \(E=\mathbb{Q}^+-f(\mathbb{N}^+),\) 设 \({\large\frac{m}{n}}\in E\) 使 \({\large\frac{u}{v}}\in E\implies u+v\ge m+n\)
设 \(m< n,\) 则 \(\exists k\in\mathbb{N}^+\,f(k)={\large\frac{m}{n-m}},\,f(2k)={\large\frac{m}{n}}\) 又若 \(m>n,\) 则
有 \(k'\in\mathbb{N}^+\)使 \(f(k') = {\large\frac{m-n}{n}},\;f(2k'+1)={\large\frac{m}{n}}.\) 故必有 \(m=n.\) 但
这蕴涵 \(1\in E\) 与 \(f(1)=1\) 矛盾. 所以 \(E=\varnothing,\;f(\mathbb{N}^+)=\mathbb{Q}^+.\quad_\blacksquare\)

【例】\(\small 21 = 2^4 +0\cdot 2^3 + 1\cdot 2^2 + 0\cdot 2^1 + 1=2^4+v_12^3+v_22^2+v_32^1+v_4\)
\(\small =2(2(2(2+v_1)+v_2)+v_3)+v_4,\scriptsize\;\;f(2)=\dfrac{1}{2},\,f(5)=\dfrac{3}{2},\;f(10)=\dfrac{3}{5},\;\boxed{f(21)=\dfrac{8}{5}}\)
【注记】给出二同势集合间的一一对应通常是一件不易但有趣的事情.