21주차 — 귀류법 1 (Proof by Contradiction)

21주차 — 귀류법 1 (Proof by Contradiction)#

이 주의 길잡이

핵심 문장: 결론을 부정해 가정 자리에 놓으면, 만들 목표 꼴이 없던 자리에 전개할 등식이 생긴다.

이 주의 위치: 50주 과정의 21주차. 18주차에서 진단만 하고 넘긴 “부정형 결론의 막힘”을 뚫는 세 번째 증명 기법을 세운다.

원서 대응: BoP(Book of Proof) 6.1 (Proving Statements with Contradiction). 원서 없이 읽을 수 있다.

이번 주 목표#

  1. 귀류법의 3단계 구조와 서식을 백지에 쓰고, 각 단계가 하는 일을 설명할 수 있다.

  2. “\(\sqrt{2}\)는 무리수이다”와 “소수는 무한히 많다”를 백지에서 증명할 수 있다.

  3. “가장 큰/가장 작은 ~는 없다”, “정수 해가 없다” 유형을 귀류법으로 처리할 수 있다.

  4. 모순이 나오지 않는 상황(\(\sqrt{4}\))에서 무엇을 읽어야 하는지 판단할 수 있다.

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

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

  1. \(a \equiv b \pmod n\)의 정의를 쓰시오.

  2. “\(n^2\)이 짝수이면 \(n\)은 짝수이다”의 증명 구조를 말로 재현하시오 (19주차 예제 2.1 — 이번 주의 핵심 부품이다).

  3. 11주차 문제 20에서 써 둔 “\(\sqrt{2}\) 귀류법의 첫 두 줄”을 다시 쓰시오.

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

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

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

  • 유형 1 — 부정을 말로만 다시 적기. “\(\sqrt{2}\)는 무리수가 아니다”라고 적고

멈춘다. 부정 자체는 옳다. 문제는 “무리수가 아니다”가 아직 전개할 수 없는 말이라는 것이다 — 정의 15.1로 “\(\sqrt{2}\)는 유리수이다”로 바꾸고, 다시 3주차 \(\mathbb{Q}\)의 정의로 “\(\sqrt{2} = \frac{a}{b}\)인 정수 \(a, b\)(\(b \neq 0\))가 존재한다”까지 풀어야 등식이 손에 들어온다. 그 두 단계가 §1.1의 초점이다.

  • 유형 2 — 등식까지 풀었지만 조건은 없이. “\(\sqrt{2} = \frac{a}{b}\)인 정수

\(a, b\)가 존재한다”까지 정확히 적었다. 11주차 문제 20이 요구한 것은 여기까지이므로 그 자체로 완결이다. 이번 주의 증명은 이 줄에 조각 하나를 더 붙인다 — “기약분수로 잡을 수 있다”. 그 조각이 왜 필요한지가 §1.8과 예제 2.2의 초점이다.

  • 유형 3 — 백지. 첫 줄을 무엇으로 시작할지 몰라 적지 못했다. 귀류법의 첫

두 줄은 창작이 아니라 두 규칙의 기계적 적용이다 — 11주차 §1.3(부정 제작)과 정의 15.1(유리수의 정의). 이번 주는 그 기계적 절차를 서식으로 고정한다.

개념 — 귀류법의 구조#

1 부정형 결론에서 직접 증명이 어디서 막히는가#

이번 주의 대표 명제는 “\(\sqrt{2}\)는 무리수이다”이다. 18주차까지 세운 도구 — 직접 증명과 대우 증명 — 만으로 밀어붙여 보자.

시도 1 — 직접 증명으로 밀어붙이기

명제: \(\sqrt{2}\)는 무리수이다.

“\(\sqrt{2}\)를 생각하자. 무리수의 정의(정의 15.1)에 의해 보여야 할 것은

\(\sqrt{2}\)가 유리수가 아니라는 것, 곧 \(\sqrt{2} = \frac{a}{b}\)인 정수

\(a, b\)(\(b \neq 0\))가 존재하지 않는다는 것이다. 따라서 … “

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

시도 2 — 대우로 갈아타기

대우 증명(19주차)은 “\(P \Rightarrow Q\)”의 \(P\)와 \(Q\)를 뒤집는 기법이다.

그런데 “\(\sqrt{2}\)는 무리수이다”에는 뒤집을 \(P\)도 \(Q\)도 없다 —

조건문이 아니기 때문이다.

확인 1. 두 시도가 막힌 자리를 각각 한 문장으로 적어 보자. 두 막힘은 같은 것인가 다른 것인가.

답

직접 증명은 결론이 부정형이라 만들 목표 꼴이 없어서 막혔고, 대우 증명은

뒤집을 조건문 구조 자체가 없어서 막혔다. 두 막힘은 다르다. 18주차 §1의

진단 표가 이 중 앞의 것을 “부정형 결론의 막힘”이라 부르고 21주차의 소재로

넘긴 그 자리다.

이 주 전체의 기준

부정형 결론은 만들 목표 꼴이 없다. 그렇다면 결론을 부정해 가정 쪽으로

옮긴다. 부정형의 부정은 긍정형이고, 긍정형은 정의로 풀려 등식이 된다.

2 부정을 가정으로 옮기면 무엇이 손에 들어오는가#

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

증명하려는 명제 \(P\)

부정 \(\neg P\)

\(\neg P\)를 가정하면 손에 들어오는 것

\(\sqrt{2}\)는 무리수이다

\(\sqrt{2}\)는 유리수이다

\(\sqrt{2} = \frac{a}{b}\)인 정수 \(a, b\) (\(b \neq 0\))

가장 큰 정수는 존재하지 않는다

\(\underline{\quad(1)\quad}\)

가장 큰 정수 — 이름을 \(N\)이라 붙일 수 있다

소수는 무한히 많다

소수는 유한 개뿐이다

\(\underline{\quad(2)\quad}\)

\(x^2 = 4y+3\)인 정수 \(x, y\)는 존재하지 않는다

\(\underline{\quad(3)\quad}\)

\(\underline{\quad(4)\quad}\)

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

답

(1) 가장 큰 정수가 존재한다 (2) 소수 전체의 유한한 목록 \(p_1, p_2, \dots, p_n\)

(3) \(x^2 = 4y+3\)인 정수 \(x, y\)가 존재한다 (4) 그 등식을 만족하는 정수 \(x, y\)와 등식 \(x^2 = 4y+3\).

공통으로 일어난 일: 부정하기 전에는 “없다\(\cdot\)아니다”여서 붙잡을 것이 없었는데,

부정한 뒤에는 이름을 붙일 수 있는 대상과 전개할 수 있는 등식이 되었다.

셋째 열에 해당하는 것이 곧 증명의 재료다.

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

정의 21.1 — 귀류법 (proof by contradiction) [백지 암기 대상]#

명제 \(P\)를 귀류법으로 증명한다는 것은 다음 세 단계를 밟는다는 뜻이다.

① \(\neg P\)를 가정한다.

② 논리를 전개해, 어떤 명제 \(C\)에 대해 \(C \land \neg C\)를 얻는다.

③ \(C \land \neg C\)는 항상 거짓이므로 그것을 유도한 가정 \(\neg P\)가 거짓이다. 따라서 \(P\)가 참이다.

\(C \land \neg C\)처럼 어떤 상황에서도 거짓인 명제를 모순(contradiction)이라 한다 — 7주차 §3에서 두 행짜리 진리표로 확인한 그 명제다. \(C \land \neg C\)는 “씨 그리고 씨가 아니다”로 읽는다. 읽는 법까지가 정의다. 라틴어 이름 reductio ad absurdum도 같은 절차를 가리킨다.

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

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

조각

하는 일

증명에서의 역할

“\(\neg P\)를 가정한다”

출발점 제공

부정형 결론이 긍정형 가정으로 바뀌어 정의로 풀린다 — §1.1의 막힘이 풀리는 자리

“논리를 전개해”

몸통

직접 증명과 한 줄도 다르지 않다. 각 줄의 근거는 여전히 ①~④뿐이다

“\(C \land \neg C\)를 얻는다”

도착점 지정

도착할 곳이 아무 모순이나이므로 방향이 하나로 정해지지 않는다

“따라서 \(P\)가 참이다”

원명제 회수

①~③을 원래 주장으로 되돌린다. 근거는 §1.4의 진리표

조각 삭제 실험. 셋째 조각의 “\(C \land \neg C\)”를 “어딘가 어색한 결과”로 완화해 보자. 예제 2.2의 전개를 따라가면 “\(a\)와 \(b\)가 둘 다 짝수”라는 문장이 나오는데, 여기서 멈추고 “이상하다”고 적으면 증명이 끝나는가. 끝나지 않는다 — \(\frac{4}{2}\)처럼 분자와 분모가 둘 다 짝수인 표현은 유리수의 정당한 표현이므로 그 자체로는 거짓이 아니다. 무너지는 것은 도착점의 자격이다. 모순은 “이상함”이 아니라 한 명제와 그 부정이 동시에 성립함이다.

확인 3. 위 실험에서 “\(a\)와 \(b\)가 둘 다 짝수”가 모순이 되려면, 증명이 미리 무엇을 선언해 두어야 하는가.

답

첫머리에 “\(\frac{a}{b}\)를 기약분수로 잡는다”를 선언해 두어야 한다. 그러면

\(C\) = “2는 \(a\)와 \(b\)의 공통 약수가 아니다”(공통 약수가 \(\pm 1\)뿐이고 \(2 \neq \pm 1\)이므로

따라온다), \(\neg C\) = “2는 \(a\)와 \(b\)의 공통 약수이다”(전개에서 얻은 것)가 되어

\(C \land \neg C\)가 문자 그대로 완성된다.

모순은 저절로 생기지 않는다 — 충돌할 상대를 미리 설치해 두는 것이 귀류법

설계의 절반이다. 문제 3(c)가 이 조각의 하중을 다시 확인한다.

조각 변형 실험. 첫째 조각의 \(\neg P\)를 부정확하게 만들어 보자. “\(\sqrt{2}\)는 무리수이다”의 부정을 “\(\sqrt{2}\)는 정수이다”로 적고 시작하면 어떻게 되는가 (유리수를 정수로 좁혀 부정한 전형적 오류다).

확인 4. 부정을 \(\neg P\)가 아닌 다른 명제 \(R\)로 잘못 만들면, 모순을 이끌어낸 뒤 실제로 증명되는 것은 무엇인가.

답

\(\neg R\)이다 — \(P\)가 아니다. 위 예에서 증명되는 것은 “\(\sqrt{2}\)는 정수가

아니다”뿐이고, 그것은 무리수라는 결론과 다른 주장이다(\(\frac{3}{2}\)은 정수가

아니지만 유리수다). 11주차의 부정 제작이 귀류법의 첫 줄에서 소비되는

이유가 이것이다. 첫 줄이 틀리면 뒤의 모든 줄이 옳아도 다른 명제를 증명한

답안이 된다.

4 왜 이것이 증명이 되는가#

②가 실제로 증명한 것은 조건문 “\(\neg P \Rightarrow (C \land \neg C)\)”이다. \(C \land \neg C\)는 어떤 상황에서도 거짓이므로 이 조건문의 결론 자리는 항상 F다. 조건문은 가정이 T이고 결론이 F인 경우에만 F이므로(8주차 정의 8.1), 결론이 F인 조건문이 참이려면 가정이 F여야 한다.

\(P\)

\(\neg P\)

\(C \land \neg C\)

\(\neg P \Rightarrow (C \land \neg C)\)

T

F

F

T

F

T

F

F

확인 5. 위 표의 마지막 열과 첫 열을 비교해 보자. 두 열이 같다는 것은 무엇을 뜻하는가.

답

“\(\neg P\)에서 모순이 유도된다”는 명제와 “\(P\)이다”는 명제가 모든 행에서

진리값이 같다 — 9주차의 뜻으로 동치다. 그러므로 앞의 것을 보이면 뒤의

것을 보인 것이다. 귀류법이 새로운 논리를 도입하는 것이 아니라 이미 세운

동치 하나를 쓰는 것임이 이 두 행에 전부 들어 있다.

문제 2가 이 표를 직접 작성하는 자리다.

5 서식#

백지 암기 대상

귀류법의 서식

명제. \(P\)이다.

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

\(\quad\vdots\)

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

서식 포인트 두 가지.

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

\(\neg P\)가 저자가 참이라고 믿는 문장으로 읽힌다 — 증명하려는 것과 정반대다.

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

충돌했는지 적지 않으면 도착점이 확인되지 않는다. 지목할 두 문장이 \(C\)와 \(\neg C\)다.

확인 6. 어떤 답안이 “\(\sqrt{2} = \frac{a}{b}\)라 하자”로 시작한다. 서식상 무엇이 빠졌고, 그 결과 이 줄은 어떻게 읽히는가.

답

“모순을 이끌어내기 위해 \(\sqrt{2}\)가 유리수라고 가정하자”라는 선언이 빠졌다.

그 문장이 없으면 “\(\sqrt{2} = \frac{a}{b}\)”는 저자가 참으로 주장하는 등식으로

읽힌다. 기법 선언은 장식이 아니라 뒤에 오는 모든 줄의 지위를 정하는 문장이다.

6 언제 귀류법을 고르는가 — 신호 [백지 암기 대상]#

신호

이유

결론이 “~는 무리수” 등 부정형 개념

부정을 가정하면 “유리수 \(= \frac{a}{b}\)”라는 전개 가능한 등식이 생긴다

“존재하지 않는다 / ~일 수 없다”

부정(“존재한다”)을 가정하면 그 대상이 손에 들어온다 — 그 대상을 재료로 모순을 만든다

“가장 큰/작은 ~는 없다”

부정하면 최대\(\cdot\)최소인 대상 \(M\)이 생긴다 — 그보다 크거나 작은 것을 만들어 최대\(\cdot\)최소성과 충돌시킨다

“무한히 많다”

부정(“유한 개뿐”)하면 전체 목록을 손에 쥔다 — 목록 밖의 대상을 만들어 목록의 완전성과 충돌시킨다

공통 원리: 부정형\(\cdot\)비존재형 결론은 목표 꼴이 없어 직접 증명이 막히지만 (18주차 문제 20), 부정을 가정으로 돌리면 그 자리가 재료가 된다.

확인 7. 다음 셋 중 귀류법의 신호가 있는 것은 어느 것인가. (가) 짝수와 짝수의 합은 짝수이다 (나) \(\sqrt{3}\)은 무리수이다 (다) 가장 작은 양의 유리수는 존재하지 않는다.

답

(나)와 (다). (가)는 결론이 긍정형이고 목표 꼴 \(2 \times (\text{정수})\)이 그대로

만들어지므로 직접 증명이 최단이다(1주차 예제 2.1).

신호가 없는 명제에 귀류법을 쓰는 것이 틀린 증명이 되지는 않지만, 첫 줄과

마지막 줄만 늘고 몸통은 직접 증명과 같아진다. 기법 선택의 우선순위는

22주차에서 정한다.

7 대우 증명과 무엇이 다른가 — 도착점#

두 기법은 모두 “결론의 부정을 재료로 삼는다”는 점이 같다. 다른 것은 도착점이다.

대우 증명 (19주차)

귀류법 (이번 주)

적용 대상

조건문 \(P \Rightarrow Q\)만

아무 명제나

가정하는 것

\(\neg Q\)

\(\neg P\) (증명하려는 명제 전체의 부정)

도착점

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

아무 모순이나

방향

시작 전에 정해진다

시작 전에 정해지지 않는다

확인 8. 도착점이 정해져 있지 않다는 성질이 장점인 이유와 단점인 이유를 각각 한 문장으로 적어 보자.

답

장점 — 어느 방향의 충돌이든 이용할 수 있으므로 적용 범위가 가장 넓다

(예제 2.1은 부등식 충돌, 예제 2.2는 약분 가능성 충돌, 예제 2.3은 나누어떨어짐

충돌로 서로 다르다).

단점 — 목표가 없으므로 전개가 어디로 가는지 모른 채 밀고 나가야 하고,

모순이 나오지 않는 길로 오래 갈 수 있다. 문제 18과 문제 20이 이 단점을

정면으로 다룬다.

8 부품 준비 — 기약분수와 소수 약수#

이번 주의 두 대표 증명은 이번 주에 증명하지 않는 사실 두 개를 쓴다. 어느 것이 빌려 쓰는 것인지 미리 못 박아 둔다.

정의 21.2 — 기약분수 (reduced fraction) [백지 암기 대상]#

정수 \(a, b\)(\(b \neq 0\))에 대해, 분수 \(\dfrac{a}{b}\)가 기약분수라는 것은 \(a\)와 \(b\)의 공통 약수가 \(\pm 1\)뿐이라는 뜻이다.

빌려 쓰는 사실 1

모든 유리수는 기약분수로 나타낼 수 있다.

직관은 이렇다. 공약수가 남아 있으면 약분하면 되고, 약분할 때마다 분모의 절댓값이 줄어드므로 언젠가 끝난다. “언젠가 끝난다”를 엄밀하게 말하려면 33주차의 최소원리가 필요하다 — 지금은 사실로 인정하고 쓴다(33주차에서 증명한다).

빌려 쓰는 사실 2

2 이상의 모든 정수는 소수인 약수를 가진다.

이것도 33주차의 강한 귀납법에서 증명한다 — 지금은 인정하고 쓴다.

확인 9. \(\frac{12}{18}\)은 기약분수인가. 정의 21.2로 판정하고, 같은 유리수의 기약분수 표현을 하나 제시해 보자.

답

기약분수가 아니다. \(12 = 6 \times 2\), \(18 = 6 \times 3\)이므로 6이 공통 약수이고,

\(\pm 1\) 말고도 \(\pm 2, \pm 3, \pm 6\)이 공통 약수다. 분자와 분모를 6으로 나누면

\(\frac{12}{18} = \frac{2}{3}\)이고, 2와 3의 공통 약수는 \(\pm 1\)뿐이므로 \(\frac{2}{3}\)이

기약분수 표현이다.

같은 유리수에 표현이 여러 개 있고 그중 기약인 것을 골라 쓸 수 있다는 것이

빌려 쓰는 사실 1의 내용이다.

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

근거

이번 주의 내용

이번 주에는 이렇게 쓴다

① 정의

정의 15.1(유리수\(\cdot\)무리수), 정의 20.1(합동), 정의 21.2(기약분수)

“유리수” \(\leftrightarrow\) “\(\frac{a}{b}\) 꼴” 사이를 번역한다

② 닫힘성

정수의 합\(\cdot\)차\(\cdot\)곱은 정수

“\(N + 1\)은 정수이므로”를 별도 설명 없이 쓴다

③ 등식\(\cdot\)부등식의 성질

양변 제곱 / 대입 / 양변을 같은 수로 더하기\(\cdot\)나누기, 부등호의 부정(\(\le\)의 부정은 \(>\), 11주차 §1.3)

\(\sqrt{2} = \frac{a}{b}\)의 양변을 제곱한다

④ 이미 증명한 명제

19주차 예제 2.1(\(2 \mid n^2 \Rightarrow 2 \mid n\))\(\cdot\)예제 2.2(\(3 \mid n^2 \Rightarrow 3 \mid n\))\(\cdot\)문제 15(\(5 \mid n^2 \Rightarrow 5 \mid n\))\(\cdot\)문제 8(\(n^3\) 짝수 \(\Rightarrow n\) 짝수), 20주차 문제 13(\(2 \mid x\)이고 \(3 \mid x\)이면 \(6 \mid x\)), 15주차 유리수 닫힘성 다섯 개, 2주차 문제 17, 17주차 문제 9, 1주차 문제 16

“19주차 예제 2.1에 의해 \(a\)는 짝수이다”

여기에 빌려 쓰는 사실 두 개(기약분수 표현, 소수 약수의 존재)를 목록 옆에 따로 적어 둔다 — 지금은 인정하고 쓰되 33주차에서 증명해 회수할 항목이라는 표시다. 17주차부터 같은 자격으로 써 온 나눗셈 정리(몫과 나머지의 존재와 유일성)도 이 옆자리에 둔다 — 문제 19가 그 나머지의 유일성을 근거로 쓴다.

귀류법은 목록에 칸을 늘리지 않는다. 귀류법이 바꾸는 것은 증명의 뼈대 (어디서 출발해 어디로 가는가)이지 각 줄의 근거가 아니다. \(\neg P\)를 가정한 뒤의 몸통은 직접 증명과 한 줄도 다르지 않다.

확인 10. “\(\sqrt{2} = \frac{a}{b}\)의 양변을 제곱해 \(2 = \frac{a^2}{b^2}\)을 얻는다”는 줄의 근거는 몇 번인가.

답

근거 ③ 등식의 성질(양변에 같은 연산). 이어서 \(2b^2 = a^2\)으로 정리하는 것도

같은 ③이다. 귀류법을 쓰는 중이어도 각 줄의 근거는 평소와 같다 — 달라진 것은

첫 줄에 무엇을 놓았는가뿐이다.

정의 21.1과 21.2, 서식(§1.5), 신호 표(§1.6)가 [백지 암기 대상]이다. 문장을 통째로만 외우면 일부를 잊었을 때 복구할 길이 없으므로, §1.3의 조각별 이유와 함께 외운다. 조각을 잊어도 이유에서 재구성할 수 있다.