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

## 예제 — 동치류의 증명을 함께 만들기

완성된 증명을 먼저 보이지 않는다. 설계부터 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다.

### 예제 2.1 — 핵심 정리의 증명

**명제.** $R$이 $A$ 위의 동치관계이면, 임의의 $x, y \in A$에 대해 $x\,R\,y \iff [x] = [y]$이다.

**설계 — 쓰기 전에 정하는 것.** 명제가 $\iff$ 꼴이므로 두 방향을 각각 증명한다 (25주차 서식). 방향마다 출발점과 도착점을 정의로 번역해 둔다.

| **방향** | **출발점 (가정)** | **도착점 (만들 것)** |
|---|---|---|
| ($\Rightarrow$) | $x\,R\,y$ | $[x] = [y]$ — 집합 상등 |
| ($\Leftarrow$) | $[x] = [y]$ — 집합 상등 | $x\,R\,y$ — 관계 문장 하나 |

:::{container} quotebox
**확인 11.** ($\Rightarrow$)의 도착점 $[x] = [y]$를 정의 27.1(상등의 판정 기준)로

번역하면 무엇을 보여야 하는가. 그리고 각 포함을 보이는 첫 문장은 어떤 꼴인가.
:::

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

$[x] \subseteq [y]$와 $[y] \subseteq [x]$ 둘 다 보여야 한다. 각 포함의 첫 문장은

원소 추적의 서식대로 "$z \in [x]$라 하자"이고, 이 문장은 정의 37.2에 의해 곧바로

"$x\,R\,z$이다"로 번역된다. 집합 차원의 목표가 원소 차원의 작업으로 내려온다.
:::

:::{container} quotebox
**확인 12.** ($\Leftarrow$)의 출발점은 집합의 상등뿐이다. 여기서 관계 문장 하나를

뽑아내려면, 먼저 어느 집합에 어떤 원소가 속한다는 사실부터 확보해야 하는가.
:::

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

$x \in [x]$를 먼저 확보한다(확인 5 — 반사성). 가정 $[x] = [y]$를 쓰면 $x \in [y]$가

되고, 이것은 정의 37.2에 의해 $y\,R\,x$이다. 목표는 $x\,R\,y$이므로 방향이 뒤집혀

있다 — 마지막에 대칭성이 한 번 필요하다. 반사성이 문을 열고 대칭성이 방향을 맞춘다.
:::

**1단계 — ($\Rightarrow$)의 첫 포함.** $x\,R\,y$를 가정하고 $[x] \subseteq [y]$를 보인다.

:::{container} quotebox
**확인 13.** 다음을 완성해 보자.

"$z \in [x]$라 하자. 정의 37.2에 의해 $\underline{\quad}$이다.

가정 $x\,R\,y$에 $\underline{\quad}$성을 적용하면 $y\,R\,x$이고,

$\underline{\quad}$성($y\,R\,x$와 $x\,R\,z$)에 의해 $y\,R\,z$이다.

따라서 정의 37.2에 의해 $z \in [y]$이다."
:::

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

$x\,R\,z$ / **대칭**성 / **추이**성.

손에 있는 것은 $x\,R\,y$와 $x\,R\,z$인데 둘 다 $x$가 앞자리에 있어 그대로는 이어지지

않는다. 대칭성으로 하나를 뒤집어 $y\,R\,x$로 만들면 $y \to x \to z$의 사슬이 되고,

추이성이 지름길 $y\,R\,z$를 준다. 그리고 $y\,R\,z$가 바로 $[y]$의 소속 조건이다.
:::

**2단계 — ($\Rightarrow$)의 둘째 포함.** 같은 가정에서 $[y] \subseteq [x]$를 보인다.

:::{container} quotebox
**확인 14.** 다음을 완성해 보자.

"$z \in [y]$라 하자. 정의 37.2에 의해 $\underline{\quad}$이다.

가정 $x\,R\,y$와 함께 $\underline{\quad}$성을 쓰면 $x\,R\,z$이므로 $z \in [x]$이다."

이 방향에도 대칭성이 필요한가.
:::

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

$y\,R\,z$ / **추이**성. 대칭성은 필요하지 않다 — 가정 $x\,R\,y$와 $y\,R\,z$가 이미

$x \to y \to z$의 사슬을 이루므로 추이성 한 번으로 끝난다.

두 포함이 겉보기에는 대칭적이지만 소비하는 부품이 다르다. 어느 줄에서 무엇을 썼는지

표시해 두는 습관이 문제 13의 진단을 가능하게 한다.
:::

**3단계 — ($\Leftarrow$).** 이번에는 $[x] = [y]$를 가정하고 $x\,R\,y$를 만든다.

:::{container} quotebox
**확인 15.** 다음을 완성해 보자.

"$[x] = [y]$라 가정하자. $\underline{\quad}$성에 의해 $x\,R\,x$이므로

정의 37.2에 의해 $x \in [x]$이다. 가정에 의해 $x \in \underline{\quad}$이고,

정의 37.2에 의해 $\underline{\quad}$이다. $\underline{\quad}$성에 의해 $x\,R\,y$이다."
:::

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

**반사**성 / $[y]$ / $y\,R\,x$ / **대칭**성.

$[y]$의 소속 조건은 "앞자리가 $y$"이므로 $x \in [y]$에서 나오는 것은 $y\,R\,x$다.

목표 $x\,R\,y$와 순서가 반대이므로 대칭성으로 마무리한다. 순서를 확인하지 않고

$x\,R\,y$를 곧바로 적는 경우가 많은데, 그러면 정의 37.2를 반대로 읽은 것이 된다.
:::

**완성본.** 방금 만든 세 덩어리를 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 "왜?"에 스스로 답해 본다.

| 증명의 한 줄 | 왜 이 줄을 쓰는가? |
|---|---|
| ($\Rightarrow$) $x\,R\,y$라 가정하자. 먼저 $[x] \subseteq [y]$를 보인다. $z \in [x]$라 하자. 정의 37.2에 의해 $x\,R\,z$이다. | $\iff$이므로 방향을 나눈다. 집합 상등의 목표를 정의 27.1로 포함 둘로 쪼개고, 소속을 관계 문장으로 번역한다(근거 ①). |
| 대칭성에 의해 $y\,R\,x$이고, 추이성($y\,R\,x$, $x\,R\,z$)에 의해 $y\,R\,z$이다. 따라서 $z \in [y]$이고, $[x] \subseteq [y]$이다. | 두 관계 문장의 $x$가 모두 앞자리라 이어지지 않는다 — 대칭성이 방향을 맞추고 추이성이 잇는다. |
| 다음으로 $[y] \subseteq [x]$를 보인다. $z \in [y]$라 하자. 그러면 $y\,R\,z$이고, 가정 $x\,R\,y$와의 추이성에 의해 $x\,R\,z$이다. 따라서 $z \in [x]$이다. | 이 방향은 사슬이 이미 $x \to y \to z$로 맞아 있어 추이성 한 번으로 닫힌다. |
| 양방향 포함이 성립하므로 $[x] = [y]$이다. | 정의 27.1을 인용하며 집합 상등을 선언한다(근거 ④). |
| ($\Leftarrow$) $[x] = [y]$라 가정하자. 반사성에 의해 $x\,R\,x$이므로 $x \in [x] = [y]$이다. | 가정이 집합 상등뿐이므로, 반사성으로 원소 하나를 확보해 가정을 쓸 자리를 만든다. |
| $x \in [y]$이므로 정의 37.2에 의해 $y\,R\,x$이고, 대칭성에 의해 $x\,R\,y$이다. 두 방향이 모두 증명되었으므로 $x\,R\,y \iff [x] = [y]$이다. $\blacksquare$ | $[y]$의 소속 조건은 앞자리가 $y$다 — 순서를 대칭성으로 맞추고 $\iff$의 종합을 선언한다. |

**세 성질이 전부 쓰였는지 확인.** 반사성은 ($\Leftarrow$)의 첫 줄, 대칭성은 ($\Rightarrow$)의 첫 포함과 ($\Leftarrow$)의 마지막 줄, 추이성은 ($\Rightarrow$)의 두 포함에서 쓰였다. 셋 중 하나라도 없으면 그 줄이 그대로 비고 정리가 무너진다 — 문제 13이 그 확인이다.

:::{container} quotebox
**확인 16.** 이 증명의 $R$에 $\equiv \pmod 3$을, $x$에 $1$을, $y$에 $4$를 넣어 읽어

보자. ($\Rightarrow$)의 첫 포함은 어떤 계산이 되는가.
:::

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

"$1 \equiv 4 \pmod 3$이라 하자. $z \in [1]$이라 하자. 즉 $1 \equiv z$이다.

대칭성에 의해 $4 \equiv 1$이고, 추이성에 의해 $4 \equiv z$이다. 따라서 $z \in [4]$이다."

$z = 7$을 넣으면 $1 \equiv 7$, $4 \equiv 1$, $4 \equiv 7$로 모든 줄이 성립한다.

증명의 어느 줄도 $R$이 합동이라는 사실을 쓰지 않았다 — 쓴 것은 세 성질이라는

자격뿐이므로, 같은 여섯 줄이 "같은 홀짝"에도 "원점에서 같은 거리"에도 그대로 작동한다.
:::

### 예제 2.2 — 따름정리: 같거나 서로소

**명제.** $R$이 $A$ 위의 동치관계일 때, $[x] \cap [y] \neq \emptyset$이면 $[x] = [y]$이다.

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

:::{container} quotebox
**확인 17.** 번역표를 채워 보자.

가정: $[x] \cap [y] \neq \emptyset$ $\to$ 공통 원소 $z$가 $\underline{\quad}$하고,

정의 37.2에 의해 $\underline{\quad}$이고 $\underline{\quad}$이다.

목표: $[x] = [y]$ $\to$ 예제 2.1을 인용하면 $\underline{\quad}$ 하나만 만들면 된다.
:::

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

존재 / $x\,R\,z$ / $y\,R\,z$ / $x\,R\,y$.

"공집합이 아니다"는 원소의 존재 주장이므로, 증명의 첫 동작은 그 원소에 이름을

붙이는 것이다("$z \in [x] \cap [y]$라 하자"). 목표 쪽은 양방향 포함으로 직접 갈

필요가 없다 — 핵심 정리가 이미 $x\,R\,y$에서 $[x] = [y]$로 가는 길을 뚫어 두었다.
:::

:::{container} quotebox
**확인 18.** 손에 있는 것은 $x\,R\,z$와 $y\,R\,z$이고 목표는 $x\,R\,y$다.

두 문장을 그대로 이을 수 없는 이유와, 무엇을 먼저 해야 하는지 적어 보자.
:::

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

두 문장 모두 $z$가 **뒷자리**에 있어 $x \to z$와 $y \to z$가 같은 방향으로 들어온다.

추이성은 $x \to z \to y$ 꼴의 사슬을 요구하므로, 대칭성으로 $y\,R\,z$를 $z\,R\,y$로

뒤집어야 사슬이 이어진다. 예제 2.1의 확인 13과 같은 상황이고, 처방도 같다.
:::

| 증명의 한 줄 | 왜 이 줄을 쓰는가? |
|---|---|
| $[x] \cap [y] \neq \emptyset$이라 가정하자. 그러면 $z \in [x] \cap [y]$인 $z$가 존재한다. | "공집합이 아니다"는 존재 주장이다 — 원소에 이름을 붙이는 것이 첫 동작이다. |
| 교집합의 정의에 의해 $z \in [x]$이고 $z \in [y]$이므로, 정의 37.2에 의해 $x\,R\,z$이고 $y\,R\,z$이다. | 집합 차원의 정보를 관계 문장 둘로 번역한다(근거 ①). |
| 대칭성에 의해 $z\,R\,y$이고, 추이성($x\,R\,z$, $z\,R\,y$)에 의해 $x\,R\,y$이다. | 두 문장의 $z$가 모두 뒷자리라 이어지지 않는다 — 대칭성으로 뒤집어 사슬을 만든다. |
| 핵심 정리(예제 2.1)에 의해 $[x] = [y]$이다. $\blacksquare$ | 원소 차원의 결과를 집합 차원으로 옮긴다(근거 ④). 양방향 포함을 다시 쓸 필요가 없다. |

**이 결과가 하는 일.** 두 동치류가 원소를 하나라도 공유하면 통째로 같은 집합이 된다 — 일부만 걸치는 상태가 불가능하다. 정의 37.3의 조건 ②가 여기서 나오고, 확인 5에서 얻은 $x \in [x]$가 ①과 ③을 준다. 세 조건이 모두 채워지므로 분할 정리가 성립한다 (그 문장을 세우는 일이 문제 8이다).

### 예제 2.3 — 유리수의 정체

$A = \mathbb{Z} \times (\mathbb{Z} - \{0\})$ 위에 관계를 정의한다.

$$
(a, b) \sim (c, d) \iff ad = bc
$$

기호 $\sim$는 "물결"로 읽고, $(a,b) \sim (c,d)$는 "$(a,b)$와 $(c,d)$는 동치이다"로 읽는다. $R$ 대신 $\sim$을 쓰는 것은 관계가 "같음의 기준"일 때의 관례이며, 뜻은 정의 37.1의 $R$과 다르지 않다.

이 관계가 $A$ 위의 동치관계임은 문제 16에서 증명한다. 여기서는 동치관계임을 인정하고 동치류 하나를 계산한다. 이번에는 설계부터 스스로 해 보자.

**명제.** $[(1,2)] = \{(k, 2k) : k \in \mathbb{Z},\ k \neq 0\}$이다.

:::{container} quotebox
**확인 19.** 번역표를 채워 보자.

목표: 집합 상등 $\to$ 정의 27.1에 의해 $\underline{\quad}$과 $\underline{\quad}$을 각각 보인다.

소속 조건: $(c,d) \in [(1,2)]$ $\to$ 정의 37.2에 의해 $\underline{\quad}$ $\to$ 관계의 정의에

의해 $\underline{\quad}$.
:::

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

$[(1,2)] \subseteq \{(k,2k) : k \in \mathbb{Z},\ k \neq 0\}$과 그 반대 포함 /

$(1,2) \sim (c,d)$ / $1 \cdot d = 2 \cdot c$, 곧 $d = 2c$.

소속 조건이 $d = 2c$라는 등식 하나로 내려오므로, 남은 일은 그 등식을 만족하는

순서쌍의 생김새를 적는 것뿐이다. 무대의 조건 $d \neq 0$을 잊지 않는다.
:::

**증명.** ($\subseteq$) $(c,d) \in [(1,2)]$라 하자. 정의 37.2에 의해 $(1,2) \sim (c,d)$이고, 관계의 정의에 의해 $1 \cdot d = 2 \cdot c$, 곧 $d = 2c$이다. $(c,d) \in A$이므로 $d \neq 0$이고, $d = 2c$에서 $c \neq 0$이다. 따라서 $(c,d) = (c, 2c)$이고 $c$는 0이 아닌 정수이므로 오른쪽 집합에 속한다.

($\supseteq$) $k$를 0이 아닌 정수라 하자. $2k \neq 0$이므로 $(k, 2k) \in A$이다. $1 \cdot 2k = 2 \cdot k$이므로 $(1,2) \sim (k, 2k)$이고, 정의 37.2에 의해 $(k,2k) \in [(1,2)]$이다.

양방향 포함이 성립하므로 두 집합은 같다. $\blacksquare$

목록으로 적으면

$$
[(1,2)] = \{\dots,\ (-2,-4),\ (-1,-2),\ (1,2),\ (2,4),\ (3,6),\ \dots\}
$$

이다. 각 순서쌍을 분수로 읽으면 $\frac{-2}{-4},\ \frac{-1}{-2},\ \frac12,\ \frac24,\ \frac36$ — 초등학교의 "약분해도 같은 분수"가 정확히 이 동치관계이고, 유리수 $\frac12$의 정체는 순서쌍 하나가 아니라 **동치류 하나**다. 3주차에서 "$\frac{a}{b}$ 꼴의 수"라고만 적었던 $\mathbb{Q}$는, 집합론의 언어로는 이 동치류들을 원소로 삼는 집합이다.

:::{container} quotebox
**확인 20.** $[(2,4)]$는 $[(1,2)]$와 같은 방인가. 목록을 비교하지 말고 핵심 정리로

판정해 보자.
:::

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

같다. $1 \cdot 4 = 2 \cdot 2$이므로 $(1,2) \sim (2,4)$이고, 핵심 정리에 의해

$[(1,2)] = [(2,4)]$이다. 방 하나에 이름이 무한히 많으므로, 실제로 적을 때는

기약분수에 해당하는 대표원 하나를 골라 쓰는 관례를 따른다. 이 대표원 선택이

48주차에서 유리수를 셀 때 실제로 일한다.
:::

### 관찰 — 같은 뼈대

세 예제는 소재가 다르지만 절차가 같다. 대응표의 빈칸을 채워 보자.

:::{container} quotebox
**확인 21.** 각 단계에 해당하는 문장을 예제에서 찾아 아래 표의 빈칸 (1)(2)(3)을 채워 보자.
:::

| **단계** | **예제 2.1 ($\Rightarrow$)** | **예제 2.2** | **예제 2.3** |
|---|---|---|---|
| ① 방의 상등을 어떻게 다루는가 | 양방향 포함(정의 27.1)으로 쪼갠다 | 핵심 정리를 인용해 $x\,R\,y$ 하나로 바꾼다 | $\underline{\quad(1)\quad}$ |
| ② 소속을 관계 문장으로 번역 | $z \in [x]$ $\leftrightarrow$ $x\,R\,z$ | $z \in [x] \cap [y]$ $\leftrightarrow$ $x\,R\,z$이고 $y\,R\,z$ | $\underline{\quad(2)\quad}$ |
| ③ 목표 문장을 만드는 도구 | 대칭성과 추이성 | $\underline{\quad(3)\quad}$ | 관계의 정의($ad = bc$)로 직접 계산 |

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

(1) 양방향 포함(정의 27.1)으로 쪼갠다.

(2) $(c,d) \in [(1,2)]$ $\leftrightarrow$ $(1,2) \sim (c,d)$ $\leftrightarrow$ $d = 2c$.

(3) 대칭성과 추이성.

세 예제 모두 ① 집합 차원의 목표를 원소 차원으로 내리고 ② 소속을 관계 문장으로

번역한 뒤 ③ 세 성질(또는 관계의 정의)로 목표 문장을 만든다.
:::

방금 확인한 절차에 이름을 붙인다.

:::{admonition} 백지 암기 대상
:class: keybox

**동치류 다루기의 3단계 틀**

① 방의 상등 $[x] = [y]$는 집합 상등이므로 양방향 포함으로 내려간다 — 또는 핵심 정리로 관계 문장 하나로 바꾼다 $\to$ ② 소속 $z \in [x]$를 정의 37.2로 관계 문장 $x\,R\,z$로 번역한다 $\to$ ③ 대칭성으로 방향을 맞추고 추이성으로 사슬을 이어 목표 문장을 만든다.
:::

이 틀은 다음 주에 $\mathbb{Z}_n$의 연산이 잘 정의되는지 검사할 때 그대로 다시 쓴다.

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

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

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

$\mathbb{Z}$ 위의 관계 "같은 홀짝"($x\,R\,y \iff x \equiv y \pmod 2$)에 대해 다음을 채운다. 이 관계는 세 칸이 모두 ✓이므로(§1.2의 표) 동치류를 말할 자격이 있다.

(1) $[0] = \{\underline{\quad(1)\quad}\}$ — 말로 하면 $\underline{\quad(2)\quad}$ 전체.

(2) $[1] = \{\underline{\quad(3)\quad}\}$ — 말로 하면 $\underline{\quad(4)\quad}$ 전체.

(3) 대표원을 $0$ 또는 $1$로 바꿔 적으면 $[4] = [\underline{\quad(5)\quad}]$이고 $[-3] = [\underline{\quad(6)\quad}]$이다. 각각 핵심 정리의 어느 조건을 확인해 얻는가.

(4) 서로 다른 동치류는 $\underline{\quad(7)\quad}$개이고, 이들이 $\mathbb{Z}$의 $\underline{\quad(8)\quad}$을 이룬다.

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

이번에는 근거 문장도 빈칸이다.

**명제.** $R$과 $S$가 모두 $A$ 위의 동치관계이면 $R \cap S$도 $A$ 위의 동치관계이다.

**증명.** (반사) 임의의 $x \in A$에 대해, $R$이 반사적이므로 $(x,x) \in R$이고 $S$가 반사적이므로 $\underline{\quad(1)\quad}$이다. 교집합의 정의에 의해 $(x,x) \in \underline{\quad(2)\quad}$이다 ✓.

(대칭) $(x,y) \in R \cap S$라 $\underline{\quad(3)\quad}$하자. 그러면 $(x,y) \in R$이고 $(x,y) \in S$이다. $R$과 $S$ 각각의 $\underline{\quad(4)\quad}$에 의해 $(y,x) \in R$이고 $(y,x) \in S$이므로 $(y,x) \in R \cap S$이다 ✓.

(추이) $(x,y) \in R \cap S$이고 $(y,z) \in R \cap S$라 하자. $R$ 안에서 $\underline{\quad(5)\quad}$에 의해 $(x,z) \in R$이고, $S$ 안에서도 같은 근거로 $(x,z) \in S$이다. 따라서 $\underline{\quad(6)\quad}$이다 ✓.

세 성질이 모두 성립하므로 $R \cap S$는 $\underline{\quad(7)\quad}$이다. $\blacksquare$

(36주차 문제 16의 "mod 2이면서 동시에 mod 3"인 관계가 이 명제의 특수한 경우다.)

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

이번에는 3단계 틀의 각 칸을 통째로 채운다.

**명제.** $R$이 $A$ 위의 동치관계이고 $[x] \neq [y]$이면 $[x] \cap [y] = \emptyset$이다.

**증명의 뼈대.**

- ① 증명 방식의 선택과 그 이유: $\underline{\quad(1)\quad}$
- ② 뒤집은 명제의 가정에서 얻는 관계 문장들: $\underline{\quad(2)\quad}$
- ③ 목표 도달과 마무리: $\underline{\quad(3)\quad}$

(결론이 "$\emptyset$이다"라는 부정형이므로 직접 가면 다루기 어렵다. 어느 서식으로 바꾸면 손에 원소가 하나 생기는지 생각해 본다. 이 훈련이 문제 8의 조건 ② 부분의 예행연습이다.)

## 연습문제 (20문항)

해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 '접근'까지만 읽고 다시 시도한다 $\to$ 그래도 안 되면 풀이를 읽는다. 동치류가 나오는 증명 문제는 반드시 §2의 3단계 틀부터 적고 시작한다.

:::{admonition} 이번 주의 채점 기준
:class: quotebox

답이 아니라 **근거**가 점수다. "$[4] = [0]$이다(맞음)"는 0점이고,

"$4 \equiv 0 \pmod 2$이므로 핵심 정리에 의해 $[4] = [0]$이다"가 만점이다.

특히 동치류를 다루는 문제에서는 어느 줄이 반사성, 어느 줄이 대칭성, 어느 줄이

추이성인지 표시한다 — 문제 8과 문제 13이 그 표시를 직접 묻는다.

난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다.
:::

### 기본 ●○○

**1.** [백지] 동치관계$\cdot$동치류$\cdot$분할의 정의를 쓰시오.

:::{admonition} 힌트
:class: quotebox dropdown

세 정의 모두 조각의 개수가 정해져 있다 — 동치관계는 성질 세 개, 동치류는

조건제시법 한 줄, 분할은 조건 ①②③이다. 분할의 ①(비공)을 빠뜨리는 경우가 많으므로

확인 8을 떠올린다.
:::

**2.** $\mathbb{Z}$ 위의 $\equiv \pmod 4$에 대해 서로 다른 동치류를 모두 나열하시오 (각각 원소 4개씩 예시).

:::{admonition} 힌트
:class: quotebox dropdown

대표원 후보는 4로 나눈 나머지다. 나머지가 몇 가지인지 세면 동치류의 개수가 나온다.

$[5]$나 $[-1]$은 새 동치류인지, 이미 적은 방의 다른 이름인지 핵심 정리로 판정한다.
:::

**3.** 빈칸 훈련(홀짝)을 백지에서 완성하시오.

:::{admonition} 힌트
:class: quotebox dropdown

훈련 1의 답을 외워 옮기지 말고, $[0]$의 소속 조건 "$0 \equiv z \pmod 2$"부터 다시

세운다. 조건을 세우면 목록은 따라 나온다.
:::

**4.** $A = \{1, 2, 3, 4, 5, 6\}$ 위의 관계 "$x \equiv y \pmod 3$"의 동치류를 모두 구하고, 분할의 세 조건을 확인하시오.

:::{admonition} 힌트
:class: quotebox dropdown

무대가 $\mathbb{Z}$가 아니라 유한집합 $A$다 — 동치류도 $A$ 안에서만 모은다.

세 조건 확인은 말로 넘기지 말고 ① 각 조각이 비지 않았음 ② 쌍마다 교집합이 공집합

③ 합집합이 $A$임을 각각 계산으로 적는다.
:::

**5.** 다음은 $A = \{a, b, c, d\}$의 분할인가? 아니라면 어느 조건 위반인지 지적하시오. (a) $\{a, b\}, \{c\}, \{d\}$  (b) $\{a, b\}, \{b, c\}, \{d\}$  (c) $\{a\}, \{c, d\}$  (d) $\{a, b\}, \emptyset, \{c, d\}$

:::{admonition} 힌트
:class: quotebox dropdown

정의 37.3의 세 조건을 검사 항목으로 삼아 항목마다 통과$\cdot$탈락을 적는다.

탈락한 항목은 위반의 증거(공유하는 원소, 빠진 원소, 빈 조각)를 지목해야 완결된다.
:::

**6.** 예제 2.1(핵심 정리)을 백지에 재현하시오.

:::{admonition} 힌트
:class: quotebox dropdown

뼈대는 네 덩어리다 — ($\Rightarrow$)의 두 포함, 상등 선언, ($\Leftarrow$).

각 덩어리를 쓴 뒤 옆에 반사$\cdot$대칭$\cdot$추이 중 무엇을 썼는지 적어 두면 빠뜨린 부품이 보인다.
:::

### 표준 ●●○

**7.** 예제 2.2(같거나 서로소)를 백지에 재현하시오.

:::{admonition} 힌트
:class: quotebox dropdown

첫 문장은 "공집합이 아니다"를 원소의 존재로 바꾸는 문장이다. 마지막 문장은

양방향 포함이 아니라 핵심 정리의 인용이다.
:::

**8.** 동치류 전체가 분할의 세 조건(비공$\cdot$서로소$\cdot$덮음)을 만족함을 — 각 조건이 어느 성질/정리에서 오는지 명시하며 — 증명하시오.

:::{admonition} 힌트
:class: quotebox dropdown

세 조건을 각각 한 문단으로 쓴다. ①과 ③의 재료는 같다($x \in [x]$)지만 결론이

다르므로 따로 적는다. ②는 "서로 **다른** 두 동치류"에 대한 주장이므로 대우로 가는

것이 짧다 — 훈련 3에서 만든 뼈대를 그대로 쓴다.
:::

**9.** $\mathbb{R}$ 위의 관계 $x R y \iff x - y \in \mathbb{Z}$ (36주차 훈련 1)에 대해: (a) $\left[\frac12\right]$의 원소를 5개 나열하시오. (b) $[0]$의 정체는? (c) $\left[\frac12\right] = \left[\frac32\right]$인 이유를 핵심 정리로 설명하시오.

:::{admonition} 힌트
:class: quotebox dropdown

소속 조건을 먼저 적는다: $z \in \left[\frac12\right] \iff \frac12 - z \in \mathbb{Z}$.

이 조건을 만족하는 $z$는 $\frac12$에서 정수만큼 떨어진 실수다.
:::

**10.** $\mathbb{R}$ 위의 관계 $x R y \iff |x| = |y|$에 대해: (a) 동치관계임을 확인하시오 (등식 기반 — 한 줄씩). (b) $[3]$, $[0]$을 구하시오. (c) 동치류들의 일반형을 묘사하시오.

:::{admonition} 힌트
:class: quotebox dropdown

관계의 조건이 등식이므로 세 성질이 전부 등호의 성질에서 상속된다. 각 성질마다

어떤 등식 조작을 했는지 한 줄씩 적는다. (c)에서는 $x = 0$인 경우를 따로 본다.
:::

**11.** (분할 $\to$ 동치관계) 집합 $A$의 분할이 주어졌을 때, "$x$와 $y$가 같은 조각에 속한다"로 정의한 관계가 동치관계임을 증명하시오. (반사에서 조건 ③, 추이에서 조건 ②가 소비된다 — 어디서인지 명시할 것)

:::{admonition} 힌트
:class: quotebox dropdown

추이가 관문이다. $x, y$가 조각 $P$에, $y, z$가 조각 $Q$에 있다고 하면 $y$가 두 조각에

동시에 들어간다 — 그러면 $P \cap Q \neq \emptyset$이고, 조건 ②를 대우로 읽으면

$P$와 $Q$에 대해 무엇을 말할 수 있는가.
:::

**12.** $A = \{1, 2, \dots, 10\}$ 위의 $\equiv \pmod 4$: 동치류를 모두 나열하고 각각의 크기를 구하시오. (크기가 균등하지 않음을 관찰)

**13.** (성질 하나가 빠지면) $\mathbb{Z}$ 위의 $\le$에 대해 "$[x] = \{z : x \le z\}$"를 동치류처럼 정의해 보자. (a) $[1]$과 $[2]$를 구하시오. (b) $[1] \cap [2] \neq \emptyset$인데 $[1] \neq [2]$임을 확인하시오. (c) 예제 2.2의 증명이 $\le$에서 정확히 어느 줄에서 무너지는지 지적하시오.

:::{admonition} 힌트
:class: quotebox dropdown

(c)는 "$\le$는 동치관계가 아니다"로 끝내면 절반이다. 예제 2.2의 네 줄을 하나씩

손가락으로 짚으며 $\le$를 대입해 보고, 처음으로 참이 아니게 되는 줄을 특정한다.

$\le$가 가진 성질(반사$\cdot$추이)로는 통과되는 줄이 어디까지인지도 함께 적는다.
:::

**14.** 36주차 문제 19(원점에서 같은 거리)의 동치류가 평면의 분할을 이룸을 확인하고, 동치류 전체의 모임이 무엇과 1:1 대응되는지 답하시오 (힌트: 반지름).

:::{admonition} 힌트
:class: quotebox dropdown

앞부분은 새 증명이 아니다 — 36주차 문제 19에서 동치관계임이 이미 판정되었으므로

문제 8의 일반론을 인용하면 끝난다. 뒷부분은 동치류 하나를 결정하는 수가 무엇인지

묻는 것이다. 원점 자신이 만드는 조각도 빠뜨리지 않는다.
:::

### 도전 ●●●

**15.** $\mathbb{Z}$ 위의 관계 $x R y \iff x^2 \equiv y^2 \pmod 3$을 생각하자. (a) 동치관계임을 증명하시오 (합동의 성질 + 등식 상속). (b) 동치류가 몇 개인지 구하시오 (힌트: 17주차 문제 8 — $n^2$의 mod 3 나머지는 0 또는 1뿐).

:::{admonition} 힌트
:class: quotebox dropdown

(a)는 $f(x)$를 "$x^2$을 3으로 나눈 나머지"로 두면 $x\,R\,y \iff f(x) = f(y)$가 되어

문제 10과 같은 꼴이 된다. (b)는 $f$가 취할 수 있는 값의 개수가 곧 방의 개수라는

관찰이다 — 값 하나마다 방 하나가 대응하고, 그 값이 실제로 나타나는지 예를 들어

확인해야 개수가 확정된다.
:::

:::{admonition} 이 문제가 빌려 쓰는 사실 — 영인수 성질 (문제 16용)
:class: quotebox

정수 $x, y$에 대해 $xy = 0$이면 $x = 0$ 또는 $y = 0$이다. 25주차 문제 13에 딸린

상자에서 영인수 성질이라는 이름으로 다룬 사실이고, 이번 주에는 근거 ④로 인용해

쓴다. 문제 16의 추이성 증명에서 $d(af - be) = 0$과 $d \neq 0$으로부터 $af = be$를

끌어내는 자리가 그 인용 지점이다.
:::

**16.** (유리수의 탄생) 예제 2.3의 관계 $(a,b) \sim (c,d) \iff ad = bc$가 $\mathbb{Z} \times (\mathbb{Z} - \{0\})$ 위의 동치관계임을 증명하시오. (추이성 힌트: $ad = bc$, $cf = de$에서 $adf = bcf = bde$ — $d \neq 0$으로 소거. "0이 아닌 정수의 소거"는 정당한가?)

:::{admonition} 힌트
:class: quotebox dropdown

반사와 대칭은 곱셈의 교환법칙과 등식 뒤집기로 각각 한 줄이다. 추이에서는

손에 있는 두 등식에 공통으로 등장하는 문자가 무엇인지 본다 — 그 문자를 소거해야

$a, b, e, f$만 남는다. 소거는 나눗셈이 아니라 위 상자의 영인수 성질로 정당화한다.
:::

**17.** 두 동치관계 $R, S$가 같은 분할을 만들면 $R = S$임을 증명하시오. (힌트: $x R y \iff$ "$x, y$가 같은 $R$-조각" — 핵심 정리)

:::{admonition} 힌트
:class: quotebox dropdown

관계는 순서쌍의 집합이므로(정의 36.1) $R = S$의 목표는 "모든 $x, y$에 대해

$x\,R\,y \iff x\,S\,y$"다. 왼쪽 끝에서 오른쪽 끝까지 $\iff$의 사슬을 만든다 —

핵심 정리가 관계를 동치류의 상등으로 바꾸고, 가정이 동치류를 조각으로 바꾼다.
:::

:::{admonition} 이 문제가 되살리는 구분 — 반례와 가정 위반 (29주차 정의 29.2, 문제 18용)
:class: quotebox

정리가 "$P$이면 $Q$이다" 꼴일 때, $Q$가 거짓인 사례를 찾았다고 곧바로 반례가 되는

것은 아니다. 반례가 되려면 $P$도 함께 참이어야 한다. $P$가 거짓인 사례는 정리의

적용 대상 밖이므로, 그 사례에서 무슨 일이 일어나든 정리와 충돌하지 않는다.

이 두 검증(가정 만족$\cdot$결론 위배)의 서식이 정의 29.2이고, 30주차 확인 1$\cdot$2가 그것을

판별 동선에 넣었다. 문제 13과 문제 18은 같은 구분을 각각 $\le$와 $R$에서 확인한다.
:::

**18.** (진단) 학생이 $A = \{1,2,3,4\}$ 위의 관계 $R = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(2,3),(3,2)\}$의 동치류를 "$[1] = \{1,2\}$, $[2] = \{1,2,3\}$, $[3] = \{2,3\}$"으로 계산하고 동치류가 겹친다고 물었다. 무엇이 잘못인지 — 관계 자체의 결함을 — 진단하고, 겹침이 핵심 정리와 모순되지 않는 이유를 설명하시오.

:::{admonition} 힌트
:class: quotebox dropdown

계산 자체는 틀리지 않았다. 그러므로 결함은 계산 앞, 정의 37.2를 쓸 자격에 있다.

세 성질을 하나씩 검사해 실패하는 항목과 그 반례 사슬을 특정한다.
:::

**19.** $|A| = 3$인 집합 $A = \{a, b, c\}$의 분할을 **모두** 나열하시오 (5개). 따라서 $A$ 위의 동치관계는 정확히 몇 개인가? (동치관계 $\longleftrightarrow$ 분할의 1:1 대응 사용)

:::{admonition} 힌트
:class: quotebox dropdown

빠뜨림 없이 세려면 기준이 필요하다. 조각의 크기 배분으로 경우를 나눈다 —

$3$ / $2+1$ / $1+1+1$의 세 가지뿐이고, 가운데 배분에서만 어느 두 원소를 묶는지의

선택이 남는다. 뒷부분은 문제 11과 문제 17이 함께 만드는 1:1 대응을 인용한다.
:::

**20.** (서술) (a) "동치관계와 분할은 같은 정보의 두 얼굴"을 양방향 대응(동치류 만들기 / 같은-조각 관계 만들기)으로 두 문장 이내 설명하시오. (b) 20주차 문제 20에서 "같음의 조건을 느슨하게 바꾼 세계마다 새로운 산술이 생긴다"고 했다 — 다음 주($\mathbb{Z}_n$)에 무엇이 만들어질지, 동치류의 언어로 예고를 써 보시오.

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

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

**1차 시도 (4일차) — 틀 카드 허용.** 동치류 다루기의 3단계 틀(§2 관찰)과 근거 목록(§1.8)만 펴 놓고, 예제 2.1(핵심 정리)을 처음부터 끝까지 적는다. 정의와 본문은 보지 않는다.

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

- [ ] 동치관계$\cdot$동치류$\cdot$분할의 정의를 조각 그대로 정확히 썼다 (분할의 ①까지).
- [ ] 예제 2.1(핵심 정리)을 두 방향 모두 처음부터 끝까지 재현했다.
- [ ] 재현한 증명의 각 줄 옆에 반사$\cdot$대칭$\cdot$추이 중 무엇을 썼는지 표시했고, 셋이 모두 등장했다.
- [ ] 예제 2.2(같거나 서로소)를 재현했고, 마지막 줄이 핵심 정리의 인용임을 확인했다.
- [ ] 분할 정리의 세 조건이 각각 어느 사실에서 오는지 말했다.
- [ ] 분할에서 동치관계를 만드는 역방향(문제 11)을 설명했다.
- [ ] 유리수가 순서쌍들의 동치류라는 것을 $\frac12$의 예로 설명했다.

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

| **막힌 지점** | **처방** |
|---|---|
| 정의가 정확히 기억나지 않는다 | §1.3과 §1.6의 해부 표 — 조각의 역할과 함께 다시 외운다 |
| $[x] = [y]$를 어디서부터 손대야 할지 모르겠다 | §2 관찰의 3단계 틀 ① — 집합 상등은 양방향 포함으로 내려간다 |
| $z \in [x]$ 다음 줄이 나오지 않는다 | 예제 2.1의 1단계 — 소속을 정의 37.2로 관계 문장으로 번역한다 |
| 관계 문장이 두 개 있는데 이어지지 않는다 | 확인 13과 확인 18 — 자리(앞$\cdot$뒤)를 보고 대칭성으로 방향을 맞춘다 |
| 세 성질 중 무엇을 쓸지 매번 헷갈린다 | §1.3의 해부 표 — 반사는 자기 방 넣기, 대칭은 방향 맞추기, 추이는 잇기 |
| 분할의 세 조건이 잘 안 떠오른다 | 확인 7의 표 — 빠짐$\cdot$겹침$\cdot$빈 조각의 세 사유로 복원한다 |
| 겹치는 "동치류"를 보고 정리를 의심하게 된다 | 문제 18 앞 상자 — 가정 위반과 반례의 구분 |

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

## 해설

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

### 빈칸 사다리 — 훈련 1

(1) $\dots, -4, -2, 0, 2, 4, \dots$  (2) 짝수  (3) $\dots, -3, -1, 1, 3, 5, \dots$  (4) 홀수 (5) $0$  (6) $1$  (7) $2$  (8) 분할

※ (5)(6)의 근거를 적는 것이 이 훈련의 핵심이다. $[4] = [0]$은 "$4 \equiv 0 \pmod 2$이므로 핵심 정리에 의해"이고, $[-3] = [1]$은 "$-3 \equiv 1 \pmod 2$($-3 - 1 = -4$가 2의 배수)이므로 핵심 정리에 의해"다. 목록을 눈으로 비교해 같다고 적으면 무한집합에서는 검사가 끝나지 않는다 — 핵심 정리가 그 검사를 유한하게 만든다. (8)에서 두 방이 $\mathbb{Z}$를 덮고 겹치지 않는다는 것은 분할 정리의 특수한 경우다.

### 빈칸 사다리 — 훈련 2

(1) $(x,x) \in S$  (2) $R \cap S$  (3) 가정  (4) 대칭성  (5) 추이성  (6) $(x,z) \in R \cap S$ (7) 동치관계

※ 세 성질이 모두 "$R$에서 한 번, $S$에서 한 번, 그다음 교집합의 정의로 합치기"라는 같은 절차로 처리된다. 교집합의 정의(정의 5.1)가 세 번 모두 마지막 줄에서 일한다. 합집합에 대해서는 같은 논증이 통하지 않는다 — 추이 단계에서 $(x,y)$가 $R$에만, $(y,z)$가 $S$에만 속하는 경우를 이을 방법이 없기 때문이고, 실제로 반례가 존재한다.

### 빈칸 사다리 — 훈련 3

(1) 대우로 증명한다. 결론이 "$[x] \cap [y] = \emptyset$"이라는 부정형이라 직접 다루기 어려운 반면, 대우의 가정 "$[x] \cap [y] \neq \emptyset$"은 원소 하나를 손에 쥐여 주므로 계산을 시작할 수 있다. 즉 "$[x] \cap [y] \neq \emptyset$이면 $[x] = [y]$"를 증명한다.

(2) $z \in [x] \cap [y]$라 하자. 교집합의 정의에 의해 $z \in [x]$이고 $z \in [y]$이므로, 정의 37.2에 의해 $x\,R\,z$이고 $y\,R\,z$이다.

(3) 대칭성에 의해 $z\,R\,y$이고, 추이성($x\,R\,z$, $z\,R\,y$)에 의해 $x\,R\,y$이다. 핵심 정리에 의해 $[x] = [y]$이다. 대우가 증명되었으므로 원명제도 성립한다. $\blacksquare$

※ 이 명제가 예제 2.2의 대우 판본이고, 문제 8의 조건 ②가 요구하는 것이 바로 이 꼴이다 ("서로 **다른** 두 동치류는 서로소"). 부정형 결론을 만나면 대우를 먼저 검토하는 것이 19주차에서 세우고 30주차의 판별 동선에서 다시 확인한 습관이다.

### 문제 1

**접근.** 세 정의를 순서대로 적되, 각 정의가 몇 조각으로 되어 있는지 세면서 적는다. 동치관계는 성질 셋, 동치류는 조건제시법 한 줄, 분할은 조건 셋이다. 조각 수를 세는 것이 빠뜨림을 막는 가장 단순한 장치다.

**풀이.** (동치관계, 정의 37.1) 집합 $A$ 위의 관계 $R$이 반사적이고 대칭적이고 추이적일 때 $R$을 $A$ 위의 동치관계라 한다. — 세 성질을 함께 적으면 다음과 같다. 반사적: 모든 $x \in A$에 대해 $x\,R\,x$. 대칭적: 모든 $x, y \in A$에 대해 $x\,R\,y$이면 $y\,R\,x$. 추이적: 모든 $x, y, z \in A$에 대해 $x\,R\,y$이고 $y\,R\,z$이면 $x\,R\,z$.

(동치류, 정의 37.2) $A$ 위의 동치관계 $R$과 $x \in A$에 대해 $[x] = \{z \in A : x\,R\,z\}$이며, $x$를 이 동치류의 대표원이라 한다.

(분할, 정의 37.3) 집합 $A$의 분할이란 $A$의 부분집합들의 모임으로서 ① 각 조각이 공집합이 아니고 ② 서로 다른 두 조각이 서로소이며 ③ 조각들의 합집합이 $A$인 것이다.

**복기.** 동치류의 정의에 "동치관계 $R$과"라는 전제가 들어 있다는 것과, 분할의 ①이 있다는 것 — 이 두 조각이 가장 자주 빠진다. 앞의 것이 빠지면 문제 18의 혼란이 생기고, 뒤의 것이 빠지면 문제 19의 개수가 두 배로 부풀어 동치관계와의 1:1 대응이 깨진다.

### 문제 2

**접근.** 대표원 후보는 4로 나눈 나머지 $0, 1, 2, 3$이다. 나머지가 같은 정수끼리 한 방에 모이므로 방의 개수는 나머지의 가짓수와 같다. 새로 적은 방이 이미 있는 방과 같은지는 핵심 정리로 판정한다.

**풀이.** 소속 조건은 $z \in [r] \iff r \equiv z \pmod 4 \iff 4 \mid (z - r)$이다. 따라서

$$
[0] = \{\dots, -4, 0, 4, 8, \dots\},\quad [1] = \{\dots, -3, 1, 5, 9, \dots\}
$$

$$
[2] = \{\dots, -2, 2, 6, 10, \dots\},\quad [3] = \{\dots, -1, 3, 7, 11, \dots\}
$$

서로 다른 동치류는 이 **4개**다. 다른 이름은 새 방이 아니다 — 예컨대 $[5]$는 $5 \equiv 1 \pmod 4$이므로 핵심 정리에 의해 $[5] = [1]$이고, $[-1]$은 $-1 \equiv 3 \pmod 4$이므로 $[-1] = [3]$이다. 임의의 정수 $n$은 4로 나눈 나머지가 $0, 1, 2, 3$ 중 하나이므로 네 방 중 하나에 반드시 속하고, 나머지는 하나뿐이므로 두 방에 동시에 속하지 않는다.

**검산.** 네 방의 합집합이 $\mathbb{Z}$이고 쌍마다 교집합이 공집합이다 — 분할 정리가 예측한 그대로다.

### 문제 3

**접근.** 훈련 1의 답을 외워 옮기지 않는다. $[0]$의 소속 조건을 정의 37.2로 다시 세우면 목록이 저절로 나온다.

**풀이.** 소속 조건은 $z \in [0] \iff 0 \equiv z \pmod 2 \iff 2 \mid z$이므로 $[0] = \{\dots, -4, -2, 0, 2, 4, \dots\}$ — 짝수 전체다. 마찬가지로 $z \in [1] \iff 2 \mid (z - 1)$이므로 $[1] = \{\dots, -3, -1, 1, 3, 5, \dots\}$ — 홀수 전체다. $4 \equiv 0 \pmod 2$이므로 핵심 정리에 의해 $[4] = [0]$이고, $-3 \equiv 1 \pmod 2$ ($-3 - 1 = -4 = 2 \times (-2)$)이므로 $[-3] = [1]$이다. 임의의 정수는 짝수이거나 홀수이므로 서로 다른 동치류는 **2개**이고, 두 방이 겹침 없이 $\mathbb{Z}$를 덮으므로 $\mathbb{Z}$의 **분할**을 이룬다.

**복기.** "$[4] = [0]$"의 근거는 목록 비교가 아니라 $4 \equiv 0$이라는 관계 문장 하나다. 무한집합에서 방의 상등을 판정하는 유일한 실용적 방법이 핵심 정리다.

### 문제 4

**접근.** 무대가 유한집합 $A = \{1, \dots, 6\}$이므로 동치류도 $A$ 안에서만 모은다. $\mathbb{Z}$에서와 달리 각 방의 원소가 유한 개이고, 나머지가 0인 방의 대표원으로 $A$ 안에서는 $3$을 쓰게 된다.

**풀이.** 3으로 나눈 나머지로 묶으면

$$
[1] = \{1, 4\},\quad [2] = \{2, 5\},\quad [3] = \{3, 6\}
$$

이다($[4] = [1]$, $[5] = [2]$, $[6] = [3]$이므로 새 방은 없다). 분할의 세 조건을 확인한다. ① 세 조각 모두 원소를 2개씩 가지므로 공집합이 아니다. ② $\{1,4\} \cap \{2,5\} = \emptyset$, $\{1,4\} \cap \{3,6\} = \emptyset$, $\{2,5\} \cap \{3,6\} = \emptyset$으로 쌍마다 서로소다. ③ $\{1,4\} \cup \{2,5\} \cup \{3,6\} = \{1,2,3,4,5,6\} = A$이다. 세 조건이 모두 성립하므로 분할이다.

**검산.** 조각 크기의 합이 $2 + 2 + 2 = 6 = |A|$다 — 분할이면 크기의 합이 전체 크기와 같아야 하므로(14주차 덧셈 원리) 빠짐이나 겹침이 없음을 수로 재확인한 것이다.

### 문제 5

**접근.** 정의 37.3의 세 조건을 검사 항목으로 삼는다. 탈락시킬 때는 위반의 증거 — 공유하는 원소, 빠진 원소, 빈 조각 — 를 지목해야 답이 완결된다.

**풀이.** (a) 분할이다. ① $\{a,b\}, \{c\}, \{d\}$ 모두 비지 않았다. ② 쌍마다 교집합이 공집합이다. ③ 합집합이 $\{a,b,c,d\} = A$다. (b) 분할이 아니다 — 조건 ② 위반. $\{a,b\} \cap \{b,c\} = \{b\} \neq \emptyset$인데 두 조각이 서로 다르다. 원소 $b$가 두 조각에 동시에 속한다. (c) 분할이 아니다 — 조건 ③ 위반. 합집합이 $\{a, c, d\}$로 $b$가 어느 조각에도 속하지 않는다. (d) 분할이 아니다 — 조건 ① 위반. 둘째 조각이 공집합이다. (②와 ③은 통과한다 — 공집합은 어느 집합과도 서로소이고, 합집합에 아무것도 더하지 않는다.)

**복기.** (d)가 ②③을 통과한다는 점이 조건 ①의 존재 이유를 보여 준다. ①이 없으면 같은 나눔에 공집합을 붙인 목록이 별개의 분할로 한 번 더 세어지고, 문제 19의 개수가 두 배로 부풀어 동치관계와의 1:1 대응이 깨진다.

### 문제 6

**접근.** 뼈대는 네 덩어리다 — ($\Rightarrow$)의 두 포함, 상등 선언, ($\Leftarrow$). 쓰고 나서 각 줄 옆에 반사$\cdot$대칭$\cdot$추이 중 무엇을 썼는지 적어 셋이 모두 나왔는지 본다.

**풀이.** $R$이 $A$ 위의 동치관계이고 $x, y \in A$라 하자.

($\Rightarrow$) $x\,R\,y$라 가정한다. 먼저 $[x] \subseteq [y]$를 보인다. $z \in [x]$라 하자. 정의 37.2에 의해 $x\,R\,z$이다. 대칭성에 의해 $y\,R\,x$이고, 추이성($y\,R\,x$와 $x\,R\,z$)에 의해 $y\,R\,z$이다. 따라서 정의 37.2에 의해 $z \in [y]$이고, $[x] \subseteq [y]$이다. 다음으로 $[y] \subseteq [x]$를 보인다. $z \in [y]$라 하자. 정의 37.2에 의해 $y\,R\,z$이고, 가정 $x\,R\,y$와의 추이성에 의해 $x\,R\,z$이므로 $z \in [x]$이다. 양방향 포함이 성립하므로(정의 27.1) $[x] = [y]$이다.

($\Leftarrow$) $[x] = [y]$라 가정한다. 반사성에 의해 $x\,R\,x$이므로 정의 37.2에 의해 $x \in [x]$이고, 가정에 의해 $x \in [y]$이다. 정의 37.2에 의해 $y\,R\,x$이고, 대칭성에 의해 $x\,R\,y$이다.

두 방향이 모두 증명되었으므로 $x\,R\,y \iff [x] = [y]$이다. $\blacksquare$

**복기.** 소비처는 반사 1회(($\Leftarrow$) 첫 줄), 대칭 2회(($\Rightarrow$) 첫 포함과 ($\Leftarrow$) 마지막), 추이 2회(($\Rightarrow$)의 두 포함)다. 재현 후 이 표시가 비는 칸이 있으면 그 성질을 쓰는 줄을 빠뜨린 것이다.

### 문제 7

**접근.** 첫 문장은 "공집합이 아니다"를 원소의 존재로 바꾸는 문장이고, 마지막 문장은 양방향 포함이 아니라 핵심 정리의 인용이다. 이 두 끝을 먼저 적어 두면 가운데는 두 줄이다.

**풀이.** $R$이 $A$ 위의 동치관계이고 $[x] \cap [y] \neq \emptyset$이라 가정한다. 공집합이 아니므로 $z \in [x] \cap [y]$인 원소 $z$가 존재한다. 교집합의 정의에 의해 $z \in [x]$이고 $z \in [y]$이므로, 정의 37.2에 의해 $x\,R\,z$이고 $y\,R\,z$이다. 두 문장 모두 $z$가 뒷자리에 있으므로 그대로는 이어지지 않는다 — 대칭성에 의해 $y\,R\,z$를 $z\,R\,y$로 뒤집는다. 이제 $x\,R\,z$와 $z\,R\,y$가 사슬을 이루므로 추이성에 의해 $x\,R\,y$이다. 핵심 정리(예제 2.1)에 의해 $[x] = [y]$이다. $\blacksquare$

**복기.** 대칭성이 필요한 이유는 두 가정의 $z$가 같은 자리에 있기 때문이다. 관계 문장을 이을 때는 문자의 자리(앞$\cdot$뒤)를 먼저 본다 — 이 습관 하나가 문제 13에서 $\le$가 무너지는 줄을 정확히 짚게 해 준다.

### 문제 8

**접근.** 세 조건을 각각 한 문단으로 쓴다. ①과 ③은 재료가 같지만($x \in [x]$) 결론이 다르므로 따로 적는다. ②는 "서로 **다른** 두 동치류"에 대한 주장이므로 대우로 간다 — 훈련 3에서 만든 뼈대를 그대로 쓴다.

**풀이.** $R$을 $A$ 위의 동치관계라 하고, $\mathcal{P}$를 서로 다른 동치류 전체의 모임이라 하자.

(① 비공) 임의의 동치류 $[x] \in \mathcal{P}$를 잡자. **반사성**에 의해 $x\,R\,x$이고, 정의 37.2에 의해 $x \in [x]$이다. 따라서 $[x] \neq \emptyset$이다.

(② 서로소) 보일 것은 "$[x], [y] \in \mathcal{P}$이고 $[x] \neq [y]$이면 $[x] \cap [y] = \emptyset$이다"이다. 대우를 보인다 — 대우는 "$[x] \cap [y] \neq \emptyset$이면 $[x] = [y]$이다"이고, 이것이 곧 **따름정리(예제 2.2)** 그 자체다. 대우가 성립하므로 원명제도 성립한다. 즉 서로 다른 두 동치류는 서로소다(훈련 3에서 만든 뼈대가 이 문단이다).

(③ 덮음) $\bigcup_{[x] \in \mathcal{P}} [x] \subseteq A$는 각 동치류가 $A$의 부분집합이므로 성립한다. 반대로 임의의 $a \in A$에 대해, **반사성**에 의해 $a \in [a]$이고 $[a]$는 동치류이므로 $\mathcal{P}$에 속한다. 따라서 $a$는 합집합에 속하고 $A \subseteq \bigcup [x]$이다. 양방향 포함으로 합집합은 $A$와 같다.

세 조건이 모두 성립하므로 $\mathcal{P}$는 $A$의 분할이다. $\blacksquare$

**복기.** 각 조건의 출처를 한 줄로 정리하면 ① 반사성, ② 따름정리(그 안에서 대칭$\cdot$추이), ③ 반사성이다. 세 성질 중 반사성만이 두 번 등장하는데, 반사성이 각 원소를 자기 방에 넣는 유일한 부품이기 때문이다. 반사성이 빠지면 방이 비고 무대에 구멍이 남는다.

### 문제 9

**접근.** 소속 조건을 먼저 적는다. $z \in \left[\frac12\right] \iff \frac12 - z \in \mathbb{Z}$이므로, $\frac12$에서 정수만큼 떨어진 실수 전체가 이 방의 원소다.

**풀이.** (a) $\frac12 - z$가 정수가 되는 $z$를 고르면 된다. $z = \frac12$($\frac12 - z = 0$), $z = \frac32$($=-1$), $z = -\frac12$($=1$), $z = \frac52$($=-2$), $z = -\frac32$($=2$)이므로

$$
\left[\tfrac12\right] \supseteq \left\{-\tfrac32,\ -\tfrac12,\ \tfrac12,\ \tfrac32,\ \tfrac52\right\}
$$

이고, 일반형은 $\left[\frac12\right] = \left\{\frac12 + n : n \in \mathbb{Z}\right\}$이다.

(b) $z \in [0] \iff 0 - z \in \mathbb{Z} \iff z \in \mathbb{Z}$이므로 $[0] = \mathbb{Z}$ — 정수 전체가 하나의 방이다.

(c) 관계 문장의 앞자리가 $\frac12$이므로 확인할 값은 $\frac12 - \frac32$다. $\frac12 - \frac32 = -1 \in \mathbb{Z}$이므로 $\frac12\,R\,\frac32$이다. 핵심 정리에 의해 $\left[\frac12\right] = \left[\frac32\right]$이다. 원소 두 개의 관계 하나를 확인한 것만으로 무한집합 두 개의 상등이 확정된다.

**복기.** 각 동치류는 "소수 부분이 같은 실수 전체"이고, 대표원을 구간 $[0,1)$에서 하나씩 고를 수 있다. 20주차의 시계가 12시간마다 같은 눈금을 가리키는 것의 실수 판본이다.

### 문제 10

**접근.** 관계의 조건이 등식 $|x| = |y|$이므로, 세 성질이 전부 등호의 성질에서 상속된다. 성질마다 어떤 등식 조작을 했는지 한 줄씩 적는다. (c)에서는 $x = 0$인 경우를 따로 본다.

**풀이.** (a) (반사) 임의의 $x \in \mathbb{R}$에 대해 $|x| = |x|$이므로 $x\,R\,x$이다 — 등호의 반사성. (대칭) $x\,R\,y$라 하면 $|x| = |y|$이고, 등식의 양변을 바꾸면 $|y| = |x|$이므로 $y\,R\,x$이다. (추이) $x\,R\,y$이고 $y\,R\,z$라 하면 $|x| = |y|$이고 $|y| = |z|$이므로, 등식을 이으면 $|x| = |z|$이고 $x\,R\,z$이다. 세 성질이 모두 성립하므로 동치관계다.

(b) $z \in [3] \iff |3| = |z| \iff |z| = 3 \iff z = 3$ 또는 $z = -3$이므로 $[3] = \{3, -3\}$이다. $z \in [0] \iff |z| = 0 \iff z = 0$이므로 $[0] = \{0\}$이다.

(c) $x \neq 0$이면 $|z| = |x|$의 해가 $z = x$와 $z = -x$의 두 개이므로 $[x] = \{x, -x\}$로 원소가 2개다. $x = 0$이면 $[0] = \{0\}$으로 원소가 1개다. 따라서 수직선은 "원점 대칭인 두 점의 쌍들"과 "원점 하나"로 분할된다.

**복기.** 관계의 조건이 "어떤 값이 같다"는 꼴이면 세 성질은 항상 등호에서 상속된다 — 따로 증명할 것이 없다시피 하다. 문제 15가 같은 구조의 다른 사례이고, 그때는 값이 "$x^2$의 mod 3 나머지"로 바뀔 뿐이다. 크기가 다른 동치류가 한 분할 안에 공존한다는 점은 문제 12에서도 관찰된다 — 분할은 균등 분배를 요구하지 않는다.

### 문제 11

**접근.** 세 성질을 각각 분할의 조건에서 끌어온다. 반사는 ③(모든 원소가 어느 조각엔가 속함), 대칭은 "같은 조각"이라는 표현 자체의 좌우 무관함, 추이는 ②(서로 다른 조각은 서로소)의 대우다. 추이가 관문이므로 여기에 시간을 쓴다.

**풀이.** $\mathcal{P}$를 $A$의 분할이라 하고, 관계 $R$을 "$x\,R\,y \iff$ 어떤 조각 $P \in \mathcal{P}$가 있어 $x \in P$이고 $y \in P$"로 정의한다.

(반사) 임의의 $x \in A$를 잡자. 분할의 조건 ③에 의해 조각들의 합집합이 $A$이므로 $x$가 속하는 조각 $P \in \mathcal{P}$가 존재한다. 이 $P$에 대해 $x \in P$이고 $x \in P$이므로 정의에 의해 $x\,R\,x$이다.

(대칭) $x\,R\,y$라 하자. 정의에 의해 어떤 조각 $P$가 있어 $x \in P$이고 $y \in P$이다. 같은 $P$에 대해 $y \in P$이고 $x \in P$이므로 $y\,R\,x$이다. (정의의 조건이 $x$와 $y$의 순서에 무관하므로 새로 할 일이 없다.)

(추이) $x\,R\,y$이고 $y\,R\,z$라 하자. 정의에 의해 조각 $P$가 있어 $x, y \in P$이고, 조각 $Q$가 있어 $y, z \in Q$이다. 그러면 $y \in P \cap Q$이므로 $P \cap Q \neq \emptyset$이다. 분할의 조건 ②는 "서로 다른 두 조각은 서로소"이므로, 그 대우에 의해 서로소가 아닌 두 조각은 같다 — 즉 $P = Q$이다. 따라서 $x \in P$이고 $z \in Q = P$이므로, 이 한 조각 $P$가 $x\,R\,z$의 증인이 된다.

세 성질이 모두 성립하므로 $R$은 $A$ 위의 동치관계다. $\blacksquare$

**복기.** ③이 반사를, ②가 추이를 책임진다. 조건 ①(비공)은 이 증명에서 쓰이지 않는데, 빈 조각이 있어도 관계 자체는 동치관계로 남기 때문이다. ①이 일하는 곳은 관계가 아니라 분할을 **세는** 자리다(문제 19). 조건과 성질의 대응이 정확히 어긋나지 않는다는 점이, 동치관계와 분할이 같은 정보라는 주장의 절반이다.

### 문제 12

**접근.** 4로 나눈 나머지로 묶되, 무대가 $\{1, \dots, 10\}$이므로 각 방의 원소를 그 안에서만 센다. 10이 4의 배수가 아니므로 방의 크기가 균등하지 않을 것을 미리 예상할 수 있다.

**풀이.** 나머지가 1인 수는 $1, 5, 9$, 나머지가 2인 수는 $2, 6, 10$, 나머지가 3인 수는 $3, 7$, 나머지가 0인 수는 $4, 8$이다. 따라서

$$
[1] = \{1, 5, 9\},\quad [2] = \{2, 6, 10\},\quad [3] = \{3, 7\},\quad [4] = \{4, 8\}
$$

이고, 서로 다른 동치류는 4개이며 크기는 각각 $3, 3, 2, 2$다. 크기가 균등하지 않다 — 무대의 크기 10이 4로 나누어떨어지지 않기 때문이고, 나머지 $1, 2$에 해당하는 방만 원소를 하나씩 더 받는다.

**검산.** 크기의 합이 $3 + 3 + 2 + 2 = 10 = |A|$다. 분할이면 조각 크기의 합이 전체 크기와 같아야 하므로(14주차 덧셈 원리), 빠뜨린 원소나 중복이 없음을 수로 확인한 것이다.

**복기.** 분할은 "똑같이 나눈다"가 아니라 "빠짐없이 겹침 없이 나눈다"이다. 문제 10의 $[x] = \{x, -x\}$와 $[0] = \{0\}$도 같은 관찰이었다.

### 문제 13

**접근.** $\le$는 반사적$\cdot$추이적이지만 대칭적이 아니다. 그러므로 예제 2.2의 증명에서 대칭성을 쓰는 줄이 유일한 고장 지점이다. (c)에서는 "동치관계가 아니다"로 끝내지 말고, 증명의 네 줄에 $\le$를 대입해 가며 처음 참이 아니게 되는 줄을 특정한다.

**풀이.** (a) $[1] = \{z \in \mathbb{Z} : 1 \le z\} = \{1, 2, 3, 4, \dots\}$이고 $[2] = \{z \in \mathbb{Z} : 2 \le z\} = \{2, 3, 4, 5, \dots\}$이다.

(b) $2 \in [1]$이고 $2 \in [2]$이므로 $[1] \cap [2] \neq \emptyset$이다(실제로 교집합은 $\{2,3,4,\dots\}$로 무한집합이다). 그런데 $1 \in [1]$이고 $1 \notin [2]$($2 \le 1$이 거짓)이므로 $[1] \neq [2]$이다. 따라서 "같거나 서로소"가 성립하지 않는다.

(c) 예제 2.2의 증명을 $\le$에 대입해 한 줄씩 따라간다. 첫 줄 "$z \in [x] \cap [y]$인 $z$가 존재한다"는 참이다($z = 2$). 둘째 줄 "$x \le z$이고 $y \le z$이다"도 참이다 ($1 \le 2$, $2 \le 2$). 셋째 줄 "**대칭성에 의해 $z\,R\,y$이다**"에서 무너진다 — $\le$에는 대칭성이 없으므로 $2 \le 2$에서 얻을 것이 없고, 일반적으로 $z \le y$를 보장할 수 없다($x = 1$, $y = 2$, $z = 5$이면 $5 \le 2$는 거짓이다). 사슬 $x \le z \le y$가 만들어지지 않으므로 넷째 줄의 추이성도 발동하지 못한다.

**복기.** 정의 37.1의 세 성질은 검사 항목이 아니라 정리의 부품이다. 부품 하나를 빼면 그 부품을 쓰던 줄이 그대로 비고, 그 줄이 없으면 결론이 나오지 않는다. 여기서 얻은 겹침은 따름정리의 반례가 아니다 — $\le$는 동치관계가 아니므로 따름정리의 가정을 만족하지 않고, 적용 대상 밖이다(문제 18 앞 상자의 구분).

### 문제 14

**접근.** 앞부분은 새 증명이 아니다. 36주차 문제 19에서 이 관계가 반사$\cdot$대칭$\cdot$추이임이 이미 판정되었으므로, 문제 8의 일반론을 인용하면 분할임이 따라온다. 뒷부분은 동치류 하나를 결정하는 수가 무엇인지 묻는 것이다.

**풀이.** 평면의 점 집합을 $\Pi$라 하고 $P\,R\,Q \iff |OP| = |OQ|$라 하자. 36주차 문제 19에 의해 $R$은 $\Pi$ 위의 동치관계다(조건이 등식이므로 세 성질이 등호에서 상속된다). 따라서 분할 정리(문제 8)에 의해 서로 다른 동치류 전체는 $\Pi$의 분할을 이룬다.

동치류의 정체는 $[P] = \{Q \in \Pi : |OQ| = |OP|\}$이므로, $|OP| = r > 0$이면 $[P]$는 원점 중심 반지름 $r$인 **원**이고, $P$가 원점이면 $[O] = \{O\}$(반지름 0인 조각)이다. 평면은 원점 하나와 원점을 중심으로 하는 동심원들로 빠짐없이 겹침 없이 덮인다.

동치류 하나는 반지름 하나로 완전히 결정되고, 반지름이 다르면 동치류도 다르다. 따라서 동치류 전체의 모임은 **가능한 거리 값들의 집합 $[0, \infty)$와 1:1 대응**한다 — 대응은 $[P] \leftrightarrow |OP|$이다.

**복기.** "동치류들의 집합"을 하나의 새 집합으로 보고 그 집합이 무엇과 대응되는지 묻는 시선이 다음 주의 문법이다. 여기서는 동심원들의 모임이 반지름의 집합과 대응했고, 다음 주에는 mod $n$의 동치류들의 모임 $\mathbb{Z}_n$이 그 자체로 연산의 무대가 된다.

### 문제 15

**접근.** (a) $f(x)$를 "$x^2$을 3으로 나눈 나머지"로 두면 $x\,R\,y \iff f(x) = f(y)$가 되어 문제 10과 같은 구조다 — 세 성질이 등호에서 상속된다. (b) 값이 몇 가지냐가 방이 몇 개냐를 결정한다. 17주차 문제 8이 값의 가짓수를 준다.

**풀이.** (a) $f(x)$를 $x^2$을 3으로 나눈 나머지라 하면, $x^2 \equiv y^2 \pmod 3$은 $f(x) = f(y)$와 같은 뜻이다. (반사) $f(x) = f(x)$이므로 $x\,R\,x$이다. (대칭) $f(x) = f(y)$이면 등식의 양변을 바꿔 $f(y) = f(x)$이므로 $y\,R\,x$이다. (추이) $f(x) = f(y)$이고 $f(y) = f(z)$이면 등식을 이어 $f(x) = f(z)$이므로 $x\,R\,z$이다. 세 성질이 성립하므로 동치관계다.

(b) 17주차 문제 8에 의해 임의의 정수 $n$에 대해 $n^2$을 3으로 나눈 나머지는 0 또는 1뿐이므로 $f$의 값은 두 가지다. 두 값이 실제로 모두 나타난다 — $f(3) = 0$이고 $f(1) = 1$이다. 따라서 방은 $[3]$과 $[1]$의 두 개다. 정체를 적으면, 17주차 문제 8의 경우 나누기에서 $3 \mid n$이면 $n^2 \equiv 0$이고 $3 \nmid n$이면 $n^2 \equiv 1$이었으므로

$$
[3] = \{n \in \mathbb{Z} : 3 \mid n\},\qquad [1] = \{n \in \mathbb{Z} : 3 \nmid n\}
$$

이며 동치류는 **2개**다.

**검산.** $1\,R\,2$인가. $1^2 = 1 \equiv 1$이고 $2^2 = 4 \equiv 1 \pmod 3$이므로 참이다 — $1$과 $2$가 같은 방에 있다. $\equiv \pmod 3$ 자체에서는 $[1] \neq [2]$였는데 여기서는 한 방이다. 관계가 바뀌면 분할도 바뀐다.

**복기.** "어떤 함숫값이 같다"는 꼴의 관계는 항상 동치관계이고, 동치류의 개수는 그 함수가 실제로 취하는 값의 개수와 같다. 문제 10($|x|$), 문제 14($|OP|$), 문제 15 ($x^2 \bmod 3$)가 모두 이 하나의 틀이다. 44주차에서 이 틀이 함수의 언어로 다시 정리된다.

### 문제 16

**접근.** 반사와 대칭은 곱셈의 교환법칙과 등식 뒤집기로 각각 한 줄이다. 추이가 본체다 — 가정 두 식에 공통으로 나오는 문자 $d$를 소거해야 $a, b, e, f$만 남는다. 소거는 나눗셈이 아니라 영인수 성질(문제 16 앞 상자)로 정당화한다. 무대의 조건 $b, d, f \neq 0$이 그 소거의 자격을 준다.

**풀이.** $A = \mathbb{Z} \times (\mathbb{Z} - \{0\})$이고 $(a,b) \sim (c,d) \iff ad = bc$라 하자.

(반사) 임의의 $(a,b) \in A$에 대해 곱셈의 교환법칙에 의해 $ab = ba$이므로 $(a,b) \sim (a,b)$이다.

(대칭) $(a,b) \sim (c,d)$라 하자. 즉 $ad = bc$이다. 목표는 $(c,d) \sim (a,b)$, 곧 $cb = da$이다. 교환법칙과 가정에 의해 $cb = bc = ad = da$이므로 성립한다.

(추이) $(a,b) \sim (c,d)$이고 $(c,d) \sim (e,f)$라 하자. 즉 $ad = bc$이고 $cf = de$이다. 첫 식의 양변에 $f$를 곱하면 $adf = bcf$이다. 여기에 $cf = de$를 대입하면 $bcf = b(cf) = b(de) = bde$이므로 $adf = bde$이다. 이항하면

$$
adf - bde = 0,\qquad \text{곧}\qquad d(af - be) = 0
$$

이다. $(c,d) \in A$이므로 $d \neq 0$이고, 영인수 성질에 의해 $af - be = 0$, 곧 $af = be$이다. 따라서 $(a,b) \sim (e,f)$이다.

세 성질이 모두 성립하므로 $\sim$은 $A$ 위의 동치관계다. $\blacksquare$

**검산.** $(1,2) \sim (2,4)$이고 $(2,4) \sim (3,6)$인지 확인하면 $1 \cdot 4 = 2 \cdot 2$, $2 \cdot 6 = 4 \cdot 3$으로 둘 다 참이고, 추이성이 예측하는 $(1,2) \sim (3,6)$도 $1 \cdot 6 = 2 \cdot 3$으로 참이다.

**복기.** 소거를 "양변을 $d$로 나눈다"로 적으면 정수 세계를 벗어난다. 같은 일을 "이항 $\to$ 인수분해 $\to$ 영인수 성질"의 세 걸음으로 적으면 정수 안에서 끝난다 — 2주차에서 나눗셈 대신 곱셈 등식을 택한 이유가 여기서 다시 회수된다. 이 결과로 예제 2.3의 계산이 정당해지고, $\mathbb{Q}$가 이 동치류들의 집합으로 건설된다. 수 체계가 집합론 위에 서는 자리다.

### 문제 17

**접근.** 관계는 순서쌍의 집합이므로(정의 36.1) 목표 $R = S$는 "모든 $x, y \in A$에 대해 $x\,R\,y \iff x\,S\,y$"와 같다. 핵심 정리가 관계를 동치류의 상등으로 바꾸고, 가정(같은 분할)이 동치류를 조각으로 바꾼다. $\iff$의 사슬을 왼쪽 끝에서 오른쪽 끝까지 잇는다.

**풀이.** $R$과 $S$가 $A$ 위의 동치관계이고, 두 관계가 만드는 분할이 같다고 하자. 즉 $\{[x]_R : x \in A\} = \{[x]_S : x \in A\} = \mathcal{P}$이다. 먼저 각 $x$에 대해 $[x]_R = [x]_S$임을 본다. $x \in [x]_R$이고(반사성), $[x]_R \in \mathcal{P}$이며, 가정에 의해 $[x]_R$은 $S$의 동치류이기도 하다 — 곧 어떤 $w$에 대해 $[x]_R = [w]_S$이다. 그러면 $x \in [w]_S$이므로 $w\,S\,x$이고, 핵심 정리($S$에 적용)에 의해 $[w]_S = [x]_S$이다. 따라서 $[x]_R = [x]_S$이다.

이제 임의의 $x, y \in A$에 대해

$$
x\,R\,y \iff [x]_R = [y]_R \iff [x]_S = [y]_S \iff x\,S\,y
$$

이다. 첫 $\iff$는 핵심 정리($R$에 적용), 가운데 $\iff$는 방금 보인 $[x]_R = [x]_S$와 $[y]_R = [y]_S$의 대입, 마지막 $\iff$는 핵심 정리($S$에 적용)다. 순서쌍의 소속 조건이 모든 $(x,y)$에 대해 동치이므로 두 집합은 같다 — 즉 $R = S$이다. $\blacksquare$

**복기.** 문제 11이 "분할에서 동치관계를 만들 수 있다"를 주고, 문제 17이 "그 대응이 서로 다른 관계를 섞지 않는다"를 준다. 둘을 합치면 동치관계와 분할 사이의 대응이 1:1임이 확정되고, 문제 19에서 동치관계를 셀 때 분할을 세는 것으로 대신할 수 있는 근거가 된다.

### 문제 18

**접근.** 학생의 계산 자체는 정의 37.2를 그대로 적용한 것이라 틀리지 않았다. 그러므로 결함은 계산보다 앞, 정의 37.2를 쓸 **자격**에 있다. 세 성질을 하나씩 검사한다.

**풀이.** 진단: $R$은 **추이적이지 않다**. $(1,2) \in R$이고 $(2,3) \in R$이므로 $1\,R\,2$이고 $2\,R\,3$인데, $(1,3) \notin R$이므로 $1\,R\,3$이 아니다. 사슬은 있는데 지름길이 없다. (반사는 $(1,1),(2,2),(3,3),(4,4)$가 모두 있으므로 성립하고, 대칭도 $(1,2)$와 $(2,1)$, $(2,3)$과 $(3,2)$가 짝을 이루므로 성립한다. 실패하는 항목은 추이 하나다.)

따라서 $R$은 동치관계가 아니고, 정의 37.2의 전제("$A$ 위의 동치관계 $R$")를 만족하지 않는다. 학생이 계산한 세 집합은 $\{z : x\,R\,z\}$라는 식의 값일 뿐 동치류가 아니다.

겹침이 핵심 정리와 모순되지 않는 이유: 핵심 정리와 따름정리는 모두 "$R$이 동치관계일 때"라는 가정 아래의 정리다. 이 $R$은 그 가정을 만족하지 않으므로 정리의 적용 대상이 아니고, 여기서 관찰된 겹침은 정리의 반례가 아니라 가정 위반의 증상이다. 반례가 되려면 가정(동치관계)이 참이면서 결론(같거나 서로소)이 거짓이어야 한다.

**검산.** 결함을 수리해 보면 진단이 확인된다. $(1,3)$과 $(3,1)$을 추가하면 $R$이 추이적이 되어 동치관계가 되고, 그때의 동치류는 $[1] = [2] = [3] = \{1,2,3\}$과 $[4] = \{4\}$로 겹침이 사라진다. 겹침의 원인이 정확히 추이성의 부재였음이 드러난다.

**복기.** 문제 13($\le$, 대칭 부재)과 이 문제($R$, 추이 부재)는 같은 유형이다 — 빠진 성질이 다르고 증상도 다르지만, 진단의 절차는 하나다. ① 세 성질을 검사해 실패 항목을 특정한다 ② 그 실패가 정리의 어느 줄을 비게 하는지 짚는다 ③ 관찰된 이상 현상을 반례가 아니라 가정 위반으로 분류한다.

### 문제 19

**접근.** 빠뜨림 없이 세려면 기준이 필요하다. 조각 크기의 배분으로 경우를 나눈다 — $|A| = 3$이므로 배분은 $3$ / $2+1$ / $1+1+1$의 세 가지뿐이고, 가운데 배분에서만 어느 두 원소를 묶는지의 선택이 남는다.

**풀이.** (배분 $3$) 조각이 하나뿐이므로 $\{a,b,c\}$ 하나다 — 1가지. (배분 $2+1$) 크기 2인 조각에 들어갈 두 원소를 고르면 나머지 하나가 자동으로 정해진다. 세 원소 중 둘을 고르는 방법이 3가지이므로 $\{a,b\},\{c\}$ / $\{a,c\},\{b\}$ / $\{b,c\},\{a\}$ — 3가지. (배분 $1+1+1$) $\{a\},\{b\},\{c\}$ 하나다 — 1가지.

따라서 분할은 $1 + 3 + 1 = $ **5개**다.

이 개수를 동치관계 쪽으로 옮기려면 대응이 1:1임을 확인해야 한다. 문제 8이 동치관계 $R$마다 분할 $\Phi(R) = \{[x]_R : x \in A\}$를 하나 주고, 문제 17이 이 사상 $\Phi$가 **단사**임을 준다(같은 분할을 만드는 두 동치관계는 같다). **전사**성은 문제 11에서 만든 관계 $R_{\mathcal{P}}$의 동치류를 직접 계산하면 나온다 — 임의의 $x \in A$는 조건 ③에 의해 어떤 조각 $P \in \mathcal{P}$에 속하고, 조건 ②에 의해 그런 $P$는 유일하다. 따라서 $x$와 같은 조각에 속하는 원소 전체는 정확히 $P$이고, 곧 $[x]_{R_{\mathcal{P}}} = P$이다. 조각마다 그 안의 원소를 대표원으로 잡으면 조각 전체가 동치류로 회수되므로 $\Phi(R_{\mathcal{P}}) = \mathcal{P}$다. 단사이고 전사이므로 $\Phi$는 1:1 대응이고, $A$ 위의 동치관계도 정확히 **5개**다.

**검산.** 36주차 문제 2의 세는 방식대로 하면 $|A| = 3$일 때 $A$ 위의 관계는 $A \times A$의 부분집합이므로, 4주차의 $|\mathcal{P}(X)| = 2^{|X|}$와 12주차 곱셈 원리에 의해 $2^{3^2} = 2^9 = 512$개다. 그중 동치관계는 5개뿐이다 — 세 성질이 얼마나 강한 제약인지가 수로 드러난다.

**복기.** 집합의 분할 개수를 벨 수(Bell number)라 하고 $B_n$으로 쓴다. 여기서 구한 것은 $B_3 = 5$이며, 크기 4에서는 $B_4 = 15$로 급격히 늘어난다. 세는 문제를 만나면 배분으로 경우를 나누는 것이 12~14주차에서 세운 기본 전략이고, 여기서도 그대로 작동했다.

### 문제 20

**접근.** (a)는 문제 8(관계 $\to$ 분할)과 문제 11(분할 $\to$ 관계), 문제 17(왕복의 일치)을 한 문장으로 압축하는 서술이다. (b)는 "동치류들의 집합을 새 무대로 삼고 그 위에 연산을 얹는다"는 다음 주의 계획을 동치류의 언어로 적는 것이다.

**풀이.** (예시 답안)

(a) 동치관계가 주어지면 동치류를 모아 분할을 얻고(문제 8), 분할이 주어지면 "같은 조각에 속한다"는 관계로 동치관계를 얻는다(문제 11). 이 두 변환은 서로를 정확히 되돌리므로 — 문제 17이 한쪽(같은 분할을 주는 두 동치관계는 같다)을, 문제 19 풀이의 동치류 계산이 다른 쪽($R_{\mathcal{P}}$의 동치류가 다시 $\mathcal{P}$의 조각들이다)을 보인다 — "같음의 기준"과 "그 기준으로 자른 결과"는 같은 정보를 다르게 적은 것이다.

(b) mod $n$의 동치류는 $[0], [1], \dots, [n-1]$의 $n$개이고(문제 2가 $n = 4$의 경우다), 이들을 원소로 삼는 새 집합 $\mathbb{Z}_n = \{[0], [1], \dots, [n-1]\}$ 위에 $[a] + [b] = [a+b]$, $[a][b] = [ab]$ 같은 연산을 정의하면, 원소가 수가 아니라 동치류인 새 산술이 생긴다 — 20주차의 시계 산술이 정식 무대를 얻는 것이다. 다만 방 하나에 이름이 여러 개이므로($[1] = [5] = [-3]$, 문제 2의 mod 4), 연산의 결과가 어느 이름을 골랐느냐에 따라 달라지지 않는지를 먼저 확인해야 한다. 그 확인을 통과해야 위의 정의가 성립한다.

**복기.** (b)에서 지목한 물음 — 대표원을 바꿔도 결과가 같은가 — 이 다음 주의 주제인 "잘 정의됨"이다. 이번 주의 핵심 정리($x\,R\,y \iff [x] = [y]$)가 그 검사의 도구가 된다.

---

**다음 주 예고:** 동치류들의 집합 $\mathbb{Z}_n = \{[0], [1], \dots, [n-1]\}$ 위에 덧셈과 곱셈을 얹는다. 원소가 수가 아니라 집합인 무대에서 연산을 정의하려면 대표원을 골라 계산해야 하는데, 방 하나에 이름이 여러 개이므로 "대표원을 바꿔도 결과가 같은가"라는 검문을 먼저 통과해야 한다. 이것이 **잘 정의됨(well-defined)** 이며, 이후의 모든 주차에서 집합 위에 무언가를 정의할 때마다 되풀이되는 절차다. 검문을 통과한 뒤에는 연산표를 그려 $\mathbb{Z}_6$에서 $[2][3] = [0]$이 되는 현상 — 0이 아닌 두 원소의 곱이 0이 되는 현상 — 을 관찰하고, $n$이 소수일 때와 아닐 때 이 세계가 어떻게 달라지는지 비교한다.