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

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\)

확인 11. 대칭 행의 도착점 빈칸을 채워 보자. §1.7의 완전 서식대로, 무엇을 몇 개

제시하고 무엇을 확인해야 하는가.

답

구체적인 수 두 개 \(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{정수})\)”를 만드는 일이다.

확인 12. 반사 판정의 한 줄을 완성해 보자: “임의의 \(n \in \mathbb{N}\)에 대해

\(n = n \cdot \underline{\quad}\)이고 \(\underline{\quad} \in \mathbb{Z}\)이므로 \(n \mid n\)이다.”

답

\(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\)”이다.

확인 13. 이 문장을 위해 새 증명을 써야 하는가. 아니라면 무엇을 인용하는가.

답

새 증명이 필요 없다. 정확히 2주차 예제 2.1의 명제다 — 근거 ④로 인용하면 끝난다.

30주 전에 “추이성”이라는 제목으로 증명해 둔 정리가 이번 주에 와서 성질의 이름표를

받는 것이다.

3단계 — 대칭 불성립. 완전 서식 세 조각을 갖춘다.

확인 14. 반례를 \(a_0 = 2\), \(b_0 = 4\)로 잡았다. 세 조각을 완성해 보자.

① 제시: \(\underline{\qquad}\)

② 가정 확인: \(4 = 2 \cdot \underline{\quad}\)이고 그 수가 정수이므로 \(2 \mid 4\) ✓

③ 결론 부정 확인: \(2 = 4c\)인 \(\underline{\qquad}\)가 없으므로 \(4 \nmid 2\) ✓

답

① \(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\)추이적이다.

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

확인 15. 세 항목이 각각 20주차의 어느 성질이고, 그 주의 어느 문제에서 이미

증명되었는지 짝지어 보자.

반사 \(\to\) \(\underline{\qquad}\) / 대칭 \(\to\) \(\underline{\qquad}\) / 추이 \(\to\) \(\underline{\qquad}\)

답

반사 \(\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)\}\)의 세 성질을 판정하시오. 이번에는 설계부터 스스로 해 보자.

확인 16. 판정을 시작하기 전에 정할 것 세 가지를 적어 보자.

① 반사를 확인하려면 어느 순서쌍들이 \(R\)에 있는지 보아야 하는가.

② 대칭을 확인하려면 무엇과 무엇을 짝지어야 하는가.

③ 추이를 확인하려면 무엇을 전수 점검해야 하는가.

답

① \((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은 소재도 무대도 다르지만 절차가 같다. 대응표의 빈칸을 채워 보자.

확인 17. 세 예제에서 각 단계에 해당하는 일을 찾아 보자.

① 무대와 관계를 확정하기: 예제 2.1에서는 \(\underline{\qquad}\)

② 성립을 주장하는 항목의 처리: 예제 2.1의 반사에서는 \(\underline{\qquad}\)

③ 불성립을 주장하는 항목의 처리: 예제 2.1의 대칭에서는 \(\underline{\qquad}\)

답

① “\(\mathbb{N}\) 위의 관계 \(\mid\)” — 무대가 바뀌면 칸이 달라질 수 있다(문제 14).

② 문자 \(n\)을 잡고 정의로 \(n \mid n\)을 유도했다 — \(\forall\) 증명이다.

③ 구체적인 수 \(2, 4\)를 잡고 완전 서식으로 반례를 제시했다 — 반증이다.

예제 2.2는 ②만 세 번(전부 인용으로), 예제 2.3은 ②만 세 번(전수 점검으로) 수행한 것이다.

방금 확인한 뼈대에 이름을 붙인다.

백지 암기 대상

성질 판정의 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\) 그래도 안 되면 풀이를 읽는다.

이번 주의 채점 기준

답이 아니라 근거가 점수다. “\(\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\)추이)의 정의를 쓰시오.

힌트

세 성질은 전부 “모든 ~에 대해”로 시작한다. 대칭과 추이에는 그 뒤에 조건(“~이면”)이

하나 더 붙는다는 것까지 적었는지 확인한다.

2. \(A = \{1, 2\}\) 위의 관계는 모두 몇 개인가? (힌트: 관계 = \(A \times A\)의 부분집합 — 4주차 멱집합 세기.)

힌트

세는 대상은 “관계”가 아니라 “\(A \times A\)의 부분집합”이다. 먼저 \(|A \times A|\)를 구하고,

원소가 \(m\)개인 집합의 부분집합 개수(4주차)를 쓴다.

3. \(A = \{1, 2, 3\}\) 위의 관계 \(R = \{(1,2), (2,3), (1,3)\}\)을 화살표 그림으로 그리고 세 성질을 판정하시오.

힌트

반사와 대칭은 각각 반례 하나로 끝난다 — 비어 있는 대각선 칸, 짝이 없는 순서쌍을 찾는다.

추이는 두 칸 사슬이 몇 개인지부터 센다.

4. \(\mathbb{Z}\) 위의 \(\le\)에 대해: 반사\(\cdot\)추이가 성립함을 증명하고, 대칭이 아님을 반례로 보이시오.

힌트

\(x \le y\)를 “\(y - x \ge 0\)”으로 바꿔 놓으면 추이가 “음이 아닌 두 수의 합은 음이 아니다”로

환원된다.

5. 빈칸 훈련(\(x - y \in \mathbb{Z}\))을 백지에서 완성하시오.

힌트

세 항목 모두 도착점이 “어떤 차가 정수임을 보인다”이고, 쓰는 근거는 ② 닫힘성 하나뿐이다 —

정수의 \((-1)\)배와 정수끼리의 합.

6. 예제 2.1(\(\mid\)의 성적표)을 백지에 재현하시오.

힌트

세 줄이다. 반사는 \(n = n \cdot 1\), 추이는 2주차 예제 2.1 인용, 대칭은 \(2\)와 \(4\)의

완전 서식. 인용 문구까지 그대로 적었는지 확인한다.

표준 ●●○#

7. \(\mathbb{Z}\) 위의 \(<\)에 대해 세 성질을 판정하시오 (각각 증명 또는 반례).

힌트

반사부터 의심한다 — \(x < x\)가 참인 \(x\)가 하나라도 있는가. 추이는 \(y - x\)와 \(z - y\)가

자연수임을 쓰면 닫힘성으로 닫힌다.

8. \(A = \{1, 2, 3\}\) 위의 \(R = \{(1,2), (2,1)\}\)에 대해: (a) 대칭임을 확인하시오. (b) 추이가 아님을 반례 사슬로 보이시오 (어떤 순서쌍이 빠져 있는가?). (c) 추이가 되도록 최소한의 순서쌍을 추가한다면 무엇 무엇인가?

힌트

\(1 \to 2 \to 1\)이라는 사슬을 실제로 따라가 본다. 이 사슬이 요구하는 지름길의 출발점과

도착점이 같다는 것이 이 문제의 전부다.

9. \(\mathbb{R}\) 위의 관계 \(x\,R\,y \iff |x - y| \le 1\)에 대해 세 성질을 판정하시오.

힌트

반사와 대칭은 절댓값의 성질로 즉시 닫힌다. 추이는 “거리 1과 거리 1을 이으면 거리가

얼마까지 벌어지는가”를 수직선에 그려 본다.

10. \(\mathbb{Z}\) 위의 관계 \(x\,R\,y \iff x + y\)가 짝수 — 세 성질을 판정하시오. (이 관계의 정체는? 25주차 문제 9\(\cdot\)17과 연결하라)

힌트

세 항목을 각각 새로 증명해도 되지만, 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\)를 구분해 보라)

힌트

\(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\))

힌트

훈련 3과 같은 구조다. 문제에 딸린 항등식은 “구하려는 식 = (3의 배수) \(\pm\) (가정으로

아는 3의 배수)” 꼴이므로, 2주차 문제 7(배수의 차)로 닫힌다.

14. 실수 전체에서 \(x\,R\,y \iff xy > 0\)의 세 성질을 판정하시오. 무대를 \(\mathbb{R} - \{0\}\)으로 좁히면 판정이 어떻게 달라지는가?

힌트

반사는 \(x \cdot x = x^2 > 0\)인지 묻는 것이고, 이 부등식이 깨지는 \(x\)는 정확히 하나다.

무대에서 그 하나를 빼면 무엇이 달라지는지 본다.

도전 ●●●#

되살리는 개념 — 공허한 참 (4\(\cdot\)8주차)

“\(P\)이면 \(Q\)이다” 꼴의 문장은 \(P\)가 거짓인 경우에 아무 조건 없이 참이 된다. 대칭과

추이의 정의가 정확히 이 꼴이므로, 관계 맺은 짝이 하나도 없는 원소 앞에서 두 성질은

검사할 것이 없어 자동으로 통과한다. 반사에는 이 통로가 없다 — 조건 없이 “모든 \(x\)에서

\(x\,R\,x\)”를 요구하기 때문이다. 이 비대칭이 문제 15의 함정을 만든다.

15. (유명한 함정) 다음 ‘증명’의 오류를 해부하시오.

“주장: 대칭적이고 추이적인 관계는 반사적이다. 증명: \(x R y\)라 하자. 대칭성에 의해 \(y R x\)이다. 추이성을 \(x R y\)와 \(y R x\)에 적용하면 \(x R x\)이다. 따라서 반사적이다. \(\blacksquare\)”

그리고 실제 반례(대칭\(\cdot\)추이지만 반사가 아닌 관계)를 하나 제시하시오. (힌트: 첫 문장 “\(x R y\)라 하자”에서 그런 \(y\)의 존재를 누가 보장하는가? 공허한 관계 또는 일부 원소가 고립된 관계를 시도하라)

힌트

논증이 실제로 결론짓는 문장을 정확히 적어 본다: “\(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).

힌트

(a)는 18주차의 \(\land\) 결론 서식이다 — 두 부분을 각각 마감한 뒤 “따라서 둘 다

성립한다”로 묶는다. (b)는 두 조건을 \(x - y\)에 대한 나누어떨어짐으로 바꾼 뒤

25주차 문제 12를 그대로 대입한다.

이 문제가 되살리는 도구 — 곱셈 원리 (12주차)

문제 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주차 곱셈 원리)

이 문제가 만드는 새 관계 — 뒤집기

관계는 집합이므로, 집합을 재료로 새 집합을 만드는 연산을 관계에도 쓸 수 있다.

문제 18의 \(R^{-1}\)이 그런 연산의 첫 사례다 — 모든 순서쌍의 좌우를 바꿔 만든 새 관계이고,

정의는 문제 안에 주어져 있다. 43주차 역함수가 이 연산의 특수한 경우로 등장한다.

18. “역관계” \(R^{-1} = \{(y, x) : (x, y) \in R\}\)를 정의하자. (a) \(R\)이 대칭적 \(\iff R = R^{-1}\)임을 증명하시오. (b) \(\mathbb{Z}\) 위의 \(<\)의 역관계는 무엇인가?

힌트

(a)는 집합의 상등이므로 27주차의 양방향 포함으로 간다. 그리고 \(\iff\)이므로 방향이

둘이다 — 25주차의 서식대로 (\(\Rightarrow\))와 (\(\Leftarrow\))를 나눠 적는다.

19. 다음 관계의 세 성질을 판정하시오: 평면의 점들 위에서 \(P\,R\,Q \iff\) “\(P\)와 \(Q\)는 원점에서 같은 거리에 있다”. 이 관계로 평면이 어떤 조각들로 나뉘는지 기하적으로 묘사하시오 (다음 주 동치류의 예고).

힌트

조건을 등식 \(|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칸이 그 사례임을 확인한다. 이번 주의 성적표에서 세 칸이 모두 ✓였던 관계들이 그 주의 재료다.