# 4주차 — 부분집합과 멱집합

:::{admonition} 이 주의 길잡이
:class: keybox

**핵심 문장**: $\subseteq$는 "모든 원소가 건너간다"는 약속이다.

**이 주의 위치**: 50주 과정의 4주차. 3주차의 $\in$ 위에 $\subseteq$와 멱집합을 세운다 — 고1 '집합' 단원의 부분집합$\cdot$진부분집합이 여기서 재건축되고, 27주차 집합 증명의 틀("$x \in A$라 하자")을 처음 만든다.

**원서 대응**: BoP(Book of Proof) 1.3–1.4. 원서 없이 읽을 수 있다.
:::

## 이번 주 목표

1. $A \subseteq B$의 **정의**를 "모든 ~이면 ~" 형태로 정확히 쓰고, 각 조각이 왜 필요한지 설명할 수 있다.
1. $\in$과 $\subseteq$를 느낌이 아니라 **절차**로 판정한다 — 20문항 연속으로 틀리지 않는 것이 기준이다.
1. $\emptyset \subseteq A$가 참인 이유(공허한 참)를 설명할 수 있다.
1. 멱집합 $\mathcal{P}(A)$를 빠뜨림 없이 나열하고, 번역 규칙 $X \subseteq A \iff X \in \mathcal{P}(A)$를 쓸 수 있다.

## 준비 운동 (3주차 복습)

1. $\mathbb{Q}$의 정의를 조건제시법으로 쓰시오.
1. $\{x \in \mathbb{Z} : x^2 \le 6\}$을 나열하시오.
1. $B = \{\{1\}, 2\}$일 때 $1 \in B$의 참$\cdot$거짓과 이유를 쓰시오.

1번의 답: $\mathbb{Q} = \{\frac{a}{b} : a, b \in \mathbb{Z},\ b \neq 0\}$. 2번의 답: $\{-2, -1, 0, 1, 2\}$ — $x^2 \le 6$인 정수는 $-2$부터 $2$까지다($(\pm 3)^2 = 9 > 6$).

### 3번에서 자주 나오는 세 가지 답

3번이 이번 주의 출발점이다. 방금 쓴 답은 대개 다음 세 유형 중 하나다.

- **유형 1 — "참. 1이 보인다."** $\{1\}$ 속의 1을 본 관찰 자체는 정확하다. 간격은

$\in$ 판정의 규칙을 적용하지 않은 데 있다 — 원소인지는 **한 겹만** 본다(3주차). $B$의 한 겹 목록은 $\{1\}$과 $2$이고, 숫자 1은 그 목록에 없다. 이번 주 내내 이 한 겹 규칙이 새 기호 $\subseteq$와 부딪히며 단련된다.

- **유형 2 — "거짓. 원소는 $\{1\}$과 2뿐."** 정확하다. 원소 목록을 먼저 적어 두고

대조하는 이 절차가 이번 주 문제 전체의 기본 동작이다.

- **유형 3 — 판정 유보.** $\{1\}$과 $1$이 같은 것인지에서 멈췄다. 멈춘 자리가

정확한 질문이다 — 상자 $\{1\}$(크기 1의 집합)과 수 $1$은 다른 대상이고, 이 구분을 놓치는 지점을 이번 주 문제 7$\cdot$8$\cdot$11이 집중 훈련한다.

## 개념 — ⊆와 멱집합

### 1 ∈ 하나로는 적을 수 없는 관계

3주차 끝에서 확인한 사실이 있다: 모든 정수는 유리수다($n = \frac{n}{1}$). 이 관계를 기호로 적어 두려 한다. 지금 가진 기호는 $\in$뿐이므로 그것으로 시도해 보자.

:::{admonition} 시도 — $\in$으로 밀어붙이기
:class: quotebox

"$\mathbb{Z}$의 원소가 전부 $\mathbb{Q}$의 원소다"를 $\mathbb{Z} \in \mathbb{Q}$로 적는다.
:::

:::{container} quotebox
**확인 1.** $\mathbb{Z} \in \mathbb{Q}$는 참인가? 3주차의 한 겹 규칙으로 판정해 보자 —

$\mathbb{Q}$의 원소 목록에는 무엇이 들어 있는가?
:::

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

거짓이다. $\mathbb{Q}$의 원소는 $\frac{1}{2}$, $-3$, $\frac{7}{5}$ 같은 유리수

하나하나다. $\mathbb{Z}$는 수가 아니라 상자(집합)이므로 그 목록에 통째로 들어

있지 않다. $\in$은 왼쪽 대상을 **통째로** 오른쪽의 한 겹 목록과 대조하는 기호다 —

내용물을 하나씩 꺼내 대조하는 일은 $\in$의 일이 아니다.
:::

표현하고 싶은 관계 — "내용물이 전부 건너간다" — 는 성립하는 관계인데, 그것을 적을 기호가 없다. 새 기호가 필요한 자리다.

### 2 대조 실험 — 표를 채우고 이름 붙이기

작은 집합으로 "원소가 전부 건너가는가"를 직접 대조해 보자. $B = \{1, 2, 3\}$에 대해:

| **$A$** | **$A$의 원소를 하나씩 — $B = \{1,2,3\}$에 있는가** | **전부 통과?** |
|---|---|---|
| $\{1, 3\}$ | $1$ ✓, $3$ ✓ | 통과 |
| $\{1, 4\}$ | $1$ ✓, $4$ ✗ | 탈락 |
| $\{2\}$ | $\underline{\quad(1)\quad}$ | $\underline{\quad(2)\quad}$ |
| $\{1, 2, 3\}$ | $\underline{\quad(3)\quad}$ | $\underline{\quad(4)\quad}$ |

:::{container} quotebox
**확인 2.** 표의 빈칸 (1)~(4)를 채워 보자. 둘째 행($\{1,4\}$)에서 원소 $1$은

건너갔는데도 판정이 탈락인 이유는 무엇인가?
:::

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

(1) $2$ ✓  (2) 통과  (3) $1$ ✓, $2$ ✓, $3$ ✓  (4) 통과.

탈락의 이유: 대조는 **전수 검사**다 — 하나만 실패해도 탈락이다. 마지막 행에서

자기 자신도 통과한다는 것을 관찰해 둔다(§1.3에서 다시 쓴다).
:::

이 대조에 정식 이름과 형식을 붙인다. 식 자체에 새로운 것은 없다 — 방금 표에서 한 대조를 문장으로 굳혔을 뿐이다.

### 정의 4.1 — 부분집합 (subset) [백지 암기 대상]

:::{container} quotebox
$A$의 **모든** 원소가 $B$의 원소일 때, $A$는 $B$의 **부분집합**이라 하고 $A \subseteq B$로 쓴다.

즉, $A \subseteq B$ $\iff$ "모든 $x$에 대해, $x \in A$이면 $x \in B$이다."
:::

"$A \subseteq B$"는 "에이는 비의 부분집합이다" 또는 "에이는 비에 포함된다"로 읽는다. 부분집합이 아니면 $A \nsubseteq B$로 쓴다 — "에이는 비의 부분집합이 아니다"로 읽는다.

**정의 해부.** 뒷문장은 세 조각으로 되어 있고, 조각마다 하는 일이 다르다.

| **조각** | **하는 일** | **증명에서의 역할** |
|---|---|---|
| "모든 $x$에 대해" | 검사 범위의 선언 — 전수 검사 | "임의의 $x \in A$를 잡는" 문장으로 실행된다 (§1.6) |
| "$x \in A$이면" | 심사 대상의 한정 | $A$ 밖의 대상은 심사받지 않는다 — $\emptyset$의 판정(§1.4)이 여기서 갈린다 |
| "$x \in B$이다" | 통과 조건 | 원소 추적의 도착점 — $x$가 $B$의 원소임을 보이면 끝난다 |

**조각 삭제 실험.** 첫 조각 "모든"을 지워 보자. "어떤 원소 하나라도 건너가면 부분집합"으로 읽히게 되고, 그러면 $\{1, 4\}$도 — $1$이 건너가므로 — $\{1,2,3\}$의 부분집합이 된다. 표의 탈락 판정이 사라진다. 공통 원소가 하나라도 있는 두 집합은 전부 서로의 부분집합이 되어, $\subseteq$는 거의 아무것도 구별하지 못하게 된다.

:::{container} quotebox
**확인 3.** 이번에는 둘째 조각 "$x \in A$이면"을 지워 보자. 남는 문장은

무엇이고, 무엇이 무너지는가?
:::

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

"모든 $x$에 대해 $x \in B$이다"가 남는다. 문장에서 $A$가 사라졌다 — $B$가

세상의 모든 대상을 원소로 가져야만 참이 되는, $A$와 무관한 전혀 다른 문장이다.

심사 대상을 $A$의 원소로 한정하는 이 조각이 $\subseteq$를 **두 집합 사이의**

관계로 만든다. 정의의 조각 하나하나가 이런 붕괴를 막는 조건이다.
:::

### 3 거짓 판정, 자기 자신, 진부분집합

정의가 "모든 원소 통과"이므로, $A \nsubseteq B$임을 보이는 데 필요한 것은 **못 건너간 원소 하나의 지목**이다.

:::{container} quotebox
**확인 4.** $\{1, 4\} \nsubseteq \{1, 2, 3\}$ — 지목할 원소는 무엇인가.

그리고 거짓 판정에 $A$의 원소를 전부 검사할 필요가 있는가?
:::

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

$4$를 지목하면 끝난다 — $4 \in \{1,4\}$인데 $4 \notin \{1,2,3\}$.

전부 검사할 필요가 없다. **참 판정은 전수 검사, 거짓 판정은 하나의 지목** —

이 비대칭이 §1.4의 공허한 참과 문제 18~19(1주차의 반례)로 이어진다.
:::

표의 마지막 행에서 관찰한 것: 모든 원소가 자기 자신 안에 있으므로 $A \subseteq A$는 항상 참이다 — 자기 자신도 부분집합이다. 여기에 3주차의 수 체계 포함 관계가 이 기호로 정식화된다:

$$
\mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R}
$$

§1.1에서 적지 못했던 관계가 $\mathbb{Z} \subseteq \mathbb{Q}$ 한 조각으로 적혔다.

**진부분집합(proper subset).** $A \subseteq B$이면서 $A \neq B$일 때 $A \subsetneq B$로 쓴다 — "에이는 비의 진부분집합이다"로 읽는다. (고1 교과서의 '진부분집합'이다.)

:::{container} quotebox
**확인 5.** $\{1, 2\} \subseteq \{1, 2\}$와 $\{1, 2\} \subsetneq \{1, 2\}$를 각각 판정해 보자.
:::

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

$\subseteq$는 참($A \subseteq A$), $\subsetneq$는 거짓이다 — $\subsetneq$의

정의는 "$\subseteq$이고 $\neq$"라는 두 조각짜리인데 둘째 조각이 실패한다.

조각이 둘인 정의는 두 조각을 각각 검사한다.
:::

### 4 원소가 없으면 — $\emptyset \subseteq A$와 공허한 참

거짓 판정 조건(§1.3)을 그대로 $\emptyset$에 적용해 보자.

:::{container} quotebox
**확인 6.** 임의의 집합 $A$에 대해 $\emptyset \subseteq A$는 참인가?

거짓이려면 무엇을 지목해야 하고, 그것이 가능한가?
:::

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

참이다. 거짓이려면 $\emptyset$의 원소 중 $A$에 없는 것을 하나 지목해야 하는데,

$\emptyset$에는 지목할 원소 자체가 없다. **거짓이 될 방법이 없는 문장은 참이다.**

정의의 둘째 조각("$x \in \emptyset$이면")을 만족하는 $x$가 없으므로,

약속을 어길 사례가 존재할 수 없다.
:::

이렇게 어길 사례가 없어서 참이 되는 참을 **공허한 참**(vacuous truth)이라 한다. (8주차에서 조건문의 진리표로 이 판정이 규칙으로 정식화된다. 지금 이 판정 감각을 만들어 두면 그때 이어진다.)

따라서 **모든 집합 $A$에 대해 $\emptyset \subseteq A$이고 $A \subseteq A$이다.** 부분집합을 나열할 때 이 둘 — 공집합과 자기 자신 — 은 항상 포함된다.

### 5 ∈과 ⊆ — 판정 절차의 분리

두 기호의 판정 절차를 나란히 놓는다. 이번 주 전체가 이 표 두 줄의 훈련이다.

| **질문** | **판정 절차** |
|---|---|
| $x \in A$? | $x$가 $A$의 원소 목록에 **통째로, 한 겹에서** 등장하는가 |
| $A \subseteq B$? | $A$의 원소를 **하나씩 꺼내서** 전부 $B$에서 찾을 수 있는가 |

**예.** $A = \{1, 2\}$, $B = \{1, 2, \{1, 2\}\}$일 때 —

:::{container} quotebox
**확인 7.** $A \subseteq B$와 $A \in B$를 각각 위 절차대로 판정해 보자.
:::

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

$A \subseteq B$: $A$의 원소 $1$, $2$를 꺼내 대조 — 둘 다 $B$에 있다. 참.

$A \in B$: $B$의 한 겹 목록은 $1$, $2$, $\{1,2\}$ — 상자 $\{1,2\}$가 통째로

있다. 이것도 참이다.

즉 $\in$과 $\subseteq$는 동시에 성립할 수도, 하나만 성립할 수도 있다.

두 판정은 **독립**이고, 각각 자기 정의의 절차로 판정한다.
:::

**문법 검사가 판정보다 먼저다.** $\subseteq$의 양쪽에는 집합만 올 수 있다. "$1 \subseteq C$"처럼 왼쪽이 집합이 아니면 참도 거짓도 아닌, 문장 자체가 성립하지 않는 표기다 — 이런 답은 "문법 오류"로 적는다. (2주차 문제 6에서 "$3 \mid 12 = 4$"를 걸러낸 것과 같은 검사다. 문제 11에서 다시 만난다.)

### 6 "모든"을 증명하는 방법 — 원소 추적

정의의 첫 조각 "모든 $x$에 대해"는, 원소가 유한하면 표(§1.2)의 전수 검사로 끝난다. 그런데 원소가 무한히 많으면 — 예컨대 4의 배수 전체가 짝수 전체에 포함되는가(문제 12) — 전수 검사가 불가능하다. 1주차에서 "모든 짝수"를 문자 하나로 처리한 해법이 여기서도 그대로 쓰인다: 이름 없는 대표 $x$를 하나 잡아 그 $x$가 건너감을 보이면, 그 논증은 어느 원소에나 그대로 적용된다.

:::{admonition} 백지 암기 대상
:class: keybox

**부분집합 증명의 틀**

$A \subseteq B$의 증명은 세 걸음이다.

① "$x \in A$라 하자" — 임의의 원소를 잡는다 $\to$ ② $x \in A$라는 조건을 정의로 풀어 $x$의 정보를 얻는다 $\to$ ③ 그 정보로 $x \in B$임을 보인다.
:::

이 틀은 27주차 집합 증명의 표준 오프닝이고, §3의 빈칸 사다리에서 손에 익힌다.

:::{container} quotebox
**확인 8.** 틀의 첫 문장이 "$x \in A$라 하자"인 이유 — 이 문장은 정의 4.1의

어느 조각을 실행하는 것인가?
:::

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

"모든 $x$에 대해, $x \in A$이면"까지의 두 조각이다. 특정 원소가 아니라 문자

$x$를 잡는 것이 "모든"의 처리이고(1주차 확인 13과 같은 원리 — 문자의 일반성),

$x \in A$라는 가정을 다는 것이 "이면" 앞부분의 처리다. 남는 것은 셋째 조각

"$x \in B$이다"를 보이는 일 — 그것이 걸음 ②③이다.
:::

### 7 멱집합 — 부분집합 전부를 한 상자에

$A = \{1, 2\}$의 부분집합을 전부 나열해 보자. §1.4 끝의 관찰 — 공집합과 자기 자신은 항상 포함된다 — 이 출발점이다.

:::{container} quotebox
**확인 9.** 나열을 완성해 보자: $\emptyset$, $\underline{\quad(1)\quad}$,

$\underline{\quad(2)\quad}$, $\{1, 2\}$. 모두 몇 개인가?
:::

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

(1) $\{1\}$  (2) $\{2\}$ — 모두 4개다. 양 끝($\emptyset$과 자기 자신)은

§1.4에서 자동이고, 그 사이는 원소 하나짜리들이다.
:::

이 네 개를 원소로 모아 새 집합 하나를 만든다. 방금 나열한 것들을 상자 하나에 담았을 뿐, 새로운 계산은 없다.

### 정의 4.2 — 멱집합 (power set) [백지 암기 대상]

:::{container} quotebox
집합 $A$의 **멱집합** $\mathcal{P}(A)$는 $A$의 부분집합 **전부**를 원소로 모은 집합이다.

$$
\mathcal{P}(A) = \{X : X \subseteq A\}
$$
:::

"$\mathcal{P}(A)$"는 "에이의 멱집합" 또는 "피 에이"로 읽는다. $\mathcal{P}(A)$의 원소는 수가 아니라 **집합**($A$의 부분집합)이다 — 상자들을 담은 상자.

$$
\mathcal{P}(\{1, 2\}) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}, \qquad |\mathcal{P}(\{1,2\})| = 4 = 2^2
$$

:::{admonition} 지금은 인정하고 쓰는 사실 — 멱집합의 크기 (31주차에서 증명)
:class: quotebox

$|A| = n$이면 $|\mathcal{P}(A)| = 2^n$이다.
:::

이유의 관찰: 부분집합 하나를 만드는 일은 원소마다 "넣는다/뺀다"를 정하는 일이다 — 원소마다 2가지 선택이 겹쳐 $2 \times 2 \times \cdots = 2^n$. 고1의 "부분집합 개수 $2^n$" 공식이 이것이다. 엄밀한 증명은 31주차 귀납법에서 하고, 그때까지는 인정하고 쓴다.

:::{container} quotebox
**확인 10.** $\mathcal{P}(\{1, 2, 3\})$의 크기를 나열하기 전에 예측해 보자.

그리고 $\emptyset$과 $\{1,2,3\}$은 나열에 들어가는가?
:::

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

$2^3 = 8$개. $\emptyset$과 $\{1,2,3\}$ 둘 다 들어간다 — 각각

$\emptyset \subseteq \{1,2,3\}$(공허한 참)과 $\{1,2,3\} \subseteq \{1,2,3\}$

(자기 자신)이 근거다. 나열 자체는 예제 2.1에서 절차로 만든다.
:::

### 8 번역 규칙 — 층을 오르내리는 한 줄

멱집합의 정의 $\mathcal{P}(A) = \{X : X \subseteq A\}$를 조건제시법의 읽는 법 (3주차) 그대로 읽으면 다음 한 줄이 나온다.

:::{admonition} 백지 암기 대상
:class: keybox

**번역 규칙**

$$
X \subseteq A \iff X \in \mathcal{P}(A)
$$

"부분집합이다"($\subseteq$의 문장)와 "멱집합의 원소다"($\in$의 문장)는 같은 말이다.
:::

$\subseteq$ 판정을 한 층 위의 $\in$ 판정으로, 또 그 반대로 오갈 수 있다. 도전 문제 15~17은 전부 이 한 줄로 환원된다.

:::{container} quotebox
**확인 11.** "$\{1\} \subseteq \{1, 2\}$"를 번역 규칙으로 멱집합의 문장으로

바꿔 적어 보자. 확인 9의 나열과 일치하는가?
:::

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

$\{1\} \in \mathcal{P}(\{1, 2\})$. 확인 9에서 나열한

$\mathcal{P}(\{1,2\}) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}$의 목록에 $\{1\}$이

실제로 있다 — 두 문장이 같은 사실의 두 표기임이 확인된다.
:::

### 9 이번 주의 근거

증명(§3의 훈련, 문제 12$\cdot$16$\cdot$18)에서 쓰는 근거는 여전히 1주차 §1.6의 목록 ①~④다. 새 근거는 추가되지 않는다 — 새로 생긴 것은 근거가 아니라 **형식**(§1.6의 틀)이다. 이번 주 안에서 근거 ④(이미 증명한 명제)에 들어가는 것은 훈련 1의 추이성이다 (문제 16이 재사용한다). 반면 $|\mathcal{P}(A)| = 2^n$은 아직 증명 전이므로 근거 ④가 아니다 — "인정하고 쓰는 사실"로 구분해 두고, 31주차에서 ④로 승격된다.