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

:::{admonition} 이 주의 길잡이
:class: keybox

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

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

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

## 이번 주 목표

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

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

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

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

:::{admonition} 답
:class: quotebox dropdown

**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주차는 함수를 세 정보로 기술했다: 정의역, 공역, 치역. 이 세 정보만 가지고 아래 두 물음을 밀어붙여 보자.

:::{admonition} 시도 — 세 정보만으로
:class: quotebox

함수 $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주차의 세 정보 어디에도 기록되지 않는다.

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

:::{admonition} 답
:class: quotebox dropdown

"서로 다른 두 입력이 같은 출력을 가진다." $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}$ |

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

:::{admonition} 답
:class: quotebox dropdown

$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) [백지 암기 대상]

:::{container} quotebox
$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 — 화살표를 뒤집으면.**

:::{container} quotebox
**확인 3.** 뒤집은 문장 "$a = a'$이면 $f(a) = f(a')$"은 어떤 함수에서 성립하는가. 40주차 정의 40.1의 어느 조각이 이것을 보장하는가.
:::

:::{admonition} 답
:class: quotebox dropdown

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

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

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

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

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

해부하는 자리다.
:::

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

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

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

:::{admonition} 답
:class: quotebox dropdown

쓸 것이 없다. "$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}$ |

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

:::{admonition} 답
:class: quotebox dropdown

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

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

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

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

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

얻는다.
:::

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

:::{container} quotebox
$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$의 치역"으로 읽는다.

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

:::{admonition} 답
:class: quotebox dropdown

$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\}$로 선언하는 이유가 여기에 있다.

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

:::{admonition} 답
:class: quotebox dropdown

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

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

"그 $a$가 정말 $b$를 만드는가"라는 요구가 확인되지 않은 채 남는다. 26주차의

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

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

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

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

:::{container} quotebox
$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$가 없음을 논증한다 |

:::{container} quotebox
**확인 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$은 전사가 아니다"
:::

:::{admonition} 답
:class: quotebox dropdown

(가) 단사 반증 — 쌍 $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에서

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

:::{container} quotebox
**확인 9.** $|A| = 5$, $|B| = 3$일 때 $A \to B$ 단사가 존재할 수 없는 이유를 "입력"과 "출력"이라는 낱말로 적어 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

단사라면 서로 다른 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'$"의 계산으로 바꿔 적어야 근거가 된다.

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

:::{admonition} 답
:class: quotebox dropdown

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

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

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

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

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

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