1. 증명의 기초

해석학의 언어인 증명을 처음부터 — 명제와 양화사부터 직접증명·대우·귀류법, 강한 귀납법, 동치관계와 함수 증명까지, Hammack의 Book of Proof 흐름을 따라갑니다.

• 명제와 진리표 — 연결사를 바꾸면 $P$, $Q$ 열은 고정된 채 새 연결사 열이 다시 채워집니다. 음영으로 표시된 $P \to Q$ 열과 대우 $\lnot Q \to \lnot P$ 열을 한 행씩 비교해 보세요 — 네 행 모두 똑같습니다. 그러나 역 $Q \to P$ 열은 $(T, F)$ 행에서 갈라집니다.
• 전칭·존재 양화사 — 수직선 위의 게임입니다: 도전자가 $x$를 제시하면 답하는 쪽이 더 큰 $y = x + 1$을 올려놓습니다 — $\forall x \,\exists y \,(y > x)$. 순서를 바꾸면 같은 게임이 무너집니다. 그리고 $\varepsilon$-$\delta$ 줄은 이 패턴 그대로이며, $f(t) = 2t$에서는 $\delta = \varepsilon/2$가 답입니다.
• 직접증명 — 두 유리수 $r_1 = \frac{p_1}{q_1}$, $r_2 = \frac{p_2}{q_2}$의 합을 수직선 위에 표시하고, 가정에서 결론까지 곧바로 이어지는 계산 $\frac{p_1 q_2 + p_2 q_1}{q_1 q_2}$을 따라간다 — 이것이 직접증명이다.
• 대우법 — $n^2$이 짝수인 행이 정확히 $n$이 짝수인 행과 일치하는 $n = 1..12$ 표 — "$n^2$ 짝수 $\Rightarrow$ $n$ 짝수"의 직접증명이 막히는 곳에서, 대우 "$n$ 홀수 $\Rightarrow$ $n^2$ 홀수"의 계산 $(2k+1)^2 = 2(2k^2+2k)+1$이 열린다.
• 귀류법 — 소수가 전부 $p_1, \ldots, p_k$뿐이라 가정해 보자 — 칩 위에 그 목록, $P = p_1 \cdots p_k$, 그리고 $N = P+1$이 놓인다. 어떤 목록의 소수로도 나누어떨어지지 않지만(나머지 1) 소인수를 가지는 $N$ — 그 소인수는 목록 밖에 있다. 모순이다. $k = 6$에서는 $N = 30031 = 59 \times 509$처럼 합성수여도 증명이 온전함을 보여, 귀류법의 모양($\lnot P$ 가정 → 모순 → $P$)을 익힌다.
• 경우 나누기와 존재 증명 — 점 $(x, y)$를 움직이면 그 점이 속한 사분면이 음영되고, 그 경우의 계산 $|xy| = |x|\cdot|y|$가 펼쳐진다 — 네 경우(와 축)가 평면을 빠짐없이 덮는다. 한편 $c = \sqrt{2}^{\sqrt{2}}$에서 갈라지는 두 갈래는 어느 쪽이 참인지 밝히지 않고도 "무리수 $a, b$와 유리수 $a^b$가 존재한다"는 결론에 도달한다 — 비구성적 존재 증명의 맛.
• 반례와 필요충분조건 — 단 하나의 반례가 보편 주장을 무너뜨리는 모습을, 네 개의 거짓 주장 — 모든 소수는 홀수, $4 \mid n^2 \Rightarrow 4 \mid n$, 무리수끼리의 합은 무리수, $|x| = |y| \Rightarrow x = y$ — 위에서 확인하세요. $n$을 밀며 가정과 결론의 표시등을 켜고 끄다 보면 $\lnot(\forall x\, P(x)) = \exists x\, \lnot P(x)$가 손에 잡힙니다. 반대 방향의 기술 — $P \iff Q$의 양쪽 화살표를 각각 증명하는 일 — 은 문제에서 이어집니다.
• 강한 귀납법 — $n = 30$의 소인수분해 트리를 그려 보면 강한 귀납법이 왜 필요한지 보입니다 — 분기는 $n-1 = 29$가 아니라 $15$와 $2$처럼 훨씬 작은 수들로 떨어집니다. $n$을 밀어 트리가 다시 그려지는 동안, $P(2), \dots, P(n-1)$ 전체를 가정하는 귀납 단계를 따라가 보세요. 약한 귀납의 $P(n-1)$만으로는 인자들에 닿을 수 없습니다.
• 동치관계 — $n$으로 나눈 나머지가 같으면 같은 조각에 — 합동을 동치관계로 배우는 장면입니다: 반사·대칭·추이 세 공리를 $0$부터 $3n-1$까지 모든 원소·쌍·삼중항에 대해 brute force로 검증하고, 동치류 $[r] = \{r, r+n, r+2n\}$이 집합을 겹침 없이 나눈 모습을 $n$을 움직이며 직접 봅니다.
• 함수 합성 증명 — 합성 함수의 단사성·전사성 법칙을 구체적 표로 증명하는 장면입니다: $g \circ f$가 단사이면 $f$도 단사, $g \circ f$가 전사이면 $g$도 전사 — 그리고 역이 왜 거짓인지($g$가 단사일 필요가 없고 $f$가 전사일 필요가 없음)를 화살표 그림 위에서 직접 확인합니다. 전단사인 경우 $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$의 순서 뒤집힘까지 계산으로 보입니다.