Mathematical induction

Original article: w:Mathematical induction

Mathematical induction can be informally illustrated by reference to the sequential effect of falling dominoes.

수학적 귀납법(Mathematical induction)은 수학적 증명 기법입니다. 이것은 속성 P(n)이 모든 자연수 n, 즉 n = 0, 1, 2, 3,  등에 대해 성립한다는 것을 증명하기 위해서 필수적으로 사용됩니다. 넘어지는 도미노 또는 사다리 오르는 것과 같은, 은유는 수학적 귀납법의 개념을 이해하기 위해서 비공식적으로 사용될 수 있습니다.

수학적 귀납법은, 우리가 밑바닥 가로장 (기초) 위로 올라갈 수 있다는 것을 증명하고 각 가로장에서 다음 가로장 (단계)까지 올라갈 수 있음을 증명함으로써, 우리가 사다리에서 원하는 만큼 높이 올라갈 수 있다는 것을 증명할 수 있습니다.

— Concrete Mathematics, page 3 margins.

귀납법의 방법은 증명해야 할 두 경우를 요구합니다. 기본 경우(base case) (또는, 때때로 기초(basis))라고 불리는, 첫 번째 경우는 속성이 숫자 0에 대해 유지된다는 것을 증명합니다. 귀납법 단계(induction step)라고 불리는, 두 번째 경우는, 만약 속성이 하나의 자연수 n에 대해 유지되면, 그것은 다음 자연수 n + 1에 대해 유지됨을 증명합니다. 이러한 두 단계는 모든 자연수 n = 0, 1, 2, 3, ...에 대해 속성 P(n)을 확증합니다. 기본 단계는 영으로 시작할 필요가 없습니다. 흔히 그것은 숫자 일로 시작하고, 그리고 그것이 임의의 자연수로 시작하여, 시작 번호보다 크거나 같은 모든 자연수에 대한 속성의 참을 확증할 수 있습니다.

이 방법은, 트리(trees)와 같은, 보다 일반적으로 바른-토대(well-founded) 구조에 대한 명제를 증명하기 위해서 확대될 수 있습니다; 구조적 귀납법(structural induction)으로 알려진, 이 일반화는 수학적 논리 및 컴퓨터 과학에 사용됩니다. 이 확장된 의미에서의 수학적 귀납법은 재귀(recursion)와 밀접하게 관련됩니다. 수학적 귀납법은, 어떤 형태로든, 컴퓨터 프로그램에 대한 모든 정확성 증명의 기초입니다.

비록 그의 이름이 다르게 제시할지라도, 수학적 귀납법은 철학에서 사용된 귀납적 추론(inductive reasoning)의 한 형태로써 곡해되어서는 안됩니다 (귀납법의 문제를 역시 참조하십시오). 수학적 귀납법은 공식적 증명(formal proof)에 사용되는 추론 규칙(inference rule)입니다. 수학적 귀납법에 의한 증명은, 사실, 연역적 추론(deductive reasoning)의 예제입니다.

History

기원전 370년에서, 플라톤(Plato)의 파르메니데스(Parmenides)는 암시적인 귀납적 증명의 초기 예제를 포함하고 있을 수 있습니다. 수학적 귀납법의 초기의 암시적 흔적은 소수의 숫자는 무한하다는 유클리드(Euclid)의 증명과 바스카라(Bhaskara)의 "순환 방법(cyclic method)"에서 발견할 수 있습니다. 위쪽으로 대신에 아래쪽으로 세는, 반대쪽의 반복된 기법이 소크라테스의 역설(Sorites paradox)에서 발견되며, 여기서 그것은 만약 모래의 1,000,000알이 하나의 더미를 형성하고, 더미로부터 한 알을 제거하여 그것을 하나의 더미로 남기면, 모래의 하나의 알 (또는 심지어 알 없이) 하나의 더미를 형성합니다.

산술 수열(arithmetic sequences)에 대해 수학적 귀납법에 의한 암시적 증명(proof)은 기원후 1000년 경에 알 카라지(Al-Karaji)에 의해 쓰인 al-Fakhri에서 소개되었으며, 그는 이항 정리(binomial theorem)와 파스칼 삼각형(Pascal's triangle)의 속성을 증명하기 위해 그것을 사용했습니다.

이들 고대 수학자들 중 어느 누구도, 어쨌든, 귀납법 가설을 명시적으로 언급하지 않았습니다. 또 다른 비슷한 경우 (바카(Vacca)가 써왔던 것과는 반대로, 프로이덴탈(Freudenthal)은 조심스럽게 보여준 것처럼)는 Arithmeticorum libri duo (1575)에서 프란체스코 마우롤리코(Francesco Maurolico)의 것으로, 그는 처음 n 개의 홀수 정수의 합이 n²이라는 것을 증명하기 위해서 기법을 사용했습니다. 귀납법의 원리의 첫 번째 명시적 공식화는 Traité du triangle arithmétique (1665)에서 파스칼(Pascal)에 의해 제공되었습니다. 또 다른 프랑스인, 페르마(Fermat)는 무한 하강(infinite descent)에 의한 간접적인 증명에 관련된 원칙을 충분한 사용했습니다. 귀납법 가설은 스위스의 야코프 베르누이(Jakob Bernoulli)에 의해 역시 사용되었으며, 그 이후로는 어느 정도 잘 알려지게 되었습니다. 원칙의 현대의 엄격하고 시스템적인 처리는 조지 부울(George Boole), 오거스터스 드 모르간(Augustus de Morgan), 찰스 샌더스 퍼스(Charles Sanders Peirce), 주세페 페아노(Giuseppe Peano), 리하르트 데데킨트(Richard Dedekind)와 함께 단지 19세기에서 일어났습니다.

Description

수학적 귀납법의 가장 단순하고 가장 공통적인 형태는 자연수 n을 포함하는 명제가 n의 모든 값에 대해 유지한다고 추론합니다. 증명은 두 단계로 구성됩니다:

1. 기본 경우: 명제가 첫 번째 자연수 n에 대해 유지되는 것을 증명합니다. 보통, n = 0 또는 n = 1; 드물게, 때때로 편리하게, n의 기본 값은 더 큰 숫자, 또는 심지어 음수 로 취할 수 있습니다 (명제는 해당 임계 값에서 그리고 위에 오직 유지되며, 왜냐하면 이들 확장이 바른-순서화된 집합(well-ordered set)인 것의 속성을 방해하지 않기 때문입니다).
2. 단계 경우 또는 귀납적 단계: 명제가 어떤 자연수 n에 대해 유지되는 것을 가정하고, 그리고 명제가 n + 1에 대해 성립하는 것을 증명합니다.

명제가 어떤 n에 대해 유지된다는, 귀납적 단계에서 가설은 귀납법 가설(induction hypothesis) 또는 귀납적 가설(inductive hypothesis)이라고 불립니다. 귀납적 단계를 증명하기 위해, 귀납법 가설을 가정하고 그런 다음 n + 1에 대해 명제를 증명하기 위해, n을 포함하는, 이 가정을 사용합니다.

n = 0 또는 n = 1이 표준 기본 경우로 취해지는지 여부는 자연수(natural number)의 선호하는 정의에 따라 다릅니다. 조합론(combinatorics) 및 수학적 논리(mathematical logic)의 분야에서, 그것은 0을 자연수로 고려하는 것이 공통적입니다.

Example

수학적 귀납법은, 다음 명제 P(n)가 모든 자연수 n에 대해 유지된다는 것을 증명하기 위해서 사용됩니다.

$0+1+2+\cdots +n={\frac {n(n+1)}{2}}.$

P(n)은 숫자 n보다 작거나 같은 자연수(natural number)의 합에 대해 공식을 제공합니다. 각 자연수 n에 대해 P(n)이 참이라는 증명은 다음과 같이 진행됩니다.

기본 경우: 명제가 n = 0에 대해 유지되는 것을 보입니다.
P(0)은 참이 되는 것을 쉽게 보입니다:

$0={\frac {0\cdot (0+1)}{2}}\,.$

귀납적 단계: 만약 P(k)이 유지되면, 역시 P(k + 1)가 유지되는 것을 보입니다. 이것은 다음처럼 행해질 수 있습니다.

(k의 어떤 불특정 값에 대해) P(k)가 유지되는 것을 가정합니다. 그런 다음 그것은 반드시 P(k + 1)가 유지되는 것을 보여야 합니다, 즉:

$(0+1+2+\cdots +k)+(k+1)={\frac {(k+1)((k+1)+1)}{2}}.$

P(k)가 유지되는 것을 귀납법 가설을 사용하여, 왼쪽 변은 다음과 같이 다시 쓸 수 있습니다:

${\frac {k(k+1)}{2}}+(k+1)\,.$

대수적으로:

${\begin{aligned}{\frac {k(k+1)}{2}}+(k+1)&={\frac {k(k+1)+2(k+1)}{2}}\\&={\frac {(k+1)(k+2)}{2}}\\&={\frac {(k+1)((k+1)+1)}{2}}\end{aligned}}$

이것에 의하여 실제로 P(k + 1)가 유지된다는 것을 보였습니다.

기본 경우와 귀납적 단계 둘 다는 수행되었기 때문에, 수학적 귀납법에 의해 명제 P(n)는 모든 자연수 n에 대해 유지됩니다. Q.E.D.

Variants

연습에서, 귀납법에 의한 증명은, 입증되어야 할 속성의 정확한 본질에 따라, 종종 다르게 구성됩니다.

Induction basis other than 0 or 1

만약 모든 자연수가 아니라 오직 특정 숫자 b보다 크거나 같은 모든 숫자 n에 대해 명제를 증명하는 것을 원한다면, 귀납법에 의한 증명은 다음과 같이 구성됩니다:

1. 명제가 n = b일 때 유지되는 것을 보입니다.
2. 만약 명제가 어떤 n ≥ b에 대해 유지되면 같은 명제가 n + 1에 대해 역시 유지되는 것을 보입니다.

이것은, 예를 들어, n ≥ 3에 대해 2ⁿ ≥ n + 5인 것을 보여주기 위해 사용될 수 있습니다.

이런 방법에서, 어떤 명제 P(n)이 모든 n ≥ 1, 또는 심지어 n ≥ −5에 대해 유지된다는 것을 증명할 수 있습니다. 수학적 귀납법의 이 형태는 사실은 이전의 형태의 특별한 경우인데, 왜냐하면 만약 입증되기 위한 명제가 P(n)이면, 이들 두 규칙은 귀납법 기본 경우 0을 갖는 모든 자연수 n에 대해 P(n + b)을 입증하는 것과 동일하기 때문입니다.

Example: forming dollar amounts by coins

4- 그리고 5-달러 동전의 무한 공급을 가정합니다. 귀납법은, $12$이상 달러의 임의의 전체 양은 그러한 동전의 조합에 의해 형성될 수 있는 것을 증명하기 위해서 사용될 수 있습니다. 양 $n$은, 명제가 모든 각 더 낮은 숫자에 대해 유지되지 않기 때문에, $12$에서 시작하도록 선택됩니다; 특히, 그것은 $n=11$에 대해 위반됩니다.

보다 정확한 용어에서, 우리는 임의의 양 $n\geq 12$에 대해, 0이 자연수(natural number)로 포함되는, $n=4a+5b$를 만족하는 자연수 $a,b$가 존재하는 것을 보이는 것을 원합니다. 보이기를 원하는 문장은, 따라서, 다음과 같습니다:

$S(n):\,\,n\geq 12\Rightarrow \exists \,a,b\in \mathbb {N} .\,\,n=4a+5b$

기본 경우: $S(k)$가 $k=12$에 대해 유지되는 것을 보이는 것은 자명합니다: $a=3$과 $b=0$라고 놓습니다. 그러면, $4\cdot 3+5\cdot 0=12$입니다.

단계 경우: $S(k)$가 $k\geq 12$의 어떤 값에 대해 유지된다는 것이 주어지면 (귀납법 가설), $S(k+1)$가 역시 유지되는 것을 입증합니다. 즉, 어떤 자연수 $a,b$에 대해 $k=4a+5b$인 것이 주어지면, $k+1=4a_{1}+5b_{1}$를 만족하는 자연수 $a_{1},b_{1}$이 존재하는 것을 입증합니다.

여기서 우리는 두 경우를 고려할 필요가 있습니다.

첫 번째 경우에 대해, $a\geq 1$을 가정합니다. 어떤 대수적 조작에 의해 그리고 가정에 의해, 우리는 해당 경우에서 다음을 알 수 있습니다:

${\begin{aligned}k&=4a+5b\\k+1&=4a+5b+1\\&=4a+5b-4+5\\&=4(a-1)+5(b+1)\\&=4a_{1}+5b_{1}\end{aligned}}$

여기서 $a_{1}=a-1$와 $b_{1}=b+1$는 자연수입니다.

이것은 총 양에 $1$을 더하는 것을 보여줍니다—임의의 양이 무엇이든지, 그것이 $12$보다 큰 동안은—5-달러 동전을 더하는 동안 하나의 4-달러 동전을 제거하는 것으로 충분합니다. 어쨌든, 이 구성은 $a=0$인 경우에서, 또는 단어에서, 4-달러 동전이 없을 때, 실패합니다.

그래서 경우 $a=0$을 입증하는 것이 남았습니다. 그러면 $k=5b\geq 12$이며, 이것은 $b\geq 3$임을 의미합니다.

${\begin{aligned}k&=5b\\k+1&=5b+1\\&=5b-15+16\\&=5(b-3)+4\cdot 4\\&=4\cdot 4+5(b-3)\\&=4a_{1}+5b_{1}\end{aligned}}$

여기서 $a_{1}=4$와 $b_{1}=b-3$은 다시 자연수입니다.

위의 계산은 4-달러 동전이 없는 경우에서, 우리가 네 개의 4-달러 동전을 더하는 동안 세 개의 5-달러를 제거하여 양에 $1$을 더할 수 있는 것을 보여줍니다.

따라서, 귀납적 단계와 함께, 우리는 모든 자연수 $k\geq 12$에 대해 $S(k)$가 $S(k+1)$를 의미하는 것을 보여 왔고, 증명은 완료되었습니다. Q.E.D.

Induction on more than one counter

그것은 때때로, 귀납법 프로세서를 반복함으로써 두 자연수, n과 m을 포함하는 명제를 증명하는 것이 바람직합니다. 즉, n에 대해 기본 경우와 귀납적 단계를 증명하고, 그들의 각 경우에서 m에 대해 기본 경우와 귀납적 단계를 증명합니다. 예를 들어, 자연수의 덧셈(addition of natural numbers)을 따르는 교환 가능성의 증명(proof of commutativity)을 참조하십시오. 셋 이상의 카운터가 포함되는 보다 복잡한 논증도 역시 가능합니다.

Infinite descent

Main article: Infinite descent

무한 하강의 방법은 피에르 드 페르마(Pierre de Fermat)에 의해 사용된 수학적 귀납법의 변형입니다. 그것은 어떤 명제 Q(n)이 모든 자연수 n에 대해 거짓임을 보여주기 위해 사용됩니다. 그의 전통적인 형태는 만약 어떤 자연수 n에 대해 Q(n)이 참이면, 그것이 어떤 엄격하게 더 작은 자연수 m에 대해 유지된다는 것을 보여줍니다. 자연수의 무한하게 감소하는 수열은 없기 때문에, 이 상황은 불가능할 것이며, 모순에 의해 Q(n)은 임의의 n에 대해 절대 참이 될 수 없다는 것을 보입니다.

이 방법의 타당성은 수학적 귀납법의 보통 원리로부터 입증될 수 있습니다. "Q(m)이 n보다 작거나 같은 모든 자연수 m에 대해 거짓입니다"라고 정의된 명제 P(n)에 수학적 귀납법을 사용하여, 그것은 P(n)은 모든 n에 대해 유지되는 것을 따르며, 이것은 Q(n)이 모든 각 자연수 n에 대해 거짓임을 의미합니다.

Prefix induction

수학적 귀납법에 의한 증명의 가장 공통적인 형태는 다음과 같은 귀납적 단계에서 입증하는 것을 요구합니다:

$\forall k(P(k)\to P(k+1))$

그 위에 귀납법 원리는 P(0)에서 P(n)에 이르는 이 단계의 n 적용을 "자동화"합니다. 이것은 각 단계가 그 숫자의 전임에 대한 무언가로부터 숫자에 대한 무언가를 증명하기 때문에 "전임 귀납법"이라고 불릴 수 있습니다.

계산상의 복잡성에 대한 관심의 변종은 "접두사 귀납법(prefix induction)"으며, 이것은 다음을 증명하는 것이 필요합니다:

$\forall k(P(k)\to P(2k)\land P(2k+1))$

또는 동등하게

$\forall k\left(P\left(\left\lfloor {\frac {k}{2}}\right\rfloor \right)\to P(k)\right)$

귀납법 원리는 그런 다음 P(0)에서 P(n)에 이르는 이 추론의 로그 n 적용을 "자동화"합니다. (각 단계는 그의 이진 표현의 낮은 비트를 잘라내는 것으로 형성된 해당 숫자의 "접두사"에 대한 무언가로부터 숫자에 대한 뭔가를 증명하기 때문에 그것은 "접두사 귀납법"이라고 불립니다. 그것은 해당 이진 표현의 길이에 대한 전통적인 귀납법의 응용으로 보일 수 있습니다.)

만약 전통적인 전임 귀납법은 n-단계 루프로 계산적으로 해석된다면, 접두사 귀납법은 로그 n-단계 루프에 해당하고, 따라서 접두사 귀납법을 사용하는 증명은 전임 귀납법을 사용한 증명보다 "보다 실행 가능하게 건설적"입니다.

전임 귀납법은 같은 명제에서 접두사 귀납법을 자명하게 시뮬레이션할 수 있습니다. 접두사 귀납법은 전임 귀납법을 시뮬레이트할 수 있지만, 단지 명제를 (경계진 보편적인 정량화를 더하여) 보다 구문적으로 복잡하게 만드는 것의 대가를 치르므로, 그래서 접두사 귀납법과 다항식-시간 계산을 관련시키는 흥미로운 결과는 전적으로 비-경계진 정량화를 제외하는 것, 그리고 명제에서 허용된 경계진 보편적 그리고 실존적 전량화의 교대를 제한하는 것에 달려 있습니다.

아이디어를 한 걸음 더 나아갈 수 있습니다: 반드시 다음을 입증해야 합니다:

$\forall k\left(P\left(\left\lfloor {\sqrt {k}}\right\rfloor \right)\to P(k)\right)$

그 위에 귀납법 원리는 P(0)에서 P(n)에 이르는 이 추론의 로그 로그 n 적용을 "자동화"합니다. 귀납법의 이 형태는 로그-시간 평행 계산을 연구하기 위해, 유사하게, 사용되어 왔습니다.

Complete (strong) induction

(기본 형태는 때때로 약한 귀납법으로 알려진 반면에) 완비 귀납법(complete induction), 값 귀납법의 과정(course of values induction) 또는 강한 귀납법 (strong induction)이라고 불리는 또 다른 변형은 더 강한 가설을 사용하여 귀납적 단계를 더 쉽게 입증하는 것을 만듭니다: P(n)이 m + 1보다 작은 모든 자연수 n에 대해 유지된다고 가정 아래에서 명제 P(m + 1)을 입증합니다; 반면에 기본 형태는 오직 P(m)을 가정합니다. 이름 "강한 귀납법"은 이 방법이 "약한 귀납법" 이상을 입증할 수 있음을 의미하는 것이 아니라, 귀납적 단계에서 사용된 더 강한 가설을 나타냅니다; 사실 아래 표현한 것처럼 두 방법은 동일합니다. 완비 귀납법의 이러한 형태에서 여전히 기본 경우, P(0)를 증명해야 하고, 피보나치 숫자 F_n의 아래 예제에서 처럼, 일반적인 논증을 적용하기 전에 P(1)과 같은 별도의 기본 경우를 입증하는 것이 심지어 필요할 수 있습니다.

비록 방금 설명한 형태가 기본 경우를 입증하는 것이 필요하지만, 만약 모든 m ≥ 0에 대해 (모든 더 낮은 n에 대해 P(n)을 가정하는) P(m)을 입증할 수 있으면, 이것은 불필요합니다. 이것은, 아래에서 묘사된 것처럼, 초월유한 귀납법(transfinite induction:초한 귀납법)의 특별한 경우입니다. 이 형태에서 기본 경우는 경우 m = 0에 포함되며, 여기서 P(0)은 가정된 다른 P(n)을 갖지 않고 입증됩니다; 이 경우는 분리해서 다루는 것이 필요할 수 있지만, 때때로 같은 논증이 m = 0 및 m > 0에 적용되며, 증명을 더 간단하고 우아하게 만듭니다. 이 방법에서, 어쨌든, P(m)의 증명이 암시적으로 m > 0이라고 가정하지 않도록 보장하는 것이 중요하며, 즉, "임의의 n < m을 선택"을 말하는 것에 의해 또는 m 개의 원소의 집합은 원소를 가진다고 가정합니다.

완비 귀납법은 위에 설명된 것처럼, 한 가지 방법에 의한 증명은 다른 방법에 의한 증명으로 변형될 수 있다는 의미에서, 보통의 수학적 귀납법과 동등합니다. 완비 귀납법에 의한 P(n)의 증명이 있다고 가정합니다. Q(n)은 "P(m)이 0 ≤ m ≤ n을 만족하는 모든 m에 대해 유지된다"는 것을 의미합니다. 그러면 Q(n)은 모든 n에 대해 유지되는 것과 P(n)이 모든 n에 대해 유지되는 것은 필요충분 조건이고, P(n)의 우리의 증명은 (보통의) 귀납법에 의해 Q(n)의 증명으로 쉽게 변환됩니다. 만약, 다른 한편으로, P(n)이 보토의 귀납법에 의해 증명되었다면, 증명은 완비 귀납법에 의해 이미 효과적으로 증명될 것입니다: P(0)은, 가정을 사용하지 않고, 기본 경우에서 입증되었고, P(n + 1)은 귀납적 단계에서 증명되며, 이것은 모든 더 이전 경우에서 가정할 수 있지만 오직 경우 P(n)을 사용합니다.

Example: Fibonacci numbers

완비 귀납법은 귀납적 가설의 여러 예제가 각 귀납적 단계마다 요구될 때 가장 유용합니다. 예를 들어, 완비 귀납법은 다음을 보이기 위해 사용될 수 있습니다:

$F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}$

여기서 F_n는 n번째 피보나치 숫자(Fibonacci number)이고, φ = (1 + √5)/2 (황금 비율(golden ratio))이고 ψ = (1 − √5)/2는 다항식 x² − x − 1의 근입니다. 각 n ∈ N에 대해 F_n+2 = F_n+1 + F_n이라는 사실을 사용하여, 위의 항등식은 만약 그것이 F_n+1과 F_n 모두에 대해 이미 유지된다는 것을 가정하면 F_n+2에 대해 직접 계산에 의해 검증될 수 있습니다. 증명을 완료하기 위해, 항등식은 n = 0와 n = 1의 두 가지 기본 경우에서 반드시 검증되어야 합니다.

Example: prime factorization

완비 귀납법에 의한 또 다른 증명은 그 명제가 모든 더 작은 n에 대해 보다 철저하게 유지된다는 가설을 사용합니다. 산술의 기본 정리의 "존재(existence)"부분인, "1보다 큰 모든 각 자연수(natural number)는 (하나 이상의) 소수(prime number)의 곱"이라는 명제를 생각해 보겠습니다. 귀납적 단계를 증명하기 위해, 귀납법 가설은 주어진 n > 1에 대해 명제가 모든 작은 n > 1에 대해 유지된다는 것입니다. 만약 m이 소수이면 그것은 확실히 소수의 곱이고, 그렇지 않다면, 정의에 의해 그것은 곱: m = n₁n₂이며, 여기서 인수 중 어느 것도 1과 같지 않습니다; 따라서 둘 다 m과 같지 않고, 그래서 둘 다 m보다 작습니다. 귀납법 가설은 이제 n₁와 n₂에 적용되므로, 각 가설은 소수의 곱입니다. 따라서 m은 소수의 곱의 곱입니다; 그러므로 그 자체는 소수의 곱입니다.

Example: dollar amounts revisited

우리는 위(above)에서 처럼 같은 예제를 입증에 유의할 것입니다, 이번에는 강한 귀납법이라고 불리는 변형을 사용합니다. 명제는 같은 것을 이용합니다:

$S(n):\,\,n\geq 12\implies \,\exists \,a,b\in \mathbb {N} .\,\,n=4a+5b$

어쨌든, 증명의 구조 및 가정과 약간의 차이가 있을 수 있습니다. 기본 경우와 함께 시작해 보겠습니다.

기본 경우: $S(k)$가 $k=12,13,14,15$에 대해 유지된다는 것을 보입니다.

${\begin{aligned}4\cdot 3+5\cdot 0=12\\4\cdot 2+5\cdot 1=13\\4\cdot 1+5\cdot 2=14\\4\cdot 0+5\cdot 3=15\end{aligned}}$

기본 경우는 유지됩니다.

귀납법 가설: $S(m)$가 $12\leq m<j$을 갖는 모든 $m$에 대해 유지되는 것을 만족하는 어떤 $j>15$이 주어집니다.

귀납적 단계: $S(j)$가 유지되는 것을 입증합니다.

$m=j-4$를 선택하고, $15<j\implies 12\leq j-4<j$인 것을 관찰하여, 귀납적 가설에 의해, $S(j-4)$가 유지된다는 것을 보입니다. 즉, 합 $j-4$은 $4$와 $5$ 달러 동전의 어떤 조합에 의해 형성될 수 있습니다. 그런 다음, 그 조합에 $4$ 달러 동전을 단순히 더하는 것은 합계 $j$를 산출합니다. 즉, $S(j)$가 유지됩니다. Q.E.D.

Example of error in the inductive step

Main article: All horses are the same color

귀납적 단계는 n의 모든 값에 대해 증명되어야 합니다. 이것을 설명하기 위해, Joel E. Cohen은, 모든 말들이 같은 색깔을 가진다는 것을 수학적 귀납법에 의해 입증을 주장하는, 다음 논증을 제안했습니다:

• 기본 경우: 오직 한마리의 말의 집합에서, 오직 하나의 색깔이 있습니다.
• 귀납적 단계: n 마리의 말의 임의의 집합 내에, 오직 하나의 색깔이 있다는 귀납법 가설로 가정합니다. 이제 n + 1 마리의 임의의 집합을 보십시오. 그들을 세어 봅니다: 1, 2, 3, ..., n, n + 1. 집합 {1, 2, 3, ..., n}과 {2, 3, 4, ..., n + 1}을 생각해 보겠습니다. 각각은 오직 n 마리의 말의 집합이며, 그러므로 각각의 집합 내에는 오직 하나의 색깔이 있습니다. 그러나 두 집합이 중첩되고, 그래서 모든 n + 1 마리 사이에 오직 하나의 색상만 있습니다.

기본 경우 n = 1은 자명하고 (임의의 말이 그 자체로 같은 색깔이기 때문에), 귀납적 단계는 모든 경우 n > 1에서 맞습니다. 어쨌든, 귀납적 단계의 논리는 n = 1에 대해 맞지 않습니다. 왜냐하면 "두 집합 중첩"은 거짓이라는 명제이기 때문입니다 (둘 다 제거 이전에 오직 n + 1 = 2 마리 말이 있고, 제거 후에 각각 한 마리의 집합은 중첩되지 않습니다).

Formalization

이-차 논리(second-order logic)에서, 다음과 같이 "귀납법의 공리(axiom)"를 적어둘 수 있습니다:

$\displaystyle \forall P{\Bigl (}P(0)\land \forall k{\bigl (}P(k)\Rightarrow P(k+1){\bigr )}\Rightarrow \forall n{\bigl (}P(n){\bigr )}{\Bigr )}$,

여기서 P(.)는 하나의 자연수를 포함하는 술어에 대한 변수이고 k와 n은 자연수에 대한 변수입니다.

단어에서, 기본 경우 P(0)와 귀납적 단계 (즉, 귀납법 가설 P(k)는 P(k + 1))을 의미합니다) 함께 임의의 자연수 n에 대한 P(n)을 의미합니다. 귀납법의 공리는 P(n)이 기본 경우와 귀납적 단계로부터 임의의 자연수 n에 대해 유지된다는 것을 유추하는 것의 타당성을 주장합니다.

공리에서 첫 번째 정량화는 개별 숫자에 관한 것이 아닌 술어에 관한 범위를 나타내는 것을 주목하십시오. 이것은 이-차 정량화이며, 이것은 이 공리가 이-차 논리(second-order logic)에서 말해지는 것을 의미합니다. 일-차 논리(first-order logic)에서 산술 귀납법을 공리화하는 것은 각 가능한 술어에 대해 별도의 공리를 포함하는 공리 스키마(axiom schema)를 요구합니다. 기사 페아노 공리(Peano axioms)는 이 이슈의 자세한 논의를 포함합니다.

자연수에 대해 구조적 귀납법의 공리는 페아노에 의해 처음으로 공식화되었으며, 그는 (1) 0은 자연수이고, (2) 모든 각 자연수의 후속 함수 s는 자연수 (s(x)=x+1)를 산출하고, (3) 후속 함수는 단사이고, 그리고 (4) 0은 s의 치역(range)에 속하지 않는다는 네 개의 다른 공리와 함께 자연수를 지정하기 위해 그것을 사용했습니다.

일-차(first-order) ZFC 집합 이론에서, 술어에 관한 정량화는 허용되지 않지만, 집합에 관한 정량화에 의한 귀납법을 여전히 말로 나타낼 수 있습니다:

$\forall A{\Bigl (}0\in A\land \forall k\in \mathbb {N} {\bigl (}k\in A\Rightarrow (k+1)\in A{\bigr )}\Rightarrow \mathbb {N} \subseteq A{\Bigr )}$

$A$는 전제를 표현하는, 그리고 자연수를 표함하는, 전제가 유지되는 것에 대해, 집합으로 읽힐 수 있습니다. 이것은 공리가 아니지만, 자연수가, 페아노의 공리와 유사한, 공리에 의해 ZFC 집합 이론의 언어로 정의되는 것으로 주어지는, 정리입니다.

Transfinite induction

Main article: Transfinite induction

완비 귀납법의 원리는 자연수에 대한 명제에 유효할 뿐만 아니라, 임의의 바른-토대 집합(well-founded set:정초 집합), 즉, 무한 내려가는 체인(infinite descending chain)을 포함하지 않는 비반사 관계(irreflexive relation) <을 갖는 집합의 원소에 대한 명제에 대해 유효합니다. 세는-숫자(cardinal number)의 임의의 집합은, 자연수의 집합을 포함하는, 바른-토대입니다.

바른-토대 집합에 적용하면, 그것은 단일 단계로 공식화될 수 있습니다:

1. 어떤 명제가 모든 m < n에 대해 유지된다면, 같은 명제가 n에 대해 역시 유지된다는 것을 보입니다.

귀납법의 이 형태는, 순서-숫자(ordinals)의 집합에 적용될 때 (바른-순서화되고 따라서 바른-토대 클래스를 형성하는), 초월유한 귀납법(transfinite induction)이라고 불립니다. 그것은 집합 이론(set theory), 토폴로지(topology) 그리고 다른 분야에서 중요한 증명 기술입니다.

초월유한 귀납법에 의한 증명은 전형적으로 세 가지 경우를 구별합니다:

1. n이 가장 작은 원소일 때, 즉, n보다 작은 원소가 없습니다;
2. n이 직접 선행을 가질 때, 즉, n보다 작은 원소들의 집합은 가장 큰 원소를 가집니다;
3. n이 직접 선행을 가지지 않을 때, 즉, n은 소위 극한 순서-숫자(limit ordinal)입니다.

엄격하게 말하면, 기본 경우를 증명하기 위해 초월유한 귀납법에서 필수적인 것은 아니지만, 왜냐하면 만약 P가 모든 n < m이면, P는 m의 참이라는 전제의 공허한(vacuous) 특별한 경우이기 때문입니다. 그것은 정확하게 공허하게 참이며 왜냐하면 반례로 사용할 수 있는 n < m의 값이 없기 때문입니다. 그래서 특별한 경우는 일반적인 경우의 특별한 경우입니다.

Equivalence with the well-ordering principle

수학적 귀납법의 원리는 보통 자연수의 공리(axiom)로 표현됩니다; 페아노 공리(Peano axioms)를 참조하십시오. 어쨌든, 그것은 바른-순서화 원리(well-ordering principle)로부터 입증될 수 있습니다. 사실, 다음을 가정합니다:

• 자연수의 집합은 바른-순서(well-ordered)입니다.
• 모든 각 자연수는 어떤 자연수 숫자 n에 대해 0, 또는 n + 1 둘 중 하나입니다.
• 임의의 자연수 n에 대해, n + 1은 n보다 큽니다.

이들 공리들로부터 간단한 귀납법을 도출하기 위해, 만약 P(n)이 다음과 같은 n의 단언한 어떤 명제임을 반드시 보여야 합니다:

• P(0)는 유지되고
• P(m)이 참일 때마다 P(m + 1)은 역시 참이고, P(n)은 모든 n에 대해 유지됩니다.

증명. S를 P(m)이 거짓인 것에 대해 모든 자연수의 집합으로 가정합니다. 만약 S가 비어 있지 않다고 주장하면 어떤 일이 일어나는지 보겠습니다. 바른-순서화는 S가 가장 작은 원소, 말하자면 n을 가짐을 말합니다. 게다가, P(0)은 참이므로, n은 0은 아닙니다. 모든 각 자연수가 0 또는 어떤 m + 1이므로, m + 1 = n을 만족하는 어떤 자연수 m이 있습니다. 이제 m은 n보다 작고, n은 S의 가장 작은 원소입니다. 그것은 m은 S 안에 있지 않고, 그래서 P(m)은 참인 것을 따릅니다. 이것은 P(m + 1)이 참이라는 것을 의미합니다; 달리 말해서, P(n)은 참입니다. 이것은 모순이며, 왜냐하면 n은 S 안에 있었기 때문입니다. 그러므로, S는 비어 있습니다.

그것은, 귀납법은, 다른 공리를 주어지면, 바른-순서화 원리를 의미하는 것을 역시 입증될 수 있습니다.

증명. 가장 작은 원소를 가지지 않는 자연수의 비-빈 집합(비-공집합), S가 있다고 가정합니다. P(n)을 n이 S 안에 없다는 주장으로 놓습니다. 그런 다음 P(0)는 참이며, 만약 그것이 거짓이면 0은 S의 가장 작은 원소입니다. 게다가, P(1), P(2),..., P(n)은 모두 참이라고 가정합니다. 그런 다음 만약 P(n+1)가 거짓이면 n+1이 S 안에 있고, 따라서 S 안에 가장 작은 원소이고, 모순입니다. 따라서 P(n+1)은 참입니다. 그러므로, 귀납법 공리에 의해, P(n)은 모든 n에 대해 유지되므로, S는 비어 있고, 모순입니다.

See also

• Combinatorial proof
• Recursion
• Recursion (computer science)
• Structural induction
• Proof by exhaustion