괴델의 완전성 정리와 불완전성 정리는 어떻게 공존 가능할까?

논리학
1

수리논리학을 처음 공부하는 사람은 괴델의 완전성 정리와 괴델의 불완전성 정리가 공존한다는 사실에 혼란을 느끼곤 합니다. 여기에 페아노-데데킨트 공리계에 대한 잘못된 이해까지 포함되면 더욱 혼란스럽습니다. 흔히 혼란은 위 세 정리에 대한 다음의 (오해의 여지가 큰) 요약에서 비롯됩니다.

괴델의 완전성 정리. 1차 논리는 완전하다.

괴델의 불완전성 정리. 자연수를 포함하는 모든 수학 체계는 불완전하다.

페아노-데데킨트. 1차 논리적 페아노 공리계는 자연수를 정의한다.

이렇게 위의 세 정리를 요약하면 그저 망했습니다. 더 정확한 요약은 다음과 같습니다.

괴델의 완전성 정리. 1차 논리는 의미론적으로 완전하다.

괴델의 불완전성 정리. 자연수를 포함하는 모든 1차 논리 이론은 형태론적으로 불완전하다.

페아노-데데킨트. 1차 논리적 페아노 공리계는 자연수와 비슷한 일군의 집합들을 정의한다.

먼저 세 번째 정리부터 보겠습니다. 1차 논리에는 뢰벤하임-스콜렘 정리가 적용됩니다. 뢰벤하임-스콜렘 정리는 저의 이전 글인 자연수라는 신기루: 수리논리학과 언어철학에 관한 짧은 이야기 에서도 잠깐 다뤘는데, 내용은 대략 다음과 같습니다.

뢰벤하임-스콜렘 정리. 1차 논리 이론만으로 무한한 크기의 모델을 유일하게 특정할 수 없다.

즉, 1차 논리만으로는 자연수의 필요충분조건을 기술할 수 없습니다(자연수는 무한하므로). 때문에 우리는 완벽한 자연수의 정의를 찾는 대신 적당한 자연수의 정의를 찾는 것으로 만족해야 하는데, 페아노 공리계가 이 역할을 꽤 잘 만족합니다. 그러나 자연수 집합이 아니면서 페아노-데데킨트 공리계를 만족하는 어떤 괴상한 집합이 존재한다는 사실은 염두에 둬야 하겠습니다.

이제 괴델의 완전성 정리 및 불완전성 정리의 수정본을 살펴 봅시다. 형태론적 완전성과 의미론적 완전성이라는 표현이 등장했는데요, 각 의미는 다음과 같습니다. 참고로 T ⊢ φ는 φ가 T에서 증명 가능하다는 의미이며, T ⊨ φ는 T의 모든 모델에서 φ가 참이라는 의미입니다.

의미론적 완전성. 임의의 문장 φ에 대해 T ⊨ φ라면 T ⊢ φ일 때, T는 의미론적으로 완전하다.

형태론적 완전성. 임의의 문장 φ에 대해 T ⊢ φ이거나 T ⊢ ¬φ일 때, T는 형태론적으로 완전하다.

둘의 미묘한 차이를 구분하는 것이 중요합니다. 일례로 T ⊢ ¬φ와 T ⊬ φ는 동치가 아님이라는 사실에 주목합시다. T ⊢ ¬φ는 ¬φ의 증명이 존재한다는 긍정적 의미인 한편, T ⊬ φ는 φ의 증명이 존재하지 않는다는 부정적 의미입니다.

또한 의미론적 완전성이 형태론적 완전성을 함의하지 않는다는 사실에 주목해야 합니다. 수리논리학을 처음 공부하면 의미론적 완전성이 형태론적 완전성을 함의한다는 다음의 추론에 빠지기 쉽습니다.

  1. T가 의미론적으로 완전하다고 하자.
  2. T ⊨ φ 또는 T ⊭ φ이다.
    1. T ⊨ φ라면 T ⊢ φ이다. (의미론적 완전성의 정의)
    2. T ⊭ φ라면 T ⊨ ¬φ이고, 따라서 T ⊢ ¬φ이다.
  3. 따라서 T는 형태론적으로 완전하다.

하지만 이것은 잘못된 추론입니다. 잘못된 이유는 2.2, "T ⊭ φ라면 T ⊨ ¬φ이다"에 있습니다. 모델 M에 대해 M ⊭ φ라면 M ⊨ ¬φ인 것은 맞지만, 이론 T에 대해 T ⊭ φ 라면 T ⊨ ¬φ인 것은 아닙니다.

예를 들어 보겠습니다. 다음의 이론, 문장, 그리고 모델을 생각해 봅시다.

  • T = { ∀x P(x, x) }
  • φ = ∃y ¬P(a, y)
  • M = { P: { (a, a), (b, b) } }
  • N = { P : { (a, a) } }

이 때,

  • M ⊨ T, N ⊨ T
  • M ⊨ φ, M ⊭ ¬φ (둘은 동치)
  • N ⊨ ¬φ, N ⊭ φ (둘은 동치)

입니다. 하지만 N ⊭ φ이므로 T ⊭ φ인 동시에 M ⊭ ¬φ이므로 T ⊭ ¬φ입니다. 즉,

  • T ⊭ φ, T ⊭ ¬φ

입니다. 즉, T는 1차 논리의 이론이므로 의미론적으로 완전하지만 T ⊭ φ인 동시에 T ⊭ ¬φ일 수도 있기 때문에 언제나 T ⊢ φ이거나 T ⊢ ¬φ인 것은 아닙니다.

결론을 내리자면 이렇습니다. 어떤 자연수 문장은 참이지만 증명 불가능할 수 있습니다. 구체적으로, 1차 논리 페아노 공리계 PA와 자연수 모델 N에 대하여 N ⊨ PA이고 N ⊨ φ 이지만 PA ⊬ φ인 경우가 가능하기 때문입니다. 이같은 경우가 발생하는 이유는, 위의 반례의 경우에서도 드러나듯이 이론의 모델이 여럿이기 때문입니다. 만약 PA의 모델이 유일하다면 참과 증명 가능성의 괴리는 발생하지 않습니다. 하지만 뢰벤하임-스콜렘 정리에 의해 1차 논리 PA는 자연수만을 유일한 모델로 가질 수 없습니다.

그러므로 괴델의 완전성 정리, 불완전성 정리, 그리고 페아노-데데킨트 공리는 모순 없이 공존 가능합니다.

14개의 좋아요
2

괴델 정리에서의 불완전성은 그러면 고차 논리의 불완전성의 한 경우가 아닌 것인가요? 고차 논리의 불완전성은 제가 알기로 통상적으로 말하는 불완전성, 즉 ⊨가 ⊢를 함축하지 않는 것이어서… 또, 괴델의 불완전성 자체도 이런 종류의 불완전성을 함축하지 않는가요?

4개의 좋아요
3

@car_nap 님이 말씀하신 바가 맞습니다. 본문에서는 1차 논리를 위주로 다루다 보니 괴델의 불완전성 정리를 설명하는 데 있어 "자연수를 포함하는 모든 수학 체계는 형태론적으로 불완전하다"라고 말하는 오류를 범했네요. 이 오류를 수정하고 보완할 겸, 불완전성 정리의 핵심을 다음과 같이 더 잘 설명해 보겠습니다.

표준 자연수 모델 N에서 참인 문장을 완전히 증명하는 무모순적 증명 체계는 존재하지 않는다. 즉, N ⊨ φ 이지만 T ⊬ φ인 경우가 존재한다.

이러면 왜 1차 논리는 형태론적으로 불완전하고 2차 논리는 의미론적으로 불완전한지 알 수 있습니다. T ⊢ φ가 실패하는 경우의 수는 두 가지입니다.

  1. T ⊨ ψ가 언제나 T ⊢ ψ를 시사하나, T ⊨ φ도 아니고 T ⊨ ¬φ도 아닌 경우 (형태론적 불완전성)
  2. T ⊨ φ이나, T ⊨ ψ가 언제나 T ⊢ ψ를 시사하지 않을 경우 (의미론적 불완전성)

1차 논리의 경우 (1)에 의해 N ⊨ φ이지만 T ⊬ φ인 경우가 발생합니다. 한편 2차 논리 페아노 이론은 정언적입니다(즉, PA₂를 만족하는 모델은 N으로 유일합니다). 그러므로 2차 논리에서는 임의의 자연수 문장 φ에 대해 PA₂ ⊨ φ 또는 PA₂ ⊨ ¬φ가 언제나 성립합니다. 그러니 2차 논리가 의미론적으로 완전했다면 (1)에도, (2)에도 해당하지 않으므로 괴델의 불완전성 정리와 상충합니다. 이로부터 2차 논리는 의미론적으로 완전하지 않다는 사실을 알 수 있습니다. 1차 논리와 달리 2차 논리는 (2)에 의해 불완전한 것입니다.

결론적으로 고차 논리의 불완전성은 ⊨가 ⊢을 함축하지 않는 것이 맞으며 이 또한 불완전성 정리의 따름정리입니다. 지적해주셔서 감사합니다!

4개의 좋아요
4

설명 감사합니다! 다만 한가지 더…

뢰벤하임 스콜렘 정리에 따라 무한한 크기의 모형을 갖는 이론이 그것과 동형 사상을 갖는 다른 모형을 갖는 것은 이해하고 있는데, 이것이 증명론적 참과 어떤 관계인지를 잘 모르겠습니다.

이론의 모델이 여럿이라고 해서 그것이 증명도 반증도 안됨을 함축하지는(implies) 않지 않는가요? 증명 가능성은 순수하게 구문론적(syntactic) 관계이니 말입니다.

괴델 증명에 관해서는 설명받을 때마다 매번 아리까리하네요;;

4개의 좋아요
5

1차 논리 이론의 모델이 여러 개라고 해서 반드시 해당 이론이 구문론적으로 불완전한 것은 아닙니다. 하지만 1차 논리 이론의 모델이 여러 개인 것은 해당 이론이 구문론적으로 불완전할 필요조건입니다.

증명 가능성은 구문론적 개념이 맞습니다. 하지만 1차 논리의 경우 구문론과 의미론을 이어주는 다리가 있으니, 다름아닌 완전성 정리입니다. 완전성 정리는 이론 T의 모든 모델에서 참인 문장은 T에서 증명 가능함을 알려줍니다. 이에 따라 만약 1차 논리 이론 T의 모델이 하나밖에 없다면 T는 의미론적으로 완전할 뿐 아니라 구문론적으로도 완전합니다. 이유는 다음과 같습니다. 문장 φ가 주어졌을 때, T의 모델 M에 대해서 M ⊨ φ 또는 M ⊨ ¬φ가 성립합니다. 그런데 T의 모델이 M으로 유일하다면, “M ⊨ φ 또는 M ⊨ ¬φ”은 각각 “T ⊨ φ 또는 T ⊨ ¬φ"를 시사합니다. 여기에 완전성 정리를 적용하면 “T ⊢ φ 또는 T ⊢ ¬φ", 즉 구문론적 완전성을 얻습니다.

따라서 모델이 유일한 1차 논리 이론, 즉 정언적 1차 논리 이론은 구문론적으로 완전합니다. 거꾸로 말해, 1차 페아노 이론이 구문론적으로 완전하지 않을 수 있는 이유는 그것의 모델이 (뢰벤하임-스콜렘 정리에 따라) 유일하지 않기 때문입니다. 답변이 도움 됐기를 바랍니다!

4개의 좋아요
6

아! 이해했습니다. 상세한 설명 감사합니다.

2개의 좋아요