무한강하법

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

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

의 무리수 증명 

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

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

를 얻을 수 있다. 따라서 이 방정식을 만족하는 정수쌍 이 존재하는 것과 가 유리수에 속하는 것은 동치이다.

그러한 이 존재한다고 가정하면, 는 2의 배수이므로, 은 2의 배수가 되어야 한다. 그러면 인 자연수 이 존재하여야 하고( 은 정수) 식을 정리하면

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

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

같이 보기 
 귀류법

증명
수학 용어
디오판토스 방정식