무한강하법

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

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

${\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'$인 자연수 $n'$이 존재하여야 하고($n'$ 은 정수) 식을 정리하면

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

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

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

같이 보기

• 귀류법