본문으로 이동

완전성

위키백과, 우리 모두의 백과사전.

논리학에서 완전성(完全性, 영어: completeness)이란, 형식 체계 내에서 모든 참인 문장이 증명 가능한 성질이다. 더욱 일반화하면, 특정 성질을 가진 명제가 도출 가능한 성질을 가리킨다.

정의

[편집]

건전성의 역으로서 완전성이란 "의미론적 귀결이 구문론적 귀결을 함의한다"는 것을 의미한다. 형식 체계 S에서 다음이 항상 성립하면 S가 완전(영어: complete)하다고 한다:

괴델의 완전성 정리에 따르면 잘 정의된 1차 논리 체계에서는 귀결 명제의 집합이 항상 모형을 가지므로 완전성이 성립한다.

구문론적 완전성

[편집]

형식 체계의 언어 내에서 구성되는 임의의 문장 에 대하여, 형식 체계 내에서 혹은 가 반드시 도출되는 성질을 구문론적 완전성(syntactical completeness)이라 한다. 불완전성 정리는 어떠한 형식 체계가 재귀(recursion)의 개념을 나타낼 수 있을 정도로 강력하다면, 무모순성과 구문론적 완전성을 동시에 가질 수 없음을 의미한다.

같이 보기

[편집]