関数の存在を証明する $f:\Bbb Z^+ \to \Bbb Z^+$ そのような $a,b,c$ が存在します $n$ そのような $f(an+b)=c$

Question

私はVellemanの「HowtoProveit」の本から次の演習を解決しようとしています。

機能があることを証明する $f:\Bbb Z^+ \to \Bbb Z^+$ すべての正の整数に対して $a, b$ そして $c$ いくつかの正の整数があります $n$ そのような $f(an+b) = c$。

私は関数のファミリー間で同等の定理を使おうと試みてきましたが、成功しませんでした。誰かが私にこの問題に取り組む方法についてのヒントを教えてもらえますか？

Answer 1

ヒント：正の整数のトリプルは数え切れないほどあります $(a,b,c)$。だから、の値を定義してみてください$f$ トリプルの1つを処理する各ステップで1つずつ。

Answer 2

フォームのトリプルに注意してください $(a,b,c)$ ために $a,b,c\in\mathbb{N}$可算です。したがって、トリプルと自然数の間には全単射が存在します。しましょう$S(n):\mathbb{N}\to (a,b,c)\in\mathbb{N}^{3}$ そのような全単射であり、定義する

$$\omega(n)=\omega(n-1)[S_1(n-1)+1]S_2(n-1)$$

どこ $\omega(1)=1$ （どこ $S_i(n)$ それは $i$のエントリ $n$thトリプレット）。表示します

$$S_1(n-1)\omega(n-1)+S_2(n-1)<S_1(n)\omega(n)+S_2(n)$$

基本ケースについては、次の点に注意してください。

$$S_1(2)\omega(2)+S_2(2)=S_1(2)\bigg[\omega(1)[S_1(1)+1]S_2(1)\bigg]+S_2(2)$$

$$=S_1(2)[S_1(1)+1]S_2(1)+S_2(2)=S_1(2)S_1(1)S_2(1)+S_1(2)S_2(1)+S_2(1)$$

$$>S_1(1)+S_1(2)=S_1(1)\omega(1)+S_2(1)$$

帰納法のステップについては、

$$S_1(n)\omega(n)+S_2(n)=S_1(n)\bigg[ \omega(n-1) [S_1(n-1)+1]S_2(n-1)\bigg]+S_2(n)$$

$$=S_1(n) \omega(n-1) S_1(n-1)S_2(n-1)+S_1(n) \omega(n-1)S_2(n-1)+S_2(n)$$

$$> S_1(n-1)\omega(n-1)+S_2(n-1)$$

私たちはそれを $i\neq j$

$$S_1(i)\omega(i)+S_2(i)\neq S_1(j)\omega(j)+S_2(j)$$

関数を定義します

$$f(m)=\begin{cases} S_3(m)&& m=S_1(n)\omega(n)+S_2(n)\text{ for }n\in\mathbb{N}\\ 0&& \text{otherwise} \end{cases}$$