기호논리학
I 임의의 논리식 φ, 서로 다른 (즉，어떠한 두 개도 동일하지 않은) 변항들 α1, . . . , αn, 그리고 (꼭 다를 필요가 없는)
개체기호들 β1, . . . , βn에 대해, φαβ11,...,β...αnn은 φ속에 있는 모든
자유변항들 α1, . . . , αn을 개체상항 β1, ..., βn으로 각각 치환한
결과이다.
I 예를 들어 , 만일 φ = ‘(x)(Fxyz → (∃z)Gzyua)’, α1 = ‘y0,
α2= ‘u’, β1 = ‘a’, 그리고 β2= ‘b’라면, 논리식 φαβ11βα22는
정의: 도출과 타당성
I X 를 어떤 추론규칙들의 집합이라고 하자. 예를 들어, 그것은 바로 우리들의 추론규칙들의 집합, 즉 {P, T, C, US, UG,E}일 수도 있다. I 모든 규칙집합 X , 문장 φ, 문장집합 Γ에 대해서, Γ `X φ이라는 것은 φ가 Γ로부터 X 에 속하는 추론규칙들에 의해 도출된다는 것이다. 특히 Γ는 공집합일 수 있으며, 그 경우 `X φ으로 쓰며, 이때 φ는 X 의 추론규칙들을 포함하는 논리학의 정리이다. I 모든 문장 φ와 문장집합 Γ에 대해서, Γ |= φ이라는 것은 φ가 Γ 의 귀결이라는 것이다. 특히 Γ는 공집합일 수 있으며, 그 경우 |= φ으로 쓰며, 이것은 φ가 타당하다는 뜻이다.I 추론규칙들의 집합 X 는 정확히 다음 경우 건전하다: 모든 문장 φ와 문장집합 Γ에 대해서, 만일 Γ `X φ이면 Γ |= φ이다. 이것은 또 다음 주장과 동치이다: 모든 문장 φ에 대해서, 만일 `X φ이면 |= φ이다. (왜 그런가?) I 그런집합 X 는 다음 경우 완전하다: 모든 문장 φ와 문장집합 Γ 에 대해서, 만일 Γ |= φ이면 Γ `X φ이다. 마찬가지로, 이것은 다음과 동치이다: 모든 문장 φ에 대해서, 만일 |= φ이면 `X φ 이다. I 또 추론규칙들의 어떤 집합 X 는 정확히 다음 경우 일관적이다: 어떤 문장 φ에 대해서도, φ와 −φ가 각각 ∧로부터 X 의 추론 규칙들에 의해 도출되지 않는다. 즉 어떤 문장 φ에 대해서도, `X φ이면서 동시에 `X −φ인 경우가 아닐 경우 그리고 그 경우에만 X 는 일관적이다.
증명: 건전성
I 이제 우리의 추론규칙들 S =df {P, T, C, US, UG, E}가
건전하고 일관적이라는 것을 보여주고자 한다. I 사실 S가 건전하다면 그것은 일관적이다. 왜냐하면 S가 건전하지만 비일관적이라고 해 보자. 그렇다면 `S φ이면서 동시에 `S −φ인 그런 φ가 존재한다. 그렇다면 T에 의해서 `S (φ& − φ)이고 건전성의 가정에 의해서 |= (φ& − φ)여야 하지만 그것은 불가능하다. I 이제 우리는 S의 건전성을 (따라서 S의 일관성도 함께) 증명한다. 즉 Γ `S φ를 가정하고 Γ |= φ임을 보여주고자 한다.
I 가정에 의해서 " .. . ... ... {m1. . . mq} (n) φ # 형태의 도출이 존재한다. ({m1. . . mq}는 전제집합 Γ의 원소들을 가리키는 행번호들이다.) 우리는 그 도출의 모든 행에 대해서 그 문장이 그 전제집합의 귀결이라는 것을 보이고자 한다. 이를 위해서는 (i) 그 도출의 첫번째 행의 문장이 그 전제집합의 귀결이라는 점과 (ii) 임의의 k ∈ {1 . . . n − 1}에 대해서 k째까지의 모든 행에서 그 행의 문장이 그 행의 전제집합의 귀결이라면 k + 1 째 행에 대해서도 그렇다는 것을 보여주면 된다. I 명백히 위 도출의 첫 부분은 " {1} (1) ψ P .. . ... ... ... # 형태거나 " ∧ (1) ψ T .. . ... ... ... # 형태여야 한다. 어느 경우건 첫째 행의 문장 ψ는 그 행의 전제집합의 귀결이다. 즉 (i)이 증명됐다.
증명: 건전성 (계속)
I 다음으로 모든 k ∈ {1 . . . n − 1}에 대해서 k째까지의 모든 행에서 그 문장이 그 전제집합의 귀결이라고 가정하자. 우리가 보여줘야 하는 것은, 위 가정을 이용하여, k + 1째 행의 문장 ξ 가 그 전제집합 ∆의 귀결이라는 것이다. I 먼저 k + 1째 행이 P에 의해 도입된 경우를 생각해 보자. 그 행의 문장을 ξ라고 하면 명백히 ∆ = {ξ}이고 {ξ} |= ξ이다.I k + 1째 행이 US에 의해 도출 속에 도입된 경우 그 도출은 .. . ... ... ... {n1. . . np} (l ) (α) ξ ... .. . ... ... ... {n1. . . np} (k + 1) ξαβ l US .. . ... ... ... 형태를 띨 것이다. 가정에 의해서 (α) ξ는 n1. . . np이 가리키는 행들의 문장들(∆) 의 귀결이다. 따라서 임의의 해석 T 하에서 ∆의 문장들이 참이라면 (α) ξ 역시 T 하에서 참이다. 그런데 T 는 T 자체의 β-변형이기 때문에 ξβα는 T 하에서 참이다. 따라서 ∆ |= ξα β 이다. I k + 1째 행이 T에 의해서 도입된 경우도 본질적으로 똑같다. 다만 그 경우에는 하나 이상의 전제집합들을 다뤄야 할 수도 있다.
증명: 건전성 (계속)
I k + 1째 행이 C에 의해서 도입된 경우 그 도출은 .. . ... ... ... {l } (l ) χ P .. . ... ... ... {n1. . . np, l } (m) ξ ... .. . ... ... ... {n1. . . np} (k + 1) χ → ξ mC .. . ... ... ... 형태를 띤다. 이제 문제는 n1. . . np가 가리키는 문장들(∆)이 임의의 해석 T 하에서 참일 경우 χ → ξ 역시 T 하에서 참인가이다. ∆의 모든 문장들이 T 하에서 참이라고 하자. T 하에서 χ는 거짓이거나 참이다. 앞의 경우 χ → ξ는 T 하에서 참이다. 뒤의 경우 ∆ ∪ {ξ} 즉 m째 행의 전제들이 모두 T 하에서 참이기 때문에 ξ도, 따라서 χ → ξ도 T 하에서 참이다. 따라서 χ → ξ는 ∆의 귀결이다.I k + 1째 행이 T, UG, 또는 E에 의해서 도입된 경우들은 연습문제로 남겨둔다. 여러분들이 이 연습문제를 풀었다고 가정하면, (ii)가 증명된 셈이다. I (i)과 (ii)가 둘 다 증명되었으므로, 수학적 귀납법에 의해서, 주어진 도출의 어느 행에 대해서도 그 행의 문장은 그 전제집합의 귀결이다. I 그러므로 마지막 행의 문장 φ역시 그 행의 전제집합 Γ의 귀결이다. 이로써 S의 건전성과 일관성이 증명되었다.
증명: 완전성
I 다음은 S의 완전성을 증명할 차례다. 먼저 정의를 하나 도입한다: 임의의 추론규칙들의 집합 X 에 대해 문장집합 Γ가 X -도출일관적인 경우 오직 그경우에만 X 의 추론규칙들에 의해 Γ로부터 (φ& − φ)가 도출될 수 있는 그런 φ가 존재하지 않는다. (이것은 교과서에 나온 도출일관성의 정의보다 약간 더 일반적이다.) I 학기 초에 배웠던 다음 정의를 상기하라: 문장집합 Γ가 해석일관적인 경우 오직 그 경우에만 모든 φ ∈ Γ가 T 하에서 참인 그런 해석 T 가 적어도 하나 존재한다. (그때는 이 특성을 그냥 “일관성”이라고 불렀지만, 혼동을 피하기 위해서 지금은 해석일관성이라고 하자.) I 다음 사실들을 관찰하라: (i) 모든 문장집합 Γ와 문장 φ에 대해서, φ가 Γ로부터 S의 추론규칙들에 의해 도출되는 경우 오직 그 경우에만 Γ ∪ {−φ}는 S-도출일관적이지 않다. (ii) 모든 문장집합 Γ와 문장 φ에 대해서, φ가 Γ의 귀결인 경우 오직 그 경우에만 Γ ∪ {−φ}는 해석일관적이지 않다. (왜 그런가?)따라서 다음 주장들은 서로 동치이다: (C1) 모든 문장집합 Γ와 문장 φ에 대해서, φ가 Γ의 귀결이면 φ가 Γ로부터 S의 추론규칙들에 의해 도출된다. (S의 완전성) (C2) 모든 문장집합 Γ와 문장 φ에 대해서, Γ ∪ {−φ}가 해석일관적이지 않으면 Γ ∪ {−φ}는 S -도출일관적이지 않다. (C3) 모든 문장집합 Γ와 문장 φ에 대해서, Γ ∪ {−φ}가 S -도출일관적이면 Γ ∪ {−φ}는 해석일관적이다. 마지막 조건문 (C3)는 물론 다음의 I로부터 따라나온다: I 모든 문장집합 Γ에 대해서, 만일 Γ가 S -도출일관적이면 Γ는 해석일관적이다. (즉 임의의 문장집합 Γ로부터 S의 추론규칙들에 의해서 모순이 도출되지 않는다면, Γ의 모든 문장들을 참으로 만드는 해석 T 가 적어도 하나 존재한다.)
증명: 완전성 (계속)
따라서 S의 완전성을 증명하려면 I를 증명하면 된다. 그런데 어떤 이유로 인해서, I보다는 다음의 I’를 증명하는 것이 편하다: I’ 모든 문장집합 Γ에 대해서, 만일 Γ가 S -도출일관적이고 Γ의 원소문장들에 등장하는 모든 개체상항들이 짝수만을 아래첨자로 가지고 있다면, Γ 는 해석일관적이다. 왜 I 대신 I’을 증명하는지 이상하겠지만, 지금은 I’을 증명하면 I 역시 증명된다는 것을 관찰하는 것으로 충분하다. 왜냐하면, Γ의 원소들에 나타나는 모든 개체상항들을 그 아랫첨자에 2를 곱하여 대체한 원소들로 구성된 문장집합 Γ0을 생각해 보자. 예: Γ =‘F21a1’, ‘ (∃x) G32b1c2’ 라면 Γ0 =‘F21a2’, ‘ (∃x) G32b2c4’ . 명백히, Γ가 S-도출일관적인 꼭 그 경우 Γ0도 S-도출일관적이고, Γ 가 해석일관적인 꼭 그 경우 Γ0도 해석일관적이다. (왜인가?)I 결국 우리는 I’가 참임을 보임으로서 S의 완전성을 보이고자 한다. 즉 임의의 S-도출일관적인 문장집합에 대해서 그 원소들을 모두 참으로 만드는 해석이 존재함을 보이는 것이 우리의 목표다. I 하지만 다소 역설적이게도, 이 목표는 언뜻 보아 더 야심찬 것처럼 보이는목표를 달성함으로써 더 쉽게 달성될 수 있다. 그 야심찬 목표가 무엇인지 기술하기 위해서 우리는 또 다른 정의들을 필요로 한다: (i) 모든 문장집합 ∆에 대해서, ∆가 S -최대도출일관적인 경우 오직 그 경우에만 ∆는 S -도출일관적이고 어떤 S -도출일관적인 문장집합에도 진부분집합으로 포함되지 않는다. (ii) 모든 문장집합 Γ에 대해서, Γ가 ω-완전할 경우 오직 그 경우에만, 만일 (∃α) φ ∈ Γ 이면 또한 어떤 개체상항 β에 대해서 φα/β ∈ Γ이다.
증명: 완전성 (계속)
I 이제 우리는 다음 두 조건문들을 기술할 수 있다: II 모든 문장집합 Γ에 대해서, 만일 Γ가 S -도출일관적이고 그 원소들이 오직 짝수 아래첨자의 개체상항들만을 가진다면, S-최대도출일관적이고 ω-완전한 문장집합 ∆ ⊃ Γ가 존재한다. III 모든 문장집합 ∆에 대해서, 만일 ∆가 S -최대도출일관적이고 ω-완전하다면, ∆는 해석일관적이다.I II와 III이 함께 I’을 함축하는 것을 깨닫기는 어렵지 않다. 어떤
문장집합 Γ가 S-도출일관적이고 짝수 아래첨자 개체상항들만을 포함한다고 하자. II에 의해 S -최대도출일관적이고 ω-완전한 ∆ ⊃ Γ가 존재한다. III에 의해서 ∆는 해석일관적이다; 즉 모든 φ ∈ ∆가 T 하에서 참인 해석 T 가 존재한다. 따라서 모든 ψ ∈ Γ ⊂ ∆역시 T 하에서 참이다. 따라서 Γ는 해석일관적이다.
II와 III을 증명하기 전에, S-최대도출일관적인 문장집합 ∆의 다음 특성들을 알 필요가 있다: (1) φ ∈ ∆인 꼭 그 경우 −φ /∈ ∆이며 (2) φ ∈ ∆인 꼭 그 경우 ∆ `S φ이다. 왜 그런지 이해하려면, φ, −φ ∈ ∆라고 해 보자. 그 경우 ∆는 S -도출일관적이지 않다. 반대로 φ /∈ ∆, −φ /∈ ∆라고 해 보자. 물론 ∆는 S -도출일관적이므로 ∆ 6`S φ거나 ∆ 6`S −φ이다. 전자의 경우 ∆ ∪ {−φ}가, 후자의 경우에는 ∆ ∪ {φ}가 S -도출일관적이면서 ∆ 를진부분집합으로 가진다. 따라서 φ와 −φ중 정확히 하나만이 ∆ 에 포함되어야 그것이 S-최대도출일관적이라는 조건과 모순되지 않는다. (2)는 (1)로부터 쉽게 보여진다. (왜 그런가?)
증명: 완전성 (계속)
나아가서 다음 사실들이 성립한다: ∆은 S-최대도출일관적이고 ω-완전한 문장집합이며 φ와 ψ는 임의의 두 문장들이라고 하자. 이 경우 다음 사실들이 성립한다: (3) (φ ∨ ψ) ∈ ∆인 꼭 그 경우 φ ∈ ∆ 혹은 ψ ∈ ∆이다. (4) (φ&ψ) ∈ ∆인 꼭 그 경우 φ ∈ ∆ 그리고 ψ ∈ ∆이다. (5) (φ → ψ) ∈ ∆인 꼭 그 경우 φ /∈ ∆ 혹은 ψ ∈ ∆ 혹은 양자 모두이다. (6) (φ ↔ ψ) ∈ ∆ 인 꼭 그 경우 φ, ψ ∈ ∆ 혹은 φ, ψ /∈ ∆ 이다. (7) ((α) φ) ∈ ∆인 꼭 그 경우 모든 개체상항 β에 대해 φα/β ∈ ∆이다. (8) ((∃α) φ) ∈ ∆인 꼭 그 경우 어떤 개체상항 β에 대해 φα/β ∈ ∆이다. 각각의 증명은 어렵지 않다. (pp.234-235참조.)먼저 II를 증명한다. Γ가 짝수아래첨자 개체상항만을 포함하는 문장들의 S-도출일관적인 집합이라고 가정하자. 우리는 L의 모든 문장들이 아래 조건들 (a)와 (b)를 만족하면서 φ1, φ2, φ3, φ4, . . . 으로 무한히 배열될 수 있다는 사실을 이용한다. (a) L의 각 문장은 적어도 한 번 목록 속에 나타난다. (b) (∃α)φ의 형태를 지닌 각 문장에 대해, β가 ‘새로운’ 개체상항일 때 (즉, 문장들 φ1, φ2, . . . , φi에도 Γ 의 어떠한 문장에도 나타나지 않는 개체상항일 때), φi = (∃α)φ 그리고 φi +1 = φα/β인 그러한 i 가 적어도 하나 존재한다. (이 조건은 홀수 아래첨자를 가진 β를 채택함으로써 언제나 만족시킬 수 있다.)
증명: 완전성 (계속)
이제 문장집합들의 배열 ∆0, ∆1, ∆2, ∆3, ∆4, . . . 을 다음 방법으로 구성해 보자: (i) ∆0 = Γ. (ii) ∆n= ( ∆n−1∪ {φn} 이 합집합이 S-도출일관적인 경우 ∆n−1 그렇지 않은 경우 . 즉, 우리는 Γ를 씨앗으로 삼아 위에 배열된 L의 모든 문장들을 S -도출일관성을 유지하면서 더해 나간다. 예를 들어, ∆1 = ( ∆0∪ {φ1} 이 합집합이 S-도출일관적인 경우 ∆0 그렇지 않은 경우 , ∆2 = ( ∆1∪ {φ2} 이 합집합이 S-도출일관적인 경우 ∆1 그렇지 않은 경우 , 하는 식이 된다. 이제 ∆ =df ∆0∪ ∆1∪ ∆2∪ . . .로 정의한다.이렇게 정의된 ∆는 S-최대도출일관적이며 ω-완전하다: I 먼저 그 구성방법에 의해서 ∆는 S-도출일관적일 수밖에 없다는 것을 관찰하라. 다음으로 S-도출일관적인 Ξ가 ∆를 진부분집합으로 가진다고 가정해 보라. 그러면 어떤 문장 φ에 대해서 φ ∈ (Ξ − ∆)이다. 그런데 φ /∈ ∆이므로 −φ ∈ ∆ ⊂ Ξ 이다. 그러면 φ, −φ ∈ Ξ가 되어 Ξ가 S-도출일관적이라는 가정이 깨진다. 따라서 그런 Ξ가 존재하지 않으므로 ∆는 S -최대도출일관적이다. I 다음으로 ∆에 포함된 임의의 존재양화문 (∃α) ψ를 생각해 보자. 그로부터 ∆가 구성된 φ1, φ2, . . . 의 배열방법에 의해서 어떤 i에 대해서 φi = (∃α) ψ이고 φi +1 = ψα/β이며 이때 β는 Γ에도 φ1, φ2, . . . φi에도 등장한 적이 없는 개체상항이다. ∆i∪ {φi +1}이 S-도출일관적이지 않다고 가정해 보자. 그러면 C, T, UG, E에 의해 ∆i `S − (∃α) ψ이다. 이것은 (∃α) ψ, − (∃α) ψ ∈ ∆가 되어 가정과 모순된다. 그러므로 ∆i +1 = ∆i∪ {φi +1}이 되어 ψα/β ∈ ∆이다. 그러므로 ∆는 ω-완전하다.
증명: 완전성 (계속)
다음은 III을 증명할 차례이다. 이를 위해 임의의 S -최대도출일관적이고 ω-완전한 문장집합 ∆를 고려해 보자. 여기서 우리의 목표는 모든 φ ∈ ∆를 참으로 만드는 해석 T 를 구성하는 것이다. 그 해석 T 는 다음과 같다: I 모든 개체상항 β에 β자체를 할당한다. (예를 들어 ‘a1’에 ‘a1’ 자체를 할당한다.) I 모든 술어 γ1에 β|γ1β ∈ ∆ 를 할당한다. (예를 들어, ∆에 포함된 술어 ‘F1’을 포함한 원자문장들이 ‘F1a 1’, ‘F1b612’, 등이라면,‘F1’에 {‘a 1’, ‘b612’, . . .}를 할당한다.) I 모든 술어 γn>1에 {hβ 1. . . βni |γnβ1. . . βn∈ ∆} 를 할당한다. (예를 들어, ∆에 포함된 술어 ‘G2’을 포함한 원자문장들이 ‘G2a1b612’, ‘G2f1a1’, 등이라면,‘G2’에{h‘a1’, ‘b612’i , h‘f1’, ‘a1’i , . . .}를 할당한다.)
I 주어진 문장집합 ∆와 앞에 구성한 해석 T 에 대해서 우리는 다음과 같은 점을 보여주고자 한다: L의 모든 문장 φ에 대해서, φ ∈ ∆인 경우 오직 그 경우에만 φ는 T 하에서 참이다. I 이 점을 보여주기 위해서 우리는 L의 문장들의 연결사와 양화사의 갯수에 수학적 귀납법을 적용한다: 그 갯수가 0인 경우, 즉 L의 원자문장들 φ는 모두 그 구성에 의해서 φ ∈ ∆인 경우 그리고 그 경우에만 φ가 T 하에서 참이다. 이것은 해석 T 의 구성에 의해서 명백하다. I 그 갯수가 k보다 작은 모든 ψ에 대해서 ψ ∈ ∆인 경우 오직 그 경우에만 ψ가 T 하에서 참이라 가정하자. 이제 그 갯수가 k인 모든 φ에 대해서 φ ∈ ∆인 경우 오직 그 경우에만 φ가 T 하에서 참이라는 것을 보인다. 우리는 다음 경우들 각각에 대해서 그 점을 보여야 한다: (i) φ = −ξ, (ii) φ = (ξ&χ), (iii) φ = (ξ ∨ χ), (iv) φ = (ξ → χ), (v) φ = (ξ ↔ χ), (vi)
증명: 완전성 (계속)
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의 완전성이 증명되었다.
