25주차 — 동치(iff) 증명

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

이 주의 길잡이

핵심 문장: 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\)) 파트 + 종합 선언)을 백지에 쓸 수 있다.

  2. 방향마다 다른 기법(직접\(\cdot\)대우\(\cdot\)귀류)을 고르는 기준을 세우고, 한 증명 안에서 조합한다.

  3. “다음은 모두 동치이다(TFAE)”를 순환 사슬로 증명하고, 사슬이 충분한 이유를 설명한다.

  4. 동치 변형 사슬(\(\iff\) 연쇄)을 쓰고, 비가역 변형(제곱 등)이 끼었을 때 무엇이 무너지는지 안다.

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

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

  1. \(P \iff Q\)는 어떤 두 명제의 \(\land\)인가? (8주차 정의 8.2)

  2. “\(n\)이 짝수 \(\iff\) \(n^2\)이 짝수”의 두 방향 각각에 적합한 기법은? (8주차 문제 14의 계획)

  3. 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\)에 그대로 대어 보자.

시도 — 조건문 하나로 밀어붙이기

명제: 실수 \(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\)이다. 참인 계산만으로 이루어진 답안이 거짓 명제를 결론으로 내놓았다.

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

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

답

증명된 문장은 “\(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}\)

거짓

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

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

답

(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) [백지 암기 대상]#

명제 \(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)과 같은 붕괴다.

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

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

답

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

(\(\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\)”다.

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

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

답

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

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

두 줄로 재현하면 된다. “\(n^2\)이 홀수이면 \(n\)이 홀수”로 적는 경우가 많은데,

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

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

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

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

확인 5. \(P_1, P_2, P_3\)가 모두 동치임을 쌍마다 iff로 보인다면, 증명해야 할

조건문은 모두 몇 개인가.

답

쌍은 \(\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 \]

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

“\(P_2 \Rightarrow P_1\)”은 어떻게 복원되는가.

답

사슬을 따라 이어 간다: \(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) [백지 암기 대상]#

“다음은 모두 동치이다”(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}\)

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

지목하면 된다.

답

(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)이다.

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

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

답

\(\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주차 최소원리에서 한다.

확인 9. 어떤 답안의 마지막 줄이 “(\(\Rightarrow\))와 (\(\Leftarrow\))를 모두

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

답

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

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

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