# 36주차 · 강의 — 예제 · 연습 · 해설 ## 예제 — 성질 판정을 함께 만들기 완성된 판정을 먼저 보이지 않는다. 설계부터 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다. ### 예제 2.1 — 성적표 만들기: 나누어떨어짐 **명제.** $\mathbb{N}$ 위의 관계 $\mid$ 는 반사적$\cdot$추이적이지만 대칭적이지 않다. **설계 — 쓰기 전에 정하는 것.** 성질 판정에서는 세 항목마다 출발점과 도착점이 따로 있다. 명제가 항목별 결론까지 이미 알려 주므로, 항목마다 §1.7의 표에서 어느 열을 쓸지 먼저 고른다. | **항목** | **주장** | **출발점** | **도착점** | |---|---|---|---| | 반사 | 성립 | 임의의 $n \in \mathbb{N}$ | $n \mid n$ | | 대칭 | 불성립 | 없음 (반례를 고른다) | $\underline{\quad(?)\quad}$ | | 추이 | 성립 | $a \mid b$, $b \mid c$ | $a \mid c$ | :::{container} quotebox **확인 11.** 대칭 행의 도착점 빈칸을 채워 보자. §1.7의 완전 서식대로, 무엇을 몇 개 제시하고 무엇을 확인해야 하는가. ::: :::{admonition} 답 :class: quotebox dropdown 구체적인 수 두 개 $a_0, b_0$ 한 벌을 제시하고, $a_0 \mid b_0$가 참임과 $b_0 \nmid a_0$가 참임을 각각 정의 2.1로 확인하는 것이 도착점이다. 성립 항목은 문자로 시작하고, 불성립 항목은 구체적인 수로 시작한다 — 이 방향의 차이가 판정의 전부다. ::: **1단계 — 반사.** 도착점은 $n \mid n$이고, 정의 2.1에 따르면 이것은 "$n = n \times (\text{정수})$"를 만드는 일이다. :::{container} quotebox **확인 12.** 반사 판정의 한 줄을 완성해 보자: "임의의 $n \in \mathbb{N}$에 대해 $n = n \cdot \underline{\quad}$이고 $\underline{\quad} \in \mathbb{Z}$이므로 $n \mid n$이다." ::: :::{admonition} 답 :class: quotebox dropdown $n = n \cdot 1$이고 $1 \in \mathbb{Z}$이므로 $n \mid n$이다. 2주차 문제 1(e)에서 $3 \mid 3$을 판정한 계산을 문자로 일반화한 것이다. $n$을 특정 숫자로 잡지 않았으므로 "모든 $x$"라는 조각이 채워진다. ::: **2단계 — 추이.** 도착점은 "$a \mid b$이고 $b \mid c$이면 $a \mid c$"이다. :::{container} quotebox **확인 13.** 이 문장을 위해 새 증명을 써야 하는가. 아니라면 무엇을 인용하는가. ::: :::{admonition} 답 :class: quotebox dropdown 새 증명이 필요 없다. 정확히 2주차 예제 2.1의 명제다 — 근거 ④로 인용하면 끝난다. 30주 전에 "추이성"이라는 제목으로 증명해 둔 정리가 이번 주에 와서 **성질의 이름표**를 받는 것이다. ::: **3단계 — 대칭 불성립.** 완전 서식 세 조각을 갖춘다. :::{container} quotebox **확인 14.** 반례를 $a_0 = 2$, $b_0 = 4$로 잡았다. 세 조각을 완성해 보자. ① 제시: $\underline{\qquad}$ ② 가정 확인: $4 = 2 \cdot \underline{\quad}$이고 그 수가 정수이므로 $2 \mid 4$ ✓ ③ 결론 부정 확인: $2 = 4c$인 $\underline{\qquad}$가 없으므로 $4 \nmid 2$ ✓ ::: :::{admonition} 답 :class: quotebox dropdown ① $a_0 = 2$, $b_0 = 4$. ② $4 = 2 \cdot 2$이고 $2 \in \mathbb{Z}$이므로 $2 \mid 4$. ③ $2 = 4c$인 **정수** $c$가 없다 ($c = \frac12$은 정수가 아니다). 따라서 $4 \nmid 2$. 이 한 벌로 "모든 $x, y$"라는 조각이 깨지므로 대칭은 불성립이다. ::: **완성본.** 방금 만든 세 판정을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 "왜?"에 스스로 답해 본다. | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | (반사) 임의의 $n \in \mathbb{N}$에 대해 $n = n \cdot 1$이고 $1 \in \mathbb{Z}$이므로 $n \mid n$이다. ✓ | 성립 주장이므로 $\forall$ 증명이다 — 특정 숫자가 아니라 문자 $n$으로 시작한다(근거 ①). | | (추이) $a \mid b$이고 $b \mid c$라 가정하자. 2주차 예제 2.1에 의해 $a \mid c$이다. ✓ | 조건문 증명이고, 몸통은 이미 증명된 정리다(근거 ④). 새 계산이 필요 없다. | | (대칭) 반례: $2$와 $4$. $4 = 2 \cdot 2$이므로 $2 \mid 4$이고, $2 = 4c$인 정수 $c$가 없으므로 $4 \nmid 2$이다. ✗ | 불성립은 반례 하나로 끝난다 — 29주차의 완전 서식(제시 + 가정 확인 + 결론 부정 확인). | | 따라서 $\mathbb{N}$ 위의 $\mid$는 반사적$\cdot$추이적이고 대칭적이지 않다. $\blacksquare$ | 세 판정을 명제의 진술과 대조해 종합한다. | 이 네 줄로 §1.8 성적표의 $\mid$ 행이 전부 채워졌다. ### 예제 2.2 — 합동: 세 성질 전부 **명제.** $\mathbb{Z}$ 위의 관계 $\equiv \pmod n$은 반사적$\cdot$대칭적$\cdot$추이적이다. 이번에는 설계만 함께 하고, 판정은 완성된 산문으로 본다. :::{container} quotebox **확인 15.** 세 항목이 각각 20주차의 어느 성질이고, 그 주의 어느 문제에서 이미 증명되었는지 짝지어 보자. 반사 $\to$ $\underline{\qquad}$ / 대칭 $\to$ $\underline{\qquad}$ / 추이 $\to$ $\underline{\qquad}$ ::: :::{admonition} 답 :class: quotebox dropdown 반사 $\to$ (C1), 20주차 문제 4 ($n \mid (a - a) = 0$). 대칭 $\to$ (C2), 20주차 문제 5 ($n \mid (a-b)$이면 $n \mid (b-a)$). 추이 $\to$ (C3), 20주차 문제 7 (두 배수의 합). 세 항목의 도착점이 전부 이미 증명된 명제와 문장까지 같다 — 그러므로 이번 주에 할 일은 계산이 아니라 **대응시키기**다. ::: **증명.** 반사성은 (C1)이다: 20주차 문제 4에서 $n \mid (a - a)$, 곧 $a \equiv a \pmod n$이 모든 정수 $a$에 대해 증명되었다. 대칭성은 (C2)이다: 20주차 문제 5에서 $a \equiv b \pmod n$이면 $b \equiv a \pmod n$임이 증명되었다. 추이성은 (C3)이다: 20주차 문제 7에서 $a \equiv b$이고 $b \equiv c$이면 $a \equiv c \pmod n$임이 증명되었다. 세 항목이 모두 성립하므로 $\equiv \pmod n$은 반사적$\cdot$대칭적$\cdot$추이적이다. $\blacksquare$ **관찰.** 새 증명이 한 줄도 필요하지 않았다. 개념(관계의 성질)이 생기자 **이미 가진 정리들이 제자리를 찾은 것**이다. 20주차에서는 (C1)~(C3)이 합동 하나에만 붙은 성질 세 개였고, 지금은 임의의 관계에 던질 수 있는 질문 세 개가 되었다. 개념이 하는 일 중 하나가 이런 재조직이다. ### 예제 2.3 — 유한 관계: 그림으로 판정 $A = \{1, 2, 3\}$ 위의 관계 $R = \{(1,1), (2,2), (3,3), (1,2), (2,1)\}$의 세 성질을 판정하시오. 이번에는 설계부터 스스로 해 보자. :::{container} quotebox **확인 16.** 판정을 시작하기 전에 정할 것 세 가지를 적어 보자. ① 반사를 확인하려면 어느 순서쌍들이 $R$에 있는지 보아야 하는가. ② 대칭을 확인하려면 무엇과 무엇을 짝지어야 하는가. ③ 추이를 확인하려면 무엇을 전수 점검해야 하는가. ::: :::{admonition} 답 :class: quotebox dropdown ① $(1,1), (2,2), (3,3)$ — 대각선 세 칸이다. ② $R$의 각 순서쌍 $(x,y)$마다 짝 $(y,x)$가 $R$에 있는지 본다. 대각선 원소는 짝이 자기 자신이므로 자동으로 통과하고, 실제로 볼 것은 $(1,2)$와 $(2,1)$이다. ③ $R$ 안의 두 칸짜리 사슬 $x \to y \to z$를 전부 훑고, 각각에 지름길 $(x,z)$가 있는지 본다. ::: **풀이.** 격자표로 그리면 대각선 세 칸이 모두 ✓이고, 그 밖에 1행 2열과 2행 1열이 ✓다. 화살표 그림으로는 세 점 모두에 자기 고리가 있고 1과 2 사이에 왕복 화살표가 있다. (반사) $A$의 원소는 $1, 2, 3$이고 $(1,1), (2,2), (3,3)$이 모두 $R$에 있으므로 모든 $x \in A$에 대해 $x\,R\,x$이다 ✓. (대칭) $(1,1), (2,2), (3,3)$은 짝이 자기 자신이므로 $R$에 있다. $(1,2)$의 짝 $(2,1)$도, $(2,1)$의 짝 $(1,2)$도 $R$에 있다. 모든 원소가 짝을 가지므로 대칭적이다 ✓. (추이) 두 칸짜리 사슬을 전수 점검한다. 대각선을 거치는 사슬($x \to x \to y$ 또는 $x \to y \to y$)은 지름길이 사슬의 한 변과 같으므로 자동으로 성립한다. 남는 것은 대각선이 아닌 두 변으로 된 사슬 둘뿐이다. $1 \to 2 \to 1$은 지름길 $(1,1)$을 요구하고 $R$에 있으며, $2 \to 1 \to 2$는 $(2,2)$를 요구하고 $R$에 있다 ✓. 셋 다 성립하므로 $R$은 반사적$\cdot$대칭적$\cdot$추이적이다. $\blacksquare$ **포인트.** 유한 관계의 추이 판정은 "두 칸 사슬 전수 점검"이다. 특히 **왕복 사슬 ($x \to y \to x$)이 자기 고리($x \to x$)를 요구**한다는 것이 가장 자주 놓치는 지점이다. 이 지점만 따로 떼어 낸 것이 문제 8이다. ### 관찰 — 같은 뼈대 예제 2.1, 2.2, 2.3은 소재도 무대도 다르지만 절차가 같다. 대응표의 빈칸을 채워 보자. :::{container} quotebox **확인 17.** 세 예제에서 각 단계에 해당하는 일을 찾아 보자. ① 무대와 관계를 확정하기: 예제 2.1에서는 $\underline{\qquad}$ ② 성립을 주장하는 항목의 처리: 예제 2.1의 반사에서는 $\underline{\qquad}$ ③ 불성립을 주장하는 항목의 처리: 예제 2.1의 대칭에서는 $\underline{\qquad}$ ::: :::{admonition} 답 :class: quotebox dropdown ① "$\mathbb{N}$ 위의 관계 $\mid$" — 무대가 바뀌면 칸이 달라질 수 있다(문제 14). ② 문자 $n$을 잡고 정의로 $n \mid n$을 유도했다 — $\forall$ 증명이다. ③ 구체적인 수 $2, 4$를 잡고 완전 서식으로 반례를 제시했다 — 반증이다. 예제 2.2는 ②만 세 번(전부 인용으로), 예제 2.3은 ②만 세 번(전수 점검으로) 수행한 것이다. ::: 방금 확인한 뼈대에 이름을 붙인다. :::{admonition} 백지 암기 대상 :class: keybox **성질 판정의 3단 절차** ① 무대 $A$와 관계 $R$의 소속 조건을 확정한다 $\to$ ② 항목마다 성립$\cdot$불성립을 먼저 정한다 $\to$ ③ 성립이면 $\forall$$\cdot$조건문 증명, 불성립이면 반례 완전 서식으로 마감한다. ::: 이 절차는 다음 주 동치관계 판정과 39주차 종합에서 그대로 재사용된다. ## 빈칸 사다리 — 지지대를 하나씩 빼며 필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다. ### 훈련 1 ●○○ — 수식 빈칸 **명제.** $\mathbb{R}$ 위의 관계 $x\,R\,y \iff x - y \in \mathbb{Z}$는 반사적$\cdot$대칭적$\cdot$추이적이다. **증명.** (반사) 임의의 $x \in \mathbb{R}$에 대해 $x - x = \underline{\quad(1)\quad}$이고 이것은 정수이므로 $x\,R\,x$이다 ✓. (대칭) $x\,R\,y$라 가정하자. $x - y \in \mathbb{Z}$이고, $y - x = \underline{\quad(2)\quad}$도 정수(정수의 $(-1)$배)이므로 $y\,R\,x$이다 ✓. (추이) $x\,R\,y$, $y\,R\,z$라 가정하자. $x - z = (x - y) + \underline{\quad(3)\quad}$는 정수의 합이므로 정수이고, 따라서 $\underline{\quad(4)\quad}$이다 ✓. $\blacksquare$ 이 관계는 "소수 부분이 같다"는 관계다: $0.5\,R\,3.5$가 참이고, $\pi\,R\,(\pi - 7)$도 참이다. 다음 주 동치류에서 다시 만난다. ### 훈련 2 ●●○ — 수식과 근거를 함께 이번에는 구조 낱말과 근거 문장도 빈칸이다. **명제.** $\mathbb{Z}$ 위의 관계 $x\,R\,y \iff x + y = 10$은 대칭적이지만, 반사적이지도 추이적이지도 않다. **증명.** (대칭) $x\,R\,y$라 $\underline{\quad(1)\quad}$하자. 그러면 $x + y = 10$이고, 덧셈의 $\underline{\quad(2)\quad}$에 의해 $y + x = x + y = 10$이므로 $y\,R\,x$이다 ✓. (반사) 반례로 $x = \underline{\quad(3)\quad}$을 잡는다. 이때 $x + x = \underline{\quad(4)\quad} \ne 10$이므로 $x \not R x$이다. 반사성은 $\underline{\quad(5)\quad}$ $x$에 대한 요구이므로 이 한 개의 실패로 불성립이 확정된다 ✗. (추이) 반례 사슬: $1\,R\,9$ ($1 + 9 = 10$ ✓)이고 $9\,R\,1$ ($9 + 1 = 10$ ✓)인데, $1 + 1 = \underline{\quad(6)\quad} \ne 10$이므로 $\underline{\quad(7)\quad}$이다 ✗. $\blacksquare$ ### 훈련 3 ●●● — 뼈대만 남기고 이번에는 3단 절차의 각 칸을 통째로 채운다. **명제.** $\mathbb{Z}$ 위의 관계 $x\,R\,y \iff 5 \mid (2x + 3y)$는 반사적$\cdot$대칭적$\cdot$추이적이다. **판정의 뼈대.** - ① 무대와 관계 확정, 세 항목 모두 성립을 주장한다는 선언: $\underline{\quad(1)\quad}$ - ② 반사: $\underline{\quad(2)\quad}$ - ③ 대칭: $\underline{\quad(3)\quad}$ (항등식 $2y + 3x = 5(x + y) - (2x + 3y)$를 쓴다) - ④ 추이: $\underline{\quad(4)\quad}$ (항등식 $(2x + 3y) + (2y + 3z) = (2x + 3z) + 5y$를 쓴다) (이 훈련이 문제 13의 예행연습이다 — 계수와 법만 바뀐다.) ## 연습문제 (20문항) 해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 '접근'까지만 읽고 다시 시도한다 $\to$ 그래도 안 되면 풀이를 읽는다. :::{admonition} 이번 주의 채점 기준 :class: quotebox 답이 아니라 **근거**가 점수다. "$\mid$는 대칭이 아니다(맞음)"는 0점이고, "$4 = 2 \cdot 2$이므로 $2 \mid 4$이고, $2 = 4c$인 정수 $c$가 없으므로 $4 \nmid 2$ — 따라서 대칭이 아니다"가 만점이다. 성질 판정의 답안은 항목마다 두 가지를 갖춰야 한다: ① 성립$\cdot$불성립의 선언 ② 성립이면 $\forall$$\cdot$조건문 증명, 불성립이면 반례 완전 서식. 난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다. ::: ### 기본 ●○○ **1.** [백지] 관계의 정의($R \subseteq A \times A$)와 세 성질(반사$\cdot$대칭$\cdot$추이)의 정의를 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown 세 성질은 전부 "모든 ~에 대해"로 시작한다. 대칭과 추이에는 그 뒤에 조건("~이면")이 하나 더 붙는다는 것까지 적었는지 확인한다. ::: **2.** $A = \{1, 2\}$ 위의 관계는 모두 몇 개인가? (힌트: 관계 = $A \times A$의 부분집합 — 4주차 멱집합 세기.) :::{admonition} 힌트 :class: quotebox dropdown 세는 대상은 "관계"가 아니라 "$A \times A$의 부분집합"이다. 먼저 $|A \times A|$를 구하고, 원소가 $m$개인 집합의 부분집합 개수(4주차)를 쓴다. ::: **3.** $A = \{1, 2, 3\}$ 위의 관계 $R = \{(1,2), (2,3), (1,3)\}$을 화살표 그림으로 그리고 세 성질을 판정하시오. :::{admonition} 힌트 :class: quotebox dropdown 반사와 대칭은 각각 반례 하나로 끝난다 — 비어 있는 대각선 칸, 짝이 없는 순서쌍을 찾는다. 추이는 두 칸 사슬이 몇 개인지부터 센다. ::: **4.** $\mathbb{Z}$ 위의 $\le$에 대해: 반사$\cdot$추이가 성립함을 증명하고, 대칭이 아님을 반례로 보이시오. :::{admonition} 힌트 :class: quotebox dropdown $x \le y$를 "$y - x \ge 0$"으로 바꿔 놓으면 추이가 "음이 아닌 두 수의 합은 음이 아니다"로 환원된다. ::: **5.** 빈칸 훈련($x - y \in \mathbb{Z}$)을 백지에서 완성하시오. :::{admonition} 힌트 :class: quotebox dropdown 세 항목 모두 도착점이 "어떤 차가 정수임을 보인다"이고, 쓰는 근거는 ② 닫힘성 하나뿐이다 — 정수의 $(-1)$배와 정수끼리의 합. ::: **6.** 예제 2.1($\mid$의 성적표)을 백지에 재현하시오. :::{admonition} 힌트 :class: quotebox dropdown 세 줄이다. 반사는 $n = n \cdot 1$, 추이는 2주차 예제 2.1 인용, 대칭은 $2$와 $4$의 완전 서식. 인용 문구까지 그대로 적었는지 확인한다. ::: ### 표준 ●●○ **7.** $\mathbb{Z}$ 위의 $<$에 대해 세 성질을 판정하시오 (각각 증명 또는 반례). :::{admonition} 힌트 :class: quotebox dropdown 반사부터 의심한다 — $x < x$가 참인 $x$가 하나라도 있는가. 추이는 $y - x$와 $z - y$가 자연수임을 쓰면 닫힘성으로 닫힌다. ::: **8.** $A = \{1, 2, 3\}$ 위의 $R = \{(1,2), (2,1)\}$에 대해: (a) 대칭임을 확인하시오. (b) 추이가 **아님**을 반례 사슬로 보이시오 (어떤 순서쌍이 빠져 있는가?). (c) 추이가 되도록 최소한의 순서쌍을 추가한다면 무엇 무엇인가? :::{admonition} 힌트 :class: quotebox dropdown $1 \to 2 \to 1$이라는 사슬을 실제로 따라가 본다. 이 사슬이 요구하는 지름길의 출발점과 도착점이 같다는 것이 이 문제의 전부다. ::: **9.** $\mathbb{R}$ 위의 관계 $x\,R\,y \iff |x - y| \le 1$에 대해 세 성질을 판정하시오. :::{admonition} 힌트 :class: quotebox dropdown 반사와 대칭은 절댓값의 성질로 즉시 닫힌다. 추이는 "거리 1과 거리 1을 이으면 거리가 얼마까지 벌어지는가"를 수직선에 그려 본다. ::: **10.** $\mathbb{Z}$ 위의 관계 $x\,R\,y \iff x + y$가 짝수 — 세 성질을 판정하시오. (이 관계의 정체는? 25주차 문제 9$\cdot$17과 연결하라) :::{admonition} 힌트 :class: quotebox dropdown 세 항목을 각각 새로 증명해도 되지만, 25주차 문제 17이 이 조건을 합동식으로 바꿔 준다. 바꾸고 나면 예제 2.2가 그대로 적용된다. ::: **11.** $\mathcal{P}(\{1,2,3\})$ 위의 $\subseteq$에 대해: 반사$\cdot$추이 성립을 증명하고(4주차 정리 인용 가능), 대칭 불성립을 반례로 보이시오. **12.** $\mathbb{N}$ 위의 관계 $x\,R\,y \iff$ "$x$와 $y$가 서로소"($\gcd$ 언어 없이: 공통 약수가 1뿐)에 대해 세 성질을 판정하시오. (반사부터 의심할 것 — $x = 1$과 $x = 2$를 구분해 보라) :::{admonition} 힌트 :class: quotebox dropdown $x$와 $x$의 공통 약수에는 $x$ 자신이 들어 있다. $x = 2$에서 이 관찰이 무엇을 뜻하는지 적고, §1.6 실험 A의 문장과 대조한다. ::: **13.** $\mathbb{Z}$ 위의 관계 $x\,R\,y \iff 3 \mid (x + 2y)$가 반사적$\cdot$대칭적$\cdot$추이적임을 증명하시오. (대칭 힌트: $y + 2x = 3(x + y) - (x + 2y)$; 추이 힌트: $(x + 2y) + (y + 2z) = (x + 2z) + 3y$) :::{admonition} 힌트 :class: quotebox dropdown 훈련 3과 같은 구조다. 문제에 딸린 항등식은 "구하려는 식 = (3의 배수) $\pm$ (가정으로 아는 3의 배수)" 꼴이므로, 2주차 문제 7(배수의 차)로 닫힌다. ::: **14.** 실수 전체에서 $x\,R\,y \iff xy > 0$의 세 성질을 판정하시오. 무대를 $\mathbb{R} - \{0\}$으로 좁히면 판정이 어떻게 달라지는가? :::{admonition} 힌트 :class: quotebox dropdown 반사는 $x \cdot x = x^2 > 0$인지 묻는 것이고, 이 부등식이 깨지는 $x$는 정확히 하나다. 무대에서 그 하나를 빼면 무엇이 달라지는지 본다. ::: ### 도전 ●●● :::{admonition} 되살리는 개념 — 공허한 참 (4$\cdot$8주차) :class: quotebox "$P$이면 $Q$이다" 꼴의 문장은 $P$가 거짓인 경우에 아무 조건 없이 참이 된다. 대칭과 추이의 정의가 정확히 이 꼴이므로, **관계 맺은 짝이 하나도 없는 원소** 앞에서 두 성질은 검사할 것이 없어 자동으로 통과한다. 반사에는 이 통로가 없다 — 조건 없이 "모든 $x$에서 $x\,R\,x$"를 요구하기 때문이다. 이 비대칭이 문제 15의 함정을 만든다. ::: **15.** (유명한 함정) 다음 '증명'의 오류를 해부하시오. :::{container} quotebox "주장: 대칭적이고 추이적인 관계는 반사적이다. 증명: $x R y$라 하자. 대칭성에 의해 $y R x$이다. 추이성을 $x R y$와 $y R x$에 적용하면 $x R x$이다. 따라서 반사적이다. $\blacksquare$" ::: 그리고 실제 반례(대칭$\cdot$추이지만 반사가 아닌 관계)를 하나 제시하시오. (힌트: 첫 문장 "$x R y$라 하자"에서 그런 $y$의 **존재**를 누가 보장하는가? 공허한 관계 또는 일부 원소가 고립된 관계를 시도하라) :::{admonition} 힌트 :class: quotebox dropdown 논증이 실제로 결론짓는 문장을 정확히 적어 본다: "$x\,R\,y$인 $y$가 존재하는 $x$에 대해 $x\,R\,x$이다." 반사성이 요구하는 문장과 나란히 놓으면 간격이 보인다. ::: **16.** $\mathbb{Z}$ 위의 관계 $x\,R\,y \iff x \equiv y \pmod 2$ **그리고** $x \equiv y \pmod 3$을 생각하자. (a) 이 관계가 반사$\cdot$대칭$\cdot$추이적임을 증명하시오 (각 성질이 "그리고"로 묶인 두 조건에 각각 성립함을 이용). (b) $x R y \iff x \equiv y \pmod 6$임을 증명하시오 (25주차 문제 12). :::{admonition} 힌트 :class: quotebox dropdown (a)는 18주차의 $\land$ 결론 서식이다 — 두 부분을 각각 마감한 뒤 "따라서 둘 다 성립한다"로 묶는다. (b)는 두 조건을 $x - y$에 대한 나누어떨어짐으로 바꾼 뒤 25주차 문제 12를 그대로 대입한다. ::: :::{admonition} 이 문제가 되살리는 도구 — 곱셈 원리 (12주차) :class: quotebox 문제 17은 관계를 세는 문제다. 관계가 $A \times A$의 부분집합이므로, 관계를 하나 정하는 일은 $A \times A$의 칸마다 "넣는다 / 안 넣는다"를 정하는 일이다. 칸이 $m$개이면 선택이 $m$번이고 각 선택이 2택이므로 곱셈 원리에 의해 $2^m$가지다 (4주차의 $|\mathcal{P}(A)| = 2^n$이 이 논증이었다). 반사성이 강제하는 칸은 그 선택에서 빠진다. ::: **17.** 관계 $R$이 $A$ 위에서 반사적일 때, $R$의 순서쌍 개수의 최솟값은? $|A| = n$일 때 반사적 관계의 총 개수를 세시오. (힌트: 대각선 $n$쌍은 강제, 나머지 $n^2 - n$쌍은 자유 — 12주차 곱셈 원리) :::{admonition} 이 문제가 만드는 새 관계 — 뒤집기 :class: quotebox 관계는 집합이므로, 집합을 재료로 새 집합을 만드는 연산을 관계에도 쓸 수 있다. 문제 18의 $R^{-1}$이 그런 연산의 첫 사례다 — 모든 순서쌍의 좌우를 바꿔 만든 새 관계이고, 정의는 문제 안에 주어져 있다. 43주차 역함수가 이 연산의 특수한 경우로 등장한다. ::: **18.** "역관계" $R^{-1} = \{(y, x) : (x, y) \in R\}$를 정의하자. (a) $R$이 대칭적 $\iff R = R^{-1}$임을 증명하시오. (b) $\mathbb{Z}$ 위의 $<$의 역관계는 무엇인가? :::{admonition} 힌트 :class: quotebox dropdown (a)는 집합의 상등이므로 27주차의 양방향 포함으로 간다. 그리고 $\iff$이므로 방향이 둘이다 — 25주차의 서식대로 ($\Rightarrow$)와 ($\Leftarrow$)를 나눠 적는다. ::: **19.** 다음 관계의 세 성질을 판정하시오: 평면의 점들 위에서 $P\,R\,Q \iff$ "$P$와 $Q$는 원점에서 같은 거리에 있다". 이 관계로 평면이 어떤 조각들로 나뉘는지 기하적으로 묘사하시오 (다음 주 동치류의 예고). :::{admonition} 힌트 :class: quotebox dropdown 조건을 등식 $|OP| = |OQ|$로 적고 나면, 세 성질이 전부 등호의 성질로 환원된다. 조각 묘사는 "원점에서 거리가 $r$인 점 전체"가 무엇인지 답하면 된다. ::: **20.** (서술) (a) "관계는 순서쌍들의 집합"이라는 정의가 "$<$를 정의하라"는 요구에 어떻게 답하는지 두 문장 이내로. (b) 세 성질 판정이 30주차 "증명 또는 반증" 모드의 특수형인 이유를 한 문장으로. ## 백지 재현 — 복습 프로토콜 권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 재현은 두 번으로 나눈다. 한 번에 완전 백지로 가지 않는다. **1차 시도 (4일차) — 틀 카드 허용.** 성질 판정의 3단 절차(§2 관찰)와 근거 목록(§1.9)만 펴 놓고, 예제 2.1($\mid$의 성적표)을 처음부터 끝까지 적는다. 정의와 본문은 보지 않는다. **2차 시도 (5일차) — 완전 백지.** 아무것도 보지 않고 수행한다. - [ ] 관계의 정의($R \subseteq A \times A$)와 세 성질의 정의를 "모든 ~에 대해"라는 조각까지 그대로 썼다. - [ ] 성적표($=$, $\le$, $<$, $\mid$, $\equiv$, $\subseteq$)를 재현하고 각 칸의 근거를 댈 수 있다. - [ ] 예제 2.1을 백지에 재현했고, 대칭 반례에 완전 서식 세 조각을 갖췄다. - [ ] 예제 2.2에서 새 증명이 필요 없었던 이유를 한 문장으로 설명했다. - [ ] 왕복 사슬 함정(문제 8)과 "대칭+추이이면 반사" 함정(문제 15)을 각각 해부했다. - [ ] 유한 관계의 그림 판정(대각선$\cdot$왕복$\cdot$지름길)을 격자표로 한 번 수행했다. **막힌 지점별 처방.** 막힌 지점이 무엇을 다시 볼지 알려 준다. | **막힌 지점** | **처방** | |---|---| | "$<$가 집합"이라는 말이 낯설다 | §1.2 — 순서쌍을 하나씩 심사해 모으는 표부터 다시 채운다 | | 정의 36.2가 정확히 기억나지 않는다 | §1.6 해부 표 — "모든"과 조건부의 역할과 함께 다시 외운다 | | 성립$\cdot$불성립 중 무엇을 쓸지 모르겠다 | §1.7의 표 — 항목마다 열을 먼저 고른 뒤 시작한다 | | 반례를 찾았는데 답안이 짧다 | §1.7 완전 서식 — 제시 + 가정 확인 + 결론 부정 확인 | | 추이 점검에서 무엇을 볼지 모르겠다 | 예제 2.3 — 두 칸 사슬 전수 점검, 특히 왕복 사슬 | | 무대가 바뀌면 왜 답이 달라지는지 모르겠다 | §1.3의 첫 조각과 문제 14 | 하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다. ## 해설 각 해설은 **접근**(문제 앞에서 무엇을 생각하는가)과 **풀이**로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다. ### 빈칸 사다리 — 훈련 1 (1) $0$ (2) $-(x - y)$ (3) $(y - z)$ (4) $x\,R\,z$ ※ 세 항목이 전부 근거 ② 닫힘성 하나로 닫힌다. (1)에서 $0$이 정수임을 명시해야 반사가 완결되고, (2)에서 "정수의 $(-1)$배는 정수"를 적어야 대칭이 완결된다. ### 빈칸 사다리 — 훈련 2 (1) 가정 (2) 교환법칙 (3) $1$ (5가 아닌 정수면 무엇이든 된다) (4) $2$ (5) 모든 (6) $2$ (7) $1 \not R 1$ ※ (5)가 이 훈련의 핵심이다. $5\,R\,5$가 참인데도 반사가 불성립인 이유는 정의의 조각이 "어떤"이 아니라 "모든"이기 때문이다(§1.6 실험 A). 이 관계는 대칭만 가진 관계의 표본이고, 문제 15에서 다시 필요한 감각이다. ### 빈칸 사다리 — 훈련 3 (1) $\mathbb{Z}$ 위의 관계 $R$를 $x\,R\,y \iff 5 \mid (2x + 3y)$로 둔다. 세 항목 모두 성립을 주장하므로 셋 다 $\forall$ 또는 조건문 증명으로 간다. (2) (반사) 임의의 $x \in \mathbb{Z}$에 대해 $2x + 3x = 5x$이고 $5x = 5 \cdot x$, $x \in \mathbb{Z}$이므로 $5 \mid (2x + 3x)$, 곧 $x\,R\,x$이다. (3) (대칭) $x\,R\,y$라 가정하자. 곧 $5 \mid (2x + 3y)$이다. 항등식 $2y + 3x = 5(x + y) - (2x + 3y)$에서 $5 \mid 5(x+y)$이고 $5 \mid (2x + 3y)$이므로 두 배수의 차도 5의 배수다(2주차 문제 7). 따라서 $5 \mid (2y + 3x)$, 곧 $y\,R\,x$이다. (4) (추이) $x\,R\,y$이고 $y\,R\,z$라 가정하자. 두 배수의 합은 배수이므로(2주차 예제 2.2) $5 \mid \big((2x + 3y) + (2y + 3z)\big)$이고, 항등식에 의해 그 값은 $(2x + 3z) + 5y$이다. $5 \mid 5y$이므로 차를 취하면 $5 \mid (2x + 3z)$, 곧 $x\,R\,z$이다. $\blacksquare$ ※ 세 항등식이 전부 "구하려는 식 $=$ (명백한 5의 배수) $\pm$ (가정으로 아는 5의 배수)" 꼴이다. 이 꼴만 만들면 나머지는 2주차의 합$\cdot$차 정리가 끝낸다. 문제 13은 계수가 $(1, 2)$이고 법이 3인 같은 문제다. ### 문제 1 **접근.** 개념 절의 재현이다. 채점 포인트는 세 곳이다 — 관계의 정의에서 "$A \times A$의 부분집합"이라는 조각, 세 성질 전부의 "모든 ~에 대해"라는 조각, 그리고 대칭$\cdot$추이가 **조건문**이라는 구조다. **풀이.** 집합 $A$ 위의 관계 $R$란 $A \times A$의 부분집합이다: $R \subseteq A \times A$. $(x, y) \in R$일 때 $x\,R\,y$로 쓴다. 그리고 $A$ 위의 관계 $R$에 대해 — 반사적: 모든 $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$이다. **복기.** 반사만 조건 없는 $\forall$ 문장이고 대칭$\cdot$추이는 $\forall$ 안에 조건문이 들어 있다. 이 구조 차이가 그대로 판정 방법의 차이가 되고(§1.7), 문제 15의 함정도 여기서 나온다. ### 문제 2 **접근.** 세는 대상을 바꿔 읽는 것이 전부다. "관계의 개수"는 정의 36.1에 의해 "$A \times A$의 부분집합의 개수"와 같은 말이고, 부분집합 세기는 4주차의 $|\mathcal{P}(X)| = 2^{|X|}$이다. 그러므로 먼저 $|A \times A|$를 구한다. **풀이.** $A = \{1, 2\}$이므로 $A \times A = \{(1,1), (1,2), (2,1), (2,2)\}$이고 $|A \times A| = 2 \cdot 2 = 4$이다(6주차의 $|A \times B| = |A| \cdot |B|$). 관계는 $A \times A$의 부분집합이므로 관계의 개수는 $|\mathcal{P}(A \times A)| = 2^{4} = 16$, 곧 **16개**다. **검산.** 곱셈 원리로 직접 세도 같다 — 네 칸 각각에 2택이 있으므로 $2^4 = 16$이다. **복기.** 관계를 "집합"으로 정의해 두면 세기 도구(3부)가 즉시 작동한다. 문제 17이 이 세기에 반사성이라는 제약을 하나 얹은 문제다. ### 문제 3 **접근.** 그림부터 그린다. 화살표는 $1 \to 2$, $2 \to 3$, $1 \to 3$ 세 개이고 자기 고리는 없다. 반사와 대칭은 불성립이 눈에 보이므로 반례 하나씩으로 끝내고, 추이는 두 칸 사슬을 세어 전수 점검한다. **풀이.** 화살표 그림: 점 1, 2, 3을 찍고 $1 \to 2$, $2 \to 3$, $1 \to 3$을 그린다. 자기 고리는 없고 왕복도 없다. (반사) ✗. 반례: $x_0 = 1$. $1 \in A$이다. $(1,1) \notin R$이므로 $1 \not R 1$이고, 반사성은 모든 $x$를 요구하므로 불성립이다. (대칭) ✗. 반례: $(1,2)$. $1\,R\,2$는 참인데($(1,2) \in R$) $(2,1) \notin R$이므로 $2 \not R 1$이다. (추이) ✓. 두 칸 사슬은 $1 \to 2 \to 3$ 하나뿐이다(2에서 나가는 화살표는 $2 \to 3$뿐이고, 3에서 나가는 화살표는 없다). 이 사슬이 요구하는 지름길 $(1,3)$이 $R$에 있으므로 추이적이다. $\blacksquare$ **복기.** 이 관계는 $\{1,2,3\}$ 위의 $<$와 정확히 같은 순서쌍을 갖는다(§1.2에서 만든 집합이다). 판정 결과도 §1.8 성적표의 $<$ 행과 일치한다 — 유한 무대의 미니어처로 무한 관계의 성질을 예습할 수 있다. ### 문제 4 **접근.** 반사는 등호가 허용되므로 즉시 끝난다. 추이는 $\le$를 "$y - x \ge 0$"으로 옮겨 놓으면 "음이 아닌 두 수의 합은 음이 아니다"로 환원되어 계산이 짧아진다. 대칭은 성적표에서 ✗이므로 반례 완전 서식이다. **풀이.** (반사) ✓. 임의의 $x \in \mathbb{Z}$에 대해 $x - x = 0 \ge 0$이므로 $x \le x$이다. (추이) ✓. $x \le y$이고 $y \le z$라 가정하자. 그러면 $y - x \ge 0$이고 $z - y \ge 0$이다. 음이 아닌 두 수의 합은 음이 아니므로 $(y - x) + (z - y) = z - x \ge 0$이고, 따라서 $x \le z$이다. (대칭) ✗. 반례: $x_0 = 1$, $y_0 = 2$. $1 \le 2$는 참이고($2 - 1 = 1 \ge 0$), $2 \le 1$은 거짓이다($1 - 2 = -1 < 0$). 따라서 대칭이 아니다. $\blacksquare$ **복기.** 추이 증명에서 두 부등식을 더해 중간항 $y$를 소거하는 것이 몸통이다. 2주차 예제 2.1에서 두 등식을 대입해 다리 $b$를 소거한 것과 같은 동작이고, $\le$$\cdot$$\mid$$\cdot$$\subseteq$의 추이성이 전부 이 "다리 소거" 한 줄로 끝난다. ### 문제 5 **접근.** 훈련 1의 백지 재현이다. 세 항목의 도착점이 모두 "어떤 차가 정수"이고, 쓰는 근거는 ② 닫힘성 하나뿐이다. 정수의 $(-1)$배가 정수라는 것과 정수끼리의 합이 정수라는 것, 이 두 문장이 대칭과 추이를 각각 닫는다. **풀이.** $\mathbb{R}$ 위의 관계 $x\,R\,y \iff x - y \in \mathbb{Z}$라 하자. (반사) 임의의 $x \in \mathbb{R}$에 대해 $x - x = 0$이고 $0 \in \mathbb{Z}$이므로 $x\,R\,x$이다. (대칭) $x\,R\,y$라 가정하자. 곧 $x - y \in \mathbb{Z}$이다. 그러면 $y - x = -(x - y)$이고, 정수의 $(-1)$배는 정수이므로 $y - x \in \mathbb{Z}$, 곧 $y\,R\,x$이다. (추이) $x\,R\,y$이고 $y\,R\,z$라 가정하자. 곧 $x - y \in \mathbb{Z}$이고 $y - z \in \mathbb{Z}$이다. 그러면 $x - z = (x - y) + (y - z)$이고 정수의 합은 정수이므로 $x - z \in \mathbb{Z}$, 곧 $x\,R\,z$이다. $\blacksquare$ **검산.** $x = 0.5$, $y = 3.5$, $z = -1.5$로 대입하면 $x - y = -3$, $y - z = 5$, $x - z = 2$로 모두 정수다 — 세 줄이 그대로 성립한다. ### 문제 6 **접근.** 예제 2.1의 백지 재현이다. 채점 포인트는 세 곳이다 — 반사에서 문자 $n$으로 시작했는가, 추이에서 2주차 예제 2.1을 이름으로 인용했는가, 대칭에서 완전 서식 세 조각을 갖췄는가. **풀이.** $\mathbb{N}$ 위의 관계 $\mid$를 판정한다. (반사) ✓. 임의의 $n \in \mathbb{N}$에 대해 $n = n \cdot 1$이고 $1 \in \mathbb{Z}$이므로, 정의 2.1에 의해 $n \mid n$이다. (추이) ✓. $a \mid b$이고 $b \mid c$라 가정하자. 2주차 예제 2.1에 의해 $a \mid c$이다. (대칭) ✗. 반례: $2$와 $4$. $4 = 2 \cdot 2$이고 $2 \in \mathbb{Z}$이므로 $2 \mid 4$는 참이다. 한편 $2 = 4c$인 정수 $c$는 존재하지 않으므로($c = \frac12$은 정수가 아니다) $4 \nmid 2$이다. 따라서 $\mathbb{N}$ 위의 $\mid$는 반사적$\cdot$추이적이고 대칭적이지 않다. $\blacksquare$ **복기.** 추이 항목이 한 줄로 끝나는 것이 이 문제의 요점이다. 짧다고 부족한 것이 아니라, 근거 ④(이미 증명한 명제)가 계산 전체를 대신한 것이다. ### 문제 7 **접근.** 반사부터 의심한다 — $x < x$가 참인 $x$가 하나라도 있는지 물으면 답이 즉시 나온다. 세 항목 중 둘이 불성립이므로 반례를 두 벌 준비하고, 추이만 $<$의 정의 ($y - x \in \mathbb{N}$)로 증명한다. **풀이.** (반사) ✗. 반례: $x_0 = 1$. $1 \in \mathbb{Z}$이다. $1 < 1$은 $1 - 1 = 0 \in \mathbb{N}$을 요구하는데 $0$은 자연수가 아니므로 거짓이다. 반사성은 모든 $x$를 요구하므로 이 한 개로 불성립이 확정된다. (대칭) ✗. 반례: $x_0 = 1$, $y_0 = 2$. $1 < 2$는 참이고($2 - 1 = 1 \in \mathbb{N}$), $2 < 1$은 거짓이다($1 - 2 = -1 \notin \mathbb{N}$). (추이) ✓. $x < y$이고 $y < z$라 가정하자. 정의에 의해 $y - x \in \mathbb{N}$이고 $z - y \in \mathbb{N}$이다. 자연수의 합은 자연수이므로 $(y - x) + (z - y) = z - x \in \mathbb{N}$이고, 따라서 $x < z$이다. $\blacksquare$ **복기.** 반사가 **모든** $x$에서 실패하는데도 답안에는 반례 하나만 적으면 된다. 불성립의 증명 부담이 성립의 증명 부담보다 훨씬 가볍다는 것이 $\forall$ 명제의 비대칭이고, 29주차에서 정식화한 내용이다. ### 문제 8 **접근.** 왕복 사슬 $1 \to 2 \to 1$을 실제로 따라가면 요구되는 지름길의 출발점과 도착점이 같아진다 — 곧 자기 고리 $(1,1)$이다. 이 관계에는 대각선 칸이 하나도 없으므로 추이가 깨진다. (c)는 깨진 사슬 전부를 세어 필요한 지름길만 추가하는 문제다. **풀이.** (a) $R$의 원소는 $(1,2)$와 $(2,1)$ 둘뿐이다. $(1,2)$의 짝 $(2,1)$이 $R$에 있고, $(2,1)$의 짝 $(1,2)$도 $R$에 있다. 모든 원소가 짝을 가지므로 대칭적이다 ✓. (b) 반례 사슬: $1\,R\,2$이고 $2\,R\,1$이다(둘 다 $R$에 있다). 추이가 성립하려면 $1\,R\,1$이어야 하는데 $(1,1) \notin R$이다. 따라서 추이적이 아니다 ✗. 같은 이유로 사슬 $2\,R\,1$, $1\,R\,2$는 $(2,2)$를 요구하는데 그것도 없다. (c) 빠진 지름길은 $(1,1)$과 $(2,2)$ 둘이다. 이 둘을 추가한 $R' = \{(1,2), (2,1), (1,1), (2,2)\}$를 점검하면, 두 칸 사슬은 전부 1과 2 사이에서만 생기고 $R'$은 $\{1,2\} \times \{1,2\}$ 전체를 담고 있으므로 어떤 사슬의 지름길도 $R'$ 안에 있다 — 추이적이다. $(3,3)$은 추가할 필요가 없다. 3이 낀 순서쌍이 하나도 없어 3을 지나는 사슬 자체가 없기 때문이다. **복기.** "왕복이 있으면 양 끝의 자기 고리가 강제된다"가 추이 판정에서 가장 자주 놓치는 지점이다. (c)에서 $(3,3)$이 필요 없다는 것은 추이가 반사를 요구하지 않는다는 사실의 구체적 증거이고, 이것이 문제 15 함정의 씨앗이다. ### 문제 9 **접근.** 반사와 대칭은 절댓값의 두 성질($|0| = 0$, $|-t| = |t|$)로 즉시 닫힌다. 추이는 수직선에 점 세 개를 그려 본다 — 한 칸씩 두 번 움직이면 거리가 2까지 벌어지므로, 조건 $\le 1$을 넘어서는 배치를 찾을 수 있다. **풀이.** (반사) ✓. 임의의 $x \in \mathbb{R}$에 대해 $|x - x| = |0| = 0 \le 1$이므로 $x\,R\,x$이다. (대칭) ✓. $x\,R\,y$라 가정하자. 곧 $|x - y| \le 1$이다. 17주차 문제 4에 의해 $|y - x| = |-(x-y)| = |x - y| \le 1$이므로 $y\,R\,x$이다. (추이) ✗. 반례: $x_0 = 0$, $y_0 = 1$, $z_0 = 2$. $|0 - 1| = 1 \le 1$이므로 $0\,R\,1$은 참이고, $|1 - 2| = 1 \le 1$이므로 $1\,R\,2$도 참이다. 그런데 $|0 - 2| = 2 > 1$이므로 $0 \not R 2$이다. $\blacksquare$ **복기.** "가깝다"는 관계는 추이적이지 않다 — 가까움을 연쇄하면 멀어진다. 이 현상 때문에 근사$\cdot$오차를 다루는 논증에서는 추이를 쓸 수 없고, 대신 삼각부등식으로 누적 오차를 관리한다(45주차 $\varepsilon$-$N$ 논법). ### 문제 10 **접근.** 세 항목을 각각 새로 증명해도 되지만, 조건을 바꿔 읽으면 일이 훨씬 줄어든다. 25주차 문제 17이 "$x + y$가 짝수 $\iff$ $x \equiv y \pmod 2$"를 증명해 두었으므로, 이 관계는 $\equiv \pmod 2$와 **같은 순서쌍 집합**이다. 그러면 예제 2.2가 $n = 2$에서 그대로 적용된다. **풀이.** 25주차 문제 17에 의해, 임의의 정수 $x, y$에 대해 "$x + y$가 짝수"와 "$x \equiv y \pmod 2$"는 동치다. 두 조건이 정확히 같은 순서쌍을 통과시키므로, 정의 36.1의 뜻에서 이 관계는 $\mathbb{Z}$ 위의 $\equiv \pmod 2$와 같은 집합이다. 예제 2.2를 $n = 2$에 적용하면 이 관계는 반사적$\cdot$대칭적$\cdot$추이적이다. 그리고 이 관계의 정체는 "$x$와 $y$의 홀짝이 같다"는 관계다(25주차 문제 9). $\blacksquare$ **검산.** 직접 확인해도 같다 — 반사: $x + x = 2x$는 짝수 ✓. 대칭: $y + x = x + y$ ✓. 추이: $x + y$와 $y + z$가 짝수이면 합 $x + 2y + z$가 짝수이고 $2y$가 짝수이므로 차 $x + z$도 짝수 ✓. **복기.** 관계가 집합이므로, 조건이 달라 보여도 통과하는 순서쌍이 같으면 **같은 관계**다. 성질 판정 전에 "이미 판정한 관계와 같은 것이 아닌가"를 먼저 묻는 것이 가장 짧은 길일 때가 많다. ### 문제 11 **접근.** 세 항목의 몸통이 전부 4주차에 있다. 반사는 $X \subseteq X$, 추이는 $X \subseteq Y$이고 $Y \subseteq Z$이면 $X \subseteq Z$이며, 대칭은 진부분집합 아무거나 하나면 반례가 된다. 무대가 $\mathcal{P}(\{1,2,3\})$이므로 반례도 이 멱집합 안에서 고른다. **풀이.** 무대는 $\mathcal{P}(\{1,2,3\})$이고, 그 원소는 $\{1,2,3\}$의 부분집합 여덟 개다. (반사) ✓. 임의의 $X \in \mathcal{P}(\{1,2,3\})$에 대해, $x \in X$이면 $x \in X$이므로 $X \subseteq X$이다(4주차). (추이) ✓. $X \subseteq Y$이고 $Y \subseteq Z$라 가정하자. 임의의 $x \in X$를 잡으면 $X \subseteq Y$에 의해 $x \in Y$이고, $Y \subseteq Z$에 의해 $x \in Z$이다. 따라서 $X \subseteq Z$이다(4주차의 빈칸 훈련). (대칭) ✗. 반례: $X_0 = \emptyset$, $Y_0 = \{1\}$. 공집합은 모든 집합의 부분집합이므로 $\emptyset \subseteq \{1\}$은 참이다. 한편 $1 \in \{1\}$인데 $1 \notin \emptyset$이므로 $\{1\} \nsubseteq \emptyset$이다. $\blacksquare$ **복기.** 추이 증명의 몸통이 "$x \in X$라 하자"로 시작하는 것은 4주차에서 세운 집합 포함 증명의 틀 그대로다. $\le$, $\mid$, $\subseteq$가 모두 반사$\cdot$추이는 있고 대칭은 없다 — 이 패턴에 이름이 붙는 것은 순서 관계를 다룰 때이고, 이번 주는 판정까지만 한다. ### 문제 12 **접근.** 반사부터 의심하라는 지시가 힌트다. $x$와 $x$의 공통 약수에는 $x$ 자신이 들어 있으므로, $x > 1$이면 1이 아닌 공통 약수가 생겨 서로소가 아니다. $x = 1$에서만 성립한다는 사실은 반사성의 근거가 되지 못한다(§1.6 실험 A). 추이는 짝수-홀수-짝수 사슬로 깨진다. **풀이.** (반사) ✗. 반례: $x_0 = 2$. $2 \in \mathbb{N}$이다. $2$와 $2$의 공통 약수는 $1$과 $2$이고, $2 \ne 1$인 공통 약수가 있으므로 $2$와 $2$는 서로소가 아니다. 곧 $2 \not R 2$이다. (참고: $x = 1$에서는 $1\,R\,1$이 성립한다. 그러나 반사성은 "모든 $x$"를 요구하므로 일부에서의 성립은 반사성이 아니다.) (대칭) ✓. $x\,R\,y$라 가정하자. "$x$와 $y$의 공통 약수"라는 개념은 두 수를 대등하게 다루므로, $x$와 $y$의 공통 약수 전체는 $y$와 $x$의 공통 약수 전체와 같은 집합이다. 앞의 것이 $\{1\}$이면 뒤의 것도 $\{1\}$이므로 $y\,R\,x$이다. (추이) ✗. 반례: $x_0 = 2$, $y_0 = 3$, $z_0 = 4$. $2$와 $3$의 공통 약수는 $1$뿐이므로 $2\,R\,3$은 참이고, $3$과 $4$의 공통 약수도 $1$뿐이므로 $3\,R\,4$도 참이다. 그런데 $2$와 $4$는 공통 약수 $2$를 가지므로 $2 \not R 4$이다. $\blacksquare$ **복기.** 정의가 두 자리를 대등하게 쓰면 대칭은 거의 자동으로 따라오지만, 반사와 추이는 별개의 검사가 필요하다 — "정의가 대칭적으로 생겼다"는 관찰에서 나머지 두 항목을 유추하지 않는다. ### 문제 13 **접근.** 세 항목 모두 도착점이 "$3 \mid (\text{어떤 식})$"이다. 문제에 딸린 두 항등식은 "구하려는 식 $=$ (명백한 3의 배수) $\pm$ (가정으로 아는 3의 배수)" 꼴을 만들어 주므로, 나머지는 2주차의 배수 합$\cdot$차 정리가 닫는다. 반사에는 항등식이 필요 없다 — $x + 2x = 3x$가 그대로 3의 배수다. **풀이.** (반사) 임의의 $x \in \mathbb{Z}$에 대해 $x + 2x = 3x$이고 $3x = 3 \cdot x$, $x \in \mathbb{Z}$이므로 $3 \mid (x + 2x)$이다. 곧 $x\,R\,x$이다. (대칭) $x\,R\,y$라 가정하자. 곧 $3 \mid (x + 2y)$이다. 항등식 $y + 2x = 3(x + y) - (x + 2y)$에서 $3 \mid 3(x+y)$이고 가정에 의해 $3 \mid (x + 2y)$이므로, 두 배수의 차도 3의 배수다(2주차 문제 7). 따라서 $3 \mid (y + 2x)$, 곧 $y\,R\,x$이다. (추이) $x\,R\,y$이고 $y\,R\,z$라 가정하자. 곧 $3 \mid (x + 2y)$이고 $3 \mid (y + 2z)$이다. 두 배수의 합은 배수이므로(2주차 예제 2.2) $3 \mid \big((x + 2y) + (y + 2z)\big)$이고, 항등식에 의해 그 값은 $(x + 2z) + 3y$이다. $3 \mid 3y$이므로 다시 차를 취하면 $3 \mid (x + 2z)$, 곧 $x\,R\,z$이다. $\blacksquare$ **복기.** 이 관계의 정체는 합동이다. $x + 2y = (x - y) + 3y$이므로 $3 \mid (x + 2y)$와 $3 \mid (x - y)$는 같은 조건이고, 곧 $x \equiv y \pmod 3$이다. 정체를 먼저 알아채면 예제 2.2 인용 한 줄로 끝난다 — 문제 10과 같은 지름길이다. ### 문제 14 **접근.** 반사는 $x \cdot x = x^2 > 0$인지 묻는 것이고, 이 부등식이 깨지는 $x$는 $0$ 하나뿐이다. 대칭은 곱셈의 교환법칙으로 즉시 닫히고, 추이는 부호를 따지는 논증이다. 무대를 $\mathbb{R} - \{0\}$으로 좁히면 반사의 유일한 반례가 무대에서 사라진다. **풀이.** 먼저 무대가 $\mathbb{R}$인 경우. (반사) ✗. 반례: $x_0 = 0$. $0 \in \mathbb{R}$이다. $0 \cdot 0 = 0$이고 $0 > 0$은 거짓이므로 $0 \not R 0$이다. (대칭) ✓. $x\,R\,y$라 가정하자. 곧 $xy > 0$이다. 곱셈의 교환법칙에 의해 $yx = xy > 0$이므로 $y\,R\,x$이다. (추이) ✓. $xy > 0$이고 $yz > 0$이라 가정하자. $xy > 0$이므로 $x$와 $y$는 둘 다 양수이거나 둘 다 음수다(어느 쪽도 0이 아니다). $yz > 0$이므로 $y$와 $z$도 같은 부호다. 따라서 $x$와 $z$는 $y$를 매개로 같은 부호이고, 같은 부호인 두 수의 곱은 양수이므로 $xz > 0$, 곧 $x\,R\,z$이다(부호에 따른 경우 나누기, 17주차). 무대를 $\mathbb{R} - \{0\}$으로 좁히면 — (반사) ✓. 임의의 $x \ne 0$에 대해 $x^2 > 0$이므로 $x\,R\,x$이다. 대칭과 추이의 증명은 무대와 무관하게 그대로 성립한다. 따라서 셋 다 성립하고, 동치류는 양수 전체와 음수 전체 두 조각이 된다(다음 주 예고). $\blacksquare$ **복기.** **무대가 성질을 바꾼다.** 관계의 조건은 한 글자도 바뀌지 않았는데 반사 칸이 뒤집혔다. 정의 36.1의 첫 조각("집합 $A$ 위의")이 장식이 아니라는 증거이고, 3주차의 "무대가 답을 바꾼다"가 관계 판정에서 재연된 것이다. ### 문제 15 **접근.** 논증이 실제로 결론짓는 문장을 정확히 적어 본다. 첫 문장 "$x\,R\,y$라 하자"는 **그런 $y$가 존재하는 $x$**에 대해서만 시작할 수 있으므로, 논증이 주는 것은 "짝이 있는 $x$에 대해 $x\,R\,x$"다. 반사성이 요구하는 것은 "모든 $x$에 대해 $x\,R\,x$"다. 두 문장을 나란히 놓으면 고립 원소가 통째로 빠져 있음이 보인다. **풀이.** 오류의 위치는 첫 문장이다. 반사성의 목표는 "**모든** $x \in A$에 대해 $x\,R\,x$"인데, 제시된 논증은 "$x\,R\,y$인 $y$가 존재하는 $x$"에 대해서만 $x\,R\,x$를 유도한다. 그런 $y$가 하나도 없는 원소(고립 원소)에 대해서는 논증의 첫 문장부터 시작할 수 없으므로, 그 원소에서 $x\,R\,x$는 보장되지 않는다. 곧 이 논증은 "$\forall x\, \exists y\ x\,R\,y$"라는 추가 가정을 몰래 사용하고 있다(10주차의 한정기호 언어). 반례: $A = \{1, 2\}$ 위의 $R = \{(1,1)\}$. 대칭 ✓ — $R$의 원소는 $(1,1)$뿐이고 그 짝 $(1,1)$이 $R$에 있다. 추이 ✓ — 두 칸 사슬은 $1 \to 1 \to 1$뿐이고 지름길 $(1,1)$이 $R$에 있다. 반사 ✗ — $2 \in A$인데 $(2,2) \notin R$이므로 $2 \not R 2$이다. 원소 2가 고립 원소다. 더 극단적인 반례로 $A = \{1\}$ 위의 $R = \emptyset$도 된다. 대칭과 추이는 검사할 순서쌍이 없어 공허하게 참이고, $(1,1) \notin \emptyset$이므로 반사는 거짓이다. $\blacksquare$ **복기.** 대칭$\cdot$추이는 조건문이므로 짝이 없는 원소를 그냥 통과시키고, 반사는 조건 없는 $\forall$이므로 통과시키지 않는다. 가짜 증명을 만났을 때의 절차는 하나다 — 논증이 실제로 커버하는 범위를 문장으로 적고, 목표 문장의 범위와 대조한다. ### 문제 16 **접근.** (a)는 결론이 "그리고"로 묶여 있으므로 18주차의 $\land$ 서식이다 — 두 부분을 각각 마감한 뒤 마지막에 묶는다. 각 부분은 예제 2.2를 $n = 2$와 $n = 3$에 적용한 것이므로 새 계산이 없다. (b)는 두 합동을 $x - y$에 대한 나누어떨어짐으로 바꾼 뒤 25주차 문제 12를 그대로 대입한다. **풀이.** (a) 관계를 $x\,R\,y \iff (x \equiv y \pmod 2$ 그리고 $x \equiv y \pmod 3)$로 둔다. (반사) 임의의 정수 $x$에 대해, (C1)에 의해 $x \equiv x \pmod 2$이고, 같은 (C1)에 의해 $x \equiv x \pmod 3$이다. 두 조건이 모두 성립하므로 $x\,R\,x$이다. (대칭) $x\,R\,y$라 가정하자. 곧 $x \equiv y \pmod 2$이고 $x \equiv y \pmod 3$이다. (C2)를 법 2에 적용하면 $y \equiv x \pmod 2$이고, (C2)를 법 3에 적용하면 $y \equiv x \pmod 3$이다. 두 조건이 모두 성립하므로 $y\,R\,x$이다. (추이) $x\,R\,y$이고 $y\,R\,z$라 가정하자. 법 2에서 $x \equiv y$이고 $y \equiv z$이므로 (C3)에 의해 $x \equiv z \pmod 2$이다. 법 3에서도 같은 방식으로 (C3)에 의해 $x \equiv z \pmod 3$이다. 두 조건이 모두 성립하므로 $x\,R\,z$이다. $\blacksquare$ (b) 정의에 의해 $x\,R\,y \iff 2 \mid (x - y)$ 그리고 $3 \mid (x - y)$이다. 25주차 문제 12는 임의의 정수 $n$에 대해 "$6 \mid n \iff 2 \mid n$ 그리고 $3 \mid n$"을 증명했다. 이 명제를 $n = x - y$에 적용하면 $$ 2 \mid (x - y) \ \text{그리고} \ 3 \mid (x - y) \iff 6 \mid (x - y) $$ 이고, 오른쪽은 정의에 의해 $x \equiv y \pmod 6$이다. 두 동치를 이으면 $x\,R\,y \iff x \equiv y \pmod 6$이다. $\blacksquare$ **검산.** $x = 7$, $y = 1$: $7 \equiv 1 \pmod 2$ ✓, $7 \equiv 1 \pmod 3$ ✓, 그리고 $7 \equiv 1 \pmod 6$ ✓. $x = 4$, $y = 1$: $4 \equiv 1 \pmod 3$은 참이지만 $4 \equiv 1 \pmod 2$는 거짓이고 $4 \equiv 1 \pmod 6$도 거짓이다 — 양쪽이 함께 무너진다. **복기.** 동치관계 두 개를 "그리고"로 묶으면 다시 세 성질이 살아남는다는 것이 (a)의 내용이고, (b)는 그렇게 만든 관계의 정체를 밝혔다. 법 2와 법 3을 동시에 보는 일이 법 6을 보는 일과 같다는 이 현상은 두 법이 서로소일 때 일어난다. ### 문제 17 **접근.** 반사성이 강제하는 칸과 자유로운 칸을 분리한다. $A \times A$는 $n^2$칸이고, 반사성은 대각선 $n$칸을 반드시 $R$에 넣으라고 요구한다. 나머지 $n^2 - n$칸은 아무 제약이 없으므로 칸마다 2택이고, 곱셈 원리가 그대로 적용된다. **풀이.** $|A| = n$이라 하자. 반사적 관계 $R$는 대각선의 순서쌍 $(x, x)$ ($x \in A$)를 전부 포함해야 하므로 $R$의 원소는 최소 $n$개다. 대각선만으로 이루어진 관계 $R = \{(x,x) : x \in A\}$는 실제로 반사적이므로 최솟값은 정확히 **$n$**이다. 개수를 센다. $|A \times A| = n^2$이고, 그중 대각선 $n$칸은 포함이 확정되어 선택의 여지가 없다. 남은 $n^2 - n$칸은 각각 넣거나 넣지 않는 2택이고 칸마다의 선택이 서로 독립이므로, 곱셈 원리(12주차)에 의해 반사적 관계의 총수는 $2^{n^2 - n}$이다. **검산.** $n = 1$이면 $2^{0} = 1$ — 무대가 $\{a\}$일 때 반사적 관계는 $\{(a,a)\}$ 하나뿐이므로 맞다. $n = 2$이면 $2^{2} = 4$ — 대각선 두 칸은 고정이고 $(1,2)$, $(2,1)$의 포함 여부만 자유이므로 네 가지가 맞다. 전체 관계 수 $2^4 = 16$(문제 2)의 4분의 1이다. **복기.** 제약이 붙은 세기의 표준 절차다 — 강제되는 부분을 떼어 내고 자유로운 부분만 곱셈 원리로 센다. 대칭적 관계의 개수를 세는 문제도 같은 절차로 풀리고, 그때 세는 단위는 칸이 아니라 대각선 대칭인 칸의 쌍이다. ### 문제 18 **접근.** (a)는 집합의 상등을 주장하는 $\iff$ 명제다. 방향을 두 개로 나누고(25주차의 서식), $\Rightarrow$ 방향은 집합 상등이므로 양방향 포함으로 간다(27주차). (b)는 정의에 대입해 조건을 정리하면 익숙한 기호가 나온다. **풀이.** (a) ($\Rightarrow$) $R$가 대칭적이라 가정하자. $R \subseteq R^{-1}$: $(x, y) \in R$라 하자. 대칭성에 의해 $(y, x) \in R$이고, $R^{-1}$의 정의에 의해 $(x, y) \in R^{-1}$이다. $R^{-1} \subseteq R$: $(x, y) \in R^{-1}$이라 하자. $R^{-1}$의 정의에 의해 $(y, x) \in R$이고, 대칭성에 의해 $(x, y) \in R$이다. 양방향 포함이 모두 성립하므로 $R = R^{-1}$이다. ($\Leftarrow$) $R = R^{-1}$이라 가정하자. $(x, y) \in R$라 하자. 가정에 의해 $(x, y) \in R^{-1}$이고, $R^{-1}$의 정의에 의해 $(y, x) \in R$이다. 따라서 $R$는 대칭적이다. $\blacksquare$ (b) 정의에 대입하면 $<^{-1} = \{(y, x) : x < y\} = \{(a, b) : b < a\}$이고, "$b < a$"는 "$a > b$"와 같은 문장이므로 $<^{-1}$은 $\mathbb{Z}$ 위의 관계 **$>$**이다. **복기.** (a)의 두 방향이 길이가 다르다는 점을 눈여겨본다. ($\Rightarrow$)는 집합 상등을 만들어야 하므로 포함이 두 번 필요하고, ($\Leftarrow$)는 대칭성이 한 방향 문장이므로 한 번으로 끝난다. $R^{-1}$은 관계에 쓰는 첫 연산이고, 43주차의 역함수가 이 연산에 "함수가 되는가"라는 조건을 추가한 것이다. ### 문제 19 **접근.** 조건을 등식 $|OP| = |OQ|$로 적고 나면 세 성질이 전부 등호의 세 성질로 환원된다 — 곧 새 증명이 필요 없다. 조각 묘사는 "$|OP| = r$인 점 $P$ 전체"가 평면에서 무엇인지 답하는 문제다. **풀이.** 평면의 점 $P$에 대해 원점 $O$까지의 거리를 $|OP|$로 쓰고, $P\,R\,Q \iff |OP| = |OQ|$라 하자. (반사) 임의의 점 $P$에 대해 $|OP| = |OP|$이므로 $P\,R\,P$이다(등호의 반사성). (대칭) $P\,R\,Q$라 가정하자. 곧 $|OP| = |OQ|$이다. 등호의 대칭성에 의해 $|OQ| = |OP|$이므로 $Q\,R\,P$이다. (추이) $P\,R\,Q$이고 $Q\,R\,S$라 가정하자. 곧 $|OP| = |OQ|$이고 $|OQ| = |OS|$이다. 등호의 추이성에 의해 $|OP| = |OS|$이므로 $P\,R\,S$이다. 셋 다 성립한다. $\blacksquare$ **기하적 묘사.** 서로 관계있는 점들의 무리는 "원점에서 거리가 같은 점 전체"이므로, 거리 $r > 0$마다 **원점 중심 반지름 $r$인 원**이 하나씩 나오고 $r = 0$에는 원점 하나만 있는 무리가 대응된다. 평면의 모든 점은 자기 거리 $r$이 정확히 하나 정해지므로, 평면이 동심원들과 원점으로 **빈틈없이, 겹침 없이** 나뉜다. 다음 주의 언어로는 "동치류에 의한 분할"이다. **복기.** "어떤 값이 같다"는 꼴의 조건은 등호에서 세 성질을 그대로 물려받는다. 문제 10 ($x$와 $y$의 홀짝), 문제 14($x$와 $y$의 부호), 훈련 1(소수 부분)이 모두 같은 꼴이었다 — 무엇이 같은지만 바뀌었다. 이 관찰이 다음 주 동치류의 일반 원리가 된다. ### 문제 20 **접근.** (a)는 "정의하라"는 요구를 "집합을 지정하라"로 환원해 답한다. (b)는 세 성질이 어떤 논리 꼴의 명제인지 말하면 자동으로 나온다. 서술 문제이므로 근거가 되는 절을 지목하며 쓴다. **풀이.** (예시 답안) (a) 집합론은 "$<$를 정의하라"는 요구에 "$<$에 어떤 순서쌍이 속하는지의 조건을 제시하라"로 답한다 — 곧 $< \,= \{(x,y) \in \mathbb{Z} \times \mathbb{Z} : y - x \in \mathbb{N}\}$이다. $<$가 신비한 기호가 아니라 원소 자격 조건을 가진 집합이 되므로, 1주차부터 쓰던 "정의는 판정 가능한 조건이다"라는 원칙이 관계에도 그대로 적용된다. (b) 세 성질은 각각 $\forall$(대칭$\cdot$추이는 그 안에 조건문) 꼴의 명제이므로, 판정은 "참이면 $\forall$ 증명, 거짓이면 반례로 반증"이라는 30주차 모드 그 자체다. **복기.** (a)는 정의의 형식에 대한 답이고 (b)는 판정의 형식에 대한 답이다. 두 문장을 합치면 이번 주 전체가 요약된다 — 관계는 집합으로 정의되고, 그 성질은 증명 또는 반증으로 판정된다. --- **다음 주 예고:** 세 성질을 모두 가진 관계에 이름이 붙는다 — **동치관계**다. 같음의 기준을 느슨하게 잡으면 무대가 겹침 없는 조각들로 나뉜다는 것을 정리로 증명하고(동치류와 분할의 대응), 시계의 12칸과 홀짝의 2칸이 그 사례임을 확인한다. 이번 주의 성적표에서 세 칸이 모두 ✓였던 관계들이 그 주의 재료다.