# 2회 · 증명과 집합의 언어

```{admonition} 이 회차
:class: seealso

| | |
|---|---|
| **한 문장** | 이 강의에서 쓰는 논증의 형식과 집합 표기를 정리한다. |
| **출처** | L0 |
| **파트** | PART I — 무한을 담을 그릇 · 관통 질문: 넓이를 어떻게 정의할 것인가 |
| **짝 실험** | {doc}`L02_lab` |
```

앞 회차에서 아르키메데스의 논증을 살펴보았다. 그 논증은 "$A$가 $b^3/3$보다 크다고 하자. 그러면 모순이 생긴다"는 형태였다. 이런 형태의 논증을 귀류법(proof by contradiction)이라 한다.

이 강의에서는 이런 논증을 자주 쓴다. 넓이나 극한 같은 대상은 계산 규칙만으로는 다룰 수 없고, 정의로부터 성질을 하나씩 끌어내야 하기 때문이다. 그래서 논증의 형식을 먼저 정리해 둘 필요가 있다.

이번 회차에서는 집합(set)을 표기하는 방법, 명제와 그 부정을 쓰는 방법, 그리고 증명의 네 가지 형태를 정리해 보자.

## 1. 집합의 표기

집합(set)을 적는 방법은 두 가지이다. 원소를 나열하거나, 원소가 만족할 조건을 제시한다.

$$
\{1,\, 2,\, 3\},
\qquad
\{\, x \in \R \;:\; x^2 < 2 \,\}
\tag{2.1}
$$

(2.1)의 왼쪽이 나열이고 오른쪽이 조건 제시이다. 오른쪽은 "실수 $x$ 중에서 $x^2 < 2$를 만족하는 것을 모두 모은 집합"이라고 읽는다. 쌍점 앞이 원소가 어디서 오는지를 밝히고, 쌍점 뒤가 조건이다.

$x$가 집합 $S$의 원소이면 $x \in S$라 쓰고, 원소가 아니면 $x \notin S$라 쓴다.

집합 사이의 관계와 연산은 다음과 같이 쓴다.

- **포함(inclusion)** $S \subseteq T$ — $S$의 모든 원소가 $T$의 원소이다
- **합집합(union)** $S \cup T$ — $S$에 속하거나 $T$에 속하는 원소를 모두 모은 집합
- **교집합(intersection)** $S \cap T$ — $S$와 $T$ 양쪽 모두에 속하는 원소를 모은 집합
- **차집합(difference)** $S \setminus T$ — $S$에 속하고 $T$에는 속하지 않는 원소를 모은 집합
- **공집합(empty set)** $\varnothing$ — 원소가 하나도 없는 집합

두 집합이 같다는 것은 원소가 완전히 같다는 뜻이다. 이것을 포함 관계로 다시 쓰면 다음이 된다.

```{prf:definition} 집합의 상등
:label: def-2-set-equality

$S \subseteq T$이고 $T \subseteq S$일 때 두 집합이 같다고 하고 $S = T$라 쓴다.
```

{prf:ref}`def-2-set-equality`는 정의인 동시에 증명의 절차이다. 두 집합이 같음을 보이려면 다음 두 가지를 **각각** 보여야 한다.

1. $S$의 임의의 원소를 하나 잡아 그것이 $T$에 속함을 보인다
2. $T$의 임의의 원소를 하나 잡아 그것이 $S$에 속함을 보인다

한쪽만 보이면 포함 관계를 보인 것이지 상등을 보인 것이 아니다. 이 강의에서 집합의 상등을 다룰 때는 언제나 이 두 단계를 나누어 적는다.

## 2. 명제와 그 부정

참인지 거짓인지가 정해지는 문장을 명제(statement)라 한다. 명제 앞에 붙어서 "얼마나 많은 대상에 대하여 성립하는가"를 지정하는 것을 양화사(quantifier)라 한다. 양화사는 두 종류이다.

$$
\forall x \in S,\; P(x)
\qquad\text{---}\qquad
\exists x \in S,\; P(x)
\tag{2.2}
$$

(2.2)의 왼쪽은 전칭명제(universal statement)로 "$S$의 모든 원소 $x$에 대하여 $P(x)$가 성립한다"고 읽는다. 오른쪽은 존재명제(existential statement)로 "$P(x)$가 성립하는 $x$가 $S$ 안에 적어도 하나 있다"고 읽는다.

### 부정 규칙

명제 $P$의 부정을 $\neg P$라 쓴다. 양화사가 붙은 명제의 부정은 다음 규칙을 따른다.

```{prf:theorem} 양화사의 부정
:label: thm-2-negation

$$
\neg\bigl(\forall x \in S,\; P(x)\bigr)
\iff
\exists x \in S,\; \neg P(x)
\tag{2.3}
$$

$$
\neg\bigl(\exists x \in S,\; P(x)\bigr)
\iff
\forall x \in S,\; \neg P(x)
\tag{2.4}
$$
```

(2.3)을 말로 옮기면 이렇다. "모든 $x$에 대하여 $P(x)$이다"가 거짓이라는 것은, $P(x)$가 성립하지 않는 $x$가 하나라도 있다는 뜻이다. 하나만 있으면 충분하다.

(2.4)도 마찬가지이다. "$P(x)$인 $x$가 있다"가 거짓이라는 것은, 어떤 $x$를 가져와도 $P(x)$가 성립하지 않는다는 뜻이다.

```{admonition} 흔한 오해 — "모든"의 부정
:class: caution

"모든 $x$에 대하여 $P(x)$이다"의 부정을 "모든 $x$에 대하여 $P(x)$가 아니다"로 쓰는 경우가 있다. (2.3)에 따르면 부정은 "**어떤** $x$에 대하여 $P(x)$가 아니다"이다.

두 문장은 전혀 다르다. "모든 정수가 짝수이다"의 부정은 "홀수인 정수가 하나라도 있다"이지 "모든 정수가 홀수이다"가 아니다. 앞은 참이고 뒤는 거짓이다.
```

```{admonition} 흔한 오해 — 공집합에 대한 전칭명제
:class: caution

$S = \varnothing$일 때 $\forall x \in \varnothing,\, P(x)$는 **참**이다. $P$가 무엇이든 그렇다.

(2.3)으로 확인하자. 이 명제가 거짓이라면 $\neg P(x)$인 $x$가 $\varnothing$ 안에 있어야 한다. 그런데 $\varnothing$에는 원소가 하나도 없으므로 그런 $x$는 없다. 따라서 부정이 거짓이고, 원래 명제는 참이다.
```

### 양화사의 순서

양화사가 두 개 이상 나올 때 **순서를 바꾸면 명제 자체가 달라진다.** 다음 두 명제를 비교하자.

$$
\forall x \in \R,\; \exists y \in \R,\; x < y
\tag{2.5}
$$

$$
\exists y \in \R,\; \forall x \in \R,\; x < y
\tag{2.6}
$$

기호는 같은 것이 같은 개수만큼 쓰였고 순서만 다르다. 그런데 **(2.5)는 참이고 (2.6)은 거짓이다.**

(2.5)에서는 $x$가 먼저 주어지고 $y$를 그 뒤에 고른다. 따라서 $y$는 $x$에 의존해도 된다. 실제로 $x$가 무엇으로 주어지든 $y = x + 1$로 잡으면 $x < y$가 성립한다. 그러므로 (2.5)는 참이다.

(2.6)에서는 $y$를 먼저 고정한다. 그 하나의 $y$가 모든 $x$에 대하여 $x < y$를 만족해야 한다. 그런데 어떤 $y$를 고정하더라도 $x = y$로 두면 $x < y$가 거짓이 된다. 그러므로 (2.6)은 거짓이다.

(2.6)이 거짓임을 부정 규칙으로 다시 확인할 수 있다. (2.3)과 (2.4)를 차례로 적용하면

$$
\neg\bigl(\exists y \in \R,\; \forall x \in \R,\; x < y\bigr)
\iff
\forall y \in \R,\; \exists x \in \R,\; x \ge y
\tag{2.7}
$$

이다. (2.7)의 오른쪽은 참이다. $y$가 무엇으로 주어지든 $x = y$로 잡으면 $x \ge y$이기 때문이다. 부정이 참이므로 (2.6)은 거짓이다.

**무엇이 먼저 주어지고 무엇을 뒤에 고르는가.** 이것이 두 명제를 가르는 유일한 차이이다. 이 강의에서 양화사가 둘 이상인 명제를 다룰 때는 이 순서를 문장으로 매번 확인한다.

## 3. 증명의 형태

증명해야 할 명제는 대개 "$P$이면 $Q$이다"라는 형태이며 $P \Rightarrow Q$라 쓴다. 이 형태를 다루는 방법이 네 가지 있다.

### 직접 증명

$P$를 가정하고 거기서 $Q$를 끌어낸다.

```{prf:example} 직접 증명
:label: ex-2-direct

**정수 $n$이 짝수이면 $n^2$도 짝수이다.**

$n$이 짝수라고 하자. 그러면 $n = 2m$인 정수 $m$이 있다. 양변을 제곱하면

$$
n^2 = (2m)^2 = 4m^2 = 2\,(2m^2)
$$

이다. $2m^2$이 정수이므로 $n^2$은 $2$의 배수이다. 따라서 $n^2$은 짝수이다.
```

### 대우 증명

$P \Rightarrow Q$ 대신 $\neg Q \Rightarrow \neg P$를 보인다. 이 명제를 원명제의 대우(contrapositive)라 하며, 대우는 원명제와 동치이다. 즉 둘 중 하나가 참이면 다른 하나도 참이다.

```{prf:example} 대우 증명
:label: ex-2-contrapositive

**정수 $n$에 대하여 $n^2$이 짝수이면 $n$도 짝수이다.**

$P$는 "$n^2$이 짝수이다"이고 $Q$는 "$n$이 짝수이다"이다. 대우 $\neg Q \Rightarrow \neg P$는 "$n$이 홀수이면 $n^2$도 홀수이다"이다. 이것을 보인다.

$n$이 홀수라고 하자. 그러면 $n = 2m + 1$인 정수 $m$이 있다. 양변을 제곱하면

$$
n^2 = 4m^2 + 4m + 1 = 2\,(2m^2 + 2m) + 1
$$

이다. $2m^2 + 2m$이 정수이므로 $n^2$은 홀수이다. 대우가 참이므로 원명제도 참이다.
```

```{admonition} 흔한 오해 — 대우와 역
:class: caution

$P \Rightarrow Q$에 대하여 대우는 $\neg Q \Rightarrow \neg P$이고 역(converse)은 $Q \Rightarrow P$이다. **대우는 원명제와 동치이지만 역은 그렇지 않다.**

다음 예에서 확인하자. $P$를 "$n$이 $4$의 배수이다", $Q$를 "$n$이 짝수이다"라 두자.

| | 명제 | 참·거짓 |
|---|---|---|
| 원명제 | $n$이 $4$의 배수이면 $n$은 짝수이다 | 참 |
| 대우 | $n$이 짝수가 아니면 $n$은 $4$의 배수가 아니다 | 참 |
| 역 | $n$이 짝수이면 $n$은 $4$의 배수이다 | **거짓** |

역이 거짓인 것은 $n = 2$가 보여 준다. $2$는 짝수이지만 $4$의 배수가 아니다.
```

### 귀류법

$P$를 가정하고 여기에 $\neg Q$를 더 가정한 다음, 모순을 끌어낸다. 모순이 나왔으므로 $\neg Q$가 성립할 수 없고, 따라서 $Q$가 성립한다.

```{prf:example} 귀류법
:label: ex-2-contradiction

**양의 정수 중 가장 큰 것은 없다.**

가장 큰 양의 정수가 있다고 하자. 그것을 $N$이라 쓴다. $N$이 양의 정수이므로 $N + 1$도 양의 정수이고 $N + 1 > N$이다. 그런데 $N$은 가장 큰 양의 정수였으므로 $N + 1 \le N$이어야 한다. 두 부등식이 동시에 성립할 수 없으므로 모순이다.

따라서 가장 큰 양의 정수는 없다.
```

1회 3절에서 넓이 $A$가 $b^3/3$임을 보인 논증도 이 형태였다. $A \ne b^3/3$을 가정하고, $A > b^3/3$인 경우와 $A < b^3/3$인 경우 각각에서 모순을 끌어냈다.

### 반례에 의한 반박

전칭명제 $\forall x \in S,\, P(x)$가 거짓임을 보이는 일은 증명이 아니라 반박이다. (2.3)에 따르면 $\neg P(x)$인 $x$를 **하나만** 제시하면 된다. 그런 $x$를 반례(counterexample)라 한다.

```{prf:example} 반례에 의한 반박
:label: ex-2-counterexample

**"모든 음이 아닌 정수 $n$에 대하여 $n^2 + n + 41$은 소수이다"는 거짓이다.**

$n = 40$을 넣으면

$$
40^2 + 40 + 41 = 1600 + 40 + 41 = 1681 = 41^2
$$

이다. $1681$은 $41$로 나누어떨어지므로 소수가 아니다. 따라서 주어진 전칭명제는 거짓이다.
```

{prf:ref}`ex-2-counterexample`에서 $n = 0$부터 $n = 39$까지는 모두 소수가 나온다. 마흔 번을 확인해도 참이 되지 않는다. 전칭명제를 참이라고 주장하려면 확인이 아니라 증명이 필요하다.

## 4. 함수 표기

함수를 $f : A \to B$와 같이 쓴다. $A$를 정의역(domain), $B$를 공역(codomain)이라 한다. $A$의 원소 $x$에 대응하는 $B$의 원소를 $f(x)$라 쓴다.

정의역의 원소가 옮겨 간 값을 모두 모은 집합

$$
f(A) = \{\, f(x) \;:\; x \in A \,\}
\tag{2.8}
$$

을 치역(range)이라 한다. (2.8)에서 보듯 치역은 공역의 부분집합이며, 공역과 같을 필요는 없다. 예를 들어 $f : \R \to \R$, $f(x) = x^2$의 공역은 $\R$이지만 치역은 $0$ 이상의 실수 전체이다.

두 함수가 같다는 것은 다음을 뜻한다.

```{prf:definition} 함수의 상등
:label: def-2-function-equality

$f$와 $g$의 정의역이 같고, 정의역의 모든 원소 $x$에 대하여 $f(x) = g(x)$일 때 $f = g$라 쓴다.
```

{prf:ref}`def-2-function-equality`에서 정의역이 같아야 한다는 조건이 빠지지 않는다. 대응 규칙을 적는 식이 같더라도 정의역이 다르면 다른 함수이다. $f : \R \to \R$, $f(x) = x^2$과 $g : \{x \in \R : x \ge 0\} \to \R$, $g(x) = x^2$은 서로 다른 함수이다.

여기서는 표기만 정한다. 함수라는 것이 무엇인지를 집합을 써서 정의하는 일은 아직 하지 않는다.

## 마치며

이번 회차에서는 집합의 표기, 명제의 부정, 증명의 네 가지 형태를 정리하였다. 특히 양화사가 두 개 이상일 때 순서가 바뀌면 명제 자체가 달라진다는 것을 확인하였다.

여기까지가 논증의 도구이다. 이제 논증의 대상을 정해야 한다. 우리가 다루려는 수는 어떤 수인가.

다음 회차에서는 실수(real number)가 만족하는 공리를 알아보도록 하자.

```{admonition} 이어서
:class: note
같은 회차의 실험: {doc}`L02_lab`
```