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

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

예제 — 나열과 판정을 절차로#

완성된 답을 먼저 보이지 않는다. 각 예제에서 설계를 먼저 세우고, 확인 상자의 빈칸을 연필로 채운 뒤 답을 연다.

예제 2.1 — 부분집합 전부 나열#

문제. \(A = \{a, b, c\}\)의 부분집합을 모두 나열하시오.

설계. 나열 문제의 위험은 두 가지 — 빠뜨림과 중복이다. 시작 전에 세 가지를 정한다.

내용

목표

\(A\)의 부분집합 전부 — 빠뜨림 없이, 중복 없이

검산 수단

개수 공식 \(2^{\vert A\vert } = 2^3 = 8\) (§1.7) — 개수가 어긋나면 빠뜨림이 있다

전략

크기 0부터 3까지 칸을 만들어 두고 칸마다 채운다 (크기순 나열)

확인 12. 크기 0 칸과 크기 3 칸은 생각할 것도 없이 채워진다. 각각 무엇이

들어가고, §1의 어느 사실이 근거인가?

답

크기 0: \(\emptyset\) — 공허한 참(§1.4)으로 모든 집합의 부분집합이다.

크기 3: \(\{a, b, c\}\) — 자기 자신(\(A \subseteq A\), §1.3).

이 양 끝 두 칸이 나열에서 가장 빠뜨리기 쉬운 칸이기도 하다.

확인 13. 크기 1 칸을 채워 보자. 몇 개가 나와야 하는가?

답

\(\{a\}, \{b\}, \{c\}\) — 원소 하나 고르기이므로 원소 수와 같은 3개다.

확인 14. 크기 2 칸을 채워 보자. 하나씩 만들기보다 빠른 요령이 있다 —

크기 2 부분집합은 무엇을 “고르는” 것과 같은가?

답

뺄 원소 하나를 고르는 것과 같다. \(c\)를 빼면 \(\{a,b\}\), \(b\)를 빼면 \(\{a,c\}\),

\(a\)를 빼면 \(\{b,c\}\) — 3개. 그래서 크기 2 칸과 크기 1 칸의 개수가 같다.

(이 요령은 문제 14에서 재사용된다.)

완성본. 칸을 이어 붙이면 나열이 끝난다. 각 줄 옆의 “왜”에 스스로 답해 본다.

증명의 한 줄

왜 이 줄을 쓰는가?

크기 0: \(\emptyset\)

공허한 참(§1.4) — 모든 집합의 부분집합. 가장 빠뜨리기 쉬운 칸

크기 1: \(\{a\}, \{b\}, \{c\}\)

원소 하나 고르기 — 원소 수만큼 나온다

크기 2: \(\{a,b\}, \{a,c\}, \{b,c\}\)

뺄 원소 하나 고르기 — 크기 1 칸과 개수가 같다

크기 3: \(\{a,b,c\}\)

자기 자신(\(A \subseteq A\), §1.3)

검산: \(1 + 3 + 3 + 1 = 8 = 2^3\) ✓

크기 공식(§1.7)과 대조 — 개수가 맞아야 나열이 닫힌다

예제 2.2 — ∈/⊆ 판정의 사고 과정#

문제. \(B = \{1, \{2\}\}\)에 대해 \(\{2\} \subseteq B\)는 참인가?

이번에는 설계만 함께 하고, 판정 본문은 완성본으로 본다. 판정 문제도 설계는 번역표부터다 — 가정이 주는 것(출발점)과 만들 것(도착점)을 먼저 적는다.

말

번역

가정 (주어진 것)

\(B = \{1, \{2\}\}\)

\(B\)의 한 겹 목록은 \(1\)과 \(\{2\}\) — 출발점

목표 (판정할 것)

\(\{2\} \subseteq B\)의 참\(\cdot\)거짓

원소별 \(\in\) 질문으로 환원한다 — 도착점

확인 15. 첫 두 동작을 적어 보자.

① 기호는 \(\subseteq\) — 이 기호가 정하는 판정 절차는 무엇인가(§1.5의 표에서 고른다): \(\underline{\quad}\)

② 왼쪽 \(\{2\}\)의 원소는 \(\underline{\quad}\) 하나 — 그러면 판정은

“\(\underline{\quad} \in B\)인가?”라는 질문으로 환원된다.

답

① 왼쪽 집합의 원소를 하나씩 꺼내 전부 \(B\)에서 찾는 절차다(\(\subseteq\)의 줄).

② 원소는 \(2\) 하나, 질문은 “\(2 \in B\)인가?”로 환원된다.

\(\subseteq\) 판정은 원소별 \(\in\) 질문의 묶음이다 — 원소가 하나뿐이므로

질문도 하나다.

증명의 한 줄

왜 이 줄을 쓰는가?

기호는 \(\subseteq\) — 왼쪽 \(\{2\}\)의 원소를 하나씩 꺼낸다.

판정 절차의 선택(§1.5). 기호를 잘못 읽으면 절차가 통째로 바뀐다.

\(\{2\}\)의 원소는 \(2\) 하나. 질문은 “\(2 \in B\)인가?”로 환원된다.

\(\subseteq\) 판정은 원소별 \(\in\) 질문의 묶음이다.

\(B\)의 한 겹 목록은 \(1\)과 \(\{2\}\) — 숫자 \(2\)는 없다. \(2 \notin B\).

\(\in\) 판정은 한 겹 목록 대조(3주차). 상자 \(\{2\}\) 속은 열지 않는다.

못 건너간 원소 \(2\)가 지목되었으므로 \(\{2\} \nsubseteq B\). 거짓.

거짓 판정은 실패 원소 하나로 완결된다(§1.3).

확인 16. 같은 재료로 \(\{2\} \in B\)를 판정해 보자.

답

참이다 — \(B\)의 한 겹 목록에 상자 \(\{2\}\)가 통째로 있다.

\(\in\)은 참인데 \(\subseteq\)는 거짓인 사례다. 두 판정의 독립(§1.5, 확인 7)이

실제 문제에서 이렇게 나타난다.

예제 2.3 — 겹겹의 멱집합#

문제. \(\mathcal{P}(\emptyset)\)과 \(\mathcal{P}(\mathcal{P}(\emptyset))\)을 구하시오.

이번에는 설계부터 스스로 해 보자.

확인 17. 멱집합을 구하는 절차는 예제 2.1에서 세웠다. 안쪽

\(\mathcal{P}(\emptyset)\)부터 시작하면 첫 질문은 무엇이고, 크기순 칸은 몇 개나 되는가?

답

첫 질문: “\(\emptyset\)의 부분집합은 무엇인가.” \(|\emptyset| = 0\)이므로 칸은

크기 0 하나뿐이고, 그 칸에는 \(\emptyset\) 자신이 들어간다

(\(\emptyset \subseteq \emptyset\) — 공허한 참이자 자기 자신).

풀이. \(\emptyset\)의 부분집합은 \(\emptyset\) 자신 하나뿐이다. 따라서

\[ \mathcal{P}(\emptyset) = \{\emptyset\}, \qquad |\mathcal{P}(\emptyset)| = 1 = 2^0 \]

\(\mathcal{P}(\emptyset)\)은 공집합이 아니다 — 빈 상자와 “빈 상자가 든 상자”는 다른 집합이다(3주차). 다음 층으로 간다. \(\{\emptyset\}\)은 크기 1이므로 칸은 크기 0과 크기 1 둘이고, 각각 \(\emptyset\)과 \(\{\emptyset\}\)이 들어간다. 따라서

\[ \mathcal{P}(\mathcal{P}(\emptyset)) = \{\emptyset, \{\emptyset\}\}, \qquad \text{크기 } 2 = 2^1 \]

원소가 하나도 없는 집합에서 출발해 멱집합을 거듭 취하는 것만으로 크기 \(1, 2, 4, 16, \dots\)의 집합들이 생겨난다.

이번 풀이는 표 없이 산문으로 적었다. 표는 연습 단계의 장치이고, 실전의 답안은 처음부터 끝까지 이런 산문이다.

관찰 — 세 예제의 같은 첫 동작#

겉모습은 나열\(\cdot\)판정\(\cdot\)계산으로 다르지만, 세 예제의 첫 동작은 같다. 대응표의 빈칸을 채워 보자.

확인 18. 각 예제에서 “기호(개념)를 정의의 절차로 바꾼” 지점을 찾아 보자.

① 예제 2.1 — “부분집합 전부”가 어떤 절차가 되었는가: \(\underline{\qquad}\)

② 예제 2.2 — “\(\subseteq\) 판정”이 어떤 질문이 되었는가: \(\underline{\qquad}\)

③ 예제 2.3 — “멱집합 계산”이 어떤 작업이 되었는가: \(\underline{\qquad}\)

답

① 크기 칸을 만들어 채우고 \(2^n\)으로 검산하는 나열 절차.

② 왼쪽 원소를 꺼내 만든 “\(2 \in B\)인가?”라는 \(\in\) 질문.

③ “부분집합 나열”(예제 2.1의 절차)을 층마다 반복하는 작업.

셋 다 첫 동작이 같다 — 1주차의 습관 “애매하면 정의로 돌아간다”(1주차 §1.5)의

집합판이다.

방금 확인한 공통 동작에 이름을 붙여 관찰을 닫는다.

기호를 정의의 절차로 바꾼다

이번 주 문제 전부(스피드 드릴 포함)의 기본 동작이다. 증명 쪽의 같은 동작은

§1.6의 “부분집합 증명의 틀”로 이미 명명\(\cdot\)암기 지정되어 있다 — 이 관찰은 새 틀의

추가가 아니라, 그 틀의 첫 걸음이 나열\(\cdot\)판정\(\cdot\)계산에서도 같음을 확인한 것이다.

빈칸 사다리 — 원소 추적 빈칸 훈련#

§1.6의 틀을 손에 익히는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(6장)에 있다 — 다 채운 뒤에 대조한다.

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

명제. \(A \subseteq B\)이고 \(B \subseteq C\)이면 \(A \subseteq C\)이다. (부분집합의 추이성 — 2주차 \(\mid\)의 추이성과 같은 구조다.)

증명. \(A \subseteq B\)이고 \(B \subseteq C\)라 가정하자. \(A \subseteq C\)를 보이려면, \(A\)의 임의의 원소가 \(C\)의 원소임을 보이면 된다. \(x \in A\)라 하자. \(A \subseteq \underline{\quad(1)\quad}\)이므로 \(x \in \underline{\quad(2)\quad}\)이다. 또 \(B \subseteq C\)이므로 \(x \in \underline{\quad(3)\quad}\)이다. 따라서 \(A\)의 임의의 원소는 \(C\)의 원소이므로 \(A \subseteq C\)이다. \(\blacksquare\)

이 오프닝 — “\(x \in A\)라 하자” — 이 27주차 집합 증명의 표준 오프닝이다. 여기서 손에 익혀 둔다.

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

이번에는 조건제시법 집합이다. 구조 낱말과 근거 문장도 빈칸이다. (\(a \mid b\)의 정의는 2주차: \(b = ak\)인 정수 \(k\)가 존재한다.)

명제. \(E = \{x \in \mathbb{Z} : 6 \mid x\}\), \(F = \{x \in \mathbb{Z} : 3 \mid x\}\)이면 \(E \subseteq F\)이다. (문제 12의 예행연습이다.)

증명. \(x \in E\)라 하자. 그러면 \(\underline{\quad(1)\quad}\)이므로, 정의에 의해 \(x = \underline{\quad(2)\quad}\)인 정수 \(k\)가 존재한다. 그러면 \(x = 3(\underline{\quad(3)\quad})\)이고, \(\underline{\quad(4)\quad}\)이므로 \(\underline{\quad(5)\quad}\)는 정수이다. 따라서 \(3 \mid x\), 즉 \(x \in \underline{\quad(6)\quad}\)이다. 그러므로 \(E \subseteq F\)이다. \(\blacksquare\)

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

명제. \(\{6k + 3 : k \in \mathbb{Z}\} \subseteq \{2m + 1 : m \in \mathbb{Z}\}\)이다. (오른쪽은 홀수 전체의 집합이다 — 1주차 정의 1.2.)

증명의 뼈대. §1.6 틀의 세 걸음을 통째로 채운다.

  • ① 원소 잡기: \(\underline{\quad(1)\quad}\)

  • ② 조건 풀기: \(\underline{\quad(2)\quad}\)

  • ③ 목표 집합의 꼴로 재조립과 마무리: \(\underline{\quad(3)\quad}\)

연습문제 (20문항)#

해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 ‘접근’까지만 읽고 다시 시도한다 \(\to\) 그래도 안 되면 풀이를 읽는다.

이번 주의 채점 기준

답이 아니라 근거가 점수다. 참\(\cdot\)거짓 문제에서 “참”만 적으면 0점이고,

어느 절차로 판정했는지 — \(\in\)이면 한 겹 목록 대조, \(\subseteq\)이면 원소

하나씩(거짓이면 못 건너간 원소 지목) — 까지 적어야 만점이다.

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

기본 ●○○#

1. \(\{1, 2, 3, 4\}\)의 부분집합 중 크기가 2인 것을 모두 나열하시오.

힌트

첫 원소를 고정하고 둘째 원소를 훑는 사전식 나열이 빠뜨림을 막는다 —

예제 2.1의 크기 2 칸과 같은 요령. 몇 개가 나와야 하는지 먼저 세어 두면

검산이 된다.

2. 참\(\cdot\)거짓: (a) \(\{1\} \subseteq \{1, 2\}\) (b) \(\{1\} \in \{1, 2\}\) (c) \(1 \in \{1, 2\}\) (d) \(\emptyset \subseteq \{1, 2\}\) (e) \(\emptyset \in \{1, 2\}\)

힌트

문항마다 기호부터 확인한다(§1.5의 표). (d)와 (e)는 같은 \(\emptyset\)인데

기호가 다르다 — 판정 절차도 달라진다.

3. \(\mathcal{P}(\{x, y\})\)를 나열하시오.

힌트

예제 2.1의 크기순 나열 — 칸은 크기 0, 1, 2 셋이고, 양 끝 칸은 §1.4의

사실로 자동이다. 개수 예측: \(2^2\).

4. \(\mathcal{P}(\{a\})\)와 \(\mathcal{P}(\emptyset)\)을 각각 나열하시오.

힌트

개수부터 예측한다 — \(2^1\)과 \(2^0\). 뒤쪽은 예제 2.3에서 계산했다.

\(\mathcal{P}(\emptyset)\)이 공집합이 아니라는 데 주의한다.

5. \(\{1, 2, 3\}\)의 부분집합 8개를 크기순으로 모두 나열하시오.

힌트

예제 2.1의 절차 그대로 — 칸 4개(크기 0~3)를 만들어 채우고 \(1+3+3+1 = 2^3\)으로

검산한다.

6. 참\(\cdot\)거짓: (a) \(\mathbb{Z} \subseteq \mathbb{Q}\) (b) \(\mathbb{Q} \subseteq \mathbb{Z}\) (c) \(\mathbb{N} \subseteq \mathbb{R}\) (d) \(\emptyset \subseteq \mathbb{N}\) (거짓이면 반례 제시)

힌트

참이면 “임의의 원소가 건너가는 이유” 한 줄, 거짓이면 못 건너가는 원소 하나를

지목한다(§1.3). (a)는 §1.1에서 이미 다룬 관계다 — \(n = \frac{n}{1}\).

표준 ●●○ — ∈/⊆ 집중 드릴#

7. \(A = \{1, 2, \{3\}\}\)에 대해 참\(\cdot\)거짓: (a) \(3 \in A\) (b) \(\{3\} \in A\) (c) \(\{3\} \subseteq A\) (d) \(\{\{3\}\} \subseteq A\) (e) \(\{1, 2\} \subseteq A\) (f) \(\{1, 2\} \in A\)

힌트

판정 전에 \(A\)의 한 겹 목록을 박아 둔다: \(1\), \(2\), \(\{3\}\) — 세 개.

모든 문항이 이 목록과의 대조다. 숫자 \(3\)과 상자 \(\{3\}\)은 다른 대상이다.

8. \(B = \{\emptyset, \{\emptyset\}\}\)에 대해 참\(\cdot\)거짓: (a) \(\emptyset \in B\) (b) \(\emptyset \subseteq B\) (c) \(\{\emptyset\} \in B\) (d) \(\{\emptyset\} \subseteq B\) (e) \(\{\{\emptyset\}\} \subseteq B\)

힌트

\(B\)의 한 겹 목록: \(\emptyset\)과 \(\{\emptyset\}\). (b)는 목록을 볼 필요도 없이

판정된다 — §1.4의 어느 사실인가. 나머지는 원소를 꺼내 목록과 대조한다.

9. \(|A| = 5\)일 때 (a) \(A\)의 부분집합 개수, (b) 진부분집합 개수, (c) 원소 1을 반드시 포함하는 부분집합 개수(\(1 \in A\)라 가정)를 구하고 각각 이유를 쓰시오.

힌트

세 문항 모두 “원소마다 넣는다/뺀다”의 생성 원리(§1.7)에서 나온다.

(c)는 1의 선택이 이미 정해졌을 때 남는 선택의 수를 센다.

10. \(\mathcal{P}(\{1, 2, 3\})\)의 원소 중 \(\{1, 2\}\)의 부분집합이기도 한 것을 모두 찾으시오.

힌트

조건을 겹쳐 읽으면 “두 집합 모두의 부분집합”이다. 두 조건 중 어느 쪽이 더

강한가 — 추이성(훈련 1)이 조건 하나를 지워 준다.

11. \(C = \{\emptyset, 1, \{1\}\}\)에 대해 판정하시오 (참/거짓/문법 오류 중 하나로). (a) \(\emptyset \subseteq C\) (b) \(\emptyset \in C\) (c) \(\{1\} \in C\) (d) \(\{1\} \subseteq C\) (e) \(\{\{1\}\} \subseteq C\) (f) \(1 \subseteq C\)

힌트

\(C\)의 한 겹 목록: \(\emptyset\), \(1\), \(\{1\}\). (f)는 판정 전에 문장 자체를

검사한다(§1.5 끝) — \(\subseteq\)의 왼쪽에 올 수 있는 것은 무엇뿐인가.

12. \(E = \{x \in \mathbb{Z} : 4 \mid x\}\), \(F = \{x \in \mathbb{Z} : 2 \mid x\}\)일 때 \(E \subseteq F\)임을 원소 추적(”\(x \in E\)라 하자 \(\to\) …”)으로 보이시오. (8주차 필요\(\cdot\)충분조건의 예습)

힌트

훈련 2가 이 문제의 예행연습이었다 — 수만 6, 3에서 4, 2로 바뀐다.

“\(x \in E\)라 하자”로 시작해 \(4 \mid x\)를 2주차 정의로 풀고,

\(2 \times (\text{정수})\) 꼴로 재조립한다.

13. \(|\mathcal{P}(\mathcal{P}(\{1\}))|\)을 구하시오.

힌트

안쪽부터 층을 오른다 — \(|\{1\}| = 1\)이면 \(|\mathcal{P}(\{1\})|\)은 몇인가,

그 크기에 크기 공식을 한 번 더 적용하면 끝난다. 나열까지 하면 검산이 된다.

14. \(\{1, 2, 3, 4\}\)의 부분집합을 크기별로 세면 각각 몇 개인가? (크기 0, 1, 2, 3, 4) 그 합이 \(2^4\)과 일치함을 확인하시오.

힌트

크기 2 칸은 문제 1에서 이미 셌다. 크기 3 칸은 “뺄 원소 고르기”

(예제 2.1 확인 14)로 세면 빠르다.

도전 ●●●#

15. 참\(\cdot\)거짓을 판정하고 이유를 쓰시오: (a) \(\emptyset \in \mathcal{P}(A)\) (임의의 \(A\)) (b) \(A \in \mathcal{P}(A)\) (임의의 \(A\)) (c) \(\emptyset \subseteq \mathcal{P}(A)\)

힌트

세 문항 전부 번역 규칙(§1.8) 한 줄로 환원된다. (a)와 (c)는 낱말이 비슷하지만

기호가 다르다 — 각각을 번역한 결과를 나란히 적어 비교한다.

16. \(A \subseteq B\)이면 \(\mathcal{P}(A) \subseteq \mathcal{P}(B)\)임을 증명하시오. (힌트: \(X \in \mathcal{P}(A)\)라 하자 \(\to\) 번역 \(X \subseteq A\) \(\to\) 훈련 1의 추이성 사용 \(\to\) 다시 번역.)

힌트

증명할 문장 \(\mathcal{P}(A) \subseteq \mathcal{P}(B)\) 자체가 \(\subseteq\) 문장이므로

§1.6의 틀이 그대로 작동한다 — 오프닝은 “\(X \in \mathcal{P}(A)\)라 하자”.

잡은 원소 \(X\)가 이번에는 집합이라는 것만 다르다.

17. \(\mathcal{P}(A) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}\)일 때 \(A\)를 구하시오. 또, 어떤 집합 \(B\)에 대해 \(\mathcal{P}(B) = \{\emptyset, \{1\}, \{2\}\}\) (원소 3개)가 될 수 있는지 판단하고 이유를 쓰시오.

힌트

전반: \(\mathcal{P}(A)\)의 원소 중 가장 큰 것은 무엇인가 — \(A \subseteq A\)가

답을 준다. 후반: 멱집합이 반드시 갖는 성질 두 가지(크기가 \(2^n\) 꼴,

부분집합의 완비)에 하나씩 대조한다.

이 문제가 미리 쓰는 사고 — 원소가 있다고 해 보기

다음 문제 18처럼 “없다”가 결론인 명제는, 건너갈 원소를 잡는 틀이 잡을 것이

없어 헛돈다. 이럴 때는 방향을 바꾼다 — “원소가 하나라도 있다면 무슨 일이

생기는가”를 따라가서 불가능한 결론이 나오면, 원소는 있을 수 없다.

(이 사고는 21주차 귀류법으로 정식화된다. 지금은 이 문제에서 맛만 본다.)

18. \(A \subseteq \emptyset\)이면 \(A = \emptyset\)임을 설명하시오. (힌트: \(A\)에 원소가 하나라도 있다면 무슨 일이 벌어지는가?)

힌트

원소 \(x \in A\)가 있다고 하면, \(A \subseteq \emptyset\)의 정의가 \(x\)를 어디로

보내야 하는가. 그곳에 자리가 있는가.

이 문제가 미리 쓰는 기호 — \(\cap\)과 \(\cup\)

교집합 \(A \cap B\)는 양쪽에 모두 있는 원소의 집합, 합집합 \(A \cup B\)는 어느

한쪽에라도 있는 원소의 집합이다. 정의는 5주차에서 세우고, 지금은 고1의

기억으로 인정하고 쓴다.

19. \(A = \{1, 2\}\), \(B = \{2, 3\}\)에 대해 \(\mathcal{P}(A \cap B)\)와 \(\mathcal{P}(A) \cap \mathcal{P}(B)\)를 각각 계산해 같음을 확인하시오. 이어서 \(\mathcal{P}(A \cup B)\)와 \(\mathcal{P}(A) \cup \mathcal{P}(B)\)는 같지 않음을 원소 하나로 보이시오.

힌트

집합이 작으므로 네 멱집합을 전부 나열해 대조하는 것이 가장 확실하다.

반례는 “\(A\)에도 \(B\)에도 통째로는 안 들어가는 부분집합” — 양쪽에서 원소를

하나씩 섞으면 만들어진다.

20. 참\(\cdot\)거짓 스피드 드릴 (10연발, 목표: 전부 정답). (a) \(\{1\} \subseteq \{1\}\) (b) \(\{1\} \in \{1\}\) (c) \(\emptyset \subseteq \emptyset\) (d) \(\emptyset \in \emptyset\) (e) \(\{1, 2\} \subseteq \{1, 2, \{1, 2\}\}\) (f) \(\{1, 2\} \in \{1, 2, \{1, 2\}\}\) (g) \(\{\emptyset\} \subseteq \{\emptyset, 1\}\) (h) \(\mathbb{N} \in \mathbb{R}\) (i) \(\{2, 4\} \subseteq \{x \in \mathbb{Z} : 2 \mid x\}\) (j) \(\{0\} \subseteq \emptyset\)

힌트

문항마다 첫 동작은 기호 확인이다. 3초 안에 절차가 떠오르지 않는 문항은

표시해 두고, 드릴이 끝난 뒤 그 문항만 §1.5의 표로 돌아가 재판정한다.

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

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

1차 시도 (4일차) — 틀 카드 허용. 판정 절차 표(§1.5)와 부분집합 증명의 틀(§1.6)만 펴 놓고, 훈련 1(추이성)을 처음부터 끝까지 적는다. 정의 본문은 보지 않는다.

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

  • \(A \subseteq B\)의 정의를 “모든 \(x\)에 대해 \(x \in A\)이면 \(x \in B\)” 형태로 썼다.

  • \(\emptyset \subseteq A\)가 참인 이유를 거짓 판정 조건(못 건너간 원소의 지목)으로 설명했다.

  • \(\in\)과 \(\subseteq\)의 판정 절차를 각각 한 문장으로 말했다.

  • \(\mathcal{P}(\{1, 2\})\)를 백지에 정확히 나열했다 (\(\emptyset\)과 자기 자신 포함).

  • 번역 규칙 \(X \subseteq A \iff X \in \mathcal{P}(A)\)를 썼다.

  • 추이성 증명(훈련 1)을 “\(x \in A\)라 하자”부터 백지에 재현했다.

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

막힌 지점

처방

정의의 문장이 정확히 나오지 않는다

§1.2 해부 표 — 조각의 이유와 함께 다시 외운다

\(\emptyset \subseteq A\)에서 머뭇거린다

§1.4 — 거짓 판정 조건부터 다시 따라간다

\(\in\)/\(\subseteq\) 판정이 뒤섞인다

§1.5의 표 — 그리고 문제 7\(\cdot\)8을 다시 판정한다

추이성 증명의 첫 문장이 나오지 않는다

§1.6의 틀 — 첫 문장은 창작이 아니라 정해진 형식이다

멱집합 나열에서 빠뜨린다

예제 2.1 — 크기순 칸과 \(2^n\) 검산

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

해설#

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

빈칸 사다리 — 훈련 1#

(1) \(B\) (2) \(B\) (3) \(C\)

※ 두 가정이 차례로 쓰인다 — 첫 가정 \(A \subseteq B\)가 \(x\)를 \(A\)에서 \(B\)로, 둘째 가정 \(B \subseteq C\)가 \(B\)에서 \(C\)로 보낸다. 오프닝 “\(x \in A\)라 하자”가 정의의 “모든 \(x\)” 조각을 실행한다(§1.6, 확인 8).

빈칸 사다리 — 훈련 2#

(1) \(6 \mid x\) (2) \(6k\) (3) \(2k\) (4) 정수의 곱은 정수 (근거 ②) (5) \(2k\) (6) \(F\)

※ 조건제시법 집합의 원소 추적은 두 번의 번역이다 — 소속 조건을 정의(2주차)로 풀고, 계산한 뒤, 목표 집합의 소속 조건 꼴로 재조립한다. 문제 12가 같은 구조다.

빈칸 사다리 — 훈련 3#

(1) \(x \in \{6k+3 : k \in \mathbb{Z}\}\)라 하자. (2) 그러면 \(x = 6k + 3\)인 정수 \(k\)가 존재한다. (3) \(x = 6k + 3 = 2(3k + 1) + 1\)이고 \(3k + 1\)은 정수이므로(근거 ②), \(x\)는 \(2m + 1\) 꼴이다(\(m = 3k+1\)). 즉 \(x \in \{2m+1 : m \in \mathbb{Z}\}\)이다. 따라서 포함이 성립한다. \(\blacksquare\)

※ 목표 집합의 꼴(\(2m+1\))이 도착점이다 — 1주차의 “목표 꼴이 나올 때까지 변형”이 집합 표기로 재등장했다.

문제 1#

접근. “크기 2” = 원소 두 개 고르기. 첫 원소를 고정하고 둘째 원소를 훑는 사전식 나열이 빠뜨림과 중복을 막는다. 개수를 먼저 예측해 두면 검산이 된다 — 첫 원소가 1인 것, 2인 것, 3인 것을 각각 세면 \(3 + 2 + 1 = 6\).

풀이. 첫 원소 1: \(\{1,2\}, \{1,3\}, \{1,4\}\). 첫 원소 2 (1과의 짝은 이미 나왔다): \(\{2,3\}, \{2,4\}\). 첫 원소 3: \(\{3,4\}\). 따라서

\[ \{1,2\},\ \{1,3\},\ \{1,4\},\ \{2,3\},\ \{2,4\},\ \{3,4\} \]

— 모두 6개다. (검산: 문제 14의 크기별 세기에서 크기 2가 6개 — 일치 ✓.)

문제 2#

접근. 문항마다 기호를 먼저 본다(§1.5의 표): \(\in\)이면 “한 겹 목록에 통째로 있는가”, \(\subseteq\)이면 “원소를 하나씩 건너 보내기”. \(\{1,2\}\)의 한 겹 목록은 \(1\)과 \(2\)다.

풀이. (a) 참 — \(\subseteq\) 판정: \(\{1\}\)의 원소 \(1\)이 \(\{1,2\}\)에 있다. 원소 하나뿐이므로 전수 검사 끝. (b) 거짓 — \(\in\) 판정: 목록(\(1\), \(2\))에 상자 \(\{1\}\)은 없다. (c) 참 — \(\in\) 판정: 목록에 \(1\)이 있다. (d) 참 — 공허한 참(§1.4): \(\emptyset\)은 모든 집합의 부분집합이다. (e) 거짓 — \(\in\) 판정: 목록에 \(\emptyset\)이 없다.

복기. (d)와 (e)의 대비가 이번 주의 핵심이다 — 같은 \(\emptyset\)이라도 \(\subseteq\) 질문에서는 언제나 통과하고, \(\in\) 질문에서는 목록에 실제로 적혀 있어야 한다. 기호가 절차를 정하고, 절차가 답을 정한다.

문제 3#

접근. 예제 2.1의 크기순 나열 — 칸은 크기 0, 1, 2 셋. 개수 예측 \(2^2 = 4\).

풀이. 크기 0: \(\emptyset\)(공허한 참). 크기 1: \(\{x\}, \{y\}\). 크기 2: \(\{x, y\}\)(자기 자신). 따라서

\[ \mathcal{P}(\{x, y\}) = \{\emptyset, \{x\}, \{y\}, \{x, y\}\} \]

검산: 4개 \(= 2^2\) ✓.

문제 4#

접근. 개수부터 예측한다 — \(2^1 = 2\)개와 \(2^0 = 1\)개. 그다음 크기순으로 나열해 예측과 대조한다.

풀이. \(\mathcal{P}(\{a\})\): 크기 0의 \(\emptyset\)과 크기 1의 \(\{a\}\)(자기 자신) —

\[ \mathcal{P}(\{a\}) = \{\emptyset, \{a\}\} \qquad (2 = 2^1 \text{ ✓}) \]

\(\mathcal{P}(\emptyset)\): \(\emptyset\)의 부분집합은 자기 자신 하나뿐이므로(예제 2.3)

\[ \mathcal{P}(\emptyset) = \{\emptyset\} \qquad (1 = 2^0 \text{ ✓}) \]

※ \(\mathcal{P}(\emptyset)\)은 공집합이 아니다 — 크기 1이지 0이 아니다. “빈 상자”와 “빈 상자가 든 상자”의 구분(3주차)이 여기서 다시 쓰인다.

문제 5#

접근. 예제 2.1의 크기순 나열 그대로 — 칸 4개를 만들어 채우고 개수로 검산한다.

풀이. 크기 0: \(\emptyset\) / 크기 1: \(\{1\}, \{2\}, \{3\}\) / 크기 2: \(\{1,2\}, \{1,3\}, \{2,3\}\) / 크기 3: \(\{1,2,3\}\).

검산: \(1 + 3 + 3 + 1 = 8 = 2^3\) ✓. 양 끝 칸(\(\emptyset\)과 자기 자신)이 §1.4의 사실로 자동이라는 것까지 확인하면 나열이 닫힌다.

문제 6#

접근. 수 체계 사이의 \(\subseteq\) 판정. 참이면 임의의 원소가 건너가는 이유를 한 줄로, 거짓이면 못 건너가는 원소 하나를 지목한다(§1.3).

풀이. (a) 참 — \(n \in \mathbb{Z}\)라 하자. \(n = \frac{n}{1}\)이고 \(n, 1 \in \mathbb{Z}\), \(1 \neq 0\)이므로 \(n\)은 \(\mathbb{Q}\)의 정의(두 정수의 비)를 만족한다. 즉 \(n \in \mathbb{Q}\). (b) 거짓 — 반례: \(\frac{1}{2} \in \mathbb{Q}\)이지만 \(0 < \frac{1}{2} < 1\)이므로 정수가 아니다. 못 건너간 원소 하나로 판정 끝. (c) 참 — §1.3의 사슬 \(\mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R}\)에 추이성(훈련 1)을 두 번 적용하면 \(\mathbb{N} \subseteq \mathbb{R}\)이 나온다. (d) 참 — 공허한 참: \(\emptyset\)의 원소 중 \(\mathbb{N}\)에 없는 것을 지목할 수 없다.

복기. (c)에서 추이성이 벌써 부품(근거 ④)으로 쓰였다 — 증명된 명제는 다음 판정의 근거가 된다.

문제 7#

접근. 판정 전에 \(A\)의 한 겹 목록을 박아 둔다: \(1\), \(2\), \(\{3\}\) — 세 개. 모든 문항을 이 목록과의 대조로 환원한다. \(\subseteq\) 문항은 왼쪽 원소를 꺼내 \(\in\) 질문으로 바꾼다(예제 2.2).

풀이. (a) 거짓 — 숫자 \(3\)은 한 겹 목록에 없다. \(\{3\}\) 속은 열지 않는다(3주차 한 겹 규칙). (b) 참 — 목록에 상자 \(\{3\}\)이 통째로 있다. (c) 거짓 — \(\subseteq\) 판정: \(\{3\}\)의 원소 \(3\)을 꺼내면 질문이 “\(3 \in A\)?”가 되는데, (a)에서 거짓이었다. (d) 참 — \(\{\{3\}\}\)의 원소는 \(\{3\}\) 하나. “\(\{3\} \in A\)?”는 (b)에서 참이었다. (e) 참 — \(1 \in A\) ✓, \(2 \in A\) ✓. 전수 검사 통과. (f) 거짓 — 목록에 상자 \(\{1,2\}\)는 없다.

복기. \(\subseteq\) 판정은 전부 \(\in\) 질문으로 환원됐다 — (c)는 (a)로, (d)는 (b)로. 층을 하나 벗기면 이미 푼 문제가 된다.

문제 8#

접근. \(B\)의 한 겹 목록: \(\emptyset\)과 \(\{\emptyset\}\). (b)만 목록과 무관하게 즉시 판정되고(공허한 참), 나머지는 원소를 꺼내 목록과 대조한다.

풀이. (a) 참 — 목록 첫 자리에 \(\emptyset\)이 있다. (b) 참 — 공허한 참: \(\emptyset\)은 모든 집합의 부분집합이다(§1.4). (c) 참 — 목록 둘째 자리에 \(\{\emptyset\}\)이 있다. (d) 참 — \(\{\emptyset\}\)의 원소는 \(\emptyset\) 하나. “\(\emptyset \in B\)?”는 (a)에서 참이었다. (e) 참 — \(\{\{\emptyset\}\}\)의 원소는 \(\{\emptyset\}\) 하나. “\(\{\emptyset\} \in B\)?”는 (c)에서 참이었다.

※ (b)와 (d)는 둘 다 참이지만 이유가 다르다 — (b)는 어길 원소가 없어서(공허한 참), (d)는 원소 \(\emptyset\)을 실제로 추적한 결과다. 근거까지 적어야 만점인 이유가 이 대비에 있다.

문제 9#

접근. 세 문항 모두 생성 원리(§1.7) — “부분집합 하나 = 원소마다 넣는다/뺀다의 결정” — 에서 나온다. (c)는 결정 하나가 고정됐을 때 남는 자유도를 센다.

풀이. (a) \(2^5 = 32\)개. 부분집합 하나를 만드는 일은 다섯 원소 각각에 “넣는다/뺀다”를 정하는 일이고, 각 결정이 2가지이므로 \(2 \times 2 \times 2 \times 2 \times 2 = 32\). (b) \(32 - 1 = 31\)개. 진부분집합은 “부분집합이고 자기 자신은 아닌 것”(§1.3) — (a)의 32개에서 제외되는 것은 \(A\) 자신 하나뿐이다. (\(\emptyset\)은 \(A \neq \emptyset\) 이므로 진부분집합에 포함된다.) (c) \(2^4 = 16\)개. 원소 1의 결정은 “넣는다”로 고정됐으므로, 자유로운 결정은 남은 네 원소의 것뿐이다 — \(2^4\).

복기. 세 답이 전부 한 원리의 변주다 — 개수 문제는 “무엇을 자유롭게 정할 수 있는가”를 세는 문제로 바뀐다. (12주차 세기에서 이 감각을 정식으로 훈련한다.)

문제 10#

접근. 구하는 것을 조건으로 다시 적으면 — \(X \in \mathcal{P}(\{1,2,3\})\)이면서 \(X \subseteq \{1,2\}\)인 \(X\), 곧 (번역 규칙) \(X \subseteq \{1,2,3\}\)이고 \(X \subseteq \{1,2\}\)인 \(X\). 두 조건 중 어느 쪽이 다른 쪽을 함의하는지 본다.

풀이. \(X \subseteq \{1,2\}\)이면 \(\{1,2\} \subseteq \{1,2,3\}\)과 추이성(훈련 1)에 의해 \(X \subseteq \{1,2,3\}\)이 자동으로 성립한다. 즉 둘째 조건이 더 강하고, 답은 \(\{1,2\}\)의 부분집합 전부다:

\[ \emptyset,\ \{1\},\ \{2\},\ \{1,2\} \]

검산: 네 개 모두 \(\{1,2,3\}\)의 부분집합이기도 하다 ✓ (\(4 = 2^2\)개 — 크기 공식과도 일치).

복기. 조건 두 개가 겹칠 때 강한 쪽 하나로 줄이는 것 — 추이성의 실전 용법이다.

문제 11#

접근. \(C\)의 한 겹 목록: \(\emptyset\), \(1\), \(\{1\}\). 이번 집합은 숫자 \(1\)이 실제 원소라는 점이 문제 7과 다르다. (f)는 판정 전에 문장 검사부터(§1.5 끝).

풀이. (a) 참 — 공허한 참(§1.4). 목록과 무관하다. (b) 참 — 목록에 \(\emptyset\)이 있다. ((a)와 이유가 다르다 — 이쪽은 목록 대조다.) (c) 참 — 목록에 \(\{1\}\)이 있다. (d) 참 — \(\{1\}\)의 원소 \(1\)을 꺼내면 “\(1 \in C\)?” — 목록에 \(1\)이 있다. (문제 7(c)와 대비: 거기서는 숫자 3이 원소가 아니어서 거짓이었다.) (e) 참 — \(\{\{1\}\}\)의 원소 \(\{1\}\)은 (c)에서 원소임이 확인됐다. (f) 문법 오류 — \(1\)은 집합이 아니므로 \(\subseteq\)의 왼쪽에 올 수 없다. 참\(\cdot\)거짓 이전에 문장이 성립하지 않는다. (2주차 문제 6의 “\(3 \mid 12 = 4\)”와 같은 유형의 검사다.)

복기. 판정 문제의 순서는 문법 검사 \(\to\) 기호 확인 \(\to\) 절차 적용이다. 문법 단계에서 걸러지는 문항은 절차로 들어가면 안 된다.

문제 12#

접근. 훈련 2와 같은 구조 — 수만 6, 3에서 4, 2로 바뀐다. 오프닝 “\(x \in E\)라 하자”(§1.6의 틀) \(\to\) 소속 조건 \(4 \mid x\)를 2주차 정의로 풀기 \(\to\) 목표 조건 \(2 \mid x\)의 꼴 \(2 \times (\text{정수})\)로 재조립.

풀이. \(x \in E\)라 하자. 그러면 \(4 \mid x\)이므로, 정의에 의해 \(x = 4k\)인 정수 \(k\)가 존재한다. 그러면

\[ x = 4k = 2(2k) \]

이고 \(2k\)는 정수이므로(근거 ② — 정수의 곱은 정수) \(2 \mid x\)이다. 즉 \(x \in F\)이다. 따라서 \(E\)의 임의의 원소는 \(F\)의 원소이므로 \(E \subseteq F\)이다. \(\blacksquare\)

(검산: \(12 \in E\)(\(12 = 4 \times 3\))이고 \(12 \in F\)(\(12 = 2 \times 6\)) ✓ — 검산은 증명이 아니지만 오류 탐지기로는 쓸 만하다.)

복기. 조건제시법 집합의 \(\subseteq\) 증명은 “왼쪽 조건이 오른쪽 조건을 함의함”을 보이는 것이다 — 이 관점이 8주차 필요\(\cdot\)충분조건의 예습이다.

문제 13#

접근. 층을 안쪽부터 오른다 — \(|\{1\}| = 1\)에서 크기 공식으로 한 층씩. 나열까지 해 보면 공식과 대조하는 검산이 된다.

풀이. 안쪽: \(\mathcal{P}(\{1\}) = \{\emptyset, \{1\}\}\) — 크기 \(2 = 2^1\). 바깥: 크기 2인 집합의 멱집합이므로

\[ |\mathcal{P}(\mathcal{P}(\{1\}))| = 2^2 = 4 \]

검산(나열): \(\{\emptyset, \{1\}\}\)의 부분집합은 크기순으로 \(\emptyset\), \(\{\emptyset\}\), \(\{\{1\}\}\), \(\{\emptyset, \{1\}\}\) — 4개 ✓.

복기. 멱집합을 겹칠 때는 “원소가 무엇인지”를 층마다 다시 묻는다 — 바깥 층의 원소는 수가 아니라 안쪽 멱집합의 부분집합들이다.

문제 14#

접근. 크기별로 직접 센다 — 크기 2는 문제 1에서 이미 셌고, 크기 3은 “뺄 원소 고르기”(예제 2.1 확인 14)로 세면 빠르다. 합이 \(2^4 = 16\)인지로 전체를 검산한다.

풀이. 크기 0: \(\emptyset\) — 1개. 크기 1: \(\{1\}, \{2\}, \{3\}, \{4\}\) — 4개. 크기 2: 문제 1의 나열 그대로 — 6개. 크기 3: 뺄 원소 고르기 4가지 — \(\{2,3,4\}, \{1,3,4\}, \{1,2,4\}, \{1,2,3\}\) — 4개. 크기 4: \(\{1,2,3,4\}\) 자신 — 1개.

합: \(1 + 4 + 6 + 4 + 1 = 16 = 2^4\) ✓.

복기. 크기별 개수의 합 = 전체 개수 — 같은 집합을 두 방식으로 센 것이다. 이 수열 \(1, 4, 6, 4, 1\)은 파스칼 삼각형의 한 줄이다(13주차에서 정체가 밝혀진다).

문제 15#

접근. 세 문항 전부 번역 규칙(§1.8) \(X \subseteq A \iff X \in \mathcal{P}(A)\)로 환원한다. (a)와 (c)는 낱말이 비슷해 보여도 기호가 다르다 — 번역 결과를 나란히 놓고 비교한다.

풀이. (a) 참. \(\emptyset \subseteq A\)는 공허한 참(§1.4)으로 항상 성립하고, 번역 규칙에 의해 이것은 \(\emptyset \in \mathcal{P}(A)\)와 같은 말이다. (b) 참. \(A \subseteq A\)는 항상 성립하고(§1.3), 번역하면 \(A \in \mathcal{P}(A)\)다. (c) 참. 이번 기호는 \(\subseteq\)다 — \(\emptyset\)은 모든 집합의 부분집합이고 \(\mathcal{P}(A)\)도 집합이므로 \(\emptyset \subseteq \mathcal{P}(A)\).

※ (a)와 (c)는 다른 명제다 — (a)는 “\(\mathcal{P}(A)\)의 원소 목록에 \(\emptyset\)이 있다”(\(\in\)), (c)는 “\(\emptyset\)의 원소가 전부 \(\mathcal{P}(A)\)로 건너간다”(공허한 \(\subseteq\)). 같은 낱말들로 만든 다른 문장이고, 참인 이유도 각각 다르다.

복기. 멱집합 문제의 첫 동작은 언제나 번역이다 — \(\in\)의 층과 \(\subseteq\)의 층을 오가며, 지금 어느 층에 있는지를 놓치지 않는 것이 전부다.

문제 16#

접근. 증명할 문장 \(\mathcal{P}(A) \subseteq \mathcal{P}(B)\) 자체가 \(\subseteq\) 문장이므로 §1.6의 틀대로 오프닝은 “\(X \in \mathcal{P}(A)\)라 하자”. 그다음 할 수 있는 일은 번역(\(\in \to \subseteq\))뿐이다. 재료가 \(X \subseteq A\)와 \(A \subseteq B\)가 되는 순간 추이성(훈련 1)이 보이고, 마지막에 역번역으로 도착한다.

풀이. \(A \subseteq B\)라 가정하자. \(X \in \mathcal{P}(A)\)라 하자. 멱집합의 정의(번역 규칙)에 의해 \(X \subseteq A\)이다. \(X \subseteq A\)이고 \(A \subseteq B\)이므로, 부분집합의 추이성(훈련 1 — 근거 ④)에 의해 \(X \subseteq B\)이다. 다시 번역 규칙에 의해 \(X \in \mathcal{P}(B)\)이다. 따라서 \(\mathcal{P}(A)\)의 임의의 원소는 \(\mathcal{P}(B)\)의 원소이므로 \(\mathcal{P}(A) \subseteq \mathcal{P}(B)\)이다. \(\blacksquare\)

복기. 증명 전체가 “번역(\(\in \to \subseteq\)) \(\to\) 추이성 \(\to\) 역번역(\(\subseteq \to \in\))” 세 동작이다. 정의가 양방향 번역기로 쓰였다 — 이 구조는 28주차에서 역방향까지 완성되어 iff가 된다.

문제 17#

접근. 전반 — 멱집합에서 원래 집합을 복원한다. \(A \in \mathcal{P}(A)\) (문제 15(b))이고 \(\mathcal{P}(A)\)의 모든 원소가 \(A\)의 부분집합이므로, \(A\)는 목록에서 “다른 모든 원소를 부분집합으로 갖는” 가장 큰 원소다. 후반 — 멱집합이 반드시 갖는 성질(크기 \(2^n\), 부분집합의 완비)에 어긋나는지 검사한다.

풀이. 전반: 목록 \(\{\emptyset, \{a\}, \{b\}, \{a,b\}\}\)에서 나머지 셋 (\(\emptyset\), \(\{a\}\), \(\{b\}\))을 전부 부분집합으로 갖는 원소는 \(\{a, b\}\)뿐이다. 따라서 \(A = \{a, b\}\). 검산: \(\mathcal{P}(\{a,b\})\)를 크기순으로 나열하면 \(\emptyset, \{a\}, \{b\}, \{a,b\}\) — 주어진 목록과 일치 ✓.

후반: 불가능하다. 근거는 두 겹이다. ① 크기 — 멱집합의 크기는 항상 \(2^n\) 꼴(\(1, 2, 4, 8, \dots\))인데 3은 \(2^n\) 꼴이 아니다. ② 완비성 — \(\{1\} \in \mathcal{P}(B)\)이면 번역에 의해 \(\{1\} \subseteq B\), 즉 \(1 \in B\)이고, 같은 이유로 \(2 \in B\)이다. 그러면 \(\{1,2\} \subseteq B\)이므로 \(\{1,2\}\)도 \(\mathcal{P}(B)\)의 원소여야 하는데 목록에 없다. 멱집합은 부분집합 전부를 빠짐없이 담아야 하므로(정의 4.2의 “전부” 조각), 이 목록은 어떤 집합의 멱집합도 아니다.

복기. 아무 집합이나 멱집합이 될 수는 없다 — 크기 검사와 완비성 검사라는 두 관문이 있고, 하나만 무너져도 탈락이다.

문제 18#

접근. “없다”가 결론인 명제는 건너갈 원소를 잡는 틀이 헛돈다. 문제 앞 상자대로 방향을 바꾼다 — 원소가 하나라도 있다면 정의가 그 원소를 \(\emptyset\)으로 보내야 하는데, 거기에는 자리가 없다.

풀이. \(A \subseteq \emptyset\)이라 하자. 만약 \(A\)에 원소 \(x\)가 하나라도 있다면, \(\subseteq\)의 정의에 의해 (\(x \in A\)이므로) \(x \in \emptyset\)이어야 한다. 그러나 \(\emptyset\)에는 원소가 없으므로(3주차 정의 3.2) \(x \in \emptyset\)은 성립할 수 없다. 따라서 \(A\)에는 원소가 있을 수 없고, 원소가 하나도 없는 집합이 곧 공집합이므로 \(A = \emptyset\)이다.

복기. “없다”의 증명 = “있다면 불가능이 생긴다” — 이 사고가 21주차 귀류법으로 정식화된다. 한편 \(\emptyset \subseteq A\)(§1.4)와 합치면 “\(A \subseteq \emptyset\)과 \(A = \emptyset\)은 같은 말”이라는 관찰도 얻는다.

문제 19#

접근. 집합이 작으므로 네 멱집합을 전부 나열해 대조하는 것이 가장 확실하다. 합집합 쪽 반례는 “\(A\)에도 \(B\)에도 통째로는 안 들어가는 부분집합” — 양쪽에서 원소를 하나씩 섞어 만든다.

풀이. 교집합 쪽: \(A \cap B = \{2\}\)(양쪽에 모두 있는 원소는 2뿐 — 1은 \(B\)에, 3은 \(A\)에 없다)이므로

\[ \mathcal{P}(A \cap B) = \{\emptyset, \{2\}\} \]

한편 \(\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}\), \(\mathcal{P}(B) = \{\emptyset, \{2\}, \{3\}, \{2,3\}\}\)이고, 두 목록에 공통으로 있는 원소는 \(\emptyset\)과 \(\{2\}\)다. 따라서 \(\mathcal{P}(A) \cap \mathcal{P}(B) = \{\emptyset, \{2\}\}\) — 일치 ✓.

합집합 쪽: \(A \cup B = \{1, 2, 3\}\)이므로 \(\{1, 3\} \subseteq A \cup B\), 즉 \(\{1,3\} \in \mathcal{P}(A \cup B)\)이다. 그러나 \(3 \notin A\)이므로 \(\{1,3\} \nsubseteq A\)이고, \(1 \notin B\)이므로 \(\{1,3\} \nsubseteq B\)다 — 따라서 \(\{1,3\}\)은 \(\mathcal{P}(A)\)에도 \(\mathcal{P}(B)\)에도 없고, 그 합집합에도 없다. 한쪽에만 있는 원소 \(\{1,3\}\)이 지목되었으므로 두 집합은 다르다.

(교집합 쪽이 항상 같다는 일반 증명 “\(\mathcal{P}(A \cap B) = \mathcal{P}(A) \cap \mathcal{P}(B)\)”는 27주차에서 한다.)

복기. 반례 제작의 요령 — “양쪽에서 하나씩 섞은” 부분집합은 어느 한쪽에도 통째로 담기지 않는다. 수치 실험(이 문제)이 먼저 오고, 일반 증명(27~28주차)이 뒤따르는 것이 이 교재의 리듬이다.

문제 20#

접근. 문항마다 3초 안에 — 기호 확인 \(\to\) 절차 적용. 헷갈리는 순간 정의로 돌아간다. 근거는 한 구절이면 충분하다.

풀이. (a) 참 — \(A \subseteq A\)(§1.3). (b) 거짓 — \(\{1\}\)의 한 겹 목록에는 \(1\)뿐, 상자 \(\{1\}\)은 없다. (c) 참 — 공허한 참(이자 자기 자신 — 두 근거 모두 성립). (d) 거짓 — \(\emptyset\)의 목록은 비어 있다: \(\emptyset\)이라는 원소도 없다. (e) 참 — \(1\), \(2\) 모두 건너간다. (f) 참 — 상자 \(\{1,2\}\)가 목록에 통째로 있다. ((e)(f)는 §1.5의 예 그대로 — \(\subseteq\)와 \(\in\)의 동시 성립.) (g) 참 — \(\{\emptyset\}\)의 원소 \(\emptyset\)이 오른쪽 목록에 있다. (h) 거짓 — \(\mathbb{N}\)은 실수(수직선 위의 점)가 아니라 집합이므로 \(\mathbb{R}\)의 원소가 아니다. (i) 참 — \(2 = 2 \times 1\), \(4 = 2 \times 2\)이므로 둘 다 조건 \(2 \mid x\)를 만족한다. (j) 거짓 — \(0 \in \{0\}\)인데 \(\emptyset\)에는 건너갈 자리가 없다. 못 건너간 원소 \(0\)의 지목으로 끝.

복기. 10문항 전부가 §1.5의 표 두 줄의 반복이었다 — 이 주에 새로 외울 것은 정의 두 개와 절차 두 줄, 번역 규칙 한 줄이 전부다.

다음 주 예고: 집합끼리의 연산(\(\cup, \cap, -\), 여집합)을 정의하고, 고1 때 외운 벤 다이어그램의 사실들(드모르간 법칙 등)을 관찰한다. 그 관찰은 27주차에서 증명으로 승격되고, 이번 주의 원소 추적 틀이 그 증명의 뼈대가 된다.