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

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

예제 — 서식 4종을 함께 쓰기#

정의는 판정 기준이고, 서식은 그 기준을 답안으로 옮기는 순서다. 아래에서는 지지대를 단계적으로 줄인다 — 예제 2.1은 설계부터 한 줄씩 함께, 예제 2.2는 설계만 함께, 예제 2.3은 설계부터 혼자 한다.

예제 2.1 — 단사이지만 전사가 아닌 함수#

명제. \(f : \mathbb{Z} \to \mathbb{Z}\), \(f(n) = 3n - 1\)은 단사이지만 전사가 아니다.

설계 — 쓰기 전에 정하는 것. 주장이 두 개이므로 증명도 두 덩어리다. 각 덩어리마다 출발점과 도착점을 정의로 번역해 둔다.

말

수식 번역

단사: 가정 (출발점)

\(f(a) = f(a')\)

\(3a - 1 = 3a' - 1\)

단사: 목표 (도착점)

\(a = a'\)

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

전사 아님: 제시할 것

도달 불가능한 \(b_0\)

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

전사 아님: 보일 것

\(f(a) = b_0\)인 \(a\)가 없음

\(3a - 1 = b_0\)을 만족하는 \(\underline{\quad(3)\quad}\)가 없음

확인 11. 표의 빈칸 (1)(2)(3)을 채워 보자. (2)에는 정수 하나를 직접 고른다.

답

(1) \(a = a'\) — 도착점은 등식 그 자체이므로 번역할 것이 없다.

(2) \(b_0 = 0\) (다른 값도 가능하다. \(3a - 1\)이 만들 수 없는 정수면 무엇이든 된다).

(3) 정수 \(a\). “실수 해가 없다”가 아니라 “정수 해가 없다”임에 주의한다 —

정의역이 \(\mathbb{Z}\)이므로 무대가 정수다.

1단계 — 단사 서식의 첫 문장.

서식 4종 표의 첫 줄 그대로다.

확인 12. 첫 문장을 완성해 보자: “\(a, a' \in \mathbb{Z}\)이고 \(\underline{\qquad}\)이라 하자. 즉 \(\underline{\qquad}\)이다.”

답

“\(a, a' \in \mathbb{Z}\)이고 \(f(a) = f(a')\)이라 하자. 즉 \(3a - 1 = 3a' - 1\)이다.”

앞 문장은 정의의 “모든 \(a, a'\)에 대해”를 임의의 한 쌍으로 받은 것이고, 뒤

문장은 그 가정을 식으로 푼 것이다. 함수 이름만 적힌 문장은 계산이 시작되지

않으므로 반드시 식으로 풀어 쓴다(근거 ①).

2단계 — 등식 계산으로 도착점까지.

확인 13. 다음 두 줄을 채워 보자: “양변에 \(\underline{\quad}\)을 더하면 \(3a = 3a'\)이고, 양변을 \(\underline{\quad}\)으로 나누면 \(a = a'\)이다.”

답

1을 더하고, 3으로 나눈다. 두 변형 모두 되돌릴 수 있는 등식 조작이므로

(근거 ③) 정보가 손실되지 않는다. 이 “되돌릴 수 있음”이 곧 입력의 복원이며,

§1.1의 물음 A에 대한 답이다. 이로써 단사가 증명되었다.

3단계 — 전사 반증의 제시.

확인 14. \(b_0 = 0\)이 도달 불가능함을 보이려 한다. \(f(a) = 0\)을 식으로 쓰고 정리하면 어떤 등식이 남는가.

답

\(3a - 1 = 0\)이므로 \(3a = 1\)이다. 여기서 멈추지 않고 다음 줄에서 “이 등식을

만족하는 정수 \(a\)가 없다”를 논증해야 한다. 방정식을 세우는 것과 해가 없음을

보이는 것은 별개의 단계다.

4단계 — 불가능성의 논증.

확인 15. “\(3a = 1\)인 정수 \(a\)가 없다”를 2주차의 나누어떨어짐 언어로 옮기고, 그 불가능성을 확정해 주는 22주차의 결과를 인용해 보자.

답

\(3a = 1\)이면 정의 2.1에 의해 \(3 \mid 1\)이다. 22주차 보조 명제 22.A에 의해

1의 약수는 \(1\)과 \(-1\)뿐인데 \(3\)은 그중 어느 것도 아니므로 모순이다. 따라서

\(3a = 1\)인 정수 \(a\)는 존재하지 않는다.

(”\(1 = 3c\)인 정수 \(c\)가 없다”로 끝내면 보이려던 명제를 문자만 바꿔 되풀이한

것이어서 아무것도 논증하지 못한다. 1의 약수를 확정해 주는 22.A가 그 자리를

메우는 부품이고, 22주차 문제 5의 힌트가 말한 빚 회수가 여기서 이루어진다.

“\(a = \frac13\)은 정수가 아니다”라고 적어도 내용은 같지만, 나눗셈 계산은

근거 목록에 없으므로 나누어떨어짐의 언어로 옮겨 적는다 — 2주차 §1.6.)

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

증명의 한 줄

왜 이 줄을 쓰는가?

(단사) \(a, a' \in \mathbb{Z}\)이고 \(f(a) = f(a')\)이라 하자. 즉 \(3a - 1 = 3a' - 1\)이다.

서식의 오프닝. 등식에서 출발해야 계산이 시작된다(근거 ①).

양변에 1을 더하면 \(3a = 3a'\)이고, 양변을 3으로 나누면 \(a = a'\)이다. 따라서 \(f\)는 단사이다.

되돌릴 수 있는 등식 변형(근거 ③)으로 도착점 \(a = a'\)에 닿았다. 입력이 복원된다는 뜻이다.

(전사 아님) \(b_0 = 0\)이라 하자. \(f(a) = 0\)이면 \(3a - 1 = 0\), 곧 \(3a = 1\)이다.

전사 반증 서식 — 도달 불가능 후보를 먼저 제시하고 그 값을 만드는 방정식을 세운다.

\(3a = 1\)은 \(3 \mid 1\)을 뜻하는데, 보조 명제 22.A(22주차)에 의해 1의 약수는 \(1\)과 \(-1\)뿐이고 \(3\)은 그중 어느 것도 아니므로 그런 정수 \(a\)는 없다. 따라서 \(0\)은 치역에 속하지 않고, \(f\)는 전사가 아니다. \(\blacksquare\)

불가능성의 논증 — 2주차 정의 2.1로 번역하고 22주차 보조 명제 22.A로 닫는다(근거 ④). 치역이 \(\{3k-1 : k \in \mathbb{Z}\}\)로 공역의 진부분집합임을 확인한 것이다(40주차 문제 8).

같은 네 줄이 모든 정수를 처리하는 이유. 완성본의 \(a, a'\)에 구체적인 수를 넣어 읽어 보자.

확인 16. \(a = 4\), \(a' = 4\)일 때와 \(a = 4\), \(a' = 5\)일 때, 단사 부분의 두 줄은 각각 어떤 문장이 되는가.

답

\(a = a' = 4\): 가정 \(11 = 11\)이 참이고, 결론 \(4 = 4\)도 참이다.

\(a = 4\), \(a' = 5\): 가정 \(11 = 14\)가 거짓이므로 조건문은 그대로 참이다 —

확인할 것이 없다. 단사 조건이 실제로 일하는 것은 가정이 참인 쌍에서뿐이고,

증명의 두 줄은 그 모든 쌍을 문자 하나로 한꺼번에 처리한다. 구체적인 수를

아무리 많이 넣어 보아도 증명이 되지 않는 이유가 여기에 있다.

예제 2.2 — 전단사: 치역 증명의 승격#

명제. \(g : \mathbb{R} - \{2\} \to \mathbb{R} - \{1\}\), \(g(x) = \dfrac{x+1}{x-2}\)는 전단사이다.

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

확인 17. 번역표를 채워 보자. 단사: 가정 \(g(x) = g(x')\) \(\to\) \(\underline{\qquad}\), 목표 \(\underline{\quad}\). 전사: 임의의 \(y \in \mathbb{R} - \{1\}\)에 대해 증인 \(x = \underline{\qquad}\)를 제시하고 두 가지를 확인한다.

답

단사: 가정 \(\dfrac{x+1}{x-2} = \dfrac{x'+1}{x'-2}\), 목표 \(x = x'\).

전사: 증인 \(x = \dfrac{2y+1}{y-1}\) (40주차 문제 17에서 \(y = \frac{x+1}{x-2}\)을

\(x\)에 관해 풀어 제작한 식이다). 확인할 두 가지는 ① \(x \neq 2\), 즉 \(x\)가

정의역에 속함 ② \(g(x) = y\)이다.

확인 18. 단사 부분에서 분모를 없애기 위해 교차 곱을 하려 한다. 그 조작이 정당한 근거는 무엇인가.

답

정의역이 \(\mathbb{R} - \{2\}\)이므로 \(x \neq 2\)이고 \(x' \neq 2\)이며, 따라서

두 분모 \(x - 2\)와 \(x' - 2\)가 모두 0이 아니다. 0이 아닌 수를 양변에 곱하는

것은 등식의 성질(근거 ③)이다. 정의역에서 2를 제외해 둔 조각이 여기서 일한다 —

정의역은 장식이 아니라 계산의 허가 조건이다.

증명. 먼저 \(g\)가 선언된 공역으로 가는 함수임을 확인한다 — \(x \neq 2\)인 \(x\)에 대해 \(g(x) = 1\)이라면 \(\frac{x+1}{x-2} = 1\)에서 \(x + 1 = x - 2\), 곧 \(1 = -2\)가 되어 모순이므로 \(g(x) \neq 1\), 즉 \(g(x) \in \mathbb{R} - \{1\}\)이다(40주차 문제 17의 (\(\subseteq\)) 방향). 이제 두 성질을 차례로 본다.

(단사) \(x, x' \in \mathbb{R} - \{2\}\)이고 \(g(x) = g(x')\)이라 하자. 즉 \(\frac{x+1}{x-2} = \frac{x'+1}{x'-2}\)이다. 두 분모가 0이 아니므로 교차 곱하면

\[ (x+1)(x'-2) = (x'+1)(x-2) \]

이고, 양변을 전개하면 \(xx' - 2x + x' - 2 = xx' - 2x' + x - 2\)이다. 양변에서 \(xx' - 2\)를 빼면 \(-2x + x' = -2x' + x\)이고, 정리하면 \(3x' = 3x\), 곧 \(x = x'\)이다. 따라서 \(g\)는 단사이다.

(전사) \(y \in \mathbb{R} - \{1\}\)이라 하자. \(x = \dfrac{2y+1}{y-1}\)을 잡는다. \(y \neq 1\)이므로 분모가 0이 아니어서 \(x\)는 실수이고, \(x = 2\)라면 \(2y + 1 = 2(y-1) = 2y - 2\)에서 \(1 = -2\)가 되어 모순이므로 \(x \neq 2\)이다. 따라서 \(x \in \mathbb{R} - \{2\}\)이다. 이제 값을 계산하면

\[ x + 1 = \frac{2y+1}{y-1} + 1 = \frac{3y}{y-1}, \qquad x - 2 = \frac{2y+1}{y-1} - 2 = \frac{3}{y-1} \]

이므로 \(g(x) = \dfrac{3y/(y-1)}{3/(y-1)} = y\)이다. 두 검증이 끝났으므로 \(g\)는 전사이다. 단사이고 전사이므로 \(g\)는 전단사이다. \(\blacksquare\)

관찰. 40주차 문제 17은 이 함수의 치역이 \(\mathbb{R} - \{1\}\)임을 증명했다. 그때 만든 증인이 여기서 그대로 전사 증명의 증인이 되었다. 달라진 것은 공역의 선언뿐이다 — 공역을 치역에 맞춰 \(\mathbb{R} - \{1\}\)로 잡는 순간, 치역 계산이 전사 증명으로 승격된다. 공역은 함수 선언의 일부이므로(40주차 정의 40.1), 전사성은 발견하는 성질이기도 하고 설계하는 성질이기도 하다.

예제 2.3 — \(\mathbb{Z}_4\) 위의 대조 실험#

명제. \(\psi, \varphi : \mathbb{Z}_4 \to \mathbb{Z}_4\)를 \(\psi([a]) = [3a]\), \(\varphi([a]) = [2a]\)로 정의할 때, \(\psi\)는 전단사이고 \(\varphi\)는 단사도 전사도 아니다.

\(\psi\)는 “프사이”, \(\varphi\)는 “파이”로 읽는다. 두 규칙 모두 잘 정의된 함수다 — \([a] = [a']\)이면 20주차 문제 9(b)(양변에 정수를 곱해도 합동이 유지된다 — 근거 ④)에 의해 \([ca] = [ca']\)이므로 대표원 선택과 무관하다. 두 함수의 단사\(\cdot\)전사를 차례로 판정한다.

이번에는 설계부터 혼자 한다. 정의역이 원소 4개짜리 유한집합이므로, 서식을 쓰기 전에 값을 전부 나열하는 것이 가장 확실하다.

풀이. \(\psi\)의 값을 전부 계산하면 \(\psi([0]) = [0]\), \(\psi([1]) = [3]\), \(\psi([2]) = [6] = [2]\), \(\psi([3]) = [9] = [1]\)이다. 출력 목록은 \([0], [3], [2], [1]\)이며 중복이 없으므로 서로 다른 두 입력이 같은 출력을 갖지 않는다 — 단사이다. 또 출력 목록이 공역 \(\mathbb{Z}_4\)의 네 원소를 모두 포함하므로 전사이다. 따라서 \(\psi\)는 전단사이다.

\(\varphi\)의 값은 \(\varphi([0]) = [0]\), \(\varphi([1]) = [2]\), \(\varphi([2]) = [4] = [0]\), \(\varphi([3]) = [6] = [2]\)이다. \(\varphi([0]) = \varphi([2]) = [0]\)인데 \([0] \neq [2]\)이므로 단사가 아니다(단사 반증의 두 검증이 모두 끝났다). 또 \([1]\)은 출력 목록에 없으므로 \(\varphi([a]) = [1]\)인 \([a]\)가 존재하지 않고, 따라서 전사도 아니다. \(\blacksquare\)

관찰. 3은 4와 서로소이고 2는 그렇지 않다. 기호 \([a] \mapsto [ca]\)는 “\([a]\)를 \([ca]\)로 보낸다”로 읽으며, 함수 이름 없이 대응 규칙만 적을 때 쓴다. \(\mathbb{Z}_4\)의 두 사례와 38주차 문제 8(b)에서 곱셈 역원을 갖는 방이 무엇이었는지가 같은 방향을 가리킨다 — \(c\)와 \(n\)이 서로소일 때만 이 꼴의 함수가 전단사로 보인다. 사례에서 읽어 낸 추측일 뿐이며, 모든 \(n\)에 대한 일반 증명은 이 교재의 범위 밖이므로 (베주 항등식이 필요하다) 여기서는 관찰로만 둔다. 문제 12에서 \(\mathbb{Z}_5\)의 사례로 한 번 더 확인한다.

관찰 — 같은 뼈대#

세 예제의 서식이 어떻게 대응하는지 표로 맞춰 본다.

단계

예제 2.1 (단사 부분)

예제 2.2 (전사 부분)

예제 2.3 (\(\varphi\)의 단사 반증)

① 목표를 정의로 번역

\(f(a) = f(a')\)에서 \(a = a'\) 도출

임의의 \(y\)에 대한 증인 제작

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

② 서식의 첫 문장

“\(f(a) = f(a')\)이라 하자”

“\(y \in \mathbb{R} - \{1\}\)이라 하자”

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

③ 본체

등식 계산

증인 제시 + 두 검증

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

④ 마무리 선언

“따라서 단사이다”

“따라서 전사이다”

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

확인 19. 위 대응표의 빈칸 (1)~(4)를 채워 보자.

답

(1) \([a] \neq [a']\)이면서 \(\varphi([a]) = \varphi([a'])\)인 쌍 하나를 찾는 것.

(2) “\([0]\)과 \([2]\)를 잡자” — 반례 쌍의 제시가 첫 문장이다.

(3) 두 검증: \([0] \neq [2]\)의 확인과 \(\varphi([0]) = \varphi([2]) = [0]\)의 계산.

(4) “따라서 단사가 아니다.”

네 서식은 전부 같은 네 단계를 밟는다 — 목표를 정의로 번역하고, 서식이 정한

첫 문장을 쓰고, 본체를 채우고, 결론을 선언한다. 달라지는 것은 본체가

“계산”인지 “제작과 검증”인지 “반례 두 검증”인지뿐이다.

백지 암기 대상

네 서식의 공통 4단계

① 목표를 정의로 번역 \(\to\) ② 서식이 정한 첫 문장 \(\to\) ③ 본체(계산 / 제작과 검증 /

반례 두 검증) \(\to\) ④ 결론 선언.

판정의 네 목표(단사 증명\(\cdot\)단사 반증\(\cdot\)전사 증명\(\cdot\)전사 반증)에는 각각 고정된

첫 문장이 있다. 목표를 먼저 적고 서식을 고르면, 증명은 빈칸을 채우는 일이 된다.

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

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

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

명제. \(f : \mathbb{R} \to \mathbb{R}\), \(f(x) = 5x - 7\)은 전단사이다.

증명. (단사) \(f(a) = f(a')\)이라 하자. 즉 \(5a - 7 = 5a' - 7\)이다. 양변에 7을 더하고 5로 나누면 \(\underline{\quad(1)\quad}\)이다. 따라서 단사이다.

(전사) \(y \in \mathbb{R}\)이라 하자. \(x = \underline{\quad(2)\quad}\)를 잡으면 \(x\)는 실수이므로 \(x \in \mathbb{R}\)이고,

\[ f(x) = 5 \cdot \underline{\quad(2)\quad} - 7 = \underline{\quad(3)\quad} \]

이다. 두 검증이 끝났으므로 전사이다. 단사이고 전사이므로 전단사이다. \(\blacksquare\)

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

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

명제. \(f : \mathbb{Z} \to \mathbb{Z}\), \(f(n) = 5n\)은 단사이지만 전사가 아니다.

증명. (단사) \(f(a) = f(a')\)이라 \(\underline{\quad(1)\quad}\). 즉 \(5a = 5a'\)이다. 양변을 5로 나누면 \(\underline{\quad(2)\quad}\)이므로 단사이다.

(전사 아님) \(b_0 = \underline{\quad(3)\quad}\)이라 하자. \(f(a) = b_0\)이면 \(\underline{\quad(4)\quad}\)인데, 이는 \(\underline{\quad(5)\quad}\)을 뜻한다. \(\underline{\quad(6)\quad}\)이므로 그런 정수 \(a\)는 존재하지 않는다. 따라서 \(b_0\)은 치역에 속하지 않고, \(f\)는 \(\underline{\quad(7)\quad}\)이다. \(\blacksquare\)

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

이번에는 서식의 각 칸을 통째로 채운다.

명제. \(f : \mathbb{N} \to \mathbb{N}\), \(f(n) = n + 1\)은 단사이지만 전사가 아니다.

증명의 뼈대.

  • ① 단사 서식의 오프닝과 등식 계산: \(\underline{\quad(1)\quad}\)

  • ② 전사 반증에서 제시할 \(b_0\)과 그 선택의 이유: \(\underline{\quad(2)\quad}\)

  • ③ 불가능성의 논증과 결론 선언: \(\underline{\quad(3)\quad}\)

(\(\mathbb{N}\)은 1부터 시작하는 자연수 전체다. 정의역과 공역을 모두 \(\mathbb{Z}\)로 바꾸면 결론이 어떻게 달라지는지도 한 줄로 적어 본다 — 이 대조가 문제 9의 예행연습이다.)

연습문제 (20문항)#

해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 ‘접근’까지만 읽고 다시 시도한다. 판정 문제는 성립하면 서식대로 증명하고, 성립하지 않으면 반례를 완전 서식으로 적는다.

이번 주의 채점 기준

답이 아니라 근거가 점수다. “\(f(x) = x^2\)은 단사가 아니다”는 0점이고,

“\(1 \neq -1\)이고 \(f(1) = 1 = f(-1)\)이므로 단사가 아니다”가 만점이다.

전사 증명에서는 증인 제시만으로 부족하고, 정의역 소속과 대입 검증의 두 줄이

모두 있어야 만점이다. 힌트 상자는 5분 이상 막힌 뒤에만 연다.

기본 ●○○#

1. [백지] 단사\(\cdot\)전사\(\cdot\)전단사의 정의와 증명 서식 4종을 쓰시오.

힌트

정의 세 개는 §1.2, §1.5, §1.7의 상자에, 서식 4종은 §1.7의 표에 있다.

서식은 “첫 문장이 무엇인가”를 기준으로 외우면 네 개가 섞이지 않는다.

2. \(A = \{1,2,3\}\), \(B = \{x, y, z\}\). 다음 함수들의 단사\(\cdot\)전사를 판정하시오. (a) \(f = \{(1,x),(2,y),(3,z)\}\) (b) \(g = \{(1,x),(2,x),(3,y)\}\) (c) \(A' = \{1,2\}\)에서 \(h = \{(1,x),(2,y)\}\) (\(B\)는 그대로)

힌트

유한 함수는 출력 목록을 적는 것이 전부다. 중복이 있으면 단사가 아니고, 공역의 원소가

빠지면 전사가 아니다. (c)는 정의역이 달라진 것에 주의한다.

3. \(f : \mathbb{Z} \to \mathbb{Z}\), \(f(n) = n + 4\)가 전단사임을 증명하시오.

힌트

두 덩어리로 나눠 쓴다. 단사는 \(a + 4 = a' + 4\)에서 시작하고, 전사는 \(y = n + 4\)를 \(n\)에

관해 풀어 증인을 만든다.

4. \(f : \mathbb{R} \to \mathbb{R}\), \(f(x) = x^2\)이 단사도 전사도 아님을 반례로 보이시오 (각각 완전 서식).

힌트

단사 반증에는 쌍이 필요하다 — 제곱해서 같아지는 서로 다른 두 실수를 찾는다. 전사

반증에는 도달 불가능한 값 하나가 필요하다 — 제곱이 가질 수 없는 부호를 생각한다.

5. 빈칸 훈련(\(5x - 7\))을 백지에서 완성하시오.

힌트

전사 부분에서 증인의 두 검증(정의역 소속, 대입)이 모두 적혀 있는지

스스로 채점한다. 증인 제작식은 \(y = 5x - 7\)을 \(x\)에 관해 푼 결과다.

6. 예제 2.1(\(3n - 1\))을 백지에 재현하시오.

힌트

네 줄이다 — 단사 오프닝, 등식 계산과 선언, \(b_0\) 제시와 방정식, 불가능성 논증과 선언.

마지막 줄에서 “정수 해가 없다”를 나누어떨어짐의 언어로 썼는지 확인한다.

표준 ●●○#

7. \(f : \mathbb{Z} \to \mathbb{Z}\), \(f(n) = 2n + 3\)의 단사\(\cdot\)전사를 판정하시오 (단사 증명 + 전사 반증).

힌트

단사는 예제 2.1과 같은 계산이다. 전사 반증에서는 \(2n + 3\)을 1주차 홀수의 정의 꼴로

다시 써 본다.

새로 필요한 것 — 인수분해 뒤에 남는 인수를 처리하기

문제 8은 \(a^3 = a'^3\)에서 시작해 차를 인수분해한다. 그러면 두 인수의 곱이

0이 되고, 실수에서 곱이 0이면 어느 한 인수가 0이다(영인수 성질 — 25주차

문제 13). 한쪽 가지는 곧바로 \(a = a'\)을 주지만, 다른 쪽 가지는 따로

처리해야 한다. 그 가지에서 쓰는 부품은 두 개다.

① 16주차 문제 16(a)의 보조정리 “\(x^2 + xy + y^2 \ge 0\)” — 그 문제는 이 부등식을

완전제곱 변형 \(x^2 + xy + y^2 = \left(x + \frac y2\right)^2 + \frac34 y^2\)으로

보였고, 여기서 쓰는 것은 그 변형이다.

② 23주차 문제 10 “실수 \(x, y\)에 대해 \(x^2 + y^2 = 0\)이면 \(x = 0\)이고 \(y = 0\)이다”

— 진술이 두 제곱의 합에 대한 것이므로, 인용하려면 \(\frac34 y^2\)을

\(\left(\frac{\sqrt3}{2}y\right)^2\)으로 먼저 고쳐 써야 한다.

두 결과 모두 이미 증명된 것이므로 근거 ④로 인용해 쓴다.

덧붙여 문제 8의 복기에서 쓰는 사실 하나: 모든 실수는 세제곱근을 가진다 —

10주차 문제 10(a)에서 기호로 옮겼던 명제이며, 실수의 완비성이 필요하므로 이

교재에서는 인정하고 쓴다.

8. \(f : \mathbb{R} \to \mathbb{R}\), \(f(x) = x^3\)이 단사임을 증명하시오. (힌트: \(a^3 = a'^3 \Rightarrow a^3 - a'^3 = 0 \Rightarrow (a - a')(a^2 + aa' + a'^2) = 0\) — 둘째 인수가 0이 되는 경우를 16주차 문제 16(a)의 보조정리로 처리)

힌트

인수분해 \(a^3 - b^3 = (a-b)(a^2+ab+b^2)\)을 먼저 전개로 확인한다. 둘째 가지에서는

“0 이상인 두 제곱의 합이 0”이 되고, 그 결론은 두 제곱이 각각 0이라는 것이다.

9. \(f : \mathbb{N} \to \mathbb{N}\), \(f(n) = n^2\)은 단사임을 증명하고, \(f : \mathbb{Z} \to \mathbb{Z}\), \(f(n) = n^2\)은 단사가 아님을 보이시오 — 정의역이 성질을 바꾼다 (40주차 문제 10의 완성).

힌트

\(a^2 = a'^2\)에서 \((a - a')(a + a') = 0\)을 만든다. \(\mathbb{N}\)에서는 둘째 인수의 부호가

확정되고, \(\mathbb{Z}\)에서는 그 확정이 사라진다 — 사라지는 자리에서 반례가 나온다.

10. 예제 2.2(\(g(x) = \frac{x+1}{x-2}\))를 백지에 재현하시오.

힌트

출력이 공역 \(\mathbb{R} - \{1\}\) 안에 있음을 먼저 확인했는지, 단사에서 교차 곱이

정당한 이유(분모가 0이 아님)를 적었는지, 전사에서 증인이 정의역에 속한다는

확인(\(x \neq 2\))을 적었는지 세 곳을 스스로 채점한다.

11. \(f : \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}\), \(f(m, n) = m + n\)의 단사\(\cdot\)전사를 판정하시오.

힌트

입력이 순서쌍이므로 반례 쌍도 순서쌍 두 개다. 합이 같아지는 서로 다른 순서쌍을 하나

찾는다. 전사 쪽은 둘째 성분을 0으로 고정하면 증인이 곧바로 나온다.

12. \(\psi : \mathbb{Z}_5 \to \mathbb{Z}_5\), \(\psi([a]) = [2a]\)의 단사\(\cdot\)전사를 값 전수 나열로 판정하시오. 예제 2.3의 \(\mathbb{Z}_4\) 결과와 대비해 원인을 한 문장으로 쓰시오.

힌트

다섯 값을 전부 계산해 목록을 만들고 중복과 누락을 본다. 마지막 문장은 2와 5, 2와 4의

관계를 비교한다.

13. 증가함수는 단사임을 증명하시오: \(f : \mathbb{R} \to \mathbb{R}\)가 “모든 \(x < y\)에 대해 \(f(x) < f(y)\)”를 만족하면 단사이다. (힌트: 대우 서식 — \(a \neq a'\)이면 WLOG \(a < a'\))

힌트

§1.4의 예외다 — 가정이 순서 정보뿐이라 등식을 풀 수 없으므로 대우 표현으로 쓴다.

\(a \neq a'\)인 두 실수는 \(a < a'\)이거나 \(a' < a\)이고, 대칭이므로 WLOG를 쓴다(17주차).

새로 필요한 것 — 비둘기집을 함수의 언어로

§1.8에서 “\(m > n\)이면 단사가 존재할 수 없다”를 확인했다. 문제 14는 이

사실을 반대 방향으로 쓴다: 정의역이 공역보다 크면 어떤 두 입력의 출력이

반드시 같다. 26주차 문제 19(양말)에서 쓴 논법과 같고, 달라진 것은 “비둘기와

집”이 “정수와 나머지”로 바뀐 것뿐이다. 나머지가 같다는 것과 차가 배수라는

것이 같은 말임은 25주차 예제 2.2에서 이미 증명했으므로 근거 ④로 인용한다.

14. (비둘기집의 회수) 임의의 정수 \(n+1\)개 중에는 차가 \(n\)의 배수인 두 수가 존재함을 증명하시오. (힌트: 각 수를 mod \(n\) 나머지로 보내는 함수 — 나머지는 \(n\)종뿐인데 수는 \(n+1\)개. 26주차 문제 19의 논법)

힌트

함수를 먼저 만든다 — 정의역은 주어진 \(n+1\)개의 정수, 공역은 나머지의 집합

\(\{0, \dots, n-1\}\). 이 함수가 단사일 수 없다는 것이 곧 결론이 요구하는 두 수의 존재다.

도전 ●●●#

이 절이 빌려 쓰는 사실

① 유한집합 \(A, B\)에 대해 \(|A| = m\), \(|B| = n\)일 때 \(A \to B\) 단사의 개수는

\(n(n-1)\cdots(n-m+1)\)이다 — 12주차 문제 19와 곱셈 원리(12주차)로 센 것이다.

문제 15(a)는 이 세기를 직접 다시 수행하므로 곱셈 원리를 근거로 인용한다.

② 유한집합에서 크기가 같은 부분집합은 전체 자신이다 — 유한집합의 기본

성질이며, 이 교재에서는 증명 없이 인정하고 쓴다. 무한집합에서는 거짓이고,

그 붕괴가 48주차의 주제다.

15. \(|A| = 3\), \(|B| = 5\)일 때: (a) \(A \to B\) 단사의 개수 (b) \(A \to B\) 전사가 존재할 수 없는 이유 (c) \(B \to A\) 단사가 존재할 수 없는 이유(비둘기집)를 각각 논하시오.

힌트

(a)는 출력 후보가 5개, 4개, 3개로 줄어든다. (b)와 (c)는 방향이 반대이므로 근거도

반대다 — 하나는 출력의 가짓수가, 다른 하나는 출력을 놓을 자리가 모자란다.

16. \(f : \mathbb{N} \to \mathbb{Z}\)를 “\(n\)이 짝수면 \(f(n) = \frac{n}{2}\), 홀수면 \(f(n) = -\frac{n-1}{2}\)”로 정의하자. \(f(1), \dots, f(6)\)을 계산하고, \(f\)가 전단사임을 증명하시오 (단사: 케이스, 전사: \(m > 0\) / \(m \le 0\) 케이스로 증인 제작 — 48주차에서 \(|\mathbb{N}| = |\mathbb{Z}|\)의 주인공이 될 함수).

힌트

여섯 값을 먼저 계산하면 출력이 정수를 훑는 순서가 보인다. 단사 증명의 첫 관문은

“출력이 같으면 두 입력의 홀짝이 같다”를 부호로 보이는 것이다.

17. \(|A| = |B| = n\) (유한)일 때 “단사 \(\Rightarrow\) 전사”를 세기로 논증하시오. (힌트: 단사면 \(|f(A)| = n\) — 치역이 공역과 크기가 같은 부분집합) 그리고 무한에서 무너지는 예: \(f : \mathbb{N} \to \mathbb{N}\), \(f(n) = 2n\)이 단사이지만 전사가 아님을 확인하시오.

힌트

단사라는 가정에서 치역의 크기를 먼저 계산한 뒤, 치역이 공역의 부분집합이면서 크기가

같다는 상황을 위 상자의 사실 ②로 처리한다. 무한 사례는 서식대로 세 줄이면 된다.

18. (진단) 다음 답안의 결함을 지적하시오.

“명제: \(f(x) = 2x + 1\) (\(\mathbb{R} \to \mathbb{R}\))은 단사다. 증명: \(a = a'\)이라 하자. 그러면 \(2a + 1 = 2a' + 1\)이므로 \(f(a) = f(a')\)이다. 따라서 단사이다. \(\blacksquare\)”

(이 학생이 증명한 것은 무엇인가? 단사의 정의와 방향을 비교하시오.)

힌트

답안의 첫 문장과 마지막 문장을 정의 41.1의 조건문과 나란히 놓는다.

§1.3의 조각 삭제 실험 2에서 같은 문장을 이미 다뤘다.

19. \(f : A \to B\)가 단사 \(\iff\) “모든 \(b \in B\)에 대해 \(f(a) = b\)인 \(a\)가 많아야 하나”임을 설명하고, 전사(“적어도 하나”) \(\cdot\) 전단사(“정확히 하나”)와 나란히 놓아 \(\exists!\)(26주차)와의 관계를 정리하시오.

힌트

각 \(b\)에 대해 “\(f(a) = b\)인 \(a\)들”의 개수를 세는 관점으로 바꿔 읽고, 세 정의가 그

개수에 각각 어떤 제한을 거는지 적는다.

20. (서술) (a) 단사 증명 서식이 “왜 대우 꼴”인지 (등식 계산의 편의) 두 문장 이내로. (b) 전사 증명이 40주차 치역 증명의 (\(\supseteq\)) 방향과 같은 작업인 이유를 한 문장으로.

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

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

1차 시도 (4일차) — 틀 카드 허용. 서식 4종 표(§1.7)와 근거 목록(§1.9)만 펴 놓고, 예제 2.1을 처음부터 끝까지 적는다. 정의 상자와 본문은 보지 않는다.

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

  • 정의 41.1, 41.2, 41.3을 조각 그대로 정확히 썼다 — “모든”, “존재한다”까지.

  • 증명 서식 4종을 첫 문장까지 포함해 표로 재현했다.

  • 예제 2.1(단사이고 전사 아님)과 예제 2.2(전단사)를 처음부터 끝까지 재현했다.

  • 전사 증명에서 증인의 두 검증(정의역 소속, 대입)을 빠뜨리지 않았다.

  • “정의역과 공역을 손보면 성질이 바뀐다”를 문제 9와 예제 2.2의 관찰로 설명했다.

  • 유한집합의 크기 법칙 네 항목을 비둘기집 포함해 재현했다.

  • 문제 16의 함수가 \(\mathbb{N}\)의 값을 어떤 순서로 정수에 대응시키는지 목록으로 적었다.

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

막힌 지점

처방

단사 증명을 어느 문장으로 시작할지 모르겠다

§1.7 서식 4종 표 — 첫 문장이 서식마다 고정되어 있다

“\(a \neq a'\)이라 하자”로 시작해 다음 줄이 막힌다

§1.4 — 등식 서식이 표준인 이유. 대우 서식은 문제 13처럼 순서만 주어질 때 쓴다

전사 증명에서 증인이 떠오르지 않는다

예제 2.2의 설계 — \(y = f(x)\)를 \(x\)에 관해 푸는 것이 제작이다

증인을 만들고 무엇을 더 써야 할지 모르겠다

§1.6 해부 표 — 정의역 소속과 대입, 두 검증이 남았다

반례를 제시했는데 채점에서 깎인다

§1.7 반증 서식 — 쌍의 상이함과 값의 동일함, 두 검증이 모두 필요하다

유한집합의 개수 논증이 헷갈린다

§1.8 — 입력 개수와 출력 자리 개수 중 어느 쪽이 모자라는지부터 정한다

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

해설#

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

빈칸 사다리 — 훈련 1#

(1) \(a = a'\) (2) \(\dfrac{y + 7}{5}\) (3) \(y\)

※ (3)을 생략하지 않고 적으면 \(5 \cdot \frac{y+7}{5} - 7 = (y+7) - 7 = y\)이다. 증인 \(\frac{y+7}{5}\)은 \(y = 5x - 7\)을 \(x\)에 관해 푼 결과이고, 실수를 0이 아닌 5로 나눈 값이므로 정의역에 속한다 — 제작\(\cdot\)소속 확인\(\cdot\)대입 검증의 세 줄이 전사 증명의 전부다.

빈칸 사다리 — 훈련 2#

(1) 하자 (2) \(a = a'\) (3) \(1\) (5의 배수가 아닌 정수면 무엇이든 된다) (4) \(5a = 1\) (5) \(5 \mid 1\) (6) 22주차 보조 명제 22.A에 의해 1의 약수는 \(1\)과 \(-1\)뿐이고 \(5\)는 그중 어느 것도 아니므로 \(5 \nmid 1\) (7) 전사가 아니다

※ 예제 2.1과 계수만 다르고 구조는 같다. 단사 쪽은 0이 아닌 수로 나누는 등식 변형이고, 전사 쪽은 “그 값을 만드는 방정식이 정수 해를 갖지 않는다”의 논증이다. \(b_0\)은 “계수의 배수가 아닌 정수”를 하나 잡으면 된다.

빈칸 사다리 — 훈련 3#

(1) \(f(a) = f(a')\)이라 하자. 즉 \(a + 1 = a' + 1\)이다. 양변에서 1을 빼면 \(a = a'\)이므로 \(f\)는 단사이다. (2) \(b_0 = 1\). \(\mathbb{N}\)의 원소 \(n\)은 \(n \ge 1\)이므로 \(f(n) = n + 1 \ge 2\)이고, 공역에서 가장 작은 원소가 출력에서 제외된다. (3) \(f(n) = 1\)이면 \(n + 1 = 1\)이므로 \(n = 0\)인데, \(0 \notin \mathbb{N}\)이므로 그런 \(n\)은 정의역에 없다. 따라서 \(1\)은 치역에 속하지 않고 \(f\)는 전사가 아니다. 단사이지만 전사가 아니므로 전단사가 아니다. \(\blacksquare\)

※ 정의역과 공역을 모두 \(\mathbb{Z}\)로 바꾼 \(\tilde f : \mathbb{Z} \to \mathbb{Z}\), \(\tilde f(n) = n + 1\)에서는 결론이 뒤집힌다 — 임의의 \(y \in \mathbb{Z}\)에 대해 증인 \(n = y - 1\)이 정수이므로(근거 ②) 전사이고, 단사는 위와 같은 계산으로 그대로이므로 전단사다. 반면 정의역만 \(\mathbb{Z}\)로 넓히고 공역을 \(\mathbb{N}\)에 둔 대응은 \(f(-5) = -4 \notin \mathbb{N}\)이므로 “모든 \(a \in A\)에 대해 \(b \in B\)가 존재”라는 조각을 어겨 애초에 함수가 아니다 — 정의역과 공역은 함께 손봐야 한다(40주차 정의 40.1). 같은 식이라도 정의역\(\cdot\)공역이 다르면 다른 함수다(40주차 문제 10). 문제 9가 같은 대조를 제곱 함수로 다룬다.

문제 1#

접근. 개념 절의 상자 세 개와 표 하나를 재현하는 문제다. 정의는 조각 단위로 외운다 — “모든”, “존재한다”가 빠지면 §1.3의 삭제 실험대로 정의가 붕괴한다. 서식은 첫 문장으로 외운다.

풀이. 정의: \(f : A \to B\)가 단사라는 것은 모든 \(a, a' \in A\)에 대해 \(f(a) = f(a')\)이면 \(a = a'\)이라는 뜻이다. \(f\)가 전사라는 것은 모든 \(b \in B\)에 대해 \(f(a) = b\)인 \(a \in A\)가 존재한다는 뜻이다. \(f\)가 전단사라는 것은 단사이면서 전사라는 뜻이다.

서식 4종: ① 단사 증명 — “\(f(a) = f(a')\)이라 하자”로 시작해 등식 계산으로 \(a = a'\)에 도달한다. ② 단사 반증 — \(a \neq a'\)이면서 \(f(a) = f(a')\)인 쌍을 제시하고 두 조건을 각각 검증한다. ③ 전사 증명 — “\(b \in B\)라 하자”로 시작해 증인 \(a\)를 제시하고, \(a \in A\)와 \(f(a) = b\)를 검증한다. ④ 전사 반증 — 도달 불가능한 \(b_0\)을 제시하고 \(f(a) = b_0\)인 \(a\)가 없음을 논증한다.

복기. 정의와 서식은 별개의 암기 대상이다. 정의는 판정 기준이고 서식은 답안의 순서다. 정의만 외우면 어느 문장으로 시작할지 모르고, 서식만 외우면 왜 그 문장으로 시작하는지 모른다.

문제 2#

접근. 유한 함수의 판정은 출력 목록을 적는 것으로 끝난다. 목록에 중복이 있으면 단사가 아니고(중복된 두 입력이 곧 반례 쌍이다), 공역의 원소 중 목록에 없는 것이 있으면 전사가 아니다(그것이 곧 \(b_0\)이다).

풀이. (a) 출력 목록은 \(x, y, z\)이다. 중복이 없으므로 단사이고, 공역 \(\{x,y,z\}\)의 세 원소가 모두 나오므로 전사이다. 따라서 전단사이다. (b) 출력 목록은 \(x, x, y\)이다. \(g(1) = g(2) = x\)인데 \(1 \neq 2\)이므로 단사가 아니다. 또 \(z\)가 목록에 없으므로 \(g(a) = z\)인 \(a\)가 존재하지 않아 전사도 아니다. (c) 정의역이 \(A' = \{1, 2\}\)로 줄었고 공역은 \(B = \{x,y,z\}\) 그대로다. 출력 목록은 \(x, y\)이며 중복이 없으므로 단사이다. \(z\)가 목록에 없으므로 전사는 아니다.

복기. (b)와 (c)를 나란히 보면 두 결함이 서로 독립임이 드러난다 — (b)는 둘 다 무너졌고 (c)는 전사만 무너졌다. \(|A'| = 2 < 3 = |B|\)이므로 (c)의 전사 불가는 §1.8의 둘째 항목이 이미 예고한 결과다.

문제 3#

접근. 전단사이므로 두 덩어리를 각각 서식대로 쓴다. 단사는 등식 계산, 전사는 증인 제작이다. 증인은 \(y = n + 4\)를 \(n\)에 관해 풀어 얻는다.

풀이. (단사) \(a, a' \in \mathbb{Z}\)이고 \(f(a) = f(a')\)이라 하자. 즉 \(a + 4 = a' + 4\)이다. 양변에서 4를 빼면 \(a = a'\)이다(근거 ③). 따라서 \(f\)는 단사이다.

(전사) \(y \in \mathbb{Z}\)라 하자. \(n = y - 4\)를 잡는다. 정수의 차는 정수이므로 \(n \in \mathbb{Z}\)이고(근거 ②), 대입하면 \(f(n) = (y - 4) + 4 = y\)이다. 두 검증이 끝났으므로 \(f\)는 전사이다. 단사이고 전사이므로 전단사이다. \(\blacksquare\)

검산. \(y = 10\)이면 증인 \(n = 6\)이고 \(f(6) = 10\), \(y = -1\)이면 증인 \(n = -5\)이고 \(f(-5) = -1\)이다.

복기. “밀기” 꼴(\(n \mapsto n + c\))은 정의역과 공역이 모두 \(\mathbb{Z}\)이면 언제나 전단사다. 훈련 3처럼 정의역을 \(\mathbb{N}\)으로 줄이면 밀린 만큼 앞쪽이 비어 전사가 무너진다.

문제 4#

접근. 반증이 두 개이므로 반례도 두 벌이다. 단사 반증에는 쌍이, 전사 반증에는 도달 불가능한 값 하나가 필요하다. 각각 §1.7의 서식대로 두 검증을 모두 적는다.

풀이. (단사가 아님) \(a = 1\), \(a' = -1\)을 잡는다. 첫째로 \(1 \neq -1\)이다. 둘째로 \(f(1) = 1^2 = 1\)이고 \(f(-1) = (-1)^2 = 1\)이므로 \(f(1) = f(-1)\)이다. 서로 다른 두 입력이 같은 출력을 가지므로 \(f\)는 단사가 아니다.

(전사가 아님) \(b_0 = -1\)을 잡는다. \(f(x) = -1\)이라면 \(x^2 = -1\)인데, 모든 실수 \(x\)에 대해 \(x^2 \ge 0\)이므로(16주차 부등식의 기본 성질 (W1)) \(x^2 = -1\)은 불가능하다. 따라서 \(-1\)을 출력하는 실수 \(x\)는 존재하지 않고, \(f\)는 전사가 아니다. \(\blacksquare\)

복기. 반례는 “제시 + 두 검증”까지가 완결이다(29주차). 단사 반증에서 \(a \neq a'\)의 확인을 빠뜨리는 경우가 많은데, 그것을 빼면 “같은 입력의 출력이 같다”는 자명한 사실만 적은 셈이 된다. 이 함수는 43주차에서 역함수를 만드는 재료로 다시 등장한다.

문제 5#

접근. 훈련 1의 재현이다. 채점의 초점은 전사 부분 — 증인 제작식, 정의역 소속 확인, 대입 검증의 세 줄이 모두 있는지 본다.

풀이. (단사) \(f(a) = f(a')\)이라 하자. 즉 \(5a - 7 = 5a' - 7\)이다. 양변에 7을 더하면 \(5a = 5a'\)이고, 양변을 5로 나누면 \(a = a'\)이다. 따라서 단사이다.

(전사) \(y \in \mathbb{R}\)이라 하자. \(x = \dfrac{y+7}{5}\)을 잡는다. 실수를 0이 아닌 실수 5로 나눈 값은 실수이므로 \(x \in \mathbb{R}\)이고,

\[ f(x) = 5 \cdot \frac{y+7}{5} - 7 = (y+7) - 7 = y \]

이다. 두 검증이 끝났으므로 전사이다. 따라서 전단사이다. \(\blacksquare\)

복기. 일차식 \(f(x) = px + q\) (\(p \neq 0\))는 \(\mathbb{R} \to \mathbb{R}\)에서 언제나 전단사이고 증인은 \(x = \frac{y-q}{p}\)이다. \(p \neq 0\)이라는 조건이 두 곳에서 일한다 — 단사에서는 나누기를 허가하고, 전사에서는 증인식의 분모가 된다.

문제 6#

접근. 예제 2.1의 네 줄 재현이다. 단사 두 줄과 전사 반증 두 줄로 나뉘며, 마지막 줄의 불가능성 논증을 나누어떨어짐의 언어로 적었는지가 채점의 초점이다.

풀이. (단사) \(a, a' \in \mathbb{Z}\)이고 \(f(a) = f(a')\)이라 하자. 즉 \(3a - 1 = 3a' - 1\)이다. 양변에 1을 더하면 \(3a = 3a'\)이고, 양변을 3으로 나누면 \(a = a'\)이다. 따라서 단사이다.

(전사가 아님) \(b_0 = 0\)을 잡는다. \(f(a) = 0\)이면 \(3a - 1 = 0\), 곧 \(3a = 1\)이다. 이는 \(3 \mid 1\)을 뜻하는데, 22주차 보조 명제 22.A에 의해 1의 약수는 \(1\)과 \(-1\)뿐이고 \(3\)은 그중 어느 것도 아니므로 \(3 \mid 1\)은 성립할 수 없다. 따라서 \(f(a) = 0\)인 정수 \(a\)는 존재하지 않고, \(0\)은 치역에 속하지 않으므로 \(f\)는 전사가 아니다. \(\blacksquare\)

복기. 치역 \(\{3k - 1 : k \in \mathbb{Z}\}\)는 공역 \(\mathbb{Z}\)의 진부분집합이다(40주차 문제 8). “치역이 공역보다 작다”와 “전사가 아니다”는 같은 사실의 두 표현이며, 답안에는 도달 불가능한 원소를 하나 명시하는 쪽이 짧고 확실하다.

문제 7#

접근. 단사는 예제 2.1과 같은 등식 계산이다. 전사 반증에서는 \(2n + 3\)이 만들 수 있는 정수를 먼저 관찰한다 — 1주차 홀수의 정의 꼴로 다시 쓰면 홀수만 나오므로 짝수 하나가 곧 \(b_0\)이다.

풀이. (단사) \(a, a' \in \mathbb{Z}\)이고 \(f(a) = f(a')\)이라 하자. 즉 \(2a + 3 = 2a' + 3\)이다. 양변에서 3을 빼면 \(2a = 2a'\)이고, 양변을 2로 나누면 \(a = a'\)이다. 따라서 단사이다.

(전사가 아님) \(b_0 = 0\)을 잡는다. 임의의 정수 \(a\)에 대해 \(2a + 3 = 2(a + 1) + 1\)이고 \(a + 1\)은 정수이므로, \(f(a)\)는 언제나 홀수의 정의 꼴이다(1주차 정의 1.2). 그런데 \(0 = 2 \times 0\)으로 짝수이고, 어떤 정수도 짝수이면서 동시에 홀수일 수 없다(22주차 문제 5). 따라서 \(f(a) = 0\)인 정수 \(a\)는 존재하지 않고, \(f\)는 전사가 아니다. \(\blacksquare\)

검산. \(f(-2) = -1\), \(f(-1) = 1\)로 0을 건너뛴다. 치역은 홀수 전체이며, 40주차 예제 2.2에서 \(2n+1\)에 대해 증명한 것과 같은 상황이다.

복기. 전사 반증에서 \(b_0\)을 고르는 요령은 “치역의 원소가 공통으로 갖는 성질”을 먼저 찾고 그 성질을 갖지 않는 값을 하나 집는 것이다. 여기서는 홀짝이, 예제 2.1에서는 3으로 나눈 나머지가 그 성질이었다.

문제 8#

접근. 단사 서식대로 \(a^3 = a'^3\)에서 출발한다. 등식을 직접 풀어 \(a = a'\)을 얻는 길은 세제곱근을 써야 하므로, 대신 차를 0으로 만들고 인수분해한다. 곱이 0이므로 두 가지로 갈리고, 둘째 가지는 부호 논증으로 닫는다.

풀이. \(a, a' \in \mathbb{R}\)이고 \(f(a) = f(a')\)이라 하자. 즉 \(a^3 = a'^3\)이다. 양변에서 \(a'^3\)을 빼면

\[ 0 = a^3 - a'^3 = (a - a')(a^2 + aa' + a'^2) \]

이다(우변을 전개하면 \(a^3 + a^2a' + aa'^2 - a^2a' - aa'^2 - a'^3 = a^3 - a'^3\)으로 중간 항이 모두 상쇄된다). 실수에서 곱이 0이면 어느 한 인수가 0이므로(영인수 성질, 25주차 문제 13) 두 경우로 나뉜다.

경우 1: \(a - a' = 0\). 그러면 \(a = a'\)이다.

경우 2: \(a^2 + aa' + a'^2 = 0\). 16주차 문제 16(a)에서 확인한 완전제곱 변형에 의해

\[ a^2 + aa' + a'^2 = \left(a + \frac{a'}{2}\right)^2 + \frac{3}{4}a'^2 \]

이다. 여기서 \(\frac34 a'^2 = \left(\frac{\sqrt3}{2}a'\right)^2\)이므로 좌변은 두 제곱의 합이 되어

\[ \left(a + \frac{a'}{2}\right)^2 + \left(\frac{\sqrt3}{2}a'\right)^2 = 0 \]

이다. 두 제곱의 합이 0이면 각각이 0이므로(23주차 문제 10) \(\frac{\sqrt3}{2}a' = 0\)에서 \(a' = 0\)이고, \(a + \frac{a'}{2} = 0\)에 \(a' = 0\)을 넣으면 \(a = 0\)이다. 이 경우도 \(a = a'\)이다.

두 경우가 전체를 덮고 어느 경우든 \(a = a'\)이므로, \(f\)는 단사이다. \(\blacksquare\)

복기. \(x^2\)은 단사가 아닌데 \(x^3\)은 단사다. 갈림은 지수의 홀짝이다 — 짝수 거듭제곱은 부호를 지워 \(a\)와 \(-a\)를 뭉개지만 홀수 거듭제곱은 부호를 보존한다. 이 함수는 전사이기도 하므로(세제곱근 존재를 인정하면 증인이 곧 \(\sqrt[3]{y}\)다) 전단사이며, 43주차 역함수의 근거가 된다.

문제 9#

접근. 두 무대를 대조하는 문제다. 양쪽 모두 \(a^2 = a'^2\)에서 \((a - a')(a + a') = 0\)을 만든다. \(\mathbb{N}\)에서는 둘째 인수의 부호가 확정되어 첫째 인수가 0일 수밖에 없고, \(\mathbb{Z}\)에서는 그 확정이 사라진다 — 사라지는 자리가 곧 반례가 사는 자리다.

풀이. (\(\mathbb{N}\)에서 단사) \(a, a' \in \mathbb{N}\)이고 \(a^2 = a'^2\)이라 하자. 양변에서 \(a'^2\)을 빼고 인수분해하면

\[ 0 = a^2 - a'^2 = (a - a')(a + a') \]

이다. \(a \ge 1\)이고 \(a' \ge 1\)이므로 \(a + a' \ge 2 > 0\)이고, 특히 \(a + a' \neq 0\)이다. 영인수 성질에 의해 곱이 0인데 둘째 인수가 0이 아니므로 \(a - a' = 0\), 곧 \(a = a'\)이다. 따라서 \(\mathbb{N}\) 위에서 \(f\)는 단사이다.

(\(\mathbb{Z}\)에서 단사가 아님) \(a = 1\), \(a' = -1\)을 잡는다. \(1 \neq -1\)이고 \(f(1) = 1 = f(-1)\)이므로, 서로 다른 두 입력이 같은 출력을 가진다. 따라서 \(\mathbb{Z}\) 위에서 \(f\)는 단사가 아니다. \(\blacksquare\)

복기. 같은 식 \(n^2\)이 정의역에 따라 단사이기도 아니기도 하다. 증명이 무너지는 지점을 짚으면 반례도 자동으로 나온다 — \(\mathbb{Z}\)에서는 \(a + a' = 0\), 곧 \(a' = -a\)가 가능해지고 그것이 반례 쌍이다. 19주차 문제 17이 함수의 언어로 재등장한 것이며, 43주차에서 정의역을 \([0, \infty)\)로 제한해 제곱근을 정의하는 근거가 된다.

문제 10#

접근. 예제 2.2의 재현이다. 채점의 초점은 세 곳 — 출력이 선언된 공역 \(\mathbb{R} - \{1\}\) 안에 있음을 먼저 확인했는가, 단사에서 교차 곱이 정당한 이유 (분모가 0이 아님)를 적었는가, 전사에서 증인의 정의역 소속(\(x \neq 2\))을 적었는가.

풀이. (공역 확인) \(x \neq 2\)인 \(x\)에 대해 \(g(x) = 1\)이라면 \(\frac{x+1}{x-2} = 1\)에서 \(x + 1 = x - 2\), 곧 \(1 = -2\)가 되어 모순이다. 따라서 \(g(x) \neq 1\)이고 \(g\)는 실제로 \(\mathbb{R} - \{1\}\)로 가는 함수다(40주차 문제 17의 (\(\subseteq\)) 방향).

(단사) \(x, x' \in \mathbb{R} - \{2\}\)이고 \(g(x) = g(x')\)이라 하자. \(x - 2 \neq 0\)이고 \(x' - 2 \neq 0\)이므로 교차 곱이 가능하고,

\[ (x+1)(x'-2) = (x'+1)(x-2) \]

이다. 전개하면 \(xx' - 2x + x' - 2 = xx' - 2x' + x - 2\)이고, 양변에서 \(xx' - 2\)를 빼면 \(-2x + x' = -2x' + x\)이다. 정리하면 \(3x' = 3x\), 곧 \(x = x'\)이다.

(전사) \(y \in \mathbb{R} - \{1\}\)이라 하자. \(x = \dfrac{2y+1}{y-1}\)을 잡는다. \(y \neq 1\)이므로 분모가 0이 아니어서 \(x\)는 실수이고, \(x = 2\)라면 \(2y + 1 = 2y - 2\)에서 \(1 = -2\)가 되어 모순이므로 \(x \neq 2\)이다. 따라서 \(x \in \mathbb{R} - \{2\}\)이다. 값을 계산하면 \(x + 1 = \frac{3y}{y-1}\), \(x - 2 = \frac{3}{y-1}\)이므로 \(g(x) = y\)이다. 두 검증이 끝났으므로 전사이다. 단사이고 전사이므로 전단사이다. \(\blacksquare\)

복기. 정의역에서 2를 빼고 공역에서 1을 뺀 두 조각이 각각 한 번씩 일한다 — 2를 뺀 덕에 교차 곱이 정당하고, 1을 뺀 덕에 증인식의 분모가 0이 되지 않는다. 정의역과 공역의 선언은 장식이 아니라 증명의 부품이다.

문제 11#

접근. 입력이 순서쌍이므로 반례 쌍도 순서쌍 두 개다. 합이 같아지는 서로 다른 순서쌍을 하나 찾으면 단사 반증이 끝나고, 전사 쪽은 둘째 성분을 0으로 고정하면 증인이 곧바로 나온다.

풀이. (단사가 아님) \((0, 1)\)과 \((1, 0)\)을 잡는다. 순서쌍의 상등은 성분별 상등이므로(6주차 정의 6.1) 첫 성분이 다른 두 순서쌍은 서로 다르다 — \((0,1) \neq (1,0)\)이다. 한편 \(f(0,1) = 0 + 1 = 1\)이고 \(f(1,0) = 1 + 0 = 1\)이므로 \(f(0,1) = f(1,0)\)이다. 서로 다른 두 입력이 같은 출력을 가지므로 단사가 아니다.

(전사) \(k \in \mathbb{Z}\)라 하자. \((k, 0)\)을 잡는다. \(k\)와 0이 모두 정수이므로 \((k, 0) \in \mathbb{Z} \times \mathbb{Z}\)이고, \(f(k, 0) = k + 0 = k\)이다. 두 검증이 끝났으므로 전사이다. \(\blacksquare\)

복기. 예제 2.1은 단사이면서 전사가 아니었고 이 문제는 전사이면서 단사가 아니다. 두 성질은 서로를 함의하지 않으며 네 조합이 모두 실재한다 — 둘 다 성립하는 예제 2.2와 예제 2.3의 \(\psi\), 둘 다 성립하지 않는 예제 2.3의 \(\varphi\). 유한집합에서 크기가 같으면 이 독립성이 사라진다(문제 17).

문제 12#

접근. 정의역이 원소 5개짜리 유한집합이므로 값을 전부 나열한다. 목록의 중복 여부와 공역 다섯 원소의 등장 여부를 보면 두 판정이 동시에 끝난다.

풀이. \(\psi([0]) = [0]\), \(\psi([1]) = [2]\), \(\psi([2]) = [4]\), \(\psi([3]) = [6] = [1]\), \(\psi([4]) = [8] = [3]\)이다. 출력 목록은 \([0], [2], [4], [1], [3]\)으로 중복이 없으므로 단사이고, \(\mathbb{Z}_5\)의 다섯 원소가 모두 나오므로 전사이다. 따라서 \(\psi\)는 전단사이다.

대비: 예제 2.3에서 \(\varphi([a]) = [2a]\)는 \(\mathbb{Z}_4\) 위에서 단사도 전사도 아니었다. 원인은 곱하는 수와 법의 관계다 — 2와 5는 서로소이지만 2와 4는 공약수 2를 가진다.

복기. 지금까지 확인한 사례는 \(\mathbb{Z}_4\)(예제 2.3), \(\mathbb{Z}_5\)(이 문제), \(\mathbb{Z}_6\)(38주차 문제 8(b)) 셋이고, 셋 다 “\(c\)와 \(n\)이 서로소일 때 곱하기가 방들을 뭉개지 않는다”는 같은 방향을 가리킨다. 사례에서 읽어 낸 추측이므로 일반 명제로 세우지는 않는다 — 모든 \(n\)에 대한 증명은 이 교재의 범위 밖이다. 43주차 문제 10에서 이 \(\psi\)의 역함수를 구성한다.

문제 13#

접근. 가정이 순서 정보뿐이라 “\(f(a) = f(a')\)”에서 시작해도 풀 방정식이 없다. §1.4에서 예고한 예외 상황이므로 대우 표현을 쓴다. \(a \neq a'\)인 두 실수는 \(a < a'\)이거나 \(a' < a\)이고, 두 경우가 대칭이므로 WLOG로 하나만 다룬다(17주차).

풀이. 단사의 대우 표현 “모든 \(a, a'\)에 대해 \(a \neq a'\)이면 \(f(a) \neq f(a')\)”을 보인다. \(a, a' \in \mathbb{R}\)이고 \(a \neq a'\)이라 하자. 실수의 삼분법에 의해 \(a < a'\)이거나 \(a' < a\)이다. 두 경우는 \(a\)와 \(a'\)의 이름을 바꾸면 서로 옮겨 가므로, WLOG \(a < a'\)이라 하자.

가정(모든 \(x < y\)에 대해 \(f(x) < f(y)\))에 \(x = a\), \(y = a'\)을 대입하면 \(f(a) < f(a')\)이다. 특히 \(f(a) \neq f(a')\)이다(같은 수는 자기 자신보다 작을 수 없다). 따라서 대우 표현이 성립하고, \(f\)는 단사이다. \(\blacksquare\)

복기. 고교에서 “증가함수는 일대일”이라고 외운 사실의 증명이다. 이 한 정리 덕에 \(2x + 1\), \(x^3\), \(2^x\)의 단사성이 개별 계산 없이 처리된다. 42주차 문제 12(“증가함수의 합성은 증가함수”)와 결합하면 “증가함수의 합성은 단사”가 따라 나온다.

문제 14#

접근. 결론 “차가 \(n\)의 배수인 두 수가 존재한다”는 25주차 예제 2.2에 의해 “나머지가 같은 두 수가 존재한다”와 같은 말이고, 그것은 다시 “나머지로 보내는 함수가 단사가 아니다”와 같은 말이다. 그 단사 불가는 §1.8의 첫 항목이 보장한다.

풀이. \(n \ge 1\)이라 하고, 주어진 정수를 \(a_1, a_2, \dots, a_{n+1}\)이라 하자.

먼저 두 수가 같은 경우를 떼어 낸다. 어떤 \(i \neq j\)에 대해 \(a_i = a_j\)이면 차가 \(a_i - a_j = 0\)이고 \(0 = n \cdot 0\)이므로 \(n \mid 0\)이다(2주차 정의 2.1). 이 경우에는 결론이 곧바로 성립한다. 그러므로 이하에서는 \(n+1\)개가 모두 서로 다르다고 해도 좋고, 그러면 집합 \(A = \{a_1, \dots, a_{n+1}\}\)에 대해 \(|A| = n + 1\)이다.

나눗셈 정리(17주차에서 인정하고 쓰기로 한 사실, 증명은 33주차)에 의해 각 \(a_i\)를 \(n\)으로 나눈 나머지가 유일하게 정해지므로, 함수

\[ r : A \to \{0, 1, \dots, n-1\}, \qquad r(a_i) = (a_i \text{를 } n \text{으로 나눈 나머지}) \]

가 잘 정의된다. 공역의 크기는 \(n\)이고 정의역의 크기는 \(n + 1\)이다.

\(r\)가 단사라고 하면 서로 다른 \(n+1\)개의 입력이 서로 다른 \(n+1\)개의 출력을 가져야 하므로 \(n + 1 \le n\)이 되어 모순이다. 따라서 \(r\)는 단사가 아니고, \(i \neq j\)이면서 \(r(a_i) = r(a_j)\)인 두 첨자가 존재한다.

즉 \(a_i\)와 \(a_j\)를 \(n\)으로 나눈 나머지가 같다. 25주차 예제 2.2에 의해 \(a_i \equiv a_j \pmod n\)이고, 합동의 정의에 의해 \(n \mid (a_i - a_j)\)이다. 따라서 차가 \(n\)의 배수인 두 수가 존재한다. \(\blacksquare\)

검산. \(n = 3\)이고 네 수 \(5, 8, 11, 20\)을 잡으면 나머지가 모두 2로 겹치고, 실제로 \(8 - 5 = 3\)이 3의 배수다.

복기. 비둘기집 논증의 표준 절차는 세 단계다 — ① 함수를 만든다(무엇이 비둘기이고 무엇이 집인지 정한다) ② 정의역이 공역보다 큼을 확인한다 ③ 단사가 아니라는 결론을 문제의 언어로 번역한다. 26주차 문제 19의 양말 문제도 같은 세 단계였고, 달라진 것은 ①의 함수뿐이다.

문제 15#

접근. (a)는 세기 문제다 — 출력 후보가 5개, 4개, 3개로 줄어든다. (b)와 (c)는 방향이 반대이므로 무너지는 이유도 반대다 — (b)는 출력의 가짓수가, (c)는 서로 다른 출력을 놓을 자리가 모자란다.

풀이. (a) \(A = \{a_1, a_2, a_3\}\)이라 하자. 단사를 정하는 것은 \(f(a_1), f(a_2), f(a_3)\)을 서로 다르게 정하는 것과 같다. \(f(a_1)\)의 후보는 \(B\)의 5개, \(f(a_2)\)는 \(f(a_1)\)을 뺀 4개, \(f(a_3)\)은 앞의 둘을 뺀 3개다. 곱셈 원리에 의해 \(5 \times 4 \times 3 = 60\)개다(12주차 문제 19와 같은 계산이다).

(b) \(A \to B\) 함수 \(f\)의 치역은 \(f(a_1), f(a_2), f(a_3)\)의 셋 이하로 이루어지므로 \(|f(A)| \le 3\)이다. 그런데 \(|B| = 5\)이므로 \(f(A) \neq B\)이고, 치역이 공역을 덮지 못한다. 따라서 전사가 존재할 수 없다.

(c) \(g : B \to A\)가 단사라고 하자. 그러면 \(B\)의 서로 다른 5개 원소가 서로 다른 5개의 출력을 가져야 하는데 출력이 살 수 있는 곳은 \(|A| = 3\)개뿐이므로 모순이다. 따라서 \(B \to A\) 단사는 존재하지 않는다(비둘기집 원리 — 비둘기 5마리, 집 3개). \(\blacksquare\)

복기. 세 항목은 §1.8의 네 항목 중 셋을 답안 형태로 옮긴 것이다. (b)와 (c)를 한 문장으로 요약하면 “정의역이 작으면 전사가 불가능하고, 정의역이 크면 단사가 불가능하다”이다. 헷갈리면 크기가 큰 쪽이 어디인지부터 다시 적는다.

문제 16#

접근. 먼저 여섯 값을 계산해 출력의 순서를 눈으로 본다. 단사 증명의 첫 관문은 “출력이 같으면 두 입력의 홀짝이 같다”를 부호로 보이는 것이다 — 짝수 입력의 출력은 양수, 홀수 입력의 출력은 0 이하이므로 두 무리가 겹치지 않는다. 전사는 목표 정수의 부호로 케이스를 나눠 증인을 각각 제작한다.

풀이. 값 계산: \(f(1) = -\frac{1-1}{2} = 0\), \(f(2) = \frac22 = 1\), \(f(3) = -\frac{3-1}{2} = -1\), \(f(4) = \frac42 = 2\), \(f(5) = -\frac{5-1}{2} = -2\), \(f(6) = \frac62 = 3\)이다. 출력은 \(0, 1, -1, 2, -2, 3, \dots\)의 순서로 정수를 훑는다.

(단사) \(a, a' \in \mathbb{N}\)이고 \(f(a) = f(a')\)이라 하자. 먼저 \(a\)와 \(a'\)의 홀짝이 같음을 보인다. \(a\)가 짝수이면 \(a \ge 2\)이므로 \(f(a) = \frac a2 \ge 1 > 0\)이고, \(a\)가 홀수이면 \(a \ge 1\)이므로 \(f(a) = -\frac{a-1}{2} \le 0\)이다. 즉 짝수 입력의 출력은 양수이고 홀수 입력의 출력은 0 이하이므로, 두 입력의 홀짝이 다르면 출력이 같을 수 없다. 가정에서 출력이 같으므로 \(a\)와 \(a'\)의 홀짝은 같다.

경우 1: 둘 다 짝수. 그러면 \(\frac a2 = \frac{a'}2\)이고, 양변에 2를 곱하면 \(a = a'\)이다. 경우 2: 둘 다 홀수. 그러면 \(-\frac{a-1}{2} = -\frac{a'-1}{2}\)이고, 양변에 \(-2\)를 곱하면 \(a - 1 = a' - 1\), 곧 \(a = a'\)이다. 두 경우가 전체를 덮고 어느 경우든 \(a = a'\)이므로 \(f\)는 단사이다.

(전사) \(m \in \mathbb{Z}\)라 하자. 두 경우로 나눠 증인을 제작한다. \(m > 0\)이면 \(n = 2m\)을 잡는다. \(m \ge 1\)이므로 \(n = 2m \ge 2\)이고 \(n \in \mathbb{N}\)이며, \(n\)은 짝수이므로 \(f(n) = \frac{2m}{2} = m\)이다. \(m \le 0\)이면 \(n = 1 - 2m\)을 잡는다. \(-2m \ge 0\)이므로 \(n \ge 1\)이고 \(n \in \mathbb{N}\)이며, \(n = 2(-m) + 1\)은 홀수이므로 \(f(n) = -\frac{(1-2m)-1}{2} = -\frac{-2m}{2} = m\)이다. 어느 경우든 \(f(n) = m\)인 \(n \in \mathbb{N}\)이 존재하므로 \(f\)는 전사이다. 단사이고 전사이므로 전단사이다. \(\blacksquare\)

검산. \(m = 3\)이면 증인은 \(n = 6\)이고 \(f(6) = 3\)이다. \(m = -2\)이면 증인은 \(n = 1 - 2(-2) = 5\)이고 \(f(5) = -2\)이다.

복기. 정의가 케이스로 주어진 함수는 증명도 케이스로 간다. 다만 단사 증명에서 케이스를 나누기 전에 “두 입력의 홀짝이 같다”를 먼저 확보해야 한다 — 그것을 건너뛰면 “\(a\)는 짝수, \(a'\)은 홀수”인 조합이 처리되지 않은 채 남는다. 이 함수는 \(\mathbb{N}\)과 \(\mathbb{Z}\) 사이의 전단사이며, 48주차에서 “자연수와 정수의 개수가 같다”의 증인으로 그대로 쓰인다.

문제 17#

접근. 단사라는 가정에서 치역의 크기를 먼저 계산한다. 단사이면 서로 다른 입력이 서로 다른 출력을 가지므로 치역의 크기가 정의역의 크기와 같다. 그다음 “공역의 부분집합인데 크기가 같다”는 상황을 유한집합의 성질로 닫는다. 무한 사례는 서식대로 세 줄이면 된다.

풀이. (유한에서 단사 \(\Rightarrow\) 전사) \(|A| = |B| = n\)이고 \(f : A \to B\)가 단사라 하자. 치역 \(f(A) = \{f(a) : a \in A\}\)의 원소를 세면, 단사이므로 서로 다른 입력의 출력이 서로 다르고 따라서 출력의 가짓수가 입력의 개수와 같다 — \(|f(A)| = |A| = n\)이다. 한편 \(f(A) \subseteq B\)이고 \(|B| = n\)이다. 유한집합에서 크기가 같은 부분집합은 전체 자신이므로(도전 절 상자의 사실 ②) \(f(A) = B\)이다. 정의 41.2의 동치 표현에 의해 \(f\)는 전사이다. \(\blacksquare\)

(무한에서 무너짐) \(f : \mathbb{N} \to \mathbb{N}\), \(f(n) = 2n\)을 보자. 단사: \(f(a) = f(a')\)이면 \(2a = 2a'\)이고 양변을 2로 나누면 \(a = a'\)이다. 전사가 아님: \(b_0 = 1\)을 잡는다. \(f(n) = 1\)이면 \(2n = 1\)이므로 \(2 \mid 1\)인데, 22주차 보조 명제 22.A에 의해 1의 약수는 \(1\)과 \(-1\)뿐이고 \(2\)는 그중 어느 것도 아니므로 그런 \(n\)은 없다. 따라서 단사이지만 전사가 아니다. \(\blacksquare\)

복기. 무너진 이유는 “크기가 같은 부분집합은 전체”라는 사실이 유한집합의 성질이기 때문이다. 짝수 전체는 \(\mathbb{N}\)의 진부분집합이면서, 48주차에서 정의할 의미로는 \(\mathbb{N}\)과 크기가 같다. 유한 세계에서 참인 정리를 무한으로 가져갈 때는 그 정리가 유한성의 어느 조각에 기대고 있었는지 확인해야 한다 — 48주차 문제 18이 정확히 이 실수를 다룬다.

문제 18#

접근. 답안의 첫 문장과 마지막 문장을 정의 41.1의 조건문과 나란히 놓는다. 답안은 “\(a = a'\)”을 가정하고 “\(f(a) = f(a')\)”을 결론으로 삼았는데, 정의는 그 반대 방향을 요구한다. §1.3의 조각 삭제 실험 2에서 이미 해부한 문장이다.

풀이. 이 답안이 증명한 명제는 “\(a = a'\)이면 \(f(a) = f(a')\)”이다. 이것은 정의 41.1의 조건문 “\(f(a) = f(a')\)이면 \(a = a'\)”의 역이며, 두 조건문은 서로 동치가 아니다(9주차).

게다가 답안이 증명한 명제는 \(f\)가 무엇이든 자동으로 참이다 — 40주차 정의 40.1의 유일성 조각에 의해 한 입력의 출력은 하나뿐이므로, 입력이 같으면 출력은 언제나 같다. 따라서 이 답안은 어떤 함수에 대해서도 그대로 적을 수 있고, \(x^2\)처럼 단사가 아닌 함수에 대해서도 똑같이 “증명”이 완성된다. 아무 함수도 걸러 내지 못하는 논증은 단사성의 근거가 될 수 없다.

올바른 증명은 방향을 바꿔 쓰는 것이다: “\(a, a' \in \mathbb{R}\)이고 \(f(a) = f(a')\)이라 하자. 즉 \(2a + 1 = 2a' + 1\)이다. 양변에서 1을 빼면 \(2a = 2a'\)이고, 양변을 2로 나누면 \(a = a'\)이다. 따라서 \(f\)는 단사이다.”

복기. 결함을 지적할 때는 “방향이 반대다”에서 멈추지 않고, 그 답안이 실제로 증명한 명제를 적고 그것이 아무것도 구별하지 못함까지 보이는 것이 완결이다. \(x^2\)에 그대로 대입해 보는 검사가 가장 빠른 진단이다. 42주차 문제 18에서 반대 유형 — 대우 표현으로 옳게 썼지만 근거를 명시하지 않은 답안 — 을 다룬다.

문제 19#

접근. 각 \(b \in B\)에 대해 “\(f(a) = b\)인 \(a\)들”의 개수를 세는 관점으로 바꿔 읽는다. 이 개수를 \(b\)의 원상의 개수라 부르면, 세 정의가 각각 그 개수에 어떤 제한을 거는지가 한 줄로 정리된다.

풀이. 각 \(b \in B\)에 대해 \(P_b = \{a \in A : f(a) = b\}\)라 하자.

전사 \(\iff\) 모든 \(b\)에 대해 \(P_b\)가 비어 있지 않다, 곧 원소가 적어도 하나다. 정의 41.2가 “존재한다”를 요구하는 것이 바로 이것이다.

단사 \(\iff\) 모든 \(b\)에 대해 \(P_b\)의 원소가 많아야 하나다. 실제로, \(f\)가 단사이고 \(a, a' \in P_b\)이면 \(f(a) = b = f(a')\)이므로 \(a = a'\)이어서 \(P_b\)에는 서로 다른 두 원소가 있을 수 없다. 역으로 모든 \(P_b\)가 원소를 많아야 하나 가지면, \(f(a) = f(a') = b\)인 \(a, a'\)은 둘 다 \(P_b\)에 속하므로 \(a = a'\)이고 \(f\)는 단사다.

전단사 \(\iff\) 모든 \(b\)에 대해 \(P_b\)의 원소가 정확히 하나다. 이것이 26주차의 \(\exists!\) — 존재(전사)와 유일(단사)의 2단 의무 — 그 자체다.

성질

각 \(b\)의 원상 개수

26주차의 언어

전사

적어도 하나

존재

단사

많아야 하나

유일

전단사

정확히 하나

\(\exists!\)

복기. 26주차에서 존재와 유일을 두 의무로 나눠 증명했던 구조가, 여기서 전사와 단사라는 두 성질로 갈라져 재등장했다. 전단사이면 모든 \(b\)의 원상이 정확히 하나이므로 “\(b\)에 그 유일한 원상을 대응시키는” 규칙이 함수가 된다 — 그것이 43주차의 역함수이고, 43주차 정리의 증명이 이 문제의 관점을 그대로 쓴다.

문제 20#

접근. (a)는 §1.4에서 확인한 내용을 두 문장으로 압축한다 — 등식은 변형 규칙이 있고 부등은 없다. (b)는 정의 41.2와 40주차 예제 2.2의 (\(\supseteq\)) 방향을 나란히 놓고 같은 문장임을 지적한다.

풀이. (예시 답안)

(a) 정의의 직관적 표현 “서로 다른 입력은 서로 다른 출력”을 그대로 증명하려면 “\(a \neq a'\)이라 하자”에서 출발해야 하는데, \(\neq\)에는 풀어 쓸 정의 꼴이 없어 다음 줄을 쓸 수 없다(19주차에서 본 신호다). 대우 꼴 “\(f(a) = f(a')\)이면 \(a = a'\)”은 등식에서 출발하므로 양변 연산과 인수분해 같은 대수 변형을 그대로 쓸 수 있고, 그래서 이쪽을 표준 서식으로 삼는다.

(b) 전사의 정의 “모든 \(b \in B\)에 대해 \(f(a) = b\)인 \(a\)가 존재한다”는 “\(B \subseteq f(A)\)”를 원소로 풀어 쓴 문장 그 자체이므로, 치역 상등 증명의 (\(\supseteq\)) 방향과 글자 그대로 같은 작업이다.

복기. 두 물음 모두 “정의를 다른 표현으로 바꿔 적고 무엇이 달라지는지 본다”는 같은 작업이다. 서술 문제에서 점수를 만드는 것은 결론이 아니라 두 표현을 나란히 놓는 문장이다. (a)의 예외는 문제 13이며, 등식을 풀 수 없는 함수에서는 대우 표현이 오히려 실용적임을 잊지 않는다.

다음 주 예고: 함수를 이어 붙이는 연산 — 합성 \(g \circ f\)를 다룬다. 단사\(\cdot\)전사가 합성에서 보존된다는 정리를 증명하고, 거꾸로 “합성이 단사이면 앞 함수가 단사, 합성이 전사이면 뒤 함수가 전사”라는 역추적 정리도 세운다. 고1에서 계산으로만 다루던 \(f(g(x))\)가 구조를 논하는 언어로 승격된다.