2회 · 증명과 집합의 언어#
이 회차
한 문장 |
이 강의에서 쓰는 논증의 형식과 집합 표기를 정리한다. |
출처 |
L0 |
파트 |
PART I — 무한을 담을 그릇 · 관통 질문: 넓이를 어떻게 정의할 것인가 |
짝 실험 |
앞 회차에서 아르키메데스의 논증을 살펴보았다. 그 논증은 “\(A\)가 \(b^3/3\)보다 크다고 하자. 그러면 모순이 생긴다”는 형태였다. 이런 형태의 논증을 귀류법(proof by contradiction)이라 한다.
이 강의에서는 이런 논증을 자주 쓴다. 넓이나 극한 같은 대상은 계산 규칙만으로는 다룰 수 없고, 정의로부터 성질을 하나씩 끌어내야 하기 때문이다. 그래서 논증의 형식을 먼저 정리해 둘 필요가 있다.
이번 회차에서는 집합(set)을 표기하는 방법, 명제와 그 부정을 쓰는 방법, 그리고 증명의 네 가지 형태를 정리해 보자.
1. 집합의 표기#
집합(set)을 적는 방법은 두 가지이다. 원소를 나열하거나, 원소가 만족할 조건을 제시한다.
(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\) — 원소가 하나도 없는 집합
두 집합이 같다는 것은 원소가 완전히 같다는 뜻이다. 이것을 포함 관계로 다시 쓰면 다음이 된다.
정의 1 (집합의 상등)
\(S \subseteq T\)이고 \(T \subseteq S\)일 때 두 집합이 같다고 하고 \(S = T\)라 쓴다.
정의 1는 정의인 동시에 증명의 절차이다. 두 집합이 같음을 보이려면 다음 두 가지를 각각 보여야 한다.
\(S\)의 임의의 원소를 하나 잡아 그것이 \(T\)에 속함을 보인다
\(T\)의 임의의 원소를 하나 잡아 그것이 \(S\)에 속함을 보인다
한쪽만 보이면 포함 관계를 보인 것이지 상등을 보인 것이 아니다. 이 강의에서 집합의 상등을 다룰 때는 언제나 이 두 단계를 나누어 적는다.
2. 명제와 그 부정#
참인지 거짓인지가 정해지는 문장을 명제(statement)라 한다. 명제 앞에 붙어서 “얼마나 많은 대상에 대하여 성립하는가”를 지정하는 것을 양화사(quantifier)라 한다. 양화사는 두 종류이다.
(2.2)의 왼쪽은 전칭명제(universal statement)로 “\(S\)의 모든 원소 \(x\)에 대하여 \(P(x)\)가 성립한다”고 읽는다. 오른쪽은 존재명제(existential statement)로 “\(P(x)\)가 성립하는 \(x\)가 \(S\) 안에 적어도 하나 있다”고 읽는다.
부정 규칙#
명제 \(P\)의 부정을 \(\neg P\)라 쓴다. 양화사가 붙은 명제의 부정은 다음 규칙을 따른다.
정리 2 (양화사의 부정)
(2.3)을 말로 옮기면 이렇다. “모든 \(x\)에 대하여 \(P(x)\)이다”가 거짓이라는 것은, \(P(x)\)가 성립하지 않는 \(x\)가 하나라도 있다는 뜻이다. 하나만 있으면 충분하다.
(2.4)도 마찬가지이다. “\(P(x)\)인 \(x\)가 있다”가 거짓이라는 것은, 어떤 \(x\)를 가져와도 \(P(x)\)가 성립하지 않는다는 뜻이다.
흔한 오해 — “모든”의 부정
“모든 \(x\)에 대하여 \(P(x)\)이다”의 부정을 “모든 \(x\)에 대하여 \(P(x)\)가 아니다”로 쓰는 경우가 있다. (2.3)에 따르면 부정은 “어떤 \(x\)에 대하여 \(P(x)\)가 아니다”이다.
두 문장은 전혀 다르다. “모든 정수가 짝수이다”의 부정은 “홀수인 정수가 하나라도 있다”이지 “모든 정수가 홀수이다”가 아니다. 앞은 참이고 뒤는 거짓이다.
흔한 오해 — 공집합에 대한 전칭명제
\(S = \varnothing\)일 때 \(\forall x \in \varnothing,\, P(x)\)는 참이다. \(P\)가 무엇이든 그렇다.
(2.3)으로 확인하자. 이 명제가 거짓이라면 \(\neg P(x)\)인 \(x\)가 \(\varnothing\) 안에 있어야 한다. 그런데 \(\varnothing\)에는 원소가 하나도 없으므로 그런 \(x\)는 없다. 따라서 부정이 거짓이고, 원래 명제는 참이다.
양화사의 순서#
양화사가 두 개 이상 나올 때 순서를 바꾸면 명제 자체가 달라진다. 다음 두 명제를 비교하자.
기호는 같은 것이 같은 개수만큼 쓰였고 순서만 다르다. 그런데 (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)를 차례로 적용하면
이다. (2.7)의 오른쪽은 참이다. \(y\)가 무엇으로 주어지든 \(x = y\)로 잡으면 \(x \ge y\)이기 때문이다. 부정이 참이므로 (2.6)은 거짓이다.
무엇이 먼저 주어지고 무엇을 뒤에 고르는가. 이것이 두 명제를 가르는 유일한 차이이다. 이 강의에서 양화사가 둘 이상인 명제를 다룰 때는 이 순서를 문장으로 매번 확인한다.
3. 증명의 형태#
증명해야 할 명제는 대개 “\(P\)이면 \(Q\)이다”라는 형태이며 \(P \Rightarrow Q\)라 쓴다. 이 형태를 다루는 방법이 네 가지 있다.
직접 증명#
\(P\)를 가정하고 거기서 \(Q\)를 끌어낸다.
예제 1 (직접 증명)
정수 \(n\)이 짝수이면 \(n^2\)도 짝수이다.
\(n\)이 짝수라고 하자. 그러면 \(n = 2m\)인 정수 \(m\)이 있다. 양변을 제곱하면
이다. \(2m^2\)이 정수이므로 \(n^2\)은 \(2\)의 배수이다. 따라서 \(n^2\)은 짝수이다.
대우 증명#
\(P \Rightarrow Q\) 대신 \(\neg Q \Rightarrow \neg P\)를 보인다. 이 명제를 원명제의 대우(contrapositive)라 하며, 대우는 원명제와 동치이다. 즉 둘 중 하나가 참이면 다른 하나도 참이다.
예제 2 (대우 증명)
정수 \(n\)에 대하여 \(n^2\)이 짝수이면 \(n\)도 짝수이다.
\(P\)는 “\(n^2\)이 짝수이다”이고 \(Q\)는 “\(n\)이 짝수이다”이다. 대우 \(\neg Q \Rightarrow \neg P\)는 “\(n\)이 홀수이면 \(n^2\)도 홀수이다”이다. 이것을 보인다.
\(n\)이 홀수라고 하자. 그러면 \(n = 2m + 1\)인 정수 \(m\)이 있다. 양변을 제곱하면
이다. \(2m^2 + 2m\)이 정수이므로 \(n^2\)은 홀수이다. 대우가 참이므로 원명제도 참이다.
흔한 오해 — 대우와 역
\(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\)가 성립한다.
예제 3 (귀류법)
양의 정수 중 가장 큰 것은 없다.
가장 큰 양의 정수가 있다고 하자. 그것을 \(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)라 한다.
예제 4 (반례에 의한 반박)
“모든 음이 아닌 정수 \(n\)에 대하여 \(n^2 + n + 41\)은 소수이다”는 거짓이다.
\(n = 40\)을 넣으면
이다. \(1681\)은 \(41\)로 나누어떨어지므로 소수가 아니다. 따라서 주어진 전칭명제는 거짓이다.
예제 4에서 \(n = 0\)부터 \(n = 39\)까지는 모두 소수가 나온다. 마흔 번을 확인해도 참이 되지 않는다. 전칭명제를 참이라고 주장하려면 확인이 아니라 증명이 필요하다.
4. 함수 표기#
함수를 \(f : A \to B\)와 같이 쓴다. \(A\)를 정의역(domain), \(B\)를 공역(codomain)이라 한다. \(A\)의 원소 \(x\)에 대응하는 \(B\)의 원소를 \(f(x)\)라 쓴다.
정의역의 원소가 옮겨 간 값을 모두 모은 집합
을 치역(range)이라 한다. (2.8)에서 보듯 치역은 공역의 부분집합이며, 공역과 같을 필요는 없다. 예를 들어 \(f : \R \to \R\), \(f(x) = x^2\)의 공역은 \(\R\)이지만 치역은 \(0\) 이상의 실수 전체이다.
두 함수가 같다는 것은 다음을 뜻한다.
정의 2 (함수의 상등)
\(f\)와 \(g\)의 정의역이 같고, 정의역의 모든 원소 \(x\)에 대하여 \(f(x) = g(x)\)일 때 \(f = g\)라 쓴다.
정의 2에서 정의역이 같아야 한다는 조건이 빠지지 않는다. 대응 규칙을 적는 식이 같더라도 정의역이 다르면 다른 함수이다. \(f : \R \to \R\), \(f(x) = x^2\)과 \(g : \{x \in \R : x \ge 0\} \to \R\), \(g(x) = x^2\)은 서로 다른 함수이다.
여기서는 표기만 정한다. 함수라는 것이 무엇인지를 집합을 써서 정의하는 일은 아직 하지 않는다.
마치며#
이번 회차에서는 집합의 표기, 명제의 부정, 증명의 네 가지 형태를 정리하였다. 특히 양화사가 두 개 이상일 때 순서가 바뀌면 명제 자체가 달라진다는 것을 확인하였다.
여기까지가 논증의 도구이다. 이제 논증의 대상을 정해야 한다. 우리가 다루려는 수는 어떤 수인가.
다음 회차에서는 실수(real number)가 만족하는 공리를 알아보도록 하자.
이어서
같은 회차의 실험: 2회 실험 · 양화사의 순서