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

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

이 주의 길잡이

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

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

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

이번 주 목표#

  1. 조건문 \(P \Rightarrow Q\)의 귀류 증명 서식(\(P \land \neg Q\)를 가정하는 형식)을 백지에 쓰고, 각 조각이 하는 일을 설명할 수 있다.

  2. 대우 증명이 귀류법의 특수형임을 도착점의 관점에서 설명할 수 있다.

  3. 귀류와 경우 나누기, 귀류와 기약분수를 조합한 증명을 세 개 이상 쓸 수 있다.

  4. 기법 선택 가이드 네 조를 쓰고, “귀류 껍데기 안의 직접 증명”을 스스로 판별할 수 있다.

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

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

  1. \(\sqrt{2}\)가 무리수임을 보이는 증명에서 “기약분수로 잡는다”는 가정이 하는 역할을 한 문장으로 쓰시오.

  2. 빈칸을 채우시오: \(\neg(P \Rightarrow Q) \equiv \underline{\quad}\) (9주차 문제 7 — 이번 주의 주인공이다.)

  3. 소수가 무한히 많음을 보이는 증명에서 \(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주차의 틀을 조건문에 그대로 얹으면 어디서 막히는가#

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

명제. 정수 \(a, b, c\)에 대해, \(a \mid b\)이고 \(a \nmid c\)이면 \(a \nmid (b + c)\)이다.

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

시도 1 — 직접 증명

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

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

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

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

시도 2 — 21주차의 귀류법을 그대로

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

\(a \nmid c\)가 아니라고 가정하자. 그러면 … “

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

시도 3 — 대우로 갈아타기

“대우로 증명한다. \(\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\)가 결론 쪽으로 넘어가 버려 손에 없다.

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

답

시도 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}\)

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

답

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

조건문 \(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\)이 실제로 그 조건을 만족하기 때문이다.

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

답

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

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

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

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

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

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

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

답

증명된 것은 \(P\)다 — “가정 부분이 참이다”라는 주장이다. 원명제는 “\(P\)가 참일

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

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

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

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

4 서식#

백지 암기 대상

조건문 귀류 증명의 서식

명제. \(P\)이면 \(Q\)이다.

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

\(\quad\vdots\)

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

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

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

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

  • 가정 두 개를 둘 다 적는다. \(\neg Q\)만 적고 \(P\)를 빠뜨리는 답안이 많다.

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

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

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

확인 5. 어떤 답안이 “\(x + y \ge 2\)이고 \(x < 1\), \(y < 1\)이라 하자”로 시작한다. 서식상 무엇이 빠졌고, 그 결과 이 줄은 어떻게 읽히는가.

답

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

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

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

지위를 정하는 문장이다.

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

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

기법

손에 쥐는 가정

도착지

적용 대상

직접 (1주차)

\(P\) — 한 개

\(Q\) 하나로 고정

조건문 (존재 명제는 15주차 §1.7의 증인 제작 서식)

대우 (19주차)

\(\neg Q\) — 한 개

\(\neg P\) 하나로 고정

조건문

귀류 (21~22주차)

\(P\) 그리고 \(\neg Q\) — 두 개

아무 모순 (고정되지 않음)

아무 명제

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

답

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

부품을 쓸 수 있다(§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\)로 가는 부분뿐이다 — 곧 대우 증명의 몸통 그대로다.

확인 7. 위 관찰을 한 문장으로 정리해 보자. “대우 증명은 \(\underline{\qquad}\)를 미리 정해 둔 귀류법이다.”

답

“대우 증명은 충돌할 상대를 \(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 기법 선택 가이드#

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

백지 암기 대상

기법 선택 가이드

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

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

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

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

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

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

답

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

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

신호). 대우의 가정 “\(n\) 홀수”는 즉시 풀린다.

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

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

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

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

답안. 명제: 정수 \(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\)

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

확인 9. 이 답안에서 가정 “\(3n + 2\)가 짝수”가 실제로 사용된 줄은 어디인가. 그 줄을 빼면 남는 것은 무엇인가.

답

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

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

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

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

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

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

백지 암기 대상

자기 점검 질문

귀류 가정 \(\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\)”이라는 결론에서 모순을 만든다. 그 마지막 한 걸음을 부품으로 떼어 놓는다.

빌려 쓰는 사실

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

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

보조 명제 22.A — 1의 약수는 \(\pm 1\)뿐이다

정수 \(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\)뿐”이라는 사실을 인정하고 썼다. 위 증명이 그 빚을 갚은 자리다.

확인 10. \(a \ge 2\)인 정수 \(a\)에 대해 \(a \mid 1\)이 성립할 수 있는가. 보조 명제 22.A로 답해 보자.

답

성립할 수 없다. \(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로 증명됐다. 인정하고 쓴 사실은 잊히는 것이 아니라 회수 일정에 올라 있는 항목이다.

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

(가) “\(x < 1\)과 \(y < 1\)을 변끼리 더하면 \(x + y < 2\)이다”

(나) “\(a \mid (b+c)\)이고 \(a \mid b\)이므로 \(a \mid c\)이다”

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

답

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

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

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

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

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

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

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

자격이 근거를 정한다.

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