# 22주차 — 귀류법 2: 조건문의 귀류 증명과 기법 조합

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

**핵심 문장**: 조건문을 귀류로 부정하면 가정이 한 개에서 두 개로 늘어난다 — $P$와 $\neg Q$를 동시에 손에 쥔다.

**이 주의 위치**: 50주 과정의 22주차. 21주차에서 세운 귀류법을 조건문에 적용하고, 직접$\cdot$대우$\cdot$귀류 세 기법의 선택 순서를 정한다.

**원서 대응**: BoP(Book of Proof) 6.2–6.4. 원서 없이 읽을 수 있다.
:::

## 이번 주 목표

1. 조건문 $P \Rightarrow Q$의 귀류 증명 서식($P \land \neg Q$를 가정하는 형식)을 백지에 쓰고, 각 조각이 하는 일을 설명할 수 있다.
1. 대우 증명이 귀류법의 특수형임을 도착점의 관점에서 설명할 수 있다.
1. 귀류와 경우 나누기, 귀류와 기약분수를 조합한 증명을 세 개 이상 쓸 수 있다.
1. 기법 선택 가이드 네 조를 쓰고, "귀류 껍데기 안의 직접 증명"을 스스로 판별할 수 있다.

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

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

1. $\sqrt{2}$가 무리수임을 보이는 증명에서 "기약분수로 잡는다"는 가정이 하는 역할을 한 문장으로 쓰시오.
1. 빈칸을 채우시오: $\neg(P \Rightarrow Q) \equiv \underline{\quad}$ (9주차 문제 7 — 이번 주의 주인공이다.)
1. 소수가 무한히 많음을 보이는 증명에서 $N = p_1 p_2 \cdots p_n + 1$이 소수라고 주장하면 왜 안 되는지 쓰시오.

답을 노트에 적어 둔다. 이번 주 끝(§5 재현 뒤)에 이 기록을 다시 본다.

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

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

- **유형 1 — 부정을 양쪽에 나눠 넣기.** $\neg P \Rightarrow \neg Q$라고 적는다.

"부정한다"는 지시를 두 자리에 성실하게 적용한 결과이고, 그 조작 자체는 정확하다. 문제는 만들어진 것이 부정이 아니라는 점이다 — $\neg P \Rightarrow \neg Q$는 9주차에서 **이**(inverse)라는 이름으로 다룬 별개의 명제이고, 원문과 진리값이 반대가 아니다($P$가 거짓이고 $Q$가 참인 상황에서 원문도 참, 이 명제도 참이다). 부정의 자격은 "모든 상황에서 진리값이 정확히 반대"이며, 11주차 §1.3의 총목록이 그 자격을 통과한 규칙만 모아 놓은 표다.

- **유형 2 — 결론만 부정해 조건문으로 남기기.** $P \Rightarrow \neg Q$라고 적는다.

부정이 결론 자리에 있어야 한다는 판단은 옳다. 빠진 것은 **조건문이라는 껍데기가 사라진다**는 점이다. 조건문이 거짓인 상황은 "가정이 참인데 결론이 거짓"인 한 가지뿐이므로(8주차 정의 8.1), 그 상황을 문장으로 적으면 조건문이 아니라 "그리고"로 이어진 두 문장이 된다. 이번 주의 첫 줄이 통째로 이 전환이다.

- **유형 3 — $P \land \neg Q$까지 정확히 적었지만 쓸 곳을 모른다.** 9주차 문제 7의

결과를 그대로 적었으므로 그 자체로 정답이다. 남은 것은 이 등식을 증명의 첫 줄로 쓰는 일이다 — 부정이 가정 자리로 내려오면 재료가 하나에서 둘로 늘고, 그 둘을 충돌시키는 것이 이번 주의 기술이다. §1.2가 그 전환의 자리다.

## 개념 — 조건문을 귀류로 부정하기

### 1 21주차의 틀을 조건문에 그대로 얹으면 어디서 막히는가

이번 주의 첫 소재는 다음 명제다.

:::{container} quotebox
**명제.** 정수 $a, b, c$에 대해, $a \mid b$이고 $a \nmid c$이면 $a \nmid (b + c)$이다.
:::

지금까지 세운 도구 세 가지로 차례로 밀어붙여 보자.

:::{admonition} 시도 1 — 직접 증명
:class: quotebox

"$a \mid b$이고 $a \nmid c$라 가정하자. 정의 2.1에 의해 $b = ak$인 정수 $k$가

존재한다. 보여야 할 것은 $a \nmid (b + c)$, 곧 $b + c = a \times (\text{정수})$인

정수가 존재하지 **않는다**는 것이다. 따라서 … "
:::

여기서 멈춘다. 직접 증명의 몸통은 결론의 정의 꼴을 실제로 만들어 제시하는 과정인데, 만들라는 것이 "존재하지 않음"이다. 제시할 대상이 없으므로 다음 줄이 나오지 않는다 — 21주차 §1.1에서 만난 것과 같은 막힘이다.

:::{admonition} 시도 2 — 21주차의 귀류법을 그대로
:class: quotebox

"모순을 이끌어내기 위해, 명제가 거짓이라고 가정하자. 곧 $a \mid b$이고

$a \nmid c$가 아니라고 가정하자. 그러면 … "
:::

여기서도 멈춘다. 부정한 것이 명제 전체가 아니라 **가정 부분**이다. $\neg P$를 가정해 모순을 얻으면 증명되는 것은 $P$ 자체 — "$a \mid b$이고 $a \nmid c$이다"라는, 원명제와 아무 상관 없는 주장이다. 조건문의 부정을 어떻게 만드는지가 관문이다.

:::{admonition} 시도 3 — 대우로 갈아타기
:class: quotebox

"대우로 증명한다. $\neg Q$는 '$a \mid (b + c)$'이고, $\neg P$는 드모르간 1에

의해 '$a \nmid b$ 또는 $a \mid c$'이다. 대우는 '$a \mid (b+c)$이면 $a \nmid b$

또는 $a \mid c$이다'. $a \mid (b+c)$라 가정하자. 그러면 … "
:::

여기서도 멈춘다. 도착점이 "또는"이므로 어느 쪽을 만들어야 하는지 지목할 수 없다(19주차 §1.5 셋째 신호가 거꾸로 작동한 자리다). 게다가 원명제의 가정 $a \mid b$가 결론 쪽으로 넘어가 버려 손에 없다.

:::{container} quotebox
**확인 1.** 시도 1과 시도 3이 막힌 자리를 각각 한 문장으로 적어 보자. 그리고 이 명제를 뚫으려면 어떤 정보 **두 개**가 동시에 손에 있어야 하는가.
:::

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

시도 1은 도착점이 "존재하지 않음"이라 만들 목표 꼴이 없어서 막혔다.

시도 3은 도착점이 "또는"이라 어느 쪽을 만들지 지목할 수 없어서 막혔다.

동시에 손에 있어야 할 두 정보는 $a \mid b$와 $a \mid (b + c)$다. 이 둘이

함께 있으면 2주차 문제 17($a \mid (b+c)$이고 $a \mid b$이면 $a \mid c$)이

발동해 $a \mid c$가 나오고, 그것이 남은 가정 $a \nmid c$와 정면으로 충돌한다.

문제는 지금까지의 기법이 가정을 **한 번에 하나만** 손에 쥐여 준다는 것이다 —

직접은 $P$만, 대우는 $\neg Q$만. 둘을 동시에 쥐는 방법이 §1.2다.
:::

### 2 조건문의 부정을 가정 자리에 놓으면 무엇이 손에 들어오는가

조건문 $P \Rightarrow Q$가 거짓인 상황은 단 하나 — 가정이 참인데 결론이 거짓인 경우다(8주차 정의 8.1). 그 상황을 문장으로 적은 것이 9주차 문제 7의 결과다.

$$
\neg(P \Rightarrow Q) \equiv P \land \neg Q
$$

세 명제에 실제로 적용해 보자. 각 행에서 $\neg Q$를 만들고, 그 부정을 가정했을 때 손에 들어오는 것을 적는다.

| **조건문 $P \Rightarrow Q$** | **가정 $P$** | **$\neg Q$** | **$P \land \neg Q$를 가정하면 손에 들어오는 것** |
|---|---|---|---|
| $x$가 무리수이면 $x + 3$은 무리수이다 | $x$는 무리수 | $x + 3$은 유리수 | $x$의 무리수성, 그리고 $x + 3 = \frac{p}{q}$인 정수 $p, q$ ($q \neq 0$) |
| $a \mid b$이고 $a \nmid c$이면 $a \nmid (b+c)$이다 | $a \mid b$이고 $a \nmid c$ | $\underline{\quad(1)\quad}$ | $b = ak$, $a \nmid c$, 그리고 $\underline{\quad(2)\quad}$ |
| $x + y \ge 2$이면 $x \ge 1$ 또는 $y \ge 1$이다 | $x + y \ge 2$ | $\underline{\quad(3)\quad}$ | 부등식 $x + y \ge 2$, 그리고 $\underline{\quad(4)\quad}$ |

:::{container} quotebox
**확인 2.** 빈칸 (1)(2)(3)(4)를 채우고, 넷째 열 전체에 공통으로 일어난 일을 한 문장으로 적어 보자.
:::

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

(1) $a \mid (b+c)$  (2) $b + c = am$인 정수 $m$

(3) $x < 1$이고 $y < 1$ (드모르간 2, 그리고 $\ge$의 부정은 $<$ — 11주차 §1.3)

(4) 부등식 $x < 1$과 $y < 1$

공통으로 일어난 일: **가정이 한 개에서 두 묶음으로 늘었다.** 원명제의 가정

$P$는 그대로 남아 있고, 거기에 $\neg Q$가 새 가정으로 얹혔다. 직접 증명에서

만들어야 했던 $Q$가 이제 가정 자리에서 부정된 채 재료가 된다.
:::

이 절차에 정식 이름과 형식을 붙인다. 식 자체에 새로운 것은 없다 — 방금 표에서 한 일(조건문의 부정을 가정 자리에 놓기)을 문장으로 굳혔을 뿐이다.

### 정의 22.1 — 조건문의 귀류 증명 (proving a conditional by contradiction) [백지 암기 대상]

:::{container} quotebox
조건문 $P \Rightarrow Q$를 **귀류법**으로 증명한다는 것은, 등식

$\neg(P \Rightarrow Q) \equiv P \land \neg Q$에 따라 **$P$이면서 $Q$가 아니라고**

가정하고, 거기서 모순을 이끌어낸다는 뜻이다.
:::

$P \land \neg Q$는 "피, 그리고 큐가 아니다"로 읽는다. 우리말 증명문에서는 "$P$인데 $Q$가 아니라고 가정하자"로 적는 경우가 많다 — "인데"가 $\land$를 읽는 방식이고, 두 문장이 **동시에** 성립한다고 선언하는 것이다. 읽는 법까지가 정의다.

### 3 정의 해부 — 조각마다 하는 일

정의 22.1은 네 조각으로 되어 있고, 조각마다 증명에서 맡는 역할이 다르다.

| **조각** | **하는 일** | **증명에서의 역할** |
|---|---|---|
| "$P$이면서" | 원명제의 가정을 그대로 유지 | 대우와 달리 $P$가 손에서 빠져나가지 않는다 — §1.1 시도 3의 막힘이 풀리는 자리 |
| "$Q$가 아니라고" | 결론의 정확한 부정 | 부정형 결론이 긍정형 가정으로 바뀌어 정의로 풀린다 |
| "가정하고" | 두 문장을 동시에 무대에 올린다 | 어느 쪽에서 출발해도 되고, 둘을 결합해도 된다 — 재료가 두 묶음이다 |
| "모순을 이끌어낸다" | 도착점 지정 | 도착점이 고정되지 않는다. $P$와 충돌해도 되고 다른 사실과 충돌해도 된다 |

**조각 삭제 실험.** 첫째 조각 "$P$이면서"를 지워 보자. 그러면 $\neg Q$만 가정하는 셈인데, 거기서 모순이 나오면 증명되는 것은 $Q$ 그 자체다 — 가정 $P$와 무관하게 $Q$가 항상 참이라는, 훨씬 강한 주장이다. 위 표 셋째 행에 적용해 보면 결과가 분명해진다. "$x < 1$이고 $y < 1$"만 가정하고 모순을 찾으면 찾아지지 않는다. $x = y = 0$이 실제로 그 조건을 만족하기 때문이다.

:::{container} quotebox
**확인 3.** $x + y \ge 2$라는 가정을 버리면 모순이 나오지 않는 이유를 위 문장에 이어 한 문장으로 적어 보자. 그리고 그 가정은 증명의 어느 줄에서 소비되는가.
:::

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

$x < 1$이고 $y < 1$은 그 자체로는 아무것도 어기지 않는 참인 상황이므로,

거기서 유도되는 어떤 문장도 모순일 수 없다. 이 가정이 소비되는 곳은

마지막 충돌 선언이다 — 두 부등식을 변끼리 더해 $x + y < 2$를 얻은 뒤,

그것을 가정 $x + y \ge 2$와 맞부딪히는 자리다. 조각 "$P$이면서"가 없으면

충돌할 상대 자체가 무대에 없다.
:::

**조각 변형 실험.** 둘째 조각 "$Q$가 아니라고"를 "$P$가 아니라고"로 바꾸어 보자. 이것이 §1.1 시도 2에서 실제로 일어난 일이다.

:::{container} quotebox
**확인 4.** $\neg P$를 가정하고 모순을 이끌어냈다면, 실제로 증명된 명제는 무엇인가. 그것이 원명제 $P \Rightarrow Q$와 어떻게 다른가.
:::

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

증명된 것은 $P$다 — "가정 부분이 참이다"라는 주장이다. 원명제는 "$P$가 참일

때 $Q$도 참이다"이므로 둘은 내용이 겹치지 않는다. 조건문의 증명은 $P$의

참$\cdot$거짓을 묻지 않는다. $P$를 참이라고 **가정한 상태에서** $Q$를 확보하는

것이 전부다. 첫 줄에서 무엇을 부정했는지가 틀리면 뒤의 모든 줄이 옳아도

다른 명제를 증명한 답안이 된다(21주차 확인 4와 같은 사고다).
:::

### 4 서식

:::{admonition} 백지 암기 대상
:class: keybox

**조건문 귀류 증명의 서식**

**명제.** $P$이면 $Q$이다.

**증명.** 모순을 이끌어내기 위해, $P$인데 $Q$가 아니라고 가정하자. (이 자리에서 $\neg Q$를 11주차 부정 규칙으로 정확히 서술한다.)

$\quad\vdots$

이는 ~와 모순이다. 따라서 $P$이면 $Q$이다. $\blacksquare$
:::

21주차 §1.5의 서식과 비교하면 달라진 것은 첫 줄 하나뿐이다. 서식 포인트는 세 가지다.

- **첫 문장에서 기법을 선언한다.** "모순을 이끌어내기 위해"가 없으면 뒤따르는

두 문장이 저자가 참이라고 믿는 주장으로 읽힌다.

- **가정 두 개를 둘 다 적는다.** $\neg Q$만 적고 $P$를 빠뜨리는 답안이 많다.

그러면 §1.3 삭제 실험의 상황이 되어 충돌할 상대가 사라진다.

- **마지막 줄에서 충돌한 두 문장을 지목한다.** "모순이다"만 적고 무엇과 무엇이

부딪혔는지 적지 않으면 도착점이 확인되지 않는다.

:::{container} quotebox
**확인 5.** 어떤 답안이 "$x + y \ge 2$이고 $x < 1$, $y < 1$이라 하자"로 시작한다. 서식상 무엇이 빠졌고, 그 결과 이 줄은 어떻게 읽히는가.
:::

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

"모순을 이끌어내기 위해"라는 기법 선언이 빠졌다. 그 문장이 없으면 세 부등식이

저자가 참이라고 주장하는 조건으로 읽히고, 뒤에 나오는 $x + y < 2$가 모순이

아니라 계산 결과처럼 보인다. 기법 선언은 장식이 아니라 뒤에 오는 모든 줄의

지위를 정하는 문장이다.
:::

### 5 세 기법의 재료와 도착지

이번 주에 세 번째 기법이 갖춰졌으므로 한 표에 모은다.

| **기법** | **손에 쥐는 가정** | **도착지** | **적용 대상** |
|---|---|---|---|
| 직접 (1주차) | $P$ — 한 개 | $Q$ 하나로 고정 | 조건문 (존재 명제는 15주차 §1.7의 증인 제작 서식) |
| 대우 (19주차) | $\neg Q$ — 한 개 | $\neg P$ 하나로 고정 | 조건문 |
| 귀류 (21~22주차) | $P$ 그리고 $\neg Q$ — 두 개 | 아무 모순 (고정되지 않음) | 아무 명제 |

:::{container} quotebox
**확인 6.** 가정이 두 개인 것이 장점인 이유와, 도착지가 고정되지 않은 것이 단점인 이유를 각각 한 문장으로 적어 보자.
:::

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

장점 — 결합할 수 있는 재료가 둘이므로, 어느 한쪽만으로는 발동하지 않는

부품을 쓸 수 있다(§1.1에서 $a \mid b$와 $a \mid (b+c)$가 둘 다 있어야 2주차

문제 17이 발동했다).

단점 — 만들 목표가 지정되어 있지 않으므로 전개가 어디로 가는지 모른 채

밀고 나가야 하고, 모순이 나오지 않는 길로 오래 갈 수 있다(21주차 문제 18,

이번 주 문제 19).
:::

### 6 대우는 귀류의 특수형

두 기법의 관계를 정확히 짚어 둔다. 귀류로 $P \land \neg Q$를 가정하고 전개하다가 $\neg P$에 도달했다고 하자. 그러면 가정에 $P$가 있으므로 $P \land \neg P$가 완성되어 모순이 된다. 그런데 이 전개에서 실제로 쓴 것은 $\neg Q$에서 $\neg P$로 가는 부분뿐이다 — 곧 대우 증명의 몸통 그대로다.

:::{container} quotebox
**확인 7.** 위 관찰을 한 문장으로 정리해 보자. "대우 증명은 $\underline{\qquad}$를 미리 정해 둔 귀류법이다."
:::

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

"대우 증명은 **충돌할 상대를 $P$로** 미리 정해 둔 귀류법이다."

귀류법은 $P$ 이외의 어떤 사실과 충돌해도 되고, 이 자유가 21주차 예제 2.2를

가능하게 했다 — 그 증명에서 충돌한 상대는 가정 $P$가 아니라 기약성이었다.

거꾸로 가는 방향에는 조건이 하나 더 붙는다. 귀류 증명이 마지막에 가정 $P$와

충돌했고 **몸통의 어느 줄도 $P$를 쓰지 않았다면**, 그 증명은 대우 증명을 길게

적은 것이다 — 첫 줄과 마지막 줄만 지우면 대우 증명이 그대로 남는다. 이번 주

예제 2.1과 예제 2.2가 그런 사례다. 다만 두 예제 모두 $\neg Q$는 몸통에서

실제로 쓰이므로 §1.8의 껍데기 진단에는 걸리지 않는다 — 대우로 옮겨 적을 수

있다는 것과 귀류의 껍데기라는 것은 서로 다른 두 진단이다(§1.8의 표에서

나란히 비교한다).
:::

조건 하나를 덧붙인 이유를 실물로 확인해 둔다. 옮겨 적을 수 있는지를 정하는 것은 "충돌 상대가 $P$인가"가 아니라 "몸통이 $P$를 썼는가"다. 문제 8($p$가 소수이고 $p > 2$이면 $p$는 홀수)의 귀류 증명은 마지막에 가정의 조각 "$p$가 소수"와 충돌하지만, 몸통에서 다른 조각 "$p > 2$"를 이미 소비한다. 그 명제의 대우는 "$p$가 짝수이면 $p$가 소수가 아니거나 $p \le 2$이다"로 결론이 "또는"이 되어 §1.1 시도 3과 같은 자리에서 막힌다. 충돌 상대가 $P$였는데도 첫 줄과 마지막 줄만 지워서는 대우 증명이 되지 않는 자리다.

### 7 기법 선택 가이드

기법이 셋으로 늘었으므로 고르는 순서를 정해 둔다.

:::{admonition} 백지 암기 대상
:class: keybox

**기법 선택 가이드**

① **직접 증명을 먼저 시도한다.** 가장 읽기 쉽고 정보가 가정에서 결론으로 한 방향으로 흐른다.

② 가정이 합성식이거나 부정형이거나, **결론이 "또는"$\cdot$"그리고"이면** **대우**로 갈아탄다 (19주차 §1.5의 신호 셋).

③ 결론이 비존재$\cdot$무리수$\cdot$무한 등 "부정 자체"이거나, 대우로도 재료가 부족하면 **귀류**로 간다 (21주차 §1.6의 신호 네 가지).

④ 다 쓴 뒤 점검한다 — 귀류 가정 $\neg Q$를 모순 선언 이전에 실제로 사용했는가. 사용하지 않았다면 껍데기를 벗기고 직접이나 대우로 다시 쓴다.
:::

②의 셋째 신호가 걸리는 명제는 두 길이 만난다. 결론이 "또는"인 명제(예제 2.2, 문제 1(c), 문제 9)는 대우로 뒤집으면 가정이 "그리고"로 이어진 두 문장이 되고, 귀류로 적어도 첫 줄에서 그 두 문장을 그대로 손에 쥔다. 몸통이 한 줄로 겹치므로 어느 쪽으로 적어도 정답이며, 그 겹침을 확인 19에서 확인한다. 다만 대우로 뒤집었을 때 "또는"이 결론 쪽에 남는 명제는 ②로 풀리지 않고 ③으로 내려간다 — §1.1 시도 3이 그 자리였다.

:::{container} quotebox
**확인 8.** 다음 세 명제에 대해 가이드 ①~③ 중 어느 조가 걸리는지 골라 보자. (가) $n$이 홀수이면 $3n + 2$는 홀수이다 (나) $n^3$이 짝수이면 $n$은 짝수이다 (다) $x^2 - y^2 = 2$인 정수 $x, y$는 존재하지 않는다.
:::

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

(가) ① 직접 — 가정 "$n$ 홀수"가 $n = 2k+1$로 즉시 풀리고 결론도 긍정형이다.

(나) ② 대우 — 가정 "$n^3$ 짝수"가 합성식이라 $n$을 꺼낼 수 없다(19주차 첫째

신호). 대우의 가정 "$n$ 홀수"는 즉시 풀린다.

(다) ③ 귀류 — 결론이 "존재하지 않는다"라 만들 목표 꼴이 없다(21주차 둘째

신호). 부정하면 등식 $x^2 - y^2 = 2$가 재료로 들어온다. 예제 2.3이 이 명제다.
:::

### 8 남용 진단 — 껍데기 안의 직접 증명

가이드 ④가 가리키는 상황을 실물로 본다. 다음 답안을 읽어 보자.

:::{container} quotebox
**답안.** 명제: 정수 $n$에 대해, $n$이 홀수이면 $3n + 2$는 홀수이다.

증명: 모순을 이끌어내기 위해, $n$이 홀수인데 $3n + 2$가 짝수라고 가정하자.

$n$이 홀수이므로 $n = 2k + 1$인 정수 $k$가 존재한다. 그러면

$3n + 2 = 6k + 5 = 2(3k + 2) + 1$이고 $3k + 2$는 정수이므로 $3n + 2$는 홀수이다.

이는 $3n + 2$가 짝수라는 가정과 모순이다. 따라서 $3n + 2$는 홀수이다. $\blacksquare$
:::

논리적으로 틀린 줄은 하나도 없다. 각 줄의 근거도 정확하다. 그런데도 이 답안에는 군더더기가 있다.

:::{container} quotebox
**확인 9.** 이 답안에서 가정 "$3n + 2$가 짝수"가 실제로 사용된 줄은 어디인가. 그 줄을 빼면 남는 것은 무엇인가.
:::

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

마지막에서 두 번째 줄, 곧 충돌 선언에서만 사용됐다. 그 줄과 첫 줄을 빼면

"$n = 2k+1$이므로 $3n+2 = 2(3k+2)+1$은 홀수이다"가 남는데, 그것이 이미

원명제의 완결된 직접 증명이다. 곧 귀류의 껍데기가 아무 일도 하지 않았다.

이 답안은 틀린 것이 아니라 **더 길게 쓴 것**이다. 문제 18이 같은 진단을

다른 명제에서 다시 묻는다.
:::

판별 질문 하나로 고정해 둔다.

:::{admonition} 백지 암기 대상
:class: keybox

**자기 점검 질문**

귀류 가정 $\neg Q$가 모순 선언 **이전의** 줄에서 실제로 쓰였는가.

쓰이지 않았다면 그 증명은 귀류법이 아니었다.
:::

주의할 것이 하나 있다. 껍데기라는 진단은 "틀렸다"가 아니라 "짧게 쓸 수 있다"이다. 귀류로 쓴 답안이 감점될 근거는 없다. 다만 읽는 사람은 첫 줄에서 $\neg Q$를 보면 그것이 어딘가에서 쓰일 것이라 기대하고 읽으므로, 쓰이지 않는 가정은 읽는 사람을 헛되이 기다리게 한다.

**두 진단은 서로 다른 것이다.** §1.6의 "대우로 옮겨 적을 수 있다"와 이 절의 "귀류의 껍데기다"는 묻는 것이 다르고, 한쪽에만 걸리는 증명이 실제로 있다.

| **묻는 것** | **걸리면 내리는 진단** | **이번 주의 실물** |
|---|---|---|
| 몸통이 $P$를 쓰지 않은 채 마지막에 $P$와 충돌하는가 | 대우 증명으로 옮겨 적을 수 있다 (§1.6) | 예제 2.1, 예제 2.2, 빈칸 사다리 훈련 1 |
| $\neg Q$가 모순 선언 이전의 줄에서 쓰이지 **않았는가** | 귀류의 껍데기다. 직접 증명으로 줄일 수 있다 (§1.8) | 위 답안, 문제 18 |

예제 2.1과 예제 2.2는 첫 행에만 걸린다 — $\neg Q$가 몸통에서 실제로 쓰이므로 껍데기는 아니다(확인 19). 위 답안과 문제 18은 둘째 행에만 걸린다 — 몸통이 $P$를 쓰고 충돌 상대도 $\neg Q$이므로 첫 행에는 해당하지 않는다. 문제 8은 어느 행에도 걸리지 않는다. 두 물음을 하나로 묶어 판정하면 문제 8 같은 사례에서 틀린 결론이 나온다.

### 9 부품 준비 — 1의 약수

이번 주의 예제와 문제 여러 개가 "$a \mid 1$"이라는 결론에서 모순을 만든다. 그 마지막 한 걸음을 부품으로 떼어 놓는다.

:::{admonition} 빌려 쓰는 사실
:class: quotebox

0이 아닌 정수의 절댓값은 1 이상이다.
:::

곧 0과 1 사이에는 정수가 없다는 뜻이다. 직관은 분명하지만 엄밀한 증명에는 33주차의 최소원리가 필요하다 — 지금은 인정하고 쓴다. 33주차에서 세우는 최소원리가 이 사실까지 함께 덮는다.

:::{admonition} 보조 명제 22.A — 1의 약수는 $\pm 1$뿐이다
:class: quotebox

정수 $a$에 대해 $a \mid 1$이면 $a = 1$ 또는 $a = -1$이다.
:::

**증명.** $a \mid 1$이라 가정하자. 정의 2.1에 의해 $1 = ac$인 정수 $c$가 존재한다. $ac = 1 \neq 0$이므로 $a \neq 0$이고 $c \neq 0$이다. 양변의 절댓값(정의 17.1)을 취하면 $\lvert ac \rvert = \lvert 1 \rvert = 1$이고, $\lvert xy \rvert = \lvert x \rvert \lvert y \rvert$이므로(17주차 문제 10 — 근거 ④)

$$
\lvert a \rvert \cdot \lvert c \rvert = 1
$$

이다. 빌려 쓰는 사실에 의해 $\lvert a \rvert \ge 1$이며 $\lvert c \rvert \ge 1$이다.

여기서 $\lvert a \rvert = 1$임을 보인다. 만약 $\lvert a \rvert \neq 1$이라면 $\lvert a \rvert - 1$은 0이 아닌 정수이고 $\lvert a \rvert \ge 1$에서 양수이므로, 빌려 쓰는 사실을 그 수에 다시 적용하면 $\lvert a \rvert - 1 \ge 1$이다(양수의 절댓값은 자기 자신이다 — 정의 17.1). 곧 $\lvert a \rvert \ge 2$이다. 그러면 양변이 양수인 두 부등식 $\lvert a \rvert \ge 2$와 $\lvert c \rvert \ge 1$을 변끼리 곱해(16주차 §1.4의 (W3)을 두 번 쓰고 (W6)으로 잇는다 — 근거 ③) $\lvert a \rvert \cdot \lvert c \rvert \ge 2 \times 1 = 2 > 1$이 되어 위 등식과 어긋난다. 따라서 $\lvert a \rvert = 1$, 곧 $a = 1$ 또는 $a = -1$이다. $\blacksquare$

2주차 문제 20에서 "곱이 1인 두 정수는 $1$과 $1$ 또는 $-1$과 $-1$뿐"이라는 사실을 인정하고 썼다. 위 증명이 그 빚을 갚은 자리다.

:::{container} quotebox
**확인 10.** $a \ge 2$인 정수 $a$에 대해 $a \mid 1$이 성립할 수 있는가. 보조 명제 22.A로 답해 보자.
:::

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

성립할 수 없다. $a \mid 1$이면 $a = 1$ 또는 $a = -1$인데, 둘 다 $a \ge 2$를

만족하지 않는다. 곧 "$a \ge 2$"와 "$a \mid 1$"은 동시에 성립할 수 없는 두

문장이므로, 이 둘이 한 증명에 나란히 나오면 그 자체로 모순이다.

예제 2.1이 정확히 이 충돌을 만든다.
:::

### 10 근거 목록 갱신 — 칸은 그대로 네 개

| **근거** | **이번 주의 내용** | **이번 주에는 이렇게 쓴다** |
|---|---|---|
| ① 정의 | 정의 1.1$\cdot$1.2(짝수$\cdot$홀수), 정의 2.1(나누어떨어짐), 정의 15.1(유리수$\cdot$무리수), 정의 15.2(소수), 정의 17.1(절댓값), 정의 21.2(기약분수), 평균의 정의($\mu = \frac{x_1 + \cdots + x_n}{n}$ — 문제 13), **정의 22.1(조건문의 귀류 증명)** | 첫 줄에서 $P \land \neg Q$를 만들 때 각 조각을 정의로 푼다 |
| ② 닫힘성 | 정수의 합$\cdot$차$\cdot$곱은 정수, 유리수의 합$\cdot$차$\cdot$곱$\cdot$몫은 유리수(15주차) | "$3k + 2$는 정수이므로"를 별도 설명 없이 쓴다 |
| ③ 등식$\cdot$부등식의 성질 | 대입 / 전개 / 인수분해 / 양변 연산 / 부등식을 변끼리 더하기(16주차 문제 2(c)) / 양변이 양수인 부등식을 변끼리 곱하기(16주차 §1.4의 (W3)과 (W6)) | $x < 1$과 $y < 1$을 더해 $x + y < 2$를 얻는다 |
| ④ 이미 증명한 명제 | 9주차 문제 7($\neg(P \Rightarrow Q) \equiv P \land \neg Q$), 11주차 부정 규칙 총목록, 1주차 문제 8(홀$\times$홀=홀)$\cdot$문제 11($n$ 홀 $\Rightarrow n^2$ 홀)$\cdot$예제 2.2(짝수$\times$정수=짝수)$\cdot$예제 2.3(홀+홀=짝)$\cdot$빈칸 사다리 훈련 1(홀+짝=홀), 2주차 문제 17, 15주차 유리수 닫힘성 다섯 개, 17주차 경우 나누기 4단계 틀$\cdot$짝/홀 분할(정수는 짝수이거나 홀수)$\cdot$문제 10($\lvert xy \rvert = \lvert x \rvert \lvert y \rvert$), 19주차 예제 2.1, 21주차의 결과 전부, **보조 명제 22.A** | "2주차 문제 17에 의해 $a \mid c$이다" |

**귀류법은 이번 주에도 칸을 늘리지 않는다.** 바뀐 것은 증명의 첫 줄에 무엇을 놓는가뿐이고, 몸통의 각 줄은 여전히 ①~④로만 정당화된다.

이번 주에 목록에서 **빠지는** 항목이 둘 있다. "어떤 정수도 짝수이면서 동시에 홀수일 수는 없다"는 5주차 빈칸 사다리 훈련 1에서 $E \cap O = \emptyset$로 처음 적혔고, 17주차의 짝/홀 분할부터 "당연히"로 써 왔으며(문제 5의 진술이 가리키는 시점이 이 17주차다), 21주차 빈칸 사다리 훈련 3이 그것을 명시적으로 빌렸고, 이번 주 문제 5에서 증명된다. "1의 약수는 $\pm 1$뿐"은 2주차 문제 20에서 인정하고 썼고, 방금 보조 명제 22.A로 증명됐다. 인정하고 쓴 사실은 잊히는 것이 아니라 회수 일정에 올라 있는 항목이다.

:::{container} quotebox
**확인 11.** 어떤 증명에 다음 세 줄이 나왔다. 각각 허용되는가. 허용된다면 몇 번 근거인가.

(가) "$x < 1$과 $y < 1$을 변끼리 더하면 $x + y < 2$이다"

(나) "$a \mid (b+c)$이고 $a \mid b$이므로 $a \mid c$이다"

(다) "$2a = 2b + 1$인데 좌변은 짝수이고 우변은 홀수이므로 당연히 모순이다"
:::

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

(가) 허용 — 근거 ③(16주차 문제 2(c)에서 확인한 부등식의 성질).

(나) 허용 — 근거 ④(2주차 문제 17).

(다) 문제 5를 풀기 전에는 불허, 푼 뒤에는 허용. "짝수이면서 홀수일 수

없다"가 아직 증명되지 않은 동안에는 "당연히"가 근거가 되지 않는다. 문제 5가

그 줄을 근거 ④로 승격시키는 자리다. 그전까지 이 사실을 쓰는 자리에는

"문제 5에서 증명할 사실 — 지금은 인정하고 쓴다"라는 표시를 달아 둔다

(예제 2.3, 빈칸 사다리 훈련 1$\cdot$2가 그 표시를 달고 쓴다). 내용이 아니라

**자격**이 근거를 정한다.
:::

정의 22.1, 서식(§1.4), 기법 선택 가이드(§1.7), 자기 점검 질문(§1.8)이 [백지 암기 대상]이다. 문장을 통째로만 외우면 일부를 잊었을 때 복구할 길이 없으므로 §1.3의 조각별 이유와 함께 외운다.