2019년 2월 7일 목요일

수학적 귀납법(數學的歸納法, mathematical induction) KMO기초

수학적 귀납법(數學的歸納法, 영어: mathematical induction)은 모든 자연수가 어떤 주어진 성질을 만족시킨다는 명제를 증명하는 방법의 하나이다. 가장 작은 자연수(문맥에 따라 0일 수도 1일 수도 있다)가 그 성질을 만족시킴을 증명한 뒤, 만약 어떤 자연수가 만족시키면 바로 다음 자연수 역시 만족시킴을 증명하기만 하면, 모든 자연수에 대한 증명이 끝난다. 이는 임의의 정초 관계를 갖춘 집합 위의 초한 귀납법으로 확장할 수 있다. 수학적 귀납법은 이름과는 달리 귀납적 논증이 아닌 연역적 논증에 속한다. 수학적 귀납법은 자연수의 페아노 공리계의 공리이며, 메타논리학적 추론 규칙이기도 하다.
​

​

정의[편집]

자연수의 (2차 논리) 이론인 페아노 공리계에서는 다음과 같은 공리가 등장한다. 임의의 1항 술어 {\displaystyle P(-)}가 다음 두 조건을 만족시킨다고 하자.
  • {\displaystyle P(0)}이 성립한다.
  • 임의의 n\in \mathbb {N} 에 대하여, 만약 P(n)이 성립한다면, {\displaystyle P(n+1)} 역시 성립한다.
그렇다면, 임의의 n\in \mathbb {N} 에 대하여, P(n)이 성립한다. 이 공리를 수학적 귀납법이라고 한다. 이를 기호로 표기하면 다음과 같다.
{\displaystyle \forall P(-)((P(0)\land \forall n(P(n)\implies P(n+1)))\implies \forall nP(n))}
수학적 귀납법을 구체적으로 서술하면 다음과 같다. 임의의 자연수 부분 집합 {\displaystyle S\subseteq \mathbb {N} }이 다음 두 조건을 만족시킨다고 하자.
  • 0\in S
  • 임의의 n\in \mathbb {N} 에 대하여, {\displaystyle n\in S}라면, {\displaystyle n+1\in S}
그렇다면, S={\mathbb N}이다. (즉, 임의의 n\in \mathbb {N} 에 대하여, {\displaystyle n\in S}이다.) 이를 기호로 표기하면 다음과 같다.
{\displaystyle \forall S\subseteq \mathbb {N} (0\in S\supseteq S+1\implies S=\mathbb {N} )}

변형[편집]

수학적 귀납법의 여러 가지 변형 또는 일반화가 존재하며, 이들은 수학적 귀납법을 사용하여 증명된다.

시작점[편집]

정수 m\in {\mathbb Z}가 주어졌을 때, 임의의 정수 부분 집합 {\displaystyle S\subseteq \mathbb {Z} }가 다음 두 조건을 만족시킨다고 하자.
  • m\in S
  • 임의의 n\in\mathbb Z에 대하여, 만약 {\displaystyle n\in S}라면, {\displaystyle n+1\in S}
그렇다면, {\displaystyle \{n\in \mathbb {Z} \colon n\geq m\}\subseteq S}이다. 즉, 임의의 n\in\mathbb Z ({\displaystyle n\geq m})에 대하여, {\displaystyle n\in S}이다. 수학적 귀납법은 여기서 {\displaystyle m=0,1}인 특수한 경우이다.
펼치기
증명:

역진 귀납법[편집]

자연수 {\displaystyle m\in \mathbb {N} }이 주어졌을 때, 임의의 자연수 부분 집합 {\displaystyle S\subseteq \mathbb {N} }이 다음 두 조건을 만족시킨다고 하자.
  • m\in S
  • 임의의 n\in \mathbb {N} 에 대하여, 만약 {\displaystyle n+1\in S}라면, {\displaystyle n\in S}
그렇다면, {\displaystyle \{n\in \mathbb {N} \colon n\leq m\}\subseteq S}이다. 즉, 임의의 n\in \mathbb {N}  ({\displaystyle n\leq m})에 대하여, {\displaystyle n\in S}이다.
펼치기
증명:

초한 귀납법[편집]

" 이 부분의 본문은 초한 귀납법입니다
임의의 자연수 부분 집합 {\displaystyle S\subseteq \mathbb {N} }이 다음 조건을 만족시킨다고 하자.
  • 임의의 n\in \mathbb {N} 에 대하여, 만약 {\displaystyle라면, {\displaystyle n\in S}이다.
(특히, n=0일 경우 이는 0\in S를 뜻한다.) 그렇다면, S={\mathbb N}이다. 즉, 임의의 n\in \mathbb {N} 에 대하여, {\displaystyle n\in S}이다. 이를 자연수 집합 위의 초한 귀납법이라고 하며, 제2/강한/완전 수학적 귀납법이라고도 한다.
펼치기
증명:
보다 일반적으로, 정초 관계 {\displaystyle \sim _{R}}를 갖춘 집합 X의 부분 집합 S\subseteq X가 다음 조건을 만족시킨다고 하자.
  • 임의의 x\in X에 대하여, 만약 {\displaystyle \{y\in X\colon y\sim _{R}x\}\subseteq S}라면, x\in S이다.
그렇다면, {\displaystyle S=X}이다. 즉, 임의의 x\in X에 대하여, x\in S이다.

기타[편집]

그 밖에도 수학적 귀납법과 비슷한 증명법이 많이 존재한다. 예를 들어, 임의의 자연수 부분 집합 {\displaystyle S\subseteq \mathbb {N} }이 다음 두 조건을 만족시킨다고 하자.
  • {\displaystyle 0,1\in S}
  • 임의의 n\in \mathbb {N} 에 대하여, 만약 {\displaystyle n\in S}라면, {\displaystyle n+2\in S}
또는, 다음 두 조건을 만족시킨다고 하자.
  • 0\in S
  • 임의의 n\in \mathbb {N} 에 대하여, 만약 {\displaystyle n\in S}라면, {\displaystyle 2n,2n+1\in S}
그렇다면, S={\mathbb N}이다. 즉, 임의의 n\in \mathbb {N} 에 대하여, {\displaystyle n\in S}이다.

성질[편집]

수학적 귀납법보다 약한 명제[편집]

페아노 공리계에서 수학적 귀납법을 제외하여 얻는 이론 아래, 다음 두 명제가 서로 동치이다.
수학적 귀납법은 이 세 명제를 함의하지만, 이 세 명제는 수학적 귀납법을 함의하지 않는다. 예를 들어, 다음과 같은 대상들로 이루어진 구조는 자연수의 정렬성 및 초한 귀납법 및 무한 강하법을 만족시키지만, 수학적 귀납법을 만족시키지 않으므로 페아노 공리게의 모형이 아니다.
  • 집합 {\displaystyle \{0,0.5,1,1.5,\dots \}}
  • 상수 {\displaystyle 0}
  • 단항 연산 {\displaystyle (-)+1}

수학적 귀납법과 동치인 명제[편집]

페아노 공리계에서 수학적 귀납법을 제외하여 얻는 이론 아래, 다음 두 명제가 서로 동치이다.
  • 수학적 귀납법
  • 다음 두 명제의 논리곱
    • 자연수의 정렬성 (또는 초한 귀납법 또는 무한 강하법)
    • {\displaystyle \mathbb {N} \setminus \{0\}\subseteq \mathbb {N} +1}. 즉, 모든 0이 아닌 자연수는 어떤 자연수 더하기 1이다.
펼치기
증명:

예[편집]

모든 자연수가 어떤 성질을 만족시킨다는 명제에 대한 수학적 귀납법을 통한 증명은 다음과 같은 두 단계로 구성된다.
  1. 처음 오는 자연수(0 또는 1)에 대한 증명
  2. n이 만족시킨다는 가정 아래, n+1에 대한 증명
자연수와 관련된 수많은 항등식 · 부등식 · 기하학 정리 따위를 이러한 단계들을 거쳐 증명할 수 있다.

홀수의 합 공식[편집]

홀수의 합 공식
{\displaystyle 1+3+5+\cdots +(2n-1)=n^{2}}
이 임의의 자연수 n에 대하여 성립한다는 사실을 다음과 같이 증명할 수 있다.
1에 대하여 성립
1에 대한 공식 {\displaystyle 1=1^{2}}은 자명하게 성립한다.
n에 대하여 성립한다는 가정 아래, n+1에 대하여 성립
n에 대하여 성립하므로, 다음이 성립한다.
{\displaystyle 1+3+5+\cdots +(2n-1)=n^{2}}
양변에 2n+1를 더하면, 다음과 같다.
{\displaystyle 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] 알카라지는 1000년 경에 쓴 책에서 이항 정리 등을 증명하기 위해 수학적 귀납법의 한 형태를 사용했다.[2] [3] 그러나 이들은 수학적 귀납법을 자신이 사용한 가정으로서 명확히 밝히지 않았으며, 처음으로 귀납법에 대한 엄밀한 서술을 한 이는 프란체스코 마우롤리코 (Francesco Maurolico)로, 그는 1575년의 저서 〈Arithmeticorum libri duo〉에서 이를 이용해 가장 작은 n개의 홀수를 더하면 n2이 됨을 증명했다. 스위스의 야코프 베르누이와 프랑스의 블레즈 파스칼 및 피에르 드 페르마도 귀납법을 독립적으로 발견했다.[1]



Wikipedia
작성자: 시간:

댓글 없음:

댓글 쓰기

피드 구독하기: 댓글 (Atom)