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

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

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

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

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

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

|  | **내용** |
|---|---|
| 목표 | $A$의 부분집합 **전부** — 빠뜨림 없이, 중복 없이 |
| 검산 수단 | 개수 공식 $2^{\vert A\vert } = 2^3 = 8$ (§1.7) — 개수가 어긋나면 빠뜨림이 있다 |
| 전략 | 크기 0부터 3까지 칸을 만들어 두고 칸마다 채운다 (**크기순 나열**) |

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

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

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

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

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

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

:::{container} quotebox
**확인 13.** 크기 1 칸을 채워 보자. 몇 개가 나와야 하는가?
:::

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

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

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

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

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

**뺄 원소 하나를 고르는 것**과 같다. $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$ 질문으로 환원한다 — 도착점 |

:::{container} quotebox
**확인 15.** 첫 두 동작을 적어 보자.

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

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

"$\underline{\quad} \in B$인가?"라는 질문으로 환원된다.
:::

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

① 왼쪽 집합의 원소를 하나씩 꺼내 전부 $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). |

:::{container} quotebox
**확인 16.** 같은 재료로 $\{2\} \in B$를 판정해 보자.
:::

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

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

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

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

### 예제 2.3 — 겹겹의 멱집합

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

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

:::{container} quotebox
**확인 17.** 멱집합을 구하는 절차는 예제 2.1에서 세웠다. 안쪽

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

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

첫 질문: "$\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$계산으로 다르지만, 세 예제의 첫 동작은 같다. 대응표의 빈칸을 채워 보자.

:::{container} quotebox
**확인 18.** 각 예제에서 "기호(개념)를 정의의 절차로 바꾼" 지점을 찾아 보자.

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

② 예제 2.2 — "$\subseteq$ 판정"이 어떤 질문이 되었는가: $\underline{\qquad}$

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

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

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

② 왼쪽 원소를 꺼내 만든 "$2 \in B$인가?"라는 $\in$ 질문.

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

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

집합판이다.
:::

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

:::{admonition} 기호를 정의의 절차로 바꾼다
:class: quotebox

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

§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$ 그래도 안 되면 풀이를 읽는다.

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

답이 아니라 **근거**가 점수다. 참$\cdot$거짓 문제에서 "참"만 적으면 0점이고,

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

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

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

### 기본 ●○○

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

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

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

예제 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\}$

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

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

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

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

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

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

사실로 자동이다. 개수 예측: $2^2$.
:::

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

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

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

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

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

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

예제 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}$ (거짓이면 반례 제시)

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

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

지목한다(§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$

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

판정 전에 $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$

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

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

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

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

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

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

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

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

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

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

강한가 — 추이성(훈련 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$

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

$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$충분조건의 예습)

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

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

"$x \in E$라 하자"로 시작해 $4 \mid x$를 2주차 정의로 풀고,

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

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

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

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

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

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

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

크기 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)$

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

세 문항 전부 번역 규칙(§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$ 다시 번역.)

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

증명할 문장 $\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개)가 될 수 있는지 판단하고 이유를 쓰시오.

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

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

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

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

:::{admonition} 이 문제가 미리 쓰는 사고 — 원소가 있다고 해 보기
:class: quotebox

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

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

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

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

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

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

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

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

:::{admonition} 이 문제가 미리 쓰는 기호 — $\cap$과 $\cup$
:class: quotebox

교집합 $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)$는 같지 **않음**을 원소 하나로 보이시오.

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

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

반례는 "$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$

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

문항마다 첫 동작은 기호 확인이다. 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주차에서 증명으로 승격되고, 이번 주의 원소 추적 틀이 그 증명의 뼈대가 된다.