수학적 귀납법

• 상위 항목 : 수학 관련 정보. 논리학 관련 정보

1 수학적 귀납법

귀납추리와 혼동할 수 있겠지만, 엄밀히 말하면 연역법의 일종이다. 증명 과정이 타당하다면 결론 역시 반드시 타당하기 때문에 완전귀납법이라고도 한다.

자연수에 관한 명제 [math] P\left(n\right)[/math]이 모든 자연수(또는, 어떤 자연수보다 큰 모든 자연수)에 대하여 성립함을 보이는 증명법이다. 증명은 두 부분으로 구성되는데, 첫 번째 부분은 최소원 [math] n=n_0[/math]에 대해 [math]P\left(n_0\right) [/math]가 성립함을 보이는 부분이며, 두 번째 부분에서는 어떤 자연수 [math] k[/math]에 대해 [math]P\left(k\right)[/math]가 성립한다는 가정 하에 [math]P\left(k+1\right) [/math] 또한 성립함을 보이게 된다. 흔히 첫 번째 부분을 Basis step, 두 번째 부분을 Induction step이라 한다.

많은 사람들이 잊고 있지만, 반드시 주의해야 할 점이 하나 있다. 이전의 해답이 다음 해답을 반드시 보증해야 한다는 점이다. 바꿔 말하자면 일정 규모의 문제에 대한 해답이 주어지면 거기서 하나가 빠져도 해답은 그대로 유지해야 한다는 것이다. 그렇지 않은 경우에는 수학적 귀납법은 도리어 반례로 인한 논리적 오류를 낳을 수 있다. 실제로 P-NP 문제가 풀리지 않고 있는 원인 중의 하나가 바로 이러한 점을 간과해서 생긴 것이다.

1.1 유한 귀납법

수학적 귀납법의 형태는 다음과 같다.

주어진 명제에 대하여,

1. 기본 경우: 해당 명제가 [math]n=0[/math] 혹은 [math]n=1[/math], 여튼 가장 기본적인 경우에 성립하는지 확인한다.
2. 추론: 해당 명제가 [math]n=k[/math] 일때 성립한다고 가정한 후, [math]n=k+1[/math]일때도 성립하는지 증명한다.

이렇게 써 놓은게 교과서식 표현이다.

보다 쉽게 표현하자면 다음과 같다.

1. 첫 번째에 세워져 있는 도미노가 쓰러지는지 확인한다.
2. [math]n[/math]번째에 세워져 있는 도미노가 쓰러질 때 항상 [math]n+1[/math]번째에 세워져 있는 도미노도 쓰러지는지 확인한다.

이 두 가지 항목이 확인되면 전체 도미노가 무사히 쓰러지리라고 확신할 수 있다. 이것이 귀납적인 논리 전개 방식이다.

즉, [math]n=1[/math]의 경우, 성립한다. [math]n[/math]이 성립하고 [math]n+1[/math]이 성립한다. 여기서 [math]n=1[/math]로 둘 때 [math]n+1=2[/math]에서 성립힌다. 또 여기서 [math]n=2[/math]에서 성립하므로 [math]n+1=3[/math]에서도 성립한다. 이하 무한 반복. 이렇게 하면 무한대까지 쭉쭉 뻗어나가 모든 자연수에서 성립한다는 것이다.

즉, [math]\left(P\left(0\right) \,\ \& \,\ \left(\forall n \in N \,\ P\left(n\right) \Rightarrow P\left(n+1\right)\right)\right) \Rightarrow \forall n \in N\,\ P\left(n\right) [/math]

단점은 범위가 자연수(혹은 확장한다고 해도 정수)에서만 성립한다는 것이다. 정수론에서 가장 중요한 증명법 중에 하나이다.

참고로 정수의 정렬원리를 이용하여 유한 귀납법의 타당성을 증명할 수 있다.

1.2 초한귀납법

자연수를 확장한 서수(초한서수), 기수(초한기수)에 대해서 적용하기 위해서, 수학적 귀납법을 확장한 것이다.

1. 첫번째 항목에 대해서 성립합을 확인한다.
2. 어떤 서수가 성립한다고 가정할때, 그 따름서수에 대해서 성립함을 보인다.
3. 임의의 극한 서수에 대해서 그보다 작은 서수들이 모두 성립한다고 가정할떄, 그 극한서수에 대해서 성립함을 보인다.

이 세 가지를 하나의 sentence로 묶을 수 있다. [math]A[/math]가 well-ordered class(모든 subclass에 supremum이 존재하는 class)이고, [math]P\left(x\right)[/math]를 각각의 원소 [math]x\in A[/math]에 대해 참과 거짓이 명백한 명제라 하자. 다음 조건 Ind.이 모든 [math]x\in A[/math]에 대해 성립한다면, [math]P\left(x\right)[/math]는 모든 원소 [math]x\in A[/math]에 대해 참이다.

[math]\text{Ind. }\left[P\left(y\right),\,\forall y \owns\left(y\in A\right)\land\left(y\ltx\right)\right]\Rightarrow P\left(x\right)[/math]

이 조건 아래에서는 가장 작은 원소에 대한 추가적인 조건이 없어도 되는데, 바로 이 조건이 그것을 포함하고 있기 때문이다!
이것은 만약 [math]x_0[/math]를 가장 작은 원소라고 하면, [math]y\ltx_0[/math] 부분이 거짓이 되어 대괄호 부분의 논리값이 참이 되기 때문이다.

1.3 매거적 귀납법

수학적 귀납법과는 또 다른 형태의 완전 귀납법. 수학적 귀납법도 내용을 보면 매거적 귀납법과 공통분모가 있기는 하지만, 수학적 귀납법에서 증명하는 명제는 '[math]n=1[/math]에서 성립한다' 와 '[math]n=a[/math]에서 성립한다면 [math]n=a+1[/math]에서 성립한다'라는 단 두 가지 명제이기 때문에...

문자 그대로, 특정 집합에 있는 모든 원소에서 해당 명제가 성립함을 모든 원소를 일일이 언급해 가면서 직접 증명하는 방법이다. 하지만 귀납법의 생명이 해당 명제를 일반화할 수 있다는 것, 즉 그 집단에서의 일부분의 성질만 조사하고서도 그 성질을 집단 전체의 성질로 확장할 수 있다는 점, 치명적으로 이전까지의 답이 다음 답은 완전히 보증하지 않는다는 점 때문에, 아리스토텔레스는 매거적 귀납법을 '사이비 귀납법'이라고 불렀다.

2 예시

• [math]1[/math]부터 [math]2n-1[/math]까지 홀수의 합이 [math]n^2[/math]이라는 것을 증명해보자. [math]n[/math]이 [math]1[/math]일때 [math]1=1[/math]로 성립한다.
• [math]n=k[/math]일때 성립한다 가정하자. [math]1+3+\cdots+\left(2k-1\right)=k^2[/math]이므로 [math]n=k+1[/math]일 때를 살펴보면 [math]1+3+\cdots+\left(2k-1\right)+\left(2k+1\right)=k^{2}+2k+1=\left(k+1\right)^2[/math]이다. 즉, 수학적 귀납법에 의해 위의 명제는 성립한다.

이런 식으로 사용한다.

애매한 표현을 이용해서 암울한 현실을 유머적으로 표현하는데 쓰이기도 한다. 더미의 역설 참조.