술어논리(6) ㅡ 해석 하에서 참이란?

$\forall x(x\neq a \rightarrow Ox)$

 를 생각해봅시다. 한번 생각해보세요. 이 문장은 언제나 참입니까, 언제나 거짓입니까, 아니면 둘 다 아닙니까? 그리고 우리가 그것들을 따질 때 어떤 식으로 위의 식을 이해하고 있습니까?

...

 우선 답을 적어봅시다. 답은 위의 문장을 참으로 만드는 해석도, 거짓으로 만드는 해석도 존재한다 입니다.

1. $\mathcal{I}=\{x\in\mathcal{N}| x\text{는 소수}\}$라고 합시다. 그리고, $a^\mathcal{I}=2$라고 하고, $O^\mathcal{I}=\{x\in\mathcal{I}| x\text{는 홀수}\}$라고 합시다. 즉, $O^\mathcal{I}$는 소수들 중에서 홀수들만 모아둔 것입니다. 그렇다면 위의 문장은 참이 될 겁니다. 왜냐면, '모든 $x$'에서 $x$의 범위는 소수들(2,3,5,...)이고, 따라서 해석은 '각각의 모든 소수 $x$에 대하여, $x$가 $2$가 아니면 $x$는 홀수이다'라는 의미가 될 것이기 때문이고 이는 수학적으로 참이기 때문입니다.

2. 만약 $\mathcal{I}=\mathbb{N}$이고, $a$에 대한 해석은 2, $O$에 대한 해석은 홀수들의 집합이라고 한다면 위의 문장은 거짓이 됩니다. 2가 아니더라도 홀수는 무한히 많으니까요..

 비슷한 방식으로 우리는 $\exists x(x\neq a)$ 또한 해석해볼 수 있습니다. 1번이든 2번이든 3은 2와 다르므로 참이 됩니다. 즉, $\mathcal{I}$에서 속하는 어떤 원소 $\alpha = 3$이 있어서 $\alpha\neq a^\mathcal{I}$가 참이 됩니다. 만약 우리가 해석의 원소가 하나밖에 없다고 한다면 거짓인 경우도 만들어낼 수 있습니다. 전체집합에 원소가 하나밖에 없으니까 $a$는 그 원소가 될 수밖에 없고, 그와 다른 원소가 또 존재한다고 위의 문장은 말하므로 거짓이 됩니다.

 우리는 1,2를 본받아서 문장의 참/거짓에 대한 정의를 내릴 것입니다. 사실 책마다, 학파마다 이에 대해 접근하는 방식이 다르지만 우린 복잡하게 가지 않고 바로 참/거짓에 대한 정의를 내리겠습니다. 우린 $\mathcal{I}$가 문장 $\alpha$을 참으로 만든다는 표현을 $\mathcal{I}\models\alpha$ 또는 $\models_\mathcal{I} \alpha$로 쓰고 이를 '$\alpha$는 $\mathcal{I}$ 하에서 만족가능하다(satisfiable)/참이다'라고 부르겠습니다. 이에 대한 정의는 다음과 같이 이루어집니다.

(i)$\alpha$가 원자문장일 때

 원자문장은 원자식 중에서 문장인 식을 뜻합니다. 원자식에서는 변항이 모두 자유롭게 나타나므로 원자문장은 변항이 없는 원자식을 뜻합니다. $\alpha =Pt_1t_2...t_n$인 원자문장이라고 할 때, $\mathcal{I}\models Pt_1...t_n$는 $(t_1^\mathcal{I}, ..., t_n^{\mathcal{I}})\in P^\mathcal{I}$로 정의합니다. 즉, 항들에 대한 해석의 쌍이 술어에 속할 때 원자문장이 참인 것으로 정의합니다.

 가령, 자연수체계 $\mathbb{N}$에서 $t_1=fab$, $t_2=gcd$라고 하고, $f^\mathbb{N}(x,y)=x+y$, $g^\mathbb{N}(x,y)=x\cdot y$라고 하고, $a^\mathbb{N}=2, b^\mathbb{N}=3, c^\mathbb{N}=3, d^\mathbb{N}=4$라고 합시다. 그리고 $P^\mathbb{N}=\{(m,n)|m\text{은 5의 배수}, n\text{는 12의 배수}\}$ 라고 합시다. 그러면 $Pt_1t_2$는 참입니다. 왜냐면 $t_1^\mathbb{N}=f^\mathbb{N}(a^\mathbb{N},b^\mathbb{N})=2+3=5$이고 비슷한 식으로 $t_2^\mathbb{N}=12$이고, $(5,12)$는 $P^\mathbb{N}$의 원소이기 때문입니다.

(ii)$\alpha = \neg\beta$라고 할 때, $\mathcal{I}\models\alpha$는 $\mathcal{I}\not\models\beta=\neg(\mathcal{I}\models\beta)$로 정의합니다. 즉, $\beta$가 거짓일 때 $\alpha$는 참이고, $\beta$가 참일 때 $\alpha$는 거짓으로 정의합니다.

(iii) $\wedge, \vee, \rightarrow$의 경우 모두 명제논리의 진리표에 해당했던 것처럼 똑같이 정의합니다. $\wedge$는 연결사에 의해 서술되는 대상이 모두 참일 때 참으로, 아닐 경우 거짓으로. $\vee$는 양 쪽 중에 하나가 참이면 참으로 정의하고, $\rightarrow$는 실질조건문의 정의에 따라, 전건이 참이고 후건이 참일 때만 거짓으로 정의하고 나머지는 모두 참으로 정의합니다. 같은 말로 전건이 참이거나 후건이 거짓일 때로 정의해도 좋습니다.

(iv) $\alpha= \exists x\beta$이고 $\alpha$가 문장인 경우는,
$\mathcal{I}\models\alpha \Longleftrightarrow\mathcal{I}\models\exists x\beta\Longleftrightarrow \text{어떤}a\in\mathcal{I}\text{에 대해},\quad\mathcal{I}\models\beta_{a'}^x$로 정의합니다.

 $\beta_{a'}^x$는 $\beta$에 나타나는 $x$ 중에서 자유롭게 나타나는 녀석들을 모두 $a'$로 대체시킨다는 말입니다. 이 때 $a'$는 $\mathcal{I}$에 속하는 원소 $a$를 표현하는 개체상항이라고 의미를 고정시킵니다. 즉, $a=(a')^\mathcal{I}$입니다.

 기호만 보면 무슨 소리인가 하실겁니다. 위에서 본 $\exists x(x\neq c)$ 사례를 가져옵시다. 해석을 $\mathcal{I}=\{2,3,4\}$로 생각하고 $c^\mathcal{I}=2$라고 합시다. 그러면, 이 문장이 이 해석 하에서 참인 이유는 '그 어떤 x'를 바로 3(이나 4)으로 했을 때 문장이 참이 되기 때문입니다. 그런데 해석집합의 원소 3은 우리가 다루는 논리기호 밖에 있는 수이기 때문에 문장 안에 직접 넣을 수 없습니다. 그러나 3은 해석집합의 원소, 개체이므로, 개체상항을 추가해서 그 개체상항에 대한 해석을 3으로 하면 될 겁니다. 즉, $a$ 개체상항을 추가해서 $a^\mathcal{I}=3$이라고 한다면, $\mathcal{I}\models a\neq c$ 즉, $a^\mathcal{I}\neq c^\mathcal{I}$이므로 원래 문장이 성립하게 됩니다.

 식이 복잡해보이지만 결국 존재양화사가 들어간 문장의 참/거짓을 다루는 우리의 직관을 기호로 표현한 것에 불과합니다.

(v)$\alpha=\forall x\beta$이고 $\alpha$가 문장인 경우는,
$\mathcal{I}\models\alpha\Longleftrightarrow\mathcal{I}\models\forall x\beta\Longleftrightarrow \text{각각의 모든}a\in\mathcal{I}\text{에 대해},\quad \mathcal{I}\models\beta_a'^x$가 성립한다 로 정의합니다.

 위에서와 마찬가지로, $a'$는 $a\in\mathcal{I}$에 대한 개체상항입니다.

 가령, $\mathbb{N}$이 해석이고, $P^\mathbb{N}$는 $m<n$인 $(m,n)$들의 집합이라고 하고, $c^\mathbb{N}=1$이라고 합시다. 그러면, $\mathbb{N}\models\forall x Pcx$는 $\mathbb{N}$에 속하는 각각의 모든 자연수 $n$에 대해 $\mathbb{N}\models (Pcx)_a^x$ 즉 $\mathbb{N}\models Pcn'$가 성립한다는 것입니다. 이는 각각의 자연수 $n$에 대해 $c^\mathbb{N}<n'^\mathbb{N}$가 성립한다 즉, $1<n$이 성립한다는 것입니다. 그러나 가장 작은 자연수를 $1$로 보면 이는 $1<1$이 되므로 모순입니다. 따라서 위의 식은 자연수 해석 하에서는 거짓입니다.