意味 ペアリング関数は 全単射 である
π : N × N → N 。 {\displaystyle \pi :\mathbb {N} \times \mathbb {N} \to \mathbb {N} .}
カントールペアリング関数 カントールペアリング関数は、自然数のペアごとに1つの自然数を割り当てます。 カントールペアリング関数のグラフ カントールペアリング関数は、 原始的な再帰的 ペアリング関数である。
π : N × N → N {\displaystyle \pi :\mathbb {N} \times \mathbb {N} \to \mathbb {N}} 定義される
π （ k 1 、 k 2 ） := 1 2 （ k 1 + k 2 ） （ k 1 + k 2 + 1 ） + k 2 = （ k 1 + k 2 + 1 2 ） + k 2 {\displaystyle \pi (k_{1},k_{2}):={\frac {1}{2}}(k_{1}+k_{2})(k_{1}+k_{2}+1)+k_{2}={\binom {k_{1}+k_{2}+1}{2}}+k_{2}} どこk 1 、 k 2 ∈ { 0 、 1 、 2 、 3 、 … } ${\displaystyle k_{1},k_{2}\in \{0,1,2,3,\dots \}}$
また、次のように表現することもできます。π （ x 、 y ） := x 2 + x + 2 x y + 3 y + y 2 2 {\displaystyle \pi (x,y):={\frac {x^{2}+x+2xy+3y+y^{2}}{2}}}
また、各引数に関して厳密に単調である。つまり、すべての引数に対してk 1 、 k 1 ′ 、 k 2 、 k 2 ′ ∈ N {\displaystyle k_{1},k_{1}',k_{2},k_{2}'\in \mathbb {N} } k 1 < k 1 ′ {\displaystyle k_{1}<k_{1}'} π （ k 1 、 k 2 ） < π （ k 1 ′ 、 k 2 ） {\displaystyle \pi (k_{1},k_{2})<\pi (k_{1}',k_{2})} k 2 < k 2 ′ {\displaystyle k_{2}<k_{2}'} π （ k 1 、 k 2 ） < π （ k 1 、 k 2 ′ ） {\displaystyle \pi (k_{1},k_{2})<\pi (k_{1},k_{2}')}
これが唯一の二次ペアリング関数であるという記述は、フーター・ポリアの定理 として知られています。[ 8 ] これが唯一の多項式ペアリング関数であるかどうかは、まだ未解決の問題です。ペアリング関数をk 1 k 2 ⟨ k 1 , k 2 ⟩ と表記することがよくあります。[ 9 ]
この定義は、帰納的にカントールタプル関数に一般化することができる。
π （ n ） : N n → N \displaystyle \pi ^{(n)}:\mathbb {N} ^{n}\to \mathbb {N} } のためにn > 2 {\displaystyle n>2}
π （ n ） （ k 1 、 … 、 k n − 1 、 k n ） := π （ π （ n − 1 ） （ k 1 、 … 、 k n − 1 ） 、 k n ） \displaystyle \pi ^{(n)}(k_{1},\ldots ,k_{n-1},k_{n}):=\pi (\pi ^{(n-1)}(k_{1},\ldots ,k_{n-1}),k_{n})} 上記で定義したペアの基本ケース：π （ 2 ） （ k 1 、 k 2 ） := π （ k 1 、 k 2 ） 。 {\displaystyle \pi ^{(2)}(k_{1},k_{2}):=\pi (k_{1},k_{2}).}
カントールペアリング関数を全単射に一般化した別の例π （ n ） : N n → N \displaystyle \pi ^{(n)}\colon \mathbb {N} ^{n}\to \mathbb {N} } 組み合わせ数体系 によって提供される：
π （ n ） （ x 1 、 … 、 x n ） = （ x 1 + ⋯ + x n + n − 1 n ） + （ x 1 + ⋯ + x n − 1 + n − 2 n − 1 ） + ⋯ + （ x 1 + x 2 + 1 2 ） + （ x 1 1 ） 。 {\displaystyle \pi ^{(n)}(x_{1},\dots ,x_{n})={\binom {x_{1}+\dots +x_{n}+n-1}{n}}+{\binom {x_{1}+\dots +x_{n-1}+n-2}{n-1}}+\dots +{\binom {x_{1}+x_{2}+1}{2}}+{\binom {x_{1}}{1}}.}
例 π (47, 32)
47 + 32 = 79 、79 + 1 = 80 、79 × 80 = 6320 、6320 ÷ 2 = 3160 、3160 + 32 = 3192 、したがって、π (47, 32) = 3192
π ( x , y ) = 1432 となるようなx y
8 × 1432 = 11456 、11456 + 1 = 11457 、√ 11457 107.037 − 1 = 106.037 、106.037 ÷ 2 = 53.019 、⌊53.019⌋ = 53 、したがって、w = 53
53 + 1 = 54 、53 × 54 = 2862 、2862 ÷ 2 = 1431 、t = 1431 ;
1432 − 1431 = 1 、y = 1 ;
53 − 1 = 52 、したがってx = 52π (52, 1) = 1432
導出 カントールのペアリング関数と同じ原理に基づく、対角線方向に増加する「蛇行」関数は、有理数の可算性を示すためによく用いられる。 カントールのペアリング関数のグラフ形状である対角線状の数列は、無限数列 と可算性を 扱う際の標準的な手法です。[ b ] この対角線状の関数の代数規則は、帰納法を 用いることで、さまざまな多項式に対してその妥当性を検証できます。その中でも二次関数が最も単純であることがわかります。実際、この同じ手法は、平面を列挙するさまざまなスキームに対して、他の任意の数の関数を導出するためにも使用できます。
ペアリング関数は通常、帰納的に定義できます。つまり、n 番目のペアが与えられたとき、 ( n +1) 番目のペアは何か、ということです。カントール関数が平面を斜めに横切る様子は、次のように表現できます。
π （ x 、 y ） + 1 = π （ x − 1 、 y + 1 ） {\displaystyle \pi (x,y)+1=\pi (x-1,y+1)} また、関数は第1象限の境界に達したときに何をするかを定義する必要があります。カントールのペアリング関数は、x軸に戻って対角線上の進行を1ステップ先まで再開します。代数的には次のようになります。
π （ 0 、 k ） + 1 = π （ k + 1 、 0 ） {\displaystyle \pi (0,k)+1=\pi (k+1,0)} また、開始点を定義する必要があります。これは、帰納法の最初のステップになります。π ( 0, 0) = 0 です
これらの条件を満たす2次元の2次多項式が存在すると仮定します（存在しない場合は、より高次の多項式を試すことで繰り返します）。一般形は次のようになります。
π （ x 、 y ） = 1 x 2 + b y 2 + c x y + d x + e y + f {\displaystyle \pi (x,y)=ax^{2}+by^{2}+cxy+dx+ey+f} 初期条件と境界条件を代入すると、f = 0
b k 2 + e k + 1 = 1 （ k + 1 ） 2 + d （ k + 1 ） {\displaystyle bk^{2}+ek+1=a(k+1)^{2}+d(k+1)} したがって、 k
b = a d = 1- a e = 1 + a つまり、 c a
π （ x 、 y ） + 1 = 1 （ x 2 + y 2 ） + c x y + （ 1 − 1 ） x + （ 1 + 1 ） y + 1 = 1 （ （ x − 1 ） 2 + （ y + 1 ） 2 ） + c （ x − 1 ） （ y + 1 ） + （ 1 − 1 ） （ x − 1 ） + （ 1 + 1 ） （ y + 1 ） 。 {\displaystyle {\begin{aligned}\pi (x,y)+1&=a(x^{2}+y^{2})+cxy+(1-a)x+(1+a)y+1\\&=a((x-1)^{2}+(y+1)^{2})+c(x-1)(y+1)+(1-a)(x-1)+(1+a)(y+1).\end{aligned}}} 項を再度展開して一致させることで、 a c
a = 1/2 = b = d c = 1e = 3 / 2 f = 0したがって
π （ x 、 y ） = 1 2 （ x 2 + y 2 ） + x y + 1 2 x + 3 2 y = 1 2 （ x + y ） （ x + y + 1 ） + y 、 {\displaystyle {\begin{aligned}\pi (x,y)&={\frac {1}{2}}(x^{2}+y^{2})+xy+{\frac {1}{2}}x+{\frac {3}{2}}y\\&={\frac {1}{2}}(x+y)(x+y+1)+y,\end{aligned}}} これはカントール対関数であり、導出を通してこれが帰納法のすべての条件を満たすことも示しました。
序数の場合 順序数 には「標準的な」ペアリング関数が存在し、それは同時にすべてのアレフ数 （つまり、すべての無限整列基数の 最初の順序数 ）のペアリング関数でもあります。これは、順序数のペアの次の整列によって誘導されます。
（ α 、 β ） ≼ （ γ 、 δ ） どちらか { （ α 、 β ） = （ γ 、 δ ） 、 最大 （ α 、 β ） < 最大 （ γ 、 δ ） 、 最大 （ α 、 β ） = 最大 （ γ 、 δ ） そして α < γ 、 または 最大 （ α 、 β ） = 最大 （ γ 、 δ ） そして α = γ そして β < δ 。 {\displaystyle (\alpha ,\beta )\preccurlyeq (\gamma ,\delta ){\text{ if either }}{\begin{cases}(\alpha ,\beta )=(\gamma ,\delta ),\\[4pt]\max(\alpha ,\beta )<\max(\gamma ,\delta ),\\[4pt]\max(\alpha ,\beta )=\max(\gamma ,\delta )\ {\text{and}}\ \alpha <\gamma ,{\text{ or}}\\[4pt]\max(\alpha ,\beta )=\max(\gamma ,\delta )\ {\text{and}}\ \alpha =\gamma \ {\text{and}}\ \beta <\delta .\end{cases}}} 基本的な考え方は、 最大 （ α 、 β ） {\displaystyle \max(\alpha ,\beta )} は 主ソートキー として使用されます。したがって、すべての序数に対して α {\displaystyle \alpha } 、両方のエントリが α {\displaystyle \alpha } は デカルト積は α × α {\displaystyle \alpha \times \alpha } は、この新しい順序付けの最初のセグメント にマッピングされ、最初のセグメントの順序タイプはで示されます。 γ （ α ） {\displaystyle \gamma (\alpha )}
以来 γ （ α ） {\displaystyle \gamma (\alpha )} あり 、 γ （ α ） ≥ α {\displaystyle \gamma (\alpha )\geq \alpha } また 連続的 である。 λ {\displaystyle \lambda } 私 λ × λ = ⋃ α < λ （ α × α ） {\displaystyle \lambda \times \lambda =\bigcup _{\alpha <\lambda }(\alpha \times \alpha )} α {\displaystyle \alpha } γ （ α ） = α {\displaystyle \gamma (\alpha )=\alpha } 超限帰納法 によって証明できる
もし α = ω {\displaystyle \alpha =\omega } γ （ α ） = ω {\displaystyle \gamma (\alpha )=\omega } 継続 性 γ （ n ） = n 2 {\displaystyle \gamma (n)=n^{2}} は 。 n {\displaystyle n} もし α > ω {\displaystyle \alpha >\omega } は γ （ α ） = α {\displaystyle \gamma (\alpha )=\alpha } 継続 性 | γ （ δ ） | = | δ × δ | = | δ | 2 = | δ | < | α | {\displaystyle \vert \gamma (\delta )\vert =\vert \delta \times \delta \vert =\vert \delta \vert ^{2}=\vert \delta \vert <\vert \alpha \vert } δ < α {\displaystyle \delta <\alpha } | δ | 2 = | δ | {\displaystyle \vert \delta \vert ^{2}=\vert \delta \vert } は、 。 δ {\displaystyle \delta } このペアリング機能の重要な意味は、 κ 2 = κ {\displaystyle \kappa ^{2}=\kappa } κ {\displaystyle \kappa } ZFC ではすべての基数は整列可能であるため 、 κ 2 = κ {\displaystyle \kappa ^{2}=\kappa } すべて の κ {\displaystyle \kappa } κ 2 = κ {\displaystyle \kappa ^{2}=\kappa } すべて の κ {\displaystyle \kappa } 選択公理 を意味する。この結果は タルスキの選択定理 として知られている。
自然数への制限 順序数の「標準的な」ペアリング関数を自然数の集合に限定する N ≡ ω {\displaystyle \mathbb {N} \equiv \omega } は、
エレガントなペア [ x 、 y ] := { y 2 + x もし x < y 、 x 2 + x + y もし x ≥ y 。 {\displaystyle \operatorname {ElegantPair} [x,y]:={\begin{cases}y^{2}+x&{\text{if}}\ x<y,\\x^{2}+x+y&{\text{if}}\ x\geq y.\\\end{cases}}} これは、次の式を使用してペアを解除できます。
エレガントアンペア [ z ] := { { z − ⌊ z ⌋ 2 、 ⌊ z ⌋ } もし z − ⌊ z ⌋ 2 < ⌊ z ⌋ 、 { ⌊ z ⌋ 、 z − ⌊ z ⌋ 2 − ⌊ z ⌋ } もし z − ⌊ z ⌋ 2 ≥ ⌊ z ⌋ 。 {\displaystyle \operatorname {ElegantUnpair} [z]:={\begin{cases}\left\{z-\lfloor {\sqrt {z}}\rfloor ^{2},\lfloor {\sqrt {z}}\rfloor \right\}&{\text{if }}z-\lfloor {\sqrt {z}}\rfloor ^{2}<\lfloor {\sqrt {z}}\rfloor ,\\\left\{\lfloor {\sqrt {z}}\rfloor ,z-\lfloor {\sqrt {z}}\rfloor ^{2}-\lfloor {\sqrt {z}}\rfloor \right\}&{\text{if }}z-\lfloor {\sqrt {z}}\rfloor ^{2}\geq \lfloor {\sqrt {z}}\rfloor .\end{cases}}} （定性的に言えば、正方形の辺に沿ったペアに連続した数字を割り当てる。）
このペアリング関数の利点の 1 つは、ペア関数を使用して二分木の ような構造を表す場合に現れます。 c {\displaystyle c} 自然 、 ペア [ x 、 y ] + c {\displaystyle \operatorname {Pair} [x,y]+c} は、 。 x {\displaystyle x} そして y {\displaystyle y} それぞれ SKコンビネータ計算 式があります。
その他のペアリング機能 機能P 2 （ x 、 y ） := 2 x （ 2 y + 1 ） − 1 {\displaystyle P_{2}(x,y):=2^{x}(2y+1)-1}
1990 年、リーガンは、線形時間 と定数空間で計算可能な最初の既知のペアリング関数を提案しました(以前の既知の例では、乗算が でなければ 線形時間で計算できませんが、これは疑わしいです)。実際、このペアリング関数とその逆関数は、有限状態トランスデューサ を使用して計算できます。同じ論文で、著者は、オンライン で線形時間と対数空間 で計算できるさらに 2 つの単調ペアリング関数を提案しました。最初のものは、オフラインで定数空間で計算することもできます。
2001年、ピジョンはビットインターリーブ に基づくペアリング関数を提案し、それは再帰的に次のように定義される。
⟨ 私 、 j ⟩ P = { ⊥ もし 私 = j = 0 ; ⟨ ⌊ 私 / 2 ⌋ 、 ⌊ j / 2 ⌋ ⟩ P : 私 0 : j 0 さもないと、 {\displaystyle \langle i,j\rangle _{P}={\begin{cases}\bot &{\text{if}}\ i=j=0;\\\langle \lfloor i/2\rfloor ,\lfloor j/2\rfloor \rangle _{P}:i_{0}:j_{0}&{\text{otherwise,}}\end{cases}}} どこ私 0 {\displaystyle i_{0}} j 0 {\displaystyle j_{0}} はそれぞれi とj の最下位ビット である。
引用文献
注記 ↑ つまり、 A 2 → A {\displaystyle A^{2}\rightarrow A} ↑ 「対角線論法」という用語は、この種の列挙を指すのに使われることがありますが、カントールの対角線論法 とは直接関係ありません 。
参考文献 Steven Pigeon。 「ペア Lisi, Meri (2007). 「カントールペアリング関数に関するいくつかの考察」 . Le Matematiche . LXII : 55–65 . Regan, Kenneth W. (1992年12月). 「最小複雑度ペアリング関数」 . Journal of Computer and System Sciences 45 (3): 285–295 . doi : 10.1016/0022-0000(92)90027-G . ISSN 0022-0000 . Szudzik, Matthew (2006). "An Elegant Pairing Function" (PDF) . szudzik.com . 2011年11月25日のオリジナルからアーカイブ(PDF) . 2021年 8月16日 取得 . Szudzik, Matthew P. (2017年6月1日). 「ローゼンバーグ・ストロングペアリング関数」. arXiv : 1706.04129 [ cs.DM ]. Jech, Thomas (2006).集合論 . Springer Monographs in Mathematics (The Third Millennium ed.). Springer-Verlag. doi : 10.1007/3-540-44761-X . ISBN 3-540-44085-2 。ホップクロフト、ジョン・E. 、ウルマン、ジェフリー・D. (1979).オートマタ理論、言語、計算入門 版）. アディソン・ウェスリー. ISBN 0-201-02988-X 。スタイン、シャーマン K. (1999).数学：人工宇宙 （第3 版）. ドーバー出版. ISBN 9780486404509 。 
![{\displaystyle (\alpha ,\beta )\preccurlyeq (\gamma ,\delta ){\text{ 次のいずれかの場合 }}{\begin{cases}(\alpha ,\beta )=(\gamma ,\delta ),\\[4pt]\max(\alpha ,\beta )<\max(\gamma ,\delta ),\\[4pt]\max(\alpha ,\beta )=\max(\gamma ,\delta )\ {\text{かつ}}\ \alpha <\gamma ,{\text{ または }}\\[4pt]\max(\alpha ,\beta )=\max(\gamma ,\delta )\ {\text{かつ}}\ \alpha =\gamma \ {\text{かつ}}\ \beta <\delta .\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/945cfcf781cb970f8d6bf8fceea0fe4970ced082)
![{\displaystyle \operatorname {ElegantPair} [x,y]:={\begin{cases}y^{2}+x&{\text{if}}\ x<y,\\x^{2}+x+y&{\text{if}}\ x\geq y.\\\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4866db779177e64e3f5800671682b865b6381e37)
![{\displaystyle \operatorname {ElegantUnpair} [z]:={\begin{cases}\left\{z-\lfloor {\sqrt {z}}\rfloor ^{2},\lfloor {\sqrt {z}}\rfloor \right\}&{\text{if }}z-\lfloor {\sqrt {z}}\rfloor ^{2}<\lfloor {\sqrt {z}}\rfloor ,\\\left\{\lfloor {\sqrt {z}}\rfloor ,z-\lfloor {\sqrt {z}}\rfloor ^{2}-\lfloor {\sqrt {z}}\rfloor \right\}&{\text{if }}z-\lfloor {\sqrt {z}}\rfloor ^{2}\geq \lfloor {\sqrt {z}}\rfloor .\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/45f1d5e406fddda5ee9036b94e66c6407ad799cf)
![{\displaystyle \operatorname {Pair} [x,y]+c}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cf9579bfc8448dc3c797cc2b24016a0fa2bd9cb6)
