21주차 · 강의 — 예제 · 연습 · 해설

21주차 · 강의 — 예제 · 연습 · 해설#

예제 — 귀류법 증명을 함께 만들기#

완성된 증명을 먼저 보이지 않는다. 예제 2.1은 설계부터 한 줄씩 함께 만들고, 예제 2.2는 설계만 함께 하고, 예제 2.3은 설계부터 스스로 한다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다.

예제 2.1 — 가장 큰 정수는 존재하지 않는다#

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

설계 — 쓰기 전에 정하는 세 가지. 직접 증명에서는 출발점과 도착점 두 가지를 정했다(1주차 예제 2.1의 번역표). 귀류법에서는 세 가지다 — 무엇을 부정할 것인가, 그 부정이 주는 출발점은 무엇인가, 도착점은 어디인가.

말

번역

원래 목표 \(P\)

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

만들 목표 꼴이 없다 — 직접 증명이 막힌다

가정할 것 \(\neg P\)

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

그 대상에 이름을 붙여 \(N\)이라 놓는다

출발점

\(N\)이 가장 크다는 것

모든 정수 \(n\)에 대해 \(n \le N\)

도착점

아무 모순이나

어떤 \(C\)에 대해 \(C \land \neg C\)

확인 11. 표의 빈칸 (1)을 채워 보자. “존재하지 않는다”의 부정은 11주차 총목록의 어느 줄에서 나오는가.

답

(1) “가장 큰 정수가 존재한다.”

11주차 §1.3 총목록의 \(\exists\) 줄을 거꾸로 읽은 것이다 — 원문이

“존재하지 않는다”(\(\neg \exists\))이므로 그것을 다시 부정하면 이중부정이 풀려

“존재한다”가 된다.

1단계 — 부정을 선언하고 대상에 이름을 붙인다. 부정을 가정하는 순간 “가장 큰 정수”라는 대상이 생긴다. 이름이 없으면 그 대상으로 계산할 수 없다.

확인 12. 첫 문장을 완성해 보자: “모순을 이끌어내기 위해, \(\underline{\qquad}\)고 가정하고 그것을 \(N\)이라 하자.”

답

“가장 큰 정수가 존재한다”고 가정하고 그것을 \(N\)이라 하자.

존재 가정에서 대상을 받아 문자로 놓는 이 동작은, 정의에서 “정수 \(k\)가

존재한다”를 풀어 \(k\)를 받아 오던 것(1주차 §1.3의 ‘존재한다’ 표)과 같은 동작이다.

2단계 — 가정이 준 것을 문장으로 적는다. “\(N\)이 가장 큰 정수”라는 말이 무슨 뜻인지 풀어 둔다. 말로만 두면 계산이 시작되지 않는다.

확인 13. “\(N\)은 가장 큰 정수이다”를 부등식으로 풀어 보자: “모든 정수 \(n\)에 대해 \(\underline{\qquad}\)이다.”

답

\(n \le N\). 이 부등식이 이 증명에서 충돌시킬 상대다. 최대\(\cdot\)최소를 가정하는

유형에서는 이 줄을 반드시 명시적으로 적는다 — 충돌할 상대를 미리 설치하는

것이 §1.3 확인 3에서 확인한 설계다.

3단계 — 모순 후보를 만든다. 도착점은 아무 모순이나이지만, 지금 손에 있는 문장이 “모든 정수 \(n\)에 대해 \(n \le N\)”이므로 그것을 깨는 정수 하나를 만들면 된다.

확인 14. \(N\)보다 큰 정수를 하나 만들어 보자. 그것이 정수임의 근거는 몇 번인가.

답

\(N + 1\). \(N\)과 1이 정수이므로 합 \(N + 1\)도 정수다 — 근거 ② 닫힘성.

그리고 \(N + 1 > N\)이다.

만든 대상이 정수라는 확인이 빠지면 2단계의 문장(“모든 정수 \(n\)에 대해”)과

맞물리지 않아 충돌이 성립하지 않는다. 만드는 대상이 가정이 말하는 범위에

속하는지 확인하는 줄은 이 유형에서 늘 필요하다(문제 4, 문제 9에서 반복된다).

4단계 — 충돌한 두 문장을 지목한다.

확인 15. 이 증명에서 \(C\)와 \(\neg C\)에 해당하는 문장을 각각 지목해 보자.

답

\(C\) = “\(N + 1 \le N\)” (2단계의 문장을 \(n = N + 1\)에 적용한 것),

\(\neg C\) = “\(N + 1 > N\)” (3단계에서 만든 것).

두 문장이 동시에 성립하므로 \(C \land \neg C\)가 완성됐다. 답안에 적을 때는

“이는 \(N\)이 가장 크다는 가정과 모순이다”로 줄여도 되지만, 줄이더라도 무엇과

무엇이 충돌했는지는 남겨 둔다.

5단계 — 원명제를 회수한다.

확인 16. 마지막 문장을 완성해 보자: “따라서 가정이 거짓이므로, \(\underline{\qquad}\). \(\blacksquare\)”

답

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

이 한 줄의 근거는 §1.4의 진리표다 — \(\neg P\)에서 모순이 나왔으므로 \(P\)가 참이다.

완성본. 방금 만든 다섯 문장을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 “왜?”에 스스로 답해 본다.

증명의 한 줄

왜 이 줄을 쓰는가?

모순을 이끌어내기 위해, 가장 큰 정수가 존재한다고 가정하고 그것을 \(N\)이라 하자.

기법 선언 + 부정 제작 + 이름 붙이기. 이름이 없으면 다음 줄에서 계산할 대상이 없다.

그러면 모든 정수 \(n\)에 대해 \(n \le N\)이다.

가정이 준 것을 부등식으로 풀어 둔다. 이 줄이 뒤에서 충돌할 상대다.

\(N\)과 1은 정수이므로 \(N + 1\)도 정수이고(근거 ②), \(N + 1 > N\)이다.

도착점을 향해 모순 후보를 만든다. 정수임의 확인이 빠지면 앞 줄과 맞물리지 않는다.

둘째 줄을 \(n = N + 1\)에 적용하면 \(N + 1 \le N\)인데, 이는 \(N + 1 > N\)과 동시에 성립할 수 없다. 모순이다.

충돌한 두 문장을 지목한다 — \(C \land \neg C\)의 완성.

따라서 가정이 거짓이므로, 가장 큰 정수는 존재하지 않는다. \(\blacksquare\)

§1.4의 진리표로 원명제를 회수한다.

이 다섯 줄이 특정한 \(N\)에 의존하지 않는 이유. 완성본의 \(N\)에 구체적인 값을 넣어 읽어 보자.

확인 17. \(N = 100\)일 때 셋째 줄과 넷째 줄은 각각 어떤 문장이 되는가. \(N = -3\)이면 어떤가.

답

\(N = 100\): “101은 정수이고 \(101 > 100\)이다”, “\(101 \le 100\)인데 \(101 > 100\)이다”.

\(N = -3\): “\(-2\)는 정수이고 \(-2 > -3\)이다”, “\(-2 \le -3\)인데 \(-2 > -3\)이다”.

어느 값을 넣어도 모든 줄이 그대로 성립한다 — 증명의 어느 줄도 \(N\)이 특정

정수라는 사실을 쓰지 않았고, 쓴 것은 “정수”라는 자격뿐이기 때문이다.

다만 \(N\)은 결론적으로 존재하지 않는 대상이다. 존재하지 않는 것에 이름을

붙여도 되는 이유는, 이 증명이 하는 일이 정확히 “그런 이름을 붙일 수 있다고

치면 무너진다”를 보이는 것이기 때문이다.

예제 2.2 — \(\sqrt{2}\)는 무리수이다#

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

이번에는 설계만 함께 하고, 본문은 완성본으로 본다.

확인 18. 번역표를 채워 보자. 가정할 것 \(\neg P\): \(\sqrt{2}\)는 \(\underline{\quad(1)\quad}\)이다. 출발점: \(\sqrt{2} = \underline{\quad(2)\quad}\)인 정수 \(a, b\)(\(b \neq 0\))가 존재하며, 게다가 \(\underline{\quad(3)\quad}\)로 잡을 수 있다. 도착점: 아무 모순이나.

답

(1) 유리수 (2) \(\frac{a}{b}\) (3) 기약분수.

셋째 칸이 이 증명의 설계다. §1.3 확인 3에서 본 대로, 충돌할 상대를 첫머리에

설치해 두지 않으면 마지막 줄에서 충돌시킬 것이 없다. 그 상대를 공급하는 것이

빌려 쓰는 사실 1(모든 유리수는 기약분수로 나타낼 수 있다)이다.

확인 19. 출발점의 등식 \(\sqrt{2} = \frac{a}{b}\)에는 근호가 있다. 정수의 언어로 계산하려면 먼저 무엇을 하는가.

답

양변을 제곱한다(근거 ③). \(2 = \frac{a^2}{b^2}\), 곧 \(a^2 = 2b^2\).

근호가 사라지고 정수만 남는 등식이 되었다 — 이제부터는 1주차와 2주차의

도구가 그대로 통한다. 근호를 없애는 이 한 걸음이 무리수 논증의 표준 절차다

(문제 7, 15, 17이 각각 제곱과 세제곱으로 이 걸음을 반복한다).

완성본.

증명의 한 줄

왜 이 줄을 쓰는가?

모순을 이끌어내기 위해, \(\sqrt{2}\)가 유리수라고 가정하자.

기법 선언 + 부정 제작. “무리수”의 부정은 “유리수”다(정의 15.1). 11주차 문제 20이 이 한 줄이었다.

그러면 \(\sqrt{2} = \frac{a}{b}\)인 정수 \(a, b\)(\(b \neq 0\))가 존재하며, 기약분수로 잡을 수 있다 — 곧 \(a\)와 \(b\)의 공통 약수는 \(\pm 1\)뿐이다.

유리수의 정의를 풀고(근거 ①), 빌려 쓰는 사실 1로 기약 조건을 붙인다. 이 조건이 마지막 줄에서 충돌할 상대다.

양변을 제곱하면 \(2 = \frac{a^2}{b^2}\), 곧 \(a^2 = 2b^2\)이다.

근호를 없애고 정수 세계의 등식으로 옮긴다(근거 ③).

\(a^2 = 2b^2\)은 \(2 \times (\text{정수})\) 꼴이므로 짝수이고, 따라서 \(a\)는 짝수이다 (19주차 예제 2.1).

대우로 증명해 둔 명제를 부품으로 쓴다(근거 ④). “\(a^2\)이 짝수이면 \(a\)가 짝수”는 정의만으로는 나오지 않는다.

\(a = 2c\)인 정수 \(c\)가 존재한다. 대입하면 \(4c^2 = 2b^2\), 곧 \(b^2 = 2c^2\)이다.

짝수의 정의를 풀고(근거 ①) 대입한 뒤 양변을 2로 나눈다(근거 ③).

\(b^2 = 2c^2\)도 짝수이므로 \(b\)도 짝수이다 (같은 부품).

같은 명제를 \(b\)에 한 번 더 적용한다. 이제 \(a\)와 \(b\)가 둘 다 짝수다.

\(a\)와 \(b\)가 모두 짝수이면 2가 공통 약수인데, 이는 공통 약수가 \(\pm 1\)뿐이라는 것과 동시에 성립할 수 없다. 모순이다. 따라서 \(\sqrt{2}\)는 무리수이다. \(\blacksquare\)

둘째 줄과 충돌 — \(C\) = “2는 공통 약수가 아니다”(기약 조건에서 따라온다), \(\neg C\) = “2는 공통 약수이다”. 원명제 회수.

구조 읽기. 이 증명에서 “기약”은 장식이 아니다. 그 조각이 없으면 마지막 줄에 남는 것은 “\(a\)와 \(b\)가 둘 다 짝수”라는 문장 하나뿐이고, 그 문장은 그 자체로 거짓이 아니다. 그리고 19주차 예제 2.1은 두 번 소비된다 — \(a\)에 한 번, \(b\)에 한 번. 두 곳 모두 근거를 적어야 한다.

예제 2.3 — 소수는 무한히 많다#

명제. 소수는 무한히 많다.

이번에는 설계부터 스스로 해 보자.

확인 20. 가정할 것 \(\neg P\)는 무엇이고, 그 가정이 손에 쥐여 주는 것은 무엇인가.

답

\(\neg P\) = “소수는 유한 개뿐이다”. 손에 들어오는 것은 소수 전체의 목록

\(p_1, p_2, \dots, p_n\)이다. 유한 개라는 가정이 없으면 “전부를 나열했다”고

적을 수 없다 — 이 목록이 이 증명의 재료 전부이고, 도착점은 목록의 완전성과의

충돌이 된다.

확인 21. 목록 \(p_1, \dots, p_n\)의 어느 소수로도 나누어떨어지지 않는 수를 만들려 한다. 곱 \(p_1 p_2 \cdots p_n\)에 무엇을 더하면 되는가. 그렇게 만든 수를 \(p_i\)로 나눈 나머지는 얼마인가.

답

1을 더한다. \(N = p_1 p_2 \cdots p_n + 1\)을 \(p_i\)로 나누면 앞의 곱은 \(p_i\)의

배수이므로 나머지는 1이다. “목록의 어느 것으로도 나누어떨어지지 않는 수”를

만드는 것이 이 증명의 설계이고, 그 수의 소수 약수가 목록 밖에 있을 수밖에

없다는 것이 충돌의 내용이다.

증명. 모순을 이끌어내기 위해, 소수가 유한 개뿐이라고 가정하고 그 전부를 \(p_1, p_2, \dots, p_n\)이라 하자. 수

\[ N = p_1 p_2 \cdots p_n + 1 \]

을 생각하자. \(N \ge 2\)이므로 \(N\)은 소수인 약수 \(p\)를 가진다(빌려 쓰는 사실 2). \(p\)는 소수이고 목록이 소수 전부이므로, 어떤 \(i\)에 대해 \(p = p_i\)이다. 그러면 \(p \mid N\)이고, 또 \(p\)는 곱 \(p_1 p_2 \cdots p_n\)의 인수 중 하나이므로 \(p \mid p_1 p_2 \cdots p_n\)이다(2주차 훈련 1). 따라서 2주차 문제 17 (\(a \mid (b + c)\)이고 \(a \mid b\)이면 \(a \mid c\))에 의해

\[ p \mid \big(N - p_1 p_2 \cdots p_n\big) = 1 \]

이다. 그러나 \(p\)는 소수이므로 \(p \ge 2\)이고, \(p \mid 1\)이려면 \(1 = pc\)인 정수 \(c\)가 있어야 하는데 그러면 \(|p| \cdot |c| = 1\)이고 \(|c| \ge 1\)이므로 \(|p| \le 1\)이 되어 \(p \ge 2\)와 어긋난다. 모순이다. 따라서 소수는 무한히 많다. \(\blacksquare\)

이번 증명은 표 없이 산문으로 적었다. 표는 연습 단계의 장치이고, 실전의 증명은 처음부터 끝까지 이런 산문이다.

흔한 오해 교정. 이 증명은 \(N\) 자체가 소수라고 주장하지 않는다. 실제로

\[ 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \times 509 \]

로 \(N\)이 합성수인 사례가 있다. 논증이 말하는 것은 “\(N\)의 소수 약수가 목록 안에 있을 수 없다”는 것 — 곧 목록이 완전할 수 없다는 것이다. 위 사례에서도 소수 약수 59와 509는 둘 다 목록 \(2, 3, 5, 7, 11, 13\) 밖에 있다. 문제 13의 채점 기준에 이 구분이 들어간다.

관찰 — 세 증명의 같은 뼈대#

예제 2.1, 2.2, 2.3은 소재가 각각 순서\(\cdot\)분수\(\cdot\)소수로 전혀 다르다. 대응표의 빈칸을 채워 뼈대를 비교해 보자.

단계

예제 2.1

예제 2.2

예제 2.3

① 부정 가정 + 이름 붙이기

가장 큰 정수가 존재한다 — 그것을 \(N\)이라 하자

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

소수가 유한 개뿐이다 — 전부를 \(p_1, \dots, p_n\)이라 하자

② 재료 전개 + 모순 후보 제작

모든 정수 \(n\)에 대해 \(n \le N\); \(N + 1\)을 만든다

\(a^2 = 2b^2\)에서 \(a\)와 \(b\)가 모두 짝수임을 유도

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

③ 충돌 지목 + 원명제 회수

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

공통 약수 2 vs 공통 약수는 \(\pm 1\)뿐

\(p \mid 1\) vs \(p \ge 2\)

확인 22. 표의 빈칸 (1)(2)(3)을 채워 보자.

답

(1) \(\sqrt{2}\)가 유리수이다 — \(\sqrt{2} = \frac{a}{b}\)(기약)로 놓자.

(2) \(N = p_1 \cdots p_n + 1\)을 만들고 그 소수 약수 \(p\)를 잡아 \(p \mid 1\)을 유도한다.

(3) \(N + 1 \le N\) vs \(N + 1 > N\).

세 증명 모두 정확히 이 세 걸음이다.

방금 확인한 뼈대에 이름을 붙인다.

백지 암기 대상

귀류법의 3단계 틀

① \(\neg P\)를 가정하고, 그 가정이 주는 대상에 이름을 붙인다 \(\to\) ② 가정이 준 재료로 전개해 모순 후보를 만든다 \(\to\) ③ 충돌한 두 문장을 지목하고 원명제를 회수한다

22주차에서는 이 틀이 조건문 \(P \Rightarrow Q\)에 적용될 때 ①이 어떻게 바뀌는지를 본다.

빈칸 사다리 — 지지대를 하나씩 빼며#

필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다.

훈련 1 ●○○ — 수식 빈칸#

명제. 유리수와 무리수의 합은 무리수이다.

증명. 모순을 이끌어내기 위해, 유리수 \(x\)와 무리수 \(y\)에 대해 \(x + y\)가 \(\underline{\quad(1)\quad}\)라고 가정하자. 그러면

\[ y = (x + y) - x \]

는 유리수에서 유리수를 뺀 것이므로 \(\underline{\quad(2)\quad}\)이다 (15주차 문제 9: 두 유리수의 차는 유리수). 이는 \(y\)가 \(\underline{\quad(3)\quad}\)라는 가정과 모순이다. 따라서 \(x + y\)는 무리수이다. \(\blacksquare\)

훈련 2 ●●○ — 수식과 근거를 함께#

이번에는 구조 낱말과 근거 문장도 빈칸이다.

명제. 유리수 \(r\)과 무리수 \(y\)에 대해 \(y - r\)은 무리수이다.

증명. 모순을 이끌어내기 위해, \(y - r\)이 \(\underline{\quad(1)\quad}\)라고 가정하고 그것을 \(q\)라 하자. 그러면

\[ y = q + \underline{\quad(2)\quad} \]

이고, \(\underline{\quad(3)\quad}\)이므로 \(y\)는 유리수이다. 이는 \(\underline{\quad(4)\quad}\)과 모순이다. 따라서 \(\underline{\quad(5)\quad}\). \(\blacksquare\)

훈련 3 ●●● — 뼈대만 남기고#

이번에는 3단계 틀(§2 관찰)의 각 칸을 통째로 채운다.

명제. \(6n + 3 = 2m\)을 만족하는 정수 \(n, m\)은 존재하지 않는다.

증명의 뼈대.

  • ① 부정 가정과 이름 붙이기: \(\underline{\quad(1)\quad}\)

  • ② 재료 전개와 모순 후보 제작: \(\underline{\quad(2)\quad}\)

  • ③ 충돌 지목과 원명제 회수: \(\underline{\quad(3)\quad}\)

(좌변과 우변의 홀짝을 각각 판정하면 된다. “어떤 정수도 짝수이면서 동시에 홀수일 수는 없다”는 지금은 인정하고 쓴다 — 22주차 문제 5에서 증명한다. 이 훈련이 문제 12의 예행연습이다.)

연습문제 (20문항)#

해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 ‘접근’까지만 읽고 다시 시도한다 \(\to\) 그래도 안 되면 풀이를 읽는다.

이번 주의 채점 기준

답이 아니라 근거가 점수다. “\(\sqrt{3}\)은 무리수다(맞음)”는 0점이고,

첫 줄에 정확한 부정을 선언하고 마지막 줄에 충돌한 두 문장을 지목한 증명이

만점이다. 귀류법 답안에서 가장 자주 비는 칸이 정확히 그 두 군데다 —

첫 줄의 “모순을 이끌어내기 위해 ~라고 가정하자”와 마지막 줄의 “무엇과

무엇이 모순인지”. 난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다.

기본 ●○○#

1. 다음 명제를 귀류법으로 증명한다면 첫 문장에 가정할 내용을 정확히 쓰시오 (증명 불필요). (a) \(\sqrt{3}\)은 무리수이다. (b) 가장 작은 양의 유리수는 존재하지 않는다. (c) \(x^2 = 4y + 3\)을 만족하는 정수 \(x, y\)는 존재하지 않는다.

힌트

세 항목 모두 §1.5 서식의 첫 문장을 채우는 일이다. (b)(c)의

“존재하지 않는다”는 11주차 총목록의 \(\exists\) 줄을 거꾸로 읽는다 — 부정하면

“존재한다”가 되고, 존재한다고 가정하는 순간 그 대상에 이름을 붙일 수 있다.

2. 진리표로 확인하시오: \(\neg P \Rightarrow F\) (\(F\)는 항상 거짓인 명제)의 진리값 열이 \(P\)의 열과 일치한다. (2행이면 충분 — §1.4의 표를 직접 작성하는 자리다)

힌트

\(F\) 열은 두 행 모두 F로 채워 놓고 시작한다. 남은 것은 조건문 한 열뿐이고,

조건문은 가정이 T이고 결론이 F인 행에서만 F다(8주차).

3. (a) “기약분수”의 뜻을 쓰시오. (b) \(\frac{12}{18}\)을 기약분수로 나타내시오. (c) \(\sqrt{2}\) 증명에서 “기약으로 잡을 수 있다”는 가정이 없으면 마지막 모순이 왜 안 터지는지 한 문장으로 쓰시오.

힌트

(c)는 예제 2.2의 마지막 줄에서 “기약”을 지우는 삭제 실험이다. 그 줄이

충돌시키는 두 문장 중 하나가 사라지면, 남는 문장 하나는 그 자체로 거짓인가.

4. 가장 큰 짝수는 존재하지 않음을 귀류법으로 증명하시오.

힌트

예제 2.1의 \(N + 1\) 자리에 무엇을 놓아야 하는가. \(M + 1\)은 \(M\)보다 크지만

짝수가 아니므로 “가장 큰 짝수”의 최대성과 충돌하지 않는다. 만든 수가

① 짝수임 ② \(M\)보다 큼 — 두 가지를 모두 확인한다.

5. 빈칸 사다리 훈련 1(유리수 + 무리수 = 무리수)을 백지에서 완성하시오.

힌트

첫 줄에서 부정할 것은 “\(x + y\)가 무리수이다”이고 그 부정은

“\(x + y\)가 유리수이다”이다. 몸통은 \(y\)를 \(x + y\)와 \(x\)만으로 표현하는

등식 한 줄이 전부다.

6. 예제 2.1(가장 큰 정수 없음)을 백지에 재현하시오.

힌트

세 걸음만 확인하면 된다 — ① 부정 선언과 이름 붙이기 ② \(N + 1\) 제작과

정수임의 확인 ③ 충돌한 두 문장의 지목. 셋 중 하나라도 빠졌으면 다시 쓴다.

표준 ●●○#

부품 갈아 끼우기 — “\(\sqrt{p}\)는 무리수” 유형

예제 2.2의 몸통에서 2 고유의 성질(짝수 부품)에 의존하는 줄은 넷째\(\cdot\)여섯째

두 곳이다 — “\(a^2\)이 짝수이면 \(a\)는 짝수”(19주차 예제 2.1)를 쓴 자리다.

그 밖에 숫자 2가 그대로 갈리는 자리는 셋째\(\cdot\)다섯째 줄의 등식과 마지막 줄의

공통 약수값이고, 이쪽은 부품이 필요 없는 계산이다.

소수 \(p\)를 바꾸려면 앞의 두 자리에 “\(p \mid n^2\)이면 \(p \mid n\)”의 \(p\) 버전을 끼워

넣어야 한다. 3 버전은 19주차 예제 2.2에, 5 버전은 19주차 문제 15에 있다.

이 부품이 준비되지 않은 수에 대해서는 예제 2.2의 복사가 통하지 않는다 —

문제 18이 그 경계를 보여 준다.

7. \(\sqrt{3}\)은 무리수임을 증명하시오. (부품: “\(3 \mid n^2\)이면 \(3 \mid n\)” — 19주차 예제 2.2)

힌트

예제 2.2를 그대로 옮기되 2를 3으로 바꾼다. 양변을 제곱해 \(a^2 = 3b^2\)을

얻은 뒤, 짝수 부품이 아니라 3 버전 부품을 인용한다. \(a = 3c\)를 대입하면

처음과 같은 꼴의 등식이 \(b\)에 대해 다시 나온다.

8. \(x\)가 0이 아닌 유리수이고 \(y\)가 무리수이면 \(xy\)는 무리수임을 귀류법으로 증명하시오. (부품: 15주차 문제 15 — 유리수 나눗셈 닫힘)

힌트

목표를 부정하면 \(xy\)가 유리수 — 이름을 붙여 \(xy = q\)로 둔다. \(y\)를 \(q\)와

\(x\)만으로 표현하려면 나누어야 하고, 나눗셈에는 조건이 하나 붙는다.

문제의 가정 중 그 조건을 공급하는 것은 무엇인가.

9. 가장 작은 양의 유리수는 존재하지 않음을 증명하시오.

힌트

그런 \(q\)가 있다면 \(\frac{q}{2}\)는 무엇인가.

10. [백지 재현] \(\sqrt{2}\)는 무리수 — 예제 2.2를 재현하시오.

힌트

일곱 줄 중 세 곳이 자주 빈다 — 둘째 줄의 “기약분수로 잡을 수 있다”,

넷째\(\cdot\)여섯째 줄의 부품 인용(19주차 예제 2.1), 마지막 줄의 충돌 지목.

그 세 곳부터 확인한다.

11. 다음이 무리수임을 증명하시오 (\(\sqrt{2}\)가 무리수라는 사실은 이제 자유롭게 인용). (a) \(1 + \sqrt{2}\) (b) \(\dfrac{\sqrt{2}}{2}\)

힌트

(a)는 \(\sqrt{2}\)를 \(1 + \sqrt{2}\)와 1만으로 표현하는 등식 한 줄이 몸통이다.

(b)는 귀류를 새로 쓸 필요가 없다 — \(\frac{\sqrt{2}}{2} = \frac{1}{2} \cdot \sqrt{2}\)로

보면 이미 증명한 문제가 그대로 적용된다. 어느 문제인가.

새 유형 — “정수 해가 없다”

방정식에 정수 해가 없음을 보이려면, 해가 있다고 가정한 뒤 그 해가 반드시

만족해야 할 성질 두 가지를 각각 계산해 충돌시킨다. 가장 자주 쓰는 충돌은

홀짝이다 — 같은 수가 짝수이면서 동시에 홀수라는 결론이 나오면 모순이다.

“어떤 정수도 짝수이면서 동시에 홀수일 수는 없다”는 지금은 인정하고 쓴다

(22주차 문제 5에서 증명한다). 빈칸 사다리 훈련 3이 이 유형의 예행연습이었다.

12. \(a^2 - 4b = 2\)를 만족하는 정수 \(a, b\)는 존재하지 않음을 증명하시오.

힌트

존재한다면 \(a^2 = 2(2b+1)\)이다. \(a\)의 홀짝을 추적해 홀수 = 짝수 충돌을 만든다.

13. [백지 재현] 소수는 무한히 많다 — 예제 2.3을 재현하시오.

힌트

세 곳이 자주 빈다 — ① “유한 개뿐”이라는 부정의 정확한 서술과 목록에

이름 붙이기 ② \(N\)의 소수 약수를 빌려 쓰는 사실 2로 확보하기

③ \(N\)이 소수라고 주장하지 않기.

14. 방정식 \(x^2 + x - 1 = 0\)은 정수 해를 갖지 않음을 증명하시오.

힌트

정수 해 \(x\)가 있다면 \(x^2 + x\)는 무엇인가 — 1주차 문제 16.

도전 ●●●#

15. \(\sqrt{6}\)은 무리수임을 증명하시오. (안내: \(a^2 = 6b^2\)에서 ① \(a^2\)이 짝수 \(\to\) \(a\) 짝수(19주차 예제 2.1) ② \(3 \mid a^2\) \(\to\) \(3 \mid a\)(19주차 예제 2.2) ③ 따라서 \(6 \mid a\)(20주차 문제 13) \(\to\) \(a = 6c\) 대입 \(\to\) \(b\)도 같은 운명 \(\to\) 기약 모순)

힌트

안내의 ①②③을 \(a\)에 대해 끝낸 뒤 그대로 \(b\)에 반복한다. \(a = 6c\)를

대입해 얻는 등식이 처음 등식과 같은 꼴(\(b^2 = 6c^2\))이라는 것이 반복의

근거다. 같은 꼴이 아니면 반복은 정당하지 않다.

16. \(\sqrt{2} + \sqrt{3}\)은 무리수임을 증명하시오.

힌트

유리수 \(r\)과 같다고 가정하고 양변을 제곱하면 \(r^2 = 5 + 2\sqrt{6}\)이다.

\(\sqrt{6}\)을 유리수들로 표현할 수 있게 되어 문제 15와 충돌한다.

17. \(\sqrt[3]{2}\)(세제곱해서 2가 되는 수)는 무리수임을 증명하시오. (부품: “\(n^3\)이 짝수이면 \(n\)은 짝수” — 19주차 문제 8)

힌트

예제 2.2의 제곱을 세제곱으로 바꾼다. \(a^3 = 2b^3\)에서 \(a\)가 짝수임을

끌어내는 부품은 19주차 문제 8이다. \(a = 2c\)를 대입해 정리하면 \(b^3\)이

짝수임이 나오는지 확인한다.

모순이 나오지 않을 때 무엇을 읽는가

지금까지의 증명은 전부 모순이 나왔다. 나오지 않는 경우도 있다. 그 경험을

해부하는 것이 다음 문제이고, 여기서 얻는 결론이 이번 주 목표의 4번이다.

풀기 전에 예제 2.2의 각 줄을 종이 왼쪽에 적고 오른쪽에 \(\sqrt{4}\) 버전을

나란히 적어, 어느 줄에서 갈라지는지 눈으로 비교한다.

18. (진단) 어떤 학생이 예제 2.2를 흉내 내어 “\(\sqrt{4}\)는 무리수”를 증명하려 했다: “\(\sqrt{4} = \frac{a}{b}\) 기약, \(4b^2 = a^2\), \(a^2\)이 짝수이므로 \(a = 2c\), 대입하면 \(4b^2 = 4c^2\), 즉 \(b^2 = c^2\)…” — 여기서 멈췄다. (a) \(\sqrt{2}\) 증명과 달리 왜 \(b\)가 짝수라는 결론이 안 나오는지 지적하시오. (b) 모순이 안 나오는 것이 당연한 이유는? (c) 이 경험이 말해 주는 “귀류법의 성질”을 한 문장으로 쓰시오.

힌트

\(\sqrt{2}\) 증명의 대응하는 줄은 \(b^2 = 2c^2\)이었고 이 시도의 줄은 \(b^2 = c^2\)이다.

두 등식이 \(b\)의 홀짝에 대해 각각 무엇을 강제하는지 비교한다.

(b)는 \(\sqrt{4}\)의 값을 실제로 계산해 보면 나온다.

19. \(n^2 \equiv 3 \pmod 4\)인 정수 \(n\)은 존재하지 않음을 귀류법으로 증명하시오. (부품: 17주차 문제 9 — \(n^2\)의 mod 4 나머지는 0 또는 1)

힌트

17주차 문제 9가 \(n^2\)을 4로 나눈 나머지의 후보를 0과 1로 좁혀 놓았다.

가정이 말하는 나머지는 3이다. 한 수를 4로 나눈 나머지가 두 값을 동시에

가질 수 없는 근거는 나눗셈 정리의 나머지 유일성이다.

20. (서술) (a) 대우 증명과 귀류법의 공통점과 차이(도착점의 관점에서)를 두 문장으로 쓰시오. (b) “귀류법은 도착점을 미리 모른다”는 특징이 장점이자 단점인 이유를 각각 한 문장으로 쓰시오.

백지 재현 — 복습 프로토콜#

권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 재현은 두 번으로 나눈다. 한 번에 완전 백지로 가지 않는다.

1차 시도 (4일차) — 틀 카드 허용. 귀류법의 3단계 틀(§2 관찰)\(\cdot\)서식(§1.5)\(\cdot\) 근거 목록(§1.9)만 펴 놓고, 예제 2.2(\(\sqrt{2}\))를 처음부터 끝까지 적는다. 본문과 19주차 부품 문장은 보지 않는다.

2차 시도 (5일차) — 완전 백지. 아무것도 보지 않고 수행한다.

  • 귀류법의 3단계 구조(정의 21.1)와 서식(§1.5)을 조각 그대로 썼다.

  • “\(\neg P\)에서 모순이 유도되면 \(P\)”가 왜 정당한지 두 행짜리 진리표로 설명했다.

  • 예제 2.2(\(\sqrt{2}\))를 처음부터 끝까지 재현했다 — “기약”의 역할과 19주차 부품이 소비되는 두 지점을 짚으면서.

  • 예제 2.3(소수 무한)을 재현했다 — “\(N\)이 소수라는 주장이 아님”을 설명하면서.

  • 귀류법의 신호 네 가지(부정형 개념 / 비존재 / 최대\(\cdot\)최소 없음 / 무한)를 썼다.

  • 이번 주에 빌려 쓴 두 사실이 무엇이고 언제 회수되는지 말할 수 있다.

  • 유리수 + 무리수, 0이 아닌 유리수 \(\times\) 무리수의 결과를 증명과 함께 기억한다.

  • 모순이 끝까지 나오지 않을 때 무엇을 읽어야 하는지 말할 수 있다 — 전개 부족인지 명제가 거짓인지의 갈림길(문제 18).

막힌 지점별 처방. 막힌 지점이 무엇을 다시 볼지 알려 준다.

막힌 지점

처방

첫 줄에 무엇을 가정할지 모르겠다

§1.5 서식 + 11주차 §1.3 부정 총목록 — 부정 제작은 규칙의 적용이다

부정은 썼는데 다음 줄이 없다

§1.2의 표 — 부정을 정의로 풀어 등식이나 대상 이름을 손에 넣는다

전개는 되는데 모순이 안 보인다

§1.3 확인 3 — 충돌할 상대를 첫머리에 설치했는지 확인한다

“이상하다”까지 갔는데 끝내지 못한다

§1.3 조각 삭제 실험 — 모순은 \(C \land \neg C\) 꼴이어야 한다

최대\(\cdot\)최소 유형에서 막힌다

예제 2.1의 2~3단계 — 최대성을 부등식으로 적고, 그 범위에 속하는 대상을 만든다

무리수 유형에서 부품이 기억나지 않는다

§1.9 근거 목록의 ④ 칸 — 2\(\cdot\)3\(\cdot\)5 각각의 부품 위치가 적혀 있다

모순이 끝까지 나오지 않는다

문제 18 — 전개가 부족한 것인지 명제가 거짓인 것인지 갈림길을 확인한다

하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다.

해설#

각 해설은 접근(문제 앞에서 무엇을 생각하는가)과 풀이로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다.

빈칸 사다리 — 훈련 1#

(1) 유리수 (2) 유리수 (3) 무리수

※ (2)의 근거는 15주차 문제 9(두 유리수의 차는 유리수)다. 부정 가정이 \(x + y\)를 유리수로 만들어 주었으므로 \(y = (x+y) - x\)의 우변은 유리수 두 개의 차이고, 따라서 \(y\)가 유리수가 된다 — 무리수라는 가정과 충돌한다. 이 훈련의 설계는 “무리수 \(y\)를 유리수들만으로 표현하는 등식 한 줄”을 만드는 것이고, 문제 8\(\cdot\)11\(\cdot\)16이 전부 같은 설계의 변형이다.

빈칸 사다리 — 훈련 2#

(1) 유리수 (2) \(r\) (3) 두 유리수의 합은 유리수이므로 (15주차 예제 2.2, 근거 ④) (4) \(y\)가 무리수라는 가정 (5) \(y - r\)은 무리수이다

※ 훈련 1과 다른 점은 부정한 대상에 이름을 붙인 것뿐이다. “\(y - r\)이 유리수라고 가정하고 그것을 \(q\)라 하자”로 이름을 붙였기 때문에 \(y = q + r\)처럼 등식으로 옮겨 적을 수 있다. 이름 붙이기가 없으면 이 등식이 나오지 않는다.

빈칸 사다리 — 훈련 3#

(1) 모순을 이끌어내기 위해, \(6n + 3 = 2m\)인 정수 \(n, m\)이 존재한다고 가정하자. (2) 좌변은 \(6n + 3 = 2(3n + 1) + 1\)이고 \(3n + 1\)은 정수이므로(근거 ②) 홀수이다. 우변은 \(2m\)이고 \(m\)은 정수이므로 짝수이다. 두 변은 같은 수이므로, 그 수는 짝수이면서 동시에 홀수이다. (3) 어떤 정수도 짝수이면서 동시에 홀수일 수는 없으므로(인정하고 쓰는 사실, 22주차 문제 5) 모순이다. 따라서 \(6n + 3 = 2m\)인 정수 \(n, m\)은 존재하지 않는다. \(\blacksquare\)

※ 이 유형의 요령은 하나다 — 같은 수를 두 가지 방식으로 읽어 서로 다른 판정을 얻는 것. 문제 12와 문제 14가 같은 요령을 쓴다.

문제 1#

접근. 세 항목 모두 §1.5 서식의 첫 문장을 만드는 일이고, 재료는 11주차 §1.3의 부정 총목록과 정의 15.1뿐이다. (a)는 “무리수”의 부정이 “유리수”라는 것, (b)(c)는 “존재하지 않는다”(\(\neg \exists\))를 다시 부정하면 이중부정이 풀려 “존재한다”가 된다는 것. 존재 가정에서는 그 대상에 이름을 붙이는 데까지가 첫 문장의 임무다 — 이름이 없으면 둘째 줄에서 계산할 것이 없다.

풀이. (a) “모순을 이끌어내기 위해, \(\sqrt{3}\)이 유리수라고 가정하자.” (이어지는 둘째 줄은 “그러면 \(\sqrt{3} = \frac{a}{b}\)인 정수 \(a, b\)(\(b \neq 0\))가 존재하고 기약분수로 잡을 수 있다”가 된다.) (b) “모순을 이끌어내기 위해, 가장 작은 양의 유리수가 존재한다고 가정하고 그것을 \(q\)라 하자.” (c) “모순을 이끌어내기 위해, \(x^2 = 4y + 3\)을 만족하는 정수 \(x, y\)가 존재한다고 가정하자.”

복기. (b)와 (c)의 차이도 짚어 둔다. (b)는 대상이 하나이므로 이름 하나(\(q\))를 붙이고, (c)는 문제가 이미 \(x, y\)라는 이름을 주었으므로 새로 붙일 이름이 없다. 이름이 필요한지 아닌지는 부정한 문장이 무엇을 존재한다고 말하는지가 정한다.

문제 2#

접근. \(F\)는 항상 거짓인 명제이므로 그 열은 두 행 모두 F로 미리 채워 놓는다. 남은 것은 조건문 \(\neg P \Rightarrow F\) 한 열을 행마다 계산하는 것뿐이고, 조건문은 가정이 T이고 결론이 F인 행에서만 F다(8주차).

풀이.

\(P\)

\(\neg P\)

\(F\)

\(\neg P \Rightarrow F\)

T

F

F

T

F

T

F

F

첫 행: \(\neg P\) = F이고 \(F\) = F이므로 가정이 거짓인 조건문 — 진리값은 T. 둘째 행: \(\neg P\) = T이고 \(F\) = F이므로 T \(\Rightarrow\) F — 진리값은 F. 마지막 열 (T, F)는 첫 열 \(P\)의 (T, F)와 완전히 일치한다. 두 명제의 진리값이 모든 행에서 같으므로 둘은 동치다(9주차). 곧 “\(\neg P\)에서 거짓이 유도됨”을 보이는 것은 “\(P\)이다”를 보이는 것과 논리적으로 같은 일이다. \(\blacksquare\)

복기. 귀류법이 정당한 이유가 이 두 행에 전부 들어 있다. 모순 \(C \land \neg C\)는 어떤 상황에서도 거짓인 명제(7주차)이므로 \(F\) 자리에 그대로 들어간다 — 그래서 §1.4의 표와 이 표는 같은 표다.

문제 3#

접근. (a)(b)는 정의 21.2의 적용이다. (c)는 예제 2.2의 마지막 줄에서 “기약”을 지우는 삭제 실험이고, 물을 것은 하나다 — 충돌시키는 두 문장 중 하나가 사라지면 남는 문장은 그 자체로 거짓인가.

풀이. (a) 분자와 분모의 공통 약수가 \(\pm 1\)뿐인 분수. 정확히는, 정수 \(a, b\)(\(b \neq 0\))에 대해 \(\frac{a}{b}\)가 기약분수라는 것은 \(a\)와 \(b\)의 공통 약수가 \(\pm 1\)뿐이라는 뜻이다(정의 21.2). (b) \(12 = 6 \times 2\), \(18 = 6 \times 3\)이므로 6이 공통 약수이고 \(\frac{12}{18}\)은 기약분수가 아니다. 분자와 분모를 6으로 나누면 \(\frac{12}{18} = \frac{2}{3}\)이고, 2와 3의 공통 약수는 \(\pm 1\)뿐이므로 \(\frac{2}{3}\)이 기약분수 표현이다. (c) 기약 가정이 없으면 마지막 줄에서 손에 남는 것은 “\(a\)와 \(b\)가 모두 짝수”라는 문장 하나뿐인데, 그 문장은 그 자체로 거짓이 아니다 — \(\frac{4}{2}\)처럼 분자와 분모가 모두 짝수인 유리수 표현은 얼마든지 있기 때문이다. 모순은 \(C \land \neg C\) 꼴이어야 하는데 충돌할 상대 \(C\)(“공통 약수는 \(\pm 1\)뿐”)를 첫머리에 설치하지 않았으므로 \(\neg C\) 하나만 남고, 그 하나로는 아무것도 무너지지 않는다.

복기. 귀류법 설계의 절반은 “무엇과 충돌시킬지”를 미리 정해 첫머리에 적어 두는 것이다. 문제 18이 같은 조각을 반대 방향에서 확인한다 — 거기서는 상대를 설치했는데도 충돌이 나오지 않는다.

문제 4#

접근. 예제 2.1의 구조를 그대로 쓰되 조건이 하나 붙는다. 만드는 수가 짝수 여야 한다. \(M + 1\)은 \(M\)보다 크지만 짝수가 아니므로 “가장 큰 짝수”의 최대성과 충돌하지 않는다 — 그 최대성은 짝수들 사이에서만 주장되기 때문이다. \(M + 2\)를 쓰고, 그것이 짝수임을 정의로 확인한다.

풀이. 모순을 이끌어내기 위해, 가장 큰 짝수가 존재한다고 가정하고 그것을 \(M\)이라 하자. 그러면 모든 짝수 \(n\)에 대해 \(n \le M\)이다. \(M\)은 짝수이므로 정의에 의해 \(M = 2k\)인 정수 \(k\)가 존재한다. 이제 \(M + 2\)를 생각하면

\[ M + 2 = 2k + 2 = 2(k + 1) \]

이고 \(k + 1\)은 정수이므로(근거 ②) \(M + 2\)는 짝수이다. 또 \(M + 2 > M\)이다. \(M + 2\)가 짝수이므로 둘째 문장을 \(n = M + 2\)에 적용할 수 있고, 그러면 \(M + 2 \le M\)인데 이는 \(M + 2 > M\)과 동시에 성립할 수 없다. 모순이다. 따라서 가장 큰 짝수는 존재하지 않는다. \(\blacksquare\)

복기. 최대\(\cdot\)최소 유형에서 만든 대상이 가정이 말하는 범위에 속하는지를 확인하는 줄이 반드시 필요하다. 여기서는 “\(M + 2\)가 짝수임”이 그 줄이고, 문제 9에서는 “\(\frac{q}{2}\)가 양의 유리수임”이 그 줄이다.

검산. \(M = 100\)이면 \(M + 2 = 102 = 2 \times 51\) — 짝수이고 100보다 크다 ✓.

문제 5#

접근. 훈련 1의 세 빈칸을 채운 뒤 통째로 재현한다. 설계의 핵심은 “무리수 \(y\)를 유리수들만으로 표현하는 등식”을 한 줄 만드는 것이다: \(y = (x + y) - x\). 부정 가정이 \(x + y\)를 유리수로 만들어 주었으므로 우변은 유리수 두 개의 차다.

풀이. 모순을 이끌어내기 위해, 유리수 \(x\)와 무리수 \(y\)에 대해 \(x + y\)가 유리수라고 가정하자. 그러면

\[ y = (x + y) - x \]

이고, 우변은 유리수에서 유리수를 뺀 것이므로 유리수이다(15주차 문제 9). 곧 \(y\)가 유리수인데, 이는 \(y\)가 무리수라는 가정과 모순이다. 따라서 \(x + y\)는 무리수이다. \(\blacksquare\)

복기. 이 세 줄이 이번 주 무리수 논증의 표준형이다 — 무리수를 유리수들의 사칙연산으로 표현하는 등식을 한 줄 만들고, 15주차 닫힘성 정리로 그것이 유리수임을 선언한 뒤, 무리수라는 가정과 충돌시킨다. 문제 8\(\cdot\)11\(\cdot\)16이 각각 곱\(\cdot\)차\(\cdot\)제곱으로 같은 설계를 반복한다.

검산. \(x = 1\), \(y = \sqrt{2}\)로 두면 \(x + y = 1 + \sqrt{2}\) — 문제 11(a)가 이 명제의 특수한 경우다 ✓.

문제 6#

접근. 재현 문제이므로 채점 기준을 미리 정해 놓고 쓴다 — ① 부정 선언과 이름 붙이기 ② \(N + 1\)의 정수임 확인 ③ 충돌한 두 문장의 지목. 셋 중 하나라도 빠지면 재현이 아니다.

풀이. 모순을 이끌어내기 위해, 가장 큰 정수가 존재한다고 가정하고 그것을 \(N\)이라 하자. 그러면 모든 정수 \(n\)에 대해 \(n \le N\)이다. \(N\)과 1이 정수이므로 \(N + 1\)도 정수이고(근거 ②), \(N + 1 > N\)이다. 둘째 문장을 \(n = N + 1\)에 적용하면 \(N + 1 \le N\)인데, 이는 \(N + 1 > N\)과 동시에 성립할 수 없다. 모순이다. 따라서 가장 큰 정수는 존재하지 않는다. \(\blacksquare\)

복기. 다섯 줄짜리 증명이지만 세 걸음이 모두 들어 있다. 가장 자주 빠지는 것은 둘째 줄(“모든 정수 \(n\)에 대해 \(n \le N\)”)이다 — 이 줄이 없으면 마지막에서 \(N + 1 \le N\)을 끌어낼 근거가 없어, 충돌 대신 “\(N+1\)이 더 크다”는 관찰 하나만 남는다.

문제 7#

접근. 예제 2.2를 그대로 옮기되 2를 3으로 바꾼다. 조심할 곳은 부품 한 군데다 — “\(a^2\)이 짝수이면 \(a\)는 짝수”(19주차 예제 2.1)는 2 전용이므로, 3에 대해서는 “\(3 \mid a^2\)이면 \(3 \mid a\)”(19주차 예제 2.2)로 갈아 끼워야 한다.

풀이. 모순을 이끌어내기 위해, \(\sqrt{3}\)이 유리수라고 가정하자. 그러면 \(\sqrt{3} = \frac{a}{b}\)인 정수 \(a, b\)(\(b \neq 0\))가 존재하고, 기약분수로 잡을 수 있다 — 곧 \(a\)와 \(b\)의 공통 약수는 \(\pm 1\)뿐이다. 양변을 제곱하면 \(3 = \frac{a^2}{b^2}\), 곧

\[ a^2 = 3b^2 \]

이다. 우변이 \(3 \times (\text{정수})\) 꼴이므로 \(3 \mid a^2\)이고, 19주차 예제 2.2에 의해 \(3 \mid a\)이다. 그러면 \(a = 3c\)인 정수 \(c\)가 존재하고, 대입하면 \(9c^2 = 3b^2\), 곧

\[ b^2 = 3c^2 \]

이다. 같은 이유로 \(3 \mid b^2\)이고, 같은 부품에 의해 \(3 \mid b\)이다. 그러면 3이 \(a\)와 \(b\)의 공통 약수인데, 이는 공통 약수가 \(\pm 1\)뿐이라는 것과 동시에 성립할 수 없다. 모순이다. 따라서 \(\sqrt{3}\)은 무리수이다. \(\blacksquare\)

복기. 예제 2.2와 이 증명의 차이는 두 낱말(“짝수” \(\to\) “\(3 \mid\)”)과 부품 인용처, 그리고 등식 속 숫자 2를 3으로 바꾼 계산뿐이다. 증명의 뼈대가 소재와 분리되어 있음을 확인하는 자리이고, 문제 15가 이 갈아 끼우기를 두 부품 동시에 하는 문제다.

검산. \(1.7^2 = 2.89\), \(1.8^2 = 3.24\)이므로 \(\sqrt{3}\)은 1과 2 사이에 있어 정수가 아니다. 다만 이 관찰은 무리수임의 증명이 아니다 — 정수가 아니라는 것과 유리수가 아니라는 것은 다른 주장이다(\(\frac{3}{2}\)은 정수가 아니지만 유리수다).

문제 8#

접근. 결론이 “무리수”이므로 부정하면 “\(xy\)가 유리수”가 되고, 이름을 붙여 \(xy = q\)로 둔다. 목표는 \(y\)를 유리수들만으로 표현하는 것 — \(y = \frac{q}{x}\)다. 나눗셈에는 분모가 0이 아니어야 한다는 조건이 붙고, 가정 “\(x\)가 0이 아닌 유리수”가 정확히 그 자리에서 소비된다.

풀이. 모순을 이끌어내기 위해, \(xy\)가 유리수라고 가정하고 그것을 \(q\)라 하자. \(x \neq 0\)이므로 양변을 \(x\)로 나눌 수 있고,

\[ y = \frac{xy}{x} = \frac{q}{x} \]

이다. \(q\)는 유리수이고 \(x\)는 0이 아닌 유리수이므로, 15주차 문제 15(유리수를 0이 아닌 유리수로 나눈 몫은 유리수)에 의해 \(y\)는 유리수이다. 이는 \(y\)가 무리수라는 가정과 모순이다. 따라서 \(xy\)는 무리수이다. \(\blacksquare\)

복기. 가정 “\(x \neq 0\)”이 증명의 어느 지점에서 소비되는지 짚어 두는 습관 (18주차 확인 2)이 여기서 발동한다. 그 조건이 없으면 \(x = 0\)일 때 \(xy = 0\)이 유리수이므로 명제 자체가 거짓이 된다 — 조건이 없으면 무너지는 자리를 아는 것이 조건을 이해한 것이다.

검산. \(x = \frac{1}{2}\), \(y = \sqrt{2}\)로 두면 \(xy = \frac{\sqrt{2}}{2}\) — 문제 11(b)가 이 명제의 특수한 경우다 ✓.

문제 9#

접근. 부정하면 “가장 작은 양의 유리수 \(q\)”가 손에 들어온다. 그 최소성을 깨려면 \(q\)보다 작은 양의 유리수를 하나 만들면 되고, 후보는 \(\frac{q}{2}\)다. 확인할 것이 세 가지다 — ① 유리수인가 ② 양수인가 ③ \(q\)보다 작은가. 셋 중 하나라도 빠지면 “가장 작은 양의 유리수”라는 가정과 맞물리지 않는다.

풀이. 모순을 이끌어내기 위해, 가장 작은 양의 유리수가 존재한다고 가정하고 그것을 \(q\)라 하자. 그러면 \(q > 0\)이고, 모든 양의 유리수 \(r\)에 대해 \(q \le r\)이다. 이제 \(\frac{q}{2}\)를 생각한다.

① \(q\)는 유리수이고 2는 0이 아닌 유리수이므로 \(\frac{q}{2}\)는 유리수이다 (15주차 문제 15). ② \(q > 0\)이고 \(2 > 0\)이므로 \(\frac{q}{2} > 0\)이다. ③ \(0 < q\)의 양변에 \(q\)를 더하면 \(q < 2q\)이고, 양변을 2로 나누면 \(\frac{q}{2} < q\)이다.

①②③에 의해 \(\frac{q}{2}\)는 양의 유리수이고 \(q\)보다 작다. ①②에 의해 둘째 문장을 \(r = \frac{q}{2}\)에 적용할 수 있으므로 \(q \le \frac{q}{2}\)인데, 이는 ③과 동시에 성립할 수 없다. 모순이다. 따라서 가장 작은 양의 유리수는 존재하지 않는다. \(\blacksquare\)

복기. 예제 2.1과 같은 유형이지만 만드는 방향이 반대다 — 최대를 깰 때는 더 큰 것을, 최소를 깰 때는 더 작은 것을 만든다. 그리고 만든 대상이 가정이 말하는 범위(여기서는 양의 유리수)에 속하는지 확인하는 줄이 문제 4와 같은 자리에서 필요하다.

검산. \(q = \frac{1}{1000}\)이면 \(\frac{q}{2} = \frac{1}{2000}\) — 유리수이고 양수이며 더 작다 ✓. 0에 아무리 가까운 양의 유리수를 잡아도 그 절반이 또 있다.

문제 10#

접근. 예제 2.2의 일곱 줄 재현이다. 자주 비는 칸은 세 곳 — 둘째 줄의 “기약분수로 잡을 수 있다”, 넷째\(\cdot\)여섯째 줄의 부품 인용(19주차 예제 2.1), 마지막 줄의 충돌 지목. 쓰기 전에 이 세 곳을 채점 기준으로 적어 둔다.

풀이. 모순을 이끌어내기 위해, \(\sqrt{2}\)가 유리수라고 가정하자. 그러면 \(\sqrt{2} = \frac{a}{b}\)인 정수 \(a, b\)(\(b \neq 0\))가 존재하고, 기약분수로 잡을 수 있다 — 곧 \(a\)와 \(b\)의 공통 약수는 \(\pm 1\)뿐이다. 양변을 제곱하면 \(2 = \frac{a^2}{b^2}\), 곧

\[ a^2 = 2b^2 \]

이다. 우변이 \(2 \times (\text{정수})\) 꼴이므로 \(a^2\)은 짝수이고, 19주차 예제 2.1에 의해 \(a\)는 짝수이다. 그러면 \(a = 2c\)인 정수 \(c\)가 존재하고, 대입하면 \(4c^2 = 2b^2\), 곧

\[ b^2 = 2c^2 \]

이다. 같은 이유로 \(b^2\)은 짝수이고, 같은 부품에 의해 \(b\)도 짝수이다. 그러면 \(a\)와 \(b\)가 모두 짝수이므로 2가 공통 약수인데, 이는 공통 약수가 \(\pm 1\)뿐이라는 것과 동시에 성립할 수 없다. 모순이다. 따라서 \(\sqrt{2}\)는 무리수이다. \(\blacksquare\)

복기. 채점 포인트 다섯 가지: ① 부정을 정확히(“유리수라고 가정”) ② 기약 선언 ③ \(a^2\) 짝수에서 \(a\) 짝수로 갈 때 근거 인용 ④ 같은 논증을 \(b\)에 반복 ⑤ 기약과의 충돌 지목. ③이 빠진 답안이 가장 많은데, 그 줄은 정의만으로는 나오지 않는 줄이므로 근거 없이 쓰면 증명이 끊긴다.

문제 11#

접근. 두 항목 모두 이미 증명한 결과를 부품으로 쓰면 짧아진다(근거 ④). (a)는 \(\sqrt{2}\)를 \(1 + \sqrt{2}\)와 1만으로 표현하는 등식 한 줄이 몸통이다. (b)는 귀류를 새로 쓸 필요가 없다 — 문제 8이 이미 “0이 아닌 유리수 \(\times\) 무리수 = 무리수”라는 일반 명제이므로, 이 문제는 그 명제의 한 사례일 뿐이다.

풀이. (a) 모순을 이끌어내기 위해, \(1 + \sqrt{2}\)가 유리수라고 가정하자. 그러면

\[ \sqrt{2} = (1 + \sqrt{2}) - 1 \]

이고, \(1 = \frac{1}{1}\)은 유리수이므로 우변은 유리수에서 유리수를 뺀 것 — 따라서 유리수이다(15주차 문제 9). 곧 \(\sqrt{2}\)가 유리수인데, 이는 예제 2.2에서 증명한 “\(\sqrt{2}\)는 무리수”와 모순이다. 따라서 \(1 + \sqrt{2}\)는 무리수이다. \(\blacksquare\)

(b) \(\frac{\sqrt{2}}{2} = \frac{1}{2} \cdot \sqrt{2}\)이다. \(\frac{1}{2}\)은 0이 아닌 유리수이고 \(\sqrt{2}\)는 무리수이므로(예제 2.2), 문제 8에 의해 곱 \(\frac{1}{2} \cdot \sqrt{2}\)는 무리수이다. 따라서 \(\frac{\sqrt{2}}{2}\)는 무리수이다. \(\blacksquare\)

복기. (b)에서 귀류를 새로 쓰지 않은 것이 요령이다. 이미 증명한 일반 명제가 있으면 개별 사례는 그 명제의 적용 한 줄로 끝난다 — 1주차 문제 13의 풀이 2와 같은 감각이고, 이것이 근거 ④가 목록에 있는 이유다. (a)도 훈련 1의 일반 명제 “유리수 + 무리수 = 무리수”를 \(x = 1\), \(y = \sqrt{2}\)에 적용하는 한 줄로 대신할 수 있다 — 두 방식 모두 정답이다.

검산. 소수 전개(\(2.414\dots\), \(0.707\dots\))로는 무리수 여부를 판정할 수 없다 — 판정의 근거는 언제나 증명이지 수치가 아니다.

문제 12#

접근. “정수 해가 없다”는 비존재형이므로 귀류법의 신호다. 해가 존재한다고 가정하면 등식 \(a^2 - 4b = 2\)가 손에 들어온다. 문제의 힌트대로 정리하면 \(a^2 = 2(2b+1)\)이므로 \(a^2\)이 짝수이고, 여기서 \(a\)가 짝수임을 끌어낸다 (19주차 예제 2.1). \(a = 2c\)를 대입해 양변을 2로 나누면 좌변과 우변의 홀짝이 갈라진다.

풀이. 모순을 이끌어내기 위해, \(a^2 - 4b = 2\)인 정수 \(a, b\)가 존재한다고 가정하자. 그러면

\[ a^2 = 4b + 2 = 2(2b + 1) \]

이고 \(2b + 1\)은 정수이므로(근거 ②) \(a^2\)은 짝수이다. 19주차 예제 2.1에 의해 \(a\)는 짝수이므로 \(a = 2c\)인 정수 \(c\)가 존재한다. 대입하면 \(4c^2 = 4b + 2\)이고, 양변을 2로 나누면

\[ 2c^2 = 2b + 1 \]

이다. 좌변은 \(2 \times (\text{정수})\)이므로 짝수이고, 우변은 \(2 \times (\text{정수}) + 1\)이므로 홀수다. 두 변은 같은 수이므로 그 수는 짝수이면서 동시에 홀수인데, 어떤 정수도 그럴 수는 없다(인정하고 쓰는 사실, 22주차 문제 5에서 증명한다). 모순이다. 따라서 \(a^2 - 4b = 2\)를 만족하는 정수 \(a, b\)는 존재하지 않는다. \(\blacksquare\)

복기. 훈련 3과 같은 요령이다 — 같은 수를 두 방식으로 읽어 서로 다른 판정을 얻는다. 다른 점은 홀짝 정보를 바로 얻지 못하고 “\(a\)가 짝수”라는 중간 단계를 19주차 부품으로 확보해야 한다는 것이다.

검산. \(a^2 - 2 = 4b\)여야 하므로 \(a^2 - 2\)가 4의 배수여야 한다. \(a = 0, 1, 2, 3, 4\)에서 \(a^2 - 2 = -2, -1, 2, 7, 14\) — 어느 것도 4의 배수가 아니다 ✓. 검산은 증명이 아니지만 방향 확인에는 쓸 수 있다.

문제 13#

접근. 예제 2.3의 재현이다. 채점 기준은 세 가지 — ① “소수가 유한 개뿐”이라는 부정을 정확히 쓰고 목록에 이름을 붙였는가 ② \(N\)의 소수 약수를 빌려 쓰는 사실 2로 확보했는가 ③ \(N\)이 소수라고 주장하지 않았는가.

풀이. 모순을 이끌어내기 위해, 소수가 유한 개뿐이라고 가정하고 그 전부를 \(p_1, p_2, \dots, p_n\)이라 하자. 수 \(N = p_1 p_2 \cdots p_n + 1\)을 생각한다. \(N \ge 2\)이므로 \(N\)은 소수인 약수 \(p\)를 가진다(빌려 쓰는 사실 2). 목록이 소수 전부이므로 어떤 \(i\)에 대해 \(p = p_i\)이다. 그러면 \(p \mid N\)이고, \(p\)는 곱 \(p_1 p_2 \cdots p_n\)의 인수 중 하나이므로 \(p \mid p_1 p_2 \cdots p_n\)이다 (2주차 훈련 1). 2주차 문제 17에 의해

\[ p \mid \big(N - p_1 p_2 \cdots p_n\big) = 1 \]

이다. 그러나 \(p\)는 소수이므로 \(p \ge 2\)인데, \(1 = pc\)인 정수 \(c\)가 있다면 \(|p| \cdot |c| = 1\)이고 \(|c| \ge 1\)이므로 \(|p| \le 1\)이 되어 \(p \ge 2\)와 어긋난다. 모순이다. 따라서 소수는 무한히 많다. \(\blacksquare\)

복기. 이 증명이 “\(N\)은 소수다”라고 주장한다는 오해가 가장 흔하다. 실제로 \(2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \times 509\)는 합성수다. 논증이 말하는 것은 “\(N\)의 소수 약수가 목록 안에 있을 수 없다”는 것이고, 위 사례에서도 59와 509는 목록 \(2, 3, 5, 7, 11, 13\) 밖에 있다. 이 구분을 설명할 수 있으면 재현이 완결된 것이다.

검산. 목록이 \(\{2, 3\}\)이면 \(N = 7\), 소수 약수 7 — 목록 밖이다 ✓. \(\{2, 3, 5\}\)면 \(N = 31\), 소수 약수 31 — 역시 밖이다 ✓.

문제 14#

접근. “정수 해를 갖지 않는다”는 비존재형이므로 귀류법이다. 해가 있다고 가정하면 \(x^2 + x = 1\)이라는 등식이 손에 들어온다. 좌변은 \(x(x+1)\)로 묶이는데, 연속한 두 정수의 곱이 짝수임은 1주차 문제 16에서 증명해 두었다. 우변 1은 홀수이므로 홀짝 충돌이 만들어진다.

풀이. 모순을 이끌어내기 위해, \(x^2 + x - 1 = 0\)을 만족하는 정수 \(x\)가 존재한다고 가정하자. 그러면

\[ x^2 + x = 1 \]

이다. 좌변은 \(x^2 + x = x(x+1)\)로 묶이고, 이는 연속한 두 정수의 곱이므로 짝수이다(1주차 문제 16). 곧 \(x^2 + x = 2k\)인 정수 \(k\)가 존재한다. 그러면 \(2k = 1\)인데, 좌변은 짝수이고 \(1 = 2 \cdot 0 + 1\)은 홀수이므로 같은 수가 짝수이면서 동시에 홀수가 된다 — 어떤 정수도 그럴 수는 없다(인정하고 쓰는 사실, 22주차 문제 5에서 증명한다). 모순이다. 따라서 이 방정식은 정수 해를 갖지 않는다. \(\blacksquare\)

복기. 근의 공식으로 \(x = \frac{-1 \pm \sqrt{5}}{2}\)를 구한 뒤 “정수가 아니다”라고 적는 길도 있지만, 그 길은 \(\sqrt{5}\)가 무리수인지까지 따로 따져야 한다. 홀짝 충돌은 근을 전혀 구하지 않고 세 줄로 끝난다 — 구하지 않고도 판정할 수 있으면 구하지 않는다.

검산. \(x = -2, -1, 0, 1\)에서 \(x^2 + x - 1\)은 각각 \(1, -1, -1, 1\)이고, \(|x| \ge 2\)이면 \(|x^2+x| \ge 2\)이다 ✓.

문제 15#

접근. 예제 2.2의 갈아 끼우기를 부품 두 개로 동시에 하는 문제다. \(a^2 = 6b^2\) 하나에서 \(a\)의 성질을 두 번 읽는다 — 2의 배수임과 3의 배수임. 두 정보를 합쳐 \(6 \mid a\)를 얻는 것이 20주차 문제 13이고, 그래야 \(a = 6c\)를 대입했을 때 처음과 같은 꼴의 등식이 \(b\)에 대해 나와 논증을 반복할 수 있다.

풀이. 모순을 이끌어내기 위해, \(\sqrt{6}\)이 유리수라고 가정하자. 그러면 \(\sqrt{6} = \frac{a}{b}\)인 정수 \(a, b\)(\(b \neq 0\))가 존재하고 기약분수로 잡을 수 있다. 양변을 제곱하면

\[ a^2 = 6b^2 \]

이다. 이제 \(a\)에 대해 두 가지를 읽는다. ① \(a^2 = 2(3b^2)\)이므로 \(a^2\)은 짝수이고, 19주차 예제 2.1에 의해 \(a\)는 짝수다. 곧 \(2 \mid a\). ② \(a^2 = 3(2b^2)\)이므로 \(3 \mid a^2\)이고, 19주차 예제 2.2에 의해 \(3 \mid a\). ③ \(2 \mid a\)이고 \(3 \mid a\)이므로 20주차 문제 13에 의해 \(6 \mid a\)이다.

따라서 \(a = 6c\)인 정수 \(c\)가 존재한다. 대입하면 \(36c^2 = 6b^2\), 곧

\[ b^2 = 6c^2 \]

이다. 이는 처음 등식과 같은 꼴이므로 ①②③을 \(b\)에 그대로 반복할 수 있고, \(6 \mid b\)를 얻는다. 그러면 6이 \(a\)와 \(b\)의 공통 약수인데, 이는 공통 약수가 \(\pm 1\)뿐이라는 것과 동시에 성립할 수 없다. 모순이다. 따라서 \(\sqrt{6}\)은 무리수이다. \(\blacksquare\)

복기. ③이 없으면 논증이 닫히지 않는다. \(2 \mid a\)만으로 \(a = 2c\)를 대입하면 \(4c^2 = 6b^2\), 곧 \(2c^2 = 3b^2\)이 되어 처음과 다른 꼴이 되고 반복이 끊긴다. “같은 꼴로 되돌아오는가”가 이 유형에서 확인할 지점이다.

검산. \(2.4^2 = 5.76\), \(2.5^2 = 6.25\)이므로 \(\sqrt{6}\)은 2와 3 사이에 있다. \(6 = 2 \times 3\)처럼 서로 다른 소수의 곱인 경우에 이 논법이 통하고, \(4 = 2^2\)처럼 제곱수인 경우에는 통하지 않는다 — 그 경계가 문제 18이다.

문제 16#

접근. \(\sqrt{2} + \sqrt{3}\)을 직접 다루는 부품은 없다. 대신 유리수라고 가정한 뒤 제곱하면 \(\sqrt{6}\)이 유리수들의 식으로 표현되고, 이미 증명한 문제 15와 충돌시킬 수 있다. 이 문제의 설계는 “충돌 상대를 이미 증명된 정리에서 빌려 온다”는 것이다.

풀이. 모순을 이끌어내기 위해, \(\sqrt{2} + \sqrt{3}\)이 유리수라고 가정하고 그것을 \(r\)이라 하자. 양변을 제곱하면

\[ r^2 = (\sqrt{2} + \sqrt{3})^2 = 2 + 2\sqrt{2}\sqrt{3} + 3 = 5 + 2\sqrt{6} \]

이므로

\[ \sqrt{6} = \frac{r^2 - 5}{2} \]

이다. \(r\)이 유리수이므로 \(r^2 = r \cdot r\)은 유리수이고(15주차 훈련 1, 곱 닫힘), \(5 = \frac{5}{1}\)은 유리수이므로 \(r^2 - 5\)도 유리수이며(15주차 문제 9, 차 닫힘), 2는 0이 아닌 유리수이므로 \(\frac{r^2 - 5}{2}\)도 유리수이다(15주차 문제 15, 몫 닫힘). 곧 \(\sqrt{6}\)이 유리수인데, 이는 문제 15와 모순이다. 따라서 \(\sqrt{2} + \sqrt{3}\)은 무리수이다. \(\blacksquare\)

복기. 무리수 둘의 합이 항상 무리수인 것은 아니다 — \(\sqrt{2} + (-\sqrt{2}) = 0\)이 반례다(15주차 문제 19). 일반 법칙이 없다는 것과 특정한 합이 무리수라는 것은 별개의 주장이므로, 이런 문제는 개별적으로 증명해야 한다. “무리수 + 무리수 = 무리수”를 정리처럼 인용한 답안은 그 반례 앞에서 무효가 된다.

검산. \(3.146^2 \approx 9.90 = 5 + 2 \times 2.449\) — \(\sqrt{6} \approx 2.449\)와 맞는다 ✓.

문제 17#

접근. 예제 2.2의 제곱을 세제곱으로 바꾼다. 근호를 없애는 걸음이 “양변을 세제곱한다”로 바뀌고, 짝수 부품도 세제곱 버전(19주차 문제 8)으로 갈아 끼운다. 나머지 뼈대는 한 줄도 다르지 않다.

풀이. 모순을 이끌어내기 위해, \(\sqrt[3]{2}\)가 유리수라고 가정하자. 그러면 \(\sqrt[3]{2} = \frac{a}{b}\)인 정수 \(a, b\)(\(b \neq 0\))가 존재하고 기약분수로 잡을 수 있다. 양변을 세제곱하면 \(2 = \frac{a^3}{b^3}\), 곧

\[ a^3 = 2b^3 \]

이다. 우변이 \(2 \times (\text{정수})\) 꼴이므로 \(a^3\)은 짝수이고, 19주차 문제 8 (”\(n^3\)이 짝수이면 \(n\)은 짝수”)에 의해 \(a\)는 짝수이다. 그러면 \(a = 2c\)인 정수 \(c\)가 존재하고, 대입하면 \(8c^3 = 2b^3\), 곧

\[ b^3 = 4c^3 = 2(2c^3) \]

이다. \(2c^3\)은 정수이므로 \(b^3\)은 짝수이고, 같은 부품에 의해 \(b\)도 짝수이다. 그러면 2가 \(a\)와 \(b\)의 공통 약수인데, 이는 공통 약수가 \(\pm 1\)뿐이라는 것과 동시에 성립할 수 없다. 모순이다. 따라서 \(\sqrt[3]{2}\)는 무리수이다. \(\blacksquare\)

복기. 예제 2.2\(\cdot\)문제 7\(\cdot\)문제 15\(\cdot\)문제 17을 나란히 놓으면 바뀐 것은 세 자리뿐이다 — 근호를 없애는 연산(제곱/세제곱), 인용하는 부품, 마지막 공통 약수의 값. 뼈대를 외우고 이 세 자리만 갈아 끼우는 것이 이 유형의 재현 방법이다.

문제 18#

접근. \(\sqrt{2}\) 증명의 각 줄을 \(\sqrt{4}\) 버전과 나란히 놓고 어느 줄에서 갈라지는지 찾는다. 갈라지는 곳은 대입 직후의 등식이다 — \(\sqrt{2}\) 쪽은 \(b^2 = 2c^2\)이고 \(\sqrt{4}\) 쪽은 \(b^2 = c^2\)이다. 그리고 (b)는 \(\sqrt{4}\)의 값을 실제로 계산하면 바로 나온다.

풀이. (a) \(\sqrt{2}\) 증명에서는 대입 후 \(b^2 = 2c^2\)이 되어 우변이 \(2 \times (\text{정수})\) 꼴이므로 \(b^2\)의 짝수성이 강제되고, 부품에 의해 \(b\)가 짝수가 되었다. \(\sqrt{4}\) 시도에서는 \(4b^2 = 4c^2\)의 양변을 4로 나누어 \(b^2 = c^2\)이 되는데, 여기에는 2라는 인수가 남아 있지 않아 \(b\)의 홀짝에 대해 아무것도 강제하지 않는다. 실제로 \(b = 1\), \(c = 1\)이면 \(b^2 = c^2\)이 성립하고 \(b\)는 홀수다 — 갈라지는 지점은 “우변에 2가 남는가”이다.

(b) \(\sqrt{4} = 2 = \frac{2}{1}\)이므로 \(\sqrt{4}\)는 실제로 유리수다. 곧 이 시도가 가정한 “\(\sqrt{4}\)가 유리수이다”는 참인 명제이고, 참인 가정에서 유도되는 것은 참뿐이므로 모순이 나올 수 없다. 증명 시도가 막히는 것이 당연하다.

(c) 귀류법은 거짓인 명제를 증명해 주지 않는다 — 모순이 나오지 않는 경험은 “전개가 아직 부족하다”는 신호일 수도 있고 “증명하려는 명제가 애초에 거짓이다”는 신호일 수도 있으며, 그 갈림길은 귀류법 자체가 알려 주지 않는다.

복기. 문제 3(c)와 짝을 이루는 문제다. 문제 3(c)는 충돌 상대를 설치하지 않아 모순이 안 나오는 경우였고, 이 문제는 상대를 제대로 설치했는데도 모순이 안 나오는 경우다. 후자에서 읽어야 할 것은 명제 자체의 진위이며, 이 갈림길을 정식으로 다루는 것이 29주차의 반증이다. 22주차 문제 19가 이 진단을 다시 묻는다.

검산. \(\sqrt{6}\)(문제 15)은 \(6 = 2 \times 3\)이라 논증이 닫혔고 \(\sqrt{4}\)는 \(4 = 2^2\)이라 닫히지 않았다 — 갈림은 제곱수인가에 있다 ✓.

문제 19#

접근. 존재 가정에서 시작해 그 \(n\)에 17주차 문제 9를 적용한다. 그 결과가 말하는 나머지 후보(0 또는 1)와 가정이 말하는 나머지(3)가 충돌한다. 충돌을 성립시키려면 “한 수를 4로 나눈 나머지는 하나뿐”이라는 유일성이 필요하고, 그 근거는 나눗셈 정리다.

풀이. 모순을 이끌어내기 위해, \(n^2 \equiv 3 \pmod 4\)인 정수 \(n\)이 존재한다고 가정하자. 정의 20.1에 의해 이는 \(4 \mid (n^2 - 3)\), 곧 \(n^2\)을 4로 나눈 나머지가 3이라는 뜻이다. 한편 17주차 문제 9에 의해 모든 정수 \(n\)에 대해 \(n^2\)을 4로 나눈 나머지는 0 또는 1이다. 그러므로 \(n^2\)을 4로 나눈 나머지가 3이면서 동시에 0 또는 1이 되는데, 나눗셈 정리에 의해 한 수를 4로 나눈 나머지는 유일하므로 두 주장이 동시에 성립할 수는 없다. 모순이다. 따라서 \(n^2 \equiv 3 \pmod 4\)인 정수 \(n\)은 존재하지 않는다. \(\blacksquare\)

복기. 같은 사실을 17주차에서는 케이스 소진으로 증명했다 — \(n\)을 4로 나눈 나머지 네 가지를 전부 계산해 3이 나오지 않음을 보이는 방식이다. 불가능성은 케이스로도 귀류로도 잡힌다. 두 증명의 관계를 논평하는 것이 23주차 문제 13이다.

검산. \(n = 0, 1, 2, 3, 4, 5\)에서 \(n^2 = 0, 1, 4, 9, 16, 25\)이고 4로 나눈 나머지는 \(0, 1, 0, 1, 0, 1\) — 3이 한 번도 나오지 않는다 ✓.

문제 20#

접근. (a)는 §1.7의 표를, (b)는 확인 8을 근거로 삼아 자기 문장으로 다시 쓴다. 서술 문제에서도 채점 기준은 같다 — 주장만 적지 말고 예를 들어 근거를 붙인다. 예제 2.1~2.3이 그 예다.

풀이. (예시 답안) (a) 공통점: 두 기법 모두 결론의 부정을 가정 쪽으로 옮겨, 직접 증명이 막히는 자리에서 전개 가능한 재료를 만든다. 차이: 대우 증명은 \(\neg Q\)에서 출발해 \(\neg P\)라는 정해진 도착점으로 가야 하지만, 귀류법은 \(\neg P\)에서 출발해 어떤 모순이든 하나만 터뜨리면 되는 열린 도착점을 가진다.

(b) 장점: 도착점이 열려 있으므로 어느 방향의 충돌이든 이용할 수 있고, 따라서 적용 범위가 가장 넓다 — 예제 2.1은 부등식 충돌, 예제 2.2는 약분 가능성 충돌, 예제 2.3은 나누어떨어짐 충돌로 서로 전혀 다른 방향이었지만 셋 다 같은 기법으로 처리되었다. 단점: 목표가 정해져 있지 않으므로 전개가 어디로 가는지 모른 채 밀고 나가야 하고, 모순이 나오지 않는 길로 오래 갈 수 있다 — 문제 18에서 본 대로, 모순이 나오지 않을 때 그것이 전개 부족 때문인지 명제가 거짓이기 때문인지도 기법 자체는 알려 주지 않는다.

복기. 이 두 물음의 답이 곧 기법 선택의 기준이 된다. 직접 증명이 되면 직접, 조건문이고 가정 쪽이 빈약하면 대우, 결론이 부정형이거나 비존재형이면 귀류 — 이 순서를 정식으로 정하는 것이 22주차다.

다음 주 예고: 귀류법을 조건문 \(P \Rightarrow Q\)에 적용한다. 조건문의 부정은 \(P \land \neg Q\)이므로(9주차), 가정이 하나가 아니라 두 개가 손에 들어온다. 그리고 대우 증명이 사실 귀류법의 특수한 경우임을 확인하고, “어떤 기법을 언제 쓰는가”의 선택 기준을 완성한다. 이번 주에 빌려 쓴 두 사실(기약분수 표현, 소수 약수의 존재)은 33주차에서 회수한다.