41주차 — 단사, 전사, 전단사

내용

41주차 — 단사, 전사, 전단사#

이 주의 길잡이

핵심 문장: 단사는 “서로 다른 입력을 뭉개지 않는다”, 전사는 “공역을 남김없이 쓴다” — 서로 다른 두 조건이고, 각각 고유한 증명 서식을 가진다.

이 주의 위치: 50주 과정의 41주차. 40주차의 치역 계산이 전사 증명이라는 이름을 얻고, 42주차(합성)\(\cdot\)43주차(역함수)\(\cdot\)48주차(무한의 크기 비교)가 쓸 부품이 여기서 만들어진다.

원서 대응: BoP(Book of Proof) 12.2 (Injective and Surjective Functions). 원서 없이 읽을 수 있다.

이번 주 목표#

단사\(\cdot\)전사\(\cdot\)전단사의 정의를 백지에 쓰고, 증명 서식 4종(단사 증명 / 단사 반증 / 전사 증명 / 전사 반증)을 구분해 쓸 수 있다.
40주차의 치역 계산이 전사 증명으로 승격되는 지점을 확인한다.
유한집합에서 크기와 단사\(\cdot\)전사의 관계를 비둘기집 원리까지 포함해 정리한다.
정의역과 공역을 손보면 같은 식의 함수가 다른 성질을 갖는다는 것을 예로 확인한다 (40주차 문제 10의 완성).

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

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

함수의 정의를 \(\exists!\) 조건까지 포함해 백지에 쓰시오.
40주차 예제 2.2에서 치역의 (\(\supseteq\)) 방향 증명이 무엇을 하는 작업이었는지 한 문장으로 쓰시오.
\(f : \mathbb{R} \to \mathbb{R}\), \(f(x) = x^2\)의 치역을 쓰고, 공역과 같은지 판정하시오.

답

1. \(f\)가 \(A\)에서 \(B\)로의 함수라는 것은, \(f \subseteq A \times B\)이고 모든 \(a \in A\)에 대해 \((a, b) \in f\)인 \(b \in B\)가 정확히 하나 존재한다(\(\exists!\))는 뜻이다(40주차 정의 40.1). “적어도 하나”(전체성)와 “많아야 하나”(유일성)가 함께 요구되며, 정의역 \(A\)와 공역 \(B\)는 규칙과 더불어 함수 선언의 일부다.

2. 목표 집합의 원소 \(y\)를 아무거나 잡고 \(f(k) = y\)인 입력 \(k\)를 제작해 보이는 작업이다. 곧 존재 증명이며, 제작한 \(k\)가 정의역에 속하는지와 대입하면 실제로 \(y\)가 나오는지의 두 검증까지가 완결이다(26주차).

3. 치역은 \(f(\mathbb{R}) = \{x^2 : x \in \mathbb{R}\} = [0, \infty)\)이고, 공역은 \(\mathbb{R}\)이다. 둘은 같지 않다 — 음수는 어떤 실수의 제곱도 아니므로 출력되지 않는다. 치역이 공역보다 작을 수 있다는 이 판정이 §1.5와 정의 41.2에서 “전사”라는 이름을 얻는다.

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

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

유형 1 — 방향을 합쳐서 답한다. “치역이 공역과 같음을 보이는 작업”이라고

적는다. 큰 그림은 맞다. 다만 물음은 두 방향 중 (\(\supseteq\)) 한쪽만 떼어 물었다. (\(\subseteq\))는 출력이 그 꼴임을 확인하는 방향이고, (\(\supseteq\))는 목표 집합의 원소 \(y\)를 아무거나 잡고 그것을 출력하는 입력을 만드는 방향이다. 두 방향이 하는 일이 다르다는 것이 이번 주 정의 두 개의 갈림길이다.

유형 2 — 방정식을 푼 것으로 답한다. “\(y = 2n + 1\)을 \(n\)에 관해 푼 것”이라고

적는다. 계산은 정확하고, 실제로 증인은 그 계산에서 나온다. 빠진 것은 두 검증이다 — 나온 \(n = \frac{y-1}{2}\)이 정의역에 속하는지, 그리고 대입했을 때 실제로 \(y\)가 나오는지. 26주차의 존재 증명은 제작 + 두 검증까지가 완결이다.

유형 3 — 검증만 적는다. “\(n = \frac{y-1}{2}\)을 넣으면 \(y\)가 나온다”라고

적는다. 검증은 옳다. 빠진 것은 그 \(n\)이 어디서 왔는가이다. 제작(연습장에서 방정식 풀기)과 검증(답안에 적는 대입)은 별개의 단계이며, 답안에 적는 것은 검증이지만 그 앞에 “\(n = \frac{y-1}{2}\)을 잡자”라는 제시 문장이 반드시 있어야 한다. 이번 주 전사 증명 서식이 그 두 단계를 고정한다.

개념 — 뭉개지 않음과 빠뜨리지 않음#

1 40주차의 도구만으로 답할 수 없는 물음#

40주차는 함수를 세 정보로 기술했다: 정의역, 공역, 치역. 이 세 정보만 가지고 아래 두 물음을 밀어붙여 보자.

시도 — 세 정보만으로

함수 \(f : \mathbb{Z} \to \mathbb{Z}\), \(f(n) = 3n - 1\)에 대해

물음 A: 출력 값 하나를 알려 주면 입력을 되찾을 수 있는가.

물음 B: 공역의 모든 정수가 실제로 출력되는가.

손에 있는 것: 정의역 \(\mathbb{Z}\), 공역 \(\mathbb{Z}\), 치역 \(\{3k - 1 : k \in \mathbb{Z}\}\) (40주차 문제 8).

물음 B는 답이 나온다. 치역과 공역을 비교하면 된다 — \(0\)은 공역에 있지만 \(0 = 3k - 1\)을 만족하는 정수 \(k\)는 없으므로(\(3k = 1\)이면 \(3 \mid 1\)인데, 22주차 보조 명제 22.A에 의해 1의 약수는 \(1\)과 \(-1\)뿐이다), 치역은 공역보다 작다. 답은 “아니다”이며 새 개념이 필요 없었다.

물음 A에서 멈춘다. 치역은 “어떤 값이 출력되는가”의 목록일 뿐, 그 값이 몇 개의 입력에서 나오는지는 어디에도 적혀 있지 않다. 같은 도구로 \(h : \mathbb{Z} \to \mathbb{Z}\), \(h(n) = n^2\)을 보면 치역은 \(\{0, 1, 4, 9, \dots\}\)이고, 출력 \(4\)만으로는 입력이 \(2\)인지 \(-2\)인지 정할 수 없다. \(f\)와 \(h\)의 이 차이는 40주차의 세 정보 어디에도 기록되지 않는다.

확인 1. \(h(n) = n^2\)에서 복원이 실패한 지점을 “입력”과 “출력”이라는 낱말만 써서 한 문장으로 적어 보자: “서로 다른 두 입력이 \(\underline{\qquad}\).”

답

“서로 다른 두 입력이 같은 출력을 가진다.” \(2 \neq -2\)인데 \(h(2) = h(-2) = 4\)이다.

복원이 가능하다는 것의 반대말이 정확히 이 현상이므로, 이번 주의 첫 정의는

이 현상을 금지하는 조건이 된다. 물음 B 쪽에는 새 개념이 필요 없었고, 이번

주에는 그 비교에 이름만 붙는다 — 두 물음이 두 정의로 갈라진다.

2 표를 채워 조건을 찾아내기 — 단사#

\(A = \{1, 2, 3\}\), \(B = \{x, y, z\}\) 위의 함수 넷을 나란히 놓는다. 셋째 열에는 “\(f(a) = f(a')\)이면서 \(a \neq a'\)인 쌍”이 있으면 그 쌍을, 없으면 “없다”를 적는다.

함수	출력 목록	같은 출력을 갖는 서로 다른 입력	출력만으로 입력 복원
\(f_1 = \{(1,x),(2,y),(3,z)\}\)	\(x, y, z\)	없다	가능
\(f_2 = \{(1,x),(2,x),(3,y)\}\)	\(x, x, y\)	\(\underline{\quad(1)\quad}\)	\(\underline{\quad}\)
\(f_3 = \{(1,z),(2,y),(3,x)\}\)	\(\underline{\quad(2)\quad}\)	\(\underline{\quad}\)	\(\underline{\quad}\)
\(f_4 = \{(1,y),(2,y),(3,y)\}\)	\(\underline{\quad(3)\quad}\)	\(\underline{\quad}\)	\(\underline{\quad}\)

확인 2. 빈칸 (1)(2)(3)과 나머지 칸을 채우고, 셋째 열과 넷째 열이 어떤 관계인지 한 문장으로 적어 보자.

답

\(f_2\): 셋째 열은 \(1\)과 \(2\) (둘 다 \(x\)로 간다), 넷째 열은 “불가능”.

\(f_3\): 출력 목록 \(z, y, x\), 셋째 열은 “없다”, 넷째 열은 “가능”.

\(f_4\): 출력 목록 \(y, y, y\), 셋째 열은 \(1\)과 \(2\) (또는 \(1\)과 \(3\), \(2\)와 \(3\)),

넷째 열은 “불가능”.

두 열은 언제나 반대로 움직인다 — 같은 출력을 갖는 서로 다른 입력이 하나라도

있으면 복원은 불가능하고, 하나도 없으면 복원이 가능하다. 복원 가능성이라는

말은 검사하기 어렵지만, 셋째 열의 조건은 등식 하나로 적을 수 있다.

이 관찰에 이름을 붙인다. 식 자체에 새로운 것은 없다 — 방금 셋째 열에서 한 판정을 문장으로 굳혔을 뿐이다.

정의 41.1 — 단사 (injective, one-to-one) [백지 암기 대상]#

\(f : A \to B\)가 단사라는 것은, 모든 \(a, a' \in A\)에 대해

\(f(a) = f(a')\)이면 \(a = a'\)이라는 뜻이다.

대우 표현으로는, 모든 \(a, a' \in A\)에 대해 \(a \neq a'\)이면 \(f(a) \neq f(a')\)이다.

“\(f\)는 단사이다”는 “\(f\)는 일대일이다”로도 읽는다. 영어 one-to-one의 번역이다. 뒤에 나오는 일대일 대응(정의 41.3)은 다른 말이므로, 우리말로 읽을 때 “일대일”과 “일대일 대응”을 섞지 않는다.

예. 정의로 위 표의 네 함수를 판정하면, \(f_1\)과 \(f_3\)은 단사이고, \(f_2\)는 \(f_2(1) = f_2(2) = x\)인데 \(1 \neq 2\)이므로, \(f_4\)는 \(f_4(1) = f_4(2) = y\)인데 \(1 \neq 2\)이므로 각각 단사가 아니다.

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

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

조각	하는 일	증명에서의 역할
“모든 \(a, a' \in A\)에 대해”	검사 범위의 선언	증명은 임의의 한 쌍을 문자로 잡고 시작한다 — 특정 값 한 쌍의 확인으로는 끝나지 않는다
“\(f(a) = f(a')\)이면”	출발점 제공	등식이므로 대수 계산이 시작된다 — 이 조각이 서식의 첫 문장이 된다
“\(a = a'\)”	도착점 지정	계산이 도달해야 할 꼴 — 입력이 복원되었다는 뜻

조각 삭제 실험 1 — “모든”을 지우면. “어떤 \(a, a'\)에 대해 \(f(a) = f(a')\)이면 \(a = a'\)”으로 약화하면 \(h(n) = n^2\)도 단사가 된다: \(a = a' = 1\)인 쌍에서 \(h(1) = h(1)\)이고 \(1 = 1\)이므로 조건이 만족된다. 어떤 함수도 걸러 내지 못하는 조건은 아무것도 정의하지 못한다.

조각 삭제 실험 2 — 화살표를 뒤집으면.

확인 3. 뒤집은 문장 “\(a = a'\)이면 \(f(a) = f(a')\)”은 어떤 함수에서 성립하는가. 40주차 정의 40.1의 어느 조각이 이것을 보장하는가.

답

모든 함수에서 성립한다. 40주차 정의 40.1의 유일성 조각(“한 입력에 출력이

하나”)이 곧 “같은 입력에는 같은 출력”이기 때문이다. 즉 뒤집은 문장은 함수라면

무조건 참이므로 아무 함수도 걸러 내지 못한다. 단사의 정의는 그 역방향

“\(f(a) = f(a')\)이면 \(a = a'\)”이고, 조건문과 그 역은 별개의 명제다(9주차).

답안에서 이 두 방향을 바꿔 쓰는 경우가 많고, 문제 18이 그 답안을 실제로

해부하는 자리다.

4 왜 등식 서식을 표준으로 쓰는가#

정의 41.1은 두 표현을 함께 제시했다. 뜻이 더 직관적인 쪽은 대우 표현(“서로 다른 입력은 서로 다른 출력”)인데, 증명에서 표준으로 쓰는 쪽은 등식 표현이다.

확인 4. “\(a \neq a'\)이라 하자”로 증명을 시작하면 다음 줄에 무엇을 쓸 수 있는가. \(f(n) = 3n - 1\)로 실제로 시도해 보자.

답

쓸 것이 없다. “\(a \neq a'\)”에는 풀어 쓸 정의 꼴이 없고, \(3a - 1 \neq 3a' - 1\)을

목표로 삼아도 부등을 변형하는 규칙이 손에 없다(19주차에서 본 신호와 같다).

반면 “\(3a - 1 = 3a' - 1\)이라 하자”로 시작하면 양변에 1을 더하고 3으로 나누는

등식 변형이 곧바로 가능하다. 대부분의 함수에서 “\(f(a) = f(a')\)”은 **풀 수 있는

방정식**이고 “\(f(a) \neq f(a')\)”은 계산의 출발점이 되지 못한다 — 그래서 정의를

등식 꼴로 적어 둔다. 다만 유한 함수나 증가함수처럼 등식을 풀 수 없고 순서

정보만 있는 경우에는 대우 표현이 오히려 자연스럽다 (문제 13).

5 표를 다시 채워 — 전사#

같은 네 함수를 이번에는 공역 쪽에서 본다. 넷째 열에는 “공역의 원소 중 출력되지 않는 것”을 적는다.

함수	출력 목록	치역	출력되지 않는 공역 원소
\(f_1 = \{(1,x),(2,y),(3,z)\}\)	\(x, y, z\)	\(\{x, y, z\}\)	없다
\(f_2 = \{(1,x),(2,x),(3,y)\}\)	\(x, x, y\)	\(\underline{\quad(1)\quad}\)	\(\underline{\quad}\)
\(f_3 = \{(1,z),(2,y),(3,x)\}\)	\(z, y, x\)	\(\underline{\quad(2)\quad}\)	\(\underline{\quad}\)
\(f_4 = \{(1,y),(2,y),(3,y)\}\)	\(y, y, y\)	\(\underline{\quad(3)\quad}\)	\(\underline{\quad}\)

확인 5. 빈칸을 채우고, “출력되지 않는 공역 원소가 없다”를 치역과 공역이라는 낱말로 다시 적어 보자.

답

\(f_2\): 치역 \(\{x, y\}\), 출력되지 않는 원소 \(z\).

\(f_3\): 치역 \(\{x, y, z\}\), 없다.

\(f_4\): 치역 \(\{y\}\), 출력되지 않는 원소 \(x\)와 \(z\).

“출력되지 않는 공역 원소가 없다”는 곧 “치역이 공역 전체와 같다”이다. 이것이

40주차 정의 40.2가 이미 다룰 수 있던 비교이고, 이번 주에는 그 비교가 이름을

얻는다.

정의 41.2 — 전사 (surjective, onto) [백지 암기 대상]#

\(f : A \to B\)가 전사라는 것은, 모든 \(b \in B\)에 대해

\(f(a) = b\)인 \(a \in A\)가 존재한다는 뜻이다.

동치 표현으로는, 치역과 공역이 같다 — 즉 \(f(A) = B\)이다.

“\(f\)는 전사이다”는 “\(f\)는 \(B\) 위로의 함수이다”로도 읽는다. 영어 onto의 번역이다. 기호 \(f(A)\)는 40주차 정의 40.2의 치역이며 “\(A\)의 상” 또는 “\(f\)의 치역”으로 읽는다.

확인 6. 정의의 앞 문장과 동치 표현 “\(f(A) = B\)”가 왜 같은 말인가. 집합 상등 증명의 두 방향 중 어느 쪽이 항상 참이라 생략되는가.

답

\(f(A) \subseteq B\)는 언제나 참이다 — 출력은 정의상 공역 안에 있다(40주차 정의 40.2).

따라서 상등 \(f(A) = B\)에서 실제로 확인할 것은 (\(\supseteq\)) 방향, 곧

\(B \subseteq f(A)\)뿐이고, 이것을 원소로 풀어 쓰면 “모든 \(b \in B\)에 대해

\(b \in f(A)\)”, 즉 “\(f(a) = b\)인 \(a\)가 존재한다”가 된다. 정의의 앞 문장이

정확히 그 원소 번역이다.

40주차의 승격. 40주차 예제 2.2에서 치역이 홀수 전체임을 보일 때, (\(\supseteq\)) 방향은 “홀수 \(y\)를 아무거나 잡고 \(f(k) = y\)인 \(k\)를 제작한다”였다. 그 작업이 그대로 전사 증명이다. 새로 배우는 기술이 아니라, 이미 하던 작업에 이름이 붙었다. 공역을 치역에 맞춰 선언하면 전사성은 함수를 설계하는 단계에서 확보할 수 있다 — 예제 2.2가 그 사례다.

6 정의 해부 — 전사의 조각들#

조각	하는 일	증명에서의 역할
“모든 \(b \in B\)에 대해”	검사 범위의 선언	증명은 임의의 \(b\)를 문자로 잡고 시작한다 — 값 하나를 확인해서는 끝나지 않는다
“\(a \in A\)가 존재한다”	제작 의무	증인 \(a\)를 식으로 제시하고 정의역에 속함을 확인한다 (26주차 2단 의무)
“\(f(a) = b\)인”	검증 조건	제작한 증인을 대입해 실제로 \(b\)가 나오는지 확인한다 — 증명의 마지막 줄

조각 삭제 실험 — 정의역 소속 확인을 빼면. 예제 2.2에서 공역만 바꾼 \(g_1 : \mathbb{R} - \{2\} \to \mathbb{R}\), \(g_1(x) = \frac{x+1}{x-2}\)을 전사라고 주장해 보자. 임의의 \(y \in \mathbb{R}\)에 대해 증인 \(x = \frac{2y+1}{y-1}\)을 제시하고 대입 계산으로 \(g_1(x) = y\)만 형식적으로 적으면 증명이 끝난 것처럼 보인다. 그러나 \(y = 1\)을 넣으면 제작식의 분모가 \(1 - 1 = 0\)이 되어 증인이 아예 존재하지 않는다. 실제로 \(g_1(x) = 1\)은 \(x + 1 = x - 2\), 곧 \(1 = -2\)를 뜻하므로 \(1\)은 어떤 입력으로도 만들 수 없고 \(g_1\)은 전사가 아니다. 소속 확인이 이 붕괴를 붙잡는 유일한 장치이며, 예제 2.2가 공역을 \(\mathbb{R} - \{1\}\)로 선언하는 이유가 여기에 있다.

확인 7. 전사 증명에서 증인을 제시한 뒤 반드시 확인해야 하는 두 가지를 적어 보자. 그중 하나를 빠뜨리면 무엇이 무너지는가.

답

① 증인이 정의역에 속한다 ② 증인을 대입하면 \(b\)가 나온다. ①을 빠뜨리면

정의되지 않은 대입을 한 셈이 되어 계산 자체가 무효가 되고, ②를 빠뜨리면

“그 \(a\)가 정말 \(b\)를 만드는가”라는 요구가 확인되지 않은 채 남는다. 26주차의

존재 증명이 요구한 두 검증이 그대로 여기서 회수된다.

7 전단사 — 두 조건을 겹쳐 보기#

단사와 전사는 서로를 함의하지 않는 독립된 두 조건이고, 네 조합이 모두 실재한다 — 예제 2.1은 단사이지만 전사가 아니고, 문제 11은 전사이지만 단사가 아니며, 예제 2.3의 \(\varphi\)는 둘 다 아니다. 둘이 동시에 성립하는 경우에만 따로 이름을 준다.

정의 41.3 — 전단사 (bijective) [백지 암기 대상]#

\(f : A \to B\)가 전단사라는 것은, \(f\)가 단사이면서 전사라는 뜻이다.

일대일 대응(one-to-one correspondence)이라고도 한다.

전단사는 \(A\)의 원소와 \(B\)의 원소를 하나씩 빠짐없이 짝짓는다. 13주차 문제 15에서 “\(k\)명을 뽑는 것”과 “\(n-k\)명을 남기는 것”을 대응시켜 개수를 비교한 논증이 이 개념의 비공식판이었고, 48주차에서는 무한집합의 크기 비교 도구가 된다.

네 가지 목표에 각각 고정된 서식이 있다. 이 표는 통째로 외운다.

증명 서식 4종 [백지 암기 대상]#

목표	서식
단사 증명	“\(f(a) = f(a')\)이라 하자.” \(\to\) 등식 계산 \(\to\) “따라서 \(a = a'\)이다.”
단사 반증	반례 쌍 제시: \(a \neq a'\)임을 확인하고, \(f(a) = f(a')\)임을 계산으로 확인한다 (두 검증 모두 — 29주차 완전 서식)
전사 증명	“\(b \in B\)라 하자.” \(\to\) 증인 \(a = (\text{제작식})\) 제시 \(\to\) ① \(a \in A\) 확인 ② \(f(a) = b\) 확인
전사 반증	도달 불가능한 \(b_0 \in B\) 하나를 제시하고, \(f(a) = b_0\)인 \(a\)가 없음을 논증한다

확인 8. 다음 각각에 어느 서식을 쓰는가. (가) “\(f : \mathbb{R} \to \mathbb{R}\), \(f(x) = x^2\)은 단사가 아니다” (나) “\(f : \mathbb{Z} \to \mathbb{Z}\), \(f(n) = n + 4\)는 전사이다” (다) “\(f : \mathbb{N} \to \mathbb{N}\), \(f(n) = 2n\)은 전사가 아니다”

답

(가) 단사 반증 — 쌍 \(1 \neq -1\)과 \(f(1) = f(-1) = 1\)의 두 검증.

(나) 전사 증명 — 임의의 \(y\)에 대해 증인 \(n = y - 4\)를 제시하고 두 검증.

(다) 전사 반증 — 도달 불가능한 \(b_0\)(예: 홀수 \(1 \in \mathbb{N}\)) 하나와 불가능성 논증.

세 문항 모두 정의역과 공역이 함께 적혀 있다 — 무대가 정해져야 판정이 정해지기

때문이다((다)는 문제 17 후반의 함수와 같다).

목표의 꼴이 서식을 정한다. 무엇을 보이려는지 먼저 적고 서식을 고르는 순서를

지키면, 시작 문장에서 헤매는 일이 없어진다.

8 유한집합에서 — 크기의 법칙#

기호 \(|A|\)는 집합 \(A\)의 원소 개수이며 “\(A\)의 크기”로 읽는다(3주차). \(|A| = m\), \(|B| = n\)인 유한집합에서 다음이 성립한다.

\(m > n\)이면 \(A \to B\) 단사가 존재할 수 없다. 이것이 비둘기집 원리다 —

비둘기 \(m\)마리가 집 \(n\)개에 들어가면 어떤 집에는 두 마리 이상이 들어간다 (26주차 문제 19에서 양말 문제로 처음 썼다).

\(m < n\)이면 \(A \to B\) 전사가 존재할 수 없다. 출력은 많아야 \(m\)종류인데

공역에는 \(n\)개가 있으므로 치역이 공역을 덮지 못한다.

\(m = n\)이면 단사이면 곧 전사이고(문제 17), 역도 성립하여 셋이 같은 말이 된다.

역방향(“전사이면 단사”)은 문제 17과 같은 세기 논증을 뒤집으면 되므로 연습으로 남긴다 — 전사이면 \(|f(A)| = n\)인데, 단사가 아니면 두 입력이 한 출력으로 뭉쳐 \(|f(A)| < n\)이 되어 어긋난다. 이 성질은 유한집합에서만 성립하며 무한집합에서는 무너진다 (문제 17 후반, 48주차).

\(A \to B\) 단사의 개수는 \(n(n-1)\cdots(n-m+1)\)이다 — 12주차 문제 19에서

“서로 다른 값을 배정하는 방법의 수”로 이미 센 것이다.

확인 9. \(|A| = 5\), \(|B| = 3\)일 때 \(A \to B\) 단사가 존재할 수 없는 이유를 “입력”과 “출력”이라는 낱말로 적어 보자.

답

단사라면 서로 다른 5개의 입력이 서로 다른 5개의 출력을 가져야 하는데,

출력이 살 수 있는 곳은 3개뿐이므로 5개의 서로 다른 출력을 놓을 자리가 없다.

따라서 어떤 두 입력은 같은 출력을 가질 수밖에 없고, 그 순간 단사가 무너진다.

문제 15(c)가 이 논증을 답안 형태로 쓰는 자리이고, 문제 14는 같은 논증을

나머지 집합에 적용한다.

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

칸의 개수는 늘지 않는다. ① 칸에 정의 세 개가 추가되고, ④ 칸에 40주차의 결과가 들어온다.

근거	내용	이번 주에는 이렇게 쓴다
① 정의	1~40주차의 정의 전부 + 정의 41.1, 41.2, 41.3	“단사” \(\leftrightarrow\) “\(f(a) = f(a')\)이면 \(a = a'\)” 사이를 번역한다
② 닫힘성	정수\(\cdot\)실수의 합\(\cdot\)차\(\cdot\)곱은 각각 정수\(\cdot\)실수이고, 0이 아닌 실수로 나눈 몫은 실수 (정수를 정수로 나눈 몫은 정수라는 보장이 없다)	제작한 증인이 정의역에 속함을 확인할 때 쓴다
③ 등식의 성질	대입 / 전개 / 묶기 / 양변 연산	단사 서식의 등식 계산 전체
④ 이미 증명한 명제	40주차 문제 17의 증인 제작, 16주차 문제 16(a), 16주차 부등식의 기본 성질 (W1), 16주차 §1.2의 삼분법, 22주차 문제 5(짝수이면서 홀수일 수 없음), 22주차 보조 명제 22.A(1의 약수는 \(1\)과 \(-1\)뿐), 20주차 문제 9(b)(양변에 정수를 곱해도 합동이 유지된다 — 예제 2.3의 잘 정의됨), 17주차 나눗셈 정리(인정하고 쓰는 사실, 증명은 33주차), 26주차 문제 19	예제 2.2의 전사 부분을 40주차 결과 인용으로 끝낸다

목록 밖의 것은 이번 주에도 근거가 되지 않는다. 특히 “그래프를 그려 보니 한 번씩만 만난다”는 관찰은 목록에 없다 — 같은 내용을 “\(f(a) = f(a')\)이라 하면 \(a = a'\)”의 계산으로 바꿔 적어야 근거가 된다.

확인 10. 다음 세 문장은 각각 허용되는가. 허용된다면 몇 번 근거인가. (가) “\(3a - 1 = 3a' - 1\)의 양변에 1을 더한다” (나) “\(\frac{2y+1}{y-1}\)은 \(y \neq 1\)이므로 실수이다” (다) “그래프가 증가하니까 단사이다”

답

(가) 허용 — 근거 ③ 등식의 성질.

(나) 허용 — 근거 ② 닫힘성(0이 아닌 실수로 나눈 값은 실수). 증인이 정의역에

속함을 확인하는 문장이다.

(다) 불허 — 그림은 목록에 없다. 같은 내용을 “모든 \(x < y\)에 대해

\(f(x) < f(y)\)이므로”라는 가정 문장에서 출발해 문제 13의 논증으로 적으면

근거 ④가 되어 허용된다. 내용이 아니라 꼴이 근거의 자격을 정한다.