【対関数③】N×Nの３つの対関数を使って自然数全体を表す（値を表にすると並びがコラッツ計算？？）
自然数は1以上と定義します。
自然数全体を、対関数3つで表すことを考えてみます。
$s,t$が1以上の自然数であるとき
$\boldsymbol{a}(s,t)=2^{s}(2t-1)$
奇数を３倍して１を足した数を、奇数になるまで２で割ったときに、２で割る回数が偶数回になる奇数を$\boldsymbol{b_e}$、奇数回になる奇数を$\boldsymbol{b_o}$とすると
$\boldsymbol{b_{e} }(s,t)= \frac{2^{2s}(6t-5)-1}{3} $
$\boldsymbol{b_{o} }(s,t)=\frac{2^{2s-1}(6t-1)-1}{3}$
である
$\boldsymbol{a}$ : $\mathbb{N}$$\times$$\mathbb{N}$$\longrightarrow$$\mathbb{N_{a}}$
$\boldsymbol{b_{e}}$ : $\mathbb{N}$$\times$$\mathbb{N}$$\longrightarrow$$\mathbb{N_{be}}$
$\boldsymbol{b_{o}}$ : $\mathbb{N}$$\times$$\mathbb{N}$$\longrightarrow$$\mathbb{N_{bo}}$で、
$(\mathbb{N_{a}} \cap \mathbb{N_{be}} ) = \varnothing $ , $(\mathbb{N_{a}} \cap \mathbb{N_{bo}} ) = \varnothing $ , $(\mathbb{N_{be}} \cap \mathbb{N_{bo}} ) = \varnothing $
$(\mathbb{N_{a}} \cup \mathbb{N_{be}} \cup \mathbb{N_{be}})= \mathbb{N} $となり、
$\boldsymbol{a,b_{e},b_{o}}$合わせて全単射となる
偶数$\boldsymbol{a(s,t)}$
$a$の単射性の証明
異なる入力$(s_{1},t_{1})$と$(s_{2},t_{2})$が同じ出力を持つと仮定すると
$2^{s_{1}}(2t_{1}-1)$=$2^{s_{2}}(2t_{2}-1)$
$2$のべき乗は常に偶数、$2t-1$は常に奇数なので、それぞれの部分を比較すると、
$2^{s_{1}}$=$2^{s_{2}}$より、$s_{1}=s_{2}$
$2t_{1} -1$=$2t_{2}-1$より、$2t_{1}=2t_{2}$なので、$t_{1}=t_{2}$
よって、$\boldsymbol{a}(s,t)$は偶数への単射である。
$\boldsymbol{a}$の全射性の証明
$n \in \mathbb{N} $を任意に取り、この$n$を$n=2^{k-1} \cdot m$の形に素因数分解する。
ここでkは1以上の整数、$m$は正の奇数とする。
$k=s$,$m=2t-1$とおくと、
$m$は奇数であるから$m+1$は偶数、よって、$s$も$t$も$1$以上の整数であり、
$\boldsymbol{a}(s,t)=2^{s}(2t-1)=2^k \cdot m=2n$
である。ゆえに、$\boldsymbol{a}(s,t)$は偶数全体への全射である。
よって、$\boldsymbol{a}(s,t)$は単射かつ全射であるため、$s,t$すべての自然数の組から偶数全体への全単射である。
次に、奇数を３倍して１を足した数を、奇数になるまで２で割ったときに、２で割る回数が偶数回になる奇数を$\boldsymbol{b_e}$、奇数回になる奇数を$\boldsymbol{b_o}$とする。
奇数$\boldsymbol{b_e}(s,t),\boldsymbol{b_o}(s,t)$
$\boldsymbol{b_e}$の単射性の証明
異なる入力$(s_{1},t_{1})$と$(s_{2},t_{2})$が同じ出力を持つと仮定すると
$ \frac{2^{2s_{1}}(6t_{1}-5)-1}{3} $=$ \frac{2^{2s_{2}}(6t_{2}-5)-1}{3} $
よって$ 2^{2s_{1}}(6t_{1}-5) $=$ 2^{2s_{2}}(6t_{2}-5) $
2のべき乗は常に偶数、$6t-5$は常に奇数なので、それぞれの部分を比較すると、
$2^{2s_{1}}$=$2^{2s_{2}}$より、$s_{1}=s_{2}$
$6t_{1} -5$=$6t_{2}-5$より、$6t_{1}=6t_{2}$なので、$t_{1}=t_{2}$
よって、$\boldsymbol{b_e}(s,t)$は単射である。
$\boldsymbol{b_o}$の単射性の証明
異なる入力$(s_{1},t_{1})$と$(s_{2},t_{2})$が同じ出力を持つと仮定すると
$ \frac{2^{2s_{1}-1}(6t_{1}-1)-1}{3} $=$ \frac{2^{2s_{2}-1}(6t_{2}-1)-1}{3} $
よって$ 2^{2s_{1}-1}(6t_{1}-1) $=$ 2^{2s_{2}-1}(6t_{2}-1) $
2のべき乗は常に偶数、$6t-1$は常に奇数なので、それぞれの部分を比較すると、
$2^{2s_{1}-1}$=$2^{2s_{2}-1}$より、$s_{1}=s_{2}$
$6t_{1} -1$=$6t_{2}-1$より、$6t_{1}=6t_{2}$なので、$t_{1}=t_{2}$
よって、$\boldsymbol{b_o}(s,t)$は単射である。
奇数を$3$倍して$1$を足した数を、奇数になるまで$2$で割ったときの商は、$3$を因数には持たないので、その奇数は、$6$で割ったときに$1$余る数か、もしくは$5$余る数である。$1$余る数のとき$2$で割る回数は偶数回であり、$5$余る数のとき$2$で割る回数は奇数回である
$\boldsymbol{b_e}$の全射性の証明
３倍して１を足し、奇数になるまで２で割ったときの商が、$6$で割ったときに$1$余る数であるときの自然数$n_{be} \in \mathbb{N} $を任意に取る。
奇数になるまで$2$で割ったときの商を$m$,$2$で割る回数を$k$回とおくと
$\frac{3\boldsymbol{n_{be}}+1}{2^k}=m$
$3n_{be}+1=2^k\cdot m$
$n_{be}=\frac{2^{k} \cdot m-1}{3}$
ここで$k$は正の偶数、$ m $は正の奇数である。
$2^{k}=2^{2s}$,$m=6t-5$とおくと、
$s=\frac{k}{2}$ , $t= \frac{m+5}{6} $
$k$は偶数、 $m$は奇数であるから、$s$も$t$も$1$以上の整数であり、
$\boldsymbol{b_{e} }(s,t)= \frac{2^{2s}(6t-5)-1}{3} $$=\frac{2^{k} \cdot m-1}{3}$$=n_{be}$
よって、$\boldsymbol{b_e}(s,t)$は全射である。
$\boldsymbol{b_o}$の全射性の証明
３倍して１を足し、奇数になるまで２で割ったときの商が、$6$で割ったときに5余る数であるときの自然数$n_{bo} \in \mathbb{N} $を任意に取る。
奇数になるまで$2$で割ったときの商を$m$,$2$で割る回数を$k$回とおくと
$\frac{3\boldsymbol{n_{bo}}+1}{2^k}=m$
$3n_{bo}+1=2^k\cdot m$
$n_{bo}=\frac{2^{k} \cdot m-1}{3}$
ここで$k$と$ m $は正の奇数である。
$2^{k}=2^{2s-1}$,$m=6t-1$とおくと、
$s=\frac{k+1}{2}$ , $t= \frac{m+1}{6} $
$k$も$m$も奇数であるから、$s$も$t$も$1$以上の整数であり、
$\boldsymbol{b_{o} }(s,t)= \frac{2^{2s-1}(6t-1)-1}{3} $$=\frac{2^{k} \cdot m-1}{3}$$=n_{bo}$
よって、$\boldsymbol{b_o}(s,t)$は全射である。
ゆえに、$\boldsymbol b_o(s,t),\boldsymbol{b_e}(s,t)$は単射かつ全射であるため、正の奇数への全単射である。
結論
よって、$\boldsymbol{a,b_{e},b_{o}}$合わせて自然数への全単射となる
最後までお読みいただき、ありがとうございました！
この記事を高評価した人
この記事に送られたバッジ
投稿者
