제1장 집합과 논리의 기초

``철학은 우주라는 드넓은 책에 쓰여있다. … 그것은 수학의 언어로 쓰였으며 그것의 문자는 삼각형, 동그라미 그리고 다른 기하학적 수치들이다.''
-갈릴레오 갈릴레이(Galileo Galilei; 1564--1642)-

19세기 말 수학자 칸토르(Cantor, G.; 1845--1918)는 무한집합에 관한 이론을 처음으로 발표하였다. 수학의 긴 역사를 생각해볼 때 `집합'이라는 개념을 구체적으로 다룬 것은 비교적 최근의 일이라 할 수 있다. 오늘날에는 모든 수학적 대상을 집합을 이용하여 정의한다고 해도 과언이 아니다. 즉 집합은 오늘날의 수학을 기술하는 현대수학의 언어라고 할 수 있다. 집합과 명제에 대한 공부는 생각하는 대상을 명확히 말할 수 있게 해주며 논리적인 전개의 바탕이 된다.

1.1 집합과 명제

집합의 뜻과 표현

주어진 조건에 의하여 그 대상을 분명하게 결정할 수 있는 모임을 집합이라고 하고, 집합을 이루고 있는 대상 하나하나를 그 집합의 원소라고 한다. 예를 들어

• 훌륭한 사람들의 모임
• 키가 큰 사람들의 모임
• 아주 큰 자연수들의 모임

과 같은 모임들은 집합이 아니고

• \(10\)보다 작은 수들의 모임
• 한 자리 자연수들의 모임
• 2020년에 세종과학예술영재학교에 입학한 학생들의 모임
• 2016년에 세종과학예술영재학교를 졸업한 학생들의 모임

과 같은 모임들은 집합이다.

\(10\)보다 작은 소수들의 모임을 \(A\)라고 할 때, \(2\)는 집합 \(A\)의 원소이다. 이때, ``\(2\)는 집합 \(A\)에 속한다.''라고 말하고 이를 간단히 기호로 \[ 2\in A \] 와 같이 나타낸다. 한편 \(6\)은 \(A\)의 원소가 아니고 이때는 \(6\notin A\)와 같이 나타낸다. 관례적으로 집합을 나타낼 때는 대문자 \(A, B, C, \ldots\) 등을 쓰고, 원소를 나타낼 때에는 소문자 \(a, b, c, \ldots\) 등을 쓴다.

집합은 그것을 이루고 있는 원소들에 의해 결정되므로 어떤 집합을 표현하고자 할 때는 그 원소들이 무엇인지를 표현해주면 된다. 가장 간단한 방법은 원소들을 중괄호 \(\{\quad\}\) 안에 모두 나열하는 것으로 이 표기 방법을 원소나열법이라고 한다. 예를 들어 \(10\)보다 작은 소수들의 모임은 \[ A=\{ 2, 3, 5, 7 \} \] 과 같이 나타낼 수 있다. 원소나열법으로 집합을 나타낼 때는 원소들이 나열된 순서는 중요하지 않다. 그리고 하나의 원소가 두 번 표현된 것은 의미가 없다. 즉 \(\{ 2, 3, 5, 7\}=\{3, 7, 2, 5\}=\{7, 5, 3, 2\}\)이고 \(\{ 2, 2, 3, 5, 5, 5, 5, 7\}\)과 같이 원소를 중복해서 쓰는 표현은 잘 사용하지 않는다.¹ 한편 어떠한 경우에는 집합의 원소들을 일일이 나열하는 것보다 그 집합의 원소가 될 조건을 명시하여 나타내는 것이 필요할 때가 있다. 예를 들어 \[ A=\{ n\in\mathbb{N} \mid n<10, \mbox{\(n\)은 소수}\} \] 는 \(A\)가 `\(n<10\)'과 `\(n\)은 소수'라는 조건을 만족시키는 \(\mathbb{N}\)의 원소 \(n\)들의 모임이라는 뜻이다.[efn_note] \(\mathbb{N}\)은 자연수 전체의 집합이다. 그리고 중괄호 안에 있는 기호 `\(\mid\)'는 `such that'을 의미하는 기호이다.[/efn_note] 따라서 \(A\)는 집합 \(\{2, 3, 5, 7\}\)을 나타낸다. 이와 같이 조건을 명시하여 집합을 나타내는 방법을 조건제시법이라고 한다.

보기 다음은 각 집합들을 원소나열법과 조건제시법으로 나타낸 예이다.

1. \(\{1,2,3,4,5,6,7,8,9,10\}=\{ x\in\mathbb{N} \mid \mbox{\(x\)는 \(10\) 이하의 자연수}\}\)
2. \(\{1,2,3,4,6,9,12,18,27,36,54,108\} =\{ x\in\mathbb{N} \mid \mbox{\(x\)는 \(108\)의 양의 약수}\} \)
3. \(\{2, 4, 6, 8, \ldots\}=\{ x\in\mathbb{N} \mid \mbox{\(x\)는 짝수}\}\)

집합을 그림으로 나타낼 수도 있다. 예를 들어 집합 $A$를 $6$의 약수들 전체의 집합이라고 하면, $A$의 원소는 $1, 2, 3, 6$이므로 이를 다음 그림과 같이 나타낼 수 있다.

이와 같은 그림을 벤 다이어그램이라고 한다. 이처럼 그림을 통해 집합의 원소까지 나타낼 때엔 원소나열법 혹은 조건제시법을 함께 사용해야 한다. 벤 다이어그램은 집합들 간의 논리적 관계를 시각적으로 손쉽게 나타낼 수 있는 장점이 있지만, 나타내야 할 집합의 수가 많아질 경우에는 오히려 불편할 수 있다.²

집합을 원소의 개수에 따라 두 종류로 분류하기도 한다. 원소가 유한개인 집합을 유한집합이라고 하며, 원소가 무한히 많은 집합을 무한집합이라고 한다.³ 한편, 예를 들어 $\{ x \mid \mbox{$x$는 $1$보다 크고 $2$보다 작은 자연수}\}$처럼 원소가 하나도 없는 집합을 공집합이라 하고 기호로 \[ \varnothing\quad\mbox{혹은}\quad\emptyset \] 와 같이 나타낸다. 물론 공집합은 유한집합이다.

집합 \(A\)가 유한집합일 때, 집합 \(A\)의 원소의 개수를 기호로 \[ n(A) \] 와 같이 나타낸다.⁴ 예를 들어 집합 $A=\{ 0, 1, 2, 3, 4\}$는 원소의 개수가 $5$이므로 \(n(A)=5\)이고 공집합은 원소가 하나도 없으므로 \(n(\varnothing)=0\)이다.

명제와 조건

집합의 뜻과 표현을 살펴본 후에는 `집합의 연산'에 대해 공부하는 것이 보통이지만, 우리는 좀 더 명료하게 그 이론들을 살펴보기 위해 `명제'에 대해 살펴보고자 한다.

수학에서는 이론을 엄밀하고 일관되게 전개하기 위해 일정한 형식을 갖는 언어를 사용하는데 이러한 형식언어는 명제의 형태를 띄고 있다. 형식언어를 사용하지 않은 진술은 그 의미가 모호하고 변질되기 쉽다.⁵ 그러나 명제 그 자체의 의미는 명제의 형태로 진술되기 어렵다. 따라서 수학적 논리를 전개해 나가기 위해 필요한 매우 기초적인 몇몇 개념에 대해서는 일상적으로 사용하는 언어를 통해 진술한다.⁶

이제 명제와 그것을 이용한 기초적인 논리에 대하여 살펴보자.

예를 들어 `$3$은 홀수이다'는 참인 명제이며 `자연수의 개수는 유한이다'는 거짓인 명제이다. 그러나 `우리학교 급식은 맛있다', `오늘 날씨가 좋으냐?'와 같은 문장은 명제가 아니다. 명제에는 참, 거짓 중 어느 한쪽이어야 함을 분명히 가릴만한 조건이 갖추어져 있어야 한다. 명제의 참, 거짓은 곧바로 정할 수 있는 경우도 있고 경우에 따라서는 노력이 다소 들 때가 있으며, 결론에 도달할 수 없는 경우도 있다.

참 거짓 여부를 결정하는 하나의 진술만을 포함하고 있는 명제를 단순명제(simple statement)라고 하고, 둘 이상의 단순명제가 결합된 것을 합성명제(compounded statement)라고 한다. 이를테면,

``나는 여자이고 내 동생은 남자이다.''

라는 명제는 `나는 여자이다.'라는 명제와 `내 동생은 남자이다.'라는 명제가 합성된 것이다.

흔히 수를 나타낼 때 문자를 사용하듯이 논리에 있어서도 명제를 $p, q, r, \ldots$과 같이 문자를 사용하여 나타낼 수 있다. 명제를 연결하여 합성명제를 구성하는 방법은 여러 가지가 있으나 흔히 이용되고 있는 것으로는 다섯 가지가 있다. 이 다섯 가지의 결합자(connective)는 다음과 같다.

위 정의만으로는 결합자의 의미를 정확하게 파악할 수 없으므로 지금부터 `진리표'를 이용하여 결합자의 의미를 살펴보자.

하나의 명제 $p$에 대하여 `$p$의 부정'이라고 부르는 $\sim p$는 명제 $p$가 거짓일 때에 참이고, $p$가 참일 때에 거짓인 명제이다. 즉 명제 $\sim p$의 참, 거짓 여부는 명제 $p$의 참, 거짓에 달려있다. 이러한 의존성을 다음과 같은 진리표(truth table)에 실어두면 편리하다.

물론 여기서 문자 T는 참, 문자 F는 거짓을 나타낸다. 위 표의 첫째 열은 $p$에 대한 두 가지 가능한 진릿값(truth value), 즉 T 또는 F를 기록하였다.

다음으로 논리곱과 논리합을 진리표로 나타내보면 다음과 같다.

논리곱 $p\wedge q$와 같은 합성명제에 대하여 각각의 명제 $p, q$를 그 명제의 성분(component)이라고 한다. 합성명제의 성분은 단순명제이거나 합성명제일 수도 있다. $p\wedge q$와 같이 두 성분으로 이루어진 합성명제에 있어서 검토해야 할 모든 가능성, 이른바 논리적 가능성(logical possibility)은 많아야 $4$가지가 있다.

명제를 합성할 때에는 괄호를 통해 우선순위를 정해준다. 예를 들어 \[ (q\wedge r)\vee p \] 는 $q$와 $r$의 논리곱의 결과와 $p$를 논리합 하는 것을 뜻한다. 그리고 괄호가 없을 때에는 연결사의 우선순위는 보통 $\sim, \wedge, \vee, \longrightarrow, \longleftrightarrow$ 순으로 쓰기도 하지만 역시 모호하지 않게 괄호를 이용하여 나타내는 것이 가장 좋다고 할 수 있겠다.

다음으로 논리 조건을 살펴보아야 하는데, 그 전에 논리적 동치의 개념을 정의한다.

예제 1.1 두 명제 \(p, q\)에 대하여 $p\vee q \equiv\ \sim(\sim p\ \wedge \sim q)$임을 보여라.

Sol. 명제 \(\sim (\sim p\ \wedge \sim q)\)의 진리표를 작성해보면 다음과 같다.

따라서 명제 $\sim(\sim p\ \wedge \sim q)$의 진릿값이 앞서 살펴본 $p\vee q$의 진릿값과 동일함을 알 수 있다.

임의의 두 명제 $p$와 $q$ 사이에 조건부(conditional)라고 불리는 결합자 $\longrightarrow$를 붙여서 만든 합성명제 $p\longrightarrow q$는 $\sim p \vee q$와 동치인 것으로 정의되며 이를 진리표로 나타내면 다음과 같다.

조건부의 진리표를 살펴보면 $p$가 참이고 $q$가 거짓인 경우를 제외하면 $p\longrightarrow q$는 참이다. 일상적인 언어에서는 `토끼가 식물이면 감자는 동물이다.'와 같은 말은 토끼가 식물이 아니고 감자는 동물이 아니기 때문에 무의미한 문장이 된다. 하지만 이 문장을 명제의 논리로 살펴보면 참인 명제가 된다. 이처럼 일상 언어에서는 의미 없이 결합된 문장이라도 논리적으로 보면 참, 거짓을 정할 수 있는 명제가 될 수 있다. % 이러한 문장을 형식적 언어라고 한다

명제 $p\longrightarrow q$가 $\sim p\vee q$로 정의된 것은 논리법칙들 중에 조금은 이상하게 느껴질 수 있는데 `$p$이면 $q$이다.'라는 말은 $p$가 참일 때 $q$가 참이라는 주장이므로 $p$가 거짓일 때는 $q$의 진위에 관계없이 참인 말이 되는 것이다. 예를 들어 ``삼각형의 내각의 합이 \(360\)도라면 $2$의 $10$제곱은 $37$이다.''는 참인 명제이다. 이와 같이 가정이 거짓이라서 결론에 관계없이 참이 되는 경우를 vacuously true인 경우라고 한다.

유제 1.2 다음 각 명제의 진리표를 작성하여라.

1. $(p\wedge q)\wedge r$
2. $p\wedge (q\wedge r)$
3. $(p\ \vee \sim q)\wedge r$
4. $\sim (p\wedge q)\vee r$
5. $p\longleftrightarrow q$
6. $(p \wedge q)\vee(\sim p\ \wedge \sim q)$

유제 1.3 명제 $p$가 `나는 펭수이다.', 명제 $q$가 `나는 빌런이다.'일 때, 다음의 합성명제를 자연스러운 문장으로 만들어라.

1. $p\vee q$
2. $p\wedge q$
3. $p\longrightarrow q$
4. $\sim p\longrightarrow\ \sim q$
5. $\sim q\longrightarrow\ \sim p$
6. $\sim p\wedge q$

유제 1.4 명제 $p$가 `나는 펭수이다.'이고, 명제 $q$가 `나는 빌런이다.'일 때, 문장으로 된 다음의 명제를 기호를 사용하여 표현하여라.

1. 나는 펭수이지만 빌런은 아니다.
2. 나는 빌런이므로 펭수이다.
3. 내가 빌런이려면 나는 펭수이어야 한다.
4. 내가 펭수이면 나는 빌런이 아니다.

한편 문장들 중에서는 \[ \text{$x$는 $6$의 약수이다.} \] 처럼 변수 $x$에 특정한 경우를 대입했을 때 명제가 되는 경우가 있다. 이러한 문장을 조건이라고 한다. 이 때, 이 조건이 참인 $x$들을 모두 모아 놓은 집합을 생각할 수 있는데 이 집합을 그 조건의 진리집합이라고 부른다. 예를 들어 위에서 제시한 조건의 진리집합은 \[ P=\{ x\mid \mbox{$x$는 $6$의 약수}\} \] 이다. 이렇게 집합 $P$를 설정하고나면 `$x$는 $6$의 약수이다.'라고 말하는 것이나 `$x\in P$'라고 하는 것이나 동일한 말이 된다. 집합을 표현할 때, 이미 알고 있는 집합을 상정하고 그것의 원소들 가운데 특정 조건을 만족시키는 원소들을 모음으로써 집합을 구성하는 경우가 많다. 이때 처음 가정하는 집합을 전체집합이라고 부르고 보통 기호로는 \(U\)로 나타낸다. 전체집합 \(U\)를 가정하고 있는 경우, 조건 \(p(x)\)가 집합 \(U\)에서 정의되어 있다고 말한다. ⁷ 물론 위의 조건은 자연수 전체의 집합 \(\mathbb{N}\)에서 정의되어 있는 것이다. 이러한 맥락에서 진리집합 \(P\)를 \[ P=\{ x\in \mathbb{N}\mid p(x) \}=\{ x\in \mathbb{N}\mid \mbox{$x$는 $6$의 약수}\} \] 라고 쓸 수 있다. 즉 진리집합 \(P\)는 전체집합인 \(\mathbb{N}\)의 원소들 가운데 \(6\)의 약수들을 모아 놓은 것이다.

집합의 포함관계

두 집합 \(A, B\)가 있을 때, 모든 $x$에 대하여 \[ x\in A\ \longrightarrow\ x\in B \] 와 \[ x\in B\ \longrightarrow\ x\in A \] 가 참일 때, 두 집합이 같다고 말하고 이를 \(A=B\)로 나타낸다. 또한 모든 $x$에 대하여 \[ x\in A\ \longrightarrow\ x\in B \] 가 참일 때, \(A\)를 \(B\)의 부분집합이라고 부르고 이를 기호로 \[ A\subset B\quad\mbox{혹은}\quad A\subseteq B \] 와 같이 나타낸다. 만일 \(A\neq B\)이고 \(A\subset B\)이면 \(A\)를 \(B\)의 진부분집합이라고 부른다. 재미있는 명제를 하나 증명해보자.

Proof. 모든 $x$에 대하여 \begin{equation} x\in \varnothing\ \longrightarrow\ x\in A \tag{1.1} \end{equation} 가 참임을 보이면 된다. 그런데 공집합의 정의에 의하여 $x\in \varnothing$는 거짓이므로 (1.1)은 참이다.

유제 1.5 집합 \(S=\{ a, b, c\}\)의 부분집합을 모두 구하여라.

Sol. 각각의 원소가 속하는 경우와 속하지 않는 경우를 생각하면 모두 \(2^{3}=8\)가지의 경우가 나온다. 따라서 부분집합은 $8$개이며 이것을 나열하면 다음과 같다. \[ \varnothing, \{ a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, S \] 참고로 이들 중 \(S\)를 제외한 다른 것들은 \(S\)의 진부분집합이다.

유제 1.6 집합 $\{ x, \{y, z\}\}$의 부분집합을 모두 구하여라.

유제 1.7 집합 $\{a, b, c, d, e\}$의 부분집합 중에서 두 원소 $\{a, b\}$를 반드시 원소로 갖는 집합을 모두 구하여라.

유제 1.8 두 집합 $A=\{ a, 2\}, B=\{b, b^{2}\}$에 대하여 $A\subset B$이고 $B\subset A$가 되도록 하는 정수 $a, b$의 값을 구하여라.

집합 $A$가 주어졌을 때, $A$의 부분집합들을 모두 모아놓은 집합을 $A$의 멱집합(power set)이라고 부르고 이를 기호로 \[ \wp(A) \]이 나타낸다.

보기 집합 $A=\{ 1, 2\}$ 에 대하여 $A$의 멱집합 $\wp(A)$는 \[ \wp(A)=\left\{ \varnothing, \{1 \}, \{2 \}, \{1, 2\} \right\} \] 이다.

유제 1.9 공집합 $\varnothing$에 대하여 $\wp(\wp(\varnothing))$을 구하여라.

---

1. 수학자들은 쓸데 없이 잉크를 낭비하는 것을 그리 좋아하지 않는다(절약정신).
2. 당장 4--5개의 집합을 벤 다이어그램으로 한꺼번에 나타내는 것을 시도해보라.
3. `유한', `무한'... 뭘까...
4. 집합의 원소의 개수를 나타낼 때 \(\vert A\vert\) 혹은 \(\# (A)\)와 같은 표기도 많이 사용한다.
5. 명제 및 집합의 이론을 대하여 공부해야 하는 이유는 바로 여기에 있다.
6. 정말 엄밀하게 `논리의 바닥'부터 공부하고자 하는 것은 몇 년 뒤로 미루는 것이 바람직하다. 수학의 논리 자체를 공부하는 학문을 `수학 기초론'이라 하는데 이는 수학의 기초를 제대로 공부한 후에 하는 것이 바람직하다.
7. 변수 $x$를 사용한 조건을 $p(x), q(x),\ldots$와 같이 문자를 사용하여 나타낸다. 때로는 절약정신을 발휘해 그냥 $p, q,\ldots$로 나타내기도 한다.