Church Encoding with specific function

본 글에서는 Church Encoding의 기본적 개념과 이를 특정한 함수로 구현할 때 발생할 수 있는 문제점을 다룬다.

 

1. Church Numeral이란

Church Numeral은 어떤 함수 $f$에 대해 자연수 $k$를 $f^k$로 표현하는 것이다.

2. Church Numeral의 사칙연산

Church Numeral은 페아노 공리계를 만족하며 자연수에 대한 사칙연산을 정의할 수 있다.

• successor: 함수 $g$가 자연수 $n$을 encode하면 $f\circ g$는 $f\circ f^n=f^{n+1}$이므로 $g$의 successor이다.
• 덧셈: 자연수 $n$과 $m$을 encode하는 함수 $g$, $h$에 대해 $g\circ h$는 $f^n \circ f^m=f^{n+m}$이므로 $n+m$을 encode한다. 즉, $g\circ h$는 $g$와 $h$의 합이다.
• 곱셈: 자연수 $n$과 $m$와 $n$을 encode하는 함수 $g$에 대해 $g^m$은 $(f^n)^m=f^{nm}$이므로 $nm$을 encode한다. 즉 $g^m$은 $g$에 자연수 $m$을 곱한 결과이다.
• predecessor: $f$의 역함수 $f^{-1}$와 2 이상의 자연수 $n$을 encode하는 함수 $g$에 대해 $f^{-1}\circ g=f^{-1}\circ f^n=f^{n-1}$이므로 $f^{-1}\circ g$은 $n-1$을 encode하며 $g$의 predecessor이다.
• 뺄셈: 자연수 $n,m(n>m)$을 encode하는 함수 $g$, $h$에 대해 $g\circ h^{-1}$은 $f^n\circ (f^m)^{-1}=f^{n-m}$이므로 $n-m$을 encode한다. 즉, $g\circ h^{-1}$은 $g$와 $h$의 차이다. 이를 통해 $0$과 음수의 encoding을 자연스럽게 정의할 수 있다.

3. 유한 집합과 Church Numeral

Church Numeral을 특정한 함수를 이용하여 구현할 때, 어떤 함수를 쓰는지와는 무관하게 같은 수는 같은 함수로 encode된다. 다만, 사용하는 함수에 따라 "다른 수는 항상 다른 함수로 encode된다"는 명제는 성립하지 않을 수 있다. 특히, 유한 집합 $S$에 대해 $f:S\Rightarrow S$는 $f^a= f^b$를 만족하는 서로 다른 자연수 $a,b$를 무한히 많이 갖는다. 이를 증명해보자.

Proof: $\exists a,b\in S : a\neq b \land f^a = f^b$ 

$S$의 각 원소를 정점으로 갖고, 간선 집합이 $\{x\rightarrow f(x) | x\in S\}$인 함수 $f:S\Rightarrow S$가 존재하는 그래프를 functional graph라고 한다. functional graph가 사이클을 갖지 않는다고 가정하면, 임의의 $x\in S$에 대해 집합 $\{x, f(x), f^2(x),\cdots,f^{n(S)}(x)\}$는 크기가 $n(S)+1$이며 $S$의 부분 집합이다. 이는 모순이므로 functional graph는 사이클을 적어도 하나 가진다. 또한 모든 정점의 outdegree는 정확히 1이므로 모든 사이클은 단순 사이클이라는 것도 확인할 수 있다.

즉 functional graph는 단순 사이클과 그 사이클의 정점을 루트로 하는 몇 개의 트리로 구성된 component를 하나 이상 가진다. 따라서 모든 사이클의 길이 $L_1, L_2,\cdots$의 최소공배수 $L$, 어떠한 자연수 $N$에 대해 $x\ge N$이면 $f^x=f^{x+L}$인 $N$이 존재하므로 위 명제는 참인 동시에 그러한 $a,b$는 무한히 많이 존재한다.

4. 무한 집합과 Church Numeral

그렇다면, 무한 집합에서 정의되는 함수는 이러한 문제에서 자유로운가? $f(x)=ix$와 이를 일반화한 $f(x)=e^{i\frac{2k\pi}{n}}x$는 무수히 많은 길이 $n$의 단순 사이클이 나타난다.

functional graph $f(x)=\alpha x$의 기본 단위체 (Constraint: $\alpha^n=1$)

이외의 예시로는 $f(x)=\sqrt{1-x^2}$이 있다. 위의 예시와는 다르게, 2개의 수가 사이클을 이루고 나머지 2개의 수가 사이클에 붙어 있는 꼴이다.

$a_{n+1}=f(a_n)$을 네 번 적용하는 다이어그램

functional graph $f(x)=\sqrt{1-x^2}$의 기본 단위체

두번째 예시인 $f(x)=\sqrt{1-x^2}$와 $f(x)=-\frac{1}{x}$ 등의 예시를 통해 길이가 2인 사이클을 구성하는 수들을 정의역으로 할 때 사용한 함수 $f$는 $y=x$에 대해 대칭임을 알 수 있다. 나아가, $f:\mathbb{R}\Rightarrow \mathbb{R}$의 모든 사이클의 길이가 2일 필요충분조건은 $f:S\Rightarrow S$가 $y=x$ 대칭이며 정의역 $T$에서 $f$와 동일한 $g:T\Rightarrow S$가 존재하는 만족하는 두 집합 $S$와 $T=\mathbb{R}\backslash S$가 존재한다는 것임을 확인할 수 있다.