【対関数①】2つの自然数から自然数全体を生成する関数、Cantorの対関数の別の式を考えてみる
対関数（ついかんすう、英: Pairing function）とは、2つの自然数を一意に符号化して1つの自然数を返す関数である
だそうで、この「対関数」について、他に式がないかを考察してみたいと思います。
自然数は1以上の整数と定義して話します。
下のような関数を定義してみます！カントールの対関数のように、自然数について全単射となる、2変数の関数です。ぱっと見で、すぐ全単射だろうと予想できる式ですし、自明のことかもしれませんが、証明を以下に記してみます。
s,tが自然数（1以上）であるとき、自然数$\boldsymbol{p}(s,t)$を
$\boldsymbol{p}(s,t)=2^{s-1}(2t-1)$
で表す
写像$\boldsymbol{p}$ : $\mathbb{N}$$\times$$\mathbb{N}$$\rightarrow$$\mathbb{N}$を$\boldsymbol{p}(s,t)=2^{s-1}(2t-1)$で定めるとき、$\boldsymbol{p}$は全単射である。
単射性の証明
異なる入力$(s_{1},t_{1})$と$(s_{2},t_{2})$が同じ出力を持つと仮定すると
$2^{s_{1} -1}(2t_{1}-1)$=$2^{s_{2}-1}(2t_{2}-1)$
$2$のべき乗は常に偶数、$2t-1$は常に奇数なので、それぞれの部分を比較すると、
$2^{s_{1} -1}$=$2^{s_{2}-1}$より、$s_{1} -1$=$s_{2}-1$なので、$s_{1}=s_{2}$
$2t_{1} -1$=$2t_{2}-1$より、$2t_{1}=2t_{2}$なので、$t_{1}=t_{2}$
よって、$\boldsymbol{p}(s,t)$は単射である。
全射性の証明
$n \in \mathbb{N} $を任意に取る。$n$の素因数分解により、$n=2^k \cdot m$となる、$0$以上の整数$k$と正の奇数$m$が存在する。
ここで、$k=s-1$,$m=2t-1$とすると、
$s=k+1$なので、$s$は$1$以上の整数、
$t= \frac{m+1}{2} $、$m$は奇数であるから$m+1$は偶数、よって、$t$も$1$以上の整数であり、
$\boldsymbol{p}(s,t)=2^{s-1}(2t-1)=2^k \cdot m=n$
ゆえに、$\boldsymbol{p}(s,t)$は全射である。
結論
よって、単射かつ全射であるため、$\boldsymbol{p}$は全単射である。
最後までお読みいただき、ありがとうございました！
この記事を高評価した人
この記事に送られたバッジ
投稿者
