일계논리의 건전성과 완전성

By | August 18, 2017

일계논리언어 \(\mathcal{L}\)에서 논리식 \(\phi\)가 논리적으로 유효하다(logically valid)는 것은 임의의 \(\mathcal{L}\)-구조 \(M\)과 \(M\)에서의 임의의 값매김에 대하여 \(\phi\)의 값이 \(\mathrm{T}\)가 되는 것을 의미한다. 만약 \(\phi\)가 문장이면 \(\phi\)의 참거짓 여부는 값매김에 영향을 받지 않고 오직 구조에 의해서만 결정된다. 그러므로 다음을 얻는다.

문장 \(\phi\)가 논리적으로 유효할 필요충분조건은 임의의 \(\mathcal{L}\)-구조 \(M\)에 대하여 \(M \models \phi\)인 것이다.

위 정리에 의하면, 논리식 \(\phi\)가 논리적으로 유효하지 않다는 것을 보이려면 \(M \models \phi\)가 성립하지 않는 구조 \(M\)을 하나만 만들어내면 된다. 그러나 위 정리는 문장이 논리적으로 유효한지를 밝히는 데에 도움을 주는 것처럼 보이지 않는다. 왜냐하면 모든 구조를 다 고려하는 것은 어려운 일이기 때문이다. 하지만 형식계에서는 그것이 가능하다. 다음 정리에서 논리식이 유효함을 보이려면 그것의 증명을 찾아내는 것으로 충분함을 보일 것이다. 이것이 일계논리의 완전성 정리이다. 또한 그 역이 성립하는데, 그것은 일계논리의 건전성 정리이다.

명제논리에서와 마찬가지로 일계논리의 건전성 정리와 완전성 정리도 더 일반화된 것이 있다. 즉 논리식이 논리식의 집합 \(\varSigma\)로부터 추론될 필요충분조건은 논리식이 \(\varSigma\)의 논리적 귀결(logical consequence)인 것이다. 또한 이것을 '무모순성'과 관련하여 진술할 수도 있다. 즉 논리식의 집합이 무모순일 필요충분조건은 그것이 (적당한 \(\mathcal{L}\)-구조의 적당한 값매김에 의하여) 만족될 수 있는 것이다.

정리 1.  일계논리의 건전성과 완전성.
\(\mathcal{L}\)이 가산 개의 함수기호, 관계기호, 상수기호를 가진 일계논리언어라고 하자.

(ⅰ) 논리식 \(\phi\)가 논리적으로 유효할 필요충분조건은 \(\phi\)가 정리인 것이다.

(ⅱ) \(\varSigma\)가 논리식의 집합이고 \(\phi\)가 논리식일 때, \(\phi\)가 \(\varSigma\)의 논리적 귀결일 필요충분조건은 \(\phi\)가 \(\varSigma\)로부터 추론될 수 있는 것이다.

(ⅲ) \(\varSigma\)가 논리식의 집합일 때, \(\varSigma\)가 무결할 필요충분조건은 \(\mathcal{L}\)-구조 \(M\)과 값매김 \(v\)가 존재하여 \(\varSigma\)의 모든 논리식의 값이 \(\mathrm{T}\)가 되는 것이다.

건전성 정리와 완전성 정리의 엄밀한 증명은 대단히 길다. 여기서는 간략하게 살펴보자.

건전성 정리의 증명

(ⅱ)에서 \(\varSigma\)를 공집합으로 두면 (ⅰ)을 얻는다. 즉 (ⅰ)은 (ⅱ)의 특별한 경우이므로 여기서는 (ⅱ)를 증명한다. \(\phi\)가 \(\varSigma\)에서 증명 가능하다는 가정 하에 \(\varSigma\)의 모든 논리식이 참이 되도록 하는 임의의 구조와 그 구조의 값매김에 대하여 \(\phi\)가 참임을 보여야 한다. \(\varSigma\)로부터의 \(\phi\)의 증명 길이에 대한 수학적 귀납법을 이용하여 이것을 보일 수 있다.

만약 한 줄짜리 증명이 존재한다면 \(\phi\)는 \(\varSigma\)에 속하거나 또는 그 자체로서 공리이다. 만약 \(\phi\)는 \(\varSigma\)에 속한다면 가정에 의하여 \(\phi\)는 참이다. 공리 (A1), (A2), (A3)은 명제논리적 항진이다. 공리 (A4), (A5)는 구조의 값매김을 이용한 추론을 필요로 한다. 예컨대 (A5)를 살펴보자. \(M\)이 구조이고 \(v\)가 값매김이라고 하자. 함의를 위한 진리표를 이용하여, \(v((\forall x)(\phi \rightarrow \psi ))=\mathrm{T}\)이고 \(v(\phi ) = \mathrm{T}\)일 때 \(v((\forall x )\psi ) = \mathrm{T}\)임을 보이면 충분하다. [\(x\)가 \(\phi\)의 자유변수가 아니라는 점을 기억하자.] 그러므로 \(v '\)이 \(x =x_i\)인 조건 하에 \(v\)와 \(i\)-근접한 임의의 값매김일 때 \(v'(\psi )=\mathrm{T}\)임을 보여야 한다. \(v((\forall x)(\phi \rightarrow \psi ))=\mathrm{T}\)로부터 \(v ' (\phi \rightarrow \psi )=\mathrm{T}\)를 얻으므로, \(v'(\phi ) = \mathrm{F}\) 또는 \(v' (\psi )=\mathrm{T}\)이다. 그런데 \(x\)는 \(\phi\)의 자유변수가 아니므로 \(v'(\phi )=v(\phi ) = \mathrm{T}\)이다. 그러므로 \(v'(\psi )=\mathrm{T}\)로서 원하는 결론을 얻는다.

(E1)-(E4)의 유효성은 등호의 해석으로부터 자명하게 성립한다.

Modus Ponens가 논리식의 진리 여부를 보존한다는 것은 명제논리에서 논할 때와 마찬가지로 진리표에 의하여 보장된다. 그러므로 일반화에 대하여 논하자. \(v(\phi )=\mathrm{T}\)이고 \(x=x_i\)가 \(\varSigma\)에서 나타나지 않는 변수라고 하자. 그러면 \(v\)와 \(i\)-인접한 임의의 값매김 \(v'\)은 \(\varSigma\)에서 \(v\)와 같은 값매김이 된다. [\(x_i\)가 \(\varSigma\)에서 자유변수로 나타나지 않기 때문이다.] 따라서 귀납적 가정에 의하여 \(v'(\phi )=\mathrm{T}\)가 성립한다. 그러므로 정의에 의하여 \(v((\forall x)\phi )=\mathrm{T}\)를 얻는다.

이제 (ⅱ)를 이용하여 (ⅲ)을 보이자. \(\varSigma\)가 값매김 \(v\)에 의하여 만족될 수 있고 \(\varSigma\)가 무결하지 않다면 모순이 존재하게 된다. 즉 \(\varSigma\)에서 \(\phi\)와 \((\lnot \phi )\)가 모두 추론 가능한 경우가 발생하게 된다. 그런데 (b)에 의하여 \(v(\phi ) = v((\lnot \phi )) = \mathrm{T}\)이므로, 이러한 모순은 발생할 수 없다.

완전성 정리의 증명

먼저 (ⅲ)만 증명하면 충분하다는 사실을 보이자. \(\phi\)가 \(\varSigma\)의 논리적 귀결이라고 하자. 그러면 \(\varSigma \cup \left\{(\lnot \phi )\right\}\)는 어떠한 구조와 어떠한 값매김에 의해서도 만족될 수 없다. (ⅲ)에 의하여 \(\varSigma \cup \left\{(\lnot \phi )\right\}\)는 무모순적이다. 명제논리의 항진인 \[((\lnot p_1 )\rightarrow (p_1 \rightarrow p_2 ))\] 와 Modus Ponens를 이용하면 필요로 하는 모든 것을 증명할 수 있다. 예컨대 \(\alpha\)가 공리 중 하나일 때 \((\lnot \alpha)\)를 추론할 수 있다. 추론 정리에 의하여 \(\varSigma\)로부터 \(((\lnot \phi )\rightarrow (\lnot \alpha ))\)를 추론할 수 있다. 이제 \(\varSigma\)로부터 다음과 같은 추론을 얻는다. \[ \begin{eqnarray} \varSigma &\,\,\vdash\,\,& ((\lnot \phi )\rightarrow (\lnot \alpha )) \\[8pt] \varSigma &\,\,\vdash\,\,& (((\lnot \phi )\rightarrow (\lnot \alpha )) \rightarrow ( \alpha \rightarrow \phi )) \\[8pt] \varSigma &\,\,\vdash\,\,& (\alpha \rightarrow \phi ) \\[8pt] \varSigma &\,\,\vdash\,\,& \alpha \\[8pt] \varSigma &\,\,\vdash\,\,& \phi \end{eqnarray} \] 이로써 (ⅲ)을 증명하는 일만 남았다. 지금부터 (ⅲ)을 네 단계로 나누어 증명한다. 앞서 밝힌 바와 같이 여기서는 간략한 증명을 살펴보자.

제 1 단계.

먼저 \(\mathcal{L}\)에 지금까지 나타나지 않은 상수들의 무한열 \((c_0 ,\, c_1 ,\, c_2 ,\, \cdots )\)를 추가하여 확장한다. 확장한 후에도 언어는 여전히 가산이다. 이 상수들은 나중에 존재문장[\( (\exists x ) p\)꼴의 문장]의 진리 여부를 '목격'하는 역할을 하게될 것이다.

\(\mathcal{L}\)의 논리식 중에서 단 하나의 자유변수만을 갖는 것 전체를 나열하여 \(\alpha _0 ,\) \(\alpha _1 ,\) \(\alpha_2 ,\) \(\cdots\)로 나열하자. 또한 \(\alpha_m\)에 나타나는 자유변수를 \(x_{i_m}\)이라고 하자. \((c_0 ,\, c_1 ,\, c_2 ,\, \cdots )\)의 부분열 \((d_0 ,\, d_1 ,\, d_2 ,\, \cdots )\)를 잡되, \((d_0 ,\, d_1 ,\, d_2 ,\, \cdots )\)의 모든 항이 서로 다르고, \(m\leq n\)일 때 \(\alpha_m\)에서 \(d_n\)이 나타나지 않도록 하자. 이제 \[((\lnot (\forall x_{i_n} )\alpha _n ) \rightarrow (\lnot \alpha_n [d_n / x_{i_n} ] ))\] 을 \(\theta_n\)으로 나타내자. 만약 \(\phi = (\lnot \alpha_n ) ,\) \(x=x_{i_n}\)에 대하여 \((\exists x)\phi\)가 무모순적이면 \(d_n\)은 '목격자'가 되고 \(\phi [d_n / x]\)는 우리가 다루는 구조에서 참이 된다.

\(\theta_n\)을 \(\varSigma\)에 추가한 집합 \(T\)가 여전히 무모순적임을 보이자. 만약 \(\theta_n\)을 추가한 집합이 무모순적이지 않다면 \(\varSigma\)에 문장 \[((\lnot (\forall x_{i_n} )\alpha _n)\rightarrow (\lnot \alpha _n [d_n / x_{i_n} ]))\] 을 추가했을 때 모순이 유도된다. 이 모순을 유도한 증명의 어디에도 나타나지 않는 새로운 변수를 잡아서 \(x\)라고 두자. 일반화 공리와 추론 정리를 이용하면 \[(\alpha [x/x_{i_n} ]\rightarrow (\forall x_{i_n} )\alpha _n )\] 이 유도되며, 명제논리의 항진을 이용하면 다음을 얻는다. \[((\lnot (\forall x_{i_n} )\alpha _n )\rightarrow (\lnot \alpha_n [x/x_{i_n}]))\] 모순을 유도한 증명에서 \(d_n\)을 \(x\)로 치환하면 \(\varSigma\)로부터의 모순의 증명을 얻는다. 그런데 \(\varSigma\)가 무모순적이므로 이것은 성립할 수 없다. 그러므로 \(\varSigma\)에 \(\theta_n\)을 추가해도 무모순적이다.

제 2 단계.

명제논리의 긴밀성을 증명할 때 결정적인 역할을 했던 다음 내용을 보조정리로 사용하자. 이 보조정리의 증명은 명제논리에서 살펴본 것과 동일하다. 집합 \(\varSigma\)가 완전하다(complete)는 것은 임의의 논리식 \(\phi\)에 대하여 \(\phi\) 또는 \((\lnot \phi )\) 둘 중 하나가 \(\varSigma\)에 속하는 것을 의미한다.

보조정리 1.

(a) \(\varSigma\)가 논리식의 집합이고 무모순적이면 \(\varSigma \cup \left\{ \phi \right\}\)와 \(\varSigma \cup \left\{(\lnot \phi )\right\}\) 중 하나는 무모순적이다.

(b) \(\varSigma\)가 무모순적이면 \(\varSigma\)를 포함하고 완전하고 무모순인 집합이 존재한다.

모든 논리식을 \((\phi_0 ,\, \phi_1 ,\, \phi_2 ,\, \cdots)\)로 나열하고 \(n\)째 단계에서 \(\phi_n\) 또는 \((\lnot \phi_n )\) 중 추가하였을 때 무모순성이 유지되는 것을 골라 추가함으로써 (b)가 증명된다.

보조정리 1에 의하여 무모순인 집합 \(T\)를 확장하여 완전하고 무모순인 집합 \(T^+\)를 얻는다.

제 3 단계.

\(T^{+}\)를 이용하여 원래의 집합 \(\varSigma\)를 만족시키는 구조를 구성하자. 변수를 갖지 않는 항을 닫힌항(closed term)이라고 부른다. 구조 \(M\)의 항 중에서 닫힌 것을 모두 모아 \(V\)라고 하자. 모든 상수기호는 닫힌항이므로 상수기호는 그 자체로서 해석한다. 특히 모든 '목격자'는 \(V\)에 속한다.

\(f\)가 \(n\)항함수이고 \(t_1 ,\) \(t_2 ,\) \(\cdots ,\) \(t_n\)이 닫힌항일 때 \(t_1 ,\) \(t_2 ,\) \(\cdots ,\) \(t_n\)을 \(f\)에 입력한 결과를 \(f(t_1 ,\, t_2 ,\, \cdots ,\,t_n )\)으로 나타낸다. 이 값은 닫힌항이므로 \(V\)에 속한다.

\(R\)가 \(n\)항관계기호이고 \(t_1 ,\) \(t_2 ,\) \(\cdots ,\) \(t_n\)이 닫힌항이라고 하자. 이때 \(R(t_1 ,\, t_2 ,\, \cdots ,\,t_n )\)이 참일 필요충분조건은 이 문장이 \(T\)로부터 추론 가능한 것으로 정의한다.

이로써 구조 \(M\)을 구성하였다.

제 4 단계.

이와 같은 방법으로 만든 구조 \(M\)은 우리가 바라던 구조가 아니다. \(T\)의 두 닫힌항이 서로 같을 수 있기 때문이다. 그러므로 \(M\)에 적당한 동치관계를 준 뒤 상집합을 취해야 한다. \(V\)에서의 관계 \(\sim\)을 '\(t_1 \sim t_2\)일 필요충분조건은 \(T\)로부터 \((t_1 = t_2 )\)가 추론되는 것'으로 정의한다. 그러면 공리 (E1)-(E3)에 의하여 \(\sim\)은 동치관계이다.

이제 \(\sim\)에 의한 \(M\)의 상집합을 \(\overline{M} = M/\sim \)이라고 하자. 그러면 \(\overline{M}\)이 \(\varSigma\)의 모델이다.

이로써 일계논리의 완전성이 증명되었다.

언어가 비가산인 경우

우리는 언어가 가산인 경우의 건전성 정리와 완전성 정리를 살펴보았다. 군론이나 자연수계와 같이 수학의 많은 분야에서 언어가 가산인 경우의 정리만으로도 이론을 전개하는 데에 충분하다. 그러나 그렇지 않은 분야도 있다. 예컨대 \(F\)가 체(field)일 때 \(F\) 위에서의 벡터공간을 일계논리로 다루려면 각 \(c\in F\)에 대한 단항함수기호(스칼라 \(c\)의 곱을 나타내는 기호)가 필요하므로, \(F\)가 비가산인 경우 일계논리도 비가산 개의 상수기호를 갖게 된다.

일계논리의 완전성을 증명하는 과정에서 언어의 가산성을 사용한 부분은 1단계와 2단계이다. 이들 단계에서 논리식을 한 줄로 나열하여 열을 만들었으며, 이 열을 만들 때 귀납적 구성 방법을 사용하였다. 언어가 가산이 아닌 경우에는 논리식들의 모임을 정렬집합으로 간주하고 초한귀납법을 사용할 수 있다면 이와 같은 방법을 그대로 사용할 수 있다.

따라서 논리식들의 집합이 정렬집합일 때 그 집합에 우리가 사용한 방법을 그대로 사용할 수 있는지의 여부를 밝히는 것이 필요하다. 이 내용은 Löwenheim-Skolem 정리와 선택 공리에 대하여 논할 때 함께 살펴볼 것이다. 여기서는 \(\mathcal{L}\)이 가산일 때뿐만 아니라 \(\mathcal{L}\)이 정렬집합일 때에도 건전성과 완전성을 가진다는 사실만 알아두기로 하자. 언어에서 기호들의 집합이 정렬집합이면 유한 개의 기호들로 구성된 문자열들의 집합 또한 정렬집합이므로 논리식들의 집합도 정렬집합이다. 이 결과를 요약하면 다음과 같다.

정리 4. 언어 \(\mathcal{L}\)의 기호들의 집합이 정렬집합일 때 이 언어는 건전성과 완전성을 가진다.

ZFC에서는 Zermelo의 정렬 정리에 의하여 임의의 집합이 정렬 가능하다. 따라서 다음을 얻는다.

정리 5. ZFC에서 일계논리는 건전성과 완전성을 가진다.

Leave a Reply