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