재귀적 정의

수학과 컴퓨터 과학에서 재귀적 정의 또는 귀납적 정의는 집합 내의 다른 원소를 통해 그 집합의 원소를 정의할 때 사용된다^[1]. 팩토리얼, 자연수, 피보나치 수, 칸토어 집합 등을 재귀적으로 정의할 수 있다.

함수의 재귀적 정의는 어떤 원소에 대한 함수의 결과를 다시 원소로 삼는 함수로 정의한다. 예를 들어 계승 함수 $n!$ 는 다음과 같이 정의된다.

{\begin{aligned}&0!=1.\\&(n+1)!=(n+1)\cdot n!.\end{aligned}}

이 정의는 모든 자연수 $n$ 에 대해 타당하다. 위 식에서 어떠한 $n$ 도 풀어쓰면 결국 0!=1이라는 재귀의 기초로 도달하기 때문이다. 이 정의는 거꾸로 올라가서 함수의 값을 계산하는 것으로도 생각할 수도 있다. 즉, $n!$ 은 $n = 0$ 부터 시작하여 $n = 1, 2, 3$ 으로 올라가는 것으로 계산할 수 있다.

재귀 정리는 이러한 정의가 실제로 유일한 함수를 정의한다고 말한다. 증명은 수학적 귀납법을 통해 유도된다.^[2]

집합의 귀납적 정의는 집합의 다른 원소를 통해 집합의 원소를 기술한다. 예를 들어, 자연수 집합 $\mathbb {N}$ 을 통해 자연수를 귀납적으로 정의할 때 다음과 같이 정의한다.

1은 집합 $\mathbb {N}$ 의 원소이다.
n이 $\mathbb {N}$ 의 원소이면 $n + 1$ 도 $\mathbb {N}$ 의 원소이다.
$\mathbb {N}$ 은 (1)과 (2)를 모두 만족하는 집합의 교집합이다.

위 정의에서 (1)과 (2)를 동시에 만족하는 집합은 유일하지 않다. 집합 ${1, 2, 3, 4, 5, \dots$ }뿐만 아니라 ${1, 1.649, 2, 2.649, 3, 3.649, \dots$ } 역시 위의 두 정의를 충족한다. (3)을 통해 이러한 자연수가 아닌 수가 있는 집합을 없애 자연수 집합을 정의한다. 이 정의는 + 연산이 정의되어 있다고 가정한 상태에서 집합 $\mathbb {N}$ 이 더 큰 집합(예: 실수집합)에 포함되어 있다고 가정한다.(대각선 논법)

재귀적 정의로 된 함수와 집합의 특성은 재귀적 정의를 따르는 귀납적 원리에 의해 증명될 수도 있다. 위의 자연수에 대한 정의에서 자연수의 특성은 계속 유지된다. 자연수 0(또는 1)이 자연수라는 특성을 가지고 있으면, $n + 1$ 에 의해 특성이 유지가 되어 $n$ 도 자연수라는 특성이 유지가 된다. 따라서 위의 자연수에 대한 정의는 자연수에 대한 수학적 귀납의 원리를 직접적으로 내포하고 있다.^[3]

재귀적 정의의 형태

대부분의 재귀적 정의에는 재귀의 기초(첫째항)와 점화식이 존재한다.

순환정의와 재귀적 정의의 차이점은, 재귀적 정의는 항상 재귀적 기초 (정의 자체의 관점에서 정의되지 않고 정의를 충족하는 사례)를 가져야 하며 점화식의 다른 모든 경우는 어떤 의미에서 "터지지 말아야" 한다는 것이다.(즉, 다른 밧줄에서는 터지지 말아야 하는 것이다.^{[주 1]}) "더 단순한 경우에서만 반복"이라고도 알려진 규칙이다.^[4]

순환 정의에는 재귀적 기초가 없을 수 있으며 함수의 다른 값이 아닌 스스로의 값을 통해서 함수 값을 정의할 수도 있다. 이렇게 정의하면 무한 회귀로 이어진다.

재귀적 정의가 타당하다는 것(재귀적 정의가 고유한 함수를 가진다는 것)은 재귀정리로 알려진 집합론의 정리이며, 그 증명은 비자명(non-trivial)하다.^{[주 2]} 함수의 정의역이 자연수인 경우 정의가 타당하기 위한 충분 조건은 $f (0)$ 의 값(재귀적 기초)이 주어지고 $n > 0$ 에 대해 $n$ 에 관한 함수 $f (n)$ 가 $f(0),f(1),\dots ,f(n-1)$ 의 값을 가지는 알고리즘(점화식)이 있어야 한다는 것이다.

좀 더 일반적으로, 함수의 재귀적 정의는 초한재귀 원리를 사용하여 정의역이 잘 정렬된 집합인 경우 만들어질 수 있다. 타당한 재귀적 정의를 만족하는 형식적 기준은 일반적인 경우에 더 복잡하다. 일반적인 증명의 큰 틀과 기준은 제임스 멍크레스의 Topology에서 찾을 수 있다. 일반적인 재귀 정의의 특정한 경우(정의역은 잘 정렬된 집합 대신 양의 정수로 제한되는 경우)는 아래 문단에 나와있다.^[5]

재귀적 정의의 원리

집합 $A$ 에 대하여 $a 0$ 를 $A$ 의 원소라 하자. $ρ$ 를 양의 정수의 비어 있지 않은 부분을 $A$ 의 원소인 $A$ 에 매핑하는 각 함수 $f$ 에 할당하는 함수라고 하면, 다음과 같이 나타나는 유일한 함수 $h:\mathbb {Z} _{+}\to A$ 가 존재한다.

{\begin{aligned}h(1)&=a_{0}\\h(i)&=\rho \left(h|_{\{1,2,\ldots ,i-1\}}\right){\text{ for }}i>1.\end{aligned}}

재귀적 정의의 예시

초등함수

덧셈은 다음과 같이 셈으로서 재귀적으로 정의된다.

{\begin{aligned}&0+a=a,\\&(1+n)+a=1+(n+a).\end{aligned}}

곱셈은 다음과 같이 재귀적으로 정의된다.

{\begin{aligned}&0\cdot a=0,\\&(1+n)\cdot a=a+n\cdot a.\end{aligned}}

지수는 다음과 같이 재귀적으로 정의된다.

{\begin{aligned}&a^{0}=1,\\&a^{1+n}=a\cdot a^{n}.\end{aligned}}

이항 계수는 다음과 같이 재귀적으로 정의될 수 있다.

{\begin{aligned}&{\binom {a}{0}}=1,\\&{\binom {1+a}{1+n}}={\frac {(1+a){\binom {a}{n}}}{1+n}}.\end{aligned}}

소수

소수의 집합은 다음을 만족하는 유일한 양의 정수 집합으로 정의될 수 있다.

1은 소수이다.
다른 양의 정수는 자신보다 작은 1이 아닌 소수들로 나누어지지 않을 때만 소수이다.

정수 1은 소수의 재귀적 기초다. 이 정의에 따라 더 큰 정수 $X$ 의 소수성을 확인하려면 1 과 $X$ 사이의 모든 정수의 소수성을 알아야 하며 이는 이 정의에 의해 잘 정의된다.

음이 아닌 짝수

짝수는 다음과 같이 구성하여 정의할 수 있다.

0은 음수가 아닌 짝수의 집합 $E$ 의 원소이다.
집합 $E$ 의 임의의 원소 $x$ 에 대해 $x + 2$ 는 $E$ 의 원소이다.
위 두 조건으로 얻어지지 않는 것은 $E$ 의 원소가 아니다.

정형 논리식

논리나 컴퓨터 프로그래밍에서 재귀적 정의를 자주 찾아볼 수 있다. 예를 들어, 정형 논리식(wff)은 다음과 같이 정의될 수 있다.

"코너는 변호사다." 같이 명제를 나타내는 기호 $p$ .
"코너는 변호사가 임은 사실이 아니다."를 나타내는 $\neg p$ 와 같이, 뒤에 wff가 붙는 부정 기호( $\neg$ )
"코너는 변호사이고, 메리는 음악을 좋아한다"를 나타내는 $p \land q$ 와 같이, 두 개의 wff 사이에 들어오는 네가지 이진 접속사 부정 ( $\neg$ ), 곱 ( $\land$ ), 합 ( $\lor$ ), 귀결 ( $\to$ )

이런 재귀적 정의는 특정한 기호열이 "좋은 형식"인지 아닌지를 판단하는데 사용할 수 있다는게 가치가 있다.

곱( $\land$ ) 양 옆에 원자 wff $p, q$ 가 오므로 $p \land q$ 는 좋은 형식이다.
wff를 바꾸는 부정( $\neg$ ) 뒤에 wff인 $p \land q$ 가 오므로 $\neg (p \land q)$ 는 좋은 형식이다.
곱( $\land$ ) 사이에 모두 wff인 $\neg p$ 와 $\neg q$ 가 있으므로 좋은 형식이다.

같이 보기

각주

↑ Aczel, Peter (1977). 《An Introduction to Inductive Definitions》 (영어) 90. Elsevier. 740쪽. doi:10.1016/s0049-237x(08)71120-0. ISBN 978-0-444-86388-1.
↑ Henkin, Leon (1960). “On Mathematical Induction”. 《The American Mathematical Monthly》 67 (4): 323–338. doi:10.2307/2308975. ISSN 0002-9890. JSTOR 2308975.
↑ Aczel, Peter (1977). 《An Introduction to Inductive Definitions》 (영어) 90. Elsevier. 742쪽. doi:10.1016/s0049-237x(08)71120-0. ISBN 978-0-444-86388-1.
↑ “All About Recursion”. 《www.cis.upenn.edu》. 2019년 8월 2일에 원본 문서에서 보존된 문서. 2019년 10월 24일에 확인함.
↑ Munkres, James (1975). 《Topology, a first course》 1판. New Jersey: Prentice-Hall. 68, exercises 10 and 12쪽. ISBN 0-13-925495-1.

내용주

↑ 물론 점화식의 점화(漸化)는 그 점화(点火)가 아니다.
↑ 재귀 정리의 증명은 On Mathematical Induction (1960) by Leon Henkin를 참고하십시오.