수학적 귀납법
1. 수학적 귀납법
mathematical induction · 數學的 歸納法
귀납추리와 혼동할 수 있겠지만, 엄밀히 말하면 연역법의 일종이다. 증명 과정이 타당하다면 결론 역시 반드시 타당하기 때문에 완전귀납법이라고도 한다.
자연수에 관한 명제 $$P(n)$$이 모든 자연수(또는, 어떤 자연수보다 큰 모든 자연수)에 대하여 성립함을 보이는 증명법이다.[1] 증명은 두 부분으로 구성되는데, 첫 번째 부분은 최소원 $$n=n_0$$에 대해 $$P(n_0)$$가 성립함을 보이는 부분이며, 두 번째 부분에서는 어떤 자연수 $$k$$에 대해 $$P(k)$$가 성립한다는 가정 하에 $$P(k+1)$$ 또한 성립함을 보이게 된다. 흔히 첫 번째 부분을 Basis step, 두 번째 부분을 Induction step이라 한다.
전제하는 원리는 다음과 같다.
가산무한집합 $$X$$가 자연수 집합 $$\mathbb{N}$$의 부분집합일 때
이 두 가지 성질을 만족하면 집합 $$X$$는 집합 $$\mathbb{N}$$과 같다는 성질, 즉 페아노 공리계를 이용한다.[2]1) $$1\in X$$ (최소원 $$1$$의 존재)
2) $$n\in X$$일 때 $$n+1\in X$$
이 때, $$P(n)$$이 모든 자연수에 대하여 성립함을 보이기 위해 다음 2가지만 보이면 된다.
그러면 명제 $$P(n)$$을 만족하는 자연수 $$n$$들의 집합을 $$X$$라고 할 때, $$X$$는 자연수의 집합 $$\mathbb{N}$$과 같아지므로 모든 자연수 $$n$$에서 $$P(n)$$이 성립한다.1) $$P(1)$$이 성립
2) $$P(n)$$이 성립하면 $$P(n+1)$$이 성립
수학적 귀납법과 동치이지만 뭔가 조건이 좀 더 강해보이는(?) 강한 수학적 귀납법이라는 것도 얻을 수 있다. 구체적으로는 $$P(n)$$이 성립하는 것을 확인하기 위해서는 다음을 증명하면 된다.
수학적 귀납법도 다변수함수처럼 다차원 수학적 귀납법, 다변수 수학적 귀납법을 상정해볼 수 있다.1) $$P(0)$$이 성립한다.
2) $$P(0),\,P(1),\,P(2),\,\cdots,\,P(n)$$이 모두 성립하면 $$P(n + 1)$$이 성립한다.
1.1. 유한 귀납법
수학적 귀납법의 형태는 다음과 같다.
주어진 명제에 대하여,
- 기본 경우: 해당 명제가 $$n=0$$ 혹은 $$n=1$$에 대해서 성립하는지 확인한다.[3]
- 추론: 해당 명제가 $$n=k$$ 일때 성립한다고 가정한 후, $$n=k+1$$일때도 성립하는지 증명한다.[4]
보다 쉽게 이해시키기 위하여 흔히 도미노에 비유하곤 한다.
- 첫 번째에 세워져 있는 도미노가 쓰러지는지 확인한다.
- 무작위로 고른 $$n$$번째에 세워져 있는 도미노가 쓰러질 때 항상 $$n+1$$번째에 세워져 있는 도미노도 쓰러지는지 확인한다.
즉, $$n=1$$의 경우 성립한다. $$n$$이 성립하면, $$n+1$$이 성립한다. 여기서 $$n=1$$로 둘 때 $$n+1=2$$에서 성립한다. 또 여기서 $$n=2$$에서 성립하므로 $$n+1=3$$에서도 성립한다. 이하 무한 반복. 이렇게 하면 무한대까지 쭉쭉 뻗어나가 모든 자연수에서 성립한다는 것이다.
즉, $$(P(0)\quad\&\quad(\forall n\in N\quad P(n)\Rightarrow P(n+1)))\Rightarrow \forall n\in N\quad P(n)$$
단점은, 범위가 자연수(혹은 확장한다고 해도 정수)에서만 성립한다는 것이다. 정수론에서 가장 중요한 증명법 중에 하나이다.[5]
참고로 정수의 정렬원리를 이용하여 유한 귀납법의 타당성을 증명할 수 있다.[6]
1.2. 초한귀납법
자연수를 확장한 서수(초한서수), 기수(초한기수)에 대해서 적용하기 위해서, 수학적 귀납법을 확장한 것이다.
- 첫번째 항목에 대해서 성립합을 확인한다.
- 어떤 서수가 성립한다고 가정할 때, 그 따름서수에 대해서 성립함을 보인다.
- 임의의 극한 서수에 대해서 그보다 작은 서수들이 모두 성립한다고 가정할 때, 그 극한 서수에 대해서 성립함을 보인다.
이 조건 아래에서는 가장 작은 원소에 대한 추가적인 조건이 없어도 되는데, 바로 이 조건이 그것을 포함하고 있기 때문이다! 만약 $$x_0$$를 가장 작은 원소라고 하면, $$y<x_0$$ 부분이 거짓이 되어 전건의 논리값이 참이 된다. 따라서 $$P(x_0)$$가 참이다.$$\forall y\in A (y<x\Rightarrow P(y))\Rightarrow P(x)$$
1.3. 매거적 귀납법
수학적 귀납법과는 또 다른 형태의 완전 귀납법. 수학적 귀납법도 내용을 보면 매거적 귀납법과 공통 분모가 있기는 하지만, 수학적 귀납법에서 증명하는 명제는 '$$n=1$$에서 성립한다' 와 '$$n=a$$에서 성립한다면 $$n=a+1$$에서 성립한다'라는 단 두 가지 명제이기 때문에...
문자 그대로, 특정 집합에 있는 '''모든 원소에서''' 해당 명제가 성립함을 '''모든 원소를 일일이 언급해 가면서''' 직접 증명하는 방법이다. 하지만 귀납법의 생명이 해당 명제를 일반화할 수 있다는 것, 즉 그 집단에서의 일부분의 성질만 조사하고서도 그 성질을 집단 전체의 성질로 확장할 수 있다는 점,[7] 치명적으로 이전까지의 답이 다음 답은 완전히 보증하지 않는다는 점 때문에, 아리스토텔레스는 매거적 귀납법을 '사이비 귀납법'이라고 불렀다.
2. 예시
- $$1$$부터 $$2n-1$$까지 모든 홀수의 합이 $$n^2$$임을 보이시오.
- $$n$$이 $$1$$일때 $$1(+0)=1^2=1$$로 성립한다.
- $$n=k$$일때 성립한다고 가정하자. $$\displaystyle \sum_{i=1}^k (2i-1) = k^2$$이므로 $$n=k+1$$일 때를 살펴보면
$$\displaystyle \sum_{i=1}^{k+1} (2i-1) = \sum_{i=1}^k (2i-1) + (2k+1)=k^{2}+2k+1=(k+1)^2$$이다.
즉, 수학적 귀납법에 의해 위의 명제는 성립한다.
이런 식으로 사용한다.즉, 수학적 귀납법에 의해 위의 명제는 성립한다.
애매한 표현을 이용해서 암울한 현실을 유머적으로 표현하는데 쓰이기도 한다. 더미의 역설 참조.
3. 관련 문서
[1] 사실 자연수일 필요는 없다. Well-ordered class의 특수한 경우가 자연수일 뿐이다.[2] 만약 최소원이 $$1$$이 아닌 $$2$$ 이상의 정수 $$a$$라면, 이 성질을 만족하는 집합 $$X$$는 집합 $$\mathbb{N}-\{1,\,\cdots,\,a-1\}$$이 된다.[3] 굳이 $$n$$을 [math(0)] 또는 $$1$$로만 둘 필요는 없다. 필요하다면 $$n=2,\,n=100,\,n=3000$$ 등 원하는 $$n$$에 대해서 참인지 따져봐도 되고, $$n$$이 무한대로 발산할 때에 대해 알아보고 싶다면 '정확히 얼마인지는 알 바 아니고 여튼 유한한 $$n$$ 어딘가'에서 참이라는 것만 보여도 된다. 물론 $$n$$이 $$1~100$$일 때에 대해 관심이 있는데 기본 경우를 $$n=101$$같이 알아보고자 하는 범위를 포함하지 않도록 잡으면 당연히 안 된다.[4] 그러니까, 수학적 귀납법을 풀 때는 해당하는 명제가 $$n=k$$에서 성립하는지 안 하는지를 밝힐 필요가 없다. 더 정확하게 말하자면, $$n=k$$일 때 성립하는지 밝히는 것은 해당 명제를 증명하는 것과 같다. 수학적 귀납법을 처음 배우는 고등학생들이 이 부분을 정말 헷갈려하는데, 이것만 이해하면 수학적 귀납법은 꽤 쉬워질 것이다.[5] 미친 짓을 한다면 자연수×자연수(그러니까 (자연수, 자연수) 좌표계)에서도 사용할 수는 있다. 선택공리에 의하여 $$\mathbb{N}^{n}\sim\mathbb{N}$$이기 때문. 그러니까 잘하면 유리수까지는 가능하다는 이야기. 근데 실수부터는 안 된다. 자세한 건 연속체 가설의 설명 참조.[6] 참고로 유한귀납법이 성립함을 가정하면 정렬원리를 증명할 수 있다. 즉, 두 명제는 동치관계.[7] 일단 수학적 귀납법에서는 그 명제가 참이라는 것을 직접 밝혀야 하는 원소는 맨 처음의 원소 하나밖에 없다.