집합의 개념

by I Seul Bee

집합은 현대 수학의 가장 기본적인 개념이다. 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\)가 속하는 집합을 명시해 주어야 한다. 집합론의 공리에서 '분류 공리'를 참조하기 바란다.]

2. 집합 사이의 관계

집합 \(A\)의 모든 원소가 집합 \(B\)의 원소일 때, \(A\)를 \(B\)의 부분집합(subset)이라고 부르고 \(A \subseteq B\)로 나타낸다. [\(A\)가 \(B\)의 부분집합인 것을 기호로 \(A\subset B\)와 같이 나타내기도 한다.] 부분집합의 정의를 기호로 나타내면 다음과 같다. \[A \subseteq B \quad \Longleftrightarrow \quad \forall x\, (x \in A \to 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. 다음을 증명하시오.

  1. 임의의 집합 \(A\)에 대하여 \(\varnothing \subseteq A\)이다.
  2. 임의의 집합 \(A\)에 대하여 \(A \subseteq A\)이다.
  3. \(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\}\]

집합의 기본 연산 법칙은 다음과 같다.

  • 교환법칙: \[\begin{aligned} A \cup B &= B \cup A\\[6pt] A \cap B &= B \cap A \end{aligned}\]
  • 결합법칙: \[\begin{aligned} (A \cup B) \cup C &= A \cup (B \cup C)\\[6pt] (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)\\[6pt] 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\\[6pt] (A \cap B)^c &= A^c \cup B^c \end{aligned}\]
  • 항등법칙: \[\begin{aligned} A \cup \varnothing &= A\\[6pt] A \cap U &= A \end{aligned}\]
  • 지배법칙: \[\begin{aligned} A \cup U &= U\\[6pt] A \cap \varnothing &= \varnothing \end{aligned}\]
  • 멱등법칙: \[\begin{aligned} A \cup A &= A\\[6pt] A \cap A &= A \end{aligned}\]
  • 여집합법칙: \[\begin{aligned} A \cup A^c &= U\\[6pt] A \cap A^c &= \varnothing\\[6pt] (A^c)^c &= A \end{aligned}\]

이러한 집합 연산의 법칙들은 1장에서 다룬 명제 연산의 법칙들과 일대일 대응 관계에 있다. 예를 들어, 집합 연산의 분배법칙 중 첫 번째 등식은 다음과 같이 명제 연산의 분배법칙을 사용하여 증명된다. \[\begin{align*} x\in A \cup (B \cap C ) &\,\,\Longleftrightarrow\,\, x\in A \,\vee\, x\in B\cap C &&\text{(합집합의 정의)}\\[6pt] &\,\,\Longleftrightarrow\,\, x\in A \,\vee\, (x\in B \,\wedge\, x\in C) &&\text{(교집합의 정의)}\\[6pt] &\,\,\Longleftrightarrow\,\, (x\in A \,\vee\, x\in B ) \,\wedge\, (x\in A \,\vee\, x\in C) &&\text{(명제 연산의 분배법칙)}\\[6pt] &\,\,\Longleftrightarrow\,\, (x\in A \cup B ) \,\wedge\, (x\in A \cup C) &&\text{(합집합의 정의)} \\[6pt] &\,\,\Longleftrightarrow\,\, x\in (A \cup B ) \cap (A \cup C) . &&\text{(교집합의 정의)} \end{align*}\]

문제 2.2. 명제 연산의 성질을 사용하여 집합의 기본 연산 법칙을 증명하시오.

문제 2.3. 집합의 연산의 정의를 사용하여 다음 등식을 증명하시오.

  1. \((A \cup B) \setminus C = (A \setminus C) \cup (B \setminus C)\)
  2. \((A \setminus B) \cap C = (A \cap C) \setminus B\)
  3. \(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)\)인 것이다.

5. 유한집합과 무한집합

집합은 원소의 개수에 따라 유한집합(finite set)과 무한집합(infinite set)으로 분류된다. 즉 원소의 개수를 \(0\) 또는 양의 정수로 나타낼 수 있는 집합을 유한집합이라고 부르고, 그렇지 않은 집합을 무한집합이라고 부른다. 유한집합 \(A\)의 원소의 개수를 \(n(A)\) 또는 \(|A|\)로 나타낸다. 특히 \(n(\varnothing) = 0\)이다.

유한집합의 원소의 개수에 대하여 다음이 성립한다.

  • \(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}\) 등이 있다. 무한집합도 그 크기에 따라 가산무한집합과 비가산무한집합으로 분류되는데, 이것은 뒤에서 자세히 다룬다.

문제 2.4. 유한집합 \(A\), \(B\), \(C\)에 대하여 다음을 증명하시오.

  1. \(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)\)
  2. \(A \subseteq B\)이면 \(n(A) \leq n(B)\)이다.
  3. \(n(A \times B) = n(A) \cdot n(B)\)이다. (여기서 \(A \times B\)는 데카르트 곱이다.)

문제 2.5. '포함-배제의 원리'를 조사해 보자.

6. 한정명제

집합과 관련하여 자주 사용되는 중요한 논리 기호로 한정기호(quantifier)가 있다. 한정기호를 사용한 명제를 한정명제라고 한다. 한정명제는 전칭명제와 존재명제가 있다.

전칭명제

명제 함수 \(p(x)\)와 집합 \(A\)에 대하여, "\(A\)의 모든 원소 \(x\)에 대하여 \(p(x)\)가 참이다"를 \[\forall x \in A,\, 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\)는 존재기호라고 부르며, "어떤 \(\sim\)가 존재한다" 또는 "\(\cdots\)를 만족시키는 원소가 적어도 하나 존재한다"를 의미한다. 존재기호를 사용하여 표현한 명제를 존재명제(existential statement)라고 부른다. 예를 들어, "제곱하여 2가 되는 실수가 존재한다"라는 문장은 다음과 같이 나타낼 수 있다. \[\exists x \in \mathbb{R},\,\, x^2 = 2 \]

한정명제의 부정

한정명제의 부정 규칙은 다음과 같다. \[\begin{align*} \neg(\forall x \in A,\, p(x)) &\,\equiv\, \exists x \in A,\, \neg p(x),\\[6pt] \neg(\exists x \in A,\, q(x)) &\,\equiv\, \forall x \in A,\, \neg q(x). \end{align*}\]

문제 2.6. 다음 명제를 한정기호를 사용하여 나타내고, 그 부정을 구하시오.

  1. 모든 실수의 제곱은 음이 아니다.
  2. 어떤 자연수는 소수이다.
  3. 임의의 양수 \(\epsilon\)에 대하여, \(|x| < \epsilon\)을 만족시키는 \(x \neq 0\)이 존재한다.

집합의 표현과 한정명제

조건제시법으로 집합을 나타낼 때 한정명제가 중요한 역할을 한다. 다음과 같은 예를 살펴보자.

  • 짝수의 집합: \(\{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}\}\)

이처럼 집합론과 논리는 서로 밀접하게 연관되어 있으며, 한정기호는 수학적 개념을 정확하게 표현하는 데 필수적인 도구이다.

집합과 수리논리 첫걸음 목차 보기

명제와 논리 집합의 개념 다양한 집합의 연산 관계와 함수 유한집합과 무한집합 자연수 집합의 기수 집합의 서수 집합론의 공리 선택 공리 형식논리 명제논리의 개념 명제논리의 건전성과 완전성 일계논리의 구문론 일계논리의 의미론 일계논리의 추론규칙 일계논리의 콤팩트성 페아노 산술 불완전성 정리