수학적 귀납법

역사 raw
대문 랜덤 문서 최근 토론
분류
1. 수학적 귀납법
1.1. 유한 귀납법1.2. 초한귀납법1.3. 매거적 귀납법
2. 예시3. 관련 문서

1. 수학적 귀납법[편집]

mathematical induction · 數學的 歸納法

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

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

전제하는 원리는 다음과 같다.
가산무한집합 XX가 자연수 집합 N\mathbb{N}의 부분집합일 때
1) 1∈X1\in X (최소원 11의 존재)
2) n∈Xn\in X일 때 n+1∈Xn+1\in X
이 두 가지 성질을 만족하면 집합 XX는 집합 N\mathbb{N}과 같다는 성질, 즉 페아노 공리계를 이용한다.[2]

이 때, P(n)P(n)이 모든 자연수에 대하여 성립함을 보이기 위해 다음 2가지만 보이면 된다.
1) P(1)P(1)이 성립
2) P(n)P(n)이 성립하면 P(n+1)P(n+1)이 성립
그러면 명제 P(n)P(n)을 만족하는 자연수 nn들의 집합을 XX라고 할 때, XX는 자연수의 집합 N\mathbb{N}과 같아지므로 모든 자연수 nn에서 P(n)P(n)이 성립한다.

수학적 귀납법과 동치이지만 뭔가 조건이 좀 더 강해보이는(?) 강한 수학적 귀납법이라는 것도 얻을 수 있다. 구체적으로는 P(n)P(n)이 성립하는 것을 확인하기 위해서는 다음을 증명하면 된다.
1) P(0)P(0)이 성립한다.
2) P(0), P(1), P(2), ⋯ , P(n)P(0),\,P(1),\,P(2),\,\cdots,\,P(n)이 모두 성립하면 P(n+1)P(n + 1)이 성립한다.

수학적 귀납법도 다변수함수처럼 다차원 수학적 귀납법, 다변수 수학적 귀납법을 상정해볼 수 있다.

1.1. 유한 귀납법[편집]

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

주어진 명제에 대하여,
  1. 기본 경우: 해당 명제가 n=0n=0 혹은 n=1n=1에 대해서 성립하는지 확인한다.[3]
  2. 추론: 해당 명제가 n=kn=k 일때 성립한다고 가정한 후, n=k+1n=k+1일때도 성립하는지 증명한다.[4]
이렇게 써 놓은 게 교과서식 표현이다.

보다 쉽게 이해시키기 위하여 흔히 도미노에 비유하곤 한다.
  1. 첫 번째에 세워져 있는 도미노가 쓰러지는지 확인한다.
  2. 무작위로 고른 nn번째에 세워져 있는 도미노가 쓰러질 때 항상 n+1n+1번째에 세워져 있는 도미노도 쓰러지는지 확인한다.
이 두 가지 항목이 확인되면 전체 도미노가 쓰러지게 된다고 확신할 수 있다. 이것이 귀납적인 논리 전개 방식이다.

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

즉, (P(0)&(∀n∈NP(n)⇒P(n+1)))⇒∀n∈NP(n)(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. 초한귀납법[편집]

자연수를 확장한 서수(초한서수), 기수(초한기수)에 대해서 적용하기 위해서, 수학적 귀납법을 확장한 것이다.
  1. 첫번째 항목에 대해서 성립합을 확인한다.
  2. 어떤 서수가 성립한다고 가정할 때, 그 따름서수에 대해서 성립함을 보인다.
  3. 임의의 극한 서수에 대해서 그보다 작은 서수들이 모두 성립한다고 가정할 때, 그 극한 서수에 대해서 성립함을 보인다.

이 세 가지를 하나의 sentence로 묶을 수 있다. AA가 well-ordered class(모든 subclass에 supremum이 존재하는 class)이고, P(x)P(x)를 각각의 원소 x∈Ax\in A에 대해 참과 거짓이 명백한 명제라 하자. 다음 조건이 모든 x∈Ax\in A에 대해 성립한다면, P(x)P(x)는 모든 원소 x∈Ax\in A에 대해 참이다.
∀y∈A(y<x⇒P(y))⇒P(x)\forall y\in A (y<x\Rightarrow P(y))\Rightarrow P(x)

이 조건 아래에서는 가장 작은 원소에 대한 추가적인 조건이 없어도 되는데, 바로 이 조건이 그것을 포함하고 있기 때문이다! 만약 x0x_0를 가장 작은 원소라고 하면, y<x0y<x_0 부분이 거짓이 되어 전건의 논리값이 참이 된다. 따라서 P(x0)P(x_0)가 참이다.

1.3. 매거적 귀납법[편집]

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

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

2. 예시[편집]

  • 11부터 2n−12n-1까지 모든 홀수의 합이 n2n^2임을 보이시오.
    • nn이 11일때 1(+0)=12=11(+0)=1^2=1로 성립한다.
    • n=kn=k일때 성립한다고 가정하자. ∑i=1k(2i−1)=k2\displaystyle \sum_{i=1}^k (2i-1) = k^2이므로 n=k+1n=k+1일 때를 살펴보면
      ∑i=1k+1(2i−1)=∑i=1k(2i−1)+(2k+1)=k2+2k+1=(k+1)2\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] 만약 최소원이 11이 아닌 22 이상의 정수 aa라면, 이 성질을 만족하는 집합 XX는 집합 N−{1, ⋯ , a−1}\mathbb{N}-\{1,\,\cdots,\,a-1\}이 된다.[3] 굳이 nn을 00 또는 11로만 둘 필요는 없다. 필요하다면 n=2, n=100, n=3000n=2,\,n=100,\,n=3000 등 원하는 nn에 대해서 참인지 따져봐도 되고, nn이 무한대로 발산할 때에 대해 알아보고 싶다면 '정확히 얼마인지는 알 바 아니고 여튼 유한한 nn 어딘가'에서 참이라는 것만 보여도 된다. 물론 nn이 1 1001~100일 때에 대해 관심이 있는데 기본 경우를 n=101n=101같이 알아보고자 하는 범위를 포함하지 않도록 잡으면 당연히 안 된다.[4] 그러니까, 수학적 귀납법을 풀 때는 해당하는 명제가 n=kn=k에서 성립하는지 안 하는지를 밝힐 필요가 없다. 더 정확하게 말하자면, n=kn=k일 때 성립하는지 밝히는 것은 해당 명제를 증명하는 것과 같다. 수학적 귀납법을 처음 배우는 고등학생들이 이 부분을 정말 헷갈려하는데, 이것만 이해하면 수학적 귀납법은 꽤 쉬워질 것이다.[5] 미친 짓을 한다면 자연수×자연수(그러니까 (자연수, 자연수) 좌표계)에서도 사용할 수는 있다. 선택공리에 의하여 Nn∼N\mathbb{N}^{n}\sim\mathbb{N}이기 때문. 그러니까 잘하면 유리수까지는 가능하다는 이야기. 근데 실수부터는 안 된다. 자세한 건 연속체 가설의 설명 참조.[6] 참고로 유한귀납법이 성립함을 가정하면 정렬원리를 증명할 수 있다. 즉, 두 명제는 동치관계.[7] 일단 수학적 귀납법에서는 그 명제가 참이라는 것을 직접 밝혀야 하는 원소는 맨 처음의 원소 하나밖에 없다.