수학적 귀납법

수학적 귀납법(數學的歸納法, 영어: 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 nP(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\geq m\}\subseteq S$ 이다. 즉, 임의의 $n\in \mathbb {Z}$ ( $n\geq 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'\geq 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\leq m\}\subseteq S$ 이다. 즉, 임의의 $n\in \mathbb {N}$ ( $n\leq m$ )에 대하여, $n\in S$ 이다.

증명:

임의의 $n\in \mathbb {N}$ 에 대하여 $n>m$ 이거나 $m-n\in S$ 임을 증명하기만 하면 된다. 이는 수학적 귀납법으로 다음과 같이 증명된다.

0에 대하여 성립: $m-0=m\in S$
$n$ 에 대하여 성립한다는 가정 아래, $n+1$ 에 대하여 성립: 만약 $n\geq m$ 이라면, $n+1>m$ 이므로 성립한다. 만약 $n<m$ 이라면, $m-(n+1)=(m-n)-1\in S$ 이므로 성립한다.

초한 귀납법

임의의 자연수 부분 집합 $S\subseteq \mathbb {N}$ 이 다음 조건을 만족시킨다고 하자.

임의의 $n\in \mathbb {N}$ 에 대하여, 만약 $\{k\in \mathbb {N} \colon k<n\}\subseteq S$ 라면, $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<n\}\subseteq S$ 임을 증명하기만 하면 된다. 이는 수학적 귀납법으로 다음과 같이 증명된다.

0에 대하여 성립: $\{k\in \mathbb {N} \colon k<0\}=\varnothing \subseteq S$
$n$ 에 대하여 성립한다는 가정 아래, $n+1$ 에 대하여 성립: $n$ 에 대하여 성립하므로, $S$ 가 만족시키는 조건에 따라, $n\in S$ 이다. 따라서, $\{k\in \mathbb {N} \colon k<n+1\}=\{k\in \mathbb {N} \colon k<n\}\cup \{n\}\subseteq S$ 이다. 즉, $n+1$ 에 대하여 성립한다.

보다 일반적으로, 정초 관계 $\sim _{R}$ 를 갖춘 집합 $X$ 의 부분 집합 $S\subseteq X$ 가 다음 조건을 만족시킨다고 하자.

임의의 $x\in X$ 에 대하여, 만약 $\{y\in X\colon y\sim _{R}x\}\subseteq S$ 라면, $x\in S$ 이다.

그렇다면, $S=X$ 이다. 즉, 임의의 $x\in X$ 에 대하여, $x\in S$ 이다.

기타

그 밖에도 수학적 귀납법과 비슷한 증명법이 많이 존재한다. 예를 들어, 임의의 자연수 부분 집합 $S\subseteq \mathbb {N}$ 이 다음 두 조건을 만족시킨다고 하자.

$0,1\in S$
임의의 $n\in \mathbb {N}$ 에 대하여, 만약 $n\in S$ 라면, $n+2\in S$

또는, 다음 두 조건을 만족시킨다고 하자.

$0\in S$
임의의 $n\in \mathbb {N}$ 에 대하여, 만약 $n\in S$ 라면, $2n,2n+1\in S$

그렇다면, $S=\mathbb {N}$ 이다. 즉, 임의의 $n\in \mathbb {N}$ 에 대하여, $n\in S$ 이다.

성질

수학적 귀납법보다 약한 명제

페아노 공리계에서 수학적 귀납법을 제외하여 얻는 이론 아래, 다음 두 명제가 서로 동치이다.

수학적 귀납법은 이 세 명제를 함의하지만, 이 세 명제는 수학적 귀납법을 함의하지 않는다. 예를 들어, 다음과 같은 대상들로 이루어진 구조는 자연수의 정렬성 및 초한 귀납법 및 무한 강하법을 만족시키지만, 수학적 귀납법을 만족시키지 않으므로 페아노 공리계의 모형이 아니다.

집합 $\{0,0.5,1,1.5,\dots \}$
상수 $0$
단항 연산 $(-)+1$

수학적 귀납법과 동치인 명제

페아노 공리계에서 수학적 귀납법을 제외하여 얻는 이론 아래, 다음 두 명제가 서로 동치이다.

수학적 귀납법
다음 두 명제의 논리곱
- 자연수의 정렬성 (또는 초한 귀납법 또는 무한 강하법)
- $\mathbb {N} \setminus \{0\}\subseteq \mathbb {N} +1$ . 즉, 모든 0이 아닌 자연수는 어떤 자연수 더하기 1이다.

증명:

수학적 귀납법 ⟹ 자연수의 정렬성 + 모든 0이 아닌 자연수는 어떤 자연수 더하기 1: 이는 자연수의 성질이다.
수학적 귀납법 ⟸ 자연수의 정렬성 + 모든 0이 아닌 자연수는 어떤 자연수 더하기 1: 귀류법을 사용하여, 어떤 진부분 집합 $S\subsetneq \mathbb {N}$ 이 수학적 귀납법의 전제 조건을 만족시킨다고 하자. 그렇다면 $\mathbb {N} \setminus S\neq \varnothing$ 이므로, 최소 원소 $m\in \mathbb {N} \setminus S$ 가 존재한다. 이때 $0\in S$ 이므로 $m\neq 0$ 이다. 페아노 공리계의 공리와 모든 0이 아닌 자연수는 어떤 자연수 더하기 1임에 따라, $m-1\in \mathbb {N}$ 을 유일하게 정의할 수 있으며, $m-1<m$ 이므로 $m-1\in S$ 이다. $S$ 가 만족시키는 조건에 따라 $m=(m-1)+1\in S$ 인데, 이는 모순이다.

예

모든 자연수가 어떤 성질을 만족시킨다는 명제에 대한 수학적 귀납법을 통한 증명은 다음과 같은 두 단계로 구성된다.

처음 오는 자연수(0 또는 1)에 대한 증명
$n$ 이 만족시킨다는 가정 아래, $n+1$ 에 대한 증명

자연수와 관련된 수많은 항등식 · 부등식 · 기하학 정리 따위를 이러한 단계들을 거쳐 증명할 수 있다.

홀수의 합 공식

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

이 임의의 자연수 $n$ 에 대하여 성립한다는 사실을 다음과 같이 증명할 수 있다.

1에 대하여 성립

1에 대한 공식

1=1^{2}

은 자명하게 성립한다.

$n$ 에 대하여 성립한다는 가정 아래, $n+1$ 에 대하여 성립

n

에 대하여 성립하므로, 다음이 성립한다.

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

양변에

2n+1

를 더하면, 다음과 같다.

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

이에 따라,

n+1

에 대하여 성립한다.

수학적 귀납법에 따라, 임의의 $n\in \mathbb {N}$ 에 대하여, 홀수의 합 공식이 성립한다.

빨간 눈 퍼즐

어떤 섬의 사람들에게 다음과 같은 조건이 주어졌다고 하자.

각 섬사람은 빨간 눈을 갖거나, 파란 눈을 갖는다.
각 섬사람은 자신을 제외한 이들의 눈 색을 안다.
각 섬사람은 거울을 볼 수 없으며, 다른 이들에게 자신의 눈 색을 물을 수 없다.
자신이 빨간 눈임을 알게 된 섬사람은 그날 밤 섬을 떠나야 한다.
어느 날 아침에 이방인이 찾아와 섬사람들 중에 빨간 눈이 있다는 말을 흘렸다.
다음과 같은 지식들은 섬사람들 사이에서 공유 지식이다. (즉, 사실이며, 모두가 알며, 모두가 앎을 모두가 알며, ...)
- 모든 구성원의 사고력은 충분히 뛰어나다.
- 이방인은 정직하다.

그렇다면, 빨간 눈을 가진 섬사람의 수가 $n$ 이라면, 모든 빨간 눈은 이방인이 찾아온 날부터 세어 $n$ 번째 날 밤에 섬을 떠나게 되며, 이를 수학적 귀납법을 통해 증명할 수 있다. 이방인은 ( $n>1$ 이라면) 모두가 알고 있는 뻔한 사실을 말했을 뿐이지만, 평소와는 다른 특별한 결과를 가져왔다.

역사

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

수학적 귀납법은 1838년 오거스터스 드 모르간에 의해 처음으로 귀납법(induction) 또는 연속 귀납법(successive induction)이라고 불렸다.^[5] 1888년과 1889년에는 리하르트 데데킨트와 주세페 페아노가 각각 독립적으로 귀납법을 공식화, 공리화했다. 1888년, 데데킨트는 <Was sind und was sollen die Zahlen?>라는 제목의 모노그래프를 내면서 완전 귀납법(Vollständige Induktion)이라는 표현을 사용했다.^[6]^[7] 여기서 데데킨트는 실수의 산술을 귀납법 공리를 포함하는 수 공리로부터 이끌어내는 데에 초점을 두었다. 이듬해인 1889년에는 주세페 페아노가 자연수를 기술하는 최초의 공식화된 공리계인 페아노 공리계를 제안하면서 귀납법을 공리화했다. 이 시기에 이르러 수학적 귀납법은 비로소 지금의 엄밀함을 갖추었다.

같이 보기

각주

↑ ^가 ^나 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
↑ 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.
↑ O’Connor, John J.; Robertson, Edmund F. (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.
↑ De Morgan: Artikel Induction (Mathematics) in: Penny Cyclopædia XII (1838), S. 465–466.
↑ 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 m₀ 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 m₀ stets seine Gültigkeit auch für die folgende Zahl n’ folgt.
↑ Richard Dedekind (1888). 《Was sind und was sollen die Zahlen?》. Braunschweig: Vieweg. Online available at: MPIWG GDZ UBS

[Induction_Bussey-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] [참고](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

[3] 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.

[4] O’Connor, John J.; Robertson, Edmund F. (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.

[De_Morgan-5] De Morgan: Artikel Induction (Mathematics) in: Penny Cyclopædia XII (1838), S. 465–466.

[Dedekind-6] 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 m₀ 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 m₀ stets seine Gültigkeit auch für die folgende Zahl n’ folgt.

[7] Richard Dedekind (1888). 《Was sind und was sollen die Zahlen?》. Braunschweig: Vieweg. Online available at: MPIWG GDZ UBS

[1]

[2]

[3]

[4]

[5]

[6]

[7]