귀류법 (Proof by Contradiction)
쉽게 풀면
"이 방 안에 도둑은 없다"를 증명하고 싶다고 해봅시다. 직접 증명하기 어려우니, 일단 "도둑이 있다"고 가정해 봅니다. 그런데 CCTV를 보니 그 시간에 문이 잠겨 있었고 아무도 드나든 흔적이 없다는 사실과 "도둑이 있다"는 가정이 서로 모순됩니다.
모순이 나왔다는 것은 애초의 가정("도둑이 있다")이 틀렸다는 뜻이므로, "도둑은 없다"가 참이라고 결론 내릴 수 있습니다. 이것이 귀류법의 원리입니다. 수학에서 가장 유명한 예는 "√2는 무리수다"의 증명입니다.
먼저 "√2가 유리수(분수 a/b, 단 a와 b는 서로소)라고 가정"한 뒤 식을 전개하면 결국 a와 b가 둘 다 짝수여야 한다는 결론이 나오는데, 이는 "a와 b가 서로소(공약수가 1뿐)"라는 처음 가정과 정면으로 모순됩니다. 따라서 "√2는 유리수"라는 가정이 틀렸으므로 √2는 무리수라는 것이 증명됩니다.
왜 중요한가
귀류법은 어떤 대상이 "존재하지 않는다"거나 "유일하다"는 것처럼 직접 구성해서 보이기 어려운 명제를 증명하는 데 특히 강력하기 때문에, 순수수학뿐 아니라 이론전산학의 계산 불가능성·복잡도 증명, 논리학의 정리 증명 등 다양한 분야의 논문에서 핵심 증명 전략으로 쓰인다. 어떤 성질을 만족하는 대상이 존재한다고 가정했을 때 이미 알려진 사실과 충돌함을 보이는 방식은, 문제를 직접 푸는 대신 반대 방향에서 접근할 수 있게 해준다는 점에서 널리 활용된다.
핵심 정리
귀류법은 증명하려는 명제 P가 참이라는 것을 직접 보이는 대신, P가 거짓이라고 가정하고 모순을 이끌어 내어 P가 참일 수밖에 없다고 결론짓는 방법입니다.
- P의 부정(¬P)을 가정한다.
- 그 가정과 이미 알려진 사실로부터 논리적으로 추론한다.
- 이미 알려진 사실이나 가정 자체와 충돌하는 결과(모순)가 나온다.
- 따라서 가정이 틀렸고 P가 참이다.
대표 예는 “√2는 무리수다”입니다. √2 = a/b(서로소)라고 가정하면 a² = 2b²이므로 a가 짝수이고, a = 2k로 두면 b² = 2k²이므로 b도 짝수입니다. 그러면 a와 b가 모두 짝수라 서로소라는 가정과 모순이므로 √2는 유리수가 아닙니다.
예시로 보기
유클리드의 소수 무한 증명도 흔히 귀류법의 형태로 제시됩니다. 소수가 유한하다고 가정하고 그 모두의 곱에 1을 더한 수 N을 만들면, N은 어떤 소수로도 나누어떨어지지 않아 모순이 됩니다(유클리드 『원론』 제9권).
자주 생기는 오해를 코드로 확인. “N이 소수다”라고 읽으면 틀립니다. 모순은 ‘목록에 없는 소수가 존재한다’까지만 보장합니다. 처음 6개 소수 2, 3, 5, 7, 11, 13의 곱에 1을 더하면 30,031인데, 이는 59 × 509로 합성수입니다. 이 경우 N 자체는 소수가 아니지만 N의 소인수(59, 509)가 목록에 없는 소수여서 증명의 결론은 유지됩니다.
자주 하는 오해
- “모순이 나오면 아무 모순이나 좋다”가 아닙니다. 가정(¬P)이나 이미 증명된 사실과 어디서 충돌하는지를 정확히 밝혀야 합니다.
- “이상해 보이는 결과”는 모순이 아닙니다. 논리적으로 성립할 수 없음을 보여야 합니다.
- 귀류법과 대우 증명은 다릅니다. 대우 증명은 ‘Q가 아니면 P가 아니다’를 직접 보이는 것이고, 귀류법은 P와 ¬Q를 함께 가정해 모순을 끌어냅니다.
- 직관주의 논리에서는 제한됩니다. ¬P에서 모순을 얻어 P로 결론짓는 형태(이중부정 제거)는 배중률을 전제하므로 구성적 수학에서는 인정되지 않습니다. 반면 P를 가정해 모순을 얻어 ¬P를 결론짓는 것은 허용됩니다. 하디(Hardy, 1940)는 귀류법을 수학자의 가장 훌륭한 무기 중 하나라고 불렀습니다.
논문에서는 이렇게 쓰입니다
실제 논문에서
이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.
예시 문장
아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.
이 문장은 "해가 두 개 이상 존재한다고 가정한 뒤, 그 가정이 앞서 세운 정리의 전제와 충돌한다는 것을 보임으로써 결국 해가 하나뿐임을 증명했다"는 뜻으로, 직접 증명이 까다로운 유일성·비존재성 정리를 다룰 때 논문에서 자주 사용하는 증명 전략입니다.
이론전산학 분야에서 어떤 문제의 계산 복잡도 하한을 증명할 때 귀류법을 활용하는 대표적인 표현입니다.
그래프이론 분야에서 특정 구조가 존재하지 않음을 보이는 명제를 증명할 때도 귀류법이 흔히 사용됩니다.
조금 더 깊게 보면
귀류법은 형식논리학적으로 "명제 P가 참이 아니라고 가정했을 때 거짓인 명제가 도출되면 P는 참이다"라는 원리에 기반하며, 이는 고전논리의 배중률(어떤 명제든 참이거나 거짓 둘 중 하나)을 전제로 한다. 이 때문에 배중률을 인정하지 않는 직관주의 논리 체계에서는 귀류법의 사용이 제한적으로만 허용되며, 이 점은 수리논리학이나 구성적 수학을 다루는 논문에서 종종 언급되는 배경 지식입니다.
주의할 점
귀류법은 "결론을 부정했을 때 모순이 나온다"는 것만 보이면 되므로, 원래 주장 자체를 직접 구성하거나 계산할 필요가 없습니다. 다만 도출한 모순이 정말로 논리적 모순인지(단순히 이상해 보이는 결과와는 다름) 명확히 짚어야 하며, 가정한 내용 중 정확히 어느 부분과 충돌하는지 밝혀야 증명으로 인정받습니다.
참고 문헌
- Hardy, G. H. (1940). A Mathematician's Apology. Cambridge University Press.
- Velleman, D. J. (2006). How to Prove It: A Structured Approach (2nd ed.). Cambridge University Press.
- Solow, D. (2013). How to Read and Do Proofs: An Introduction to Mathematical Thought Processes (6th ed.). Wiley.
표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.