수학적 증명방법

어떠한 수학적 이론을 증명하는 데는 여러 방법이 있을 수 있다. 기존에 증명된 다른 사실을 연역하여 증명할 수도 있으며(직접 증명법), 대우를 이용하여 증명할 수 도 있다.

이 글에서는 수학적 사실을 증명하는 테크닉들을 소개하고자 한다. 잘 기억해두고 유용히 쓸 수 있도록 하자.

---

귀류법

수학 교과에서도 소개되는 방법이다. 원명제를 부정하여 새로운 명제를 세우고(Ex. "불은 뜨겁다"→"불을 뜨겁지 않다") 그 명제를 대전제로 하여 논리를 펼쳤을 때 논리에 모순이 생김을 보여 원명제가 사실임을 보이는 것이다.

다음은 귀류법을 이용하여 소수가 무한함을 보이는 과정이다.

증명하고자 하는 명제: 소수는 무한하다.
부정한 명제: 소수는 유한하다.
대전제에 따라 소수는 유한하므로 소수들로 이루어진 수열 $P$에서 $P_n$을 가장 큰 소수라고 해보자.
$P_n<x$인 $x$를 생각해보면 $x$는 수열 $P$중 한 개 이상의 원소로 나누어 떨어져야 한다.
그런데 수열 $P$의 모든 원소들의 곱에 +1을 한 $x$(다시말해 $x=\prod_{i=1}^{n}P_i+1$)를 생각해보면 $x$는 $P$의 어느 원소로도 나누어 떨어뜨릴 수 없게 된다. 즉, $x$는 소수이다.
이는 가장 큰 소수가 $P$라는 사실에 모순되므로 대전제가 틀렸다는 결론을 도출할 수 있다.
따라서 소수는 무한하다.

이 외에도 $\sqrt{2}$가 무리수임을 보일 때도 사용될 수 있다. $\sqrt{2}$가 실수일 때 $\sqrt{2}$가 무리수임을 귀류법을 이용하여 증명해보아라.

---

더블카운팅

더블카운팅은 등식을 증명할 때 양 변의 의미가 같음을 보여 결국 등식 자체가 성립함을 보이는 것이다.

더블카운팅을 이용하여 $2^0+2^1+2^2+\cdots+2^{n-1}=2^n-1$임을 증명해보자.

$T_n=\left\{x|1 \leq x \leq n, x\in\mathbb{N}\right\}$인 집합 $T_n$을 생각해보자.
1. $T_n$의 공집합을 제외한 부분집합의 개수는 $2^n-1$이다. 각 $n$개의 원소에 대해 선택/버림의 2개의 선택권이 주어져 선택된 원소들로 부분집합을 만들 수 있기 때문이다.
2. $T_n$의 공집합을 제외한 부분집합의 개수를 다른 방식으로도 구할 수 있다. $1 \leq i \leq n$인 자연수 $i$에 대해 $T_n$의 부분집합 중 가장 큰 원소가 $i$인 부분집합의 개수는 $2^{i-1}$개이다. 가장 큰 원소 $i$를 뽑힌다고 가정하고 그보다 작은 $n-1$개의 원소들로 부분집합을 구성하는 방법의 수이기 때문이다.
그렇기 때문에 $T_n$의 부분집합 중 공집합이 아닌 집합은 $i$가 $1$부터 $n$일 때까지 부분집합을 모두 더한 $2^0+2^1+2^2+\cdots+2^{n-1}$이다.
1, 2에서 구한 식은 둘 다 $T_n$의 부분집합 중 공집합이 아닌 집합의 개수를 구하는 식이다. 즉, 두 식의 의미가 같으므로 $2^0+2^1+2^2+\cdots+2^{n-1}=2^n-1$임을 증명할 수 있다.

더블카운팅을 적절히 사용하기 위해서는 주어진 식이 어떤 것을 나타내고 있는지 분석하고 두 변의 의미가 같음을 어떻게 증명할지 생각하는 것이 중요하다. 따라서 창의력이 중요하다고 할 수 있겠다.

---

무한 강하 법

실수 중에서 자연수의 범위는 제한되어있다. 어떠한 자연수도 1보다 작을 수는 없다. 무한 강하 법은 이를 이용하여 증명을 하는 것이다. 무한 강하 법을 이용하여 $\sqrt{2}$가 무리수임을 증명해보자.

귀류법을 사용하기 위해 $\sqrt{2}$가 유리수라고 가정해보자. 그럼 $\sqrt{2}=\frac{m}{n}$인 정수이며 서로소인 $m, n$이 있을 것이다. 따라서 양변을 제곱해주면 $2n^2=m^2$이 될 것이다.
$m^2$이 $2$의 배수여야 하므로 $m$또한 2의 배수일 것이다. 그럼 $m=2m'$인 $m'$이 존재할 것이며 이를 앞선 식에 대입하면 $n^2=2m'^2$일 것이다.
이번에는 $n^2$이 2의 배수이므로 $n=2n'$인 $n$이 있을 것이며 이를 다시 대입하면 $2n'^2=m'^2$이 될 것이다.
이 과정을 계속 반복하면 $n'^2=2m''^2, 2n''^2=m''^2 \cdots$으로 무한히 진행될 것이다. 결국 $m$과 $n$의 값은 계속 $\frac{1}{2}$가 되므로 어느샌가는 정수가 아닌 순간이 올 것이다. 그렇게 되면 결국 $m, n$이 정수라는 전제에 위배되며 모순이다.
따라서 $\sqrt{2}$는 무리수인 것이다.

---

이 글에서는 수학에서 쓰이는 증명법중 3가지를 다루어 보았다. 모두 자주 쓰이는 것이니 잘 기억해두도록 하자. 어떠한 명제를 증명하는 방법을 암기할 필요는 없다. 하지만, 어떠한 증명방법을 어떻게 수행하는지는 알아둘 필요가 있다.