수학적 귀납법

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

수학적 귀납법(數學的歸納法, 영어: mathematical induction), 줄여서 귀납법은 어떤 성질이 모든 자연수에 대해 성립함을 증명하기 위해 사용되는 방법이다. 첫 자연수에 대해 참인 것과, 어떤 자연수에 대해 참이면 항상 다음 자연수에 대해서도 참인 것을 증명하는 두 과정으로 이루어진다.

보다 일반적으로, 이는 모든 순서수모임에 대한 초한귀납법으로 확장할 수 있으며, 임의의 기초관계에 대한 구조적 귀납법으로 확장할 수도 있다.

수학적 귀납법에 의한 증명은, 이름과는 달리 귀납적 논증이 아닌 연역적 논증에 속한다. 이러한 증명의 합리성을 기술하는 수학적 귀납법의 원리는, 페아노 공리계공리 중 하나이며, 메타논리추론 규칙이기도 하다.

수학적 귀납법의 원리[편집]

만약 자연수에 대한 어떤 성질 P가 두 조건

  • P(0)은 참이다.
  • P(n)이 참이면 항상 P(n + 1)도 참이다.

를 만족하면, P(n)은 모든 자연수 n에 대해 성립한다. 두 조건으로부터 P(0),\ P(1),\ P(2),\ P(3),\ \ldots이 모두 참이라는 것이 직관적으로 보여지는데, 귀납원리는 그것으로 충분하다는 의미, 즉 임의의 자연수는 0으로부터 1씩 증가해 도달 가능하다는 의미, 즉 자연수가 0, 1, 2, 3, ... 밖에는 없다는 의미가 된다. 0이 아닌 1을 첫 자연수로 간주하는 경우도 있다.

귀납원리는 페아노 공리계의 한 가지 공리로 등장한다. 논리학적으로는

\forall P.\,[[P(0) \land \forall k \in \mathbb{N}.\,[P(k) \Rightarrow P(k+1)]] \Rightarrow \forall n \in \mathbb{N}.\,P(n)]

과 같은 2차 논리적 공리로 형식화된다. 1차 산술에서는 이를 1차 공리꼴이 대신한다.

귀납원리는 명제의 임의 자연수 성립에 대한 증명법을 제공한다.

수학적 귀납법에 의한 증명[편집]

어떤 성질이 모든 자연수 n에 대해 성립함을 보이기 위해서는, '두 조건'을 각각 증명하는 두 과정

  1. 첫 자연수(0 또는 1)에 대해 성립 증명
  2. n에 대해 성립함을 가정하고, n + 1에 대한 성립 증명

을 거친다. 조합론, 수리논리학에서는 주로 0, 첫 자연수를 1로 한 경우는 1을 시작점으로 한다.

[편집]

홀수의 합 공식

1 + 3 + 5 + \cdots + (2n - 1) = n^2

이 모든 자연수 n에 대해 성립하는 것을 두 단계로 나눠 증명할 수 있다.

우선, n = 1이 명제를 성립시킴을 보인다. 이는 대입으로 쉽게 검증된다.

1 = 1^2

그 후, n = k에 대한 성립으로부터 n = k + 1에 대한 성립을 유도한다. 자연수 n=k에 대해 명제가 성립, 즉

1 + 3 + \cdots + (2k - 1) = k^2

이라 가정하면, 양변에 (2k + 1)을 더해

1 + 3 + \cdots + (2k - 1) + (2k + 1) = k^2 + 2k + 1 = (k + 1)^2

을 얻으며, n = k + 1에 대해서도 성립한다는 것을 알 수 있다.

귀납원리에 따라, 홀수의 합 공식은 모든 자연수 n에 대해 성립한다.

변형[편집]

수학적 귀납법과 비슷한 유형의 증명법은 여럿 존재한다. 이들은 때로 자연수의 더 많은 구조(이를테면 덧셈, 순서)를 필요로 하며, 수학적 귀납법을 이용해 합리성을 증명할 수 있다. 예를 들어 '임의 성립'을 보이기 위해, 수학적 귀납법처럼

P(1),\ \forall n \in \N .\, [P(n) \Rightarrow P(n + 1)]

을 보이는 대신

P(1),\ P(2),\ \forall n \in \N .\, [P(n) \Rightarrow P(n + 2)]

또는

P(1),\ \forall n \in \N .\, [P(n) \Rightarrow P(2n) \wedge P(2n + 1)]

등을 보이기도 한다.

다른 시작점[편집]

첫 자연수가 아닌 수를 귀납의 시작점으로 둘 수도 있다. 만약 어떤 성질 P가 자연수 m에 대해 참, 또한 어떤 자연수 n \ge m에게 참일 때 n + 1에게도 참이라면, 그 성질은 모든 자연수 n \ge m에 대해 성립한다.

역진귀납법[편집]

성질 Pm에 대해 성립하고, 어떤 n + 1에 대해 성립할 때 n에 대해서도 성립한다면, 그 성질은 m과 같거나 그보다 작은 모든 자연수 n에 대해 성립한다.

제2 수학적 귀납법[편집]

제2 수학적 귀납법(완전 수학적 귀납법, 강한 수학적 귀납법)에 의하면, 만약 어떤 성질 Pn보다 작은 모든 자연수에게 참일 때 n에게도 참이면, 즉

\forall n \in \N .\, [[\forall m \in \N .\, [m < n \Rightarrow P(m)]] \Rightarrow P(n)]

이면, P는 모든 자연수에 대해 성립한다. 제2 귀납법의 특징은 시작점에 대한 성립을 보일 필요가 없다는 것이다. n이 첫 자연수일 때, 'n보다 작은 모든 자연수에게 참'은 내용이 빈 명제로서 참이기 때문에, 첫 자연수에 대해서는 자연히 P가 성립한다.

초한귀납법[편집]

자연수의 정렬성과의 관계[편집]

수학적 귀납법은 자연수 체계의 한 가지 공리로 사용되며, 이때 자연수의 정렬성(즉 공집합아닌 부분집합 최소원 존재)은 수학적 귀납법을 통해 증명 가능하다. 하지만 그 역은 성립하지 않는다, 즉 페아노 공리계의 앞에 네 공리와 정렬성을 만족하지만, 귀납법을 만족하지 않는 수 체계 모형은 존재한다.

하지만 다음의 가정을 추가했을 때, 수학적 귀납법은 자연수의 정렬성과 동치이다.

  • 어느 자연수의 따름수도 아닌 자연수는 0이 유일하다.
  • 임의의 자연수 n에 대해 n<n+1이 성립한다.

즉 두 가정이 참이라는 전제 하에, 자연수의 정렬성을 이용하여 수학적 귀납법 원리를 증명할 수 있다. 귀류법으로 증명하기 위해, 자연수에 대한 성질 P가 다음을 만족한다고 하자.

  • P(0)은 참
  • P(n)이 참이면 P(n + 1)도 참
  • P(n)을 거짓이게끔 하는 자연수 n 존재

이에 따라 자연수의 공집합 아닌 부분집합을 다음과 같이 만들 수 있으며, 정렬성에 따라 최소원 m이 존재한다.

S = \{n \in \N : \neg P(n) \}

mP를 성립시키지 않아 0은 아니므로, 가정에 의해 m = m' + 1인 자연수 m'이 존재한다. 이미 정의한 순서에 따라 이는 S의 최소원 m보다 작기에, S에 속하지 않는다, 즉 P(m')은 참이다. 그러므로 P(m' + 1), 즉 P(m)은 참이다. 이는 모순이며, 귀납법을 적용할 수 없는 성질 P는 존재치 않음을 보인다.

역사[편집]

아래의 문단에 한국어로 번역되지 않은 내용이 담겨 있습니다. 번역되지 않은 부분은 번역을 마치거나 삭제해주어야 합니다.

This section needs to be translated into Korean. Untranslated parts of the section should be rewritten in Korean or eliminated. (2010년 8월 4일에 문단의 번역이 요청되었습니다.)

최초로 수학적 귀납법이 사용된 예는 유클리드의 소수의 무한성에 대한 증명이나 바스카라 2세의 "순환 방법"(cyclic method) 등에서 찾을 수 있다.".[1] 알카라지는 1000년 경에 쓴 책에서 이항 정리 등을 증명하기 위해 수학적 귀납법의 한 형태를 사용했다.[2] [3] 그러나 이들은 수학적 귀납법을 자신이 사용한 가정으로서 명확히 밝히지 않았으며, 처음으로 귀납법에 대한 엄밀한 서술을 한 이는 프란체스코 마우롤리코 (Francesco Maurolico)로, 그는 1575년의 저서 〈Arithmeticorum libri duo〉에서 이를 이용해 가장 작은 n개의 홀수를 더하면 n2이 됨을 증명했다. 스위스의 야코프 베르누이와 프랑스의 블레즈 파스칼피에르 드 페르마도 귀납법을 독립적으로 발견했다.[1]

같이 보기[편집]

각주[편집]

  1. Cajori (1918), p. 197

    The process of reasoning called "Mathematicla Induction" has had several independent origins. It has been traced back to the Swiss Jakob (James) Bernoulli, the Frenchman B. Pascal and P. Fermat, and the Italian F. Maurolycus. [...] By reading a little between the lines one can find traces of mathematical induction still earlier, in the writings of the Hindus and the Greeks, as, for instance, in the "cyclic method" of Bhaskara, and in Euclid's proof that the number of primes is infinite.

  2. Katz (1998), p. 255-259.

    Another important idea introduced by al-Karaji and continued by al-Samaw'al and others was that of an inductive argument for dealing with certain arithmetic sequences.

  3. O’Connor, John J.; Edmund F. Robertson (1999년 7월). “Abu Bekr ibn Muhammad ibn al-Husayn Al-Karaji”. 《MacTutor History of Mathematics Archive》 (영어). 세인트앤드루스 대학교. 

    Al-Karaji also uses a form of mathematical induction in his arguments, although he certainly does not give a rigorous exposition of the principle.