최근 수정 시각 : 2023-10-20 23:10:45

수학적 귀납법

수학기초론
Foundations of Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px" 		다루는 대상과 주요 토픽
수리논리학 논리 · 논증{ 귀납논증 · 연역논증 · 귀추 · 유추} · 공리 및 공준 · 증명{ 자동정리증명 · 귀류법 · 수학적 귀납법 · 반증 · 더블 카운팅 · PWW} · 논리함수 · 논리 연산 · 잘 정의됨 · 조건문( 조각적 정의) · 명제 논리( 명제 · 아이버슨 괄호 · 역 · 이 · 대우) · 양상논리 · 술어 논리( 존재성과 유일성) · 형식문법 · 유형 이론 · 모형 이론
집합론 집합( 원소 · 공집합 · 집합족 · 곱집합 · 멱집합) · 관계( 동치관계 · 순서 관계) · 순서쌍( 튜플) · 서수( 하세 다이어그램 · 큰 가산서수) · 수 체계 · ZFC( 선택공리) · 기수( 초한기수) · 절대적 무한 · 모임
범주론 범주 · 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성
계산가능성 이론 계산 · 오토마타 · 튜링 기계 · 바쁜 비버 · 정지 문제 · 재귀함수
정리
드모르간 법칙 · 대각선 논법 · 러셀의 역설 · 거짓말쟁이의 역설 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 집합-부분합 정리 · 퍼스의 항진명제 · 굿스타인 정리 · 완전성 정리 · 불완전성 정리( 괴델 부호화) · 힐베르트의 호텔 · 연속체 가설 · 퍼지 논리
기타
예비사항( 약어 및 기호) · 추상화 · 벤 다이어그램 · 수학철학
틀:논리학 · 틀:이산수학 · 틀:이론 컴퓨터 과학 · 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 }}}}}}}}}



1. 수학적 귀납법
1.1. 유한 귀납법
1.1.1. 강한 수학적 귀납법
1.2. 초한귀납법1.3. 매거적 귀납법
2. 예시3. 관련 문서

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, 두 번째 n에대한 임의의 상수 k를 가정하는 부분을 assumption step, 세 번째 k+1 또한 n에서 성립함을 보이는 부분을 inductive step, 네 번째 결론을 도출하는 부분을 conclusion 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})]과 같다는 성질, 즉 페아노 공리계를 이용한다.[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))]이 성립하는 것을 확인하기 위해서는 다음을 증명하면 된다. 하지만, 본질적으로 수학적 귀납법과 동일하다.
1) [math(P(1))]이 성립한다.
2) [math(P(1),\,P(2),\,\cdots,\,P(n))]이 모두 성립하면 [math(P(n + 1))]이 성립한다.

실제 증명에서는 원래 수학적 귀납법 못지 않게 강한 수학적 귀납법을 자주 사용한다. 많은 경우 [math(P(n+1))]을 보이기 위해 [math(P(n))]이 성립할 때 생기는 무언가보다 [math(P(1))], [math(P(2))], ..., [math(P(n))] 중 어떤 하나에서 생기는 무언가를 쓰는 게 더 적절하기 때문이다.[3] 조건이 강해 보여서 쓰기 불편해 보이겠지만 그건 큰 오해이다. 원래 수학적 귀납법의 것보다 더 잔뜩 가정해 놓고[4] 그 중에 원하는 거 아무 거나 한두 개 골라 쓰는 것인데도 패널티가 생기기는커녕 이게 원래 수학적 귀납법과 사실 상 동치이니, 오히려 더 편리한 녀석이라고 할 수도 있다.

많은 경우 1번 스텝보다 2번 스텝을 보이는 게 훨씬 더 어렵다. 사실 1번 스텝은 많은 경우 자명하다(...) 한 마디로 끝내도 좋을 정도이다. 예를 들어 [math(n)]이 어떤 벡터 공간의 차원이면 이런 상황이 자주 발생한다. 즉, [math(n = 1)]일 때 다루는 대상이 엄청 단순하거나 매우 구체적이면 스텝 1 역시 단순해진다. 하지만 물론 스텝 1이 항상 그렇게 쉬운 단계이진 않다. 오히려 경우에 따라선 스텝 1이 훨씬 더 어려워지고 스텝 2는 단순해지는 경우도 종종 발생한다.[5]

정수론에서 가장 중요한 증명법 중에 하나이다. 단점은, 범위가 자연수(혹은 확장한다고 해도 정수)에서만 성립한다는 것이다.[6] 초한귀납법이 있긴 하지만 생각보다 그리 자주 쓰이지는 않는다. 그럼에도 수학적 귀납법은 정수론 뿐만 아니라 많은 분야에서 쏠쏠히 잘 쓰이는데[7], 많은 수학적 대상들이 자연수로 된 핵심적인 파라미터(parameter)를 가지기 때문이다. 다항식의 차수라든가 유한 차원 벡터 공간의 차원[8], 그리고 수열[9]의 인덱스가 가장 대표적인 예이다. 그리고 이런 대상들이 정수론, 대수학은 물론 기하학, 해석학, 위상수학을 포함한 수학 전반에서 몹시 자주 나타나고, 이들 혹은 이들을 활용한 어떤 대상의 성질을 규명할 때 이들 자연수 파라미터가 핵심으로 작용하니, 수학적 귀납법은 유한귀납법만 있어도 어디에서든 강력한 도구로 활용된다.

사실 증명 과정에서 은연 중에 수학적 귀납법을 쓰는 경우가 많다. 예를 들어 어떤 작업을 한 다음, 뭔가 더 작은 것이 나왔고 (여기에다 이해를 돕기 위해 한 번 더 비슷한 작업을 할 수도 있지만) 그 다음에 "... 이 작업을 (그 작은 것에) 계속 반복하다 보면..."라고 쓰는 경우가 왕왕 있는데, 여기서 수학적 귀납법을 썼다고 보면 된다. 사실 이런 반복 작업을 수학적으로 형식화한 것이 바로 수학적 귀납법이다.

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

1.1. 유한 귀납법

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

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

보다 쉽게 이해시키기 위하여 흔히 도미노에 비유하곤 한다.
  1. 첫 번째에 세워져 있는 도미노가 쓰러지는지 확인한다.
  2. 무작위로 고른 [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))]

1.1.1. 강한 수학적 귀납법

Strong induction
위의 귀납법을 이에 대비하여 약한 (수학적) 귀납법이라고도 한다. 이는 약한 귀납법과 동치임이 알려져있지만, 약한 귀납법보다 강력하다. 이 단락에서는 구분을 위해 모두 약한/강한 귀납법이라고 명시할 것이다.

정리. 자연수의 부분집합 [math(S)]가 다음 조건을 만족하면, [math(S)]는 자연수 전체의 집합 그 자체이다.
  1. [math(1\in S)]
  2. [math(1,2,\cdots,k\in S\Rightarrow k+1\in S)]

증명. 집합 [math(S)]가 강한 귀납법의 조건을 만족시킨다고 할 때, 다음의 집합을 생각하자.
  • [math(T=\{n\in\mathbb N|[0,n]\cap \mathbb N \subset S\})]
이제 이 집합에 대해 약한 귀납법을 사용할 것이다.
먼저, [math(1\in S)]이므로, [math(1\in T)]인 것은 자명하다. [math(S)]가 강한 수학적 귀납법의 조건을 만족시킨다고 했으니, [math(1,2,\cdots,k \in S)]이면 [math(k+1\in S)]이다. 그 말은 곧, [math(k\in T)]이면 [math(k+1\in S)]이라는 말이 되고, [math(k \in T)]가 [math(1,2,\cdots,k \in S)]라고 정의했으니 [math(k\in T \Rightarrow 1,2,\cdots,k \in S \wedge k+1\in S \Leftrightarrow k+1\in T)]이다. 약한 귀납법에 의해 [math(T=\mathbb N)]이고, [math(n\in\mathbb T \Rightarrow 1,2,\cdots,n\in S\Rightarrow n\in S)]이니 모든 자연수는 [math(S)]의 원소가 된다.

강한 귀납법으로 약한 귀납법을 증명.
이는 간단하다. [math(S)]가 약한 귀납법을 만족시킨다고 하자. 그러면,
  1. [math(1\in S)]
  2. [math(k\in S \Rightarrow k+1\in S)]
그런데 [math(1,2,\cdots,k \in S \Rightarrow k \in S \Rightarrow k+1\in S)]이므로, 강한 귀납법에 의해 [math(S=\mathbb N)]이 된다.

1.2. 초한귀납법

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

이 세 가지를 하나의 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))]가 참이다.

1.3. 매거적 귀납법

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

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

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)]이 아닌 [math(2)] 이상의 정수 [math(a)]라면, 이 성질을 만족하는 집합 [math(X)]는 집합 [math(\mathbb{N}-\{1,\,\cdots,\,a-1\})]이 된다. [3] 가장 대표적인 예로 차원(dimension)에 대한 수학적 귀납법을 쓰면서 몫공간(quotient space)을 증명에 쓰는 경우를 들 수 있다. 이 몫공간은 보통 원래 주어진 공간의 차원보다 딱 하나 더 낮은 차원을 가지지 않기 때문이다. [4] 그냥 가정만 하면 된다. 원래 버전에선 '이제 [math(P(n))]을 가정하자'로 되어 있던 것을 '이제 [math(P(1))], [math(P(2))], ..., [math(P(n))]을 가정하자'로 바꾸기만 하면 된다. [5] 예를 들어 J. M. Lee, Introduction to Smooth Manifolds, 2nd Ed. (Springer, 2012)의 Theorem C.34를 보자. [6] 미친 짓을 한다면 자연수×자연수(그러니까 (자연수, 자연수) 좌표계)에서도 사용할 수는 있다. 선택공리에 의하여 [math(\mathbb{N}^{n}\sim\mathbb{N})]이기 때문. 그러니까 잘하면 유리수까지는 가능하다는 이야기. 근데 실수부터는 안 된다. 자세한 건 연속체 가설의 설명 참조. [7] 오히려 초한귀납법을 이용한 케이스가 유한 귀납법보다 훨씬 더 적다. [8] 무한 차원도 있지만 많은 경우 유한 차원인 벡터 공간들만 가지고 논다. 사실 유한 차원 벡터 공간들을 다루는 것과 무한 차원 벡터 공간들을 다루는 것 간에는 엄청난 차이가 있다. [9] '수의 열' 뿐만 아니라 수를 넘어 임의의 무언가(e.g., 함수, 집합)로 구성된 sequence 전체. [10] 굳이 [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)]같이 알아보고자 하는 범위를 포함하지 않도록 잡으면 당연히 안 된다. [11] 그러니까, 수학적 귀납법을 풀 때는 해당하는 명제가 [math(n=k)]에서 성립하는지 안 하는지를 밝힐 필요가 없다. 더 정확하게 말하자면, [math(n=k)]일 때 성립하는지 밝히는 것은 해당 명제를 증명하는 것과 같다. 수학적 귀납법을 처음 배우는 고등학생들이 이 부분을 정말 헷갈려하는데, 이것만 이해하면 수학적 귀납법은 꽤 쉬워질 것이다. [12] 일단 수학적 귀납법에서는 그 명제가 참이라는 것을 직접 밝혀야 하는 원소는 맨 처음의 원소 하나밖에 없다.

분류