1. 개요
수학에서 재귀정리라고 하면 보통 집합론에서의 재귀정리(recursion theorem)와 푸앵카레 재귀정리(Poincaré recurrence theorem) 둘 중 하나를 지칭한다. 다만 이 둘의 영어 명칭이 약간 다르다는 것에 유의하자.2. 집합론에서의 재귀정리
2.1. 개요
집합론에서 말하는 재귀정리는 흔히 다음과 같은 정의를 말한다. (이 문서에서는 범자연수로 자연수가 정의되었다고 가정할 것이다.)임의의 집합 [math(X)]와 사상 [math(f : X \to X)], 그리고 [math(a \in X)]에 대하여, [math(g(0) = a)], [math(g(n^+) = f(g(n)))]을 만족하는 사상 [math(g : \N \to X)]가 유일하게 존재한다.
언뜻 보면 우리가 당연하다는 듯이 써 온 사실이긴 하지만, 수학에서 정말로 당연하다고 넘어갈 수 있는 것은 없기에, 이 재귀정리 역시 증명이 되어야 하는 대상이다. 그 꼴도 그렇고 증명을 봐도 알겠지만 수학적 귀납법이 이 정리의 핵심이라고 할 만하다.[1]
이 정리는 수학의 가장 기초적인 부분에서부터 중요한 역할을 수행한다. 자연수 문서에도 소개된 다음과 같은 덧셈의 정의를 보자.
함수 [math(+ : \N \times \N \to \N)]을 다음 두 성질을 만족하는 함수로 정의하자.
(A1’) 임의의 [math(n \in \N)]에 대하여 [math(+(n, 0) = n)],
(A2) 임의의 [math(m, n \in \N)]에 대하여 [math(+(m, n^+) = +(m, n)^+)].
이때 [math(+(m, n))]을 [math(m + n)]으로 표기할 수 있다.
(A1’) 임의의 [math(n \in \N)]에 대하여 [math(+(n, 0) = n)],
(A2) 임의의 [math(m, n \in \N)]에 대하여 [math(+(m, n^+) = +(m, n)^+)].
이때 [math(+(m, n))]을 [math(m + n)]으로 표기할 수 있다.
그런데 이 정의를 보면 다음과 같은 의문이 필연적으로 들 것이다. 저 성질을 만족하는 함수 [math(+)]는 과연 실제로 존재하는가? 게다가 존재하더라도 만약 저 두 성질을 만족하지만 서로 다른 함수들이 존재한다면 그 중 어느 것으로 덧셈을 정의해야 하는 것일까 하는 의문도 당연히 들 것이다. 재귀정리는 다행스럽게도 위 두 성질을 만족하는 함수가 존재하며 딱 하나 뿐임을 보장해 준다. 즉, 덧셈이 잘 정의되어 있다는 것을 재귀정리로부터 보일 수 있다는 것이다. 이를 증명하는 것은 재귀증명의 증명 아래에 두도록 하겠다.
비슷한 방법으로 같은 문서에 소개된 곱셈도 잘 정의된다는 것을 보일 수 있다.
위 정리는 다음과 같이 조금 더 확장시킬 수 있다.
임의의 집합 [math(X)]와 사상 [math(f : \N \times X \to X)], 그리고 [math(a \in X)]에 대하여, [math(g(0) = a)], [math(g(n^+) = f(n, g(n)))]을 만족하는 사상 [math(g : \N \to X)]가 유일하게 존재한다.
이렇게 확장된 정리를 가지고 흔히 점화식을 이용하여 정의하는 수열들이 항상 잘 정의되는 것들이라는 것을 보장할 수 있다.
아주 중요한 ‘수열’(?) 하나를 이 정리로 정의할 수 있다. 다음과 같이 정의되는 함수[2] [math(f : \N \times \mathcal{P}(\N) \to \mathcal{P}(\N))]를 생각해 보자. (여기서 [math(\mathcal{P}(\N))]는 [math(\N)]의 power set, 즉 [math(\N)]의 모든 부분집합들을 모은 집합이다.)
[math(\displaystyle f(n, A) = \{n\} \cup A)].
이제 재귀정리에 따라 다음과 같은 함수 [math(g : \N \to \mathcal{P}(\N))]이 유일하게 존재한다.
[math(\displaystyle g(0) = \emptyset, \;\;\; g(n^+) = \{n\} \cup g(n) \;\;\; (n \in \N))].
이는 다음과 같은 집합을 가장 최소한의 방법으로 잘 정의한 것이다.
[math(\N_0 = \emptyset, \N_1 = \{0\}, \cdots, \N_n = \{0, \cdots, n - 1\}, \cdots)].
이렇듯 재귀정리는 가장 기본적이고도 자연스러운 여러 정의들이 잘 정의되도록 보장해 주는 중요한 도구로 활용된다.
2.2. 증명
여기서는 위에서 제시한 보다 일반화된 정리를 증명하고자 한다. 이를 위해 먼저 다음 함수를 생각해 보자.[math(\displaystyle f' : \N \times X \to \N \times X)]
[math(\displaystyle \left( (n, x) \mapsto (n^+, f(n, x)) \right))].
이제, 집합 [math(\mathcal{M})]를 다음과 같이 정의하자.
[math(\displaystyle \mathcal{M} = \{ A \subseteq \N \times X \;|\; f'(A) \subseteq A, (0, a) \in A \})].
이 집합을 살펴보자. 먼저 당연히 [math((0, a) \in \N \times X)]이고 [math(f'(\N \times X) \subseteq \N \times X)]이므로 [math(\N \times X \in \mathcal{M})]이기에 [math(\mathcal{M})]는 공집합이 아니다. 여기서 [math(\Gamma = \bigcap \mathcal{M})]라고 하자. 그러면 정의에 따라 [math((0, a) \in \Gamma)]임을 바로 알 수 있고, 또한 다음을 얻을 수 있다.
[math(\displaystyle f'(\Gamma) = f'\left( \bigcap \mathcal{M} \right) = f'\left( \bigcap_{B \in \mathcal{M}} B \right) \subseteq \bigcap_{B \in \mathcal{M}} f'(B) \subseteq \bigcap_{B \in \mathcal{M}} B = \Gamma.)]
따라서 [math(\Gamma \in \mathcal{M})]이다. 이로부터 바로 알 수 있는 사실이 있는데, 이 [math(\Gamma)]가 [math(\mathcal{M})] 중에서 최소원이라는 것이다. 즉, 임의의 [math(A \in \mathcal{M})]에 대하여 [math(A \subseteq \Gamma)]이면 [math(A = \Gamma)]라는 것이다. 다른 말로, 그 어떤 [math(A \in \mathcal{M})]를 갖다 놔도 [math(A \subset \Gamma)]이면서 동시에 [math(A \ne \Gamma)]일 수 없다는 것이다.
이제부터 보일 것은 다름아닌 이 [math(\Gamma)]가 어떤 사상 [math(\N \to X)]의 그래프(graph)가 될 수 있다는 것이다. 이는 곧 모든 [math(n \in \N)]에 대하여 [math((n, x) \in \Gamma)]인 [math(x \in X)]가 유일하게 존재한다는 것을 보이는 것이다. 이를 위해 다음과 같은 집합 [math(S)]를 생각해 보자.[3]
[math(\displaystyle S = \left\{ n \in \N \;|\; \exist!x \in X \textrm{ s.t. } (n, x) \in \Gamma \right\})][4]
결국 보이고자 하는 것은 [math(S)]가 [math(\N)]과 같다는 것을 보이는 것과 같다는 것을 쉽게 알 수 있다. 이를 위해 페아노 공리계 중 수학적 귀납법에 해당하는 항목이 요구하는 조건을 [math(S)]가 만족하는지를 보여 보자.
- [math(0 \in S)]
[math(\displaystyle f’(\Gamma \setminus \{ (0, a’) \}) \subseteq f’(\Gamma) \subseteq \Gamma \cap \{ (0, a’) \}^c = \Gamma \setminus \{ (0, a’) \})].
물론 [math((0, a) \in \Gamma \setminus \{ (0, a’) \})]이다. 이로부터 [math(\Gamma \setminus \{ (0, a’) \} \in \mathcal{M})]임을 알 수 있다. 이는 [math(\Gamma)]가 [math(\mathcal{M})]의 최소원이라는 사실과 모순이다. 따라서 [math((0, a’) \in \mathcal{M})]일 수 없기에 [math(0 \in S)]임을 알 수 있다.
- [math(n \in S)]인 임의의 [math(n \in \N)]에 대하여 [math(n^+ \in S)]
편의 상 [math(y = f(n, x))]라고 하자. 이제 위와 마찬가지로 [math((n^+, y’) \in \Gamma)]이며 [math(y’ \ne y)]인 [math(y’ \in X)]가 존재한다고 가정해 보자. 이때 [math(f’(n, x’) = (n^+, y’))]이고 [math((n, x’) \in \Gamma)]인 [math(x’ \in X)]가 존재하는지 살펴 보자. 만약 그런 [math(x’)]이 있다면 [math(x)]의 유일성에 의하여 [math(x’ = x)]이어야 하는데, 그러면 다음이 성립한다.
[math(\displaystyle (n^+, y’) = f’(n, x’) = f’(n, x) = (n^+, y))].
이로부터 [math(y’ = y)]이어야 하는데, 이는 [math(y’)]에 대한 최초의 가정과 모순이다. 따라서 [math(f’(\Gamma) \subseteq \{ (n^+, y’) \}^c)]임을 알 수 있다. 이제 위와 마찬가지로 다음을 알 수 있다.
[math(\displaystyle f’(\Gamma \setminus \{ (n^+, y’) \}) \subseteq f’(\Gamma) \subseteq \Gamma \cap \{ (n^+, y’) \}^c = \Gamma \setminus \{ (n^+, y’) \})].
물론 [math((0, a) \in \Gamma \setminus \{ (n^+, y’) \})]이다. 이로부터 [math(\Gamma \setminus \{ (n^+, y’) \} \in \mathcal{M})]임을 알 수 있다. 이는 [math(\Gamma)]가 [math(\mathcal{M})]의 최소원이라는 사실과 모순이다. 따라서 [math((n^+, y’) \in \mathcal{M})]일 수 없기에 [math(n^+ \in S)]임을 알 수 있다.
결국 위 두 조건과 페아노 공리계로부터 [math(S = \N)]임을 알 수 있다. 앞서 말했듯이, 이로부터 [math(\Gamma)]를 그래프로 갖는 사상 [math(g : \N \to X)]를 찾을 수 있다.
이제 이 [math(g)]가 재귀정리에서 말하는 사싱임을 확인해 보자. 먼저, [math((0, a) \in \Gamma)]로부터 [math(g(0) = a)]임을 바로 알 수 있다. 한편, 임의의 [math(n \in \N)]에 대하여 [math((n^+, g(n^+)) = f’(n, g(n)) = (n^+, f(n, g(n))))]임을 [math(f’(\Gamma) \subseteq \Gamma)]임과 [math(S = \N)]로부터 바로 알 수 있으므로 [math(g(n^+) = f(n, g(n)))]임을 알 수 있다. 결국 우리가 찾는 [math(g)]가 최소 하나는 존재한다는 것을 보였다.
이제 [math(g)]가 유일하다는 것을 보이기 위하여 다음을 만족하는 사상 [math(g’ : \N \to X)]가 존재한다고 하자.
[math(\displaystyle g’(0) = a)],
[math(\displaystyle g’(n^+) = f(n, g(n)))].
여기서 다음을 정의하자.
[math(\displaystyle S’ = \{ n \in \N \;|\; g’(n) = g(n) \})].
[math(g)]와 [math(g’)]의 정의에 따라 당연히 [math(0 \in S’)]이다. 이제 임의의 [math(n \in S’)]을 생각하자. 그러면 [math(g’(n) = g(n))]이다. 이로부터 다음을 알 수 있다.
[math(\displaystyle g’(n^+) = f(n, g’(n)) = f(n, g(n)) = g(n^+))]
따라서 [math(n^+ \in S’)]이다. 이제 다시 한 번 페아노 공리계에 따라 [math(S’ = \N)]이고, 따라서 [math(g’ = g)]임을 얻게 된다. 이렇게 해서 주어진 조건을 만족하는 [math(g)]가 유일하게 존재한다는 것을 밝혔다.
2.3. 자연수 덧셈의 존재성 및 유일성 증명
위에서 예고한 대로 재귀정리로부터 덧셈이 잘 정의된다는 것을 증명하겠다.먼저 익숙치 않은 독자들의 이해를 위해 [math(p: \N \to \N)] ([math(p(n) = n^+)])이라고 정의된 함수 [math(p)]를 생각해 보도록 하겠다.[5] 그러면, 각 [math(m \in \N)]에 대하여 다음을 만족하는 함수 [math(+_m : \N \to \N)]이 유일하게 존재한다는 것을 재귀정리로부터 바로 알 수 있다.
- [math(\displaystyle +_m(0) = m)],
- [math(\displaystyle +_m(n^+) = p(+_m(n)))].
[math(\displaystyle +(m, n) = +_m(n) \;\;\; (m, n \in \N))].
조금 더 구체적으로, 이는 [math(G = \bigcup_{m \in \N} \{ (n, +_m(n)) \;|\; n \in \N \})]을 정의한 다음, [math(\N \times (\N \times \N) \to (\N \times \N) \times \N)] ([math((a, (b, c)) \mapsto ((a, b), c))])로 정의되는 함수 아래에서 [math(\N \times G)]의 상(image)을 그래프로 가지는 함수 [math(+ : \N \times \N \to \N)]을 정의하는 것으로 수행할 수 있다. 그러면 모든 [math(n \in \N)]에 대하여
[math(\displaystyle +(n, 0) = +_n(0) = n)],
[math(\displaystyle +(m, n^+) = +_m(n^+) = +_m(n)^+ = +(m, n)^+)]
이므로 함수 [math(+)]는 우리가 원하는 성질들을 모두 만족한다.
한편, 여기서 (A1’), (A2)를 만족하는 함수 [math(+’ : \N \times \N \to \N)]가 따로 주어져 있다고 가정하자. 여기서 각 [math(m \in \N)]에 대하여 [math(+’_m(n) = +’(m, n))]으로 정의되는 함수 [math(+’_m : \N \times \N)]을 생각해 보자. 이제 (A1’), (A2)에 의하여
[math(\displaystyle +’_m(0) = +’(m, 0) = m)],
[math(\displaystyle +’_m(n^+) = +’(m, n^+) = +’(m, n)^+ = +’_m(n)^+)]
임을 알 수 있는데, 재귀정리가 말해주는 유일성으로 인하여 모든 [math(m \in \N)]에 대해 [math(+’_m = +_m)]임을 알 수 있다. 이로부터 곧 모든 [math(m, n \in \N)]에 대하여
[math(\displaystyle +’(m, n) = +’_m(n) = +_m(n) = +(m, n))]
이고, 따라서 [math(+’ = +)]임을 알게 되어 [math(+)]의 유일성 또한 보일 수 있다.
3. 푸앵카레 재귀정리
[1] 이런 재귀적인 절차들은 모두 다 수학적 귀납법으로 갈음이 된다.[2] 함수라는 용어 대신 사상(map)이 더 어울리지 않을까 할 수 있지만, 이 문서에서는 조금 더 친숙한 느낌을 주기 위해 함수라는 용어만 사용하도록 하겠다.[3] 여기서부터 보이는 것은 사실 그냥 수학적 귀납법을 쓰는 것이다. 여기서는 재귀정리가 자연수의 덧셈 같은 아주 기본적인 정의 이전에 증명되어야 하는 정리임을 감안하여 페아노 공리계의 원형을 최대한 살려서 수학적 귀납법을 쓰는 방식을 소개하고자 한다.[4] 즉, [math((n, x) \in \Gamma)]를 만족하는 [math(x \in X)]가 유일하게 존재하는 [math(n)]의 집합인 것이다.[5] 애초부터 페아노 공리계에서 [math(n^+)]를 정의하겠다는 것 자체가 어떤 함수 [math(\N \to \N)] ([math(\N \ni n \mapsto n^+)])를 정의하겠다는 것과 같은 말이다. 그래서 해당 함수는 페아노 공리계를 생각한 순간부터 이미 주어져 있던 셈이다. 거꾸로 보면, 이미 저 함수 [math(p)]는 주어져 있고, [math(p(n))]을 [math(n^+)]로도 쓰고 있었다는 것이나 다름 없다. 다만 수학 전공자가 아닌 사람들에게는 자연수 문서에 서술된 페아노 공리계를 먼저 접하고 나서 사실 모든 게 원래 함수였다는 식의 서술을 마주하였을 때 혼동을 받을 수 있으리라 예상하여, 이런 식으로 서술하게 된 것이다.