보존적 확장

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

정의

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

• 1차 논리 언어 $ℒ$과 그 확장 ${ℒ}^{\prime }\supseteq ℒ$
• $ℒ$-문장들의 집합 $𝒯$와 ${ℒ}^{\prime }$-문장들의 집합 ${𝒯}^{\prime }\supseteq 𝒯$

만약 다음 조건이 성립한다면, ${𝒯}^{\prime }$이 $𝒯$의 (증명 이론적) 보존적 확장(틀:Llang)이라고 한다.틀:Rp

$\{\varphi \in \mathrm{Sent}(ℒ):𝒯⊢\varphi \}=\{\varphi \in \mathrm{Sent}(ℒ):{𝒯}^{\prime }⊢\varphi \}$

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

만약 다음 조건이 성립한다면, ${𝒯}^{\prime }$이 $𝒯$의 모형 이론적 보존적 확장(틀:Llang)이라고 한다.

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

성질

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

$\mathrm{Con}(𝒯)⟺\mathrm{Con}({𝒯}^{\prime })$

(여기서 $\mathrm{\perp }$은 거짓인 문장이다.)

무모순적 이론 $𝒯$의 확장 ${𝒯}^{\prime }$에 대하여, ${𝒯}^{\prime }⊢\mathrm{Con}(𝒯)$라면, 괴델의 불완전성 정리에 따라 ${𝒯}^{\prime }$은 $𝒯$의 보존적 확장이 아니다.

예

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

$𝒯⊢\mathrm{\forall }{x}_1\mathrm{\forall }{x}_2\cdots \mathrm{\forall }{x}_m\mathrm{\exists }{y}_1\mathrm{\exists }{y}_2\cdots \mathrm{\exists }{y}_n\varphi (x_1,\dots ,x_m,y_n,\dots ,y_n)$

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

그렇다면, $ℒ$에 $n$개의 새 $m$항 연산 기호 ${𝖿}_1,\dots ,{𝖿}_n$를 추가한 언어를 ${ℒ}^{\prime }$이라고 하고,

${𝒯}^{\prime }=𝒯\cup \{\mathrm{\forall }{x}_1\mathrm{\forall }{x}_2\cdots \mathrm{\forall }{x}_m\varphi (x_1,\dots ,x_m,{𝖿}_1(x_1,\dots ,x_m),\dots ,{𝖿}_n(x_1,\dots ,x_m))\}\subseteq \mathrm{Sent}({ℒ}^{\prime })$

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