앞 장에서는 명제와 논리 연산, 명제 함수를 살펴보았다. 이제 이러한 논리의 언어를 사용하여 수학의 기본 대상인 집합을 다룬다. 19세기 말 칸토어(Georg Cantor)가 발전시킨 집합론은 현대 수학의 거의 모든 분야의 기반이 되었다. 이 장에서는 집합의 기본 개념과 연산을 다루며, 명제와 집합 사이의 관계를 살펴본다.
1. 집합과 원소
이 장에서는 집합(set)을 명확하게 구별되는 대상들의 모임으로 직관적으로 이해한다. 집합을 이루는 각각의 대상을 원소(element)라고 부른다. 집합은 보통 대문자 \(A\), \(B\), \(C\) 등으로 나타내고, 원소는 소문자 \(a\), \(b\), \(c\) 등으로 나타낸다. 이러한 직관적 설명을 공리적으로 정교하게 만드는 방법은 뒤의 공리적 집합론에서 다룬다.
원소 \(a\)가 집합 \(A\)에 속할 때 \(a \in A\)로 나타내고, 속하지 않을 때 \(a \notin A\)로 나타낸다. 예를 들어, \(A\)가 세 개의 자연수 \(1,\) \(2,\) \(3\)으로 이루어진 집합일 때 \(2 \in A\)이고 \(4 \notin A\)이다.
원소를 하나도 갖지 않는 집합을 공집합(empty set)이라고 부르고 \(\varnothing\) 또는 \(\{\}\)로 나타낸다.
집합을 나타내는 방법에는 다음과 같은 것들이 있다.
- 원소나열법: 집합의 모든 원소를 나열하고 중괄호로 묶어 나타낸다.
예를 들어 \(5\) 이하인 양의 정수의 모임은 \(\{1,\, 2,\, 3,\, 4,\, 5\}\)이다. - 조건제시법: 원소가 만족시켜야 할 조건을 제시한다.
예를 들어 \(5\) 이하인 양의 정수의 모임은 \(\{x \mid x\text{는 } 5 \text{ 이하인 양의 정수}\}\)이다.
[원래는 \(\left\{ x\in\mathbb{Z} \mid 0 < x \le 5\right\}\)와 같이 \(x\)가 속하는 집합을 명시해 주어야 한다. 집합론의 공리 장의 분리 공리꼴을 참조하기 바란다.]
앞 장에서 정의한 명제 함수 \(p(x)\)와 집합 \(A\)에 대하여, "\(A\)의 모든 원소 \(x\)에 대하여 \(p(x)\)가 참이다"를 \(\forall x\in A,\,p(x)\)로 나타내고, "\(p(x)\)를 만족시키는 \(A\)의 원소 \(x\)가 적어도 하나 존재한다"를 \(\exists x\in A,\,p(x)\)로 나타낸다. 범위가 문맥상 정해져 있으면 각각 \(\forall x\,p(x)\), \(\exists x\,p(x)\)와 같이 쓰기도 한다. 이 기호들은 이 장의 뒤에서 한정명제를 다룰 때 자세히 설명한다.
2. 집합 사이의 관계
집합 \(A\)의 모든 원소가 집합 \(B\)의 원소일 때, \(A\)를 \(B\)의 부분집합(subset)이라고 부르고 \(A \subseteq B\)로 나타낸다. [일부 문헌에서는 \(A\subset B\)를 \(A\subseteq B\)와 같은 뜻으로 사용하기도 한다. 이 책에서는 \(A\subset B\)를 진부분집합의 뜻으로 사용한다.] 부분집합의 정의를 기호로 나타내면 다음과 같다. \[A \subseteq B \quad \Longleftrightarrow \quad \forall x\in A,\, x\in B\]
\(A \subseteq B\)이면서 \(A \neq B\)일 때 \(A\)를 \(B\)의 진부분집합(proper subset)이라고 부르고 \(A \subsetneq B\) 또는 \(A \subset B\)로 나타낸다.
두 집합 \(A\)와 \(B\)가 같다는 것은 \(A \subseteq B\)이고 \(B \subseteq A\)인 것이다. 두 집합이 같다는 정의를 기호로 나타내면 다음과 같다. \[A = B \quad \Longleftrightarrow \quad A \subseteq B \,\,\,\wedge\,\,\, B \subseteq A\] 이것은 또한 다음과 같이 나타낼 수도 있다. \[A = B \quad \Longleftrightarrow \quad \forall x\, (x\in A \,\, \leftrightarrow x\in B)\] 위 두 식 중 하나를 정의로 삼으면 다른 하나는 정리가 된다.
문제 2.1. 집합 \(A=\{1,\,2,\,\{1,2\}\}\)라 하자. 다음 명제가 참인지 거짓인지 판단하시오.
- \(1\in A\)
- \(\{1\}\in A\)
- \(\{1\}\subseteq A\)
- \(\{1,2\}\in A\)
- \(\{1,2\}\subseteq A\)
- \(\varnothing\in A\)
- \(\varnothing\subseteq A\)
문제 2.2. 다음을 증명하시오.
- 임의의 집합 \(A\)에 대하여 \(\varnothing \subseteq A\)이다.
- 임의의 집합 \(A\)에 대하여 \(A \subseteq A\)이다.
- \(A \subseteq B\)이고 \(B \subseteq C\)이면 \(A \subseteq C\)이다.
3. 집합의 연산
자주 사용하는 집합의 연산은 다음과 같은 것들이 있다.
- 두 집합 \(A\)와 \(B\)의 합집합(union) \(A \cup B\)는 \(A\)나 \(B\) 중 적어도 하나에 속하는 모든 원소들의 집합이다. \[A \cup B = \{x \mid x \in A \;\text{ 또는 }\; x \in B\}\]
- 두 집합 \(A\)와 \(B\)의 교집합(intersection) \(A \cap B\)는 \(A\)와 \(B\) 모두에 속하는 원소들의 집합이다. \[A \cap B = \{x \mid x \in A \;\text{ 그리고 }\; x \in B\}\] 두 집합 \(A\)와 \(B\)에 대하여 \(A \cap B = \varnothing\)일 때, \(A\)와 \(B\)는 서로소(disjoint)라고 한다.
- 집합 \(A\)에서 집합 \(B\)를 뺀 차집합(difference) \(A \setminus B\) 또는 \(A - B\)는 \(A\)에는 속하지만 \(B\)에는 속하지 않는 원소들의 집합이다. \[A \setminus B = \{x \mid x \in A \;\text{ 그리고 }\; x \notin B\}\]
- 전체집합 \(U\)가 주어졌을 때, 집합 \(A\)의 여집합(complement) \(A^c\) 또는 \(\overline{A}\)는 \(U\)에는 속하지만 \(A\)에는 속하지 않는 원소들의 집합이다. \[A^c = U \setminus A = \{x \in U \mid x \notin A\}\]
집합의 기본 연산 법칙은 다음과 같다.
정리 2.1. (집합 연산의 법칙)
전체집합 \(U\)를 고정시키고 \(A,B,C\subseteq U\)라 하자. 그러면 다음이 성립한다.
- 교환법칙: \[\begin{aligned} A \cup B &= B \cup A\\[3pt] A \cap B &= B \cap A \end{aligned}\]
- 결합법칙: \[\begin{aligned} (A \cup B) \cup C &= A \cup (B \cup C)\\[3pt] (A \cap B) \cap C &= A \cap (B \cap C) \end{aligned}\]
- 분배법칙: \[\begin{aligned} A \cup (B \cap C) &= (A \cup B) \cap (A \cup C)\\[3pt] A \cap (B \cup C) &= (A \cap B) \cup (A \cap C) \end{aligned}\]
- 드 모르간의 법칙: \[\begin{aligned} (A \cup B)^c &= A^c \cap B^c\\[3pt] (A \cap B)^c &= A^c \cup B^c \end{aligned}\]
- 항등법칙: \[\begin{aligned} A \cup \varnothing &= A\\[3pt] A \cap U &= A \end{aligned}\]
- 지배법칙: \[\begin{aligned} A \cup U &= U\\[3pt] A \cap \varnothing &= \varnothing \end{aligned}\]
- 멱등법칙: \[\begin{aligned} A \cup A &= A\\[3pt] A \cap A &= A \end{aligned}\]
- 여집합법칙: \[\begin{aligned} A \cup A^c &= U\\[3pt] A \cap A^c &= \varnothing\\[3pt] (A^c)^c &= A \end{aligned}\]
이러한 집합 연산의 법칙들은 1장에서 다룬 명제 연산의 법칙들과 일대일 대응 관계에 있다. 예를 들어, 집합 연산의 분배법칙 중 첫 번째 등식은 다음과 같이 명제 연산의 분배법칙을 사용하여 증명된다. \[\begin{aligned} x\in A \cup (B \cap C ) &\,\,\Longleftrightarrow\,\, x\in A \,\vee\, x\in B\cap C &&\text{(합집합의 정의)}\\[3pt] &\,\,\Longleftrightarrow\,\, x\in A \,\vee\, (x\in B \,\wedge\, x\in C) &&\text{(교집합의 정의)}\\[3pt] &\,\,\Longleftrightarrow\,\, (x\in A \,\vee\, x\in B ) \,\wedge\, (x\in A \,\vee\, x\in C) &&\text{(명제 연산의 분배법칙)}\\[3pt] &\,\,\Longleftrightarrow\,\, (x\in A \cup B ) \,\wedge\, (x\in A \cup C) &&\text{(합집합의 정의)} \\[3pt] &\,\,\Longleftrightarrow\,\, x\in (A \cup B ) \cap (A \cup C) . &&\text{(교집합의 정의)} \end{aligned}\]
문제 2.3. 전체집합 \(U=\{1,\,2,\,\ldots,\,10\}\)과 그 부분집합 \[ A=\{1,\,2,\,3,\,4,\,5\},\quad B=\{4,\,5,\,6,\,7\},\quad C=\{2,\,4,\,6,\,8,\,10\} \] 에 대하여 다음 집합을 원소나열법으로 나타내시오.
- \(A\cup B\), \(A\cap B\)
- \(A\setminus B\), \(B\setminus A\)
- \(A^c\), \(B^c\)
- \((A\cup B)^c\), \(A^c\cap B^c\)
- \((A\cap C)\setminus B\)
문제 2.4. 명제 연산의 성질을 사용하여 다음 등식을 증명하시오.
- \(A \cap (B \cup C)=(A\cap B)\cup(A\cap C)\)
- \((A\cup B)^c=A^c\cap B^c\)
- \(A\cup A^c=U\)
- \((A^c)^c=A\)
문제 2.5. 집합의 연산의 정의를 사용하여 다음 등식을 증명하시오.
- \((A \cup B) \setminus C = (A \setminus C) \cup (B \setminus C)\)
- \((A \setminus B) \cap C = (A \cap C) \setminus B\)
- \(A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)\)
4. 멱집합
집합 \(A\)의 모든 부분집합들의 집합을 \(A\)의 멱집합(power set)이라 하고 \(\mathcal{P}(A)\) 또는 \(2^A\)로 나타낸다. \(A\)의 멱집합을 조건제시법으로 나타내면 다음과 같다. \[\mathcal{P}(A) = \{X \mid X \subseteq A\}\]
예를 들어, \(A = \{1,\, 2\}\)일 때, \[\mathcal{P}(A) = \{\varnothing,\, \{1\},\, \{2\},\, \{1,\, 2\}\} .\]
멱집합이 가진 중요한 성질로는 다음과 같은 것들이 있다.
- \(\varnothing \in \mathcal{P}(A)\)이고 \(A \in \mathcal{P}(A)\)이다.
- \(X \in \mathcal{P}(A)\)일 필요충분조건은 \(X \subseteq A\)인 것이다.
- \(A \subseteq B\)일 필요충분조건은 \(\mathcal{P}(A) \subseteq \mathcal{P}(B)\)인 것이다.
문제 2.6. 집합 \(A=\{a,b,c\}\)와 \(B=\{a,b\}\)에 대하여 다음을 구하거나 증명하시오.
- \(\mathcal{P}(A)\)를 원소나열법으로 나타내시오.
- \(A\)의 원소를 정확히 두 개 가지는 부분집합을 모두 구하시오.
- \(\mathcal{P}(B)\)를 구하고 \(\mathcal{P}(B)\subseteq\mathcal{P}(A)\)임을 확인하시오.
- 임의의 집합 \(X\), \(Y\)에 대하여 \[ X\subseteq Y \quad\Longleftrightarrow\quad \mathcal{P}(X)\subseteq\mathcal{P}(Y) \] 임을 증명하시오.
5. 유한집합과 무한집합
집합은 원소의 개수에 따라 유한집합(finite set)과 무한집합(infinite set)으로 분류된다. 원소를 모두 세었을 때 그 개수가 어떤 음이 아닌 정수가 되는 집합을 유한집합이라고 부르고, 그렇지 않은 집합을 무한집합이라고 부른다. 유한집합 \(A\)의 원소의 개수를 \(n(A)\) 또는 \(|A|\)로 나타낸다. 특히 \(n(\varnothing) = 0\)이다.
유한집합 \(A\), \(B\)에 대하여 다음이 성립한다.
- \(n(A \cup B) = n(A) + n(B) - n(A \cap B)\).
- \(A \cap B = \varnothing\)이면 \(n(A \cup B) = n(A) + n(B)\)이다.
- 유한집합 \(A\)에 대하여 \(n(\mathcal{P}(A)) = 2^{n(A)}\)이다.
무한집합의 예로는 자연수의 집합 \(\mathbb{N}\), 정수의 집합 \(\mathbb{Z}\), 유리수의 집합 \(\mathbb{Q}\), 실수의 집합 \(\mathbb{R}\) 등이 있다. [이 교재에서 '자연수'는 \(0\) 이상인 정수를 나타내며, \(\mathbb{N} = \left\{0,\,1,\,2,\,3,\,\ldots\right\}\)이다.] 무한집합도 그 크기에 따라 가산무한집합과 비가산무한집합으로 분류되는데, 이것은 유한집합과 무한집합 장에서 자세히 다룬다.
문제 2.7. 집합 \(S=\{1,2,\ldots,60\}\)에서 \(2\)의 배수들의 집합을 \(A\), \(3\)의 배수들의 집합을 \(B\)라 하자. 다음을 구하시오.
- \(n(A)\)와 \(n(B)\)
- \(n(A\cap B)\)
- \(n(A\cup B)\)
- \(2\)의 배수도 아니고 \(3\)의 배수도 아닌 \(S\)의 원소의 개수
문제 2.8. 유한집합 \(A\), \(B\), \(C\)에 대하여 다음을 증명하시오.
- \(n(A \cup B \cup C) = n(A) + n(B) + n(C) - n(A \cap B) - n(B \cap C) - n(C \cap A) + n(A \cap B \cap C)\)
- \(A \subseteq B\)이면 \(n(A) \leq n(B)\)이다.
- 두 집합 \(A\), \(B\)의 데카르트 곱을 \(A\times B=\{(a,b)\mid a\in A,\ b\in B\}\)로 정의할 때, \(n(A \times B) = n(A) \cdot n(B)\)이다.
문제 2.9. 양의 정수 \(m\)과 유한집합 \(A_1,\,\ldots,\,A_m\)에 대한 '포함--배제의 원리'를 서술하고, \(m=3\)인 경우에 문제 2.8의 (1)이 얻어짐을 확인하시오.
6. 한정명제
앞에서 사용한 \(\forall\)와 \(\exists\)는 집합과 관련하여 자주 사용되는 한정기호(quantifier)이다. 한정기호를 사용한 명제를 한정명제라고 부른다. 여기서는 전칭명제와 존재명제를 살펴본다.
전칭명제
명제 함수 \(p(x)\)와 집합 \(A\)에 대하여, "\(A\)의 모든 원소 \(x\)에 대하여 \(p(x)\)가 참이다"를 \[\forall x \in A,\, p(x)\] 와 같이 나타낸다. 이 표기는 \(\forall x\,(x\in A\to p(x))\)의 약식 표기이다. 이때 \(\forall\)는 전칭기호라고 부르며, "모든"을 의미한다. 전칭기호를 사용하여 표현한 명제를 전칭명제(universal statement)라고 부른다. 예를 들어, 모든 짝수의 집합을 \(E\)라고 할 때, "모든 짝수는 2로 나누어떨어진다"라는 문장은 다음과 같이 나타낼 수 있다. \[\forall n \in E,\,\, 2 \mid n \]
존재명제
명제 함수 \(q(x)\)와 집합 \(A\)에 대하여, "\(q(x)\)를 만족시키는 \(A\)의 원소 \(x\)가 적어도 하나 존재한다"를 \[\exists x \in A,\, q(x)\] 와 같이 나타낸다. 이 표기는 \(\exists x\,(x\in A\wedge q(x))\)의 약식 표기이다. 이때 \(\exists\)는 존재기호라고 부르며, "어떤 \(\sim\)가 존재한다" 또는 "\(\cdots\)를 만족시키는 원소가 적어도 하나 존재한다"를 의미한다. 존재기호를 사용하여 표현한 명제를 존재명제(existential statement)라고 부른다. 예를 들어, "제곱하여 2가 되는 실수가 존재한다"라는 문장은 다음과 같이 나타낼 수 있다. \[\exists x \in \mathbb{R},\,\, x^2 = 2 \]
문제 2.10. 다음 한정명제가 참인지 거짓인지 판단하고 그 이유를 설명하시오.
- \(\forall n\in\mathbb{Z},\; n^2\geq 0\)
- \(\exists n\in\mathbb{Z},\; n^2=2\)
- \(\forall x\in\mathbb{R},\; \exists y\in\mathbb{R},\; y>x\)
- \(\exists y\in\mathbb{R},\; \forall x\in\mathbb{R},\; y>x\)
한정명제의 부정
정리 2.2. (한정명제의 부정)
한정명제의 부정에 대하여 다음이 성립한다. \[\begin{aligned} \neg(\forall x \in A,\, p(x)) &\,\equiv\, \exists x \in A,\, \neg p(x),\\[3pt] \neg(\exists x \in A,\, q(x)) &\,\equiv\, \forall x \in A,\, \neg q(x). \end{aligned}\]
증명 첫 번째 동치는 "\(A\)의 모든 원소가 \(p(x)\)를 만족시킨다"가 거짓이라는 것이 곧 \(p(x)\)를 만족시키지 않는 \(A\)의 원소가 적어도 하나 존재한다는 뜻이므로 성립한다. 두 번째 동치는 "\(q(x)\)를 만족시키는 \(A\)의 원소가 존재한다"가 거짓이라는 것이 곧 \(A\)의 모든 원소가 \(q(x)\)를 만족시키지 않는다는 뜻이므로 성립한다.
문제 2.11. 다음 명제를 한정기호를 사용하여 나타내고, 그 부정을 구하시오.
- 모든 실수의 제곱은 음이 아니다.
- 어떤 자연수는 소수이다.
- 임의의 양의 실수 \(\epsilon\)에 대하여, \(|x| < \epsilon\)을 만족시키는 \(0\)이 아닌 실수 \(x\)가 존재한다.
집합의 표현과 한정명제
조건제시법으로 집합을 나타낼 때 한정명제가 중요한 역할을 한다. 다음과 같은 예를 살펴보자.
- 짝수의 집합: \(\{n \in \mathbb{Z} \mid \exists k \in \mathbb{Z},\, n = 2k\}\)
- 소수의 집합: \(\{p \in \mathbb{N} \mid p > 1 \,\text{ 그리고 }\, \forall d \in \mathbb{N},\, (d \mid p \to d = 1 \,\text{ 또는 }\, d = p)\}\)
- 유리수의 집합: \(\{x \in \mathbb{R} \mid \exists p \in \mathbb{Z},\, \exists q \in \mathbb{Z} \setminus \{0\},\, x = \frac{p}{q}\}\)