모순이 없으면 가능한 세계도 있나요?

문장 집합 Γ가 무모순하다는 것은 Γ에서 모순 기호 ⊥의 증명이 없다는 뜻입니다. 만족 가능하다는 것은 Γ의 모든 문장을 한 모형에서 동시에 참으로 만드는 해석이 있다는 뜻입니다. 하나는 증명의 성질이고, 다른 하나는 해석의 존재를 말합니다.

두 조건의 동치는 일차논리의 중요한 결과입니다. 건전성으로 한 방향을 설명할 수 있으며, 다른 방향은 실제로 모형을 구성하여 확인하겠습니다.

건전성에 따라 Γ에서 정당하게 도출한 문장은 Γ가 참인 모든 모형에서 참입니다. 그런데 ⊥은 어떤 모형에서도 참이 아닙니다. 따라서 Γ를 만족하는 모형이 하나라도 있으면 Γ ⊬ ⊥입니다.

영역을 {아라}로 두고 a가 아라를, P가 {아라}를 가리키게 정하면 Γ={P(a)}를 만족합니다. 그러므로 Γ는 만족 가능하고 무모순입니다.

한 모형에서는 같은 문장이 참이면서 동시에 거짓일 수 없습니다. 두 문장 각각에는 모형이 있어도, 집합 {P(a),¬P(a)} 전체를 만족하는 모형은 없습니다.

유한 집합이든 무한 집합이든 모든 문장을 한 모형에서 동시에 만족시켜야 합니다. 전제마다 다른 모형을 내놓는 것으로는 충분하지 않습니다.

첫 문장은 모든 대상이 P라는 뜻입니다. 둘째 문장은 P가 아닌 대상이 적어도 하나 존재한다는 뜻입니다. 비어 있지 않은 영역의 고전 이값 일차논리에서 두 전제는 동시에 참일 수 없습니다.

존재 제거로 새 c에 대해 ¬P(c)를 임시로 놓고 보편 제거로 P(c)를 얻습니다. 모순 ⊥을 얻은 뒤 새 이름 조건을 지켜 부분 증명 밖으로 내보냅니다.

별개의 상수 기호라도 같은 대상을 가리킬 수 있습니다. P(a)와 P(b)는 두 상수를 모두 아라로 해석하면 한 대상 모형에서도 참입니다.

그때는 두 이름이 서로 다른 대상을 가리켜야 합니다. 이름의 개수와 영역의 크기를 구별하고, 동일성·비동일성의 실제 전제를 따로 확인합니다.

표준 형식 증명은 유한한 길이의 문장과 규칙 적용으로 이루어집니다. Γ에서 ⊥이 도출되면 그 증명에 실제 사용한 전제는 Γ의 유한 부분 Γ₀에 들어 있습니다. 모순의 증거가 있다면 유한한 부분에서 이미 발견할 수 있습니다.

아직 모형의 존재를 보여야 합니다. 유한 증명의 성질과 완전성의 반대 방향을 한 문장으로 묶어 넘어갈 수 없습니다.

모든 cₙ을 같은 아라로 해석하고 P의 외연에 아라를 넣으면 하나의 원소만으로 만족됩니다. 문장이나 이름이 무한하다고 영역도 무한해야 하는 것은 아닙니다.

그때는 서로 다른 대상이 무한히 많이 필요합니다. 각 비동일성 전제가 영역의 크기를 제약합니다.

그럴 수 있습니다. 그러나 고전 논리에서 Γ∪{A}와 Γ∪{¬A} 중 적어도 한쪽은 무모순입니다. 둘 다 모순이면 각각의 가정을 해제하여 Γ에서 ¬A와 A를 얻으므로 Γ가 이미 모순이 되어 버립니다.

이 정리는 두 확장 가운데 일관적인 선택이 존재한다는 뜻입니다. 모든 일차논리 문장의 선택을 효과적으로 판정할 알고리즘이 있다는 주장까지 담고 있지 않습니다.

Γ₀⊆Γ₁⊆Γ₂⊆…가 각 단계에서 무모순하다고 합시다. 합집합에 ⊥의 유한 증명이 생긴다면 그 증명에 쓰인 문장들은 한 단계의 Γₙ 안에 모두 들어갑니다. 그러면 Γₙ도 모순이 되어 가정에 어긋납니다.

수학적 합집합의 존재와 실제 종료하는 계산 절차는 구분합니다. 앞으로 구성에는 무모순성을 유지하는 선택의 존재를 사용합니다.

존재문을 만족시키는 대상을 부를 상수 c를 마련할 수 있습니다. 아직 ∃xA(x)의 참을 결정하지 않았으므로 증거 조건을 ∃xA(x)→A(c)라는 함의식으로 넣습니다. c는 기존 언어와 가정에 등장하지 않는 신선한 이름이어야 합니다.

존재문이 거짓일 가능성도 있기 때문입니다. 존재문이 거짓인 상황에 A(c)를 강제로 추가하면 원래 일관된 집합과 충돌할 수 있습니다.

8편에서는 존재문의 증거 이름을 만들고, 9편에서는 문장과 그 부정 가운데 한쪽을 일관되게 선택합니다. 10편에서는 닫힌 항과 동일성의 동치류로 실제 모형을 만들고, 11편에서 완전성 정리를 도출합니다.

만족 가능한 Γ는 무모순하다는 한 방향입니다. ‘무모순 Γ라면 모형이 있다’는 방향은 앞으로의 구성에서 증명하겠습니다.