무한강하법

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

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

예제: \sqrt{2}무리수 증명[편집]

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

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

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

2m^2 = n^2

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

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

m^2 = 2n'^2

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

하지만, 자연수의 성질에 의해, 해를 2로 무한히 나눌 수 없으므로,오 무한강하법에 의해 그러한 자연수해는 원래부터 존재하지 않는다.. 즉, \sqrt{2}는 유리수가 될 수 없는 무리수라는 것이 증명되었다.