증명

원문 보기: https://dawoum.duckdns.org/wiki/증명

Main article: Mathematical proof

지식이 참된 것이 되기 위해서는 근거가 필요하나 근거를 소급해 보면 더 이상 증명하기가 곤란한 명제에 다다르게 됩니다. 이것이 바로 공리(axiom)이며, 어떤 이론체계에서 가장 기초적인 근거가 되는 명제입니다. 다음은 공리의 예입니다.

• 명제 \(p\)가 성립한다면, 명제 '\(p\) 또는 \(q\)'도 성립한다.
• 두 점이 주어졌을 때, 그 두 점을 통과하는 직선을 그을 수 있다.
• \(a=b\)이면, \(a+c = b+c\)이다.
• 어떤 자연수에 대해서도, 그 수의 '다음' 자연수(따름수)가 존재한다.
• 어떤 것도 포함하지 않는 집합(빈 집합:공집합)이 존재한다.

정리(theorem)는 공리를 근거로 증명된 명제를 말하며, 다른 명제를 증명할 때 사용하는 중요한 명제를 가리킵니다.

증명(proof)은 특정한 공리들을 가정하고, 그 가정 하에서 어떤 명제가 참이라는 것을 보여주는 것을 말합니다. 

예를 들어,

\(\quad\)'선분의 수직이등분선 위의 점은 선분의 끝점에 이르는 거리가 같다'

라는 명제가 참임을 보이는 것을 증명이라고 합니다.

증명) 오른쪽 그림처럼 선분 \(\mathrm{AB}\)의 수직이등분선 \(l\)위의 한 점을 \(\mathrm P\)라고 하면, \(\triangle \mathrm{AMP}\)와 \(\triangle \mathrm{BMP}\)로 부터 다음의 사실을 알 수 있습니다.

• \(\mathrm{AM=BM}\)
• \(\angle \mathrm{AMP=BMP}=90^{\circ}\)
• \(\mathrm{MP}\)는 공통

그러므로, \(\triangle \mathrm{AMP}\)와 \(\triangle \mathrm{BMP}\)는 두 변의 길이와 끼인각이 서로 같으므로 서로 합동(SAS)입니다. 따라서 대응하는 두 변의 길이가 서로 같습니다.

\(\quad\)\(\therefore \mathrm{PA=PB}\)

직접증명법

주어진 명제를 변형하지 않고 \(p \longrightarrow q\)가 참임을 증명하는 방법을 직접 증명법(direct proof)이라고 합니다. 

\(\quad\)'두 정수가 짝수이면 두 정수의 곱이 짝수이다.'

증명) 두 짝수를 \(a = 2m, b = 2n\) (\(m, n\)은 정수)로 나타낼 수 있습니다. 그러므로

\(\quad\)\(a \times b = 2m \times 2n = 4m \cdot n = 2(2 m \cdot n)\)

입니다. 여기서 \(2m \cdot n\)이 정수이므로 \(a \cdot b\)도 짝수입니다.

그러므로 '두 정수가 짝수이면 두 정수의 곱이 짝수이다.'는 참입니다.

대우증명법

어떤 명제와 그의 대우는 서로 진리값이 같음을 알아보았습니다. 즉, 어떤 명제가 참임을 직접 증명하는 것이 힘들면, 그의 대우 명제가 참임을 보임으로써 원래 명제가 참임을 보이는 것을 대우 증명법(Proof by Contraposition)이라고 합니다.

\(\quad\)'두 정수의 곱이 홀수이면 두 정수는 홀수이다.'

이 명제를 직접 증명법으로 참임을 보이기 위해서는 정수를 짝수와 홀수로 나눈 후에 모든 경우의 곱을 수행해야 합니다. 즉, 짝수\(\times\)짝수, 홀수\(\times\)짝수, 짝수\(\times\)홀수, 홀수\(\times\)홀수의 결과를 보이고, 네 가지 경우 중에 '홀수\(\times\)홀수'만이 홀수임을 보임으로써 명제가 참임을 증명합니다.

한편, 이 명제의 대우는 다음과 같습니다.

\(\quad\)'두 정수가 짝수이면 두 정수의 곱이 짝수이다.'

대우 명제와 원래 명제의 진리값은 같기 때문에 이 대우 명제를 증명하는 것이 원래 명제를 증명하는 것과 같습니다.

또한, 두 조건 \(p, q\)의 진리집합을 \(P, Q\)라 할 때

\(\quad\)\(Q^c \subset P^c \Longleftrightarrow P \subset Q\)

입니다. 그러므로 \(Q^c \subset P^c\)임을 보이는 것은 명제 \(p \longrightarrow q\) 참임을 보이는 것과 동치관계입니다.

귀류법

명제의 부정에서 명제의 부정에 대한 부정은 원래 명제가 됨을 알아보았습니다. 어떤 명제가 참임을 보이기 위해서, 원래 명제의 부정을 참이라고 가정했을 때 모순된 결과를 보임으로써, 원래 명제가 참임을 증명하는 방법을 귀류법(Proof by Contradiction:모순 증명법)이라고 합니다.

또한, 어떤 명제의 가정하에 결론의 부정을 가정하였을 때 모순되는 가정이 나온다는 것을 보여, 원래의 명제가 참인 것을 증명하는 방법입니다. 즉, \(p\longrightarrow q\)의 참임을 보이기 위해서, \(p\;\text{and}\;\sim\! q\)가 모순됨을 보이는 증명법입니다. 

즉, 조건 \(p, q\)의 진리집합을 \(P, Q\)라 할 때 다음을 만족합니다.  

\(\quad\)\(p\Longrightarrow q \Leftrightarrow (P\subset Q) \Leftrightarrow P^c \cup Q = U\)

또한, \(p\;\text{and}\;\sim\! q\)의 모순에 대한 해집합이 다음과 같습니다.

\(\quad\)\((P \cap Q^c)^c=P^c \cup Q\)

그러므로, 두 명제의 해집합이 같기 때문에 두 명제는 동치관계입니다.
예를 들어 '\(\sqrt{2}\)는 무리수이다.'를 귀류법을 사용해서 증명해 보겠습니다.
증명) 원래 명제의 부정인 다음의 명제가 참임을 가정합니다.

\(\quad\)'\(\sqrt{2}\)가 유리수이다.'

따라서 유리수의 정의에 따라 \(\displaystyle \sqrt{2} = \frac{b}{a}\) (\(a, b\)는 서로소인 정수, \(a \neq 0\))으로 둘 수 있습니다. 

식을 정리하면, \(2a^{2} = b^{2}\)이므로 \(b^{2}\)은 2의 배수입니다.

한편, 정수는 짝수(\(2m\))와 홀수(\(2m+1\))로 나눌 수 있으며 각각을 제곱했을 때 짝수(\(4m^2\))와 홀수(\(4m^2+4m+1\))의 결과가 나옵니다. (여기서 \(m\)은 정수)

그러므로 \(b^{2}\)이 2의 배수이므로, \(b\)도 2의 배수입니다. 따라서 \(b=2n\)으로 둘 수 있습니다. (여기서 \(n\)은 정수)

이를 위의 수식에 대입하면 \(\displaystyle a^{2}=\frac{1}{2}b^{2}=2n^{2}\)이므로 \(a^{2}\)은 2의 배수입니다. 그리고, \(a^{2}\)이 2의 배수이므로, \(a\)도 2의 배수입니다.

위의 두 결과 '\(b\)는 2의 배수', '\(a\)는 2의 배수'는 공통약수 2가 있음을 보입니다. 따라서 \(a, b\)가 서로소라는 가정에 모순되므로 \(\sqrt{2}\)는 유리수가 아닙니다. 즉 '\(\sqrt{2}\)는 무리수입니다.'