수학적 귀납법 (편집)

[[분류:가져온 문서/오메가]]
[[외부:https://pbs.twimg.com/media/GShu102WwAAe0l0.jpg:large|width=400]]
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]])]

(임시 저장) (임시 저장 불러오기)

(↪️) (💎) (🛠️) (추가)