증명 (수학)

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

수학에서 증명(證明)은 특정한 공리들을 가정하고, 그 가정 하에서 어떤 명제가 참이라는 것을 보여주는 것을 가리킨다. (특정한 공리는 별다른 언급이 없으면 체르멜로-프랭켈-선택공리계로 가정한다.)

증명은 논리를 통해 이루어져야 하지만 일반적으로 자연어를 포함하게 되며, 따라서 애매한 부분을 포함하기도 한다. 실제로 수학에서 대부분의 증명은 비형식 논리를 통해 이루어진다. 순수 형식논리를 통한 증명은 증명이론에서 다룬다. 형식적인 증명과 비형식적인 증명 사이의 구별은 형식주의에 철저히 입각해 있건 그렇지 않건, 참이라는 것이 밝혀진 명제정리라고 한다. 참이라는 것이 증명된 정리는 다른 명제를 증명하는 데 사용할 수 있다.

증명 기법에는 다음과 같은 것들이 있다.

  • 직접 증명: 공리와 정의, 그리고 이미 증명된 정리를 논리적으로 직접 연결하여 증명한다.
  • 수학적 귀납법: 바탕 명제(base case)가 참일 때, 귀납 규칙(induction rule)을 증명하여 무한히 많은 다른 명제들도 참이라는 것을 보인다.
  • 귀류법(reductio ad absurdum): 어떤 명제가 거짓이라고 가정하면 모순이 발생한다는 것을 증명하면, 그 명제가 참이어야 함을 알 수 있다.
  • 예제를 통한 증명(proof by construction): 어떤 성질을 만족하는 구체적인 예제를 하나 만들어 그 성질을 만족하는 어떤 것이 실제로 존재함을 증명한다.

확률적 증명확률론적 방법을 동원해 어떤 예제가 존재함을 보이는 것이다. 이것은 어떤 명제가 참이라는 것을 '확률적'으로 보이는 것과 전혀 다르며, 명제가 참일 확률을 계산하는 것과 실제로 그것을 증명하는 것은 거리가 멀다는 것을 콜라츠 추측을 통해 알 수 있다.

조합론적 증명은 두 개의 서로 다른 식이 같은 값이라는 것을 보일 때 두 식이 같은 물체의 개수를 다른 방식으로 세는 것임을 증명한다.

참일 것으로 추정하지만 아직 참이라는 것이 밝혀지지 않은 명제는 추측이라고 한다.

때로는 주어진 공리계에서 어떤 명제를 증명하는 것은 불가능하다고 밝혀지는 경우도 있다. 연속체 가설이 그 예이다. 대부분의 공리계에는 증명도 반증도 불가능한 명제가 존재한다. 더 자세한 설명은 불완전성 정리를 보라.