보존적 확장

수리논리학에서 보존적 확장(保存的擴張, 영어: conservative extension)은 주어진 이론을 확장하되, 원래 이론의 언어로서 나타낼 수 있는 모든 명제의 증명 가능성 여부가 바뀌지 않게 하는 확장이다.

정의

다음 데이터가 주어졌다고 하자.

• 1차 논리 언어 ${\mathcal {L}}$과 그 확장 ${\mathcal {L}}'\supseteq {\mathcal {L}}$
• ${\mathcal {L}}$-문장들의 집합 ${\mathcal {T}}$와 ${\mathcal {L}}'$-문장들의 집합 ${\mathcal {T}}'\supseteq {\mathcal {T}}$

만약 다음 조건이 성립한다면, ${\mathcal {T}}'$이 ${\mathcal {T}}$의 (증명 이론적) 보존적 확장(영어: proof-theoretic conservative extension)이라고 한다.^{:37, Theorem 1.13.2}

$\{\phi \in \operatorname {Sent} ({\mathcal {L}})\colon {\mathcal {T}}\vdash \phi \}=\{\phi \in \operatorname {Sent} ({\mathcal {L}})\colon {\mathcal {T}}'\vdash \phi \}$

즉, ${\mathcal {L}}$로 서술할 수 있는 문장에 대하여, ${\mathcal {T}}$-증명 가능성은 ${\mathcal {T}}'$-증명 가능성과 동치이다.

만약 다음 조건이 성립한다면, ${\mathcal {T}}'$이 ${\mathcal {T}}$의 모형 이론적 보존적 확장(영어: model-theoretic conservative extension)이라고 한다.

• 임의의 ${\mathcal {L}}$-구조 $M$에 대하여 $M\models {\mathcal {T}}$라면, $M'|_{\mathcal {L}}=M$이자 $M'\models {\mathcal {T}}'$인 ${\mathcal {L}}'$-구조 $M'$이 항상 존재한다. (그러나 이는 유일할 필요는 없다.)

성질

이론 ${\mathcal {T}}$의 증명 이론적 보존적 확장 ${\mathcal {T}}'$이 주어졌다고 하자. 그렇다면, ${\mathcal {T}}$가 무모순적인지 여부는 ${\mathcal {T}}'$가 무모순적인지 여부와 동치이다.

$\operatorname {Con} ({\mathcal {T}})\iff \operatorname {Con} ({\mathcal {T}}')$

(여기서 $\bot$은 거짓인 문장이다.)

무모순적 이론 ${\mathcal {T}}$의 확장 ${\mathcal {T}}'$에 대하여, ${\mathcal {T}}'\vdash \operatorname {Con} ({\mathcal {T}})$라면, 괴델의 불완전성 정리에 따라 ${\mathcal {T}}'$은 ${\mathcal {T}}$의 보존적 확장이 아니다.

예

언어 ${\mathcal {L}}$의 1차 논리 문장들의 집합 ${\mathcal {T}}\subseteq \operatorname {Sent} ({\mathcal {L}})$이 주어졌다고 하고, ${\mathcal {T}}$로부터 다음과 같은 꼴의 문장을 증명할 수 있다고 하자.

${\mathcal {T}}\vdash \forall x_{1}\forall x_{2}\cdots \forall x_{m}\exists y_{1}\exists y_{2}\cdots \exists y_{n}\phi (x_{1},\dots ,x_{m},y_{n},\dots ,y_{n})$

여기서 논리식 $\phi$의 자유 변수들은 $x_{1},\dots ,x_{m},y_{n},\dots ,y_{n}$이며, $m,n\in \mathbb {N}$은 자연수이다 (특히, 0일 수 있다).

그렇다면, ${\mathcal {L}}$에 $n$개의 새 $m$항 연산 기호 ${\mathsf {f}}_{1},\dots ,{\mathsf {f}}_{n}$를 추가한 언어를 ${\mathcal {L}}'$이라고 하고,

${\mathcal {T}}'={\mathcal {T}}\cup \{\forall x_{1}\forall x_{2}\cdots \forall x_{m}\phi \left(x_{1},\dots ,x_{m},{\mathsf {f}}_{1}(x_{1},\dots ,x_{m}),\dots ,{\mathsf {f}}_{n}(x_{1},\dots ,x_{m})\right)\}\subseteq \operatorname {Sent} ({\mathcal {L}}')$

을 정의하자. 그렇다면, ${\mathcal {T}}'$은 ${\mathcal {T}}$의 모형 이론적 보존적 확장이다.