02. Basic Proof Techniques

1. 왜 수학적 증명이 필요한가?

비둘기집의 원리처럼 직관적으로 당연해 보이는 문장도, 믿지 않는 사람을 설득하려면 결국 논리적인 근거가 필요하다. 그게 바로 수학적 증명(mathematical proof)이다. 증명은 하나 이상의 전제(premise)에서 출발해 논리적 규칙을 통해 결론(conclusion)을 도출하는 과정이며, 좋은 증명은 세 가지 조건을 만족해야 한다.

• Precise(정확): 용어를 수학적으로 명확히 정의할 것 (예: "홀수란 2k+1로 쓸 수 있는 정수")
• Complete(완결): 논리의 빈틈이 없을 것
• Unambiguous(명확): 해석이 두 가지 이상이어선 안 될 것

2. 수학적 언어: Quantifier와 Predicate

일상 언어는 종종 모호하다. "Everybody loves somebody"라는 문장만 봐도 두 가지로 해석된다. 이때 등장하는 게 quantifier(한정자) 와 predicate(술어) 다.

• ∀ : for all (모든)
• ∃ : there exists (어떤 ~가 존재한다)

Predicate는 명제의 틀(template)인데, 핵심은 동사(관계)가 틀 안에 이미 고정되어 있다는 점이다. 예를 들어 P(A, B) := "A loves B"라고 정의하면, P라는 predicate 자체가 이미 "loves"라는 관계를 담고 있다. 괄호 안의 인수(argument)만 바뀌는 것이다. 그러므로 "B hates C"는 P(B, C)가 아니라 H(B, C) := "B hates C"처럼 별도의 predicate로 정의해야 한다.

그리고 quantifier의 순서는 의미를 완전히 바꾼다.

• ∀A ∃B "A loves B" → 모든 사람은 각자 좋아하는 누군가가 있다. (B가 사람마다 달라도 됨)
• ∃B ∀A "A loves B" → 모든 사람이 공통으로 좋아하는 단 한 명 B가 존재한다.

3. 증명의 종류

(1) Direct proof (직접 증명)

가정 p를 출발점으로 삼아 논리적 단계를 밟아 결론 q를 도출하는 가장 기본적인 방식이다.


Theorem 2.4 : 모든 홀수는 두 정수의 제곱의 차로 표현할 수 있다.


홀수는 2k+1로 쓸 수 있고, 이를 정리하면 (k+1)² - k²가 된다. m = k+1, n = k로 놓으면 2k+1 = m² - n²이 성립한다.

이처럼 구체적인 m, n을 직접 제시하는 방식을 constructive proof(구성적 증명) 이라고도 한다. 반대로 존재는 증명하지만 어떻게 찾는지는 알려주지 않는 경우를 nonconstructive proof 라고 한다. 비둘기집 증명이 대표적인 예다. 어느 집에 비둘기가 두 마리인지는 알 수 없다.

(2) Contrapositive (대우를 이용한 증명)

p → q를 직접 증명하기 어려울 때, 이와 동치인 대우 ¬q → ¬p를 증명하는 방식이다.

명제와 관련된 변형들의 관계를 정리하면:

이름	형태	원래 명제와의 관계
역(Converse)	q → p	동치 아님
이(Inverse)	¬p → ¬q	동치 아님
대우(Contrapositive)	¬q → ¬p	동치

"if and only if(iff)"를 증명할 때는 양방향을 모두 증명해야 한다. 한 방향은 직접 증명으로, 다른 방향은 대우로 증명하는 게 편할 때도 많다.

(3) Proof by contradiction (귀류법)

증명하고 싶은 주장의 부정을 가정한 뒤, 논리적 모순을 이끌어냄으로써 원래 주장이 참임을 보이는 방법이다. √2가 무리수임을 증명할 때 "√2가 유리수라고 가정"하고 시작하는 게 대표적인 예다.

(4) Case analysis (경우 분석)

일반적인 명제를 여러 개의 세부 경우로 나누어 각각을 따로 증명한 뒤, 전체 명제가 참임을 도출하는 방식이다. 이때 나눈 경우들이 모든 경우를 빠짐없이 포함(exhaustive) 해야 한다는 점이 중요하다.