귀류법 (Proof by Contradiction)
쉽게 풀면
"이 방 안에 도둑은 없다"를 증명하고 싶다고 해봅시다. 직접 증명하기 어려우니, 일단 "도둑이 있다"고 가정해 봅니다. 그런데 CCTV를 보니 그 시간에 문이 잠겨 있었고 아무도 드나든 흔적이 없다는 사실과 "도둑이 있다"는 가정이 서로 모순됩니다. 모순이 나왔다는 것은 애초의 가정("도둑이 있다")이 틀렸다는 뜻이므로, "도둑은 없다"가 참이라고 결론 내릴 수 있습니다. 이것이 귀류법의 원리입니다. 수학에서 가장 유명한 예는 "√2는 무리수다"의 증명입니다. 먼저 "√2가 유리수(분수 a/b, 단 a와 b는 서로소)라고 가정"한 뒤 식을 전개하면 결국 a와 b가 둘 다 짝수여야 한다는 결론이 나오는데, 이는 "a와 b가 서로소(공약수가 1뿐)"라는 처음 가정과 정면으로 모순됩니다. 따라서 "√2는 유리수"라는 가정이 틀렸으므로 √2는 무리수라는 것이 증명됩니다.
왜 중요한가
귀류법은 어떤 대상이 "존재하지 않는다"거나 "유일하다"는 것처럼 직접 구성해서 보이기 어려운 명제를 증명하는 데 특히 강력하기 때문에, 순수수학뿐 아니라 이론전산학의 계산 불가능성·복잡도 증명, 논리학의 정리 증명 등 다양한 분야의 논문에서 핵심 증명 전략으로 쓰인다. 어떤 성질을 만족하는 대상이 존재한다고 가정했을 때 이미 알려진 사실과 충돌함을 보이는 방식은, 문제를 직접 푸는 대신 반대 방향에서 접근할 수 있게 해준다는 점에서 널리 활용된다.
논문에서는 이렇게 쓰입니다
이 문장은 "해가 두 개 이상 존재한다고 가정한 뒤, 그 가정이 앞서 세운 정리의 전제와 충돌한다는 것을 보임으로써 결국 해가 하나뿐임을 증명했다"는 뜻으로, 직접 증명이 까다로운 유일성·비존재성 정리를 다룰 때 논문에서 자주 사용하는 증명 전략입니다.
이론전산학 분야에서 어떤 문제의 계산 복잡도 하한을 증명할 때 귀류법을 활용하는 대표적인 표현입니다.
그래프이론 분야에서 특정 구조가 존재하지 않음을 보이는 명제를 증명할 때도 귀류법이 흔히 사용됩니다.
조금 더 깊게 보면
귀류법은 형식논리학적으로 "명제 P가 참이 아니라고 가정했을 때 거짓인 명제가 도출되면 P는 참이다"라는 원리에 기반하며, 이는 고전논리의 배중률(어떤 명제든 참이거나 거짓 둘 중 하나)을 전제로 한다. 이 때문에 배중률을 인정하지 않는 직관주의 논리 체계에서는 귀류법의 사용이 제한적으로만 허용되며, 이 점은 수리논리학이나 구성적 수학을 다루는 논문에서 종종 언급되는 배경 지식입니다.
주의할 점
귀류법은 "결론을 부정했을 때 모순이 나온다"는 것만 보이면 되므로, 원래 주장 자체를 직접 구성하거나 계산할 필요가 없습니다. 다만 도출한 모순이 정말로 논리적 모순인지(단순히 이상해 보이는 결과와는 다름) 명확히 짚어야 하며, 가정한 내용 중 정확히 어느 부분과 충돌하는지 밝혀야 증명으로 인정받습니다.