C7주차 — 반례·귀류·존재

C7주차 — 반례·귀류·존재#

이 주의 길잡이

핵심 문장: 반례는 \(\forall\) 명제를 무너뜨리는 증인 하나이고(부정 전개 + 구성), 귀류는 결론의 부정을 가정 목록에 올리는 거래이며, 존재 증명은 증인을 내놓거나 있음만 보장하는 것이다 — 세 기술이 모두 “무엇이 있고 무엇이 없는가”를 다룬다.

이 주의 위치: 2학기 20주 과정의 C7주차. C5\(\cdot\)C6주차에서 직접\(\cdot\)대우로 밀어붙이던 자리가 막히는 두 지점 — 명제가 애초에 거짓일 때, 결론이 부정형일 때 — 을 상대하는 기술을 세운다. 다음 주 C8주차의 최소 반례법이 이번 주 귀류 위에 세워진다. 1권 21주차(귀류)\(\cdot\)26주차(존재와 유일)\(\cdot\)29주차(반증)와 S5주차(구성법)\(\cdot\)S10주차(부정 전개)\(\cdot\)S11주차(귀류)\(\cdot\)S13주차(유일성)\(\cdot\)S15주차(경우법)가 여기서 한 장으로 모인다.

원서 대응: Chartrand 5장 (Existence and Proof by Contradiction). 1일차에 이 장을 통독한 상태로 이 교안에 온다.

이번 주 목표#

  1. 반례로 거짓 \(\forall\) 명제를 반증한다 — 부정 전개(S10주차)와 구성법(S5주차)의 합성으로 두 검증까지 갖춘 답안을 쓴다.

  2. 귀류법을 네 무대(무리수\(\cdot\)부재\(\cdot\)무한\(\cdot\)부등식)에서 운용한다 — S11주차의 4단 서식과 모순의 3대 산지를 다른 소재에서 재조직한다.

  3. 존재 증명을 구성적(증인 제시)과 비구성적(존재만 보장)으로 구분해 각각 쓴다.

  4. 존재와 유일을 결합해 “정확히 하나”를 완성한다 (S13주차의 두 얼굴).

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

표기 — § 와 난이도 표시

§는 “절”이라고 읽는다. §1.3은 이 주차의 1.3 절을, §6은 6절 전체를 가리킨다.

다른 주차를 가리킬 때는 “S11주차 §1.4”처럼 주차를 앞에 적는다.

연습문제는 기본 1~6번, 표준 7~14번, 도전 15~20번이고, 빈칸 사다리는 훈련 1에서

3으로 갈수록 지지대가 줄어든다.

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

지난주까지의 도구를 손에 올려 둔다. 셋 다 이번 주 답안에서 그대로 쓴다.

  1. 합동의 대수 보존 — 덧셈\(\cdot\)곱셈\(\cdot\)거듭제곱 — 을 진술하시오 (C6주차).

  2. S5주차의 구성법 절차(증인 제시 \(\to\) 자격 검증 \(\cdot\) 사건 검증)와 증인의 세 공급로를 재현하시오.

  3. S11주차의 귀류 4단 서식과 모순의 3대 산지를 쓰시오.

이어서 진단 문제 하나를 풀어 보자. 풀지 못해도 된다 — 이번 주가 무엇을 메우는지 가늠하기 위한 기록이다.

  1. (진단) 명제 “정수 \(a, b\)에 대해, \(a \mid b^2\)이면 \(a \mid b\)이다”가 참인지 거짓인지 판정하고, 그 판정의 근거를 적어 보자.

답을 노트에 적어 둔다. §5의 백지 재현 뒤에 이 기록을 다시 본다.

자주 나오는 세 가지 답#

방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 자연스러운 출발점이고, 셋 다 이번 주에 메울 정확한 간격이 있다.

  • 유형 1 — 사례 확인 후 “참”. \(a = 2, b = 4\)에서 \(2 \mid 16\)이고 \(2 \mid 4\),

\(a = 3, b = 6\)에서 \(3 \mid 36\)이고 \(3 \mid 6\) — 몇 개를 확인하고 참이라고 적는다. 확인한 사례에 대해서는 계산이 옳다. 문제는 명제가 모든 정수쌍에 대한 주장이고, 확인한 쌍은 유한 개라는 것이다. 이 명제는 실제로 거짓이며, 반례는 확인 범위 바로 밖에 있다(§1.2에서 찾는다).

  • 유형 2 — “거짓 같다”까지 갔으나 검증이 한쪽뿐. 방향은 옳다. 그런데 답안이

“\(a = 3, b = 2\)이면 \(3 \nmid 2\)이므로 거짓”에서 끝나는 경우가 많다. 결론이 위반됨은 확인했지만 가정이 성립하는지를 확인하지 않았다. \(3 \nmid 4\)이므로 이 쌍은 애초에 가정을 만족하지 않는다 — 반례가 아니다. 조건문 \(\forall\)의 반례에 검증이 두 개 필요한 이유가 §1.4다.

  • 유형 3 — 백지. 참인지 거짓인지 모르므로 무엇부터 해야 할지 정하지 못했다.

참\(\cdot\)거짓을 모르는 상태에서 손을 대는 순서 자체가 규칙으로 정해져 있고, §1.1이 그 순서를 제시한다.

개념 — 반례와 귀류와 존재#

1 직접·대우만으로 밀어붙이면 어디서 막히는가#

새 기술을 꺼내기 전에, 지난 두 주의 도구(C5주차의 직접\(\cdot\)대우, C6주차의 다섯 무대)만으로 두 명제를 실제로 밀어붙여 본다.

시도 1 — 준비 운동 4번을 직접 증명으로

명제: 정수 \(a, b\)에 대해, \(a \mid b^2\)이면 \(a \mid b\)이다.

“\(a \mid b^2\)이라 하자. 정의에 의해 \(b^2 = ak\)인 정수 \(k\)가 존재한다.

목표는 \(b = am\)인 정수 \(m\)을 만드는 것이다. \(b^2 = ak\)에서 \(b\)를 꺼내려면

양변의 제곱근을 취해야 하는데, \(\sqrt{ak}\)는 정수라는 보장이 없다. 따라서 … “

시도 2 — “\(\sqrt2\)는 무리수이다”를 직접 증명으로

“결론은 ‘\(\sqrt2\)는 유리수가 아니다’이다. 직접 증명은 결론의 정의 꼴을 만들어

제시하는 것인데, ‘유리수가 아니다’라는 결론에는 만들어 낼 등식이 없다.

무엇을 만들어야 하는지가 정해지지 않으므로 첫 줄이 나오지 않는다.”

두 시도가 막힌 이유는 서로 다르다.

확인 1. 시도 1과 시도 2가 막힌 이유는 각각 무엇인가. 한쪽은 “도구가 없어서”이고 다른 한쪽은 그것이 아니다. 어느 쪽이 어느 쪽인가.

답

시도 2는 도구의 문제다. 결론이 부정형(“~가 아니다”)이라 만들 목표 꼴이 없다.

부정형 결론을 등식으로 바꿔 주는 도구가 §1.5의 귀류법이다.

시도 1은 도구의 문제가 아니다. 명제가 거짓이다. 아무리 좋은 도구를 가져와도

거짓 명제의 증명은 나오지 않는다. 증명 시도가 오래 막히면 도구를 더 찾기 전에

“이 명제가 참이기는 한가”를 먼저 묻는다 — 그 물음에 답하는 기술이 §1.2의 반례다.

이 주 전체의 기준

증명이 막히면 두 갈래를 함께 검토한다.

① 명제가 거짓일 수 있다 \(\to\) 반례를 찾는다.

② 명제는 참인데 결론이 부정형이라 목표 꼴이 없다 \(\to\) 결론을 부정해 가정 자리에 올린다.

2 거짓 ∀ 명제를 무너뜨리는 것 — 사례부터 모아 보기#

거짓임이 이미 알려진 \(\forall\) 명제 몇 개를 놓고, 각각을 무너뜨린 것이 무엇이었는지 적어 보자.

거짓 명제

무너뜨린 대상

그 대상에서 확인한 것

모든 소수는 홀수이다

\(x_0 = 2\)

2는 소수이고, 2는 홀수가 아니다

모든 실수 \(x\)에 대해 \(x^2 > x\)

\(x_0 = \tfrac12\)

\(\tfrac12\)은 실수이고, \(\left(\tfrac12\right)^2 = \tfrac14 \not> \tfrac12\)

\(a \mid b^2\)이면 \(a \mid b\) (정수 \(a, b\))

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

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

확인 2. 표의 (1)(2)를 채워 보자. 그리고 세 행이 공통으로 한 동작을 한 문장으로 적어 보자.

답

(1) \(a = 4\), \(b = 2\).

(2) \(4 \mid 2^2 = 4\)이므로 가정이 성립하고, \(4 \nmid 2\)이므로 결론이 위반된다.

공통 동작: 대상 하나를 내놓고, 그 대상에서 명제가 실제로 깨짐을 확인했다.

세 행 모두 “하나”만 내놓았다는 점이 핵심이다 — 무한히 많은 사례를 다 볼 필요가 없다.

이 동작에 정식 이름과 형식을 붙인다. 동작 자체에 새로운 것은 없다 — 방금 표에서 한 일을 문장으로 굳혔을 뿐이다.

정의 7.1 — 반례 (counterexample) [백지 암기 대상]#

명제 “\(\forall x \in S,\ P(x)\)”에 대한 반례란, \(x_0 \in S\)이면서 \(P(x_0)\)이 거짓인

대상 \(x_0\)를 말한다. 반례가 하나라도 있으면 그 명제는 거짓이다.

왜 하나로 충분한가. “\(\forall x \in S,\ P(x)\)”의 부정은 S10주차 N5에 의해 “\(\exists x \in S,\ \neg P(x)\)”이다. 곧 반증한다는 것은 이 존재 명제를 증명하는 것이고, 존재 명제의 증명은 S5주차의 구성법 — 증인을 하나 제시하고 검증하는 것 — 이다.

1권에서 감각으로 하던 것이 여기서 이름을 얻는 자리. 1권 29주차에서 “증인 하나면 충분하다”로 손에 익힌 반증이, 여기서 부정 전개(S10주차) + 구성법(S5주차)의 합성이라는 이름을 얻는다. 두 검증이 어디서 오는지도 이 합성에서 확정된다(§1.4).

표기 — \(\nmid\)

“\(a \nmid b\)”는 “\(a\)는 \(b\)를 나누지 않는다”로 읽는다. 정의를 풀면

“\(b = ak\)인 정수 \(k\)가 존재하지 않는다”이다. 부정형이므로, 이 문장을 결론으로

하는 증명은 §1.5의 귀류가 자주 필요하다.

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

정의 7.1의 한 문장은 세 조각으로 되어 있다.

조각

하는 일

판정에서의 역할

“\(x_0 \in S\)이면서”

증인의 자격 요구

무대 안의 대상만 반례가 된다. 무대 밖의 대상은 명제가 애초에 주장하지 않은 것이라 아무것도 무너뜨리지 못한다

“\(P(x_0)\)이 거짓인”

증인의 사건 요구

명제가 주장한 성질이 실제로 깨짐을 보인다

“하나라도 있으면 거짓”

요구량의 명시

하나면 끝이다 — 여러 개를 모아도 점수가 늘지 않고, 하나도 없으면 반증이 성립하지 않는다

조각 삭제 실험 — 첫째 조각을 지우면. “무대 안”이라는 요구를 지워 보자. 그러면 다음 답안이 합법이 된다.

삭제 실험 — 무대를 벗어난 증인

명제: 모든 소수 \(p\)에 대해 \(p \ge 2\)이다.

“반례: \(x_0 = 1\). \(1 < 2\)이므로 명제가 깨진다.”

\(1\)은 소수가 아니므로 이 명제가 애초에 아무 말도 하지 않은 대상이다. 무대 조각을 지우는 순간, 참인 명제도 전부 반증할 수 있게 되어 “반례”라는 말이 아무것도 구별하지 못한다.

확인 3. 조건문 \(\forall\) 명제 “\(\forall x,\ P(x) \Rightarrow Q(x)\)”에서, 위 표의 “자격”과 “사건”은 각각 무엇이 되는가. S10주차의 어느 규칙이 그 답을 주는가.

답

N4(\(\neg(P \Rightarrow Q) \leadsto P \wedge \neg Q\))가 답을 준다.

부정은 “\(\exists x,\ P(x) \wedge \neg Q(x)\)”이므로 — 자격은 가정 \(P(x_0)\)이 참,

사건은 결론 \(Q(x_0)\)이 거짓이다. 둘 다 확인해야 존재 명제의 증명이 완결된다.

§0 유형 2의 답안이 빠뜨린 것이 정확히 자격 쪽이다.

4 반례 답안의 서식 — 절차 해부#

정의를 답안의 문장으로 옮기면 네 걸음이 된다.

백지 암기 대상

반례 답안의 4단 서식

① 부정 전개 — “명제가 거짓임을 보인다. 곧 \(\exists x_0\): (가정 성립) \(\land\) (결론 위반)을 증명한다.” 전개는 S10주차의 N5\(\cdot\)N4로 하고 규칙 번호를 단다.

② 증인 제시 — “\(x_0 = \cdots\)로 두자.” 값을 실제로 내놓는다.

③ 자격 검증 — 그 증인이 무대에 있고 가정을 만족함을 계산으로 보인다.

④ 사건 검증 — 그 증인에서 결론이 위반됨을 계산으로 보인다.

걸음

하는 일

이 걸음을 빼면 무엇이 무너지는가

① 부정 전개

무엇을 증명할지 확정한다

아래 두 검증이 무엇을 향한 것인지 독자가 복원할 수 없다. 조건문에서 N4를 빠뜨리면 “가정도 결론도 거짓인” 쌍을 반례로 제출하게 된다

② 증인 제시

검증할 대상을 무대에 올린다

검증이 가리킬 것이 없다. “그런 것이 있다”로 메우면 곧바로 순환이 된다

③ 자격 검증

증인이 명제의 사정권 안에 있음을 보인다

무대 밖 대상이 통과한다 (§1.3의 삭제 실험)

④ 사건 검증

명제가 실제로 깨짐을 보인다

자격만 갖춘 평범한 사례를 반례라 부르게 된다

걸음 삭제 실험 — ③을 빼면. 자격 검증 의무를 지우면 다음 답안이 합법이 된다.

삭제 실험 — 사건만 검증한 답안

명제: 정수 \(a, b\)에 대해, \(a \mid b^2\)이면 \(a \mid b\)이다.

“반례: \(a = 3\), \(b = 2\). \(3 \nmid 2\)이므로 결론이 위반된다. 따라서 명제는 거짓이다.”

확인 4. 위 답안의 채점표를 만들어 보자. 자격 “\(3 \mid 2^2\)” 과 사건 “\(3 \nmid 2\)” 각각에 대해 검증 여부를 적고, 비어 있는 칸을 지목해 보자.

답

사건은 검증됨 — \(3k = 2\)인 정수 \(k\)가 없으므로 \(3 \nmid 2\)이다.

자격은 비어 있고, 채울 수도 없다 — \(2^2 = 4\)이고 \(3 \nmid 4\)이므로 이 쌍은 가정을

만족하지 않는다. 가정이 거짓인 쌍에서는 조건문 자체가 참이므로(C5주차의 공허한 증명),

이 쌍은 명제를 조금도 흔들지 못한다. 채점표에 빈칸이 하나라도 있으면 그 답안은

반례가 아니다.

5 귀류법 — 부정형 결론이 등식을 얻는 자리#

시도 2가 막힌 이유는 결론 “\(\sqrt2\)는 유리수가 아니다”에 만들 등식이 없다는 것이었다. 귀류법은 그 결론을 부정해 가정 목록에 올리는 거래다. 부정하면 “\(\sqrt2\)는 유리수이다”가 되고, 이것은 등식 \(\sqrt2 = a/b\)를 준다 — 없던 자리에 전개할 재료가 생긴다. 대가는 도착점의 상실이며, 그 대신 도착점이 “아무 모순”으로 넓어진다. 서식과 산지는 S11주차에서 이미 이름을 얻었으므로 여기서는 그대로 가져다 쓴다.

백지 암기 대상

귀류 답안의 4단 서식

① 개시 선언 — “결론을 부정하여, ~라 가정하자.” 물결 자리에는 결론의 부정을 S10주차의 규칙으로 전개한 결과를 쓴다.

② 전진 — 가정, 결론의 부정, 정의, 이미 증명된 명제로 새 사실을 만든다.

③ 모순 명시 — “그런데 ~이므로 …와 모순이다.” 충돌한 두 문장을 둘 다 지목한다.

④ 결론 선언 — “따라서 ~이다.” 원래 결론의 문장으로 돌아온다.

모순의 3대 산지도 그대로다.

산지

충돌하는 두 당사자

이번 주에서의 예

① 유도한 것 \(\leftrightarrow\) 원래 가정

개시 이후 얻은 결과가 문제의 가정을 뒤집는다

가정이 “\(t\)는 무리수”인데 유도 결과가 “\(t\)는 유리수” (§3 훈련 2)

② 유도한 것 \(\leftrightarrow\) 개시 가정의 다른 조각

개시 가정이 스스로를 뒤집는다

기약분수로 잡았는데 분자\(\cdot\)분모가 공약수를 가진다 (예제 2.2)

③ 유도한 것 \(\leftrightarrow\) 이미 아는 참

정의\(\cdot\)기지의 정리와 부딪힌다

유도 결과 “\(\sqrt3\)은 유리수”가 기지의 “\(\sqrt3\)은 무리수”와 충돌 (§3 훈련 1)

Chartrand 5장이 귀류를 집중적으로 훈련하는 무대는 넷이고, 넷 모두 결론이 부정형이라 직접 증명이 막히는 자리다.

무대

결론의 꼴

부정하면 손에 들어오는 것

무리수

“\(t\)는 유리수가 아니다”

등식 \(t = a/b\) (\(a, b\) 정수, \(b \neq 0\), 기약으로 잡을 수 있다)

부재

“그런 \(x\)는 존재하지 않는다”

“그런 \(x\)가 있다” — 이름을 붙여 받아 전개한다

무한

“소수는 무한히 많다”

전체 목록 \(p_1, \ldots, p_k\) — 유한 목록은 곱할 수 있다

부등식

“\(a \le 0\)”

“\(a > 0\)” — 양수 하나가 확보되어 \(\varepsilon\) 자리에 넣을 수 있다

확인 5. 명제 “\(x^2 = 2y^2\)인 양의 정수 \(x, y\)는 존재하지 않는다”의 귀류 개시문을 적어 보자. 위 표의 어느 무대인가.

답

무대는 부재다. 개시문: “결론을 부정하여, \(x^2 = 2y^2\)인 양의 정수 \(x, y\)가

존재한다고 가정하고, 그런 쌍 하나를 \((x, y)\)로 잡자.”

부재 명제의 부정이 존재 명제이므로, 개시문에서 그 대상에 이름을 붙여 받는 것이

전진의 출발점이다. 이름을 붙이지 않으면 다음 줄에서 쓸 문자가 없다. 이 명제가

문제 17이다.

확인 6. 예제 2.2에서 보게 될 다음 충돌의 산지 번호는 몇 번인가. “\(\sqrt p = a/b\)를 기약분수로 잡았는데, 전개 끝에 \(p\)가 \(a\)와 \(b\)의 공약수임이 나왔다.”

답

산지 ②. 충돌한 두 문장은 개시 가정의 한 조각인 “\(\gcd(a, b) = 1\)”과

유도 결과인 “\(p\)는 \(a\)와 \(b\)의 공약수”이다. 둘 다 개시 이후에 생긴 것이고,

문제의 가정(”\(p\)는 소수”)이나 외부의 기지 사실과 부딪힌 것이 아니다.

기약이라는 조각을 개시문에 미리 얹어 두지 않으면 이 산지를 쓸 수 없다는 점을

함께 기억한다.

6 존재 증명 — 증인을 내놓는가, 있음만 보장하는가#

“\(\exists x \in S,\ P(x)\)”를 증명하는 방식은 두 갈래다.

정의 7.2 — 구성적 증명 (constructive proof) [백지 암기 대상]#

“\(\exists x \in S,\ P(x)\)”의 구성적 증명이란, 증인 \(x_0\)를 명시적으로 제시하고

자격(\(x_0 \in S\))과 사건(\(P(x_0)\))을 검증하는 증명이다.

정의 7.3 — 비구성적 증명 (non-constructive proof) [백지 암기 대상]#

“\(\exists x \in S,\ P(x)\)”의 비구성적 증명이란, 증인을 제시하지 않고 증인이

있다는 사실만 확립하는 증명이다. 어느 것이 증인인지는 증명이 끝나도 알지 못할

수 있다.

두 갈래를 나란히 놓으면 차이가 분명해진다.

항목

구성적

비구성적

답안에 “\(x_0 = \cdots\)” 줄이 있는가

있다

없어도 된다

무엇으로 마무리하는가

자격 검증 + 사건 검증

존재를 보장하는 논증(기성 정리\(\cdot\)경우법\(\cdot\)귀류)

끝난 뒤 증인을 아는가

안다

모를 수 있다

전형적 공급원

역산, 재료 조립 (S5주차 공급로 ①②)

중간값 정리, 비둘기집 원리, 최소원리, 경우법 (S5주차 공급로 ③)

확인 7. 다음 셋은 각각 구성적인가 비구성적인가. (가) “\(3x - 7 = 0\)인 유리수가 존재한다” — \(x = \tfrac73\)로 두고 검증한다 (나) “\(x^5 + x - 1 = 0\)인 실수가 존재한다” — 중간값 정리를 인용한다 (다) “연속한 100개의 합성수가 존재한다” — \(101! + 2, \ldots, 101! + 101\)을 제시한다

답

(가) 구성적 — 증인의 값이 답안에 적혀 있다.

(나) 비구성적 — 해가 \(0\)과 \(1\) 사이에 있다는 것만 알고 값은 모른다.

(다) 구성적 — 증인이 천문학적으로 크지만 식으로 명시되어 있다. **크기와

구성성은 무관하다.** 구성적이냐 아니냐는 “값을 적었는가”의 문제이지

“값이 작은가”의 문제가 아니다.

7 “정확히 하나” — 존재와 유일의 두 책임#

“정확히 하나 존재한다”는 두 개의 독립된 책임이다: 존재(적어도 하나)와 유일(많아야 하나). S13주차의 두 얼굴이 유일 쪽을 담당한다.

백지 암기 대상

유일성의 두 얼굴

얼굴 1 (직접 유일성). “\(P(x_1)\)이고 \(P(x_2)\)라 하자”로 시작해 \(x_1 = x_2\)를 유도한다. 서로 다르다고 가정하지 않는다.

얼굴 2 (간접 유일성). “\(P(x_1)\), \(P(x_2)\), 그리고 \(x_1 \neq x_2\)라 가정하자”로 시작해 모순을 낸다 — 귀류가 유일성 안에서 하는 일이다.

표기 — \(\exists!\)

“\(\exists!\, x \in S,\ P(x)\)”는 “\(P\)를 만족하는 \(x\)가 \(S\) 안에 정확히 하나 존재한다”로

읽는다. 느낌표 모양의 기호이지만 강조가 아니라 “유일”의 약호다. 답안은 언제나 존재

절과 유일 절의 두 문단으로 쓴다.

확인 8. “정확히 하나”의 두 책임 중 하나만 증명하면 무엇이 남는가. 각각의 경우에 어떤 명제가 아직 열려 있는가.

답

존재만 증명하면 “여러 개일 가능성”이 남는다 — 예를 들어 “\(x^2 = 4\)인 실수가

존재한다”는 참이지만 유일하지 않다(\(2\)와 \(-2\)).

유일만 증명하면 “하나도 없을 가능성”이 남는다 — “\(x^2 = -1\)인 실수는 많아야

하나”는 공허하게 참이지만 그런 실수는 없다. 두 책임은 서로를 함의하지 않는다

(1권 26주차 문제 20이 같은 대조를 다룬다).

8 이번 주에 쓸 수 있는 근거 — 목록 갱신#

허용 목록은 1권 이래 네 줄이다: ① 정의 ② 닫힘성 ③ 등식의 성질 ④ 이미 증명한 명제. 이번 주에 ④로 새로 등록되는 항목은 다음과 같다. 답안에서 인용할 때는 이름을 밝히고 그 가정이 충족되었음을 확인한 뒤 결론을 가져온다.

이번 주에 인용하는 기성 정리

진술

출처와 취급

유클리드 보조정리

\(p\)가 소수이고 \(p \mid ab\)이면 \(p \mid a\) 또는 \(p \mid b\)

S15주차 문제 10에서 증명. 1권에서는 33주차 문제 16이 인정하고 쓴 사실이다

\(\sqrt2\)\(\cdot\)\(\sqrt3\)의 무리성

\(\sqrt2 \notin \mathbb{Q}\), \(\sqrt3 \notin \mathbb{Q}\)

1권 21주차 예제 2.2와 문제 7

\(\sqrt6\)의 무리성

\(\sqrt6 \notin \mathbb{Q}\)

1권 21주차 문제 15. \(6\)은 소수가 아니므로 예제 2.2로 덮이지 않는다 — 별도 인용이 필요하다

유리수의 사칙 닫힘성

유리수끼리 더\(\cdot\)빼\(\cdot\)곱하면 유리수, \(0\)이 아닌 유리수로 나누어도 유리수

근거 ②의 유리수판. 귀류에서 “유리수가 되어 버렸다”를 만드는 통로다

중간값 정리

닫힌 구간에서 연속인 \(f\)가 부호를 바꾸면 그 사이에 근이 있다

이 과정에서는 증명 없이 기성품으로 인정하고 쓴다 (S5주차 문제 18과 같은 취급)

비둘기집 원리

물건 수가 상자 수보다 크면 둘 이상 든 상자가 있다

1권 26주차 문제 19가 양말 문제로 다루었다. 지금은 인정하고 쓴다

최소원리(정렬성)

공집합이 아닌 양의 정수 집합에는 최소원소가 있다

1권 33주차. 다음 주 C8주차의 최소 반례법이 이 위에 세워진다

확인 9. 다음 두 인용은 각각 허용되는가. 허용된다면 몇 번 근거이고, 무엇을 함께 밝혀야 하는가. (가) “\(4 \mid 2^2\)이나 \(4 \nmid 2\)이므로 유클리드 보조정리는 합성수에서 성립하지 않는다” (나) “\(\sqrt2^{\sqrt2}\)는 무리수임이 알려져 있으므로”

답

(가) 허용 — 근거 ④의 정확한 사용이다. 정리의 가정(”\(p\)는 소수”)이 \(4\)에서

충족되지 않음을 지적한 것이고, 그 지적의 증거로 예제 2.1의 반례를 든 것이다.

(나) 불허 — 목록에 없다. \(\sqrt2^{\sqrt2}\)의 무리성은 겔폰트-슈나이더 정리가 주는

사실이지만 이 과정에서 증명하지 않았고, 예제 2.3은 그 사실 없이 성립하도록

설계되어 있다. 목록 밖의 사실을 끌어오면 증명의 요점이 사라진다.