【対関数②】次は、N×Nの2つの対関数を使って自然数全体を表すことを考えてみます！

$\boldsymbol{p_o}$の単射性の証明

異なる入力$(s_{1},t_{1})$と$(s_{2},t_{2})$が同じ出力を持つと仮定すると
$ \frac{2^{2s_{1}-1}(6t_{1}-5)+1}{3} $=$ \frac{2^{2s_{2}-1}(6t_{2}-5)+1}{3} $
よって$ 2^{2s_{1}-1}(6t_{1}-5) $=$ 2^{2s_{2}-1}(6t_{2}-5) $
2のべき乗は常に偶数、$6t-5$は常に奇数なので、それぞれの部分を比較すると、
$2^{2s_{1}-1}$=$2^{2s_{2}-1}$より、$s_{1}=s_{2}$
$6t_{1} -5$=$6t_{2}-5$より、$6t_{1}=6t_{2}$なので、$t_{1}=t_{2}$
よって、$\boldsymbol{p_o}(s,t)$は単射である。

$\boldsymbol{p_e}$の単射性の証明

異なる入力$(s_{1},t_{1})$と$(s_{2},t_{2})$が同じ出力を持つと仮定すると
$ \frac{2^{2s_{1}-2}(6t_{1}-1)+1}{3} $=$ \frac{2^{2s_{2}-2}(6t_{2}-1)+1}{3} $
よって$ 2^{2s_{1}-2}(6t_{1}-1) $=$ 2^{2s_{2}-2}(6t_{2}-1) $
2のべき乗は常に偶数、$6t-1$は常に奇数なので、それぞれの部分を比較すると、
$2^{2s_{1}-2}$=$2^{2s_{2}-2}$より、$s_{1}=s_{2}$
$6t_{1} -1$=$6t_{2}-1$より、$6t_{1}=6t_{2}$なので、$t_{1}=t_{2}$
よって、$\boldsymbol{p_e}(s,t)$は単射である。

奇数を$3$倍して$1$を引いた数を、奇数になるまで$2$で割ったときの商は、$3$を因数には持たないので、その奇数は、$6$で割ったときに$1$余る数か、もしくは$5$余る数である。$1$余る数のとき$2$で割る回数は奇数回であり、$5$余る数のとき$2$で割る回数は偶数回である

$\boldsymbol{p_o}$の全射性の証明

３倍して１を引き、奇数になるまで２で割ったときの商が、$6$で割ったときに$1$余る数であるときの自然数$n_o \in \mathbb{N} $を任意に取る。

奇数になるまで$2$で割ったときの商を$m$,$2$で割る回数を$k$回とおくと
$\frac{3\boldsymbol{n_o}-1}{2^k}=m$
$3n_o-1=2^k\cdot m$
$n_o=\frac{2^{k} \cdot m+1}{3}$
ここで$k$と$m $は正の奇数である。

$2^{k}=2^{2s-1}$,$m=6t-5$とおくと、
$s=\frac{k+1}{2}$ , $t= \frac{m+5}{6} $
$k$も$m$も奇数であるから、$s$も$t$も$1$以上の整数であり、
$\boldsymbol{p^{o} }(s,t)= \frac{2^{2s-1}s(6t-5)+1}{3} $$=\frac{2^{k} \cdot m+1}{3}$$=n_o$
よって、$\boldsymbol{p_o}(s,t)$は全射である。

$\boldsymbol{p_e}$の全射性の証明

３倍して１を引き、奇数になるまで２で割ったときの商が$6$で割ったときに$5$余る数であるときの自然数$n_e \in \mathbb{N} $を任意に取る。

奇数になるまで$2$で割ったときの商を$m$,$2$で割る回数を$k$回とおくと
$\frac{3\boldsymbol{n_e}-1}{2^k}=m$
$3n_e-1=2^k\cdot m$
$n_e=\frac{2^{k} \cdot m+1}{3}$
ここで$k$ は$0$以上の偶数、 $m$は正の奇数である。

$2^{k}=2^{2s-2}$,$m=6t-1$とおくと、
$s=\frac{k+2}{2}$ , $t= \frac{m+1}{6} $
$k$ は$0$以上の偶数、 $m$は正の奇数であるから、$s$も$t$も$1$以上の整数であり、
$\boldsymbol{p_{e} }(s,t)= \frac{2^{2s-2}(6t-1)+1}{3} $$=\frac{2^{k} \cdot m+1}{3}$$=n_e$
よって、$\boldsymbol{p_e}(s,t)$は全射である。

結論

ゆえに、$\boldsymbol p_o(s,t),\boldsymbol{p_e}(s,t)$は単射かつ全射であるため、自然数への全単射である。