일계논리의 구문론은 기호로 이루어진 식을 정의한다. 의미론은 이 기호들을 실제 집합, 함수, 관계로 해석하고 논리식이 언제 참인지를 정한다.
정의 15.1. (\(\mathcal L\)-구조)
\(\mathcal L\)-구조(\(\mathcal L\)-structure) \(\mathcal M\)은 공집합이 아닌 집합 \(M\)과 다음 해석들로 이루어진다.
- 각 \(n\)항 함수기호 \(f\)에 함수 \[ f^{\mathcal M}\colon M^n\to M, \]
- 각 \(n\)항 관계기호 \(R\)에 관계 \[ R^{\mathcal M}\subseteq M^n, \]
- 각 상수기호 \(c\)에 원소 \[ c^{\mathcal M}\in M. \]
여기서 \(M\)을 \(\mathcal M\)의 영역(domain)이라고 부른다. 등호는 항상 \(M\)에서의 실제 동일성으로 해석한다.
변수에 영역의 원소를 대응시키는 함수 \[ s\colon\{x_0,x_1,x_2,\ldots\}\to M \] 을 변수 값매김이라고 부른다. \(a\in M\)일 때 \(s[x\mapsto a]\)는 \(x\)에만 \(a\)를 대응시키고 다른 변수에서는 \(s\)와 같은 값매김을 뜻한다.
정의 15.2. (항의 해석)
구조 \(\mathcal M\)과 변수 값매김 \(s\)가 주어졌을 때 항 \(t\)의 값을 \(t^{\mathcal M}[s]\)로 쓰고 다음과 같이 재귀적으로 정의한다.
\[ \begin{aligned} x^{\mathcal M}[s]&=s(x),\\[3pt] c^{\mathcal M}[s]&=c^{\mathcal M},\\[3pt] f(t_1,\ldots,t_n)^{\mathcal M}[s] &=f^{\mathcal M}\bigl(t_1^{\mathcal M}[s],\ldots,t_n^{\mathcal M}[s]\bigr). \end{aligned} \]
문제 15.1. 언어 \(\mathcal L=\{c,f,g,R\}\)에서 \(c\)는 상수기호, \(f\)는 1항 함수기호, \(g\)는 2항 함수기호, \(R\)은 2항 관계기호라고 하자. 영역이 \[ M=\{0,1,2,3,4\} \] 인 구조 \(\mathcal M\)을 \[ c^{\mathcal M}=1,\quad f^{\mathcal M}(a)=a+1\pmod 5,\quad g^{\mathcal M}(a,b)=a+b\pmod 5 \] 로 정의하자. 값매김 \(s\)가 \(s(x)=2\), \(s(y)=4\)를 만족시킬 때 다음 항의 값을 구하시오.
- \(c\).
- \(f(x)\).
- \(g(x,c)\).
- \(f(g(x,c))\).
- \(g(f(x),f(y))\).
정의 15.3. (만족관계)
구조 \(\mathcal M\), 값매김 \(s\), 논리식 \(\phi\)에 대하여 “\(\phi\)가 \((\mathcal M,s)\)에서 참이다”를 \[ \mathcal M,s\models\phi \] 로 나타낸다. 만족관계는 다음과 같이 재귀적으로 정의한다.
\[ \begin{aligned} \mathcal M,s\models R(t_1,\ldots,t_n) &\quad\Longleftrightarrow\quad \bigl(t_1^{\mathcal M}[s],\ldots,t_n^{\mathcal M}[s]\bigr)\in R^{\mathcal M},\\[3pt] \mathcal M,s\models t_1=t_2 &\quad\Longleftrightarrow\quad t_1^{\mathcal M}[s]=t_2^{\mathcal M}[s],\\[3pt] \mathcal M,s\models\neg\phi &\quad\Longleftrightarrow\quad \mathcal M,s\not\models\phi,\\[3pt] \mathcal M,s\models\phi\to\psi &\quad\Longleftrightarrow\quad \mathcal M,s\not\models\phi\text{ 또는 }\mathcal M,s\models\psi,\\[3pt] \mathcal M,s\models(\forall x)\phi &\quad\Longleftrightarrow\quad \text{모든 }a\in M\text{에 대하여 }\mathcal M,s[x\mapsto a]\models\phi. \end{aligned} \]
약어로 정의한 \(\wedge,\vee,\leftrightarrow,\exists\)는 이에 따라 통상적인 의미를 가진다. 특히 \[ \mathcal M,s\models(\exists x)\phi \quad\Longleftrightarrow\quad \text{어떤 }a\in M\text{에 대하여 }\mathcal M,s[x\mapsto a]\models\phi. \]
문제 15.2. 문제 15.1의 구조에서 \[ R^{\mathcal M}=\{(a,b)\in M^2:a<b\} \] 로 두고, 역시 \(s(x)=2\), \(s(y)=4\)라고 하자. 다음 명제가 참인지 판정하시오.
- \(\mathcal M,s\models R(x,y)\).
- \(\mathcal M,s\models R(f(x),y)\).
- \(\mathcal M,s\models(\exists z)R(z,f(z))\).
- \(\mathcal M,s\models(\forall z)R(z,f(z))\).
- \(\mathcal M,s\models(\forall z)(\exists w)R(z,w)\).
거짓인 경우에는 반례가 되는 영역의 원소를 제시하시오.
문제 15.3. 영역이 \(M=\{0,1,2\}\)인 구조에서 2항 관계 \(R\)을 \[ R^{\mathcal M}=\{(0,0),(1,2),(2,1)\} \] 로 해석하자. 다음 문장의 진릿값을 판정하시오.
- \((\forall x)(\exists y)R(x,y)\).
- \((\exists y)(\forall x)R(x,y)\).
- \((\forall y)(\exists x)R(x,y)\).
- \((\exists x)(\forall y)R(x,y)\).
참인 존재명제에서는 각 경우의 증인을 적고, 한정기호의 순서를 바꾸면 진릿값이 달라질 수 있는 이유를 설명하시오.
다음 보조정리는 14장에서 정의한 치환과 의미론의 관계를 설명한다. 이 보조정리는 뒤에서 건전성 정리를 증명할 때 사용된다.
보조정리 15.4. (치환 보조정리)
항 \(u,t\), 변수 \(x\), 구조 \(\mathcal M\), 값매김 \(s\)에 대하여 \[ (u[t/x])^{\mathcal M}[s] =u^{\mathcal M}\bigl[s[x\mapsto t^{\mathcal M}[s]]\bigr]. \] 또 \(t\)가 논리식 \(\phi\)에서 \(x\)에 대해 자유롭게 대입 가능하면 \[ \mathcal M,s\models\phi[t/x] \quad\Longleftrightarrow\quad \mathcal M,s[x\mapsto t^{\mathcal M}[s]]\models\phi. \]
증명 첫째 식은 항의 구성에 대한 귀납법을 사용하여 증명한다. 둘째 식은 논리식의 구조에 대한 귀납법을 사용하여 증명하며, 전칭 한정기호 단계에서 “자유롭게 대입 가능” 조건이 변수 포획이 일어나지 않음을 보장한다.
다음 보조정리는 문장에서 변수 값매김을 따로 표시할 필요가 없다는 사실을 설명한다.
보조정리 15.5. (자유변수 보조정리)
논리식 \(\phi\)의 모든 자유변수에서 두 값매김 \(s,s'\)가 같은 값을 가지면 \[ \mathcal M,s\models\phi \quad\Longleftrightarrow\quad \mathcal M,s'\models\phi. \] 특히 \(\phi\)가 문장이면 그 진릿값은 변수 값매김과 무관하다.
증명 항과 논리식의 구성에 대한 구조적 귀납법을 적용한다. 아톰논리식의 경우 항의 값이 그 항에 실제로 나타나는 변수의 값에만 의존한다. \(\neg\)와 \(\to\)의 경우에는 귀납가정을 바로 적용하면 된다. \((\forall x)\psi\)의 경우 두 값매김을 각각 \(x\)에서 같은 \(a\in M\)로 바꾸면 \(\psi\)의 자유변수에서 여전히 일치하므로 귀납가정을 적용할 수 있다.
문장 \(\phi\)에 대해서는 \(\mathcal M,s\models\phi\)가 어떤 하나의 값매김에서 성립하면 모든 값매김에서 성립한다. 이때 \[ \mathcal M\models\phi \] 로 쓴다. 문장들의 집합 \(\varSigma\)에 대해 모든 \(\sigma\in\varSigma\)에 \(\mathcal M\models\sigma\)이면 “\(\mathcal M\)이 \(\varSigma\)의 모형이다”라고 말하고 \[ \mathcal M\models\varSigma \] 로 나타낸다. 이러한 모형이 존재하면 “\(\varSigma\)가 만족 가능하다”라고 표현한다.
정의 15.6. (논리적 귀결과 이론)
문장들의 집합 \(\varSigma\)와 문장 \(\phi\)에 대하여 모든 \(\varSigma\)의 모형이 \(\phi\)도 만족시키면 \[ \varSigma\models\phi \] 라고 쓰고 \(\phi\)를 \(\varSigma\)의 논리적 귀결이라고 부른다. \(\varSigma=\varnothing\)일 때 \[ \models\phi \] 라고 쓰며, 이 경우 “\(\phi\)가 논리적으로 유효하다(logically valid)”라고 표현한다.
한 구조 \(\mathcal M\)에서 참인 모든 \(\mathcal L\)-문장의 집합을 \(\mathcal M\)의 이론(theory)이라고 부르고 \[ \operatorname{Th}(\mathcal M) \] 으로 나타낸다.
문제 15.4. 언어가 하나의 2항 관계기호 \(<\)만을 갖는다고 하자. 다음 세 구조를 생각하자. \[ \mathcal N=(\mathbb N,<),\quad \mathcal Z=(\mathbb Z,<),\quad \mathcal F=(\{0,1,2\},<). \] 여기서 \(<\)는 모두 통상적인 순서이다. 다음 문장 가운데 각 구조의 이론에 속하는 것을 판정하시오.
\[ \begin{aligned} \alpha&=(\forall x)\neg(x<x),\\[3pt] \beta&=(\forall x)(\exists y)(x<y),\\[3pt] \gamma&=(\exists x)(\forall y)\neg(y<x),\\[3pt] \delta&=(\forall x)(\forall y)\bigl((x<y)\vee(x=y)\vee(y<x)\bigr). \end{aligned} \]
즉 \(\alpha,\beta,\gamma,\delta\) 가운데 어느 것이 \(\operatorname{Th}(\mathcal N)\), \(\operatorname{Th}(\mathcal Z)\), \(\operatorname{Th}(\mathcal F)\)에 속하는지 각각 구하시오.
예를 들어 \(\mathcal L_{\mathrm{grp}}\)-구조 \(\mathcal M\)이 14장에 적은 세 군 공리를 모두 만족시키면, \(\mu^{\mathcal M}\)을 연산으로 하는 \(M\)은 군이며 \(\epsilon^{\mathcal M}\)은 그 항등원, \(\iota^{\mathcal M}\)는 역원 함수이다.
문제 15.5. 1항 관계기호 \(P,Q\)가 있는 언어를 생각하자. 논리적 귀결과 논리적 유효성의 정의를 사용하여 다음 물음에 답하시오.
- \(\{(\forall x)(P(x)\to Q(x)),\;(\forall x)P(x)\}\models(\forall x)Q(x)\)를 보이시오.
- \(\{(\exists x)P(x)\}\not\models(\forall x)P(x)\)임을 두 원소 구조를 사용하여 보이시오.
- \(\models(\forall x)(x=x)\)임을 보이시오.
- \(\not\models(\exists x)(\forall y)(x=y)\)임을 보이는 구조를 하나 제시하시오.