수학적 귀납법

섬네일 **수학적 귀납법**(數學的歸納法, mathematical induction)은 모든 자연수가 어떤 주어진 성질을 만족시킨다는 명제를 증명하는 방법의 하나이다. 가장 작은 자연수(문맥에 따라 0일 수도 1일 수도 있다)가 그 성질을 만족시킴을 증명한 뒤, 만약 어떤 자연수가 만족시키면 바로 다음 자연수 역시 만족시킴을 증명하기만 하면, 모든 자연수에 대한 증명이 끝난다. 이는 임의의 정초 관계를 갖춘 집합 위의 초한 귀납법으로 확장할 수 있다. 수학적 귀납법은 이름과는 달리 귀납적 논증이 아닌 연역적 논증에 속한다. 수학적 귀납법은 자연수의 페아노 공리계의 공리이며, 메타논리학적 추론 규칙이기도 하다.
# 정의
자연수의 (2차 논리) 이론인 페아노 공리계에서는 다음과 같은 공리가 등장한다. 임의의 1항 술어 P(-)가 다음 두 조건을 만족시킨다고 하자. * P(0)이 성립한다. * 임의의 n\in\mathbb N에 대하여, 만약 P(n)이 성립한다면, P(n+1) 역시 성립한다. 그렇다면, 임의의 n\in\mathbb N에 대하여, P(n)이 성립한다. 이 공리를 **수학적 귀납법**이라고 한다. 이를 기호로 표기하면 다음과 같다. :\forall P(-)((P(0)\land\forall n(P(n)\implies P(n+1)))\implies\forall n P(n)) 수학적 귀납법을 구체적으로 서술하면 다음과 같다. 임의의 자연수 부분 집합 S\subseteq\mathbb N이 다음 두 조건을 만족시킨다고 하자. * 0\in S * 임의의 n\in\mathbb N에 대하여, n\in S라면, n+1\in S 그렇다면, S=\mathbb N이다. (즉, 임의의 n\in\mathbb N에 대하여, n\in S이다.) 이를 기호로 표기하면 다음과 같다. :\forall S\subseteq\mathbb N(0\in S\supseteq S+1\implies S=\mathbb N)
# 변형
수학적 귀납법의 여러 가지 변형 또는 일반화가 존재하며, 이들은 수학적 귀납법을 사용하여 증명된다.
## 시작점
정수 m\in\mathbb Z가 주어졌을 때, 임의의 정수 부분 집합 S\subseteq\mathbb Z가 다음 두 조건을 만족시킨다고 하자. * m\in S * 임의의 n\in\mathbb Z에 대하여, 만약 n\in S라면, n+1\in S 그렇다면, \\{n\in\mathbb Z\colon n\ge m\\}\subseteq S이다. 즉, 임의의 n\in\mathbb Z (n\ge m)에 대하여, n\in S이다. 수학적 귀납법은 여기서 m=0,1인 특수한 경우이다. 증명 임의의 n\in\mathbb N에 대하여 m+n\in S임을 증명하기만 하면 된다. 이는 수학적 귀납법으로 다음과 같이 증명된다. ;0에 대하여 성립 :m+0=m\in S ;n에 대하여 성립한다는 가정 아래, n+1에 대하여 성립 :가정에 따라 m+n\in S이므로, m+(n+1)=(m+n)+1\in S이다. 즉, n+1에 대하여 성립한다. 수학적 귀납법에 따라, 임의의 n\in\mathbb N에 대하여, m+n\in S이다. 임의의 n'\in\mathbb Z (n'\ge m)에 대하여, n'=m+n인 n\in\mathbb N이 존재하므로, n'=m+n\in S이다. 증명 끝
## 역진 귀납법
자연수 m\in\mathbb N이 주어졌을 때, 임의의 자연수 부분 집합 S\subseteq\mathbb N이 다음 두 조건을 만족시킨다고 하자. * m\in S * 임의의 n\in\mathbb N에 대하여, 만약 n+1\in S라면, n\in S 그렇다면, \\{n\in\mathbb N\colon n\le m\\}\subseteq S이다. 즉, 임의의 n\in\mathbb N (n\le m)에 대하여, n\in S이다. 증명 임의의 n\in\mathbb N에 대하여 n>m이거나 m-n\in S임을 증명하기만 하면 된다. 이는 수학적 귀납법으로 다음과 같이 증명된다. ;0에 대하여 성립 :m-0=m\in S ;n에 대하여 성립한다는 가정 아래, n+1에 대하여 성립 :만약 n\ge m이라면, n+1>m이므로 성립한다. 만약 n이라면, m-(n+1)=(m-n)-1\in S이므로 성립한다. 증명 끝
## 초한 귀납법
초한 귀납법 임의의 자연수 부분 집합 S\subseteq\mathbb N이 다음 조건을 만족시킨다고 하자. * 임의의 n\in\mathbb N에 대하여, 만약 \\{k\in\mathbb N\colon k라면, n\in S이다. (특히, n=0일 경우 이는 0\in S를 뜻한다.) 그렇다면, S=\mathbb N이다. 즉, 임의의 n\in\mathbb N에 대하여, n\in S이다. 이를 자연수 집합 위의 초한 귀납법이라고 하며, **제2/강한/완전 수학적 귀납법**이라고도 한다. 증명 임의의 n\in\mathbb N에 대하여 \\{k\in\mathbb N\colon k임을 증명하기만 하면 된다. 이는 수학적 귀납법으로 다음과 같이 증명된다. ;0에 대하여 성립 :\\{k\in\mathbb N\colon k1이라면) 모두가 알고 있는 뻔한 사실을 말했을 뿐이지만, 평소와는 다른 특별한 결과를 가져왔다.
# 역사
최초로 수학적 귀납법이 사용된 예는 유클리드의 소수의 무한성에 대한 증명이나 바스카라 2세의 "순환 방법"(cyclic method) 등에서 찾을 수 있다.".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.

[참고](EUCLID’S THEOREM ON THE INFINITUDE OFPRIMES: A HISTORICAL SURVEY OF ITS PROOFS(300B.C.–2017)ROMEO MEˇSTROVI ́C , arXiv:1202.3670) https://arxiv.org/abs/1202.3670알카라지는 1000년 경에 쓴 책에서 이항 정리 등을 증명하기 위해 수학적 귀납법의 한 형태를 사용했다.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.

date=1999-07

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

그러나 이들은 수학적 귀납법을 자신이 사용한 가정으로서 명확히 밝히지 않았으며, 처음으로 귀납법에 대한 엄밀한 서술을 한 이는 프란체스코 마우롤리코 (Francesco Maurolico)로, 그는 1575년의 저서 〈Arithmeticorum libri duo〉에서 이를 이용해 가장 작은 n개의 홀수를 더하면 n2이 됨을 증명했다. 스위스의 야코프 베르누이와 프랑스의 블레즈 파스칼 및 피에르 드 페르마도 귀납법을 독립적으로 발견했다. 수학적 귀납법은 1838년 오거스터스 드 모르간에 의해 처음으로 귀납법(induction) 또는 연속 귀납법(successive induction)이라고 불렸다.De Morgan: Artikel *Induction (Mathematics)* in: Penny Cyclopædia XII (1838), S. 465–466. 1888년과 1889년에는 리하르트 데데킨트와 주세페 페아노가 각각 독립적으로 귀납법을 공식화, 공리화했다. 1888년, 데데킨트는 *라는 제목의 모노그래프를 내면서 완전 귀납법(Vollständige Induktion)이라는 표현을 사용했다.Richard Dedekind: *Was sind und was sollen die Zahlen?'', Braunschweig 1888, § 6 Satz 80, Originalwortlaut: Satz der vollständigen Induktion (Schluss von n auf n’). Um zu beweisen, dass ein Satz für alle Zahlen n einer Kette m0 gilt, genügt es zu zeigen, dass er für n = m gilt und dass aus der Gültigkeit des Satzes für eine Zahl n der Kette m0 stets seine Gültigkeit auch für die folgende Zahl n’ folgt.location=Braunschweig Online available at: MPIWG GDZ UBS 여기서 데데킨트는 실수의 산술을 귀납법 공리를 포함하는 수 공리로부터 이끌어내는 데에 초점을 두었다. 이듬해인 1889년에는 주세페 페아노가 자연수를 기술하는 최초의 공식화된 공리계인 페아노 공리계를 제안하면서 귀납법을 공리화했다. 이 시기에 이르러 수학적 귀납법은 비로소 지금의 엄밀함을 갖추었다.