PART I — 증명
증명을 한참 다뤘으니 이제 잠깐 다른 이야기를 해볼까 합니다. 수학자에게도 자료구조가 필요합니다. 프로그래머가 배열, 리스트, 해시맵 없이 코드를 짤 수 없듯, 수학자도 무언가를 담아두고 꺼내고 묶을 그릇이 있어야 합니다. 이 챕터에서는 수학의 가장 기본적인 자료구조 셋, 즉 집합, 수열, 함수를 차례로 만나고, 거기에 이항관계와 유한 기수까지 얹어보겠습니다. 컴퓨터과학에서 배운 set, list, map의 뿌리가 모두 여기에 있습니다.
가장 단순한 그릇부터 시작합시다. 집합(set)은 그저 "물건들의 모임"입니다. 그런데 보통의 모임과 다른 점이 두 가지 있어요. 첫째, 순서가 없습니다. 둘째, 중복이 없습니다. 그래서 \(\{1, 2, 3\}\)과 \(\{3, 1, 2\}\), 그리고 \(\{1, 1, 2, 2, 3\}\)은 모두 같은 집합입니다. 파이썬의 set을 떠올리면 거의 그대로예요.
정의 4.1.1 (집합과 원소)
집합 \(A\)에 어떤 대상 \(x\)가 들어 있으면 \(x\)는 \(A\)의 원소(element)라 하고 \(x \in A\)라 씁니다. 들어 있지 않으면 \(x \notin A\)라 씁니다. 두 집합 \(A, B\)에 대해 \(A = B\)인 것은 정확히 같은 원소를 가질 때, 즉 \(\forall x\,(x \in A \iff x \in B)\)일 때입니다. 이것을 외연성 공리(axiom of extensionality)라 부릅니다.
집합을 적는 방법은 두 가지입니다. 원소를 그대로 나열하는 외연적 표기와, 조건으로 거르는 내포적 표기입니다. 예를 들어 \(\{2, 4, 6, 8\}\)은 외연적이고, \(\{n \in \mathbb{N} \mid n \text{이 짝수이고 } n \le 8\}\)은 내포적입니다. 후자는 "어떤 우주집합 \(\mathbb{N}\)에서 조건에 맞는 것만 골라낸다"는 뜻이에요.
특별한 집합 몇 개는 기호가 정해져 있습니다. \(\mathbb{N}\)은 자연수, \(\mathbb{Z}\)는 정수, \(\mathbb{Q}\)는 유리수, \(\mathbb{R}\)은 실수, \(\mathbb{C}\)는 복소수입니다. 그리고 원소가 하나도 없는 집합을 공집합(empty set)이라 하고 \(\emptyset\) 또는 \(\{\}\)로 씁니다. \(\emptyset\)은 단 하나뿐이라는 점이 중요합니다 (외연성 공리로부터 따라 나옵니다).
정의 4.1.2 (부분집합)
집합 \(A\)의 모든 원소가 \(B\)에도 들어 있으면 \(A\)는 \(B\)의 부분집합(subset)이라 하고 \(A \subseteq B\)라 씁니다. 즉 \(A \subseteq B \iff \forall x\,(x \in A \implies x \in B)\). 만약 \(A \subseteq B\)이면서 \(A \neq B\)라면 진부분집합(proper subset)이라 하고 \(A \subsetneq B\)라 씁니다.
두 집합이 서로 부분집합이면 같습니다. 이 사실은 의외로 자주 쓰여요. 어떤 집합이 다른 집합과 같다는 것을 직접 보이기 어려울 때, 양방향 포함을 따로따로 보이는 전략이 자연스럽게 나옵니다.
예제 4.1.3
\(A = \{1, 2\}\)의 모든 부분집합을 적어봅시다. \(\emptyset\), \(\{1\}\), \(\{2\}\), \(\{1, 2\}\) — 이렇게 네 개입니다. 일반적으로 원소가 \(n\)개인 집합은 부분집합이 \(2^n\)개예요. 각 원소를 "넣느냐 빼느냐" 두 가지로 정할 수 있고, 선택이 독립이니 \(2 \times 2 \times \cdots \times 2 = 2^n\)이 됩니다. 이 \(2^n\)이라는 숫자가 다음 정의와 바로 연결됩니다.
정의 4.1.4 (멱집합)
집합 \(A\)의 멱집합(power set)은 \(A\)의 모든 부분집합을 모은 집합입니다. \(\mathcal{P}(A) = \{S \mid S \subseteq A\}\). 예를 들어 \(\mathcal{P}(\{1, 2\}) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}\)이고, \(|\mathcal{P}(A)| = 2^{|A|}\)입니다.
이제 집합끼리 섞고 빼는 연산을 봅시다. 두 집합 \(A, B\)에 대해
이 연산들은 명제논리의 ∨, ∧, ¬와 정확히 짝을 이룹니다. 그래서 명제논리의 항등식이 집합 항등식으로 그대로 옮겨가요. 예컨대 드모르간 법칙 \(\overline{A \cup B} = \overline{A} \cap \overline{B}\)는 \(\neg(p \lor q) \equiv \neg p \land \neg q\)의 집합 버전입니다.
예제 4.1.5
\(A = \{1, 2, 3, 4\}\), \(B = \{3, 4, 5, 6\}\), 우주 \(U = \{1, 2, \ldots, 8\}\)이라 합시다. 그러면 \(A \cup B = \{1, 2, 3, 4, 5, 6\}\), \(A \cap B = \{3, 4\}\), \(A \setminus B = \{1, 2\}\), \(\overline{A} = \{5, 6, 7, 8\}\). 직접 손으로 그려 보면 벤다이어그램이 보일 거예요.
노트: 러셀의 역설
"임의의 조건으로 집합을 만들 수 있다"고 무심코 가정하면 큰일 납니다. 다음을 보세요. \(R = \{x \mid x \notin x\}\) — 자기 자신을 원소로 가지지 않는 모든 것의 모임. 그러면 \(R \in R\)일까요? 만약 \(R \in R\)이라면 정의에 의해 \(R \notin R\). 반대로 \(R \notin R\)이라면 정의에 의해 \(R \in R\). 어느 쪽이든 모순이죠.
버틸런드 러셀이 1901년에 발견한 이 모순을 동네 이야기로 풀면 이렇습니다. "이 마을의 이발사는 스스로 면도하지 않는 사람들 모두를 면도하고, 오직 그들만 면도한다." 그럼 이발사는 스스로 면도하나요? 한다고 하면 정의에 어긋나고, 안 한다고 해도 어긋납니다. 답은 "그런 이발사는 존재하지 않는다"이고, 마찬가지로 "그런 집합 \(R\)은 존재하지 않는다"가 됩니다. 현대 수학은 이 문제를 ZFC 공리로 우회하지만, 우리는 일단 "조심히 만들면 됩니다" 정도로 넘어갑시다.
집합은 순서가 없습니다. 하지만 살다 보면 "1번, 2번, 3번"처럼 자리가 정해져 있는 모임이 필요할 때가 있어요. 사람 줄, 시간순 이벤트, 좌표 \((x, y)\) 같은 것들이죠. 그래서 수학자들은 수열(sequence) 또는 튜플(tuple)이라는 두 번째 자료구조를 만들었습니다.
정의 4.2.1 (수열)
수열은 원소를 순서 있게 늘어놓은 것입니다. 길이가 \(n\)인 수열은 \((a_1, a_2, \ldots, a_n)\)으로 적습니다. 두 수열이 같다는 것은 길이가 같고 같은 자리에 같은 원소가 있다는 뜻입니다. 즉 \((a_1, \ldots, a_n) = (b_1, \ldots, b_m)\) iff \(n = m\) 이고 모든 \(i\)에 대해 \(a_i = b_i\). 길이가 2인 수열은 특별히 순서쌍(ordered pair)이라 부릅니다.
집합과 수열의 차이를 분명히 해두겠습니다. \(\{1, 2\} = \{2, 1\}\)이지만 \((1, 2) \neq (2, 1)\)이에요. 또 \(\{1, 1\} = \{1\}\)이지만 \((1, 1) \neq (1)\)입니다. 한국어 강의에서 "튜플"이라는 말을 영어 그대로 쓸 때가 많은데, 본질은 순서 있는 모음입니다.
정의 4.2.2 (카르테시안 곱)
두 집합 \(A, B\)의 카르테시안 곱(Cartesian product)은 \(A\)에서 하나, \(B\)에서 하나 골라 만든 모든 순서쌍의 집합입니다. \[A \times B = \{(a, b) \mid a \in A,\ b \in B\}.\] 일반화해서 \(A_1 \times A_2 \times \cdots \times A_n\)은 \((a_1, \ldots, a_n)\)들의 집합으로, 각 \(a_i \in A_i\)를 만족합니다. \(A^n\)은 \(A \times A \times \cdots \times A\) (n번)을 가리킵니다.
예제 4.2.3
\(A = \{a, b\}\), \(B = \{1, 2, 3\}\)이면 \[A \times B = \{(a,1), (a,2), (a,3), (b,1), (b,2), (b,3)\}.\] 원소가 \(2 \times 3 = 6\)개죠. 일반적으로 유한집합이면 \(|A \times B| = |A| \cdot |B|\)입니다. 이게 곱셈을 "곱"이라 부르는 한 가지 이유고, 또 \(\mathbb{R}^2\)이 평면이 되는 이유이기도 합니다.
노트
프로그래머에게 \(A \times B\)는 "타입 \(A\)와 타입 \(B\)의 곱 타입"입니다. 하스켈의 (A, B), 러스트의 튜플, 파이썬의 tuple[A, B]가 모두 카르테시안 곱이에요. 마찬가지로 \(A^n\)은 길이 \(n\)인 \(A\)-원소 리스트로 보면 됩니다.
이제 본격적인 무대입니다. 함수(function)는 "입력을 받으면 출력을 돌려주는 규칙"입니다. 고등학교에서 \(f(x) = x^2\) 같은 식으로 만났겠지만, 수학에서 함수를 정의할 때는 식이 있어야 한다고 요구하지 않습니다. 식 없이 그냥 "어떤 입력에 어떤 출력이 대응되는가"만 명시하면 충분합니다.
정의 4.3.1 (함수)
함수 \(f: A \to B\)는 \(A\)의 각 원소 \(a\)에 \(B\)의 원소 \(f(a)\)를 정확히 하나씩 대응시키는 규칙입니다. 이때 \(A\)를 \(f\)의 정의역(domain), \(B\)를 공역(codomain), \(\{f(a) \mid a \in A\}\)을 치역(image, range)이라 합니다.
여기서 두 가지를 강조하고 싶어요. 첫째, "정확히 하나씩"이 핵심입니다. 입력 하나에 출력이 두 개 나오면 함수가 아닙니다. 둘째, 공역과 치역은 다릅니다. 공역은 "출력이 살 수 있는 집"이고, 치역은 "실제로 살고 있는 집"입니다. 한국어 학생들이 자주 헷갈리는 지점이에요.
예제 4.3.2
\(f: \mathbb{R} \to \mathbb{R}\), \(f(x) = x^2\)을 봅시다. 정의역은 \(\mathbb{R}\), 공역도 \(\mathbb{R}\)이지만 치역은 \([0, \infty)\)입니다. 음수는 결코 출력으로 안 나오죠. 그래서 공역과 치역이 일치하지 않아요.
함수의 성격은 입출력의 짝짓기 패턴에 따라 세 가지로 분류됩니다.
정의 4.3.3 (단사, 전사, 전단사)
\(f: A \to B\)가
그림으로 보면 직관이 더 빠릅니다.
단사 (injective) 전사 (surjective) 전단사 (bijective)
------------------ ------------------- -------------------
A B A B A B
1 ──────► a 1 ──────► a 1 ──────► a
2 ──────► b 2 ─┐ 2 ──────► b
3 ──────► c 3 ─┴────► b 3 ──────► c
d (남음) c
서로 다른 → 서로 다른 모든 b가 화살을 받음 둘 다 만족
단사는 "겹치지 않는다", 전사는 "남는 게 없다", 전단사는 "둘 다"라고 외워두면 좋아요. 영어로는 "into" vs "onto"라는 표현도 자주 등장하는데, "into"는 그냥 함수, "onto"는 전사를 가리킵니다.
예제 4.3.4
\(f: \mathbb{Z} \to \mathbb{Z}\), \(f(n) = n + 1\)는 전단사입니다. 다른 입력은 다른 출력을 주니 단사이고, 임의의 \(m \in \mathbb{Z}\)에 대해 \(f(m - 1) = m\)이니 전사. 반면 \(g: \mathbb{Z} \to \mathbb{Z}\), \(g(n) = n^2\)는 단사도 전사도 아니에요. \(g(1) = g(-1) = 1\)이니 단사 X, 출력 -1이 안 나오니 전사 X.
노트
함수가 전단사면 역함수(inverse)가 잘 정의됩니다. \(f^{-1}: B \to A\)가 \(f^{-1}(b) = a \iff f(a) = b\)로 자연스럽게 만들어져요. 단사가 아니면 한 출력에 입력이 여러 개일 수 있어 역이 함수가 안 되고, 전사가 아니면 역의 정의역 일부에서 값을 못 정합니다. 그래서 "역함수의 존재 = 전단사" 입니다.
함수보다 더 일반적인 개념이 이항관계입니다. 직관적으로 "이 두 원소는 어떤 식으로든 관련이 있다"를 가리키는 표시예요. 예를 들어 정수에서 \(\le\), 사람들 사이에서 "친구다", 도시들 사이에서 "직항이 있다" 같은 것들이 모두 이항관계입니다.
정의 4.4.1 (이항관계)
집합 \(A, B\) 사이의 이항관계(binary relation)는 카르테시안 곱 \(A \times B\)의 부분집합입니다. 즉 \(R \subseteq A \times B\). \((a, b) \in R\)일 때 흔히 \(a\,R\,b\)라 적습니다. \(A = B\)인 경우 "\(A\) 위의 관계"라 부릅니다.
처음 보면 "관계가 부분집합이라고?" 하고 갸웃할 수 있어요. 이렇게 생각해 보세요. 어떤 두 원소가 관계가 있느냐 없느냐는 결국 yes/no 질문이고, 관련 있는 쌍들만 모아두면 그게 곧 \(A \times B\)의 부분집합이 됩니다. 모든 쌍에 대해 한 번씩 답을 적어둔 표가 바로 \(R\)이에요.
예제 4.4.2
\(A = \{1, 2, 3\}\) 위에서 "나누어 떨어진다" 관계를 \(R\)이라 합시다. 즉 \(a\,R\,b \iff a \mid b\). 그러면 \[R = \{(1,1), (1,2), (1,3), (2,2), (3,3)\}.\] 1은 모든 수를 나누고, 2는 자기만 나누고 (3을 못 나눔), 3도 자기만 나눕니다.
정리 4.4.3 (함수는 특수한 관계다)
모든 함수 \(f: A \to B\)는 그 그래프 \(\Gamma_f = \{(a, f(a)) \mid a \in A\} \subseteq A \times B\)로 표현되는 관계입니다. 거꾸로, 관계 \(R \subseteq A \times B\)가 다음 두 조건을 만족하면 함수입니다.
다시 말해 함수는 "왼쪽 입력마다 짝이 정확히 하나"인 관계입니다. 관계 일반은 짝이 0개여도, 여러 개여도 괜찮아요. 그래서 함수는 관계의 "엄격한 부분집합"인 거죠.
정의 4.4.4 (관계의 합성과 역)
관계 \(R \subseteq A \times B\)와 \(S \subseteq B \times C\)에 대해 합성 \(S \circ R \subseteq A \times C\)는 \[S \circ R = \{(a, c) \mid \exists b \in B,\ (a, b) \in R \text{ 그리고 } (b, c) \in S\}.\] 또 관계 \(R \subseteq A \times B\)의 역(inverse)은 \(R^{-1} = \{(b, a) \mid (a, b) \in R\} \subseteq B \times A\).
합성은 화살표를 이어 붙이는 것입니다. \(a\)에서 \(R\) 화살을 따라가서 \(b\)에 도착하고, 거기서 \(S\) 화살을 따라가서 \(c\)에 도착할 수 있다면 \((a, c)\)는 합성 관계에 들어갑니다. 함수의 합성 \((g \circ f)(x) = g(f(x))\)이 바로 이 일반 정의의 특수한 경우예요.
역도 마찬가지입니다. 일반 관계의 역은 항상 잘 정의됩니다 (그냥 쌍을 뒤집으면 끝). 하지만 함수의 역은 전단사일 때만 함수가 된다고 했죠. 그게 바로 관계와 함수의 차이를 보여주는 좋은 예입니다.
예제 4.4.5
사람 집합 \(P\) 위에 "부모다" 관계 \(R\)을 둡시다. \(a\,R\,b\)는 "\(a\)는 \(b\)의 부모". 그러면 \(R^{-1}\)은 "자식이다" 관계가 됩니다. 또 \(R \circ R\)은 "조부모다" 관계예요 — \(a\)가 \(b\)의 부모이고 \(b\)가 \(c\)의 부모이면 \(a\)는 \(c\)의 조부모니까요. 이렇게 합성과 역으로 새 관계를 만들어가는 게 5장에서 다룰 동치관계, 순서관계의 토대가 됩니다.
마지막은 "집합의 크기"입니다. 유한집합의 크기는 그냥 원소의 개수예요. 직관적으로는 너무 당연해서 정의할 필요가 있나 싶지만, 큰 집합이나 무한집합으로 가면 "크기"라는 말 자체가 엄밀해야 합니다. 이 챕터에서는 유한 케이스만 다루고, 무한집합의 기수는 한참 뒤(15장쯤)에서 다시 등장합니다.
정의 4.5.1 (유한 기수)
유한집합 \(A\)의 기수(cardinality) \(|A|\)는 \(A\)의 원소 개수입니다. 예를 들어 \(|\emptyset| = 0\), \(|\{a, b, c\}| = 3\), \(|\{1, 2\} \times \{x, y, z\}| = 6\), \(|\mathcal{P}(\{1, 2, 3\})| = 2^3 = 8\).
기수의 산수에는 몇 가지 기본 규칙이 있어요.
이걸 함수의 단사/전사로 다시 쓸 수 있습니다. 유한집합 \(A, B\) 사이에 단사 \(f: A \to B\)가 있다면 \(A\)의 원소들이 \(B\) 안으로 겹치지 않게 들어간 것이니 \(|A| \le |B|\)예요. 거꾸로 전사 \(g: A \to B\)가 있다면 \(B\)의 모든 원소가 화살을 받았으니 \(A\)가 그것들을 모두 만들어낼 수 있어야 하고, 그래서 \(|A| \ge |B|\). 그리고 전단사가 있다면 \(|A| = |B|\).
정리 4.5.2 (기수 비교)
유한집합 \(A, B\)에 대해
이 정리가 강력한 이유는, 크기를 직접 세지 않고도 함수를 만들어 비교할 수 있다는 점입니다. 무한집합으로 일반화할 때 진짜 빛을 발해요. "두 집합이 같은 크기다"를 "전단사가 있다"로 정의하는 게 칸토어의 통찰이었거든요.
정리 4.5.3 (비둘기집 원리)
유한집합 \(A, B\)에 대해 \(|A| > |B|\)라면 어떤 함수 \(f: A \to B\)도 단사일 수 없다. 즉 \(f(a_1) = f(a_2)\)인 서로 다른 \(a_1, a_2 \in A\)가 반드시 존재한다.
증명 (스케치)
대우로 보이면 됩니다. \(f\)가 단사라 가정하면 정리 4.5.2에 의해 \(|A| \le |B|\)이므로 \(|A| > |B|\)에 모순. ∎
∎
이름이 귀엽죠. "비둘기집(pigeonhole) 원리"라 부르는 이유는, 비둘기 \(n+1\)마리를 둥지 \(n\)개에 넣으면 어떤 둥지에는 비둘기가 두 마리 이상 들어간다는 그림으로 외우면 쉽기 때문입니다. 단순해 보이지만 조합론, 그래프이론, 알고리즘 분석 곳곳에서 결정적으로 쓰이는 무기예요. 11장에서 본격적으로 다시 만납니다.
예제 4.5.4
서울 시민 중 머리카락 수가 똑같은 사람이 적어도 두 명 있을까요? 사람 머리카락은 보통 15만 개를 넘지 않습니다. 그러니 \(B = \{0, 1, \ldots, 200{,}000\}\)이라 두면 \(|B| = 200{,}001\). 서울 인구는 900만 명이 넘으니 \(|A| > |B|\). 비둘기집 원리에 의해 머리카락 수가 같은 사람이 무수히 많이 존재합니다. 직관적으로는 별것 아닌 결론 같지만, 직접 세지 않고 순수히 크기만으로 결론을 끌어낸 게 포인트예요.
맺음말
이 챕터에서 우리는 수학자의 자료구조 네 가지(집합, 수열, 함수, 관계)에 크기 개념까지 얹어봤습니다. 앞으로 등장하는 거의 모든 정의가 이 위에서 굴러갑니다. 그래프는 정점집합과 간선관계의 짝, 동치류는 관계의 한 종류, 수열은 \(\mathbb{N}\)에서 어떤 집합으로 가는 함수 등등. 컴퓨터과학에서도 마찬가지로 set/list/map/그래프 자료구조가 정확히 이 추상에 대응됩니다. 익숙해질 때까지는 손으로 작은 예제를 자꾸 그려보세요. 손에 붙는 만큼 5장 이후가 편해집니다.