괴델의 완전성 정리

틀:위키데이터 속성 추적 수리논리학에서 괴델의 완전성 정리(Gödel-完全性定理, 틀:Llang)는 1차 논리에서 증명 가능한 명제의 집합은 모형을 갖는다는 정리다. 즉, 증명 이론으로 정의한 진리와 모형 이론으로 정의한 진리가 서로 일치한다.

이는 1차 논리의 가장 중요한 성질 가운데 하나이며, 고차 논리에서는 성립하지 않는다. 린드스트룀 정리에 따르면 1차 논리는 완전성과 콤팩트성을 만족하는 가장 강한 논리이다. 2차 논리 이상의 고차 논리에서는 완전성이 성립하지 않는다. 크립키 의미론을 이용하여 많은 경우 정규 양상 논리의 경우에도 완전성이 성립한다.

정의

부호수 $\sigma$에 대한 1차 논리 이론 (자유 변수를 갖지 않는 명제의 집합) $T$가 있다고 하자. 또한, $\varphi$가 (자유 변수를 갖지 않는) $\sigma$-명제라고 하자. 괴델의 완전성 정리에 따르면, 다음 두 조건이 서로 동치이다.틀:Rp틀:Rp

• (모형 이론적 진리) 모든 $\sigma$-구조 $M$에 대하여, 만약 $M\models T$라면 $M\models \varphi$이다. 이는 보통 $T\models \varphi$라고 쓴다.
• (증명 이론적 진리) $T⊢\varphi$

또한, 괴델의 완전성 정리에 따르면 다음 두 조건이 서로 동치이다.

• (충족 가능성) $M\models T$인 $\sigma$-구조 $M$이 존재한다.
• (무모순성) $T⊬\mathrm{\perp }$

증명

괴델의 완전성 정리는 콤팩트성 정리로부터 유도할 수 있다. 1차 논리에서 콤팩트성 정리는 다음과 같이 쓸 수 있다.($T$와 $\varphi$는 위에서와 같은 의미이다)틀:Rp

1. $T\models \varphi$이면, $T_0\models \varphi$인 유한 부분 집합 $T_0\subset T$가 존재한다.
2. $T$의 모든 유한 부분집합이 충족 가능하면, $T$ 역시 충족 가능하다.

첫 번째 정리의 증명은 다음과 같다.틀:Rp$T⊢\varphi$가 $T\models \varphi$를 함의한다는 것은 건전성 정리이다. 반대로, $T⊢\varphi$를 가정하자. 연역 과정은 유한하므로, $T_0⊢\varphi$인 유한 부분 집합 $T_0\subset T$가 존재한다. 건전성 정리에 의해, 이는 $T_0\models \varphi$를 함의한다. 콤팩트성 정리에 의하여, $T\models \varphi$이다.

두 번째 정리는 첫 번째 정리의 따름정리이다.틀:Rp $T$의 모든 유한 부분집합이 만족 가능하면, 건전성 정리에 의해 모든 유한 부분 집합이 무모순이다. 그런데 연역 과정은 유한하므로, $T$ 또한 첫 번째 명제에 의해 무모순이면 충족가능하다.

역사

이 정리는 쿠르트 괴델이 1929년에 증명하였다. 이는 괴델의 1930년 박사학위 강연에 포함되었고, 1931년에 출판되었다.틀:Rp 괴델의 불완전성 정리와 함께 괴델의 가장 중요한 초기 업적으로 꼽힌다.

같이 보기

• 괴델의 불완전성 정리
• 건전성 정리
• 콤팩트성 정리
• 뢰벤하임-스콜렘 정리

외부 링크

• 틀:Eom
• 틀:매스월드
• 틀:매스월드
• 틀:웹 인용