페어링 함수

이 글에는 여러 가지 문제가 있다.이 문제를 개선하거나 대화 페이지에서 토의하십시오.(이러한 템플릿 메시지를 제거하는 방법 및 시기 알아보기) 이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "페어링 기능" – 뉴스 · 신문 · 도서 · 학자 · JSTOR (2021년 8월) (이 템플릿 메시지를 제거하는 방법과 시기 학습) 이 글은 독자들에게 혼란스럽거나 불명확할 수 있다.특히 페어링 함수에 대한 표기법은 기사 전반에 걸쳐 일관성이 없다. 기사에 대해 명확하게 설명할 수 있도록 도와주십시오. 토크 페이지에서 이에 대한 논의가 있을 수 있다.(2021년 8월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

수학에서 페어링 함수는 두 개의 자연수를 하나의 자연수로 고유하게 인코딩하는 과정이다.^[1][2]null

정수와 합리적 숫자가 자연수와 동일한 카디널리티를 갖는다는 것을 증명하기 위해 설정된 이론에 어떤 페어링 함수를 사용할 수 있다.^[1]null

정의

페어링 함수는 바이어싱이다^{[verification needed]}.

${\displaystyle \pi :\mathb {N} \time \mathb {N} \to \mathb {N}.}$^[1][2]

보다 일반적으로, 세트 A의 페어링 함수는 A의 어떤 두 쌍의 원소가 A의 다른 원소와 연관되거나,^[3] $A{\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\$ A$^{2$}}에서 A로 편향되도록 A의 각 원소 쌍을 A의 원소로 매핑하는 기능이다.^[4]null

Hopcroft 및 Ulman 페어링 기능

Hopcroft and Ullman (1979) define the following pairing function: ${\displaystyle \langle i,j\rangle :={\frac {1}{2}}(i+j-2)(i+j-1)+i}$, where ${\displaystyle i,j\in \{1,2,3,\dots \}}$.^[1]

캔터 페어링 기능

캔터 페어링 기능은 원시 재귀 페어링 기능이다.

${\displaystyle \pi :\mathb {N} \time \mathb {N} \to \mathb {N} }$

에 의해 정의된.

${\displaystyle \pi(k_{1},k_{2}):={\frac{1}{2}}(k_{1}+k_{2})(k_{1}+k_{2}+1)+k_{2}}:$^{[1][필요하다]}

여기서 $k{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}\in \{0,}$ ${\displaystyle 1}$, ${\displaystyle 2}$,${\displaystyle 3}$,${\displaystyle \dots \}}$ ${\displaystyle k_{1},k_{2}\in$\{$0,$1,2$,3,\cHB$^[1]

또한 P ${\displaystyle a}$ ${\displaystyle i}$ r${\displaystyle }$[ ${\displaystyle x}$, ${\displaystyle y}$ ${\displaystyle ]}$= x ${\displaystyle \frac{{2\mathrm{}}^{}}{}}$+ ${\displaystyle \frac{3}{}}$+ ${\displaystyle \frac{2}{}}$ x + ${\displaystyle \frac{2}{}}$+ ${\displaystyle \frac{{y\mathrm{}}^{}}{}}$ + ${\displaystyle \frac{{}^{}}{}}$ ${\$로 표현할 수 있다.$={\frac {x^{2}+3x+2xy+y+y^{2$$}$$}}{2}}}$.^[3]

만약 k1<>또한 엄격하게 w.r.t. 각각의 주장, 그것은, 모든 k1, k1′, k2k2′∈ N{\displaystyle k_{1},k_{1}',k_{2},k_{2}'\in \mathbb{N}},;k 1′{\displaystyle k_{1}<, k_{1}'}, 그때(k1, k2)<>π(k1′, k2){\displaystyle \pi(k_{1},k_{2})& π 단조다.그것은, \pi(k_{1$}},k_{2$ 비슷하게 k < k ${\$π ( ,k ) (k 1, k ′){\$displaystyle \pi (k_{1}, k_{2$^{[citation needed]}

이것이 유일한 이차적 페어링 함수라는 말은 퓨터--로 알려져 있다.폴리야 정리.^{[1][verification needed]}이것이 유일한 다항식 페어링 함수인지 아닌지는 여전히 공개 질문이다.우리가₁ k와₂ k에 페어링 기능을 적용할 때 우리는 종종 결과 숫자를 ⟨k₁, k₂⟩^{[citation needed]}로 나타낸다.

이 정의는 캔터 튜플 함수에^{[citation needed]} 유도적으로 일반화될 수 있다.

${\displaystyle \pi ^{(n)}:\mathb {N} ^{n}\to \mathb {N}}}$

다음과 > 2[\$displaystyle n]2}$에 대해

${\displaystyle \pi ^{(n)}(k_{1},\ldots ,k_{n-1},k_{n}):=\pi(\pi ^{(n-1)}(k_{1},\ldots ,k_{n-1}),k_{n}}}$

위에서 정의한 쌍: $\pi {\displaystyle {}^{}}$( ${\displaystyle {}_{}{}^{}}$)${\displaystyle {}^{}}$( ${\displaystyle {\mathrm{k}}^{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{k\mathrm{}}_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle :=}$ ${\displaystyle \pi }$( k ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{k\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$)${\displaystyle }$. ${\displaystyle \pi ^{(2)}(k_{1}, k_{2}):$$=\pi(k_{1},k_{2}).$$}$^[1][2]

캔터 페어링 기능 반전

$z{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle N\mathbb{}}$ ${\$를) 임의의 자연수가 되도록$$ 한다.$우리$는 다음과 같은 고유한 값 x , $y$ N$${\$displaystyle$ x$,y\\in \mathb$ {N}이$$(가) 존재함을 보여줄 것이다.

${\displaystyle z=\pi(x,y)={\frac {(x+y+1)(x+y)}{2}}}+y}$

그래서 그 π은 되돌릴 수 없다.계산에서 일부 중간 값을 정의하는 것이 유용하다.

$w=x+y\!}$

${\displaystyle t={\frac {1}{2}}w(w+1)={\frac {w^{2}+w}{2}{2}{2}}}}$

${\displaystyle z=t+y\!}$

여기서 t는 w의 삼각형 번호다.2차 방정식을 풀면

${\displaystyle w^{2}+w-2t=0\!}$

w를 t의 함수로서 우리는 얻는다.

${\displaystyle w={\frac {{\sqrt{8t+1}:1}}-1}{2}}:}$

그것은 t가 음성이 아닌 실제일 때 엄격히 증가하고 연속적인 기능이다.이후

${\displaystyle t\leq z=t+y(w+1)={\frac {(w+1)^{2}+(w+1){2}}}}$

우리는 이해한다.

${\displaystyle w\leq {\frac {{\sqrt {8z+1}-1}{2}}({w+1})$

따라서

${\displaystyle w=\좌측\l바닥 {\frac {{\sqrt {8z+1}-1}{2}}:\우측\표시장치 .}$

여기서 ⌊ ⌋은 바닥 기능이다.따라서 z에서 x와 y를 계산하기 위해 다음과 같이 한다.

${\displaystyle w=\좌측\l바닥 {\frac {{\sqrt {8z+1}-1}{2}}:\우측\표시장치 }$

${\displaystyle t={\frac {w^{2}+w}{2}{2}}}}$

$y=z-t\!}$

$(\displaystyle x=w-y)\!}$

칸토어 페어링 기능은 수리가 가능하므로 일대일 및 그 이상이어야 한다.^{[3][additional citation(s) needed]}null

예

π(47, 32)를 계산하려면:

47 + 32 = 79,

79 + 1 = 80,

79 × 80 = 6320,

6320 ÷ 2 = 3160,

3160 + 32 = 3192,

그래서 π(47, 32) = 3192.null

π(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,

so1 w = 53;

53 + 1 = 54,

53 × 54 = 2862,

2862 ÷ 2 = 1431,

so t = 1431;

1432 − 1431 = 1,

so y = 1;

53 − 1 = 52,

따라서 x = 52, 따라서 π(52, 1) = 1432.^{[citation needed]}null

파생

대각선 진행인 칸토어의 페어링 기능의 그래픽 형태는 무한 시퀀스와 카운트 가능성으로 작업하는 데 있어 표준적인 트릭이다.^[a]이 대각선 모양의 함수의 대수적 규칙은 유도 방법을 사용하여 2차적 함수가 가장 간단한 것으로 판명될 다항식 범위에 대한 유효성을 검증할 수 있다.실제로, 이 같은 기법은 비행기를 열거하기 위한 다양한 계획에 대해 다른 많은 기능을 도출하기 위해 또한 따를 수 있다.null

페어링 함수는 일반적으로 유도적으로 정의될 수 있다. 즉, n번째 쌍이 주어진다면 (n+1)번째 쌍은 무엇인가?칸토어의 기능이 평면을 가로질러 대각선으로 진행되는 방식은 다음과 같이 표현할 수 있다.

${\displaystyle \pi }$( ${\displaystyle x}$, y${\displaystyle }$)${\displaystyle }$+ 1${\displaystyle }$= ${\displaystyle \pi }$( x${\displaystyle }$- ${\displaystyle 1}$,${\displaystyle \mathrm{y}}$+ ${\displaystyle 1}$) ${\displaystyle \pi (x,y)+1=\pi (x-1,y+1$

또한 이 함수는 제1 사분면의 경계에 도달했을 때 수행할 작업을 정의해야 한다. 캔터의 페어링 기능은 X 축으로 재설정되어 한 단계 더 나아가거나 대수적으로 다음과 같이 대각선 진행을 재개한다.

${\displaystyle \mathrm{\pi }}$( 0${\displaystyle ,}$ k${\displaystyle }$)${\displaystyle }$+ 1${\displaystyle }$= ${\displaystyle \pi }$(${\displaystyle \mathrm{k}}$+ ${\displaystyle 1}$,${\displaystyle }$0${\displaystyle }$) ${\displaystyle \pi (0,k)+1=\pi (k+1,0)}$.

또한 출발점, 즉 유도 방법의 초기 단계가 무엇이 될 것인가를 규정할 필요가 있다. ((0, 0) = 0.

이러한 조건에 적합할 수 있는 2차원 다항식이 있다고 가정한다(없다면, 더 높은 수준의 다항식을 시도하기만 하면 반복할 수 있다).일반적인 형태는 그때 이다.

${\displaystyle \pi }$( x${\displaystyle }$, ${\displaystyle y}$)${\displaystyle }$= ${\displaystyle {x\mathrm{}}^{}}$ ${\displaystyle {}^{}}$+ b ${\displaystyle {y\mathrm{}}^{}}$ ${\displaystyle {}^{}}$+ ${\displaystyle c}$ + ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$+ ${\displaystyle e}$ +${\displaystyle f}$ ${\displaystyle \pi (x,y)=ax^{2}+cxy+dx+ey+f$

초기 및 경계 조건을 연결하여 f = 0 및 다음을 얻으십시오.

${\displaystyle b}$ ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$+ ${\displaystyle \mathrm{e}}$ ${\displaystyle k}$+ 1${\displaystyle }$= a${\displaystyle }$( ${\displaystyle \mathrm{k}}$+ 1${\displaystyle {}^{}}$) ${\displaystyle 2{}^{}}$+ d (${\displaystyle \mathrm{k}}$+ 1${\displaystyle }$) ${\displaystyle bk^{2}+ek+1=a(k+1)^{2}+d(k+1$

그래서 우리는 우리의 k 조건에 맞출 수 있다.

b = a

d = 1-a

e = 1+a.

따라서 모든 매개변수는 c를 제외한 a의 용어로 작성될 수 있으며, 최종 방정식인 우리의 대각선 단계가 그것과 관련된다.

${\displaystyle {\regated}\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)+(1+a)(y+1)+(y+1)+(y+1)++(y+1)++(y+1)+(y+1)+(y+1)+1(y+1)+1).\end{정렬}}}$

항을 다시 확장하고 일치시켜 a 및 c에 대한 고정 값과 모든 모수를 가져오십시오.

a =1/2 = b = d

c = 1

e = 3/2

f = 0.

그러므로

${\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}}}$

칸토어 페어링 기능이며, 우리는 또한 유도를 통해 이것이 유도의 모든 조건을 만족한다는 것을 증명했다.^{[citation needed]}null

기타 페어링 기능

$기능{\displaystyle {}_{}}$ P ${\displaystyle {2\mathrm{}}_{}}$(${\displaystyle x}$ ,${\displaystyle y}$ ) ${\displaystyle :=}$ ${\displaystyle 2^{}}$ x${\displaystyle {}^{}}$( ${\displaystyle 2y}$ +${\displaystyle 1}$) - ${\displaystyle 1}${\$displaystyle P_{2}(x,y):=2^{x}(2y+1)-1}$은 쌍을 이루는 함수다$$.^[2]null

1990년에 Regan은 선형 시간 및 일정한 공간으로 계산할 수 있는 알려진 최초의 페어링 함수를 제안했다(이전에 알려진 예는 곱셈이 너무 심할 경우 선형 시간에만 계산될 수 있기 때문에 의심스럽다).^[5]실제로 이 페어링 함수와 그 역수 모두 실시간으로 작동하는 유한 상태 변환기로 계산할 수 있다.^{[5][clarification needed]}같은 논문에서 저자는 온라인에서 선형시간과 로그공간으로 계산할 수 있는 단조로운 페어링 기능 2개를 더 제안했는데, 첫 번째 기능도 0의 공간으로 오프라인에서 계산할 수 있다.^{[5][clarification needed]}null

2001년에 피용기는 비트 인터리빙을 기반으로 다음과 같이 재귀적으로 정의된 페어링 기능을 제안했다.

${\displaystyle <i,j>_{P}={\begin{case}T{{\text{}}i=j=0;\\<\lfloor i/2\rfloor,\lfloor >_{P}i_{0}j_{0}{{0}{\text}{}}}}\case}}}}}}}}$

여기서 $i{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$ 및 $j$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$은 각각 i와 j의 가장 유의미한 비트다.^{[1][verification needed]}null

2006년, Szudzik은 $E{\displaystyle }$ ${\displaystyle l}$ e ${\displaystyle g}$ ${\displaystyle a}$ n ${\displaystyle t}$ ${\displaystyle p}$ a ${\displaystyle i}$ ${\displaystyle r}$[ ${\displaystyle x}$, ${\displaystyle y]=}${ ${\displaystyle \begin{array}{l}{y\mathrm{}}^{}\end{array}}$2 + ${\displaystyle \begin{array}{l}x\end{array}}$ ${\displaystyle \begin{array}{l}만약\end{array}}$ x ${\displaystyle \begin{array}{l}\ne \end{array}}$ ${\displaystyle \begin{array}{l}\max \{,\end{array}}$ ${\displaystyle \begin{array}{l}y\end{array}}$ ${\displaystyle \begin{array}{l}\}\end{array}}$ ${\displaystyle \begin{array}{}x\\ {}^{}\end{array}}$ ${\displaystyle \begin{array}{l}{2\mathrm{}}^{}\end{array}}$+${\displaystyle \begin{array}{l}x\end{array}}$ ${\displaystyle \begin{array}{l}만약\end{array}}$ x${\displaystyle \begin{array}{l}\end{array}}$= ${\displaystyle \begin{array}{l}max\end{array}}$ = ${\displaystyle \begin{array}{l}\max \end{array}}$ ${\displaystyle \begin{array}{l},\end{array}}$ ${\displaystyle \begin{array}{l}y\end{array}}$ ${\displaystyle \begin{array}{l}\}\end{array}\begin{array}{}\end{array}}$, ${\displaystyle GrantPair[x,y]$라는 표현으로 정의되는 "더 우아한" 페어링 기능을 제안했다.={\begin{경우}y^{2}+x{\text{만약}}x\neq \max\{x,y\}\\x^{2}+x+y{\text{만약}}x=\max\{x,y\}\\\end{경우}},}은 오빠 있어 Ung의 표현 E나는 e를 사용하여 짝이 없는 수 있는 명확히 설명 r[z]:){{z−⌊ z⌋ 2,⌊ z⌋}p 만약 z−⌊ z⌋ 2<⌊ z⌋{⌊ z⌋, z−⌊ z⌋ 2− ⌊ z⌋ 만약 z−⌊ z⌋ 2. ≥$displaystyle AngelyUnpair[z]:$={\begin{경우}\{z-\lfloor{\sqrt{z}}\rfloor ^{2},\lfloor{\sqrt{z}}\rfloor)}{\text{만약}}z-\lfloor{\sqrt{z}}\rfloor ^{2}<, \lfloor{\sqrt{z}}\rfloor \\\{\lfloor{\sqrt{z}}\rfloor ,z-\lfloor{\sqrt{z}}\rfloor ^{2}-\lfloor{\sqrt{z}}\rfloor{\text{만약}}z-\lfloor{\sqrt{z}}\rfloor ^{2}\geq \lfloor{\sqrt{z}}\rfloor)}\end{경우}}}.[3]. (Quali반복적으로, 연속된 숫자를 정사각형의 가장자리를 따라 쌍에 할당한다.)^[3]이 페어링 기능은 SK 콤비네이터 미적분 식을 깊이별로 주문한다.^{[3][clarification needed]}이 방법은 ZFC의 무한$$ $추기경{\displaystyle }$ ${\displaystyle$\cappa $}$에 대한$$ $\kappa {\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$= ${\displaystyle \kappa }$ ${\displaystyle \$$mathb${$N$$}$개념의 ${\$ $\$$cappa$$}$에 대한 단순한$$ 적용이다.^[6]$\kappa {\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle \kappa }$ ${\displaystyle \kappa \time \kappa }$에 이진$$ 관계 정의

≼{\displaystyle \preccurlyeq} 다음well-ordering은 모든 요소 &lt고 싶다;κ{\displaystyle{}&lt합니다;그리고 그것은 κ 2)κ{\displaystyle\kappa ^{2}=\kappa를 암시하 \kappa}전임자}.(N×N, ≼){\displaystyle(\mathbb{N}\times \mathbb{N},\preccurlyeq)}isom은 다음과 같습니다. 나타나 있다.또는phic to${\displaystyle }$(${\displaystyle N\mathbb{}}$, ${\displaystyle ⩽}$) ${\displaystyle (\mathb {N} ,\leqslant )}.$ 위의$$ 페어링 함수는 증가 순서에 따른 정수 커플의 열거에 지나지 않는다.(또한 대화 참조:선택에 관한 타르스키의 정리#반전의 증명)null

메모들

참조