다음은 III을 증명할 차례이다. 이를 위해 임의의
S -최대도출일관적이고 ω-완전한 문장집합 ∆를 고려해 보자.
여기서 우리의 목표는 모든 φ ∈ ∆를 참으로 만드는 해석 T 를 구성하는 것이다. 그 해석 T 는 다음과 같다:
I 모든 개체상항 β에 β자체를 할당한다. (예를 들어 ‘a1’에 ‘a1’ 자체를 할당한다.)
I 모든 술어 γ1에 β|γ1β ∈ ∆ 를 할당한다. (예를 들어, ∆에 포함된 술어 ‘F1’을 포함한 원자문장들이 ‘F1a1’, ‘F1b612’, 등이라면,‘F1’에 {‘a1’, ‘b612’, . . .}를 할당한다.)
I 모든 술어 γn>1에 {hβ1. . . βni |γnβ1. . . βn∈ ∆} 를 할당한다.
(예를 들어, ∆에 포함된 술어 ‘G2’을 포함한 원자문장들이
‘G2a1b612’, ‘G2f1a1’, 등이라면,‘G2’에 {h‘a1’, ‘b612’i , h‘f1’, ‘a1’i , . . .}를 할당한다.)
I 모든 문장문자 θ에 θ ∈ ∆이면 T, θ /∈ ∆이면 F를 할당한다.
I 주어진 문장집합 ∆와 앞에 구성한 해석 T 에 대해서 우리는 다음과 같은 점을 보여주고자 한다: L의 모든 문장 φ에 대해서, φ ∈ ∆인 경우 오직 그 경우에만 φ는 T 하에서 참이다.
I 이 점을 보여주기 위해서 우리는 L의 문장들의 연결사와 양화사의 갯수에 수학적 귀납법을 적용한다: 그 갯수가 0인 경우, 즉 L의 원자문장들 φ는 모두 그 구성에 의해서 φ ∈ ∆인 경우 그리고 그 경우에만 φ가 T 하에서 참이다. 이것은 해석 T 의 구성에 의해서 명백하다.
I 그 갯수가 k보다 작은 모든 ψ에 대해서 ψ ∈ ∆인 경우 오직 그 경우에만 ψ가 T 하에서 참이라 가정하자. 이제 그 갯수가 k인 모든 φ에 대해서 φ ∈ ∆인 경우 오직 그 경우에만 φ가 T 하에서 참이라는 것을 보인다. 우리는 다음 경우들 각각에 대해서 그 점을 보여야 한다: (i) φ = −ξ, (ii) φ = (ξ&χ), (iii) φ = (ξ ∨ χ), (iv) φ = (ξ → χ), (v) φ = (ξ ↔ χ), (vi)
φ = (α) ξ, (vii) φ = (∃α) ξ.
증명: 완전성 (계속)
I 이 가운데 우리는 (i), (ii), (vii)만 살펴볼 것이다. (나머지 경우들은 비슷하다.)
I (i) φ = −ξ인 경우: 가정에 의해서, ξ ∈ ∆이고 ξ가 T 하에서 참이던지, ξ /∈ ∆이고 ξ가 T 하에서 거짓이다. 전자의 경우 (1) 에 의해 φ /∈ ∆이고 φ가 T 하에서 거짓이며, 후자의 경우 (1)에 의해 φ ∈ ∆이고 φ가 T 하에서 참이다.
I (ii) φ = (ξ&χ)인 경우: 네 가지 경우를 생각할 수 있다. 첫째, ξ, χ ∈ ∆이고 ξ, χ가 T 하에서 참. 이 경우 φ ∈ ∆이고 T 하에서 참. 둘째, ξ ∈ ∆, χ /∈ ∆이고 ξ가 T 하에서 참, χ가 T 하에서 거짓. 이 경우 φ /∈ ∆이고 (왜?) T 에서 거짓. 셋째, ξ /∈ ∆, χ ∈ ∆이고 ξ가 T 하에서 거짓, χ가 T 하에서 참. 앞 경우와 유사. 넷째, ξ, χ /∈ ∆이고 ξ, χ가 T 하에서 거짓. 이 경우 φ /∈ ∆이고 T 하에서 거짓. 어느 경우건 φ ∈ ∆인 꼭 그 경우 φ는 T 하에서 참이다.
I (vii) φ = (∃α) ξ인 경우. 한편으로 φ ∈ ∆라고 가정하자. ∆는 ω-완전하기 때문에 어떤 개체상항 β에 대해서 ξα/β ∈ ∆이다.
가정에 의해 ξα/β는 T 하에서 참이다. T 는 스스로의
β-변형이기 때문에 (∃α) ξ는 T 하에서 참이다. 다른 한편으로 φ는 T 하에서 참이라고 가정하자. T 의 논의영역은 L의 모든 개체상항들의 집합이며, 각각의 개체상항은 그 자신에 의해 지시된다. 이 조건 아래에서는 (∃α) ξ가 T 하에서 참이면 어떤 개체상항 β에 대해 ξα/β가 T 하에서 참이라는 점이 쉽게 증명된다. 주어진 가정에 의해서 ξα/β ∈ ∆이다. 따라서
∆ `S (∃α) ξ이다. 그렇다면 (2)에 의해서 (∃α) ξ ∈ ∆이다.
종합하자면, 이 경우에도, φ ∈ ∆인 꼭 그 경우 φ는 T 하에서 참이다.
증명: 완전성 (계속)
I 그러므로 임의의 갯수의 연결사 및 양화사들을 포함한 L의 문장 φ에 대해서, φ ∈ ∆일 경우 오직 그 경우에만 φ는 T 하에서 참이다.
I 결과적으로 ∆는 해석일관적이다. 우리는 이것을 ∆가 S -최대도출일관적이고 ω-완전하다는 가정만을 사용하여 증명하였으므로 III이 증명되었다.
I II와 III이 증명되었고, 이미 지적한 대로 II와 III은 I’을
함축한다. I’은 I을 함축하고, I은 다시 (서로 동치인) C1-C3를 함축한다. C1은 바로 S가 완전하다는 주장이므로, 우리가 원하던 대로 S의 완전성이 증명되었다.