완전성

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

완전성은 형식 체계의 특성으로, 크게 의미론적 완전성, 구문론적 완전성, 반증 완전성 등으로 구분된다. 의미론적 완전성은 형식 체계에서 의미론적 귀결이 구문론적 귀결을 함의하는 것을 의미하며, 괴델의 완전성 정리가 일차 논리에 대한 의미적 완전성을 확립했다. 구문론적 완전성은 형식 체계 내에서 임의의 문장 φ에 대해 φ 또는 ¬φ가 반드시 도출되는 성질을 의미하며, 괴델의 불완전성 정리는 무모순성과 구문론적 완전성을 동시에 가질 수 없음을 보여준다. 반증 완전성은 만족 불가능한 공식 집합으로부터 거짓을 도출할 수 있는 성질을 의미한다. 이 외에도 표현 완전성, 함수적 완전성, 구조적 완전성, 모형 완전성과 같은 다양한 종류의 완전성이 존재한다.

완전성

📚 더 읽어볼만한 페이지

논증 - 삼단논법
삼단논법은 아리스토텔레스가 제시한 논리적 추론 방법으로, 대개념, 소개념, 매개념을 통해 결론을 이끌어내며, 명제의 양과 질, 중명사의 위치에 따라 다양한 형식이 존재한다.
논증 - 이유
이유는 철학에서 현상이나 주장을 설명하고 정당화하는 근거로, 규범적 이유(상황 지지), 설명적 이유(현상 원인), 동기 부여 이유(행동 설명)로 나뉘며, 인식적 이유(믿음 근거)와 실천적 이유(행동 근거)로 구분되고 논증에서는 증거 및 설명을 제공한다.
모형 이론 - 괴델의 불완전성 정리
괴델의 불완전성 정리는 산술을 표현할 수 있는 무모순적 공리계는 그 안에서 증명하거나 반증할 수 없는 명제가 존재하며, 특히 체계 스스로의 무모순성을 증명할 수 없다는 수학적 논리 분야의 핵심 정리이다.
모형 이론 - 괴델의 완전성 정리
괴델의 완전성 정리는 1차 논리 이론에서 모형 이론적 진리와 증명 이론적 진리가 같음을 나타내며, 연역 체계가 완전함을 보장하고 일차 논리에서 통사론적 결과와 의미론적 결과가 동일하다는 것을 의미한다.
증명 이론 - 힐베르트 프로그램
증명 이론 - 괴델의 불완전성 정리
괴델의 불완전성 정리는 산술을 표현할 수 있는 무모순적 공리계는 그 안에서 증명하거나 반증할 수 없는 명제가 존재하며, 특히 체계 스스로의 무모순성을 증명할 수 없다는 수학적 논리 분야의 핵심 정리이다.

1. 개요
2. 의미론적 완전성
- 2.1. 강한 완전성
3. 구문론적 완전성
4. 반증 완전성
5. 기타 완전성

2. 의미론적 완전성

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

: $\models_{\mathcal S} \varphi \implies \vdash_{\mathcal S} \varphi$

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

2.1. 강한 완전성

형식 체계 $S$ 에서 모든 전제 집합 $\Gamma$ 에 대해 $\Gamma$ 로부터 의미론적으로 도출되는 모든 공식이 $\Gamma$ 로부터 유도될 수 있다면, 형식 체계 $S$ 는 강하게 완전하다 또는 강한 의미에서 완전하다라고 한다. 이는 다음을 의미한다.

:: $\Gamma\models_{\mathcal S} \varphi \ \to\ \Gamma \vdash_{\mathcal S} \varphi.$

3. 구문론적 완전성

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

: $\models_{\mathcal S} \varphi \implies \vdash_{\mathcal S} \varphi$

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

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

형식적 시스템 구문론적 완전성 또는 연역적 완전성 또는 최대 완전성을 갖는다는 것은 시스템의 언어에 속하는 각 문장 (닫힌 공식) φ에 대해 φ 또는 ¬φ가 의 정리일 경우를 말한다. 이는 부정 완전성이라고도 하며, 의미적 완전성보다 더 강력하다. 다른 의미에서, 형식적 시스템은 증명할 수 없는 문장을 일관성을 도입하지 않고 추가할 수 없을 때에만 구문론적 완전성을 갖는다. 진리 함수 명제 논리와 일차 술어 논리는 의미적으로 완전하지만 구문론적으로 완전하지 않다(예를 들어, 단일 명제 변수 A로 구성된 명제 논리 명제는 정리가 아니며, 그 부정 또한 아니다). 괴델의 불완전성 정리는 계산 가능한 시스템 중 페아노 산술과 같이 충분히 강력한 시스템은 일관적이면서 구문론적으로 완전할 수 없음을 보여준다.

4. 반증 완전성

형식적 시스템 $\mathcal{S}$ 가 모든 만족 불가능한 공식 집합으로부터 거짓을 도출할 수 있다면 반증 완전하다고 한다. 즉, 다음과 같다.
:: $\Gamma \models_{\mathcal S} \bot \to\ \Gamma \vdash_{\mathcal S} \bot.$

모든 강한 완전성을 가진 시스템은 반증 완전하기도 하다. 직관적으로, 강한 완전성은 공식 집합 $\Gamma$ 가 주어졌을 때, $\Gamma$ 의 모든 의미론적 결과 $\varphi$ 를 "계산"하는 것이 가능하다는 것을 의미하며, 반증 완전성은 공식 집합 $\Gamma$ 와 공식 $\varphi$ 가 주어졌을 때, $\varphi$ 가 $\Gamma$ 의 의미론적 결과인지 "확인"하는 것이 가능하다는 것을 의미한다.

반증 완전 시스템의 예로는 혼 절에 대한 SLD 해법, 등식 절 일차 논리에 대한 중첩 계산, 절 집합에 대한 로빈슨의 해법 등이 있다. 로빈슨의 해법은 강한 완전성을 가지지 않는다. 예를 들어, $\{ a \} \models a \lor b$ 는 일차 논리의 명제 부분집합에서도 성립하지만, $a \lor b$ 는 해법에 의해 $\{ a \}$ 에서 도출될 수 없다. 하지만, $\{ a, \lnot (a \lor b) \} \vdash \bot$ 는 도출될 수 있다.

5. 기타 완전성

건전성의 역으로서 완전성이란 "의미론적 귀결이 구문론적 귀결을 함의한다"는 것을 의미한다. 괴델의 완전성 정리에 따르면 잘 정의된 1차 논리 체계에서는 귀결 명제의 집합이 항상 모형을 가지므로 완전성이 성립한다. 완전성에 대한 역의 속성은 견실성이라고 한다. 시스템은 속성에 관하여 견실하다면(대부분 의미론적 타당성), 해당 시스템의 각 정리가 그 속성을 갖는다.

5.1. 표현 완전성

형식 언어는 의도된 주제를 표현할 수 있다면 표현 완전성을 가진다고 한다.

5.2. 함수적 완전성

논리 연산자 집합이 모든 명제 함수를 표현할 수 있다면, 이 집합은 기능적으로 완전하다고 한다.

5.3. 구조적 완전성

초직관 논리 및 양상 논리에서, 논리가 구조적 완전성을 갖는다는 것은 모든 허용 규칙이 유도 가능하다는 것을 의미한다.

5.4. 모형 완전성

형식 체계 S에서 다음이 항상 성립하면 S가 완전(complete^영어)하다고 한다.

: $\models_{\mathcal S} \varphi \implies \vdash_{\mathcal S} \varphi$

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

어떤 이론이 모형 완전하다는 것은 그 모형들의 모든 포함 관계가 기본적 포함 관계일 때에만 해당한다.