05. 배수진의 극의: 귀류법 (Proof by Contradiction)

1. 학습 목표 (Learning Objectives)

  • 직접적으로 증명하기 너무 복잡하고 막막한 난제를 풀기 위해, “결론이 거짓말”이라고 억지로 우겨서 스스로 파멸(모순)에 이르게 하는 논리학의 끝판왕 궁극기 ‘귀류법’을 익힙니다.
  • 인류 역사상 가장 아름다운 증명 중 하나인 피타고라스 학파의 붕괴, $\sqrt{2}$ (루트2)가 무리수임의 증명을 귀류법으로 전개합니다.

2. 결론을 뒤집어 파멸로 이끄는 전략

수학이나 컴퓨터 과학 알고리즘에서 어떤 명제($p \rightarrow q$)가 무조건 ‘참’임을 증명해야 할 때가 있습니다. 하지만 논리 전개가 꼬여서 도저히 $q$(결론)로 예쁘게 도달할 수 없을 때 쓰는 ‘배수진 전략’이 바로 귀류법(Proof by Contradiction) 입니다.

귀류법의 메커니즘

  1. 증명하고 싶은 결론($q$)을 억지로 부정($\sim q$) 해버립니다. (예: “만약 이 결론이 ‘거짓’이라고 가정해 보자!”)
  2. 그 억지 가정을 토대로 신나게 논리를 쭉 전개해 나갑니다.
  3. 어느 순간, 사방이 막힌 낭떠러지, 즉 말도 안 되는 개소리(모순, Contradiction) 에 부딪히게 됩니다! (예: “$1 = 2$이다 라는 헛소리가 나와버렸네?”)
  4. 아하! 이 모순은 애초에 결론을 부정(\sim q)한 것부터가 잘못되었기 때문에 발생한 재앙이다. 고로 억지 부정이 틀렸으니 원래 결론($q$)은 무조건 ‘참(True)’일 수밖에 없다!

논리를 빙글 돌아 역으로 상대의 목을 조르는 치명적이고도 아름다운 증명 방식입니다.

귀류법 증명 흐름도 (Proof by Contradiction Flow) SVG: 결론을 억지로 부정한 뒤, 논리를 무리하게 전개하다가 결국 폭발(모순)로 이어져, 본래 명제가 참으로 복귀하는 4단계 프로세스 박스 차트

3. 세기의 증명: $\sqrt{2}$ 는 무리수이다

기원전 5세기, 피타고라스 학파는 이 세상 모든 수가 분수(유리수)로 깔끔하게 떨어질 것이라 믿었습니다. 하지만 대각선 길이인 $\sqrt{2}$ 가 등장하자 이 숫자는 도저히 분수로 표현이 안 된다는 충격적 사실(무리수)에 직면합니다. 이들이 숨기려 했던 진실을 귀류법으로 무자비하게 박살 내보겠습니다.

2D 웹툰 애니 판타지 스타일: 어둡고 비밀스러운 지하 동굴 은신처에서, 고대 그리스 복장의 피타고라스 학파 수학자들이 불길한 에메랄드빛을 내뿜는 돌판을 내려다보며, 그 위에 저주처럼 계속해서 적혀 나오는 무한 소수(무리수)인 루트 2 식을 보고 머리를 감싸 쥐며 경악과 공포에 질려 있는 극적인 장면

명제: $\sqrt{2}$는 무리수이다.

[Step 1. 억지 부정을 저지르다 (가정)] “아니야! $\sqrt{2}$는 무리수가 아니라 유리수(분수) 다!” 라고 억지로 가정해 봅시다.

[Step 2. 억지 논리를 전개하다] 유리수라면, 초등학교 때 배운 대로 깔끔하게 더 이상 안 나누어 떨어지는 기약분수 $\frac{a}{b}$ 로 쓸 수 있어야 합니다. (단, $a, b$는 더 이상 나눌 수 없는 서로소인 정수) $\sqrt{2} = \frac{a}{b}$ 양변을 제곱해서 루트 껍데기를 벗겨냅니다. $2 = \frac{a^2}{b^2}$ $\rightarrow$ $a^2 = 2b^2$ 여기서 잠깐! 어떤 수($b^2$)에 2를 곱했으니, 우변 $2b^2$ 은 무조건 ‘짝수’입니다. 따라서 좌변도 똑같이 $a^2$ 도 짝수여야 합니다. 제곱해서 짝수면 본래 숫자 $a$ 도 무조건 짝수(2, 4, 6…) 일 수밖에 없습니다!

$a$ 가 짝수니까 $a = 2k$ 라고 치환해서 식에 다시 대입해 봅니다. $(2k)^2 = 2b^2$ $\rightarrow$ $4k^2 = 2b^2$ $\rightarrow$ 양변을 2로 나누면 $b^2 = 2k^2$ !!

[Step 3. 치명적 낭떠러지(모순)와 맞닥뜨리다] 오잉? $b^2$ 도 2가 곱해져서 짝수이고, 따라서 $b$ 도 무조건 짝수 여야 합니다.

잠깐… 처음에 우리가 뭐라고 가정했죠? 분수 $\frac{a}{b}$는 약분이 싹 다 끝난 ‘서로소(더는 안 나눠짐)’ 라고 호언장담했습니다. 그런데 논리를 까보니 $a$도 짝수, $b$도 짝수? 그럼 무조건 2로 또 약분이 되잖아요!! 이것은 서로소라는 초기 세팅을 정면으로 위반하는 ‘논리적 붕괴(모순)’ 입니다!

[Step 4. 배수진 폭파: 참/거짓 확정 도출] 왜 이런 말도 안 되는 모순이 터졌나요? 바로 최초에 ”$\sqrt{2}$를 유리수(분수)”라고 무모하게 억지 조작(부정) 했기 때문입니다! 따라서 최초의 억지가 틀렸으므로, 처음의 명제였던 ”$\sqrt{2}$는 분수로 절대로 나타낼 수 없는 무리수이다” 라는 주장은 10,000% 참(True)으로 우주의 진솔로 확정됩니다.

4. 학습 정리 (Summary)

  1. 귀류법(Proof by Contradiction): 증명해야 할 명제의 결론을 반대로 뒤집어 ‘거짓’이라고 가정한 뒤 논리를 짜나가다가, 절대 일어날 수 없는 헛소리(모순)에 부딪히게 만들어, “거짓이라고 억지 쓴 것이 틀렸으니 본래 문장이 참 맞잖아!” 하고 되받아치는 고급 수학 논리 증명 스킬입니다.
서브목차