집합과 명제(27)

※본문에는 수식이 사용되었습니다. 모바일에서는 수식이 깨져 보이지 않을 수 있는 점 참고 바랍니다. 만일 수식이 깨져 보일 경우 데스크톱 모드를 사용하여 주시길 부탁드립니다.

---

 보통 증명을 얘기하면 가정으로부터 출발하여 결론을 얻어내는 연역적 증명을 말한다. 그러나 증명에는 연역적 증명 이외에도 여러 종류가 있다. 본문과 본문 이후 두 개의 글에서는 수학적 귀납법에 대해 알아볼 것이다.

귀납법

 먼저 귀납법에 대해 알아보자. 귀납법이란 다양한 현상 등을 관찰하여 공통적인 특성을 추출해 그 대상에 대한 개념 또는 규칙을 찾아내는 것을 의미한다. 자연과학에서는 진화를 연구함에 주로 사용된다.  귀납법을 통해 어떤 현상에 대한 주장을 근거하기 위해서는 그와 관련된 모든 현상이 이 주장을 따름을 보여야 한다. 다만 이 방법을 수학에 적용하기 위해서는 무수히 많은 경우를 직접 하나하나 확인하는 작업이 불가능하다는 점과 주장을 따르지 않는 현상이 단 하나라도 발견될 경우 그 주장이 거짓이라는 점을 해결해야 한다. 이러한 점을 해결하기 위해 수학에서는 흔히 페아노 공리계라고도 불리는 자연수 공리계의 마지막 공리를 바탕으로 수학적 귀납법을 사용한다.

수학적 귀납법

 앞서 언급한 바와 같이 수학적 귀납법은 페아노 공리계의 마지막 공리^[각주:1]를 바탕으로 서술된다.

페아노 공리계의 제 5공리

\( N \)의 부분집합 \( S \)가 \( 1 \in S \)이며, 임의의 \( n \in S \)에 대하여 \( n^{+} \in S \)이면, \( S = N \)이다. 여기서 \( n^{+} \)는 \( n \)의 다음수이다.

 페아노 공리계의 제 5공리의 서술을 이해해보자. 먼저 자연수 집합 \( N \)의 부분집합 중 하나인 \( S \)를 생각해보자. 이 집합 S는 자연수 집합 N의 가장 작은 원소 1을 자신의 원소로 가진다. 그러므로 두 집합 N, S의 가장 작은 원소는 동일하다. 또 집합 S의 임의의 원소 n에 대하여 n의 그 다음수 n^{+}가 집합 S에 속한다는 말은 집합 S에 1이 속하면 그 다음수 2가 S에 속하며, 5가 S에 속하면 그 다음수 6이 S에 속한다는 의미이다. 그러므로 집합 S가 이 두 조건을 모두 만족하면 가장 작은 원소 1부터 1의 다음수 2, 2의 다음수 3, 3의 다음수 4, \( \cdots \)가 S에 속하게 되며, S는 자연수 집합 N과 같아진다. 이러한 페아노 공리계의 제 5공리는 다음과 같이 서술되는 수학적 귀납법과 동치이다.

수학적 귀납법

명제 \( p(n) \)이 \( p(1) \)에서 성립하고, 임의의 자연수 \( k \)에 대하여 \( p(k) \)가 성립할 때 \( p(k+1) \)이 성립하면 \( \forall n \in N \)에 대하여 명제 \( p(n) \)이 성립한다.

 수학적 귀납법은 임의의 자연수에 대하여 명제가 성립함을 보여주는 증명법이다. 수학적 귀납법에 따르면 주어진 명제가 성립하는 가장 작은 자연수인 1에서 성립함을 확인하고, 임의의 자연수 \( k \)에서 주어진 명제가 성립한다고 가정할 때, \( k+1 \)에서 명제 가 성립함을 확인하면 주어진 명제는 자연수 집합에서 참이다. 이러한 논증은 반드시 자연수 집합인 경우에만 사용할 수 있는 것이 아니라 명제가 주어진 구간이 자연수 집합과 일대일대응 관계를 만들어 줄 수 있으면 마찬가지로 수학적 귀납법을 사용할 수 있다. 그러므로 수학적 귀납법은 주로 한 쪽이 닫혀있는 정수 구간에서 주어진 명제가 성립함을 증명하는데 사용된다.

 

 

 

수학적 증명은 다이아몬드처럼 투명할 뿐만 아니라 딱딱하고 엄격한 이유로만 다루어질 수 있다.

-존 로크

---

1. 주로 페아노 공리계의 제 5공리로 부른다. [본문으로]