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