재귀적 정의 문서 원본 보기

{{위키데이터 속성 추적}}

[[파일:KochFlake.svg|오른쪽|섬네일| [[코크 곡선|코흐 눈송이]]가 만들어지는 단계들(4단계). 다른 많은 [[프랙탈]] 과 마찬가지로 다음 단계는 재귀적 정의로 얻어진다.]]
[[수학]]과 [[컴퓨터 과학]]에서 '''재귀적 정의''' 또는 '''귀납적 정의'''는 [[집합]] 내의 다른 원소를 통해 그 집합의 [[원소 (수학)|원소]]를 정의할 때 사용된다<ref>{{서적 인용|url=https://linkinghub.elsevier.com/retrieve/pii/S0049237X08711200|제목=An Introduction to Inductive Definitions|성=Aczel|이름=Peter|날짜=1977|권=90|출판사=Elsevier|쪽=740|언어=en|doi=10.1016/s0049-237x(08)71120-0|isbn=978-0-444-86388-1}}</ref>. [[계승|팩토리얼]], [[자연수]], [[피보나치 수]], [[칸토어 집합]] 등을 재귀적으로 정의할 수 있다.

[[함수]]의 [[재귀|재귀적]] [[정의 (논리학)|정의]]는 어떤 원소에 대한 함수의 결과를 다시 원소로 삼는 함수로 정의한다. 예를 들어 [[계승]] 함수 {{수학|''n''!}}는 다음과 같이 정의된다.

: <math>\begin{align}
& 0! = 1. \\
& (n+1)! = (n+1) \cdot n!.
\end{align}</math>

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

재귀 정리는 이러한 정의가 실제로 유일한 함수를 정의한다고 말한다. 증명은 [[수학적 귀납법]]을 통해 유도된다.<ref>{{저널 인용|제목=On Mathematical Induction|저널=The American Mathematical Monthly|성=Henkin|이름=Leon|날짜=1960|권=67|호=4|쪽=323–338|doi=10.2307/2308975|issn=0002-9890|jstor=2308975}}</ref>

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

# 1은 집합 <math>\mathbb{N}</math>의 원소이다.
# ''n''이 <math>\mathbb{N}</math>의 원소이면 {{수학|''n'' + 1}}도 <math>\mathbb{N}</math>의 원소이다.
# <math>\mathbb{N}</math>은 (1)과 (2)를 [[논리곱|모두 만족]]하는 집합의 [[교집합]]이다.

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

재귀적 정의로 된 함수와 집합의 특성은 재귀적 정의를 따르는 귀납적 원리에 의해 증명될 수도 있다. 위의 자연수에 대한 정의에서 자연수의 특성은 계속 유지된다. 자연수 0(또는 1)이 자연수라는 특성을 가지고 있으면,  {{수학|''n'' + 1}}에 의해 특성이 유지가 되어 {{수학 변수|n}}도 자연수라는 특성이 유지가 된다. 따라서 위의 자연수에 대한 정의는 자연수에 대한 수학적 귀납의 원리를 직접적으로 내포하고 있다.<ref>{{서적 인용|url=https://linkinghub.elsevier.com/retrieve/pii/S0049237X08711200|제목=An Introduction to Inductive Definitions|성=Aczel|이름=Peter|날짜=1977|권=90|출판사=Elsevier|쪽=742|언어=en|doi=10.1016/s0049-237x(08)71120-0|isbn=978-0-444-86388-1}}</ref>

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

[[순환정의]]와 재귀적 정의의 차이점은, 재귀적 정의는 항상 ''재귀적 기초'' (정의 자체의 관점에서 정의되지 ''않고'' 정의를 충족하는 사례)를 가져야 하며 점화식의 다른 모든 경우는 어떤 의미에서 "터지지 말아야" 한다는 것이다.(즉, 다른 밧줄에서는 터지지 말아야 하는 것이다.<ref group="주">물론 점화식의 점화(漸化)는 그 점화(点火)가 아니다.</ref>) "더 단순한 경우에서만 반복"이라고도 알려진 규칙이다.<ref>{{웹 인용|url=https://www.cis.upenn.edu/~matuszek/cis554-2011/Pages/recursion.html|제목=All About Recursion|웹사이트=www.cis.upenn.edu|확인날짜=2019-10-24|archive-date=2019-08-02|archive-url=https://web.archive.org/web/20190802084457/http://www.cis.upenn.edu/~matuszek/cis554-2011/Pages/recursion.html|url-status=}}</ref>

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

재귀적 정의가 타당하다는 것(재귀적 정의가 고유한 함수를 가진다는 것)은 [[재귀|재귀정리]]로 알려진 집합론의 정리이며, 그 증명은 비자명(non-trivial)하다.<ref group="주">재귀 정리의 증명은 [https://www.jstor.org/stable/2308975?seq=1/analyze#page_scan_tab_contents ''On Mathematical Induction'' (1960) by Leon Henkin]를 참고하십시오.</ref> 함수의 정의역이 자연수인 경우 정의가 타당하기 위한 충분 조건은 {{수학|''f''(0)}}의 값(재귀적 기초)이 주어지고 {{수학|''n'' > 0}}에 대해 {{수학 변수|n}}에 관한 함수 {{수학|''f''(''n'')}}가 <math>f(0), f(1), \dots, f(n-1)</math>의 값을 가지는 알고리즘(점화식)이 있어야 한다는 것이다.

좀 더 일반적으로, 함수의 재귀적 정의는 [[초한 귀납법|초한재귀]] 원리를 사용하여 정의역이 [[정렬 순서|잘 정렬된 집합]]인 경우 만들어질 수 있다. 타당한 재귀적 정의를 만족하는 형식적 기준은 일반적인 경우에 더 복잡하다. 일반적인 증명의 큰 틀과 기준은 [[제임스 멍크레스]]의 ''Topology''에서 찾을 수 있다. 일반적인 재귀 정의의 특정한 경우(정의역은 잘 정렬된 집합 대신 양의 [[정수]]로 제한되는 경우)는 아래 문단에 나와있다.<ref name="Munkres">{{서적 인용|url=https://archive.org/details/topologyfirstcou00munk_0/page/68|제목=Topology, a first course|성=Munkres|이름=James|날짜=1975|판=1st|출판사=Prentice-Hall|위치=New Jersey|쪽=[https://archive.org/details/topologyfirstcou00munk_0/page/68 68, exercises 10 and 12]|isbn=0-13-925495-1}}</ref>

=== 재귀적 정의의 원리 ===
집합 {{수학 변수|A}}에 대하여 {{수학|''a''<sub>0</sub>}}를 {{수학 변수|A}}의 원소라 하자. {{수학 변수|ρ}}를 양의 정수의 비어 있지 않은 부분을 {{수학 변수|A}}의 원소인 {{수학 변수|A}}에 매핑하는 각 함수 {{수학 변수|f}} 에 할당하는 함수라고 하면, 다음과 같이 나타나는 유일한 함수 <math>h : \Z_+ \to A</math>가 존재한다.

: <math>\begin{align}
h(1) &= a_0 \\
h(i) &= \rho \left(h|_{\{1,2,\ldots,i-1\}}\right) \text{ for } i>1.
\end{align}</math>

== 재귀적 정의의 예시 ==

=== 초등함수 ===
[[덧셈]]은 다음과 같이 셈으로서 재귀적으로 정의된다.

: <math>\begin{align}
& 0 + a = a, \\
& (1+n) + a = 1 + (n+a).
\end{align}</math>

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

: <math>\begin{align}
& 0 \cdot a = 0, \\
& (1+n) \cdot a = a + n \cdot a.
\end{align}</math>

[[거듭제곱|지수]]는 다음과 같이 재귀적으로 정의된다.

: <math>\begin{align}
& a^0 = 1, \\
& a^{1+n} = a \cdot a^n.
\end{align}</math>

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

: <math>\begin{align}
& \binom{a}{0} = 1, \\
& \binom{1+a}{1+n} = \frac{(1+a)\binom{a}{n}}{1+n}.
\end{align}</math>

=== 소수 ===
[[소수 (수론)|소수]]의 집합은 다음을 만족하는 유일한 양의 정수 집합으로 정의될 수 있다.

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

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

=== 음이 아닌 짝수 ===
[[홀수와 짝수|짝수]]는 다음과 같이 구성하여 정의할 수 있다.

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

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

# "코너는 변호사다." 같이 [[명제]]를 나타내는 기호 {{수학 변수|p}}.
# "코너는 변호사가 임은 사실이 아니다."를 나타내는 {{수학|¬ ''p''}}와 같이, 뒤에 wff가 붙는 [[부정 (논리학)|부정]] 기호( {{수학|¬}} )
# "코너는 변호사이고, 메리는 음악을 좋아한다"를 나타내는 {{수학|''p'' ∧ ''q''}}와 같이, 두 개의 wff 사이에 들어오는 네가지 이진 [[논리 연산|접속사]] [[부정 (논리학)|부정]] ( {{수학|¬}} ), [[논리곱|곱]] ( {{수학|∧}} ), [[논리합|합]] ( {{수학|∨}} ), [[논리적 귀결|귀결]] ( {{수학|→}} )

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

*  곱({{수학|∧}}) 양 옆에 원자 wff {{수학 변수|p, q}}가 오므로 {{수학|''p'' ∧ ''q''}}는 좋은 형식이다.
* wff를 바꾸는 부정({{수학|¬}}) 뒤에 wff인 {{수학|''p'' ∧ ''q''}}가 오므로 {{수학|¬ (''p'' ∧ ''q'')}}는 좋은 형식이다.
* 곱({{수학|∧}}) 사이에 모두 wff인 {{수학|¬ ''p''}}와 {{수학|¬ ''q''}}가 있으므로 좋은 형식이다.

== 같이 보기 ==
* [[수학적 귀납법]]
* [[재귀 데이터 유형]]
* [[재귀]]
* [[구조적 귀납법]]

== 각주 ==
{{각주}}
=== 내용주 ===
{{각주|group="주"}}

== 관련 서적 ==
* {{서적 인용|제목=Discrete Structures, Logic, and Computability|성=Hein|이름=James L.|연도=2010|출판사=Jones & Bartlett|isbn=978-0-7637-7206-2|oclc=636352297}}

[[분류:재귀]]
[[분류:수리논리학]]
[[분류:정의 (논리학)]]