2つの数値を1つの数値に一意にマッピングする関数
数学 において 、 ペアリング関数とは、2 つの 自然数を 1 つの自然数に
一意にエンコードするプロセスです。
集合論 では、任意のペアリング関数を使用して、 整数 と 有理数が 自然数と同じ 基数 を持つことを証明できます 。 [1]
意味 ペアリング関数は 一対一 で ある
π :
いいえ
×
いいえ
→
いいえ
。
{\displaystyle \pi:\mathbb{N}\times\mathbb{N}\to\mathbb{N}.}
一般化 より一般的には、集合上のペアリング関数 とは、 の各要素のペアを の要素に写像する関数で あり、 の任意の2つの要素のペアは の異なる要素に関連付けられ 、 [a] またはから へ の一対一対応である 。
あ
{\displaystyle A}
あ
{\displaystyle A}
あ
{\displaystyle A}
あ
{\displaystyle A}
あ
{\displaystyle A}
あ
2
{\displaystyle A^{2}}
あ
{\displaystyle A}
ドメインから抽象化する代わりに、ペアリング関数のアリティを一般化することもできます。つまり、n-項一般化カントールペアリング関数が存在します 。
いいえ
{\displaystyle \mathbb {N} }
ホップクロフトとウルマンのペアリング関数 HopcroftとUllman（1979）は、次のペアリング関数を定義しています。 ここで、です 。 [7] これは、以下のカンターペアリング関数と同じですが、0を除外するようにシフトされています（つまり 、、、 および ）。
⟨
i
,
j
⟩
:=
1
2
(
i
+
j
−
2
)
(
i
+
j
−
1
)
+
i
{\displaystyle \langle i,j\rangle :={\frac {1}{2}}(i+j-2)(i+j-1)+i}
i
,
j
∈
{
1
,
2
,
3
,
…
}
{\displaystyle i,j\in \{1,2,3,\dots \}}
i
=
k
2
+
1
{\displaystyle i=k_{2}+1}
j
=
k
1
+
1
{\displaystyle j=k_{1}+1}
⟨
i
,
j
⟩
−
1
=
π
(
k
2
,
k
1
)
{\displaystyle \langle i,j\rangle -1=\pi (k_{2},k_{1})}
カンターペアリング関数 カントールペアリング関数は、自然数のペアごとに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
{\displaystyle \pi (k_{1},k_{2}):={\frac {1}{2}}(k_{1}+k_{2})(k_{1}+k_{2}+1)+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}')}
これが唯一の二次ペアリング関数であるという主張は、 フュター・ポリア定理 として知られている。 [9] これが唯一の多項式ペアリング関数であるかどうかはまだ未解決の問題である。ペアリング関数を k 1 と k 2 に適用する場合、結果の数はしばしば ⟨ k 1 , k 2 ⟩ と表記される。 [ 要出典 ]
この定義はカントール組関数 に帰納的に一般化できる [ 要出典 ]
π
(
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}).}
カントールペアリング関数の反転 を任意の自然数とします。 次のような
一意の値が存在することを示します。
z
∈
N
{\displaystyle z\in \mathbb {N} }
x
,
y
∈
N
{\displaystyle x,y\in \mathbb {N} }
z
=
π
(
x
,
y
)
=
(
x
+
y
+
1
)
(
x
+
y
)
2
+
y
{\displaystyle z=\pi (x,y)={\frac {(x+y+1)(x+y)}{2}}+y}
したがって関数 π(x, y) は逆関数である。計算中にいくつかの中間値を定義すると便利である。
w
=
x
+
y
{\displaystyle w=x+y\!}
t
=
1
2
w
(
w
+
1
)
=
w
2
+
w
2
{\displaystyle t={\frac {1}{2}}w(w+1)={\frac {w^{2}+w}{2}}}
z
=
t
+
y
{\displaystyle z=t+y\!}
ここで tは w の 三角数 である。 二次方程式 を解くと
w
2
+
w
−
2
t
=
0
{\displaystyle w^{2}+w-2t=0\!}
w を t の関数として 表すと 、
w
=
8
t
+
1
−
1
2
{\displaystyle w={\frac {{\sqrt {8t+1}}-1}{2}}}
これはt が非負の実数である
とき、厳密に増加する連続関数である。
t
≤
z
=
t
+
y
<
t
+
(
w
+
1
)
=
(
w
+
1
)
2
+
(
w
+
1
)
2
{\displaystyle t\leq z=t+y<t+(w+1)={\frac {(w+1)^{2}+(w+1)}{2}}}
それは分かる
w
≤
8
z
+
1
−
1
2
<
w
+
1
{\displaystyle w\leq {\frac {{\sqrt {8z+1}}-1}{2}}<w+1}
そしてこうして
w
=
⌊
8
z
+
1
−
1
2
⌋
.
{\displaystyle w=\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor .}
ここで、 ⌊ ⌋は 床関数 です 。したがって、 z から x と y を 計算するには、次のようにします。
w
=
⌊
8
z
+
1
−
1
2
⌋
{\displaystyle w=\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor }
t
=
w
2
+
w
2
{\displaystyle t={\frac {w^{2}+w}{2}}}
y
=
z
−
t
{\displaystyle y=z-t\!}
x
=
w
−
y
.
{\displaystyle x=w-y.\!}
カントールペアリング関数は可逆なので、 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 、 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]この対角関数の代数規則は、 帰納法を 用いて、一連の多項式（その中で最も単純なのは2次式である）に対する妥当性を検証すること ができる。実際、この同じ手法を用いて、平面を列挙するさまざまな方式に対して、任意の数の他の関数を導出することもできる。
ペアリング関数は通常、帰納的に定義できます。つまり、 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
)
=
a
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
=
a
(
k
+
1
)
2
+
d
(
k
+
1
)
{\displaystyle bk^{2}+ek+1=a(k+1)^{2}+d(k+1)}
、 k 個の項を
一致させて
b = a d = 1- a ｅ ＝１＋ ａ 。 したがって、 c を除くすべてのパラメータは a で表すことができ 、それらを関連付ける最終的な方程式、つまり対角ステップが得られます。
π
(
x
,
y
)
+
1
=
a
(
x
2
+
y
2
)
+
c
x
y
+
(
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
)
.
{\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 1 = 1 です e = 3 / 2 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}}}
はカントールのペアリング関数であり、導出を通してこれが帰納法の条件をすべて満たしていることも示した。 [ 要出典 ]
その他のペアリング機能 この関数は ペアリング関数です。
P
2
(
x
,
y
)
:=
2
x
(
2
y
+
1
)
−
1
{\displaystyle P_{2}(x,y):=2^{x}(2y+1)-1}
1990 年に、Regan は、線形時間 と定数空間で 計算可能な最初のペアリング関数を提案しました(以前の既知の例は 、乗算が できる 場合にのみ線形時間で計算できますが、これは疑わしいです)。実際、このペアリング関数とその逆関数は、実時間で実行される有限状態トランスデューサで計算できます。 [ 説明が必要 ] 同じ論文で、著者は、線形時間と 対数空間 で オンラインで計算 できる 2 つの単調なペアリング関数をさらに提案しました。最初のペアリング関数は、オフラインでもゼロ空間で計算できます。 [ 説明が必要 ]
2001 年に、ピジョンはビットインターリーブ に基づくペアリング関数を提案しました 。これは次のように再帰的に定義されます。
⟨
i
,
j
⟩
P
=
{
T
if
i
=
j
=
0
;
⟨
⌊
i
/
2
⌋
,
⌊
j
/
2
⌋
⟩
P
:
i
0
:
j
0
otherwise,
{\displaystyle \langle i,j\rangle _{P}={\begin{cases}T&{\text{if}}\ i=j=0;\\\langle \lfloor i/2\rfloor ,\lfloor j/2\rfloor \rangle _{P}:i_{0}:j_{0}&{\text{otherwise,}}\end{cases}}}
ここで 、およびはそれぞれ i と j の 最下位ビット である 。 [ より良い情報源が必要 ]
i
0
{\displaystyle i_{0}}
j
0
{\displaystyle j_{0}}
2006 年に、Szudzik は次の式で定義される「よりエレガントな」ペアリング関数を提案しました。
ElegantPair
[
x
,
y
]
:=
{
y
2
+
x
if
x
<
y
,
x
2
+
x
+
y
if
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}}}
これは次の式を使用して対にすることができます:
ElegantUnpair
[
z
]
:=
{
{
z
−
⌊
z
⌋
2
,
⌊
z
⌋
}
if
z
−
⌊
z
⌋
2
<
⌊
z
⌋
,
{
⌊
z
⌋
,
z
−
⌊
z
⌋
2
−
⌊
z
⌋
}
if
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}}}
（定性的には、正方形の辺に沿ってペアに連続した番号を割り当てます。）このペアリング関数は、 SKコンビネータ計算 式を深さ順に並べます。 [ 説明が必要 ] この方法は、ほとんどの集合論の教科書に記載されているアイデア
の単なる応用であり、 [12] ZFC の 任意の無限基数に対して
確立するために使用されます 。 二項関係
で定義します
N
{\displaystyle \mathbb {N} }
κ
2
=
κ
{\displaystyle \kappa ^{2}=\kappa }
κ
{\displaystyle \kappa }
κ
×
κ
{\displaystyle \kappa \times \kappa }
(
α
,
β
)
≼
(
γ
,
δ
)
if either
{
(
α
,
β
)
=
(
γ
,
δ
)
,
max
(
α
,
β
)
<
max
(
γ
,
δ
)
,
max
(
α
,
β
)
=
max
(
γ
,
δ
)
and
α
<
γ
,
or
max
(
α
,
β
)
=
max
(
γ
,
δ
)
and
α
=
γ
and
β
<
δ
.
{\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 \preccurlyeq }
は、すべての要素に先行要素がある整列要素であることが示され 、これは を意味する 。したがって、 は と同型であり 、上記のペアリング関数は整数のペアを昇順に列挙したものに他ならない。 [c]
<
κ
{\displaystyle {}<\kappa }
κ
2
=
κ
{\displaystyle \kappa ^{2}=\kappa }
(
N
×
N
,
≼
)
{\displaystyle (\mathbb {N} \times \mathbb {N} ,\preccurlyeq )}
(
N
,
⩽
)
{\displaystyle (\mathbb {N} ,\leqslant )}
引用
注記
^ つまり、 からの 注入 です。
A
2
→
A
{\displaystyle A^{2}\rightarrow A}
^ 「対角線上の議論」という用語は、このタイプの列挙を指すために使用されることもありますが、 カントールの対角線上の議論 とは直接関係が ありません 。 [ 要出典 ] ^ トーク:選択に関するタルスキーの定理#逆定理の証明 も参照してください 。
参考文献 Steven Pigeon。「ペアリング関数」 。MathWorld 。 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. {{cite journal}}: CS1 maint: date and year (link)Szudzik, Matthew (2006). 「エレガントなペアリング関数」 (PDF) . szudzik.com . 2011年11月25日時点のオリジナルより アーカイブ (PDF) . 2021年 8月16日 閲覧 。 Szudzik, Matthew P. (2017 年 6 月 1 日). 「Rosenberg-Strong ペアリング関数」. arXiv : 1706.04129 [cs.DM]. ジェック、トーマス (2006)。 集合論 。シュプリンガー数学モノグラフ（第三千年紀版）。シュプリンガー出版。doi : 10.1007 /3-540-44761- X。ISBN 3-540-44085-2 。 ホップクロフト、ジョン E.、ウルマン、ジェフリー D. (1979)。 オートマトン理論、言語、計算入門 (第 1 版)。アディソン ウェスレー 。ISBN 0-201-02988-X 。 スタイン、シャーマン K. (1999)。 数学：人工宇宙 （第 3 版）。ドーバー 。ISBN 9780486404509 。 
![{\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 \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 (\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{and}}\ \alpha <\gamma ,{\text{ または}}\\[4pt]\max(\alpha ,\beta )=\max(\gamma ,\delta )\ {\text{and}}\ \alpha =\gamma \ {\text{and}}\ \beta <\delta .\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/945cfcf781cb970f8d6bf8fceea0fe4970ced082)
