[수학] 수학적 증명 방법

 수학 공부를 할 때마다 증명 문제를 많이 마주하게 되는데 그럴 때마다 증명에 대한 체계가 없어서 이번에 겸사겸사 정리한다.

 

 

1. 논리 기호 표시

 

• $\neg$ 또는 $\thicksim$ : not
• $\wedge$ : and
• $\vee$ : or
• $\bot$ : a logical contradiction or a false statement (a statement which truth value is false).

$\neg p \rightarrow \bot$ 은 곧 $p$가 참이라는 뜻이다.

 

2. 직접 증명 Direct proof

 

일반적인 수학책에서 다루는 것처럼 정의(definition), 공리(axiom), 정리(theorem)를 이용해서 증명하는 방법

 

3. 수학적 귀납법 proof by induction

 

 

1. $n = n_{0}$일 때 성립함을 보인다.

2. $n=k$에서 성립할 때, $n=k+1$일 때도 성립함을 보인다.

3. $n\geq n_{0}$도 성립한다. 

 

 

4. 간접 증명법

4-1. 반례증명법 proof by counter example

명제가 거짓임을 밝히기 위해서는 거짓인 사례(반례) 하나를 제시하여 증명한다.

 

 

4-2. 대우증명법 proof by contraposition

 

Conditional statement $P \Rightarrow Q$ 일 때

contraposition인 $\neg Q \Rightarrow \neg P$와 논리적으로 동치이므로 contraposition으로 바꿔서 증명할 수 있다.

 

참고

역 converse $Q \Rightarrow P$

이 inverse $\neg P \Rightarrow \neg Q$

대우 contraposition $\neg Q \Rightarrow \neg P$

 

4-3. 모순증명법 (귀류법) proof by contradiction

 

명제의 가정은 참이고, 결론이 거짓이라고 가정했을 때, 가정이 거짓임을 밝힘으로써 명제가 참임을 증명하는 방법.

가정이 참이라고 했지만, 결론을 기반으로 추론했을 때는 가정이 거짓이기 때문에 모순(contradiction)이 발생한다. 따라서 이 증명을 모순증명법(귀류법; 돌아갈 귀, 그르칠 류)이라고 한다.

 

정확한 방법론을 기호로 표현하고자 한다.

첫 번째로 이야기할 것은 일반적인 statement(preposition) P를 증명하는 과정이다.

 

Statement이자 preposition을 P이 참임을 증명하고 싶다고 하자. 그리고 증명과정에서 부수적으로 나오는 statement $C$와, $\neg C$가 동시에 성립해야하는 상황을 만든다. 이 때 $C\wedge \neg C$ (C and not C)인 경우는 무조건 FALSE라는 사실을 기억하자.

 

논리표

다음 표를 보면, $P$와 $(~P)\Rightarrow (C\wedge \neg C)$은 논리적으로 동일하다. 즉, $(\neg P)\Rightarrow (C\wedge \neg C)$가 참임을 보이면 $P$도 참이 되는 것이고, $(\neg P)\Rightarrow (C\wedge \neg C)$가 거짓임을 보이면 $P$도 거짓이 된다. 주의할 점은 $(\neg P)\Rightarrow (C\wedge \neg C)$이 참이라는 뜻이 $(C\wedge \neg C)$이 참이라는 것과는 전혀 다르다.

 

예를 들어

 

$\textbf{Preposition }\quad \text{If } a,b \in \mathbb{Z}\text{, then }a^{2}-4b\neq 2$

 

이 명제를 증명하기 까다로워서 귀류법을 써보기로 한다.

preposition을 부정하면 아래 statement의 negation 표를 참고하여, 다음과 같이 기술할 수 있다.

$\text{If }a,b \in \mathbb{Z}\text{, then }a^{2}-4b = 2$

이 경우에 $a^{2}=4b+2=2(2b+1)$이므로 $a^{2}$은 짝수가 되어야 한다.

 

따라서 $a$는 짝수여야하므로 $a=2c\text{, where }c\in \mathbb{Z}$라고 할 수 있다.

그런데 $4c^{2}=4b+2 \quad \Rightarrow 2(c^{2}-b)=1$이라는 결론이 된다.

$c^{2}-b \in \mathbb{Z}$이므로 1이 짝수라는 모순이 생긴다. ($2(c^{2}-b)=1$식만 그대로 받아들인다면)

그러나 1은 홀수이므로 statement C : 1은 짝수다, 라는 말에서 $C\wedge \neg C$은 False이다.

 

그러나 전체적인 논리 관점에서 $(\neg P)\Rightarrow (C\wedge \neg C)$ 가 참이 되고, 위의 논리표에 따라 $P$는 참이라는 것을 알 수 있다. $(C\wedge \neg C)$은 모순(contradiction)을 의미하므로, 모순임을 보이기만 하면 $(C\wedge \neg C)$이라는 틀에 끼워맞출 필요는 없지만 이렇게 생각하는 것도 하나의 방법임을 알 수 있었다.

 

 

$P\Rightarrow Q$인 Conditional statement의 경우에는 $\neg(P\Rightarrow Q)$가 $P \wedge \neg Q$으로 해석하면 된다.

 

예를 들면

$\textbf{Preposition }\quad \text{Suppose }a\in \mathbb{Z}\text{. If }a^{2}\text{ is even, then }a\text{ is even.}$

 

대우로도 증명하면 쉬워보이는데, 여기서는 귀류법으로 풀어본다.

preposition을 부정하면 $a^{2}$는 짝수이고, $a$는 짝수가 아니라고 하자.

$a=2b+1$라고 가정하면 $a^{2}=4b^{2}+4b+1$으로 짝수가 아니다. $a^{2}$이 짝수라는 statement와  $a^{2}=4b^{2}+4b+1$를 통해 알아낸 $a^{2}$이 홀수라는 statement에서 모순이 발생한다.

 

따라서 위의 preposition은 참이다.

 

 

 

참고자료

 

 

https://en.wikipedia.org/wiki/Proof_by_contradiction

Proof by contradiction - Wikipedia

 

http://cgm.cs.mcgill.ca/~godfried/teaching/dm-reading-assignments/Contradiction-Proofs.pdf

---

5. Statement의 negation(부정)

 

어떤 명제의 부정을 하는 방법을 몰라서 기록하는 글이다. 참고한 글은 아래 링크이다.

 

https://www.math.toronto.edu/preparing-for-calculus/3_logic/we_3_negation.html

Logic and Mathematical Statements - Worked Examples

 

위 링크의 내용을 요약하면 아래의 표로 말할 수 있다.

 

1) 첫 번째 statement를 기호로 표현하면 다음과 같다.

$A \vee B\quad \xrightarrow[]{negation}\quad \neg(A \vee B) =\neg A \wedge \neg B$

 

2) 두 번째 statement도 마찬가지로

$A \wedge B\quad \xrightarrow[]{negation} \quad \neg(A \wedge B) =\neg A \vee \neg B$

 

3) 세 번째 statement는 일반적인 conditional statement이다. 특이한 점은 statement는 분명 conditional statement인데 이에 대한 부정은 집합 표현으로 나타난다는 점이다.

$A \Rightarrow B \xrightarrow[]{negation} \quad A \wedge \neg B$

 

이 표현은 위의 Proof by contradiction 위키피디아 문서에서 proof by contradiction을 증명하는데 중요하게 쓰인다.

위키피디아 proof by contradiction

위의 증명을 보면 $A\rightarrow B \equiv \neg A \vee B \equiv \neg(A\wedge \neg B)$임을 관찰할 수 있다.

 

A이면 B이다, 라는 말은 벤다이어그램으로 표현하면 B 안에 A가 있는 것으로 볼 수 있다.

<A이면 B이다>라는 문장을 부정하고 싶으면, A에 속해있으면서 B는 아닌 것이 존재함을 보이면 된다. 따라서 앞서 본 $A\wedge \neg B$가 의미적으로 그렇게 해석할 수 있다.

 

그럼 <A이면 B이다>라는 문장은 집합으로 표현할 때 $A\wedge \neg B$를 부정해서 $\neg(A\wedge \neg B)=\neg A \vee B$라고 한다. 의미적으로 해석하면

B안에 A가 있을 때는 $\neg A \vee B$가 전체 diagram을 채우지만 그렇지 않을 때는 $A-B$인 집합이 존재하고 이는 $A\rightarrow B$라는 명제의 반례가 된다.

 

추가로 위키피디아에 대한 내용을 설명하면,

왜냐하면 $p=p\vee \bot=\neg (\neg p) \vee \bot = \neg p\rightarrow \bot $ 이기 때문에 (이 부분은 이해가 잘 안됨)

$\neg (A\wedge \neg B) = \neg (A\wedge \neg B) \vee \bot=(A \wedge \neg B)\rightarrow \bot$이 된다.

 

 

4-5) 네 번째 statement와 다섯 번째 statement는 for all, any, every를 어떻게 부정하는지에 대해 알려준다. for all 이 들어간 증명은 모든 사례에 대해서 증명하기가 매우 어려우므로 부정을 이용해서 증명하는 편이 더 쉬울 수 있다.