완전성

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

정의

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

${\displaystyle \models _{\mathcal {S}}\varphi \implies \vdash _{\mathcal {S}}\varphi }$

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

구문론적 완전성

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

같이 보기

• 건전성
• 괴델의 완전성 정리

이 글은 수학에 관한 토막글입니다. 여러분의 지식으로 알차게 문서를 완성해 갑시다.