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