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

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

이 주의 길잡이

핵심 문장: \(\subseteq\)는 “모든 원소가 건너간다”는 약속이다.

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

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

이번 주 목표#

  1. \(A \subseteq B\)의 정의를 “모든 ~이면 ~” 형태로 정확히 쓰고, 각 조각이 왜 필요한지 설명할 수 있다.

  2. \(\in\)과 \(\subseteq\)를 느낌이 아니라 절차로 판정한다 — 20문항 연속으로 틀리지 않는 것이 기준이다.

  3. \(\emptyset \subseteq A\)가 참인 이유(공허한 참)를 설명할 수 있다.

  4. 멱집합 \(\mathcal{P}(A)\)를 빠뜨림 없이 나열하고, 번역 규칙 \(X \subseteq A \iff X \in \mathcal{P}(A)\)를 쓸 수 있다.

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

  1. \(\mathbb{Q}\)의 정의를 조건제시법으로 쓰시오.

  2. \(\{x \in \mathbb{Z} : x^2 \le 6\}\)을 나열하시오.

  3. \(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\)뿐이므로 그것으로 시도해 보자.

시도 — \(\in\)으로 밀어붙이기

“\(\mathbb{Z}\)의 원소가 전부 \(\mathbb{Q}\)의 원소다”를 \(\mathbb{Z} \in \mathbb{Q}\)로 적는다.

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

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

답

거짓이다. \(\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}\)

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

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

답

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

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

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

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

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

\(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\)는 거의 아무것도 구별하지 못하게 된다.

확인 3. 이번에는 둘째 조각 “\(x \in A\)이면”을 지워 보자. 남는 문장은

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

답

“모든 \(x\)에 대해 \(x \in B\)이다”가 남는다. 문장에서 \(A\)가 사라졌다 — \(B\)가

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

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

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

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

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

확인 4. \(\{1, 4\} \nsubseteq \{1, 2, 3\}\) — 지목할 원소는 무엇인가.

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

답

\(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 교과서의 ‘진부분집합’이다.)

확인 5. \(\{1, 2\} \subseteq \{1, 2\}\)와 \(\{1, 2\} \subsetneq \{1, 2\}\)를 각각 판정해 보자.

답

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

정의는 “\(\subseteq\)이고 \(\neq\)”라는 두 조각짜리인데 둘째 조각이 실패한다.

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

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

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

확인 6. 임의의 집합 \(A\)에 대해 \(\emptyset \subseteq A\)는 참인가?

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

답

참이다. 거짓이려면 \(\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\}\}\)일 때 —

확인 7. \(A \subseteq B\)와 \(A \in B\)를 각각 위 절차대로 판정해 보자.

답

\(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\)가 건너감을 보이면, 그 논증은 어느 원소에나 그대로 적용된다.

백지 암기 대상

부분집합 증명의 틀

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

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

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

확인 8. 틀의 첫 문장이 “\(x \in A\)라 하자”인 이유 — 이 문장은 정의 4.1의

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

답

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

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

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

“\(x \in B\)이다”를 보이는 일 — 그것이 걸음 ②③이다.

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

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

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

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

답

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

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

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

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

집합 \(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 \]

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

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

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

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

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

답

\(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주차) 그대로 읽으면 다음 한 줄이 나온다.

백지 암기 대상

번역 규칙

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

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

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

확인 11. “\(\{1\} \subseteq \{1, 2\}\)”를 번역 규칙으로 멱집합의 문장으로

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

답

\(\{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주차에서 ④로 승격된다.