무모순적 이론

수리논리학에서 무모순적 이론(無矛盾的理論, 영어: consistent theory)은 거짓을 추론할 수 없는 이론이다. 이러한 성질을 무모순성(無矛盾性, 영어: consistency) 또는 일관성(一貫性)이라고 한다. 즉, 무모순적 이론에서는 스스로 $\phi$ 와 그 부정 $\lnot \phi$ 를 모두 증명할 수 있는 문장 $\phi$ 가 존재하지 않는다.^[1] (그러나 긍정할 수도, 부정할 수도 없는 문장은 존재할 수 있다.) 반면 모순적인 이론은 모든 문장이 증명 가능하므로 무의미한 이론이 된다. (귀류법은 어떤 문장이 성립하지 않는다고 가정하고 모순을 유도하여 가정이 틀렸음을 보이는데, 모순적 이론 아래에서는 이러한 가정을 하지 않더라도 이미 모순이 존재한다. 따라서 모든 문장은 참이며, 모든 문장의 부정 역시 문장이므로 모든 문장은 거짓이다.)

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

정의 편집

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

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

T\not \vdash \bot

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

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

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

상대적 무모순성 편집

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

\mathbb {N} \models S

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

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

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

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

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

성질 편집

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

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

불완전성 정리 편집

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

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

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

보존적 확장 편집

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

참고 문헌 편집

↑ Hodges, Wilfrid (1997). 《A Shorter Model Theory》. New York: Cambridge University Press. 37쪽. Let $L$ be a signature, $T$ a theory in $L_{\infty \omega }$ and $\varphi$ a sentence in $L_{\infty \omega }$ . We say that $\varphi$ is a consequence of $T$ , or that $T$ entails $\varphi$ , in symbols $T\vdash \varphi$ , if every model of $T$ is a model of $\varphi$ . (In particular if $T$ has no models then $T$ entails $\varphi$ .)
Warning: we don't require that if $T\vdash \varphi$ then there is a proof of $\varphi$ from $T$ . In any case, with infinitary languages, it's not always clear what would constitute proof. Some writers use $T\vdash \varphi$ to mean that $\varphi$ is deducible from $T$ in some particular formal proof calculus, and they write $T\models \varphi$ for our notion of entailment (a notation which clashes with our $A\models \varphi$ ). For first-order logic, the two kinds of entailment coincide by the completeness theorem for the proof calculus in question.
We say that $\varphi$ is valid, or is a logical theorem, in symbols $\vdash \varphi$ , if $\varphi$ is true in every $L$ -structure. We say that $\varphi$ is consistent if $\varphi$ is true in some $L$ -structure. Likewise, we say that a theory $T$ is consistent if it has a model.
We say that two theories S and T in L infinity omega are equivalent if they have the same models, i.e. if Mod(S) = Mod(T). |quote=에 지움 문자가 있음(위치 5) (도움말) (Please note the definition of Mod(T) on p. 30 ...)
↑ 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.

[1] Hodges, Wilfrid (1997). 《A Shorter Model Theory》. New York: Cambridge University Press. 37쪽. Let $L$ be a signature, $T$ a theory in $L_{\infty \omega }$ and $\varphi$ a sentence in $L_{\infty \omega }$ . We say that $\varphi$ is a consequence of $T$ , or that $T$ entails $\varphi$ , in symbols $T\vdash \varphi$ , if every model of $T$ is a model of $\varphi$ . (In particular if $T$ has no models then $T$ entails $\varphi$ .)
Warning: we don't require that if $T\vdash \varphi$ then there is a proof of $\varphi$ from $T$ . In any case, with infinitary languages, it's not always clear what would constitute proof. Some writers use $T\vdash \varphi$ to mean that $\varphi$ is deducible from $T$ in some particular formal proof calculus, and they write $T\models \varphi$ for our notion of entailment (a notation which clashes with our $A\models \varphi$ ). For first-order logic, the two kinds of entailment coincide by the completeness theorem for the proof calculus in question.
We say that $\varphi$ is valid, or is a logical theorem, in symbols $\vdash \varphi$ , if $\varphi$ is true in every $L$ -structure. We say that $\varphi$ is consistent if $\varphi$ is true in some $L$ -structure. Likewise, we say that a theory $T$ is consistent if it has a model.
We say that two theories S and T in L infinity omega are equivalent if they have the same models, i.e. if Mod(S) = Mod(T). |quote=에 지움 문자가 있음(위치 5) (도움말) (Please note the definition of Mod(T) on p. 30 ...)

[2] 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.

[1]

[2]