수학적 귀납법과 연역법

수학적 귀납법

귀납법은 연역법의 한 분야로, 논리적인 추론을 수행하는 방법 중 하나이다.

증명 과정이 타당하다면 결론 역시 반드시 타당하기 때문에 완전귀납법이라고도 한다.

1. 기초 단계 : 먼저, 귀납법을 적용할 명제나 정리가 초기 조건에서 참인지 확인한다. 즉, 명제의 첫 번째 단계나 가장 작은 값을 가지는 경우를 검토한다.

2. 귀납 단계 : 명제나 정리가 기초 단계에서 참이라고 가정하고, 그 가정 하에서 다음 조건이 참임을 증명한다. 이를 통해 모든 조건에서 명제나 정리가 참임을 보일 수 있다.

  1) 가정 단계 : 귀납적 가정을 설정한다. 기초 단계에서의 가정을 귀납 단계에서도 유지하기 위해 가정을 설정한다.

  2) 추론 단계 : 가정에 기초하여 다음 조건에서도 명제나 정리가 참임을 추론한다. 이를 위해 수학적인 규칙이나 논리적인 추론을 사용한다.

 

자연수에 관하나 명제 P(n)이 모든 자연수에 대하여 성립함을 보이는 증명법이다.

가산무한집합  X가 자연수 집합 N의 부분집합일 때,

1) 1∈X(최소원 1의 존재)

2) n∈X일 때, n+1 ∈ X

이 두가지 성질을 만족하면 집합 X는 집합 N과 같다는 성질, 즉 페아노 공리계를 이용한다.이때 P(n)이 모든 자연수에 대하여 성립함을 보이기 위해 다음 2가지만 보이면 된다.

1) P(1)이 성립

2) P(n)이 성립하면, P(n+1)이 성립

그러면 명제 P(n)을 만족하는 자연수 n들의 집합을 X라고 할 때, X는 자연수의 집합 N과 같아지므로 모든 자연수 n에서 P(n)이 성립한다. 조금 더 조건을 강하게 하면 강한 수학적 귀납법이라는 것도 얻을 수 있다.구체적으로는 P(n)이 성립하는 것을 확인하기 위해서는 다음을 증명하면 된다.

1) P(0)가 성립한다.

2) P(0),P(1),P(2),...,P(n)이 모두 성립하면, P(n+1)이 성립한다.

 

가산무한집합

가산무한집합은 무한한 원소를 갖지만, 일대일 대응이 가능한 무한집합이다. 즉, 원소의 개수를 자연수와 동일하게 생각할 수 있는 무한집합이다.

 

페아노 공리계

수학의 기초를 형성하는 일련의 공리로 구성된 시스템이다. 페아노 공리계는 자연수를 형식적으로 정의하고, 자연수에대한 산술 연산과 수학적 속성을 증명하는데 사용된다.

1. 영 공리(Zero axiom): 0은 자연수이다.
2. 후속 공리(Successor axiom): 모든 자연수 n에 대해서, 후속자(successor) s(n)이 존재한다. (예: 1은 0의 후속자, 2는 1의 후속자, 3은 2의 후속자, ...)
3. 단순성 공리(Induction axiom): 모든 속성 P(n)에 대해서, P(0)이 참이고, 자연수 n에 대해서 P(n)이 참이면 P(s(n))도 참이다. 이 공리는 귀납법의 기초를 제공한다.
4. 등가성 공리(Equalitarian axiom): 두 자연수 m과 n에 대해서, m = n이면 n = m이다.
5. 무한성 공리(Infinity axiom): 0은 어떠한 자연수의 후속자도 아니다.