무모순적 이론

수리논리학에서 무모순적 이론(無矛盾的理論, 영어: consistent theory)은 거짓을 추론할 수 없는 이론이다. 이러한 성질을 무모순성(無矛盾性, 영어: consistency) 또는 일관성(一貫性)이라고 한다. 자명한 이론(즉, 모든 문장을 증명하는 이론)은 항상 모순적 이론이다. 반대로, 폭발 원리가 성립하는 형식 체계(예를 들어, 고전/직관 명제/1차 논리)에서, 모든 모순적 이론은 자명한 이론이다.

관련된 개념으로 만족 가능 이론이 있다. 무모순성이 구문론적으로 정의되는 반면, 만족 가능성은 의미론적 개념이다. 어떤 이론이 모형을 갖는다면 만족 가능하다고 한다. (즉, 모든 공리가 참이 되는 해석을 갖춘 구조가 존재하여야 한다.) 건전한 형식 체계의 모든 만족 가능 이론은 무모순적 이론이지만, 그 역은 성립하지 않는다. (건전성에 의하여, 이론에서의 추론 과정은 모형 이론적 진리를 보존하며, 이론에서 증명 가능한 모든 문장은 모형에서도 참이다. 특히 이론이 모순을 증명할 수 있다면 모형 속에도 모순이 존재하는데, 이는 불가능하다.) 1차 논리 형식 체계는 건전하며 (건전성 정리), 또한 1차 이론의 무모순성과 만족 가능성은 동치이다 (괴델의 완전성 정리).

정의

1차 논리 언어 ${\displaystyle {\mathcal {L}}}$이 주어졌다고 하자. 그렇다면, 1차 논리 ${\displaystyle {\mathcal {L}}}$-문장(즉, 자유 변수가 없는 ${\displaystyle {\mathcal {L}}}$-논리식)들의 집합 ${\displaystyle \operatorname {Sent} ({\mathcal {L}})}$의 멱집합 ${\displaystyle {\mathcal {P}}(\operatorname {Sent} ({\mathcal {L}}))}$을 생각하자. ${\displaystyle {\mathcal {L}}}$-문장들의 집합 ${\displaystyle T\in {\mathcal {P}}(\operatorname {Sent} ({\mathcal {L}}))}$을 ${\displaystyle {\mathcal {L}}}$-이론(영어: theory)이라고 한다.

${\displaystyle {\mathcal {L}}}$-이론 ${\displaystyle T\in {\mathcal {P}}(\operatorname {Sent} ({\mathcal {L}}))}$가 다음 조건을 만족시킨다면, ${\displaystyle T}$를 무모순적 이론(영어: consistent theory)이라고 한다.

${\displaystyle T\not \vdash \bot }$

여기서 ${\displaystyle \bot }$은 거짓(모순)인 1차 논리 문장이며 (예를 들어, ${\displaystyle \exists x(\lnot x=x)}$), ${\displaystyle \vdash }$는 1차 논리의 추론 관계이다.

페아노 공리계 ${\displaystyle {\mathsf {PA}}}$의 언어 ${\displaystyle {\mathcal {L}}_{\text{Peano}}}$는 하나의 상수 ${\displaystyle 0}$과 하나의 1항 연산 ${\displaystyle (-)^{+}}$을 포함한다.

${\displaystyle {\mathcal {L}}}$의 기호들이 자연수의 재귀 집합을 이룬다고 하자 (특히, 오직 가산 개의 기호만이 존재한다). 그렇다면, ${\displaystyle {\mathcal {L}}}$-이론 ${\displaystyle T\in {\mathcal {P}}(\operatorname {Sent} ({\mathcal {L}}))}$이 무모순적인지 여부는 페아노 공리계의 언어로 나타낼 수 있다. 이 ${\displaystyle {\mathcal {L}}_{\text{Peano}}}$-문장을 ${\displaystyle \operatorname {Con} (T)}$라고 한다.

상대적 무모순성

${\displaystyle {\mathcal {L}}_{\text{Peano}}}$의 이론 ${\displaystyle S}$가 참이라고 하자. 즉,

${\displaystyle \mathbb {N} \models S}$

라고 하자 (${\displaystyle \mathbb {N} }$은 자연수의 ${\displaystyle {\mathcal {L}}_{\text{Peano}}}$-구조).

그렇다면, ${\displaystyle {\mathcal {L}}}$-이론들의 집합 ${\displaystyle {\mathcal {P}}(\operatorname {Sent} ({\mathcal {L}}))}$ 위에 다음과 같은 원순서를 정의할 수 있다.

${\displaystyle T\lesssim _{S}T'\iff S\vdash (\operatorname {Con} (T')\implies \operatorname {Con} (T))}$

이 원순서를 (메타이론 ${\displaystyle S}$ 아래의) 상대적 무모순성 원순서(영어: relative consistency preorder)라고 하며, 이것이 성립한다면 (${\displaystyle S}$ 아래) ${\displaystyle T}$가 ${\displaystyle T'}$에 대하여 상대적으로 무모순적(영어: relatively consistent)이라고 한다.^{[1]:163, Chapter 12}

${\displaystyle T\lesssim _{S}T'\lesssim _{S}T}$라면, ${\displaystyle T}$와 ${\displaystyle T'}$이 (메타이론 ${\displaystyle S}$ 아래) 등무모순적(等一致, 영어: equiconsistent)라고 한다.

성질

원순서 집합 ${\displaystyle ({\mathcal {P}}(\operatorname {Sent} ({\mathcal {L}})),\lesssim _{S})}$의 최대 원소는 모순적 이론이다. 반대로, ${\displaystyle ({\mathcal {P}}(\operatorname {Sent} ({\mathcal {L}})),\lesssim _{S})}$의 최소 원소는 ${\displaystyle S}$로 증명할 수 있는 문장만으로 구성된 이론이다.

만약 메타이론 ${\displaystyle S}$를 자연수의 완전 이론 ${\displaystyle \operatorname {Th} (\mathbb {N} )}$ (즉, ${\displaystyle \mathbb {N} }$에서 참인 모든 ${\displaystyle {\mathcal {L}}}$-문장의 집합)으로 놓는다면, ${\displaystyle ({\mathcal {P}}(\operatorname {Sent} ({\mathcal {L}})),\lesssim _{S})}$은 물론 정확히 2개의 동치류를 갖는다 (무모순적 이론의 동치류와 모순적 이론의 동치류).

불완전성 정리

 이 부분의 본문은 괴델의 불완전성 정리입니다.

${\displaystyle {\mathcal {L}}_{\text{Peano}}}$를 ${\displaystyle {\mathcal {L}}}$로 해석할 수 있다고 하자. 그렇다면, 괴델의 불완전성 정리에 따르면, 임의의 이론 ${\displaystyle T\subseteq \operatorname {Sent} ({\mathcal {L}})}$에 대하여, 다음이 성립한다.

${\displaystyle \left(T\not \vdash \operatorname {Con} (T)\right)\lor \lnot \operatorname {Con} (T)}$

즉, ${\displaystyle T}$는 모순적이거나 아니면 스스로의 무모순성을 증명할 수 없다.

보존적 확장

두 이론 ${\displaystyle T}$와 ${\displaystyle T'}$이 주어졌다고 하자. 메타이론 ${\displaystyle S}$ 아래, 만약 ${\displaystyle T'}$이 ${\displaystyle T}$의 보존적 확장이라면, ${\displaystyle T'}$와 ${\displaystyle T}$는 (메타이론 ${\displaystyle S}$ 아래) 등무모순적이다.

같이 보기

• 인지부조화
• 힐베르트 문제
• 얀 우카시에비치
• 초일관 논리
• 겐첸의 일관성 증명
• 귀류법

각주

1. Jech, Thomas (2003). 《Set theory》. Springer Monographs in Mathematics (영어) 3판. Springer-Verlag. doi:10.1007/3-540-44761-X. ISBN 978-3-540-44085-7. ISSN 1439-7382. Zbl 1007.03002.

외부 링크

• Weisstein, Eric Wolfgang. “Consistency”. 《Wolfram MathWorld》 (영어). Wolfram Research.
• Weisstein, Eric Wolfgang. “Consistency strength”. 《Wolfram MathWorld》 (영어). Wolfram Research.
• Weisstein, Eric Wolfgang. “Complete axiomatic theory”. 《Wolfram MathWorld》 (영어). Wolfram Research.