증명 도구 상자 · 노트

2 T2 대우와 귀류, 반례

정리는 대개 “$p$이면 $q$이다”의 꼴이다. $p$에서 $q$로 바로 가는 길이 보이지 않으면 대우를 증명하거나, $q$가 거짓이라고 가정해 모순을 끌어낸다. 거꾸로 “모든 경우에 성립한다”는 주장은 반례 하나로 깨진다. 1회 정리 7.1(“자연수 위의 균등 확률은 없다”)과 1회 예제 5.10(Bernstein의 정사면체)이 이 절의 두 방법이다.

2.1 조건문과 대우

정의 2.1 (역 · 이 · 대우) 조건문 $p\Rightarrow q$에 대해 $q\Rightarrow p$를 역, $\neg p\Rightarrow\neg q$를 이, $\neg q\Rightarrow\neg p$를 대우(contrapositive)라 한다.

명제 2.2 (대우는 같은 명제다) $p\Rightarrow q$와 $\neg q\Rightarrow\neg p$는 참·거짓이 같다. 역과 이는 원래 명제와 참·거짓이 다를 수 있다.

증명 전략 $p\Rightarrow q$가 거짓인 경우는 “$p$가 참이고 $q$가 거짓”뿐이다. 두 명제가 거짓이 되는 경우를 비교한다.

1. $p\Rightarrow q$가 거짓 $\iff$ $p$ 참, $q$ 거짓.조건문의 정의

2. $\neg q\Rightarrow\neg p$가 거짓 $\iff$ $\neg q$ 참, $\neg p$ 거짓 $\iff$ $q$ 거짓, $p$ 참.1을 $\neg q$, $\neg p$에 쓴다

3. 거짓이 되는 경우가 같으므로 참·거짓이 같다. 역 $q\Rightarrow p$는 $p$ 거짓, $q$ 참일 때 거짓이어서 원래 명제와 다르다.1 2

예제 2.3 (제곱이 짝수이면) 주장. 정수 $n$에서 $n^2$이 짝수이면 $n$은 짝수다. 직접 가면 $n^2=2m$에서 $n$을 끌어내야 해서 막힌다. 대우 “$n$이 홀수이면 $n^2$은 홀수”는 한 줄이다. $n=2k+1$이면 $n^2=2(2k^2+2k)+1$이다.

확률에서도 같다. “$A\subset B$이고 $P(A)>0$이면 $P(B)>0$”의 대우는 “$A\subset B$이고 $P(B)=0$이면 $P(A)=0$”이고, 이것은 단조성 $P(A)\le P(B)$에서 바로 나온다.

2.2 양화사의 부정

“모든”($\forall$)과 “어떤”($\exists$)이 들어간 문장의 부정은 양화사를 바꾸고 안쪽을 부정한다.

$$\neg\bigl(\forall x\ P(x)\bigr)\iff\exists x\ \neg P(x),\qquad \neg\bigl(\exists x\ P(x)\bigr)\iff\forall x\ \neg P(x).$$

여러 겹이면 바깥부터 한 겹씩 바꾼다.

예제 2.4 (수렴하지 않는다) $a_n\to a$의 정의([T5])는 “$\forall\varepsilon>0\ \exists N\ \forall n\ge N:\ |a_n-a|<\varepsilon$”이다. 한 겹씩 부정하면

$$a_n\not\to a\iff\exists\varepsilon>0\ \forall N\ \exists n\ge N:\ |a_n-a|\ge\varepsilon .$$

곧 어떤 $\varepsilon$에 대해 $|a_n-a|\ge\varepsilon$인 $n$이 끝없이 나온다. 수렴하지 않음을 보이려면 그런 $\varepsilon$ 하나를 찾아 주면 된다.

2.3 귀류법

귀류법(proof by contradiction)은 결론 $q$가 거짓이라고 가정하고, 가정이나 이미 아는 사실과 어긋나는 결론을 끌어낸다. 그러면 $q$가 거짓일 수 없으므로 $q$는 참이다. 대우로 충분한 경우에는 대우로 쓰는 편이 읽기 쉽다. 귀류법은 결론이 “없다”, “유한하지 않다”, “유리수가 아니다”처럼 부정의 꼴일 때 많이 쓴다.

정리 2.5 ($\sqrt2$는 무리수다) $\sqrt2$를 두 정수의 비로 쓸 수 없다.

증명 전략 기약분수로 썼다고 가정하고, 분자와 분모가 모두 짝수임을 보여 기약이라는 가정과 충돌시킨다.

1. $\sqrt2=a/b$이고 $a,b$는 공약수가 1뿐인 양의 정수라고 가정한다.귀류 가정

2. $a^2=2b^2$이므로 $a^2$은 짝수이고, 따라서 $a$는 짝수다. $a=2c$로 쓴다.예제 2.3

3. $4c^2=2b^2$, 곧 $b^2=2c^2$이므로 $b$도 짝수다.예제 2.3

4. $a,b$가 공약수 2를 가지므로 1과 모순이다.1 2 3

정리 2.6 (소수는 무한히 많다 (Euclid)) 소수의 개수는 유한하지 않다.

증명 전략 소수가 유한개라고 가정하고, 그 어느 것으로도 나누어지지 않는 1보다 큰 수를 만든다.

1. 소수가 $p_1,\dots,p_m$뿐이라고 가정한다.귀류 가정

2. $N=p_1p_2\cdots p_m+1$로 둔다. $N$을 어느 $p_i$로 나누어도 나머지는 1이다.구성

3. $N\ge2$이므로 $N$은 어떤 소수로 나누어진다. 그 소수는 $p_1,\dots,p_m$ 가운데 없다.소인수의 존재 [T3]

4. 1과 모순이다.

예제 2.7 (자연수 위의 균등 확률) 1회 정리 7.1은 귀류법이다. $P(\{n\})=c$인 확률이 있다고 가정하면, 가산가법성으로 $1=\sum_nc$이다. 오른쪽은 $c=0$이면 0이고 $c>0$이면 발산한다. 어느 쪽이든 1이 아니므로 가정이 거짓이다. 경우를 나누어 모두 모순임을 보이는 것도 귀류법의 흔한 꼴이다.

2.4 반례

“모든 $x$에서 $P(x)$”는 $P(x)$가 거짓인 $x$ 하나, 곧 반례로 거짓이 된다. 반례는 작게 만든다. 원소가 두세 개인 표본공간, 두 점에 몰린 분포, $n=1$이나 $n=2$가 첫 후보다.

예제 2.8 (쌍별 독립과 상호 독립) “세 사건이 쌍마다 독립이면 상호 독립이다”는 거짓이다. 1회 예제 5.10의 Bernstein 정사면체가 반례다. 네 면 가운데 세 면에 빨강·초록·파랑을 하나씩, 넷째 면에 세 색을 모두 칠하면 $P(R)=P(G)=P(B)=\tfrac12$, 두 색이 함께 있을 확률은 모두 $\tfrac14$이지만 $P(RGB)=\tfrac14\ne\tfrac18$이다. 표본공간의 원소가 넷뿐이어서 손으로 모든 경우를 확인할 수 있다.

흔한 실수 (1) 역을 증명하고 원래 명제를 증명했다고 여긴다. “$X$와 $Y$가 독립이면 공분산이 0”의 역은 거짓이다($X$가 $\{-1,0,1\}$ 위의 균등분포이고 $Y=X^2$이면 공분산은 0이지만 독립이 아니다). (2) 예를 여럿 확인하고 증명했다고 여긴다. $n^2+n+41$은 $n=0,1,\dots,39$에서 모두 소수이지만 $n=40$이면 $1681=41^2$이다. (3) 귀류 가정을 쓰지 않고 모순을 끌어낸다. 그런 “모순”은 가정과 무관하게 나온 것이므로 처음부터 계산이 틀렸다는 뜻이다.

연습문제

연습 2.1 (대우로 증명하기 ★) 정수 $n$에서 $n^2$이 3의 배수이면 $n$도 3의 배수임을 대우로 보여라.

풀이

대우 “$3\nmid n$이면 $3\nmid n^2$”을 보인다. $n=3k+1$이면 $n^2=3(3k^2+2k)+1$, $n=3k+2$이면 $n^2=3(3k^2+4k+1)+1$이다. 어느 경우든 나머지가 1이다.

연습 2.2 (부정 쓰기 ★) 다음 문장의 부정을 양화사를 바꿔 써라. (a) 모든 $\varepsilon>0$에 대해 어떤 $N$이 있어 $n\ge N$이면 $|a_n|<\varepsilon$이다. (b) 함수 $F$는 비감소다($x<y\Rightarrow F(x)\le F(y)$). (c) 사건 $A_1,A_2,A_3$은 상호 독립이다.

풀이

(a) 어떤 $\varepsilon>0$이 있어, 모든 $N$에 대해 $|a_n|\ge\varepsilon$인 $n\ge N$이 있다. (b) $x<y$이면서 $F(x)>F(y)$인 $x,y$가 있다. (c) 상호 독립은 네 등식 $P(A_1A_2)=P(A_1)P(A_2)$, $P(A_1A_3)=P(A_1)P(A_3)$, $P(A_2A_3)=P(A_2)P(A_3)$, $P(A_1A_2A_3)=P(A_1)P(A_2)P(A_3)$이 모두 성립한다는 것이다. 부정은 이 가운데 적어도 하나가 성립하지 않는다는 것이다.

연습 2.3 ($\sqrt3$은 무리수다 ★) 연습 2.1을 써서 $\sqrt3$이 무리수임을 귀류법으로 보여라.

풀이

$\sqrt3=a/b$, $a,b$는 공약수가 1뿐인 양의 정수라 하자. $a^2=3b^2$이므로 $3\mid a^2$이고, 연습 2.1으로 $3\mid a$이다. $a=3c$를 넣으면 $b^2=3c^2$이므로 같은 이유로 $3\mid b$이다. 공약수 3이 생기므로 모순이다.

연습 2.4 ($\log_23$은 무리수다 ★★) $\log_23$이 무리수임을 보여라. (힌트: $\log_23=a/b$이면 $3^b=2^a$이다.)

풀이

$\log_23>0$이다. $\log_23=a/b$인 양의 정수 $a,b$가 있으면 $2^{a/b}=3$이므로 $2^a=3^b$이다. 왼쪽은 짝수($a\ge1$)이고 오른쪽은 홀수이므로 모순이다.

연습 2.5 (확률의 합이 1보다 작으면 ★★) 사건 $A_1,\dots,A_n$에서 $\sum_iP(A_i)<1$이면 $P(A_1^c\cap\cdots\cap A_n^c)>0$임을 보여라. 따라서 $A_1\cup\cdots\cup A_n\ne\Omega$이다. 이것을 “$A_1\cup\cdots\cup A_n=\Omega$이면 $\sum_iP(A_i)\ge1$”의 대우로 읽어라.

풀이

De Morgan과 Boole 부등식으로

$$P(A_1^c\cap\cdots\cap A_n^c)=1-P(A_1\cup\cdots\cup A_n)\ge1-\sum_iP(A_i)>0 .$$

$A_1\cup\cdots\cup A_n=\Omega$이면 왼쪽은 $P(\emptyset)=0$이므로 모순이다. 대우로 읽으면, 합집합이 $\Omega$이면 $1=P(\bigcup A_i)\le\sum P(A_i)$이다. 대우 쪽이 Boole 부등식 한 줄이어서 더 짧다.

연습 2.6 (반례 만들기 ★★) (a) $A$와 $B$가 독립이고 $B$와 $C$가 독립이지만 $A$와 $C$는 독립이 아닌 예를 들어라. (b) $P(A\mid B)>P(A)$이고 $P(B\mid C)>P(B)$이지만 $P(A\mid C)<P(A)$인 예를 원소가 세 개인 표본공간에서 들어라.

풀이

(a) 공정한 동전을 두 번 던지고 $A=C=\{$첫째가 앞면$\}$, $B=\{$둘째가 앞면$\}$이라 하자. $A$와 $B$, $B$와 $C$는 독립이다. 그러나 $P(A\cap C)=P(A)=\tfrac12\ne\tfrac14=P(A)P(C)$이다. (b) $\Omega=\{1,2,3\}$ 위의 균등 확률에서 $A=\{1\}$, $B=\{1,2\}$, $C=\{2\}$로 두면 $P(A\mid B)=\tfrac12>\tfrac13$, $P(B\mid C)=1>\tfrac23$, $P(A\mid C)=0<\tfrac13$이다. 양의 연관은 이어지지 않는다.

연습 2.7 ($4k+3$ 꼴의 소수 ★★) $4k+3$ 꼴의 소수가 무한히 많음을 보여라. (힌트: 그런 소수가 $p_1,\dots,p_m$뿐이면 $N=4p_1\cdots p_m-1$을 본다. $4k+1$ 꼴인 수들의 곱은 $4k+1$ 꼴이다.)

풀이

3은 $4k+3$ 꼴이므로 그런 소수가 있다. 그런 소수가 $p_1,\dots,p_m$뿐이라 하고 $N=4p_1\cdots p_m-1$로 두자. $N\ge11$이고 홀수이며 $N\equiv3\pmod4$이다. $N$의 소인수는 모두 홀수다. 모두 $4k+1$ 꼴이면 $(4a+1)(4b+1)=4(4ab+a+b)+1$을 되풀이해 $N\equiv1\pmod4$가 되므로, $4k+3$ 꼴인 소인수 $q$가 있다. 가정으로 $q$는 어떤 $p_i$이므로 $q\mid4p_1\cdots p_m$이고 $q\mid N$이어서 $q\mid1$이다. 모순이다.

연습 2.8 (한 점의 확률 ★★) (a) $[0,1]$의 모든 한 점 집합에 같은 양수 확률 $c$를 주는 확률은 없음을 귀류법으로 보여라. (b) 실수 위의 확률 $P$가 모든 $x$에서 $P(\{x\})=0$이면 $P(\Q)=0$임을 보여라. 같은 논리로 $P([0,1])$이 모든 점의 확률의 합이 아닌 이유를 설명하라.

풀이

(a) $P(\{x\})=c>0$이 모든 $x\in[0,1]$에서 성립한다고 하자. $n>1/c$인 $n$과 서로 다른 점 $x_1,\dots,x_n$을 고르면 유한가법성으로 $P(\{x_1,\dots,x_n\})=nc>1$이므로 모순이다. (b) $\Q=\{q_1,q_2,\dots\}$로 늘어놓을 수 있으므로 가산가법성으로 $P(\Q)=\sum_iP(\{q_i\})=0$이다. $[0,1]$은 셀 수 없으므로 점들로 나눈 분할에 가산가법성을 쓸 수 없다. 공리는 셀 수 있는 합만 허락한다. 그래서 $\mathrm U(0,1)$처럼 모든 점의 확률이 0이면서 $P([0,1])=1$인 확률이 모순 없이 있다.

이 절을 PDF로 보기 (4쪽)

이 회차에서 읽은 절 0개 · 회차 차례