C11주차 — 동치관계: 분할이 꽃피다

이 주의 길잡이

핵심 문장: 관계는 원소 쌍의 이야기이고 분할은 부분집합의 이야기다. 세 성질(반사\(\cdot\)대칭\(\cdot\)추이)을 모두 가진 관계는 각 원소에 동치류라는 조각을 달아 주고, 그 조각들의 모임이 언제나 분할이 된다 — 동치관계와 분할은 같은 것을 양쪽에서 적은 것이다.

이 주의 위치: 2학기 20주 과정의 C11주차. C2주차가 분할을 세 조건으로 세워 놓고 “이것이 어디서 다시 나오는지는 나중에”라고 남겨 둔 자리가 여기다. C6주차의 합동이 이번 주의 대표 사례가 되고, C10주차에서 익힌 판정 걸음은 관계의 세 성질을 하나씩 증명하거나 반증하는 데 그대로 쓰인다. 1권 36~38주차에서 이미 한 번 지나간 소재이지만, 이번에는 조각을 만드는 정의와 조각이 분할이 됨을 보장하는 정리를 한 장 안에서 잇는다.

원서 대응: Chartrand 9장 (Equivalence Relations). 1일차에 이 장을 통독한 상태로 이 교안에 온다.

이번 주 목표

1. 관계를 \(A \times A\)의 부분집합으로 정의하고, 세 성질(반사\(\cdot\)대칭\(\cdot\)추이)을 각각 증명 또는 반례로 판정한다.

2. 동치관계와 동치류 \([a]\)를 정의하고, 세 성질 각각이 분할의 어느 조건을 낳는지 지목한다.

3. 핵심 정리를 양방향으로 증명한다 — 동치관계의 동치류들은 분할을 이루고, 분할은 동치관계를 낳는다.

4. \(\mathbb{Z}_n\)을 동치류 위의 연산으로 세우고, well-defined 검사를 세 걸음으로 실행한다.

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

표기 — § 와 난이도 표시

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

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

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

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

준비 운동 (C10주차 · C2주차 · C6주차 복습)

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

1. C10주차 §1.2의 Prove-or-Disprove 네 걸음(정찰 \(\cdot\) 추측 \(\cdot\) 결단 \(\cdot\) 수리)을 쓰시오.

2. C2주차 정의 2.3의 분할 세 조건(비공집합 \(\cdot\) 쌍마다 서로소 \(\cdot\) 덮음)과 §1.6의 분할 판정 네 걸음을 재현하시오.

3. C6주차 정의 6.2의 합동(\(a \equiv b \pmod n \iff n \mid (a-b)\))을 쓰고, 1권 20주차의 (C1)(C2)(C3)이 각각 무엇이었는지 적으시오.

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

1. (진단) \(\mathbb{Z}\) 위의 관계 “\(a \mathrel{R} b \iff a - b\)가 짝수”를 생각하자. 이

관계는 \(\mathbb{Z}\)의 정수들을 몇 개의 무리로 갈라놓는가. 그리고 그 무리들의 모임은 C2주차 정의 2.3의 분할인가. 두 물음에 각각 근거를 대어 답하시오.

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

자주 나오는 세 가지 답

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

• 유형 1 — 무리의 개수만 적는다. “짝수 전체와 홀수 전체, 두 무리”라고 적고

멈춘다. 개수는 옳고, 두 무리의 정체도 정확하다. 문제는 둘째 물음이 남았다는 것이다. 관계는 순서쌍에 대한 조건이고 분할은 부분집합들의 모임이므로, 둘은 서로 다른 층위의 대상이다. 관계에서 부분집합을 만들어 내는 절차가 있어야 두 물음이 이어지고, 그 절차가 §1.4의 동치류다.

• 유형 2 — 세 성질만 확인하고 멈춘다. 반사\(\cdot\)대칭\(\cdot\)추이를 각각 증명하고 “그러므로

이 관계는 특별하다”까지 적었으나 분할 물음에는 손대지 못한다. 확인한 것은 정확히 필요한 검사이고, 이 셋이 이번 주 정리의 가정 전부다. 빠진 것은 세 성질에서 분할까지 가는 길이 자동이 아니라 증명해야 할 정리라는 인식이다 — 그 정리가 §1.5이고, 증명의 핵심 부품은 예제 2.2다.

• 유형 3 — 무엇을 물었는지 잡히지 않는다. 관계와 분할이 서로 다른 층위의

대상이라 두 물음을 한 문장으로 잇지 못하고 아무것도 적지 못했다. 층위가 다르다는 판단 자체는 옳다. 그 두 층위를 잇는 다리가 이번 주의 소재 전부이며, §1.1이 다리 없이 밀어붙이면 어디서 막히는지부터 보인다.

개념 — 관계가 무대를 자른다

1 분할 판정 네 걸음만으로 밀어붙이면 어디서 막히는가

새 도구를 꺼내기 전에, 지금 가진 것(C2주차의 분할 판정 네 걸음)만으로 실제로 밀어붙여 본다.

시도 1 — 판정 절차를 그대로 적용하기

명제: \(\mathbb{Z}\) 위의 관계 “\(a \mathrel{R} b \iff 3 \mid (a-b)\)”는 \(\mathbb{Z}\)를 분할한다.

“C2주차 §1.6의 네 걸음을 실행한다. 걸음 ⓪ 층위 확인 — 판정할 모임

\(\mathcal{S}\)의 각 원소가 \(\mathbb{Z}\)의 부분집합인지 본다. 그런데 \(\mathcal{S}\)가

무엇인지 적혀 있지 않다. 주어진 것은 관계 하나뿐이고 조각들의 목록은 … “

여기서 멈춘다. 판정할 대상 자체가 없다.

시도 2 — 조각을 손으로 만들어 본 뒤

“조각이 없으면 만들면 된다. \(0\)과 관계 맺는 정수를 모으면

\(\{\ldots, -3, 0, 3, 6, \ldots\}\)이고, \(1\)에서 모으면 \(\{\ldots, -2, 1, 4, \ldots\}\),

\(2\)에서 모으면 \(\{\ldots, -1, 2, 5, \ldots\}\)이다. 세 개가 나왔다. 그런데 \(4\)에서

모으면 \(\{\ldots, -2, 1, 4, 7, \ldots\}\)로 둘째 것과 같은 집합이다. 출발 원소는

정수만큼 많은데 서로 다른 조각은 몇 개인가. 그리고 두 조각이 겹치면서 서로 다른

일이 일어나지 않는다고 무엇이 보장하는가 … “

여기서도 멈춘다. 만든 조각들이 분할이 된다는 보장이 없다.

확인 1. 두 시도가 막힌 이유는 서로 다르다. 각각 무엇이 없어서 막혔는가.

답

시도 1에는 판정할 대상이 없다. C2주차의 네 걸음은 조각들의 모임이 이미

주어졌을 때 그것이 분할인지 검사하는 절차이고, 관계에서 조각을 만들어 내는

절차가 아니다. 판정 도구는 생성 도구가 아니다.

시도 2는 조각을 만들었으나 그 모임이 분할이라는 보장이 없다. 세 조각이

서로소인 것은 이 사례에서 눈으로 확인했을 뿐이고, 임의의 관계에서 같은 일이

일어난다는 근거는 아직 없다. 실제로 관계에 따라서는 조각이 겹치면서 서로 다를

수 있고, 그런 사례를 §1.3에서 실제로 만든다.

빠진 것은 두 가지다 — 관계에서 조각을 만드는 정의와, 그렇게 만든 조각들이

분할이 됨을 보장하는 정리. 그 정리의 가정이 세 성질이다.

이 주 전체의 기준

관계는 원소 쌍의 이야기이고 분할은 부분집합의 이야기다.

두 층위를 잇는 다리가 동치류이고, 다리가 놓이는 조건이 세 성질이다.

2 사례를 모아 보기 — 세 성질이 갈리는 관계들

익숙한 관계들을 한 표에 놓고 세 성질을 매긴다. 성립하면 ✓, 성립하지 않으면 ✗와 반례를 적는다. 빈칸을 채워 보자.

관계	무대	반사	대칭	추이
\(a = b\)	\(\mathbb{Z}\)	✓	✓	✓
\(a \le b\)	\(\mathbb{Z}\)	✓	✗ (\(1 \le 2\)이나 \(2 \not\le 1\))	✓
\(a < b\)	\(\mathbb{Z}\)	✗ (\(1 < 1\)이 거짓)	✗	✓
\(a \mid b\)	\(\mathbb{Z}\)	✓	\(\underline{\quad(1)\quad}\)	✓
\(a \equiv b \pmod 2\)	\(\mathbb{Z}\)	\(\underline{\quad(2)\quad}\)	\(\underline{\quad(3)\quad}\)	\(\underline{\quad(4)\quad}\)
\(a - b \in \mathbb{Z}\)	\(\mathbb{R}\)	✓	✓	✓

확인 2. (1)~(4)를 채우고, 표의 여섯 관계 중 §1.1 시도 2처럼 무대를 겹침 없는 조각으로 자르는 것이 어느 것인지 골라 보자. 고른 기준을 한 줄로 적는다.

답

(1) ✗ — \(2 \mid 4\)이나 \(4 \nmid 2\)이다. (2) ✓ — \(a - a = 0\)이고 \(2 \mid 0\)이다.

(3) ✓ — \(2 \mid (a-b)\)이면 \(b - a = -(a-b)\)도 \(2\)의 배수다. (4) ✓ — \(2 \mid (a-b)\)이고

\(2 \mid (b-c)\)이면 \(a - c = (a-b) + (b-c)\)도 \(2\)의 배수다.

무대를 자르는 것은 첫째\(\cdot\)다섯째\(\cdot\)여섯째 행, 곧 세 칸이 모두 ✓인 관계다.

\(=\)는 정수를 한 개짜리 조각들로, \(\equiv \pmod 2\)는 짝수와 홀수 두 조각으로,

\(a - b \in \mathbb{Z}\)는 실수를 소수부가 같은 것끼리 묶은 조각들로 자른다.

✗가 하나라도 있는 \(\le\), \(<\), \(\mid\)에서는 겹침 없는 조각내기가 나오지 않는다.

이 관찰에 이름과 형식을 붙인다. 식 자체에 새로운 것은 없다 — 세 성질의 정의는 1권 36주차에서 이미 쓴 것 그대로이고, 합동에 대해서는 1권 20주차의 (C1)(C2)(C3)이 같은 세 줄이었다. 1권에서 관계마다 따로 확인하던 세 칸이 여기서 “동치관계”라는 하나의 이름을 얻는다.

정의 11.1 — 관계 (relation) [백지 암기 대상]

집합 \(A\)에 대해, \(A\) 위의 관계 \(R\)은 곱집합 \(A \times A\)의 부분집합이다.

\((a, b) \in R\)일 때 \(a \mathrel{R} b\)로 적는다.

표기 — \(A \times A\) 와 \(a \mathrel{R} b\)

\(A \times A\)는 “에이 크로스 에이”로 읽고, \(A\)의 원소로 만든 순서쌍 전체의 집합이다

(C6주차 정의 6.3). \(a \mathrel{R} b\)는 “에이 알 비”로 읽고 “\(a\)와 \(b\)가 \(R\)-관계에

있다”는 뜻이다. 관계가 부분집합이므로 “\(R\)에 어떤 순서쌍이 들어 있는가”를 정하면

관계가 정해진다 — \(\le\)나 \(\mid\) 같은 익숙한 기호도 전부 이 뜻의 부분집합이다.

정의 11.2 — 관계의 세 성질 [백지 암기 대상]

\(A\) 위의 관계 \(R\)에 대해,

① 반사적(reflexive): 모든 \(a \in A\)에 대해 \(a \mathrel{R} a\)이다.

② 대칭적(symmetric): 모든 \(a, b \in A\)에 대해, \(a \mathrel{R} b\)이면 \(b \mathrel{R} a\)이다.

③ 추이적(transitive): 모든 \(a, b, c \in A\)에 대해, \(a \mathrel{R} b\)이고 \(b \mathrel{R} c\)이면 \(a \mathrel{R} c\)이다.

세 성질은 전부 \(\forall\) 명제이므로 판정 방법이 정해져 있다. 성립을 보이려면 선택법으로 임의의 원소를 잡아 증명하고, 성립하지 않음을 보이려면 반례 하나를 C7주차 §1.4의 4단 서식으로 제시한다. 성질의 부정은 각각 다음과 같다 — “반사적이 아니다”는 “\(a \not\mathrel{R} a\)인 \(a\)가 존재한다”, “대칭적이 아니다”는 “\(a \mathrel{R} b\)이고 \(b \not\mathrel{R} a\)인 쌍 \((a,b)\)가 존재한다”, “추이적이 아니다”는 “\(a \mathrel{R} b\)이고 \(b \mathrel{R} c\)이면서 \(a \not\mathrel{R} c\)인 세 원소 \(a, b, c\)가 존재한다”이다.

정의 11.3 — 동치관계 (equivalence relation) [백지 암기 대상]

\(A\) 위의 관계 \(R\)이 반사적이고 대칭적이고 추이적이면 \(R\)을 \(A\) 위의 동치관계라 한다.

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

정의 11.3은 세 조각(세 성질)으로 되어 있고, 조각마다 §1.5의 정리에서 맡는 역할이 다르다. 셋째 열은 이번 주의 목적지인 분할의 세 조건과 짝을 이룬다.

임시 표기 — \(C(a)\)

아래에서는 조각을 만들어 놓고 이야기해야 하는데, 조각의 정식 이름과 기호는

§1.4에서 세운다. 그때까지는 임의의 관계 \(R\)와 \(a \in A\)에 대해

\(C(a) = \{x \in A : x \mathrel{R} a\}\)로 적고 “\(a\)의 조각”이라 읽는다.

\(R\)가 동치관계가 아니어도 이 집합은 그대로 만들어진다 — 아래 삭제 실험이

그런 경우다. \(R\)가 동치관계일 때 이 집합이 동치류라는 이름과 기호 \([a]\)를

얻는다(정의 11.4).

조각	하는 일	증명에서의 역할
반사적	모든 원소를 자기 조각 안에 넣는다	분할 조건 ①(비공집합)과 ③(덮음)을 동시에 준다 — \(a \in C(a)\)이므로 어느 조각도 비어 있지 않고 어느 원소도 빠지지 않는다
대칭적	조각에 속한다는 관계의 방향을 지운다	두 조각이 한 원소를 공유할 때 그 원소를 양쪽으로 되돌려 보내는 줄에서 쓰인다 (예제 2.2의 셋째 줄)
추이적	관계를 이어 붙인다	공유 원소를 통해 한 조각의 원소 전부를 다른 조각으로 옮긴다 — 대칭과 함께 분할 조건 ②(쌍마다 서로소)를 만드는 두 부품 중 하나이며, 이어 붙이는 쪽이다

조각 삭제 실험 (가) — 반사를 빼면. \(A = \{1,2,3\}\) 위의 관계 \(R = \{(1,1), (2,2), (1,2), (2,1)\}\)을 보자. 대칭적이고 추이적이지만 \(3 \mathrel{R} 3\)이 없으므로 반사적이 아니다. 이 관계로 조각을 만들면 \(C(1) = C(2) = \{1,2\}\)이고 \(3\)과 관계 맺는 원소가 하나도 없어 \(C(3) = \emptyset\)이며, \(3\)은 어느 조각에도 들어가지 못한다. 분할 조건 ①과 ③이 함께 무너진다. 조건 ②는 살아 있다는 점도 함께 봐 둔다 — 비어 있지 않은 조각은 \(\{1,2\}\) 하나뿐이므로 겹치면서 다른 두 조각이 생길 수 없다. 반사가 떠받치는 것은 ①과 ③이고 ②가 아니다.

조각 삭제 실험 (나) — 추이를 빼면. \(A = \{1,2,3\}\) 위의 관계 \(R = \{(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2)\}\)을 보자. 반사적이고 대칭적이지만 \(1 \mathrel{R} 2\)이고 \(2 \mathrel{R} 3\)인데 \(1 \not\mathrel{R} 3\)이므로 추이적이 아니다. 조각을 만들면 \(C(1) = \{1,2\}\), \(C(2) = \{1,2,3\}\), \(C(3) = \{2,3\}\)이다. 첫째와 셋째가 \(2\)를 공유하는데 서로 다르다 — §1.1 시도 2가 걱정한 그 상황이 실제로 일어난다. (1권 37주차 문제 18은 여기에 원소 \(4\)와 순서쌍 \((4,4)\)를 더한 \(A = \{1,2,3,4\}\) 위의 같은 꼴 관계로 같은 결함을 진단시킨다. 무대가 하나 넓어진 만큼 \(C(4) = \{4\}\)가 조각 목록에 더 붙는다.)

조각 삭제 실험 (다) — 대칭을 빼면. \(A = \{1,2,3\}\) 위의 \(\le\)를 보자. 반사적이고 추이적이지만 대칭적이 아니다. 조각을 \(C(a) = \{x \in A : x \le a\}\)로 만들면 \(C(1) = \{1\}\), \(C(2) = \{1,2\}\), \(C(3) = \{1,2,3\}\)이다. \(C(1)\)과 \(C(2)\)가 \(1\)을 공유하는데 서로 다르므로 역시 조건 ②가 무너진다. (1권 37주차 문제 13이 같은 실험을 \(\mathbb{Z}\) 위에서, 조각의 방향을 반대로 잡아 \(\{z : x \le z\}\)로 시킨다 — 무대가 무한이라 조각도 무한집합이 되지만 무너지는 조건은 같다.)

확인 3. 세 실험 중 (나)와 (다)는 같은 조건(②)을 무너뜨렸다. 그렇다면 대칭과 추이 가운데 하나만 있으면 되는가. 두 실험을 비교해 답해 보자.

답

하나만으로는 되지 않는다. (나)는 대칭이 있고 추이가 없는 사례, (다)는 추이가

있고 대칭이 없는 사례이며 둘 다 조건 ②가 무너졌다. 곧 ②는 대칭과 추이가

함께 있을 때에만 보장된다.

이유는 예제 2.2의 증명 순서에서 드러난다. 공유 원소 \(c\)에서 얻는 정보는

\(c \mathrel{R} a\)와 \(c \mathrel{R} b\)인데, 추이를 쓰려면 화살의 방향이

\(a \mathrel{R} c\), \(c \mathrel{R} b\)로 이어져야 한다. 방향을 뒤집는 것이 대칭이고,

이어 붙이는 것이 추이다. 어느 한쪽이 없으면 그 줄이 나오지 않는다.

확인 4. 세 성질과 분할의 세 조건을 대응시켜 보자. 조건 ①(비공집합)은 \(\underline{\quad}\)에서, 조건 ②(서로소)는 \(\underline{\quad}\)에서, 조건 ③(덮음)은 \(\underline{\quad}\)에서 온다.

답

① 반사 / ② 대칭과 추이 / ③ 반사.

반사가 두 조건을 혼자 감당하는 것은 \(a \in C(a)\)라는 한 줄이 “각 조각에 원소가

있다”와 “각 원소가 조각을 가진다”를 동시에 말하기 때문이다. 같은 한 줄을 조각

쪽에서 읽으면 ①, 원소 쪽에서 읽으면 ③이 된다.

4 동치류 — 관계에서 조각을 만드는 정의

§1.1에서 손으로 하던 일(”\(a\)와 관계 맺는 원소를 전부 모은다”)에 이름을 붙인다.

정의 11.4 — 동치류 (equivalence class) [백지 암기 대상]

\(A\) 위의 동치관계 \(R\)과 \(a \in A\)에 대해, \(a\)의 동치류는

\[ [a] = \{x \in A : x \mathrel{R} a\} \]

이다. \(a\)를 이 동치류의 대표원이라 한다.

§1.3에서 임시로 \(C(a)\)로 적었던 집합이 이것이다. 식은 글자 그대로 같고, 달라진 것은 자격이다 — \(R\)가 동치관계일 때에만 이 집합을 동치류라 부르고 기호 \([a]\)를 쓴다. 삭제 실험의 \(\le\)처럼 동치관계가 아닌 관계에서도 조각은 만들어지지만, 그 조각들에는 아래의 정리 11.1이 적용되지 않는다.

표기 — \([a]\)

\([a]\)는 “브래킷 에이” 또는 “에이의 동치류”로 읽는다. 대괄호 안에 적힌 것은

원소이고 \([a]\) 자체는 집합이므로, \(a \in [a]\)는 옳은 문장이지만

\(a = [a]\)는 층위가 어긋난 문장이다. 어느 관계에 대한 동치류인지 헷갈릴 수 있는

자리에서는 \([a]_R\)로 적는다.

동치류는 대표원을 바꿔도 같은 집합이 될 수 있다. §1.1 시도 2에서 \(1\)에서 만든 조각과 \(4\)에서 만든 조각이 같았던 것이 그 현상이다. 언제 같아지는지를 정확히 말하는 것이 다음 보조정리이며, 이번 주 계산의 대부분이 이 한 줄에서 나온다.

정리 11.1 — 동치류의 세 조건 [백지 암기 대상]

\(R\)이 \(A\) 위의 동치관계이고 \(a, b \in A\)이면 다음 셋은 서로 동치다.

① \(a \mathrel{R} b\) ② \([a] = [b]\) ③ \([a] \cap [b] \neq \emptyset\)

세 조건이 동치라는 말은, 두 동치류에 대해 같거나 서로소 두 경우밖에 없다는 뜻이다. 겹치는 순간 통째로 같아진다. ③에서 ②로 가는 방향이 예제 2.2이고, 나머지 두 방향이 문제 8이다.

확인 5. \(\mathbb{Z}\) 위의 \(\equiv \pmod 5\)에 대해 \([3]\)의 원소를 다섯 개 적고, \([3] = [8]\)인지 \([3] = [4]\)인지를 정리 11.1로 판정해 보자.

답

\([3] = \{x \in \mathbb{Z} : x \equiv 3 \pmod 5\}\)이므로 \(-7, -2, 3, 8, 13\) 등이 원소다.

\([3] = [8]\)이다 — 정리 11.1의 ①에서 ②로 가는 방향을 쓰면 되고, \(8 - 3 = 5\)이므로

\(5 \mid (8-3)\), 곧 \(3 \equiv 8 \pmod 5\)이기 때문이다.

\([3] \neq [4]\)이다 — ②가 참이면 ①도 참인데, \(4 - 3 = 1\)이고 \(5 \nmid 1\)이므로

\(3 \not\equiv 4 \pmod 5\)이다. 대우로 \([3] \neq [4]\)가 나온다.

두 판정 모두 원소를 하나하나 대조하지 않고 대표원 사이의 관계 한 줄로

끝났다는 점이 정리 11.1을 쓰는 이유다.

5 핵심 정리 — 동치관계와 분할의 왕복

§1.1에서 없다고 한 두 도구 중 정의는 §1.4에서 얻었다. 남은 것은 보장이다.

정리 11.2 — 동치관계에서 분할로 [백지 암기 대상]

\(A\)가 공집합이 아니고 \(R\)이 \(A\) 위의 동치관계이면 동치류들의 모임 \(\{[a] : a \in A\}\)는 \(A\)의 분할이다.

① 비공집합 — 반사에 의해 \(a \in [a]\)이므로 각 동치류는 공집합이 아니다.

② 쌍마다 서로소 — 정리 11.1에 의해 두 동치류는 같거나 서로소다.

③ 덮음 — 각 \(a \in A\)가 \([a]\)에 속하므로 동치류들의 합집합이 \(A\)다.

정리 11.3 — 분할에서 동치관계로 [백지 암기 대상]

\(A\)가 공집합이 아니고 \(\mathcal{S}\)가 \(A\)의 분할이면, “\(a \mathrel{R} b \iff a\)와 \(b\)가 \(\mathcal{S}\)의 같은 조각에 속한다”로 정의한 \(R\)은 \(A\) 위의 동치관계이고, 그 동치류들의 모임은 정확히 \(\mathcal{S}\)다.

두 정리 모두 무대에 “공집합이 아닌”이라는 조건이 붙는다. C2주차 정의 2.3이 분할을 공집합이 아닌 집합에 대해서만 정의하기 때문이고, \(A = \emptyset\)이면 동치류들의 모임도 공집합이어서 애초에 정의 2.3의 적용 대상이 아니다.

두 정리를 나란히 두면 대응이 보인다. 동치관계를 주면 정리 11.2가 분할을 내놓고, 분할을 주면 정리 11.3이 동치관계를 내놓으며, 한 바퀴 돌면 처음 것으로 돌아온다. C2주차가 분할을 세 조건으로 세워 놓고 남겨 둔 자리가 여기서 채워진다.

확인 6. 정리 11.3의 증명에서 반사\(\cdot\)대칭\(\cdot\)추이를 각각 보이려면 분할의 세 조건 중 무엇이 필요한가. 반사부터 생각해 보자.

답

반사에는 조건 ③(덮음)이 필요하다. \(a \mathrel{R} a\)를 말하려면 먼저 \(a\)가 어떤

조각에 속해 있어야 하는데, 그것을 주는 것이 덮음이다. 조각이 없으면 “같은

조각에 속한다”가 성립할 수 없다.

대칭에는 아무 조건도 필요 없다. “\(a\)와 \(b\)가 같은 조각에 속한다”는 진술 자체가

\(a\)와 \(b\)에 대칭이기 때문이다.

추이에는 조건 ②(서로소)가 필요하다. \(a, b\)가 조각 \(X\)에, \(b, c\)가 조각 \(Y\)에

속한다고 하면 \(b \in X \cap Y\)이므로 서로소 조건에 의해 \(X = Y\)이고, 그래야

\(a\)와 \(c\)가 같은 조각에 있다고 말할 수 있다. 서로소가 없으면 \(b\)가 두 조각에

걸쳐 있을 수 있어 이 줄이 나오지 않는다.

확인 6의 세 문단이 정리 11.3의 전반부 증명이다. 남은 것은 후반부 — 그렇게 얻은 \(R\)의 동치류들의 모임이 정확히 \(\mathcal{S}\)라는 주장이다. 이 부분도 여기서 끝내 둔다. \(a \in A\)를 잡으면 덮음에 의해 \(a\)가 속하는 조각 \(X \in \mathcal{S}\)가 있고, 서로소에 의해 그런 조각은 하나뿐이다. 이제 \([a] = X\)를 보인다. \(x \in [a]\)인 것은 \(x \mathrel{R} a\)인 것이고, 이는 정의에 의해 \(x\)가 \(a\)와 같은 조각에 속한다는 것이며, \(a\)가 속한 조각이 \(X\)뿐이므로 \(x \in X\)와 같은 말이다. 양쪽이 서로를 포함하므로 \([a] = X\)이고, 따라서 \(\{[a] : a \in A\} \subseteq \mathcal{S}\)이다. 거꾸로 \(X \in \mathcal{S}\)를 잡으면 비공집합 조건에 의해 원소 \(a \in X\)가 있고, 방금 보인 것에 의해 \([a] = X\)이므로 \(X \in \{[a] : a \in A\}\)이다. 양방향 포함에 의해 두 모임이 같다. \(\blacksquare\)

분할의 세 조건이 전부 소비되었다는 점을 짚어 둔다 — 덮음은 조각을 찾는 데, 서로소는 그 조각이 하나뿐임을 말하는 데, 비공집합은 반대 방향 포함에서 대표원을 꺼내는 데 쓰였다. 문제 11이 같은 논증을 \(\mathcal{S} = \{E, O\}\)라는 구체 분할에서 다시 밟는다.

6 \(\mathbb{Z}_n\) — 동치류 위에 연산을 얹는 절차

동치류는 집합이므로 그 자체를 원소로 삼는 새 무대를 만들 수 있다. 합동에서 그렇게 만든 무대가 \(\mathbb{Z}_n\)이다.

정의 11.5 — \(\mathbb{Z}_n\) (integers modulo n) [백지 암기 대상]

양의 정수 \(n\)에 대해, \(\equiv \pmod n\)의 동치류 전체의 집합을

\(\mathbb{Z}_n = \{[0], [1], \ldots, [n-1]\}\)로 적는다. 그 위의 두 연산은

\([a] + [b] = [a+b]\), \([a] \cdot [b] = [ab]\)로 정의한다.

표기 — \(\mathbb{Z}_n\)

“제트 엔”으로 읽는다. 원소가 정수가 아니라 정수의 집합이라는 점이 이

표기의 전부다. 일반적으로 \([n-1] + [1] = [n] = [0]\)처럼 마지막에 대표원을 \(0\)부터

\(n-1\) 사이로 바꿔 적는 것이 관례이고, 그렇게 바꿔 적어도 같은 집합이다.

법을 밝히지 않으면 되돌린 결과를 읽을 수 없다 — \([3] + [4] = [7] = [2]\)는

\(\mathbb{Z}_5\)에서의 계산이고, \(\mathbb{Z}_6\)에서라면 \([7] = [1]\)이다.

목록이 정확히 \(n\)개인 근거는 나눗셈 정리다. 임의의 정수 \(a\)에 대해 \(a = nq + r\), \(0 \le r < n\)인 \(q, r\)이 존재하므로(1권 33주차 예제 2.2) \(a \equiv r\)이고 목록이 전부를 덮으며, 그 \(r\)이 유일하므로(1권 33주차 문제 10) 목록에 중복이 없다. 자세한 논증은 문제 13에서 적는다.

정의 11.5에서 새로 생긴 위험이 하나 있다. 연산의 결과가 대표원을 통해 정의되어 있다는 것이다. \([2] = [7]\)인 \(\mathbb{Z}_5\)에서 \([2] + [3]\)을 계산할 때 왼쪽 대표원으로 \(2\)를 쓰느냐 \(7\)을 쓰느냐에 따라 결과가 갈린다면, 정의 11.5는 정의가 아니라 서로 모순되는 여러 규칙의 묶음이 된다. 이 위험을 검사하는 절차가 S19주차 정의 19.3 (well-defined의 뜻)과 그 아래에 따로 놓인 검사 서식의 세 걸음이며, 그 세 걸음을 해부하면 다음과 같다.

백지 암기 대상

well-defined 검사 세 걸음

① 두 표현 잡기 — 같은 대상의 두 표현을 임의로 잡는다: \([a] = [a']\), \([b] = [b']\).

② 표현의 같음을 등식으로 풀기 — 동치류의 같음을 대표원 사이의 등식으로 번역한다: \(n \mid (a - a')\), \(n \mid (b - b')\).

③ 값의 같음을 유도하기 — 정의가 주는 두 값이 같음을 ②에서 유도한다: \([a+b] = [a'+b']\).

걸음	하는 일	이 걸음을 빼면 무엇이 무너지는가
① 두 표현 잡기	검사할 대상을 무대에 올린다	대표원이 하나뿐인 것처럼 계산하게 된다. 위험 자체가 보이지 않으므로 검사가 시작되지 않는다
② 등식으로 풀기	집합의 같음을 계산 가능한 형태로 바꾼다	“\([a] = [a']\)이므로 결과도 같다”라는 순환이 된다 — 증명해야 할 것을 근거로 쓴 것이다
③ 값의 같음 유도	정의가 실제로 정의임을 확정한다	대표원마다 다른 값이 나오는 규칙이 정의로 통과한다 (아래 삭제 실험)

걸음 삭제 실험 — 걸음 ③을 건너뛴 규칙. \(\mathbb{Z}_6\)에서 “짝수 대표원을 반으로 나눈다”는 규칙 \(f([2k]) = [k]\)를 정의라고 부르고 걸음 ③ 없이 쓰면 어떻게 되는지 보자(1권 38주차 문제 13이 이 계산을 시킨다). \([2]\)와 \([8]\)은 \(6 \mid (8-2)\)이므로 같은 동치류인데, 왼쪽 표현으로 계산하면 \(f([2]) = [1]\)이고 오른쪽 표현으로 계산하면 \(f([8]) = [4]\)이다. \(6 \nmid (4-1)\)이므로 \([1] \neq [4]\)이다.

확인 7. 위 규칙이 정의로 통과했다고 하면 무엇을 유도할 수 있는가. 그 결과가 왜 이론 전체를 무너뜨리는지 한 줄로 적어 보자.

답

\([2] = [8]\)이고 \(f\)가 함수라면 \(f([2]) = f([8])\)이어야 하므로 \([1] = [4]\)가

유도된다. 그런데 \(\mathbb{Z}_6\)에서 \([1] \neq [4]\)이므로 같은 무대 안에서

참인 문장과 그 부정을 동시에 얻게 된다.

모순이 하나 들어오면 그 뒤로는 무엇이든 유도할 수 있으므로 무대의 어떤 계산도

신뢰할 수 없게 된다. 걸음 ③은 형식적 절차가 아니라 무대를 지키는 걸음이다.

반대로 정의 11.5의 덧셈과 곱셈은 이 검사를 통과하며, 그 증명이 예제 2.3과

문제 9다.

확인 8. \(\mathbb{Z}_4\)에서 \([3] + [3]\)과 \([3] \cdot [3]\)을 계산하고, 왼쪽 \([3]\)을 \([7]\)로 바꿔 다시 계산해 결과를 대조해 보자.

답

\([3] + [3] = [6] = [2]\)이고 \([3] \cdot [3] = [9] = [1]\)이다.

\([7] + [3] = [10] = [2]\)이고 \([7] \cdot [3] = [21] = [1]\)이다.

두 계산이 일치한다. 일치가 우연이 아님을 보장하는 것이 well-defined 검사이고,

검사를 통과했으므로 \(\mathbb{Z}_4\)에서는 어느 대표원을 골라 계산해도 된다.

1권과의 대응. 1권 38주차가 “방의 이름이 여러 개”라고 부르며 감각으로 다루던 사정이 여기서 대표원의 선택이라는 이름을 얻고, 그때마다 하던 확인이 S19주차의 세 걸음 서식으로 굳는다. 서식이 있으면 새 연산을 만날 때 무엇을 적어야 하는지가 정해진다.

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

허용 목록은 1권 이래 네 줄이다: ① 정의 ② 닫힘성 ③ 등식\(\cdot\)부등식의 성질 ④ 이미 증명한 명제. 이번 주가 채우는 것은 ①과 ④다.

근거	이번 주에 추가\(\cdot\)갱신되는 것	이번 주에는 이렇게 쓴다
① 정의	정의 11.1~11.5(관계 \(\cdot\) 세 성질 \(\cdot\) 동치관계 \(\cdot\) 동치류 \(\cdot\) \(\mathbb{Z}_n\))	“동치류의 정의에 의해 \(x \mathrel{R} a\)이다”처럼 집합 표기와 관계 사이를 번역한다
② 닫힘성	변화 없음	정수의 합\(\cdot\)차\(\cdot\)곱이 정수임을 별도 설명 없이 쓴다
③ 등식\(\cdot\)부등식의 성질	변화 없음	집합의 상등은 양방향 포함으로 보인다는 1권 27주차의 서식이 예제 2.2에서 그대로 쓰인다
④ 이미 증명한 명제	정리 11.1(세 조건의 동치 — 예제 2.2와 문제 8이 증명) \(\cdot\) 정리 11.2(문제 15가 증명) \(\cdot\) 정리 11.3(§1.5 확인 6과 그 아래 문단이 증명) \(\cdot\) 합동의 (C1)~(C5)(1권 20주차) \(\cdot\) 나눗셈 정리의 존재와 유일(1권 33주차 예제 2.2, 문제 10) \(\cdot\) 유클리드 보조정리(1권 33주차 문제 16에서 인정하고 쓴 것) \(\cdot\) 분할의 세 조건(C2주차 정의 2.3)	“정리 11.1에 의해 \([a] = [b]\)이다”가 이번 주 답안의 표준 문구가 된다

well-defined 검사와 분할 판정 네 걸음은 절차이지 근거가 아니다. 답안의 구조를 정하는 데만 쓰고 “서식에 의해”라고 인용하지 않는다.

확인 9. 어떤 답안에 다음 두 문장이 나왔다. 각각 허용되는가. 허용된다면 몇 번 근거인가.

(가) “\([a] \cap [b] \neq \emptyset\)이므로 \([a] = [b]\)이다.”

(나) “\(\mathbb{Z}_5\)에서 \([2] + [3] = [0]\)임을 \([7] + [3] = [10] = [0]\)으로도 확인했으므로 덧셈은 well-defined이다.”

답

(가) 허용 — 근거 ④. 정리 11.1의 ③에서 ②로 가는 방향이고, 인용할 때 정리

번호를 밝힌다. 단 \(R\)이 동치관계라는 것이 답안 어딘가에 확인되어 있어야 한다.

이 방향을 떠받치는 것은 대칭과 추이이고, 둘 중 하나가 없으면 §1.3의 삭제 실험

(나)\(\cdot\)(다)가 곧바로 반례를 준다.

(나) 불허 — 목록 밖이다. 두 대표원 쌍에서 값이 일치한 것은 사례 확인이며,

C10주차 §1.5의 비대칭에 따라 통과는 아무것도 확정하지 않는다. well-defined는

임의의 두 표현에 대한 \(\forall\) 명제이므로 걸음 ①에서 대표원을 문자로 잡아야 한다.