# 25주차 — 동치(iff) 증명

:::{admonition} 이 주의 길잡이
:class: keybox

**핵심 문장**: iff 증명은 조건문 두 개이고, 방향마다 기법을 따로 고를 수 있다.

**이 주의 위치**: 50주 과정의 25주차. 6부(비조건 명제)의 첫 주이며, 8주차에서 진리표로만 다루던 쌍조건문이 증명 서식으로 승격된다.

**원서 대응**: BoP(Book of Proof) 7.1 (If-and-Only-If Proof), 7.2 (Equivalent Statements). 원서 없이 읽을 수 있다.
:::

## 이번 주 목표

1. $P \iff Q$의 증명 서식(($\Rightarrow$) 파트 + ($\Leftarrow$) 파트 + 종합 선언)을 백지에 쓸 수 있다.
1. 방향마다 다른 기법(직접$\cdot$대우$\cdot$귀류)을 고르는 기준을 세우고, 한 증명 안에서 조합한다.
1. "다음은 모두 동치이다(TFAE)"를 순환 사슬로 증명하고, 사슬이 충분한 이유를 설명한다.
1. 동치 변형 사슬($\iff$ 연쇄)을 쓰고, 비가역 변형(제곱 등)이 끼었을 때 무엇이 무너지는지 안다.

본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다.

## 준비 운동 (24주차 복습)

1. $P \iff Q$는 어떤 두 명제의 $\land$인가? (8주차 정의 8.2)
1. "$n$이 짝수 $\iff$ $n^2$이 짝수"의 두 방향 각각에 적합한 기법은? (8주차 문제 14의 계획)
1. 24주차 중간 평가에서 틀린 문항 1개를 백지로 재시도하시오.

### 자주 나오는 세 가지 답 — 2번 문항

방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 옳은 부분이 있고, 셋 다 이번 주에 메울 정확한 간격이 있다.

- **유형 1 — 한 방향만 계획.** "$n = 2k$로 놓고 $n^2 = 2(2k^2)$을 만든다 — 직접

증명"이라고 적고 끝낸다. 그 한 방향의 기법 선택은 정확하다. 빠진 것은 나머지 방향이다 — 물음은 "두 방향 각각"이었다. $\iff$에서 한 방향은 절반이 아니라 미완성이라는 것을 §1.1에서 확인한다.

- **유형 2 — 두 방향 모두 직접으로 계획.** "($\Leftarrow$)도 $n^2 = 2m$에서

시작해 $n = 2k$를 만든다"라고 적는다. 방향이 둘이고 각각이 독립된 조건문이라는 판단은 정확하다. 문제는 $n^2 = 2m$에서 $n$을 꺼내려면 제곱근이 필요하고 그 순간 정수 세계를 벗어난다는 점이다. 19주차의 신호 — 가정이 합성식이면 대우 — 를 방향마다 다시 읽어야 한다.

- **유형 3 — 대우를 만들 때 앞뒤를 바꾸지 않음.** "($\Leftarrow$)는 대우로 하면

'$n^2$이 홀수이면 $n$이 홀수'"라고 적는다. 대우로 갈아탄다는 판단은 정확하다. 간격은 뒤집기다 — ($\Leftarrow$) 파트는 "$n^2$이 짝수이면 $n$이 짝수"이므로 그 대우는 부정에 더해 앞뒤까지 바꾼 "$n$이 홀수이면 $n^2$이 홀수"다. 적은 문장은 ($\Rightarrow$) 파트의 대우다. §1.4에서 다시 짚는다.

## 개념 — 양방향 명제를 증명한다는 것

### 1 이전 도구만으로 ⇔를 밀어붙이면 어디서 무너지는가

지금까지의 네 기법(직접$\cdot$케이스$\cdot$대우$\cdot$귀류)은 전부 "가정 하나에서 결론 하나로" 가는 조건문 $P \Rightarrow Q$의 도구였다. 이번 주의 명제 $P \iff Q$에 그대로 대어 보자.

:::{admonition} 시도 — 조건문 하나로 밀어붙이기
:class: quotebox

명제: 실수 $x$에 대해 $x = 2 \iff x^2 = 4$.

"$x = 2$라 가정하자. 그러면 $x^2 = 2^2 = 4$이다. 따라서 $x = 2 \iff x^2 = 4$이다. $\blacksquare$"
:::

계산에 틀린 줄은 하나도 없다. 그런데 마지막에 선언된 명제는 **거짓**이다 — $x = -2$를 넣으면 $x^2 = 4$이지만 $x \neq 2$이다. 참인 계산만으로 이루어진 답안이 거짓 명제를 결론으로 내놓았다.

:::{container} quotebox
**확인 1.** 위 답안에서 실제로 증명된 문장과 마지막 줄에서 선언된 문장을 각각

적어 보자. 둘은 같은 문장인가.
:::

:::{admonition} 답
:class: quotebox dropdown

증명된 문장은 "$x = 2 \Rightarrow x^2 = 4$" 하나뿐이고, 선언된 문장은

"$x = 2 \iff x^2 = 4$"이다. 뒤쪽에는 앞쪽에 없는 "$x^2 = 4 \Rightarrow x = 2$"가

더 들어 있고, 더 들어간 그 부분이 거짓인 부분이다. 9주차에서 확인한 대로 역은

자동으로 따라오지 않으므로, 한 방향의 증명은 다른 방향에 대해 아무것도 말해 주지 않는다.
:::

막힌 자리가 어디인지는 8주차 정의 8.2가 알려 준다.

$$
P \iff Q \quad \equiv \quad (P \Rightarrow Q) \land (Q \Rightarrow P)
$$

$\iff$는 조건문이 아니라 조건문 **두 개의 $\land$**다. 그리고 "그리고"로 묶인 결론은 두 부분을 각각 증명해야 한다(18주차 문제 18). 필요한 것은 새 기법이 아니라 기존 기법을 두 번 쓰는 **배치**다.

### 2 두 조건문으로 — 서식을 만들어 보기

각 행에서 두 방향을 따로 적고, 각각의 참$\cdot$거짓과 전체의 참$\cdot$거짓을 판정해 보자.

| **$P$ / $Q$** | **($\Rightarrow$) 방향** | **참$\cdot$거짓** | **($\Leftarrow$) 방향** | **참$\cdot$거짓** | **$P \iff Q$** |
|---|---|---|---|---|---|
| $x = 2$ / $x^2 = 4$ | $x = 2 \Rightarrow x^2 = 4$ | 참 | $x^2 = 4 \Rightarrow x = 2$ | 거짓 ($x = -2$) | 거짓 |
| $x + 2 = 5$ / $x = 3$ | $\underline{\quad(1)\quad}$ | $\underline{\quad}$ | $\underline{\quad(2)\quad}$ | $\underline{\quad}$ | $\underline{\quad}$ |
| $n$은 짝수 / $n^2$은 짝수 | $\underline{\quad(3)\quad}$ | 참 (1주차 문제 9) | $\underline{\quad(4)\quad}$ | $\underline{\quad}$ | $\underline{\quad}$ |
| $n$은 소수 / $n$은 홀수 | $n$ 소수 $\Rightarrow n$ 홀수 | $\underline{\quad(5)\quad}$ | $n$ 홀수 $\Rightarrow n$ 소수 | $\underline{\quad(6)\quad}$ | 거짓 |

:::{container} quotebox
**확인 2.** 빈칸 (1)~(6)을 채우고, 전체 열의 참$\cdot$거짓이 두 방향의 참$\cdot$거짓과

어떤 관계에 있는지 한 문장으로 적어 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

(1) $x + 2 = 5 \Rightarrow x = 3$ — 참. (2) $x = 3 \Rightarrow x + 2 = 5$ — 참. 전체도 참.

(3) $n$이 짝수 $\Rightarrow n^2$이 짝수. (4) $n^2$이 짝수 $\Rightarrow n$이 짝수 —

참이다(그 대우 "$n$이 홀수이면 $n^2$이 홀수"가 1주차 문제 11이다). 전체도 참.

(5) 거짓 — $n = 2$는 소수이면서 짝수다. (6) 거짓 — $n = 9$는 홀수이지만 소수가

아니다. 전체도 거짓.

관계: 전체 열은 두 방향 열을 $\land$로 묶은 것과 정확히 같다 — 두 방향이

**모두** 참인 행에서만 전체가 참이다.
:::

관찰이 그대로 증명의 순서가 된다 — 두 방향을 각각 증명하고 마지막에 묶는다. 이 순서에 이름을 붙인다. 식 자체에 새로운 것은 없다. 8주차 정의 8.2를 증명이 진행되는 순서로 옮겨 적었을 뿐이다.

### 정의 25.1 — 동치 증명 (proof of a biconditional) [백지 암기 대상]

:::{container} quotebox
명제 $P \iff Q$의 증명은 다음 세 부분으로 이루어진다.

($\Rightarrow$) $P$라 가정하자. … 따라서 $Q$이다.

($\Leftarrow$) $Q$라 가정하자. … 따라서 $P$이다.

양방향이 증명되었으므로 $P \iff Q$이다. $\blacksquare$
:::

기호를 읽는 법까지가 서식이다. $P \iff Q$는 "$P$와 $Q$는 **동치**이다", "$P$는 $Q$이기 위한 **필요충분조건**이다", "$P$일 때 그리고 오직 그때만 $Q$이다"로 읽으며, 영어 표기 "if and only if"를 줄인 **iff**도 같은 뜻이다. 답안 안의 ($\Rightarrow$)와 ($\Leftarrow$)는 계산 기호가 아니라 **파트 이름표**다 — "지금부터 $P \Rightarrow Q$를 증명한다", "지금부터 $Q \Rightarrow P$를 증명한다"를 한 글자로 줄인 것이다.

### 3 서식 해부 — 조각마다 하는 일

| **조각** | **하는 일** | **증명에서의 역할** |
|---|---|---|
| 파트 이름표 ($\Rightarrow$) / ($\Leftarrow$) | 지금 어느 조건문을 다루는지 선언 | 현재 가정이 $P$인지 $Q$인지 고정한다 — 각 줄의 유효 범위 표시 |
| "$P$라 가정하자 … 따라서 $Q$이다" | 첫째 조건문 $P \Rightarrow Q$ | 그 자체로 완결된 조건문 증명 — 기법(직접$\cdot$대우$\cdot$귀류)은 자유롭게 고른다 |
| "$Q$라 가정하자 … 따라서 $P$이다" | 둘째 조건문 $Q \Rightarrow P$ | 역은 자동으로 따라오지 않으므로(9주차) 반드시 따로 증명해야 하는 자리 |
| "양방향이 증명되었으므로 …" | 두 결과를 $\land$로 묶는 종합 선언 | 정의 8.2를 근거로 두 조건문에서 $\iff$를 조립한다 (18주차 문제 18의 마감과 같은 꼴) |

**조각 삭제 실험.** 셋째 조각(($\Leftarrow$) 파트)을 지우면 §1.1의 시도가 그대로 서식을 통과해 거짓 명제 $x = 2 \iff x^2 = 4$가 "증명"된다. 거짓이 통과하는 순간 서식은 참과 거짓을 구별하지 못한다 — 정의 2.1에서 "정수"라는 조각을 지웠을 때 $a \neq 0$인 모든 쌍에서 $a \mid b$가 참이 되어 버린 것(2주차 확인 3)과 같은 붕괴다.

:::{container} quotebox
**확인 3.** 이번에는 첫째 조각(파트 이름표)과 넷째 조각(종합 선언)을 각각

지워 보자. 각각 무엇을 잃는가.
:::

:::{admonition} 답
:class: quotebox dropdown

이름표를 지우면 어느 문장이 어느 조건문에 속하는지 읽히지 않는다. 특히

($\Leftarrow$)를 대우로 증명한 경우 "$n$이 홀수라 가정하자"가 갑자기 나타나

원래 가정과 충돌하는 것처럼 보인다 — 내용은 남지만 각 줄이 어느 가정 아래

쓰였는지 복원할 수 없다.

종합 선언을 지우면 붕괴하지는 않는다. 잃는 것은 마감이다 — 증명해야 할 명제는

$P \iff Q$인데 답안은 조건문 두 개를 남긴 채 끝난다. 그 둘에서 $\iff$로

넘어가는 한 걸음이 정의 8.2의 인용이다.
:::

### 4 방향마다 기법을 따로 고른다

($\Rightarrow$) 파트와 ($\Leftarrow$) 파트는 **가정이 서로 다르다**. 기법 선택의 신호는 가정을 보고 읽는 것이므로(19주차), 신호도 방향마다 다시 읽는다. 명제 "$n$이 짝수 $\iff$ $n^2$이 짝수"로 읽어 보면 —

| **파트** | **그 파트의 가정** | **가정이 전개되는가** | **1순위 기법** |
|---|---|---|---|
| ($\Rightarrow$) | $n$이 짝수 | $n = 2a$로 즉시 풀린다 | 직접 |
| ($\Leftarrow$) | $n^2$이 짝수 | $n^2 = 2m$에서 $n$이 나오지 않는다 | 대우 |

한 명제의 두 방향에 서로 다른 기법이 걸리는 것은 예외가 아니라 흔한 일이다. 그리고 ($\Leftarrow$) 파트가 증명하는 문장은 "$Q \Rightarrow P$"이므로, 그 대우는 결론의 부정을 앞에, 가정의 부정을 뒤에 놓은 "$\neg P \Rightarrow \neg Q$"다.

:::{container} quotebox
**확인 4.** 위 명제의 ($\Leftarrow$) 파트를 대우로 바꾸면 어떤 문장이 되는가.

그 문장은 이미 증명돼 있는가.
:::

:::{admonition} 답
:class: quotebox dropdown

($\Leftarrow$) 파트는 "$n^2$이 짝수이면 $n$이 짝수"이므로 대우는 "$n$이 홀수이면

$n^2$이 홀수"다 — 1주차 문제 11에서 이미 증명한 명제이므로 근거 ④로 인용하거나

두 줄로 재현하면 된다. "$n^2$이 홀수이면 $n$이 홀수"로 적는 경우가 많은데,

이것은 부정만 하고 앞뒤를 바꾸지 않은 문장이며 실제로는 ($\Rightarrow$) 파트의

대우다. 부정과 뒤집기는 둘 다 해야 대우가 된다(9주차).
:::

### 5 TFAE — 세 개 이상이 모두 동치일 때

명제가 셋 이상이고 "이들은 모두 동치이다"를 보여야 하는 상황이 있다. 정의 25.1을 쌍마다 적용하는 것이 첫 후보다.

:::{container} quotebox
**확인 5.** $P_1, P_2, P_3$가 모두 동치임을 쌍마다 iff로 보인다면, 증명해야 할

조건문은 모두 몇 개인가.
:::

:::{admonition} 답
:class: quotebox dropdown

쌍은 $\binom{3}{2} = 3$개(13주차)이고 쌍마다 양방향이므로 $3 \times 2 = 6$개다.

명제가 5개면 $2\binom{5}{2} = 20$개로 늘어난다 — 명제 수가 늘면 증명 수가

제곱으로 불어난다.
:::

여섯 개를 다 쓸 필요는 없다. 세 개면 충분하다.

$$
P_1 \Rightarrow P_2, \qquad P_2 \Rightarrow P_3, \qquad P_3 \Rightarrow P_1
$$

:::{container} quotebox
**확인 6.** 위 세 조건문만 증명했다고 하자. 사슬에 직접 등장하지 않는

"$P_2 \Rightarrow P_1$"은 어떻게 복원되는가.
:::

:::{admonition} 답
:class: quotebox dropdown

사슬을 따라 이어 간다: $P_2 \Rightarrow P_3$이고 $P_3 \Rightarrow P_1$이므로

$P_2 \Rightarrow P_1$이다. 조건문이 추이적이라는 사실(9주차 문제 9)이 근거다.

순환이므로 어느 지점에서 출발해도 어느 지점에든 도달할 수 있고, 따라서 임의의

$i, j$에 대해 $P_i \Rightarrow P_j$가 전부 복원된다.
:::

### 정의 25.2 — 순환 사슬 증명 (TFAE) [백지 암기 대상]

:::{container} quotebox
"다음은 모두 동치이다"(The Following Are Equivalent, 줄여서 **TFAE**)로 제시된

명제 $P_1, P_2, \dots, P_n$에 대해,

$$
P_1 \Rightarrow P_2 \Rightarrow \cdots \Rightarrow P_n \Rightarrow P_1
$$

의 $n$개 조건문을 증명하면 충분하다. 임의의 두 명제 사이의 양방향은 사슬의 두

구간을 이어 붙여 복원된다(조건문의 추이성).
:::

증명 수는 $2\binom{n}{2} = n(n-1)$개에서 $n$개로 줄어든다. 대신 사슬의 **순서를 고르는 일**이 새로 생긴다 — 화살표가 쉬운 방향을 먼저 살펴보고 순환을 짠다. 이 설계를 예제 2.3에서 직접 한다.

### 6 동치 변형 사슬 — 그리고 비가역 변형의 함정

$\iff$를 한 줄로 이어 쓰는 방식도 있다. 각 단계가 진짜 $\iff$이기만 하면 사슬 전체가 양 끝의 동치를 준다.

$$
x^2 = x \iff x^2 - x = 0 \iff x(x-1) = 0 \iff x = 0 \ \text{또는}\ x = 1
$$

이 한 줄이 "방정식을 푼다"의 정체다 — 고교에서 하던 식 변형은 동치 사슬 만들기였다. 문제는 모든 변형이 $\iff$는 아니라는 점이고, 되돌리는 연산이 있는 변형만 $\iff$를 보존한다.

| **변형** | **되돌리는 연산** | **$\iff$인가** |
|---|---|---|
| 양변에 3을 더한다 | 양변에서 3을 뺀다 | 예 |
| 양변을 $5$로 나눈다 | 양변에 5를 곱한다 | 예 |
| 인수분해한다 | 전개한다 | 예 (같은 식의 다른 표기) |
| 양변에 $x$를 곱한다 | $\underline{\quad(1)\quad}$ | $\underline{\quad(2)\quad}$ |
| 양변을 제곱한다 | $\underline{\quad(3)\quad}$ | $\underline{\quad(4)\quad}$ |

:::{container} quotebox
**확인 7.** 빈칸 (1)~(4)를 채워 보자. 되돌리는 연산이 없거나 조건이 붙는 자리를

지목하면 된다.
:::

:::{admonition} 답
:class: quotebox dropdown

(1) 양변을 $x$로 나눈다 — 그러나 $x = 0$이면 나눌 수 없다. (2) 아니오.

$x = 1$의 양변에 $x$를 곱하면 $x^2 = x$가 되고, 이 식은 $x = 0$도 해로 갖는다.

(3) 양변에 제곱근을 취한다 — 그러나 제곱근은 부호를 되돌려 주지 못한다.

(4) 아니오. $x = 2 \Rightarrow x^2 = 4$는 참이지만 역은 거짓이다($x = -2$).

§1.1의 시도가 무너진 자리가 정확히 이 칸이었다.
:::

**무연근의 정체.** 제곱 단계가 끼면 사슬은 $\iff$에서 $\Rightarrow$로 격하되고, 결과 방정식의 해집합은 원래 해집합을 **포함하는 더 큰 집합**이 된다. 그 초과분이 고교에서 만난 **무연근**(extraneous root)이다.

:::{container} quotebox
**확인 8.** $\sqrt{x} = x - 2$의 양변을 제곱해 풀면 후보 $x = 1, 4$가 나오는데

$x = 1$은 원래 방정식을 만족하지 않는다. 그렇다면 $x = 1$은 어느 방정식의 해인가.
:::

:::{admonition} 답
:class: quotebox dropdown

$\sqrt{x} = -(x - 2)$의 해다. $x = 1$을 넣으면 좌변은 $\sqrt1 = 1$, 우변은

$-(1 - 2) = 1$로 성립한다. 제곱은 $A = B$와 $A = -B$를 구별하지 못하므로 제곱한

식은 두 방정식의 해를 **합쳐서** 갖는다. 그래서 제곱을 쓴 뒤에는 원래 식에

대입해 검증하는 단계가 선택이 아니라 필수가 된다(문제 19).
:::

### 7 근거 목록 갱신 — 서식은 늘고 근거 칸은 그대로

| **근거** | **내용** | **이번 주에는 이렇게 쓴다** |
|---|---|---|
| ① 정의 | 지금까지의 모든 정의 + 정의 8.2(쌍조건문) | "$P \iff Q$는 두 조건문의 $\land$"를 종합 선언의 근거로 인용한다 |
| ② 닫힘성 | 정수의 합$\cdot$차$\cdot$곱은 정수 | 각 파트 안의 계산에서 이전과 똑같이 쓴다 |
| ③ 등식의 성질 | 대입 / 전개 / 묶기 / 양변 연산 | 동치 사슬의 각 단계가 가역인지 확인하며 쓴다(§1.6) |
| ④ 이미 증명한 명제 | 1~24주차의 예제$\cdot$문제 전부 + **이번 주의 예제 2.2와 그 보조정리, 영인수 성질(문제 13에 딸린 상자)**. 보조정리가 쓰는 두 부품도 여기에 속한다 — $\vert xy\vert  = \vert x\vert \vert y\vert $(17주차 문제 10), 그리고 "0이 아닌 정수의 절댓값은 1 이상"(22주차 §1.9에서 인정하고 쓰는 사실, 증명은 33주차) | 한 방향이 이미 증명돼 있으면 그 방향은 인용 한 줄로 끝낸다 |

정의 25.1과 25.2는 근거가 아니라 **서식**이다 — 답안을 배치하는 순서를 정할 뿐, 그 자체가 어떤 문장을 참으로 만들지는 않는다. 각 파트 안에서 실제로 참을 만드는 것은 여전히 근거 ①~④다. 그리고 17주차에서 인정하고 쓰기로 한 **나눗셈 정리** (정수 $a$와 자연수 $d$에 대해 $a = dq + r$, $0 \le r < d$인 정수 $q, r$이 유일하게 존재한다)를 예제 2.2에서 그대로 쓴다. 증명은 33주차 최소원리에서 한다.

:::{container} quotebox
**확인 9.** 어떤 답안의 마지막 줄이 "($\Rightarrow$)와 ($\Leftarrow$)를 모두

보였다. $\blacksquare$"이다. 이 줄은 근거 ①~④ 중 무엇을 인용하고 있는가.
:::

:::{admonition} 답
:class: quotebox dropdown

근거 ①이다 — 정의 8.2("$P \iff Q$는 두 조건문의 $\land$")를 인용해 두 조건문에서

$\iff$를 조립하는 줄이기 때문이다. "정의 8.2에 의해 두 방향의 성립은

$P \iff Q$와 같은 말이다"라고 적으면 근거가 겉으로 드러난다.
:::