기호논리학
상항과 그 괴델 수
I PA 는 다음 상항들을 가진다: I 논리상항: − ∨ = ∃ I 대수기호: 0 + × ˆ I 다음-수-기호: s I 구두점들: ( ) , I 이 목록에는 “&,” “→,” “↔” 등이 없는데, 이것은 그 연결사들이 모두 “−”와 “∨”를 통해 정의될 수 있기 때문이다. I 위의 상항들에는 다음 괴델 수들이 부여된다: − ∨ ∃ = 0 s ( ) , + × ˆ { } ∧ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 I 끝의세 기호들, 즉 “{,” “},” “∧”는 PA 의 표현들이 아니다. 하지만 전제번호들의 목록을 표시하는데 쓰이기 때문에 역시 괴델 수를 부여할 필요가 있다. 그것들을 도출기호들이라고 부르자.변항과 그 괴델 수
I 변항들에는 세 가지 종류가 있다: I 수변항: “x,” “y ,” “z” . . . 수를 값으로 가질 수 있는 개체변항들이다. I 문장변항: “P,” “Q,” “R,” . . . 은 T나 F를 값으로 가지는 문장변항들이다. I 술어변항: “F ,” “G ,” “H,” . . . 은 수들의 집합을 외연으로 가지는 술어변항들이다. I 수변항들에는 알파벳 순서대로 솟수들이, 문장변항들에는 역시 알파벳 순서대로 솟수의 제곱수들이, 술어변항들에는 솟수의 세제곱수들이 괴델 수로서 할당된다. 예: 변항 x y . . . P Q . . . F G . . . 괴델 수 17 19 . . . 172 192 . . . 173 193 . . .식과 그 괴델 수
I 앞에 살펴본 상항들, 변항들, 그리고 도출기호들을 원초적 기호들이라고 부르자. 이 원초적 기호들에는 모두 괴델 수들이 부여되었다. I 이 원초적 기호들로 구성된 식들에는 다음 방식으로 괴델 수들이 부여된다: 주어진 식에 등장하는 원초적 기호들의 수가 n이라고 할 때 크기 순서로 처음 n개의 솟수들을 택한 다음 각각의 원초적 기호의 괴델 수만큼 순서대로 거듭제곱해서 얻은 수들을 모두 곱한 수가 그 식의 괴델 수로 부여된다. I 예 1: (∃x) (x = sy )의 괴델 수는 다음과 같이 얻어진다: ( ∃ x ) ( x = s 0 ) ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 7 3 17 8 7 17 4 6 5 8 와 같이 원초적 표현들의 괴델 수들을 얻으면 그 식의 괴델 수는 27× 33× 517× 78× 117× 1317× 174× 196× 235× 298가 된다. (엄청나게 큰 수다!)행의 괴델 수
I PA 의 도출은 여러 개의 행으로 구성되며, 각 행은 전제번호들의 목록과 PA 의 문장으로 이뤄진다. (증명의 편의를 위해 행번호와 적용된 추론규칙 등은 포함시키지 않는다.) I 이때 각 행에는 다음 방식으로 괴델 수가 부여된다: 주어진 행에 등장하는 원초적 기호들의 수가 n이라고 할 때 크기 순서로 처음 n개의 솟수들을 택한 다음 각각의 원초적 기호의 괴델 수만큼 순서대로 거듭제곱해서 얻은 수들을 모두 곱한 수를 그 행의 괴델 수로 부여한다. I 예 2: 행 “∧s0 = s0”의 괴델 수는 215× 36× 55× 74× 116× 135이다. 이 수를 o라고 하자. 행 “∧ (∃x ) x = s0”의 괴델 수는 215× 37× 53× 713× 118× 137× 1713× 194× 236× 295× 318 이 된다. 이 수를 p라고 하자.도출의 괴델 수
I PA 의 도출 자체에는 다음 방식으로 괴델 수가 부여된다: 주어진 도출을 구성하는 행들의 수가 n이라고 할 때 크기 순서로 처음 n개의 솟수들을 택한 다음 각각의 행의 괴델 수만큼 순서대로 거듭제곱해서 얻은 수들을 모두 곱한 수를 그 행의 괴델 수로 부여한다. I 예 3: 도출 ∧ s0 = s0 ∧ (∃x) x = s0 를 생각해 보자. 이 도출의 괴델 수는, 앞 슬라이드에서 첫째 행의 괴델 수를 o, 둘째 행의 괴델 수를 p라고 했으므로, 2o × 3p이다. I 앞으로 g (·)를 PA 의 원초적 표현들, 식, 행 도출을 입력값으로 받아 그 괴델 수를 나타내는 PA 의 숫자를 출력값으로 돌려주는 함수로 정의할 것이다. 위 예에서는 g (“ ∧ (∃x ) (x = sy ) ”) = “ o z }| { ss . . . s0”가 된다. 주의: 괴델 함수는 괴델 수를 돌려주는 것이 아니다.디코딩
I 괴델 수의 인코딩 방식은 정신이 아득해질 만큼 비효율적이다. 그래도 한 가지 장점이 있다면, 어떤 식이나 식의 나열을 인코딩한 괴델 수를 다시 디코딩하는 것이 쉽다는 것이다. 이 작업은 기본적으로 소인수분해를 통해서 이뤄진다. 예: 5 //0 "" 8, 100, 000 //25× 34× 55 99 // %% 4 //= //0 = 0 5 //0 << I 행과 도출의 괴델 수를 디코딩하는 것도 이와 비슷하다.관계를 대
표(representation)하는 식들
우리는 먼저 대표(representation)의 개념을 정의할 필요가 있다: 정의 1: 만일 R가PA 의 표현들 간의 메타언어적 n항 관계이고 ψ (α1. . . αn)이PA 의 n항 대수식이라면 (α1. . . αn는 수를 값으로 가지는 변항들), ψ이 R을 대표하는 경우 그리고 그 경우에만 임의의 표현들 τ1, . . . , τn에 대해서 1. 만일 R (τ1, . . . , τn)이면 ψ (g (τ1) . . . g (τn))은 PA 의 정리이고 2. 만일 R (τ1, . . . , τn)이 아니면 −ψ (g (τ1) . . . g (τn))이 PA 의 정리이다. 여기서 R이 메타언어적 n항 관계라는 것은 그것이 어떤 언어적 표현들 사이에 성립하는 관계라는 뜻이다. 예 4: 고다연 학생은 “(x) (∃y ) x 6= y ”를 “(∃x) (y ) y = x”보다 좋아한다. 예 5: “=”과 “0 = 0” 사이에는 전자가 후자의 두번째 기호라는 관계가 성립한다. 예 6: “(∃x) x = s0”과 ∧ s0 = s0 ∧ (∃x) x = s0 사이에는 후자가 전자의 증명이라는 관계가 성립한다.예 1: 대표될 수 없는 자연수들 간의 관계
I 그런 언어적 표현들 간의 관계 R이 주어졌을 때, 우리는 R이 그 사이에 성립하는 표현들의 괴델 수들 간의 관계 R0을 생각해 볼 수 있다. 이 관계는 순전히 자연수들 간의 관계이기 때문에, 대수학의 이론인PA 의 문장으로 나타낼 수 있고 또 관련된 사실을PA 의 규칙과 공리들을 통해서 증명할 수 있으리라고 생각할지 모른다. 그러나 자연수들 간의 모든 관계가 다 대수학적 관계인 것은 아니다. I 예 4를 다시 생각해 보자. 고다연 학생이 문장 α를 β보다 더 좋아한다는 언어적 표현들 간의 관계가 있고, 정확히 그 관계가 성립할 때 α와 β의 괴델 수들 간에 성립하는 자연수들 간의 관계가 있다. 후자는 자연수들 간의 이항관계이지만, PA 의 어떤 두 문장들 간에 이 관계가 성립하는지 여부를 언제나 PA 의 공리들로부터 증명하거나 반증할 수 있으리라고 기대할 수는 없다.예 2: 간단한 구문적 관계
I 예 5를 생각해 보자. R = {hx, y i |x는 y 의 두번째 기호이다} 라는 관계가 주어졌을 때, 아래에 정의되는 관계 R0을 PA 의 식으로 표현할 수 있을까? R0 = hx, y i | x 를 괴델 수로 가지는 기호는 y 를 괴델 수로 가지는 식의 두번째 기호다 . I 가능하다. 왜냐하면 다음 식 ξ를 생각해 보라: (∃z) x = z · sss0y& − (∃z) x = z · sss0sy. 먼저 “sss0”가 자연수 3을 가리킨다는 것, 그리고 3은 두번째 솟수라는 것을 떠올려 보라. 괴델 수의 정의에 의해서, 어떤 식 φ의 괴델 수도 3을 정확히 그 두번째 기호 ψ의 괴델 수만큼 제곱한 것을 인수로 가질 수 밖에 없다. 만일 어떤 두 표현들 φ 와 ψ의 괴델 숫자 µ와 ν에 대해서도 ψ가 φ의 둘째 기호라면 ξ (x /µ) (y /ν)를, 아니라면 −ξ (x /µ) (y /ν)가 증명된다면, ξ는 R을 대표한다.예 3: 구문적 관계로서의 증명
I 예 6으로 돌아가서, “(∃x) x = s0”가 ∧ s0 = s0 ∧ (∃x) x = s0 을 도출로서 가진다는 사실을 생각해 보자. 사실 이 문장과 도출 사이의 관계는 그 문장에 “∧”를 앞에 붙인 것이 그 도출의 맨 끝 행으로 나타난다는 순전히 구문적인 관계인 것으로 보인다. I 이러한 구문적 사실은 그 문장과 도출의 괴델 수들 간의 어떤 복잡한 대수적 사실에 반영된다. 그 사실을PA 의 문장으로도 나타낼 수 있겠지만, 지난 주 정의했던 기호들을 일부 이용하면 더 간단히 쓸 수 있다: (∃x ) x = Times (LastPrime (τ ) , τ ) &x = 215· Shift (ρ, 1) . 여기서 τ 는 위 도출의 괴델숫자, ρ는 위 문장의 괴델숫자이다. 15는 “∧”의 괴델 숫자이다.예 3: 구문적 관계로서의 증명 (계속)
I 일반적으로, 임의의 항들 τ1, . . . , τn에 대하여, φ (τ1, . . . , τn)이 PA 에서 형식적으로 정확하게 번역된다면 φ (τ1, . . . , τn) ↔ ψ이 도출가능한 PA 의 문장 ψ가 존재할 것이다. 이 경우 ψ를 “φ의 PA 번역”이라고 부르자. I 앞 슬라이드의 문장에서 τ 와 ρ를 자유변항들 “v ”와 “w ”로 대치한 식을 이용하여 다음 정의를 얻는다: (v ) (w ) Endline (v , w ) ↔ (∃x ) x = Times (LastPrime (τ ) , τ ) &x = 215· Shift (w , 1) . 그 사실을 엄밀히 증명하려면 시간과 노고가 들겠지만, 우리는 어떤 문장 φ와 어떤 표현들의 나열 ψ 사이에 성립하는 ∧φ가 ψ의 끝 행이라는 관계를 Endline (v , w )의 PA -번역이 대표하리라는 것을 알 수 있다. (이것은 아직 문장과 도출 간의 증명관계를 대표하지 않는다. 왜인가?)일반적 교훈
I 여기서 얻을 수 있는 일반적 교훈은, PA 의 어떤 표현들 간에 관계 R이 성립하고, 그 관계가 순수하게 구문적이라면, 그 표현들의 괴델 수들간의 관계는 대수학의 이론인PA 의 식으로 기술할 수 있으리라는 것이다. I 나아가서, 주어진 구문적 관계가 상대적으로 간단한 것이라면, 그 식의 자유변항을 그표현들간의 괴델 수로 대치한 문장은 증명하거나 반증할 수 있을 것이다. I 즉 PA 의 표현들 간에 성립하는 순수하게 구문적 관계에 대해서는 대개의 경우 그것을 대표하는PA 의 식이 있을 것이다.연산을 대표(representation)하는 식들
연산도 관계의 일종이므로 그에 대해 대표의 개념을 정의할 수 있다: 정의 2: 만일 f 가 메타언어적 n항 연산이고 ψ (α1. . . αn) 이 PA 의 대수항이라면, ψ가 f 를 대표하는 경우 그리고 그 경우에만 ψ (α1. . . αn) = αn+1은 {hτ1, . . . , τni |f (τ1, . . . , τn) = τn+1}을 대표한다. 예 7: 두 표현 φ와 ψ를 인자(parameter)로 받아 둘을 접합한 φψ를 값으로 돌려주는 메타언어적 2항 연산을 생각해 보자. 이 2항 연산은 φ의 괴델 수와 ψ의 괴델 수를 값으로 가지는 변항 x와 y 를 포함하는 “x · Shift (y , Length (x))”에 의해 대표된다. 예 8: 식 φ를 입력값으로 받아 그 부정식을 값으로 돌려주는 1항 연산은 φ를 값으로 가지는 변항 x를 포함하는 “21· Shift (x, 1)”에 의해 대표된다. 이 식을 이용하여 기호 Ng 를 형식적으로 올바르게 정의할 수 있다: (x) (y ) Ng (x) = y ↔ y = 21· Shift (x, 1).메타관계와 연산들
정의 3: 다음은 PA 의 모든 표현들을 관계항으로 하는 메타관계와 연산들이다: 1. 증명관계: pr =df {hα, βi |α는 β의 증명이다}, 2. 부정연산: ng =df {hα, βi |β는 α의 부정이다}, 3. 대입연산: sub =df {hφ, α, β, ψi |ψ = φ (α/β)}, 4. 괴델연산: g =df {hα, βi |α는 β의 괴델 숫자이다}. 이 관계와 연산들은 순수하게 구문적이기 때문에, 어떤PA 의 식들과 항들에 의해서 대표되리라는 점을 쉽게 알아차릴 수 있다. 실제로 그런 식들과 항들을 찾아내는 것은 힘들지만 가능하고, 또 괴델은 실제로 그 일을 해냈다. 다만 우리는 그런 식들과 항들이 있다는 가정 하에서 괴델 정리의 핵심을 증명하고자 한다.괴델의 불완전성 정리
이제 우리는 다음 메타 정리를 증명하고자 한다: 괴델의 불완전성 정리: 만일PA 가 일관적이고 그 안에서 pr , ng , sub, 그리고 g 가 어떤 대수식들과 대수항들에 의해 대표된다면, PA 는 불완전하다. 증명: 우리는PA 가 일관적이고 위의 메타관계들과 메타함수들이 그 안에서 대표된다고 가정하고 PA 가 불완전하다는 것을 증명한다. 가정에 의해서 pr , ng , sub, g 를 (순서대로) 대표하는 φ, ν, σ, γ가 있을 텐데, 편의상 이들을 이용하여 “Pr ,” “Ng ,” “Sub,” “G ”를 다음처럼 정의한다: 1. (x ) (y ) (Pr [x , y ] ↔ φ), 2. (x ) (y ) (Ng (x ) = y ↔ ν), 3. (x ) (y ) (z) (w ) (Sub (x , y , z) = w ↔ σ), 그리고 4. (x ) (y ) (G (x ) = y ↔ γ).괴델 문장 θ
이제 다음 식을 고려해 보자: (x )
Pr [x , Sub (z, g (z) , G (z))] →
(∃y ) (y < x &Pr [y , Ng (Sub (z, g (z) , G (z)))]) . 이 식의PA -번역 ξ역시 괴델수를 가질 것이며, g (ξ)는 그 수를 가리키는 숫자이다. 이제 다음 문장을 생각해 보자: (x ) Pr [x , Sub (g (ξ) , g (z) , G (g (ξ)))] →
(∃y ) (y < x &Pr [y , Ng (Sub (g (ξ) , g (z) , G (g (ξ))))]) . 이것의PA -번역을 θ라고 하자. 그런데, 생각해 보면, g (θ) = Sub (g (ξ) , g (z) , G (g (ξ))) 이 참임을 알 수 있다. 왜냐하면 θ는 ξ안에서 자유롭게 나타난 자유변항, 즉 “z”를 모두 ξ의 괴델 수를 나타내는 숫자로 대치하여 얻어진 바로 그 문장일 것이기 때문이다.
