완전성 문서 원본 보기

{{위키데이터 속성 추적}}
[[논리학]]에서 '''완전성'''(完全性, {{llang|en|completeness}})이란, [[형식 체계]] 내에서 모든 참인 문장이 증명 가능한 성질이다. 더욱 일반화하면, 특정 성질을 가진 명제가 도출 가능한 성질을 가리킨다.

== 정의 ==
[[건전성]]의 역으로서 완전성이란 "의미론적 귀결이 구문론적 귀결을 함의한다"는 것을 의미한다. 형식 체계 S에서 다음이 항상 성립하면 S가 '''완전'''({{llang|en|complete}})하다고 한다:

: <math>\models_{\mathcal S} \varphi \implies \vdash_{\mathcal S} \varphi</math>

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

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

== 같이 보기 ==
* [[건전성]]
* [[괴델의 완전성 정리]]

{{토막글|수학}}

[[분류:수리논리학]]
[[분류:모형 이론]]
[[분류:증명 이론]]
[[분류:논증]]