전제 일부만 살펴도 무엇을 알 수 있나요?

고전 일차논리의 콤팩트성 정리는 ‘문장 집합 Γ의 모든 유한 부분집합이 만족 가능하다면 Γ 전체도 만족 가능하다’라고 말합니다. 여기서 유한 부분집합은 Γ에서 마음대로 유한 개를 골라 함께 놓은 것이고, ‘모두’라는 말이 중요합니다. 각 부분은 서로 다른 모형에서 만족해도 괜찮습니다. 최종 결론은 전체 Γ를 만족하는 한 모형이 있다는 사실입니다.

완전성에 의해 전체가 모형을 갖지 못하면 ⊥의 형식 증명이 있어야 합니다. 그 증명은 유한하므로 몇 개 전제만 사용합니다. 따라서 전체가 불가능하다면 어떤 유한 부분에서 이미 불가능함이 드러납니다. 이 대우가 콤팩트성의 근거입니다.

전체가 만족 불가능하다는 것은 Γ⊨⊥이라는 뜻입니다. 완전성으로 Γ⊢⊥를 얻습니다. 형식 증명은 유한한 줄로 이루어지므로 실제로 인용한 Γ의 유한 부분 Γ₀가 있습니다. 같은 증명으로 Γ₀⊢⊥이고 건전성에 따라 Γ₀는 만족 불가능합니다. 따라서 모든 유한 부분이 만족 가능하다는 가정과 모순됩니다.

모형이 없다는 의미론적 사실을 형식 증명 존재로 바꾸는 단계가 완전성이고, 유한 부분의 증명에서 모형 부재로 가는 단계가 건전성입니다. 방향을 바꿔 쓰면 논증이 깨집니다.

∃x∃y∃z(x≠y∧x≠z∧y≠z)라고 씁니다. 세 대상의 모든 쌍이 서로 다르다는 뜻입니다. 일반적으로 n개의 변수와 서로 다른 모든 쌍에 대한 비동일성을 적으면 ‘적어도 n개 대상이 있다’는 문장 θₙ을 얻습니다. n은 메타언어에서 지정한 자연수이고, θₙ 하나는 항상 유한 길이의 일차논리 문장입니다.

Γ={θ₁,θ₂,θ₃,…}를 만들 수 있습니다. Γ의 임의의 유한 부분이 요구하는 최대 n을 찾아 그만큼 대상이 있는 모형을 만들면 됩니다. 콤팩트성으로 Γ 전체를 만족하는 모형을 얻고, 그 모형에는 대상이 무한히 많습니다.

각 유한 부분을 만족하는 모형의 크기는 그 부분에서 가장 큰 n에 따라 계속 커질 수 있습니다. 어떤 유한한 크기 N을 고정하면 θₙ 중 n>N인 문장을 만족하지 못합니다. 따라서 Γ 전체의 모형은 유한할 수 없습니다. 콤팩트성이 보장하는 전체 모형은 무한합니다. 부분의 모형들이 하나의 고정된 유한 모형이어야 하는 것은 아닙니다.

그렇지 않습니다. Γ는 크기가 무한하다는 조건만 표현했습니다. 집합의 원소가 무엇인지, 어떤 관계가 성립하는지까지 지정하지 않았으므로 다양한 무한 모형이 가능합니다.

순수한 동일성 언어의 비어 있지 않은 모든 유한 구조만을 정의하는 일차논리 문장 φ가 있다고 가정해 봅시다. φ와 ‘적어도 n개’라는 θₙ을 모든 n에 대해 함께 놓으면, 유한 부분은 충분히 큰 유한 영역에서 만족됩니다. 콤팩트성에 따라 전체에도 모형이 생깁니다. 그런데 θₙ 전부 때문에 모형은 무한해야 하고 φ 때문에 유한해야 하므로 모순입니다. 따라서 이런 단일 문장 φ는 존재하지 않습니다.

‘무한하다’는 조건은 θₙ 전부를 포함하는 이론으로 표현할 수 있습니다. 각각의 θₙ은 유한한 일차논리 문장입니다. 무한한 문장 집합을 사용하는 것과 한 문장으로 표현하는 것은 다릅니다.

이름 cₙ들이 서로 달라야 한다는 조건이 없다면 모두 하나의 아라를 가리키게 할 수 있습니다. D={아라}, P={아라}, 모든 cₙ=아라로 해석하면 Γ 전체를 만족합니다. 이 예에서는 콤팩트성 없이도 한 모형을 직접 전시할 수 있습니다.

모든 i≠j에 대해 cᵢ≠cⱼ를 함께 요구하면 무한 영역이 필요합니다. 이때도 임의의 유한 부분은 유한 크기의 모형으로 만족할 수 있으므로 콤팩트성을 적용할 수 있습니다.

여기에는 이미 {P(a),¬P(a)}라는 두 원소의 만족 불가능한 부분집합이 있습니다. 따라서 ‘모든 유한 부분이 만족 가능하다’는 전제가 성립하지 않습니다. 콤팩트성의 결론을 여기에 적용할 수 없습니다.

물론입니다. 방금 두 문장이 그 예입니다. 각 단일 문장은 만족 가능하지만 두 문장을 함께 놓으면 불가능합니다. 그래서 유한한 모든 조합의 만족 가능성을 확인해야 합니다.

이항 관계 <를 비반사적·추이적인 엄격 순서로 정하고 ∀x∃y(x<y)를 요구한다고 합시다. 영역이 비어 있지 않으며 위로 항상 더 큰 원소가 존재한다면 유한 엄격 순서는 이런 조건을 만족할 수 없습니다. 유한한 엄격 순서에는 극대 원소가 있기 때문입니다. 자연수의 통상적인 < 관계가 이 조건들의 모형입니다.

무한성을 보이는 데에는 비반사성·추이성·모든 x보다 큰 y의 존재만으로 충분합니다. 전제가 강제하는 성질을 정확히 분리해야 합니다. 이 사례는 직접 무한 모형을 제시할 수도 있습니다.

콤팩트성의 결론은 어떤 모형의 존재입니다. 유한 모형의 존재는 보장하지 않습니다. θₙ 전부를 포함하는 사례에서 모든 유한 부분은 유한 모형으로 만족 가능하지만 전체 집합은 오직 무한 모형만 가집니다.

모형을 유한한 구조로만 제한하면 이 형태의 콤팩트성이 성립하지 않습니다. 일차논리 자체의 콤팩트성은 모든 허용된, 유한하거나 무한한 구조를 대상으로 한 정리입니다.

Γ가 B를 의미론적으로 함축한다면 Γ의 어떤 유한 부분 Γ₀도 B를 함축합니다. 완전성으로 Γ에서 B의 유한 증명을 얻고 그 증명에서 실제 사용한 전제만 모으면 됩니다. 이러한 ‘유한 근거’ 관점과 ‘모든 유한 부분이 만족 가능하면 전체도 가능’이라는 관점은 고전 일차논리에서 맞닿아 있습니다.

그 뜻은 아닙니다. 전체 이론이 표현하는 내용은 복잡할 수 있습니다. 다만 특정한 결론 B가 따라온다는 사실은 어느 유한 부분의 전제만으로도 증거를 갖는다는 뜻입니다.

일차논리는 무한성 자체를 표현하는 데 강하지만, 무한 모형의 크기를 딱 하나로 고정하는 데에는 제한이 있습니다. 다음 편에서는 언어의 크기 조건을 붙여 뢴벤하임–스콜렘 정리를 배우고, 셀 수 있는 이론이 셀 수 있는 무한 모형을 갖는다는 결론을 확인합니다.

별도 정리입니다. 콤팩트성은 유한 부분의 만족 가능성과 전체의 만족 가능성을 잇고, 뢴벤하임–스콜렘 정리는 무한 모형의 크기를 바꾸어 살펴봅니다.