문장으로 만든 세계에서 왜 그 문장이 참이 되나요?

지금까지 얻은 T는 헨킨 증거 조건을 지닌 극대 일관 문장 집합입니다. 모든 닫힌 문장 A에 대해 A 또는 ¬A 가운데 하나가 T에 있습니다. 하지만 T는 여전히 종이 위에 적힌 문장들의 모음입니다. 이를 실제로 만족하는 구조 M을 구성해야 ‘무모순한 집합에는 모형이 있다’는 말을 입증할 수 있습니다. 영역과 기호의 해석을 정하고 모든 문장에 대해 참을 확인하겠습니다.

언어에 이미 있는 닫힌 항들을 재료로 씁니다. 상수 c와 함수항 f(c), f(f(c))처럼 자유변수가 전혀 없는 항을 모으면 됩니다. 앞 편에서 상수 하나를 확보했으므로 닫힌 항의 집합이 비어 있지 않습니다.

같은 대상을 나타내는 항들이 있을 수 있습니다. T가 t=u를 포함할 때 t∼u라고 정의합니다. 동일성 규칙으로 반사성·대칭성·추이성이 성립하므로 ∼는 동치관계입니다. 닫힌 항 t의 동치류를 [t]로 쓰고, 모형의 영역 D를 모든 닫힌 항 동치류의 집합으로 둡니다.

항 a,b는 서로 다른 문자열이어도 [a]=[b]입니다. 그러나 T가 a≠b를 포함하면 두 동치류는 달라야 합니다. 구문상의 이름과 모형 속의 대상 사이를 동일성 정보로 연결한 것입니다.

동치류는 대표 항을 여럿 갖기 때문에 그 정의가 대표 선택과 무관해야 합니다. 만약 [s]=[t]이면 s=t∈T입니다. 동일성에 관한 합동 규칙으로 f(s)=f(t)∈T가 따라옵니다. 따라서 [f(s)]=[f(t)]입니다. 여러 인자를 갖는 함수도 인자마다 이 근거를 반복해 정의가 잘 정해졌음을 보입니다.

상수 a가 가리키는 대상을 [a]로 둡니다. 함수 f는 모든 동치류 입력에 대응하는 출력 동치류를 주므로 영역 위의 전체 함수가 됩니다. 이 구성에서 ‘대표를 바꾸어도 결과가 같다’는 확인을 생략하면 함수 해석이 불명확합니다.

한 자리 술어 P의 외연을 {[t]: P(t)∈T}로 정합니다. 두 자리 관계 R도 R(t,u)∈T인지에 따라 동치류의 쌍을 포함시킵니다. 동일성 치환 규칙 때문에 [t]=[s]인 경우 P(t)와 P(s)의 T-소속은 같으므로 어떤 대표를 써도 술어 해석은 잘 정의됩니다.

동일성 제거와 연역적 닫힘으로 P(b)∈T입니다. 따라서 모형에서 P([a])와 P([b])는 둘 다 참입니다. 술어의 외연이 대표 항의 선택에 의존하지 않는다는 직접 사례입니다.

가장 단순한 원자식부터 봅니다. t=u가 M에서 참인 것은 [t]=[u]라는 뜻이고, 바로 t=u∈T와 같습니다. P(t)가 M에서 참인 것은 [t]가 P의 외연에 든다는 뜻이며 역시 P(t)∈T와 같습니다. 거짓을 나타내는 ⊥은 어떤 모형에서도 참이 아니며, 무모순한 T에도 들어 있지 않습니다.

맞습니다. 동일성·술어 원자식·⊥에 대해 ‘모형에서 참 ↔ T에 속함’을 보이고, 그 뒤 연결사와 양화사로 식을 만드는 단계마다 같은 성질이 유지됨을 확인하는 구조적 귀납을 시작합니다.

모형에서 ¬A가 참이려면 A가 거짓이어야 합니다. 귀납 가정으로 ‘A가 모형에서 참 ↔ A∈T’가 이미 성립한다고 놓습니다. 극대 일관성에 따라 A가 T에 없을 때에만 ¬A가 T에 있습니다. 그러므로 ¬A가 모형에서 참인 조건과 T에 있는 조건이 정확히 맞습니다.

A∧B가 모형에서 참이려면 두 부분식이 모두 참입니다. 귀납 가정으로 이는 A,B가 모두 T에 있다는 뜻이고, 극대 일관 집합의 연역적 닫힘과 ∧ 도입·제거를 사용하면 A∧B∈T와 동치입니다. ∨와 →도 해당 연결사의 진리 조건과 T의 성질을 이용해 같은 방식으로 진행합니다.

앞서 모든 존재 요구마다 마련해 둔 헨킨 증거 조건을 사용합니다. ∃xA가 T에 있으면 적절한 닫힌 증거항 c에 대해 A(c)∈T를 얻습니다. 귀납 가정으로 M에서 A는 x에 [c]를 배정할 때 참입니다. 따라서 M⊨∃xA입니다. 반대 방향으로 M에서 ∃xA가 참이면 어떤 원소 [t]가 증인입니다. 귀납 가정으로 A(t)∈T이고 존재 도입과 연역적 닫힘으로 ∃xA∈T입니다.

우리가 영역을 닫힌 항의 동치류로 만들었으므로 그렇습니다. 일반 모형에서는 이 성질이 필수인 것은 아니지만, 지금 만드는 항 모형에서는 모든 원소에 이름 역할을 하는 항이 있습니다.

항 모형의 모든 대상은 닫힌 항의 동치류 [t]입니다. ∀xA가 T에 있다면 보편 제거로 모든 닫힌 t에 대해 A(t)가 T에 있고, 귀납 가정으로 모든 [t]에서 A가 참입니다. 그러므로 M에서 ∀xA가 참입니다.

만약 ∀xA가 T에 없다면 극대 일관성으로 ¬∀xA가 T에 들어갑니다. 고전 일차논리의 양화 동치에 따라 ∃x¬A가 T에 있고, 헨킨 증거항 c에 대해 ¬A(c)가 T에 있습니다. 따라서 M의 [c]에서 A가 거짓이므로 ∀xA도 거짓입니다. 이렇게 두 방향을 확인합니다.

문장에 대한 진리 보조정리를 중심으로 설명했습니다. 자유변수가 있는 식 A(x,y)에는 배정 g를 정해야 합니다. 항 모형에서 g(x)와 g(y)는 각각 어떤 닫힌 항의 동치류 [t]와 [u]입니다. 포획되지 않도록 동시에 대입한 닫힌 문장 A(t,u)를 살펴보면 대입 보조정리에 의해 M,g⊨A(x,y)와 M⊨A(t,u)의 참거짓이 같습니다.

닫힌 항에는 자유변수가 없으므로 대입 과정에서 새 자유변수가 양화사에 잡히는 문제가 발생하지 않습니다. 여러 변수의 동시 대입에서도 각 항의 값을 원래 배정에서 구한다는 원칙을 유지합니다.

언어에 상수 a,b와 술어 P만 있고 함수는 없다고 합시다. T가 a=b와 P(a)를 포함하는 극대 일관 집합이라면, 닫힌 항은 a와 b이며 영역은 하나의 동치류 D={[a]}입니다. a와 b는 모두 그 원소를 가리키고 P의 외연도 그 원소를 포함합니다. 이 작은 모형에서 P(a)∧P(b)∧a=b가 참입니다.

그때는 동치류가 두 개입니다. P(a)만으로 P(b)의 참은 정해지지 않으며 T가 P(b)와 ¬P(b) 중 어느 쪽을 포함하는지 따라 P의 외연이 달라집니다. 모두 결정했다는 약속이 실제 술어 해석을 정합니다.

문장을 하나하나 확인하는 유한 실험으로는 일반 정리가 나오지 않습니다. 대신 원자식에서 시작하여 식을 만드는 각 연결사·양화사에서 참과 소속의 일치를 보존함을 증명합니다. 식은 유한한 구문 나무를 가지므로 구조적 귀납이 모든 식에 적용됩니다. 그 결과 이 항 모형은 T의 모든 닫힌 문장을 동시에 만족합니다.

T가 무모순하고 극대 일관하며 헨킨 증거 조건을 갖추었다는 사실입니다. 동일성 규칙도 모형 구성의 대표 선택 독립성을 위해 필요합니다. 이 가정들이 서로 맞물려 ‘문장으로 만든 세계’가 실제로 그 문장들을 참으로 만듭니다.

T는 원래 무모순 집합 Γ를 포함하도록 구성했으므로 M은 Γ의 모든 문장도 만족합니다. 따라서 무모순한 Γ에는 모형이 있다는 결과를 얻었습니다. 다음 편에서는 이 모형 존재 정리로부터 Γ⊨B ⇒ Γ⊢B, 곧 일차논리의 의미론적 완전성을 결론내립니다.

맞습니다. 건전성은 증명에서 모든 모형의 참으로 갑니다. 완전성은 모든 전제 모형에서의 참으로부터 증명 존재로 돌아옵니다. 지금까지 모형을 만들었던 까닭이 그 두 번째 길을 연결하기 위해서입니다.