수학적 증명(Mathematical Proof)

수학적 증명(Mathematical Proof)

 

 

1.

어떤 주장이 참임을 밝히는 증명을 일컬어 수학의 꽃이라 부른다. 증명 없는 주장은 수학에서 받아들여지지 않기 때문이다. 그런데 그 어떤 증명도 전제 없이는 불가능하다. 무엇을 증명한다는 것은 결국 어떤 전제들을 바탕으로 한 논리적 추론의 결과이기 때문이다. 그러한 전제들은 그와 관련된 다른 전제들에 의해 증명되었거나, 아니면 그 자체가 증명된 것으로 간주되는 것들이다. 그 자체가 증명된 것으로 여겨지는 것들을 공리(axiom)라고 한다. 공리는 한 때 증명이 불필요한 자명한 진술들로 여겨졌다. 실례로 ‘두 점 사이를 지나는 가장 짧은 선은 직선이다.’라는 진술을 기하학의 공리로 택한 이유는 점, 직선과 같은 개념을 바탕으로 그 진술이 자명(self-evident)하다는 것이었다. 그리고 공리들을 바탕으로 논리적으로 추론된 결론, 곧 증명된 것을 ‘정리(theorem)’라고 부른다. 따라서 기하학이나 대수학 등의 수학 분과는 공리들, 논리적 추론 규칙, 그리고 정리들로 구성된 증명 체계라 할 수 있다.

 

그러나 현대 수학자들은 공리를 더 이상 자명한 진술로 받아들이지 않는다. 실례로 동일한 수론(數論)에 대해서도 여러 공리 체계가 가능하다. 즉, 공리는 수학자에게는 선택의 문제다. 수론에서 받아들여져야 하는 모든 정리들이 성립할 수 있도록 공리들을 선택하면 된다. 수론에서 인정되는 정리들을 증명할 수 있도록 해주는 논리적 추론 규칙을 어떤 것으로 택하는가에 따라 공리들에서 얻어지는 정리가 달라지기도 한다. 또 현대 수학은 공리들, 논리적 추론 규칙, 정리들로 구성된 체계를 형식 언어로 다룬다. 이러한 이유로 수학적 증명이란 무엇인가라는 주제를 간단명료하게 설명하기란 쉽지 않다. 그러나 수학적 증명에서 전통적으로 사용되어온 고전적인 접근법은 현재에도 유의미하다.

 

 

 

2. 

증명에 관한 가장 고전적인 접근법에서 논리적 추론 규칙은 배중률(law of excluded middle)과 무모순율(law of consistency)을 원리로 전제한다. 배중률이란 진술은 참(True) 또는 거짓(False) 중 단 하나의 진리치만 가져야 한다는 것이다. 무모순율이란 수학적 증명에 필요한 공리들이 모순을 가져서는 안 되기 때문에 긍정과 부정을 동시에 가지고 있는 모순은 증명의 전제로 사용될 수 없다는 것이다. 수학의 대다수 진술들은 ‘부정’, ‘그리고’, ‘또는’, ‘...면, ...’와 같은 연결사나 ‘모든’, ‘어떤’과 같은 양화사로 결합된 복합 진술형식이기 때문에, 그러한 연결사들과 양화사가 배중률과 무모순율을 위반하지 않도록 규정되어야 한다.

 

부정 연결사를 ‘￢’으로 표현하는 경우, 임의의 진술 P를 부정한 ‘￢P’는 P가 참일 때 거짓, 그리고 P가 거짓일 때 참이 된다. 접속사 ‘그리고’에 해당하는 연접 연결사를 ‘∧’로 표현하는 경우, 임의의 두 진술 P와 Q를 연접 연결사로 결합한 ‘P∧Q’는 P와 Q 모두 참일 때만 참이 된다. 접속사 ‘또는’에 해당하는 이접 연결사를 ‘∨’로 표현하는 경우, 임의의 두 진술 P와 Q를 이접 연결사로 결합한 ‘P∨Q’는 P와 Q 둘 중 적어도 하나가 참이면 참이 된다. ‘...면, ...’에 해당하는 함의 연결사를 ‘→’로 표현할 때 임의의 두 진술 P와 Q를 함의 연결사로 결합한 ‘P→Q’는 전건인 P가 참일 때 후건인 Q가 거짓인 경우를 제외하곤 참이 된다. ‘모든’에 해당하는 전칭 양화사를 ‘∀’로 표현하는 경우, 전칭 진술 ‘∀xP(x)’는 주어진 대상들 모두가 술어 P(x)를 만족할 때만 참이 된다. ‘어떤’에 해당하는 특칭 양화사를 ‘∃’로 표현하는 경우, 특칭 진술 ‘∃xP(x)’는 주어진 대상들 중 술어 P(x)를 만족하는 것이 적어도 하나가 존재하면 참이 된다.

 

이제 교환 법칙이나 결합 법칙과 같은 수론 설계에 필요한 적절한 공리들과, 배중률과 무모순율에 따른 논리적 추론 규칙들이 마련되었다고 가정해보자. 수론의 많은 정리들은 ‘H→C’의 형식으로 표현된다. 그런 형식의 진술들이 공리들과 추론 규칙에 근거하여 마지막 결론으로 얻어진 경우에만 증명된 정리로 여겨지기 때문에, 수학적 논증에 사용되는 해당 공리들과 논리적 추론 규칙들은 ‘정리가 증명된 것’으로 보장해주는 토대가 된다.

 

 

 

3.

수학적 증명의 고전적인 접근법에서 추론 규칙들은 배중률과 무모순율을 원리로 전제하고 있다. 전통적으로 자주 사용되어온 여섯 가지 증명 방식을 살펴보는 가운데, 공리들과 추론 규칙 체계가 갖추어야 조건들을 알아보자.

 

(1) 공허한 증명(Vacuous Proof)

논리적 연결사 및 양화사의 규정 방식에 따라 항상 참인 진술 형식, 실례로 ‘P∨￢P’와 같이 진술 변수에 들어갈 구체적 내용과 무관하게 항상 참인 진술형식들이 있다. 그러한 진술형식을 동어반복(tautology)이라 하는데, 수학적 증명에 필요한 추론 체계는 그러한 동어반복을 증명된 것으로 전제하거나 증명 가능하도록 설계되어야 한다. 이때 동어반복 형식을 만족하는 수학적 진술은 증명된 것으로 취급된다. 반면에 진술의 내용과 무관하게 항상 거짓인 모순형식, 실례로 긍정과 부정을 동시에 함축한 ‘P∧￢ P’와 같은 모순형식은 무모순율에 따른 추론 체계에서 절대 허용되어서는 안 된다. 따라서 다음과 같은 증명 방식이 요청된다.

 

• ‘H → C’ 형의 수학적 진술에서 H가 거짓이거나 모순을 함축한 경우, ‘H → C’ 형의 수학적 진술도 참임이 증명되도록 공리 및 추론 체계가 설계되어야 한다.

 

수학적 증명의 고전적 접근법에 따라 전건이 거짓일 때 함의 연결사의 규정 방식은 ‘H→C’가 항상 참임을 함축한다. 항상 참인 진술 형은 증명되도록 공리 및 추론 체계가 설계되어야 하므로, ‘H→C’ 형도 증명되어야 한다. 그런데 만약 H도 증명된다면 어떻게 될까? 조건문에서 전건이 긍정된 경우 후건도 긍정된 것으로 여겨지는 까닭에, C에 들어갈 진술이 거짓이거나 모순을 함축한 것이라도 증명되게 된다. 이는 무모순율을 위반한 것이다. 따라서 거짓이나 모순을 함축한 진술은 공리가 될 수 없거니와, 공리들은 그러한 진술이 증명되지 않도록 선별되어야 한다. 공허한 증명은 일상적인 추리나 논증에서는 사용되지 않지만, 수학에서는 사용되어야 하는 특수한 경우가 있다.

 

 

(2) 사소한 증명(Trivial Proof)

이번에는 ‘H → C’ 형의 수학적 진술에서 후건인 C가 참이라고 해보자. 함의 연결사의 규정 방식에 따라 ‘H → C’ 형은 진술의 내용과 무관하게 항상 참인 동어반복처럼 취급된다. 동어반복 형식을 만족하는 진술은 증명되도록 공리 및 추론 체계가 설계되어야 하므로, ‘1≠2이면, 1=1’과 같은 진술도 증명되어야 한다. 사소한 증명도 공허한 증명처럼 전건과 후건의 내용적 연결성을 결여한 까닭에 일상생활에서 사용되지 않지만, 수학에서는 필요한 경우가 있다.

 

 

(3) 직접 증명(Direct Proof)

잘 선별된 공리 및 추론 체계에서 ‘H→C1’, ‘C1→C2’, ..., ‘Cn→C’가 각각 증명된 경우, ‘H→C’도 증명되어야 한다. 여기에는 다음과 같은 전통적인 가설적 삼단 논법의 형식이 깔려 있다.

 

P→Q

Q→R

P→R

 

 

(4) 간접 증명(Indirect Proof)

간접 증명에는 ‘대우에 의한 증명(proof of the contrapositive)’과 소위 ‘귀류법(reductio ad absurdum)’으로 불리는 ‘모순을 이용한 증명(proof by contradiction)’이 있다. 배중률을 원리로 전제하는 경우, 다음과 같은 드모르간의 법칙(De Morgan‘s law)이 성립한다.

 

• ‘H → C’ 형식은 ‘￢ C → ￢ H’와 논리적 동치 관계를 맺는데, 후자를 전자의 ‘대우’라고 한다. 서로 논리적 동치 관계를 맺는 것들이 내용적으로도 동일하다고 말할 수는 없지만 형식적 추론 과정에서는 서로 바꿀 수 있는 것들이다.

 

따라서 ‘H → C’ 형의 진술은 그것의 대우인 ‘￢ C → ￢ H’를 증명하면 증명된 것이다. 모순을 이용한 증명 절차는 다음과 같다.

 

• ‘H → C’ 형의 수학적 진술을 직접적으로 증명할 수 없을 때 조건문의 후건의 부정인 ￢ C를 전제로 삼는다. 이때 ‘(H∧￢ C)→(P∧￢ P)’, 즉 원래 증명하려던 조건문의 전건에 후건의 부정한 것을 덧붙여 모순이 발생한다면, ‘H → C’ 형의 수학적 진술이 증명되게끔 공리 및 추론 체계가 설계되어야 한다.

 

모순을 사용한 증명에는 주장하려는 결론을 직접적으로 옹호하기 힘들 때 결론의 부정을 전제한다면 상식적으로 납득하기 힘든 결론이 발생한다는 것을 보임으로써 결론을 간접적으로 옹호하는 ‘일상적 의미의 귀류법’이 반영되고 있다.

 

 

(5) 경우에 따른 증명(Proof by Cases)

‘H1→C’, ‘H2→C’, ..., ‘Hn→C’가 각각 증명된 경우, ‘(H1∨H2∨…∨Hn)→C’도 증명되도록 공리 및 추론 규칙이 건설되어야 한다. 경우에 따른 증명에는 일상생활에서 발견되는 다음과 같은 논증형식이 반영되고 있다.

 

P→R

Q→R        

(P∨Q)→R

 

 

(6) 존재 증명(Existence Proof)

특칭 양화사가 개입되는 존재 증명에는 구성적 증명(constructive proof), 반례에 의한 증명(Proof by Counterexample), 비구성적 증명(nonconstructive proof)이 있다. 어떤 수학적 술어 P(x)를 만족하는 대상 a를 직접 구성할 수 있는 경우, 즉 P(a)가 성립하는 경우, ∃xP(x)가 증명되도록 공리 및 추론 규칙이 설계되어야 한다. 반례에 의한 증명은 배중률을 전제한 상태에서 다음의 드모르간 법칙을 이용한 증명이다.

 

• ￢ (∀xP(x))는 ∃x ￢ P(x)와 논리적 동치 관계를 맺는다.

 

‘모든 x는 P(x)를 만족하지 않는다’는 것, 즉 ￢ (∀xP(x))를 증명하려고 할 때 P(x)를 만족하지 않는 적어도 하나의 대상을 구성한다면, ∃x￢ P(x)가 성립한다. 따라서 ￢ (∀xP(x))를 증명하게 되는 것이다. 공리 및 추론 규칙은 이를 보장하도록 선별되어야 한다.

 

비구성적 증명은 ‘어떤 x는 P(x)를 만족한다’는 것, 즉 ∃xP(x)를 구성적 증명 방식으로 보일 수 없을 때 사용된다. 이때 일반적으로 모순을 이용한 증명 절차를 따른다.∃xP(x)를 부정한 ∀x￢ P(x)에서 모순이 발생한다면, ∃xP(x)가 증명되도록 공리 및 추론 체계가 설계되어야 한다.

 

 

 

4.

지금까지 살펴본 증명 방식들은 무조건적으로 성립하는 것은 아니라는 점에 주의하자. 그것들은 배중률과 무모순율을 원리로 전제하는 전통에 따른 것이다. 수학적 증명에 사용되는 진술들, 실례로 ‘1+1=2’와 같은 진술들은 가능성, 필연성, 당위성 및 시제와 같은 ‘양상(modality)’을 포함하지 않으며, 일상적 현실에서는 긍정과 부정을 동시에 가진 사태를 발견할 수 있기 때문에 수학적 증명을 바탕으로 일상적 논증의 참 ·거짓을 판단할 수 있는 것은 아니다. 또 논리적 연결사의 규정 방식은 진술의 내용을 제거하여 추상화된 것인 반면, 실제 일상생활 속의 판단에서 접속사의 기능은 사태의 내용에 따라 다른 의미를 지니는 경우가 많다. 따라서 일상생활에서 사용되는 논증 및 증명 방식이 수학적 증명에 어느 정도 반영될 수는 있지만 수학적 증명을 바탕으로 현실 속에서 사용되는 논증의 진위를 평가할 수 있는 것은 아니다.