무한강하법

틀:위키데이터 속성 추적 무한강하법은 귀류법의 일종으로, 자연수의 정렬성, 즉 공집합이 아닌 모든 자연수의 부분집합에는 항상 최솟값이 존재한다는 성질을 이용한 증명이다. 이 방법은 만약에 어떤 명제를 참으로 만드는 값이 존재한다면, 그 명제를 참으로 만드는 더 작은 값이 존재한다는 것을 증명하는 방식으로 사용된다. 그러면 '명제를 참으로 만드는 자연수의 집합'은 자연수의 부분집합이면서 공집합이 아니므로 최솟값이 존재하여야 하는데, 증명에 따라 그 최솟값보다 작은 값이 집합 안에 존재하여야 하고 이에 따라 모순이 발생한다.

이 증명 방식을 다르게 서술하면, 특정 명제를 참으로 만드는 최소의 값이 존재한다면 그보다 더 작은 값이 존재한다는 것을 증명하여 모순을 보이고, 따라서 그러한 최소의 값은 존재하지 않는다는 것을 증명할 수 있다.

$\sqrt{2}$의 무리수 증명

무한강하법은 $\sqrt{2}$가 무리수라는 것을 증명하는 데에 사용될 수 있다. 만약 $\sqrt{2}$가 유리수라면, 정수 $n,m$(m≠0)가 존재하여

$\sqrt{2}=\frac{n}{m}$

로 표현할 수 있다. 그렇다면 식의 양변을 제곱하여

$2m^2=n^2$

를 얻을 수 있다. 따라서 이 방정식을 만족하는 정수쌍 $(n,m)$이 존재하는 것과 $\sqrt{2}$가 유리수에 속하는 것은 동치이다.

그러한 $(n,m)$이 존재한다고 가정하면, $n^2$는 2의 배수이므로, $n$은 2의 배수가 되어야 한다. 그러면 $n=2n^{\prime }$인 자연수 $n^{\prime }$이 존재하여야 하고($n^{\prime }$ 은 정수) 식을 정리하면

$m^2=2n{\text{'}}^2$

가 된다. 앞과 마찬가지로 $m$은 2의 배수이므로 $m=2m^{\prime }$인 자연수 $m^{\prime }$ ($m^{\prime }$ 은 정수) 이 존재한다. 즉, $(n,m)$이 방정식의 해라면 $(n^{\prime },m^{\prime })=(n/2,m/2)$도 정수쌍이고 이 역시 방정식의 해가 된다.

하지만, (0을 제외한) 정수의 해를 2로 무한히 나눌 수 없으므로 그러한 해는 원래부터 존재하지 않는다. 즉, $\sqrt{2}$는 유리수가 될 수 없는 무리수라는 것이 무한강하법에 의하여 증명된다.

같이 보기

• 귀류법