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

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

예제 — 곱과 첨자를 계산하기#

이번 주의 예제는 증명이 아니라 계산이다. 그래도 진행 순서는 증명과 같다 — 기호를 정의로 풀어 판정 기준을 얻고, 후보를 기준으로 심문하고, 통과한 것으로 결과를 조립한다. 예제 2.1은 한 줄씩 함께 만들고, 2.2는 설계만 함께 하고, 2.3은 설계부터 혼자 한다.

예제 2.1 — 데카르트 곱 나열#

문제. \(A = \{0, 1\}\)일 때 \(A \times A\)와 \(\mathcal{P}(A) \times A\)의 크기를 구하고 \(A \times A\)를 나열하시오.

설계 — 계산 전에 정하는 것. 주어진 것과 만들 것을 정의로 번역한다.

말

번역

주어진 것

\(A = \{0, 1\}\)

크기 2. 멱집합의 크기는 \(\underline{\quad(?)\quad}\) (4주차 공식)

만들 것 1

\(A \times A\)의 나열

첫째 성분 \(\in A\), 둘째 성분 \(\in A\)인 순서쌍 전부

만들 것 2

두 곱의 크기

크기 사실 \(\lvert X \times Y \rvert = \lvert X \rvert \cdot \lvert Y \rvert\) (§1.4)

확인 9. 번역표의 빈칸 — \(|\mathcal{P}(A)|\)는 얼마인가. 공식과 함께 적어 보자.

답

\(|\mathcal{P}(A)| = 2^{|A|} = 2^2 = 4\) (4주차 — 원소마다 넣는다/뺀다의 두 갈래).

이것으로 재료가 다 모였다. 나열부터 시작한다.

1단계 — 격자 순서로 나열한다. 빠짐과 중복을 막는 방법은 확인 3의 격자 그대로다: 첫째 성분을 고정하고 둘째 성분을 훑는다.

확인 10. 첫째 성분이 \(0\)인 순서쌍은 \((0,0), (0,1)\)이다. 첫째 성분이 \(1\)인

순서쌍을 마저 적고, \(A \times A\)를 완성해 보자.

답

\((1, 0), (1, 1)\). 따라서 \(A \times A = \{(0,0),\ (0,1),\ (1,0),\ (1,1)\}\).

\((0,1)\)과 \((1,0)\)은 서로 다른 원소다 — 상등 기준으로 첫째 성분이 \(0 \neq 1\).

집합에서는 같았을 두 대상이 순서쌍에서는 구별된다.

2단계 — 크기를 공식으로 구하고, 나열로 검산한다.

확인 11. 두 크기를 채워 보자.

\(|A \times A| = \underline{\quad(1)\quad}\),

\(|\mathcal{P}(A) \times A| = \underline{\quad(2)\quad} \cdot \underline{\quad(3)\quad} = \underline{\quad(4)\quad}\).

답

(1) \(2 \cdot 2 = 4\) — 1단계에서 나열한 원소 개수 4와 일치한다. 검산까지 겸한다.

(2) \(4\) (3) \(2\) (4) \(8\). \(\mathcal{P}(A)\)도 하나의 집합이므로 곱의 재료가

될 수 있고, 크기 사실은 재료가 멱집합이어도 그대로 작동한다.

완성본. 손으로 베껴 쓰면서 각 줄 옆의 “왜?”에 스스로 답해 본다.

증명의 한 줄

왜 이 줄을 쓰는가?

\(A \times A = \{(0,0),\ (0,1),\ (1,0),\ (1,1)\}\)

첫째 성분을 고정하고 둘째 성분을 훑는 격자 순서 — 빠짐도 중복도 없다

크기는 \(2 \cdot 2 = 4\)

크기 사실(§1.4, 12주차에서 증명). 나열한 개수 4와 일치 — 검산을 겸한다

\(\mathcal{P}(A)\)의 크기는 \(2^2 = 4\)

멱집합 크기 공식(4주차)

\(\mathcal{P}(A) \times A\)의 크기는 \(4 \cdot 2 = 8\)

\(\mathcal{P}(A)\)도 집합이므로 곱의 재료가 된다 — 같은 크기 사실의 재적용

예제 2.2 — 곱은 교환되지 않는다#

문제. \(A = \{1\}\), \(B = \{2\}\)일 때 \(A \times B\)와 \(B \times A\)를 비교하시오.

이번에는 설계만 함께 한다.

확인 12. 두 집합이 다름을 보이는 방법은 3주차 상등 기준에서 나온다 —

한쪽에는 속하고 다른 쪽에는 속하지 않는 원소를 하나 대면 된다.

\(A \times B\)와 \(B \times A\)를 각각 나열해 보자. 남는 일은 무엇인가?

답

\(A \times B = \{(1, 2)\}\), \(B \times A = \{(2, 1)\}\) — 원소가 하나씩뿐이다.

남는 일은 \((1,2)\)와 \((2,1)\)이 같은 순서쌍인지의 판정 하나다. 성분을 비교하면 끝난다.

풀이. \(A \times B = \{(1,2)\}\), \(B \times A = \{(2,1)\}\)이다. 상등 기준에 의해 \((1,2) \neq (2,1)\) — 첫째 성분이 \(1 \neq 2\). 따라서 \((1,2)\)는 \(A \times B\)에는 속하지만 \(B \times A\)에는 속하지 않고, \(A \times B \neq B \times A\)이다.

일반적으로 **\(A \times B \neq B \times A\)**이다 (같아지는 특수한 경우: \(A = B\)이거나 한쪽이 \(\emptyset\) — 이 관찰의 완성은 28주차에서 한다). 한편 확인 5에서 본 대로 크기는 언제나 같다 — 크기가 같아도 집합은 다를 수 있다는 좋은 사례다.

예제 2.3 — 무한 첨자 집합#

문제. \(i \in \mathbb{N}\)에 대해 \(A_i = [0, \tfrac{1}{i}]\) (구간)일 때 \(\bigcup_{i \in \mathbb{N}} A_i\)와 \(\bigcap_{i \in \mathbb{N}} A_i\)를 구하시오.

이번에는 설계부터 스스로 한다.

확인 13. 계산에 들어가기 전에 두 가지를 적어 보자.

① 처음 몇 개를 나열하면 \(A_1 = [0, 1]\), \(A_2 = \underline{\quad}\), \(A_3 = \underline{\quad}\) —

구간들 사이에 어떤 포함 관계가 있는가.

② 원소 판정 기준 — \(x \in \bigcup A_i\)는 “\(\underline{\quad}\)의 \(i\)에 대해 \(x \in A_i\)”,

\(x \in \bigcap A_i\)는 “\(\underline{\quad}\)의 \(i\)에 대해 \(x \in A_i\)”.

답

① \(A_2 = [0, \tfrac12]\), \(A_3 = [0, \tfrac13]\) — \([0,1] \supseteq [0,\tfrac12] \supseteq [0,\tfrac13] \supseteq \cdots\)

로 줄어드는 사슬이다.

② “적어도 하나” / “모든” (정의 6.2). 집합이 무한 개라도 이 두 기준만 있으면

계산이 시작된다.

풀이. 구간들은 \([0,1] \supseteq [0,\tfrac12] \supseteq [0,\tfrac13] \supseteq \cdots\)로 줄어든다.

합집합부터 본다. 모든 \(A_i\)가 가장 큰 \(A_1 = [0,1]\)에 포함되므로, “적어도 하나의 \(A_i\)에 속한다”를 통과하는 수는 정확히 \([0,1]\)의 원소들이다 — \([0,1]\)의 원소는 이미 \(A_1\)이 받아 주고, \([0,1]\) 밖의 수는 어느 \(A_i\)에도 없다. 따라서 \(\bigcup_{i \in \mathbb{N}} A_i = [0, 1]\).

다음으로 교집합이다. \(0\)은 모든 구간의 왼쪽 끝이므로 모든 \(A_i\)에 속한다 — 통과. 반면 \(x > 0\)이면 \(\tfrac{1}{i} < x\)가 되는 큰 \(i\)가 존재하므로(\(i > \tfrac{1}{x}\)인 자연수를 고르면 된다) 그 \(A_i\)에서 탈락한다 — “모든”의 기준을 통과하지 못한다. 음수는 \(A_1\)에서부터 탈락한다. 따라서 \(\bigcap_{i \in \mathbb{N}} A_i = \{0\}\).

무한히 많은 집합의 교집합이 한 점으로 조여드는 이 논법은 45주차 \(\varepsilon\)-N 논법의 핵심 감각이다. (이 계산을 양방향 포함 증명으로 승격하는 것은 28주차에서 한다.)

관찰 — 세 계산의 같은 뼈대#

세 예제는 소재만 다를 뿐 걸음이 같다. 대응표의 빈칸을 채워 보자.

단계

예제 2.1

예제 2.2

예제 2.3

① 기호를 판정 기준으로 푼다

첫째 성분 \(\in A\), 둘째 성분 \(\in A\)

\(\underline{\quad(1)\quad}\)

“적어도 하나” / “모든”

② 후보를 기준으로 심문한다

격자 순서로 조합 전부

\((1,2)\)와 \((2,1)\)의 성분 비교

\(\underline{\quad(2)\quad}\)

③ 통과한 것으로 결과를 조립한다

나열 + 크기 검산

\(A \times B \neq B \times A\) 선언

\(\underline{\quad(3)\quad}\)

확인 14. 대응표의 (1)(2)(3)을 채워 보자.

답

(1) 순서쌍의 상등 기준 — 성분끼리 비교한다.

(2) \(0\)은 모든 구간을 통과, \(x > 0\)은 큰 \(i\)에서 탈락, 음수는 처음부터 탈락.

(3) \(\bigcup = [0,1]\), \(\bigcap = \{0\}\)으로 조립.

세 계산 모두 정확히 이 세 걸음이다.

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

백지 암기 대상

집합 계산의 3단계

① 기호를 정의로 풀어 원소 판정 기준을 얻는다 \(\to\) ② 후보를 기준으로 심문한다

\(\to\) ③ 통과한 것으로 결과를 조립한다 (크기\(\cdot\)작은 예로 검산).

모의시험 20문항 중 계산 문제 전부가 이 세 걸음이다.

빈칸 사다리 — 지지대를 하나씩 빼며#

모의시험 전의 마지막 다리다. 훈련 1은 나열, 훈련 2는 증명, 훈련 3은 반례 — 시험에 나오는 세 종류의 일을 하나씩 예행한다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(6장)에 있다 — 다 채운 뒤에 대조한다.

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

과제. \(A = \{3, 4\}\), \(B = \{x, y\}\)일 때.

\[ A \times B = \{(3, x),\ (3, y),\ (4, \underline{\quad(1)\quad}),\ (\underline{\quad(2)\quad},\ y)\},\qquad |A \times B| = \underline{\quad(3)\quad} \]
\[ B \times A = \{(x, 3),\ (x, 4),\ \underline{\quad(4)\quad},\ \underline{\quad(5)\quad}\} \]

\((3, x) \in B \times A\)인가? \(\underline{\quad(6)\quad}\) — 첫째 성분 \(3\)이 \(\underline{\quad(7)\quad}\)의 원소가 아니기 때문이다.

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

이번에는 구조 낱말과 근거 문장도 빈칸이다.

명제. 임의의 집합 \(A, B\)에 대해 \(A \subseteq A \cup B\)이다.

증명. \(x \in \underline{\quad(1)\quad}\)라 하자. \(x \in A\)이므로 “\(x \in A\) 또는 \(x \in B\)”는 성립한다 — 근거: \(\underline{\quad(2)\quad}\). 따라서 \(\underline{\quad(3)\quad}\)의 정의에 의해 \(x \in A \cup B\)이다. \(A\)의 임의의 원소가 \(A \cup B\)의 원소이므로 \(\underline{\quad(4)\quad}\)이다. \(\blacksquare\)

(이 훈련이 문제 9, 18의 예행연습이다.)

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

과제. 다음 주장을 반박한다: “임의의 집합 \(A, B\)에 대해 \(A - (A - B) = B\)이다.”

(관찰 하나만 두고 간다 — 좌변 \(A - (A-B)\)는 \(A\)에서 무엇을 빼든 \(A\)의 부분집합일 수밖에 없다.)

반례 조립의 뼈대. 각 칸을 통째로 채운다.

  • ① 반례 후보 선택: \(\underline{\quad(1)\quad}\)

  • ② 좌변 계산: \(\underline{\quad(2)\quad}\)

  • ③ 우변과 대조하고 결론 선언: \(\underline{\quad(3)\quad}\)

(이 훈련이 문제 10, 20의 예행연습이다.)

연습문제 (20문항)#

이 20문항은 1부(3~6주차) 총정리 모의시험을 겸한다. 규칙은 세 줄이다.

  • 노트와 본문을 덮고 90분 안에 푼다. 시험 중에는 힌트 상자를 열지 않는다.

  • 다 푼 뒤 §6 해설로 채점한다. 문제 1(정의)을 하나라도 틀리면 해당 주차부터 재복습한 뒤 넘어간다.

  • 채점 후 틀린 문제는 힌트 상자와 해설의 ‘접근’까지만 읽고 한 번 더 시도한다 — 그래도 안 되면 풀이를 읽는다.

이번 주의 채점 기준

답이 아니라 근거가 점수다. 참\(\cdot\)거짓 문제는 판정과 이유가 모두 맞아야

정답으로 친다. 증명 문제는 결론이 아니라 각 줄의 근거(정의\(\cdot\)이미 증명한

명제)를 채점한다.

1. [정의 백지 테스트] 다음 정의를 수식/조건제시법으로 쓰시오. (a) \(\mathbb{Q}\) (b) \(A \subseteq B\) (c) \(\mathcal{P}(A)\) (d) \(A \cap B\) (e) \(A \times B\)

힌트

정의는 유도가 아니라 암기의 확인이다. 다섯 개 각각에 빠지면 붕괴하는 조각이

하나씩 있다 — 채점할 때 그 조각의 유무부터 본다. 막히면 해당 주차의 정의

해부 표로 돌아가 재암기한 뒤 백지에서 다시 쓴다.

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

힌트

무대가 \(\mathbb{Z}\)인 조건제시법이다. 부등식을 실수 전체에서 먼저 풀고

(인수분해), 그 결과를 정수 무대로 거른다 — 3주차의 두 단계 그대로.

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

힌트

원소 목록 세 개(\(\emptyset\), \(1\), \(\{1\}\))를 먼저 박아 둔다. \(\in\)은 목록과의

대조, \(\subseteq\)는 왼쪽 집합의 원소를 하나씩 건너보내는 판정이다(4주차).

4. \(U = \{1,\dots,10\}\), \(A = \{x \in U : 2 \mid x\}\), \(B = \{x \in U : 3 \mid x\}\)일 때 (a) \(A \cap B\) (b) \(A^c \cap B\) (c) \((A \cup B)^c\)를 구하시오.

힌트

\(A\)와 \(B\)를 나열부터 한다. 여집합은 \(U\)가 유한하므로 \(U\)에서 지워 나가면 된다.

5. \(\mathcal{P}(\{1, \{2,3\}\})\)을 나열하시오.

힌트

원소가 몇 개인지부터 센다 — \(\{2, 3\}\)은 상자째 한 개다. 원소 2개면

부분집합은 \(2^2 = 4\)개. 크기 0, 1, 2 순으로 나열하면 빠뜨리지 않는다.

6. \(A = [-1, 2)\), \(B = [0, 4]\)일 때 \(A \cap B\), \(A - B\)를 구하시오.

힌트

수직선에 겹쳐 그리고, 끝점 \(-1, 0, 2, 4\)마다 소속을 심문한다 —

준비 운동 유형 3의 처방 그대로.

7. \(A = \{1,2\}\), \(B = \{a, b\}\)일 때 \(B \times A\)를 나열하시오.

힌트

첫째 성분의 출신은 곱의 왼쪽 집합이다 — 여기서는 \(B\). 격자 순서로

나열하고 크기 사실로 개수를 검산한다.

8. [서술] \(A \subseteq B\)이고 \(B \subseteq C\)이면 \(A \subseteq C\)임을 증명하시오. (4주차 빈칸 훈련 — 이번엔 백지에서)

힌트

\(\subseteq\) 증명의 표준 오프닝은 “\(x \in A\)라 하자”이다. 그다음 가정 두 개를

관문처럼 차례로 통과시킨다.

9. [서술] \(A - B \subseteq A\)임을 증명하시오.

힌트

\(x \in A - B\)를 정의(“그리고 아니다”)로 번역하면 필요한 조각이 이미 그 안에

들어 있다. 훈련 2와 같은 걸음이다.

반례 제시의 완결 형식 — 문제 10, 20에서 쓴다

“임의의 집합 \(A, B\)에 대해 ~”가 거짓임을 보이는 데는 등식이 무너지는 구체적

집합 한 쌍이면 충분하다(1주차 문제 18의 원리 그대로). 완결 형식은 세 줄이다:

① \(A\), \(B\)를 구체적으로 적는다 ② 좌변과 우변을 각각 계산한다 ③ 두 결과가

다름을 확인하고 거짓을 선언한다.

10. 반례 제시: “임의의 집합에 대해 \((A - B) \cup B = A\)이다.”

힌트

\((A - B) \cup B\)는 \(A\)에서 \(B\)를 뺐다가 \(B\)를 통째로 되붙인 것이다 —

\(B\)가 \(A\) 바깥 원소를 가지면 결과가 \(A\)보다 커진다. 그 상황을 가장 작은

집합으로 조립한다.

11. \(\{3k - 1 : k \in \mathbb{N}\}\)의 원소를 작은 것부터 4개 나열하고, 이 집합을 조건형(\(\{x \in \mathbb{N} : \dots\}\) 꼴)으로도 쓰시오.

힌트

나열은 \(k = 1, 2, 3, 4\) 대입. 조건형은 나열된 수들의 공통 특징을 나눗셈

언어(\(\mid\), 2주차)로 옮긴다 — \(x\) 대신 \(x + 1\)을 보면 특징이 드러난다.

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

힌트

원소 목록은 집합 세 개뿐이다 — 숫자 \(1\)이 목록에 있는지부터 확인한다.

문제 3과 겉모양이 같아도 판정은 목록에 완전히 의존한다.

13. (a) \(|\mathcal{P}(A)| = 8\)이면 \(|A|\)는? (b) \(\mathcal{P}(\{1,2\}) \subseteq \mathcal{P}(\{1,2,3\})\)은 참인가? (근거 한 줄)

힌트

(a)는 \(2^n = 8\)을 푸는 문제다. (b)는 4주차 문제 16에서 증명한 정리가 그대로

적용되는 사례다 — 이미 증명한 명제는 근거 ④로 인용해 쓴다.

14. \(A = [-2, 1)\), \(B = [0, 3]\)일 때 \(A \cup B\)와 \(A \cap B\)를 구하시오.

힌트

수직선. 합집합에서는 두 구간이 틈 없이 이어지는지 먼저 확인한다.

15. \(|A| = 3\), \(|B| = 4\)일 때 (a) \(|A \times B|\) (b) \(|B \times A|\) (c) \(|\mathcal{P}(A \times B)|\) (지수 표기로).

힌트

크기 사실(§1.4, 12주차에서 증명)과 멱집합 크기 공식(4주차)의 합성이다.

(c)는 안쪽 크기부터 구해 지수에 올린다.

16. \(A = \{1, 2\}\), \(B = \{x, y\}\)일 때 \(A \times B\)를 나열하고, \((x, 1) \in A \times B\)의 참\(\cdot\)거짓을 판정하시오.

힌트

나열한 뒤, \((x, 1)\)의 첫째 성분이 어느 집합 출신이어야 하는지를 정의로 심문한다.

17. \(A_n = \{n, n+1, n+2\}\) (\(n \in \{1, 2, 3, 4, 5\}\))일 때 (a) \(\bigcup_{n=1}^{5} A_n\) (b) \(\bigcap_{n=1}^{5} A_n\) (c) \(A_1 \cap A_2\)를 구하시오.

힌트

\(A_1\)부터 \(A_5\)까지 전부 나열하고 시작한다. (b)는 “다섯 모두에 들었는가”의

심문이다 — 확인 8에서 한 그대로.

18. [서술] \(A \cap B \subseteq B\)임을 증명하시오.

힌트

5주차 예제 2.3(\(A \cap B \subseteq A\))과 완전히 같은 틀이다 — “그리고”에서

이번에는 다른 쪽 조각을 뽑는다.

19. [서술] \(A \subseteq B\)이면 \(A - B = \emptyset\)임을 설명하시오. (힌트: \(A - B\)에 원소 \(x\)가 있다고 하면 무슨 일이 생기는가?)

힌트

“공집합이다”는 “원소가 있다고 하면 모순이 생긴다”로 보이는 것이 정석이다 —

4주차 문제 18, 5주차 문제 20에서 쓴 패턴이고, 21주차 귀류법의 씨앗이다.

모순은 가정 \(A \subseteq B\)와의 충돌에서 나온다.

20. 반례 제시: “임의의 집합에 대해 \((A \cup B) - B = A\)이다.”

힌트

문제 10과 짝이다 — 이번에는 \(A\)와 \(B\)의 겹침이 문제를 일으킨다. 합쳤다가

\(B\)를 통째로 걷어내면 \(A\)의 어느 부분이 같이 걷혀 나가는가. 겹침이 있는

가장 작은 예를 조립한다.

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

권장 일정 — 1~2일차: §0~§3 학습 / 3일차: 1차 재현 / 4일차: 모의시험(§4) 90분과 채점 / 5일차: 완전 백지 재현과 오답 재시도. 재현은 두 번으로 나눈다 — 한 번에 완전 백지로 가지 않는다.

1차 시도 (3일차) — 틀 카드 허용. 정의 6.1, 6.2와 ‘집합 계산의 3단계’만 펴 놓고, 예제 2.1과 2.3을 처음부터 끝까지 적는다. 본문은 보지 않는다.

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

  • \((a, b)\)와 \(\{a, b\}\)의 차이를 상등 기준으로 설명했다.

  • \(A \times B\)의 정의를 조건제시법으로 쓰고, \(\mathbb{R}^2\)가 무엇의 약자인지 말했다.

  • 정의 6.2를 조건제시법으로 쓰고, \(\bigcup_i\)와 \(\bigcap_i\)를 “적어도 하나/모든”으로 읽었다.

  • 모의시험 8, 9, 18번(증명)을 백지에서 재현했다.

  • 모의시험에서 틀린 문제를 전부 다시 풀어 통과했다.

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

막힌 지점

처방

\((a,b)\)와 \(\{a,b\}\)의 차이가 말로 안 나온다

§1.1~1.2 — 붕괴 사례와 상등 기준 표

\(A \times B\) 나열에서 빠뜨리거나 겹친다

확인 3의 격자 — 첫째 성분 고정, 둘째 성분 훑기

\(\bigcup\), \(\bigcap\) 판정이 헷갈린다

정의 6.2의 해부 표 — “적어도 하나 / 모든”

증명(8, 9, 18)의 첫 문장이 안 나온다

훈련 2 — “\(x \in \dots\)라 하자”는 창작이 아니라 정해진 형식이다

반례(10, 20)가 조립되지 않는다

훈련 3의 뼈대 — 좌변이 될 수 있는 것부터 관찰한다

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

해설#

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

준비 운동#

  1. \(A - B = \{x : x \in A \text{ 그리고 } x \notin B\}\).

  2. \((A \cup B)^c = A^c \cap B^c\), \(\quad (A \cap B)^c = A^c \cup B^c\) — 여집합을 취하면 \(\cup\)과 \(\cap\)이 서로 뒤집힌다.

  3. \([1, 3) \cap (2, 5] = (2, 3)\). 끝점 심문: \(2\)는 \((2, 5]\)에 없으므로 제외, \(3\)은 \([1, 3)\)에 없으므로 제외.

빈칸 사다리 — 훈련 1#

(1) \(x\) — \((4, x)\)와 \((4, y)\) 둘 다 있어야 하며 나열에서 \((4, y)\)가 곧 (2)의 쌍이다 (2) \(4\) (3) \(2 \cdot 2 = 4\) (4) \((y, 3)\) (5) \((y, 4)\) (6) 아니다 (7) \(B\) — \(B \times A\)의 첫째 성분은 \(B = \{x, y\}\) 출신이어야 하는데 \(3 \notin B\)이다.

※ \(A \times B\)와 \(B \times A\)는 크기는 4로 같지만 원소는 하나도 겹치지 않는다.

빈칸 사다리 — 훈련 2#

(1) \(A\) (2) “또는”은 한쪽만 성립해도 성립한다 (5주차 합집합의 판정 기준) (3) 합집합 (4) \(A \subseteq A \cup B\)

※ 원소를 하나 잡아 정의의 관문을 통과시키는 이 걸음이 \(\subseteq\) 증명의 전부다.

빈칸 사다리 — 훈련 3#

(1) \(B\)가 \(A\) 바깥 원소를 갖는 가장 작은 쌍 — 예: \(A = \{1\}\), \(B = \{1, 2\}\). (2) \(A - B = \emptyset\)이므로 \(A - (A - B) = \{1\} - \emptyset = \{1\}\). (3) \(\{1\} \neq \{1, 2\} = B\) (\(2\)가 우변에만 속한다). 따라서 주장은 거짓이다.

※ 위 관찰의 확인: 좌변은 언제나 \(A\)의 부분집합이므로, \(B \not\subseteq A\)인 아무 쌍이나 반례가 된다. \(A = \emptyset\), \(B = \{1\}\)은 더 작은 반례다.

문제 1#

접근. 정의는 유도하는 것이 아니라 암기를 확인하는 것이다. 각 정의에는 빠지면 붕괴하는 조각이 있다 — 그 조각의 유무로 자기 채점한다.

풀이. (a) \(\mathbb{Q} = \{\frac{a}{b} : a, b \in \mathbb{Z},\ b \neq 0\}\). 조각 “\(b \neq 0\)”이 빠지면 \(\frac{a}{0}\)이 허용되어 정의가 무너진다. (b) 모든 \(x\)에 대해, \(x \in A\)이면 \(x \in B\)이다. 조각 “모든”이 빠지면 몇 개만 확인하고 통과시키는 판정이 된다. (c) \(\mathcal{P}(A) = \{X : X \subseteq A\}\). 원소가 수가 아니라 부분집합들이라는 것이 생명이다. (d) \(A \cap B = \{x : x \in A \text{ 그리고 } x \in B\}\). “그리고”가 “또는”으로 바뀌면 합집합이 된다. (e) \(A \times B = \{(a, b) : a \in A,\ b \in B\}\). 원소가 순서쌍이라는 것, 성분마다 출신이 정해져 있다는 것이 조각이다.

복기. 이 다섯 정의가 1부의 뼈대 전부다. 하나라도 형식이 무너졌으면 답을 베끼지 말고, 해당 주차(3\(\cdot\)4\(\cdot\)5\(\cdot\)6주차)의 해부 표로 돌아가 조각의 이유와 함께 재암기한다.

문제 2#

접근. 무대가 \(\mathbb{Z}\)인 조건제시법 — 실수 전체에서 부등식을 풀고, 그 결과를 정수 무대로 거른다.

풀이. \(x^2 - 2x - 3 = (x - 3)(x + 1)\)이므로 부등식은 \((x-3)(x+1) \le 0\). 곱이 0 이하이려면 두 인수의 부호가 다르거나 하나가 0이어야 한다. \(x - 3 \le 0\)이고 \(x + 1 \ge 0\)인 경우가 \(-1 \le x \le 3\)을 주고, 반대 경우 (\(x \ge 3\) 그리고 \(x \le -1\))는 불가능하다. 따라서 실수 해는 \(-1 \le x \le 3\)이고, 이 중 정수만 거르면

\[ \{-1, 0, 1, 2, 3\} \]

검산. 경계 \(x = -1\): \(1 + 2 - 3 = 0 \le 0\) ✓. 바깥 \(x = 4\): \(16 - 8 - 3 = 5 > 0\) — 탈락 ✓.

문제 3#

접근. 원소 목록(\(\emptyset\), \(1\), \(\{1\}\))을 박아 두고, \(\in\)은 목록 대조, \(\subseteq\)는 원소 건너보내기로 기계처럼 판정한다.

풀이. (a) 참 — \(\emptyset\)이 원소 목록에 있다 (\(\in\) 판정은 목록 대조). (b) 참 — 공허한 참: \(\emptyset\)에는 원소가 없으므로 “모든 원소가 \(A\)에 있다”가 자동으로 성립한다 (4주차). (c) 참 — \(\{1\}\)이 원소 목록에 있다. (d) 참 — \(\{1\}\)의 원소는 \(1\) 하나이고 \(1 \in A\)이므로 건너보내기가 성공한다. (e) 참 — \(\{\{1\}\}\)의 원소는 \(\{1\}\) 하나이고 \(\{1\} \in A\)이다.

※ (a)와 (b)는 답이 같아도 이유가 완전히 다르다 — 하나는 목록 대조, 하나는 공허한 참. 이유까지 맞아야 정답이다.

문제 4#

접근. \(A\), \(B\)를 먼저 나열해 놓고 연산한다. 여집합은 \(U\)가 유한하므로 \(U\)에서 지워 나간다.

풀이. \(A = \{2, 4, 6, 8, 10\}\) (\(U\)의 2의 배수), \(B = \{3, 6, 9\}\) (\(U\)의 3의 배수). (a) 두 목록에 모두 있는 수는 \(6\)뿐 — \(A \cap B = \{6\}\). (b) \(A^c = \{1, 3, 5, 7, 9\}\)이고, 이 중 \(B\)에도 있는 수는 — \(A^c \cap B = \{3, 9\}\). (\(B\)에서 짝수 \(6\)을 지운 것과 같다.) (c) \(A \cup B = \{2, 3, 4, 6, 8, 9, 10\}\) — \(U\)에서 지우면 \((A \cup B)^c = \{1, 5, 7\}\).

검산. \(|A \cup B| = 5 + 3 - 1 = 7\)이므로 여집합의 크기는 \(10 - 7 = 3\)개 ✓.

문제 5#

접근. 원소가 몇 개인지부터 센다: \(1\)과 \(\{2, 3\}\) — 2개. 부분집합은 \(2^2 = 4\)개이고, 크기순으로 나열하면 빠뜨리지 않는다. \(\{2, 3\}\)은 끝까지 통째로 한 덩어리로 유지한다.

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

\[ \mathcal{P}(\{1, \{2,3\}\}) = \{\emptyset,\ \{1\},\ \{\{2,3\}\},\ \{1, \{2,3\}\}\} \]

검산. 개수 \(4 = 2^2\) ✓. 답에 \(\{2\}\)나 \(\{3\}\)이 등장하면 상자를 뜯은 것 — 오답이다. \(\{2,3\}\)을 홑겹으로 적은 것도 오답이다 — 원소로 넣을 때는 \(\{\{2,3\}\}\)처럼 두 겹이 된다.

문제 6#

접근. 수직선에 겹쳐 그리고 끝점(\(-1, 0, 2, 4\))마다 포함 여부를 심문한다.

풀이. \(A \cap B\): 겹치는 부분은 \(0\)부터 \(2\)까지. \(0\)은 \(A = [-1, 2)\)와 \(B = [0, 4]\) 모두에 속하므로 포함, \(2\)는 \(A\)가 반열림이라 \(2 \notin A\)이므로 제외. 따라서 \(A \cap B = [0, 2)\). \(A - B\): \(A\)의 원소 중 \(B = [0, 4]\)에 속하는 것(\(0 \le x\))을 지우면 \(x < 0\)인 부분만 남는다. \(-1 \in A\)이고 \(-1 \notin B\)이므로 포함, \(0\)은 \(B\)에 속하므로 제외. 따라서 \(A - B = [-1, 0)\).

문제 7#

접근. 첫째 성분의 출신은 곱의 왼쪽 집합 — 여기서는 \(B\)다. 격자 순서로 나열하고 크기로 검산한다.

풀이. 첫째 성분 \(a\): \((a, 1), (a, 2)\). 첫째 성분 \(b\): \((b, 1), (b, 2)\).

\[ B \times A = \{(a, 1),\ (a, 2),\ (b, 1),\ (b, 2)\} \]

검산. 크기 \(2 \cdot 2 = 4\) ✓. \(\{(1, a), \dots\}\)처럼 적었다면 그것은 \(A \times B\)다 — 곱의 순서가 성분의 순서다.

문제 8#

접근. \(\subseteq\) 증명의 표준 오프닝 “\(x \in A\)라 하자”로 시작해, 가정 두 개를 관문처럼 차례로 통과시킨다.

풀이. \(A \subseteq B\)이고 \(B \subseteq C\)라 가정하자. \(x \in A\)라 하자. \(A \subseteq B\)이므로 \(x \in B\)이다. 다시 \(B \subseteq C\)이므로 \(x \in C\)이다. 따라서 \(A\)의 임의의 원소가 \(C\)의 원소이므로 \(A \subseteq C\)이다. \(\blacksquare\)

복기. 가정이 두 개면 통과도 두 번 — 포함의 사슬 통과다. 포함의 이 추이성은 2주차 \(\mid\)의 추이성과 같은 뼈대이고, 25주차 이후 집합 증명의 기본 부품이 된다.

문제 9#

접근. \(x \in A - B\)를 정의(“그리고 아니다”)로 번역하면 필요한 조각 (\(x \in A\))이 이미 그 안에 들어 있다 — 뽑아 쓰면 끝난다.

풀이. \(x \in A - B\)라 하자. 차집합의 정의에 의해 \(x \in A\)이고 \(x \notin B\)이다. 특히 \(x \in A\)이다. 따라서 \(A - B\)의 임의의 원소가 \(A\)의 원소이므로 \(A - B \subseteq A\)이다. \(\blacksquare\)

복기. “그리고”로 묶인 정보에서 필요한 쪽만 뽑는 낱말이 “특히”다. 문제 18에서 같은 동작으로 다른 쪽을 뽑는다.

문제 10#

접근. \((A - B) \cup B\)는 “\(A\)에서 \(B\)를 뺐다가 \(B\)를 통째로 다시 붙인” 것 — \(B\)가 \(A\) 바깥 원소를 갖고 있으면 결과가 \(A\)보다 커진다. 그 상황을 가장 작은 집합으로 조립한다 (훈련 3의 관찰과 같은 종류).

풀이. 반례: \(A = \{1\}\), \(B = \{2\}\). 좌변: \(A - B = \{1\}\) (\(1 \notin B\)이므로 그대로 남는다)이고 \((A - B) \cup B = \{1\} \cup \{2\} = \{1, 2\}\). 우변: \(A = \{1\}\). \(2\)는 좌변에만 속하므로 \(\{1, 2\} \neq \{1\}\) — 따라서 명제는 거짓이다.

복기. \(B \subseteq A\)일 때만 성립하는 명제다. “임의의”가 붙는 순간 반례 하나로 무너진다 — 반례의 완결 형식(후보 제시 \(\to\) 양변 계산 \(\to\) 다름 확인)을 그대로 밟았는지 검사한다.

문제 11#

접근. 나열은 대입이다. 조건형 변환은 나열된 수들의 공통 특징을 나눗셈 언어(\(\mid\), 2주차)로 옮긴다 — \(x = 3k - 1\)을 \(x\)에 대한 판정 조건으로 뒤집는다.

풀이. 대입: \(k = 1\)이면 \(2\), \(k = 2\)이면 \(5\), \(k = 3\)이면 \(8\), \(k = 4\)이면 \(11\). 나열: \(2, 5, 8, 11\). 조건형 유도: \(x = 3k - 1\)인 자연수 \(k\)가 존재하는 것은 \(x + 1 = 3k\)인 \(k\)가 존재하는 것과 같은 말이고, 이는 곧 \(3 \mid (x + 1)\)이다. 따라서

\[ \{x \in \mathbb{N} : 3 \mid (x + 1)\} \]

검산. \(x = 8\): \(3 \mid 9\) ✓. \(x = 7\): \(8\)은 3의 배수가 아니므로 탈락 — 나열에 \(7\)이 없는 것과 일치 ✓.

문제 12#

접근. 원소 목록은 집합 세 개(\(\emptyset\), \(\{1\}\), \(\{1,2\}\))뿐이다. (b)가 함정 — \(\subseteq\) 판정이므로 \(\{1\}\)의 원소인 숫자 1이 \(C\)에 있어야 하는데, 목록에 숫자 \(1\)은 없다.

풀이. (a) 참 — \(\{1\}\)이 원소 목록에 있다. (b) 거짓 — \(\{1\}\)의 원소 \(1\)이 \(C\)의 원소여야 하는데 \(1 \notin C\) (\(C\)의 원소는 집합 세 개뿐이다). (c) 참 — \(\{\{1\}\}\)의 원소 \(\{1\}\)이 목록에 있다. (d) 참 — 공허한 참 (공집합은 모든 집합의 부분집합). (e) 거짓 — \(\{1, 2\}\)의 원소 \(1, 2\)가 \(C\)의 목록에 없다. (\(\{1,2\} \in C\)는 참이지만 물음은 \(\subseteq\)다.)

※ 문제 3의 (c)(d)와 이 문제의 (a)(b)를 비교한다 — 문제 3의 \(A\)에는 숫자 \(1\)이 있어서 (d)가 참이었지만, 여기에는 없어서 (b)가 거짓으로 뒤집힌다. 판정은 문맥(원소 목록)에 완전히 의존한다.

문제 13#

접근. (a)는 \(2^n = 8\)을 푸는 문제. (b)는 4주차 문제 16의 정리 (”\(A \subseteq B\)이면 \(\mathcal{P}(A) \subseteq \mathcal{P}(B)\)”)의 사례임을 알아채는 문제다 — 이미 증명한 명제는 근거 ④로 인용해 쓴다.

풀이. (a) \(|\mathcal{P}(A)| = 2^{|A|}\)이므로 \(2^{|A|} = 8 = 2^3\), 따라서 \(|A| = 3\). (b) 참. \(\{1, 2\} \subseteq \{1, 2, 3\}\)이므로 4주차 문제 16의 정리에 의해 \(\mathcal{P}(\{1,2\}) \subseteq \mathcal{P}(\{1,2,3\})\)이다. (직접 확인도 가능하다: \(\{1,2\}\)의 부분집합 \(\emptyset, \{1\}, \{2\}, \{1,2\}\) 네 개는 전부 \(\{1,2,3\}\)의 부분집합이다.)

복기. (b)에서 네 개를 일일이 확인하는 대신 정리 한 줄을 인용한 것 — 증명된 명제를 부품으로 재사용하는 근거 ④의 전형이다.

문제 14#

접근. 수직선에 겹쳐 그린다. 합집합에서는 두 구간 사이에 틈이 없는지부터 확인한다.

풀이. \(A = [-2, 1)\)과 \(B = [0, 3]\)은 \([0, 1)\)에서 겹치므로 틈 없이 이어진다. \(A \cup B\): 왼쪽 끝 \(-2\)는 \(A\)에 속하므로 닫힘, 오른쪽 끝 \(3\)은 \(B\)에 속하므로 닫힘 — \(A \cup B = [-2, 3]\). \(A \cap B\): 겹치는 부분은 \(0\)부터 \(1\)까지. \(0\)은 양쪽 모두에 속하므로 포함, \(1\)은 \(A = [-2, 1)\)에 없으므로 제외 — \(A \cap B = [0, 1)\).

검산. \(0.5\)는 양쪽에 속하므로 교집합에 있어야 한다 — \(0.5 \in [0, 1)\) ✓.

문제 15#

접근. 크기 사실 \(|A \times B| = |A| \cdot |B|\) (§1.4, 12주차에서 증명)와 멱집합 크기 공식 \(|\mathcal{P}(S)| = 2^{|S|}\) (4주차)의 합성이다.

풀이. (a) \(|A \times B| = 3 \cdot 4 = 12\). (b) \(|B \times A| = 4 \cdot 3 = 12\) — 곱의 순서가 바뀌어도 크기는 같다. 집합 자체는 다른데(예제 2.2) 크기만 같은 좋은 예다. (c) 안쪽부터: \(|A \times B| = 12\)이므로 \(|\mathcal{P}(A \times B)| = 2^{12}\) (\(= 4096\)).

문제 16#

접근. 나열한 뒤, \((x, 1)\)의 첫째 성분이 어느 집합 출신이어야 하는지 정의로 심문한다.

풀이. 격자 순서로 \(A \times B = \{(1, x),\ (1, y),\ (2, x),\ (2, y)\}\). \((x, 1)\)이 \(A \times B\)의 원소이려면 첫째 성분 \(x\)가 \(A = \{1, 2\}\)의 원소여야 하는데 \(x \notin A\)이다. 따라서 거짓. (같은 심문을 방향을 바꿔 하면 \((x, 1) \in B \times A\)는 참이다 — \(x \in B\) 그리고 \(1 \in A\).)

문제 17#

접근. \(A_1, \dots, A_5\)를 다 적어 놓고 (a) 전부 합치고 (b) 다섯 집합 모두에 든 수를 심문하고 (c) 둘만 겹친다.

풀이. \(A_1 = \{1,2,3\}\), \(A_2 = \{2,3,4\}\), \(A_3 = \{3,4,5\}\), \(A_4 = \{4,5,6\}\), \(A_5 = \{5,6,7\}\). (a) 등장한 수 전부: \(\bigcup_{n=1}^{5} A_n = \{1, 2, 3, 4, 5, 6, 7\}\). (b) 다섯 모두에 들려면 특히 \(A_1\)과 \(A_5\) 둘 다에 들어야 하는데 \(A_1 \cap A_5 = \{1,2,3\} \cap \{5,6,7\} = \emptyset\) — 그런 수는 없다. 따라서 \(\bigcap_{n=1}^{5} A_n = \emptyset\). (c) \(A_1 \cap A_2 = \{2, 3\}\).

복기. (b)에서 다섯을 다 심문하는 대신 겹칠 수 없는 두 집합(\(A_1\), \(A_5\))만 대조해 끝냈다 — “모든”의 요구는 한 곳에서만 무너져도 전체가 무너진다.

문제 18#

접근. 5주차 예제 2.3(\(A \cap B \subseteq A\))과 완전히 같은 틀 — “그리고”에서 이번에는 다른 쪽 조각을 뽑는다.

풀이. \(x \in A \cap B\)라 하자. 교집합의 정의에 의해 \(x \in A\)이고 \(x \in B\)이다. 특히 \(x \in B\)이다. 따라서 \(A \cap B\)의 임의의 원소가 \(B\)의 원소이므로 \(A \cap B \subseteq B\)이다. \(\blacksquare\)

복기. 문제 9와 이 문제는 같은 동작(“그리고”에서 한쪽 뽑기)의 두 방향이다. 정의를 풀면 결론이 이미 조각으로 들어 있는 유형 — \(\subseteq\) 증명의 가장 짧은 형태다.

문제 19#

접근. “공집합이다”는 “원소가 있다고 하면 모순이 생긴다”로 보이는 것이 정석이다 (4주차 문제 18, 5주차 문제 20과 같은 패턴). 모순은 가정 \(A \subseteq B\)와의 충돌에서 나온다.

풀이. \(A \subseteq B\)라 가정하자. 만약 \(A - B\)에 원소가 있다면, 그 원소를 \(x\)라 하자. 차집합의 정의에 의해 \(x \in A\)이고 \(x \notin B\)이다. 그런데 \(x \in A\)와 가정 \(A \subseteq B\)에 의해 \(x \in B\)이다 — \(x \notin B\)와 모순이다. 따라서 \(A - B\)에는 원소가 있을 수 없고, \(A - B = \emptyset\)이다. \(\blacksquare\)

복기. “만약 ~라면 모순이므로 ~가 아니다” — 이 어법이 21주차 귀류법의 씨앗이다. 여기서는 “원소가 없다”라는 부정형 결론을 직접 만들 수 없기 때문에, 있다고 두고 무너지는 것을 보였다.

문제 20#

접근. \((A \cup B) - B\)는 “합쳤다가 \(B\)를 통째로 걷어낸” 것 — \(A\)와 \(B\)가 겹치면 \(A\)의 일부(겹침 부분)도 같이 걷혀 나간다. 겹침이 있는 가장 작은 예를 조립한다.

풀이. 반례: \(A = \{1, 2\}\), \(B = \{2\}\). 좌변: \(A \cup B = \{1, 2\}\)이고 \((A \cup B) - B = \{1, 2\} - \{2\} = \{1\}\). 우변: \(A = \{1, 2\}\). \(2\)는 우변에만 속하므로 \(\{1\} \neq \{1, 2\}\) — 따라서 명제는 거짓이다.

복기. \(A\)와 \(B\)가 서로소일 때만 성립하는 명제다. 문제 10과 짝을 이루는 반례다 — 문제 10은 바깥 원소가 “더 붙어 옴”, 이번에는 겹침 원소가 “덜 돌아옴”. 집합 등식을 의심할 때는 이 두 방향(커지는가, 작아지는가)을 각각 실험한다.

채점 가이드#

  • 문제 1(정의) 만점 + 8, 9, 18, 19번에 논리 비약 없음 \(\to\) 통과. 7주차로 간다.

  • 3, 5, 12번에서 틀림 \(\to\) 4주차(\(\in\)/\(\subseteq\)/멱집합) 재복습.

  • 6, 14번에서 끝점 처리 틀림 \(\to\) 5주차 구간 연산 재복습.

  • 7, 15, 16, 17번에서 틀림 \(\to\) 이번 주 §1 재복습 (곱의 순서\(\cdot\)크기 사실\(\cdot\)첨자 판정).

  • 8, 9, 18번에서 “\(x \in \dots\)라 하자”로 시작하지 못함 \(\to\) 훈련 2와 5주차 예제 2.3 재필사.

다음 주 예고: 2부 ‘논리’가 시작된다. 지금까지 증명 속에서 감각으로 쓰던 “그리고/또는/이면”을 진리표라는 정밀 기계로 분해한다. 거기서 만드는 도구 (부정\(\cdot\)드모르간\(\cdot\)대우)가 19주차 이후의 증명 기법 전부를 떠받친다.