무한강하법

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

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

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

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

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

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

${\displaystyle 2m^{2}=n^{2}}$

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

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

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

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

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

같이 보기

• 귀류법