[양상논리] 9장 발제 보완

9balje2.hwp 논리철학연습 발제
Chapter 9 – Incompleteness

과학사 및 과학철학 협동과정 2004-20309 정동욱 | 제출일 : 2004.7.21

이번 장에서 우리는 어떤 체계의 모든 정리가 정확히 f-타당하게 되는 프레임들의 집합 f가 존재하지 않는다는 의미에서 불완전한 어떤 체계가 있다는 것을 보일 것이다.

프레임과 모형

정리 9.1        만일 바른식들의 집합 에 속한 모든 원소들의 모든 대입예가 어떤 모형 <W,R,V> 하에서 타당하다면, K + 의 모든 정리들 역시 <W,R,V> 하에서 타당하다.

증명 : 정리 구성에 대한 귀납으로 증명한다.
라 하고,
로 정의할 때,
의 모든 원소들이 타당한 모형 <W,R,V>에서 의 원소들은 모두 타당할 수밖에 없다.
왜냐하면, 의 모든 원소들이 모형 <W,R,V>에서 타당하다면, 의 모든 원소들도 타당하기 때문이다.

한편, K +  체계의 정리들은 공리들로부터 시작하여 N, MP 또는 US를 차례차례 적용시켜 만든 바른식이며, 오직 K +  체계의 정리들만이 의 원소가 된다.
i) N 규칙 : 일때,
ii) MP 규칙 : 일 때,
iii) US 규칙 : 일때,

iii)을 증명하기 위해서는, 다시 귀납적인 증명을 해야 한다.
① 일때,
② 일때, 이라고 가정하면,
첫째, 이고  (왜냐하면, )
둘째, 에 대해, 이고  (왜냐하면, )
따라서, 일때, 이 된다.

이로써, K + 의 정리들은 의 원소이며, 의 모든 원소들은 가 타당한 모형 <W,R,V>에서 타당하다.

KH와 KW

KH에 대한 모든 프레임들의 집합이 특성화하는 체계가 바로 KW이다.
즉, f가 KH에 대한 프레임들의 집합이라 할 때, 는 +KW일 때 오직 그 때에만 f-타당하다

증명 1: 우선, KH + 4 = KW 임을 보인다.

(i) +KH+4W
PC                (1)
(1) []        (2)
4 (2) MP                (3)
(3) L-dis, Eq        (4)
(4) DR1                (5)
H                (6)
(6) []        (7)
(5)(7) Syll                (8)
PC                (9)
(9) []        (10)
(10) DR1                (11)
(8)(11) Syll        (12)

(ii) KW가 4를 포함한다 (Ch. 8 p.150)

(iii) +KWH
PC                (1)
(1) []        (2)
(2) DR!                (3)
W                (4)
(3)(4) Syll                (5)

증명 2 : +KW라고 가정해보자. 그러면 +KH+4일 것이다. 그리고, f(KH에 대한 프레임 집합)의 모든 프레임들은 또한 KH+4에 대한 프레임들일 것이기 때문에, (위의 p.160의 A에 의해) 는 f-타당하다. 만약 +KW라면, 앞장에서 확립한 KW의 완전성으로부터 는 KW에 대한 어떤 프레임에서 타당하지 않을 것이다. 그러나, KW는 KH를 포함하기 때문에, KW에 대한 프레임은 마찬가지로 KH에 대한 프레임이 되고, 그에 따라 는 f-타당하지 않게 된다.

완전성 그리고 유한 모형 속성

유한모형속성 : 체계 S의 정리가 아닌 바른식 에 대해서는 항상 그 가 타당하지 않은 S의 유한 프레임이 있을 때 오직 그 때에만, 체계 S는 유한모형속성을 지닌다.
과연, 체계 유한모형속성을 지닌 체계에 대해서는 완전성이 자동적으로 따라나올까? f가 S에 대한 모든 유한 프레임들의 집합이라고 하면 그 f가 S를 특성화하는 귀결을 갖게 될 것으로 짐작되지만, 과연 그럴까?
체계 S에 대한 유한모형은 존재하지만, 그 유한모형이 기반하고 있는 어떤 프레임도 S에 대한 유한프레임이 아니라면, 유한모형이 기반하고 있는 프레임들의 집합으로 체계 S를 특성화할 수 없을 것이다.
그러나, 이는 불가능하다.

증명 : 만일 S에 대한 어떤 유한 모형에서 가 타당하지 않으면, 그 모형을 쉽게 S에 대한 유한프레임에 기반한 어떤 모형으로 변환할 수 있다는 것을 보임으로써 진행한다.

i) S의 모든 정리가 타당한 어떤 모형 <W,R,V>에서, 에 대해 V이라고 가정하자.
이 모형으로부터 ‘동등한’ 어떤 두 세계도 포함하지 않고 타당성을 보존시키는 방식으로 <W*,R*,V*>를 구성한다. (이는 동등한 세계 중 하나만 남기고 나머지는 누락시키는 방식으로 얻을 수 있다.)
이 경우, <W,R,V>가 S에 대한 모형이라면, <W*,R*,V*> 또한 S의 모형이다. 즉, 가 <W,R,V>에서 타당사지 않으면 <W*,R*,V*>에서도 타당하지 않으며, 이는 가 S의 유한모형에서 타당하지 않으면 그것은 동등한 세계를 포함하지 않은 (유한)모형에서도 타당하지 않다는 것을 의미한다.

ii) 동등한 세계를 포함하지 않은 S에 대한 어떤 유한모형 <W*,R*,V*>를 상정하자.
이 모형에서는 세계마다 오직 자기세계 에서만 타당한 바른식 가 존재한다.

iii) 이제 <W*,R*,V*>가 S에 대한 모형이면서, <W*,R*>가 S에 대한 프레임이라는 것을 보이자.
<W*,R*,V*>가 S에 대한 모형이지만, <W*,R*>가 S에 대한 프레임은 아니라고 가정하자.
그러면, W*에 속하는 와 S의 어떤 정리 에 대해, 이 성립하는 어떤 모형 <W*,R*,V’>가 존재한다.
이 모형의 각 명제변항 는 어떤 세계들의 모임()에서는 참이고, 나머지 세계에서는 거짓이다.
한편, 가  (란 모형 <W*,R*,V*>에서 오직 에서만 타당한 바른식)이면, .
이제 가 정리 의 부분식이라 하고, 이 의 각 변항 를 로 대치한 결과라고 하면, .
특히, 가  자신인 경우, 이 된다. 그러나, 은 의 대입예이고, 따라서 은 S의 정리이다. 따라서 는 0이 될 수 없다. 따라서 이는 모순.

일반적 프레임(general frame)

<W,R,P>는 다음의 조건을 만족할 때 오직 그 때만 일반적 프레임이다.
(a) W는 공집합이 아닌 집합이다.
(b) R은 W에서 정의된 이항관계이다.
(c) P는 W의 원소들로 구성된 집합을 부분집합으로 가지는 집합으로서(즉, PpW) 다음의 조건을 만족한다.
  (i) 만약 AP이면, W-AP이다.
  (ii) 만약 AP이면, BP이면, ABP이다.
  (iii) 만약 AP이면, W:WRAP이다.

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다.