(+)분류 : 가져온 문서/오메가
Mathematical induction
수학에서 명제를 증명하는 방법 중 하나이다. 귀납법이란 이름과 달리 연역적인 형태를 띄지만, 수학자들은 관습적으로 이를 귀납법이라 부른다.
1. 진술 ✎ ⊖
자연수에 대한 명제 P가 있다고 하자. 이 때
이면 P는 모든 자연수에 대해 참이다.
- P(0)
- P(n)\\to P(n+1)
이면 P는 모든 자연수에 대해 참이다.
2. 증명 ✎ ⊖
P가 참인 자연수의 집합을 S\\in\\Bbb N이라 하자. S\\neq\\Bbb N이면, \\Bbb N-S\\in\\Bbb N, \\Bbb N-S\\neq\\varnothing이므로 자연수의 정렬성의 원리에 의해 그 최소원소 m이 존재한다. 1\\in S이므로 m>1이고, 따라서 m-1\\in\\Bbb N-S임에서 P(m-1)이다. 하지만 그렇다면 조건 2에 의해 P(m)이므로 m\\not\\in S에 모순. 따라서 S=\\Bbb N이다.
3. 일반화 ✎ ⊖
수학적 귀납법은 초한 귀납법으로 일반화된다.
정렬집합 A에서의 P(x)가 \\forall x\\in A에 대한 모든 y<x에 대해 P(y)가 참이면 항상 P(x)도 참일 때, \\forall x\\in A\\ P(x)는 참이다. 흔히 다음을 증명하여 가정을 만족시킨다.
위의 \\alpha+1은 임의의 \\alpha에 대한 따름서수이고, Λ는 임의의 극한서수이다.
정렬집합 A에서의 P(x)가 \\forall x\\in A에 대한 모든 y<x에 대해 P(y)가 참이면 항상 P(x)도 참일 때, \\forall x\\in A\\ P(x)는 참이다. 흔히 다음을 증명하여 가정을 만족시킨다.
- P(0)
- P(\\alpha) \\to P(\\alpha+1)
- \\forall \\lambda<Λ\\ P(\\lambda) \\to P(Λ)
위의 \\alpha+1은 임의의 \\alpha에 대한 따름서수이고, Λ는 임의의 극한서수이다.
