결정불가능명제의 모순성

[한계]

이것은 논문 두번째 주제입니다. keep going~

4. 결정불능명제

1) Q: ‘A = A는 증명 가능하지 않다.’

명제 Q 즉, ‘A = A는 증명 가능하지 않다.’에서 A는 괴델¹⁾이 제시한 결정불능명제²⁾이다.'A = A는 증명 가능하지 않다.’라고 가정했을 때 명제 A의 결정 불가능성은 다음과 같이 설명될 수 있다.

(1) 명제 A가 증명 가능하다고 가정하자. 만약 어떠한 명제가 증명 가능하다면 그 명제는 반드시 참이기 때문에 A는 참이다. 그런데 Q에 의해 A가 참이라면(좌변) ‘A는 증명 가능하지 않다.’(우변)도 참이므로 A는 증명 가능하지 않다는 결론이 나온다. 하지만 이는 A가 증명 가능하다고 했던 우리의 가정과 모순된다.

(2) ‘A가 아니다.’가 증명 가능하다고 가정하자. ‘A가 아니다.’가 증명 가능하다면 이는 곧 A는 거짓이라는 것을 의미한다. 그렇다면 Q에 의해 ‘A는 증명 가능하지 않다.(우변)’도 거짓이라는 결론이 도출된다. 고로 A는 증명 가능하다. 그런데 A가 증명 가능하다는 것은 곧 A가 참임을 의미하므로 이 또한 앞에서의 A는 거짓이라는 가정과 모순된다.

이처럼 명제 A를 ‘A = A는 증명 가능하지 않다.’와 같이 정의할 때 결정 불능 명제 A는 그것이 참임도 또 그것이 거짓임도 증명 불가능하다.

2) 전제는 타당한가?

앞에서 살펴보았듯이 명제 A를 Q와 같이 정의한다면 명제 A는 그 명제가 참임도 또 그 명제가 거짓임도 증명 불가능한 명제가 된다. 하지만 이러한 명제 A의 이상한 성격 역시 거짓말쟁이 역설의 전제와 같이 A에 대한 잘못된 정의로 인해 발생하는 결과가 아닐까? 다시 말해 명제 A를 ‘A는 증명 가능하지 않다.’로 정의하는 것은 문제가 없는가? 이제 다음의 논증을 통해 전제 Q에 대해 자세히 살펴보자.

<논증I>

① M: ￢A -> A는 증명 가능하지 않다.

② M은 참이다.³⁾

③ M의 대우(N)는 다음과 같다.

N: A는 증명 가능하다. -> ￢(￢A)

④ ￢(￢A)=A이므로 N은 곧 다음과 같다.

N: A는 증명 가능하다. -> A

⑤ 참인 명제의 대우는 항상 참이므로 N은 항상 참이다.⁴⁾

즉, 명제 N은 항상 참이다. 그런데 여기서 주목해야 할 것은 이 항상 참인 명제 N은 Q와 모순된다는 점이다.

다음 논증을 살펴보자.

<논증II>

① Q: ‘A = A는 증명 가능하지 않다.’ (가정)

② R: ‘A -> A는 증명 가능하지 않다.’ (가정)

③ Q가 참이면 R도 참이다. 즉, 'Q->R'은 참이다.

④ ‘Q->R'은 참이므로 그 대우 ‘￢R->￢Q’도 참이다.

⑤ 그런데 R은 항상 참인 명제 N과 동시에 성립할 수 없다.

N&R 이 성립한다는 것은

“‘A는 증명 가능하다. -> A' & ‘A -> A는 증명 가능하지 않다.’”이 성립함을 의미하는데 그렇다면 곧 ‘A는 증명 가능하다. -> A는 증명 가능하지 않다.’라는 모순에 빠지게 되기 때문이다.⁵⁾

⑥ 그런데 N은 항상 참이므로⁶⁾ R은 항상 거짓이다.

⑦ R이 항상 거짓이므로 Q도 항상 거짓이다. (④에서 ‘￢R->￢Q'이므로)

⑧ 고로 명제 N이 항상 참인 한 명제 Q는 항상 거짓이다.

이처럼 명제 N과 명제 Q는 동시에 성립할 수 없다. 그런데 명제 N은 항상 참이므로(<논증I>에서) 명제 Q는 항상 거짓이다. 고로 ‘A = A는 증명 가능하지 않다.’는 항상 거짓이다. 이는 결정불능명제의 정의인 명제 Q가 논리적으로 성립할 수 없음을 의미한다.

3) 두 전제와 귀류법

앞에서 결정불능명제가 참임을 증명하는 것이 불가능함을 설명할 때에는 다음의 두 가지 전제가 가정되었다. ‘A = A는 증명 불가능하다.’라는 명제 A의 정의와 ‘A는 증명 가능하다.’라는 가정이 그것이다. 하지만 1), (1)에서 살펴보았듯이 두 전제의 인정은 ‘A는 증명 불가능하다.’라는 결론을 이끌게 되어 모순⁷⁾에 봉착했고 우리는 모순된 결론에 이르게 한 두 전제 중에서 ‘A는 증명 가능하다.’라는 전제가 모순을 이끌어냈다는 결론을 내렸다.⁸⁾(귀류법에 의해 결론이 모순이므로 전제 중 적어도 하나는 거짓이기 때문이다.)⁹⁾ 반면 우리가 명제 A의 정의의 성립가능성을 고찰했을 때(논증II에서)에는 다음의 두 전제가 가정되었는데 그것은 ‘A=A는 증명 불가능하다.’라는 A의 정의와 ‘A는 증명 가능하다. ->A'라는 명제였다. 이 두 가지 명제가 참이라고 가정했을 때에도 우리는 ‘A는 증명 가능하다 -> A는 증명 가능하지 않다.’라는 모순에 봉착했다. 그러므로 귀류법에 의해 두 가지 전제 중 적어도 하나는 부정해야 한다. 여기서 우리가 내릴 수 있는 결론은 무엇이었는가? 뜻 밖에도 우리는 이전과 같이 두 전제 중에서 A의 정의를 인정하고 다른 전제를 부정할 수 없었다. 왜냐하면 A의 정의 외에 다른 한 전제 ‘A는 증명 가능하다. -> A'¹⁰⁾는 항상 참인 명제이기 때문이었다. 고로 A의 정의는 부정될 수밖에 없었는데 이는 곧 'A=A는 증명 불가능하다.'라는 A의 정의가 성립 불가능한 명제였음을 의미하는 것이었다.¹¹⁾

주석

1) Kurt Gödel

2) 이운형, 󰡔거짓말쟁이 역설󰡕, 한국학술정보(주), 2006. p. 133.

3) A라는 거짓인 명제가 있다고 가정하자. 그렇다면 우리는 그 명제 A가 참임을 증명할 수 없다 것은 자명하다.

4) 사실은 자명한 이 명제(N)는 ‘결정불능명제’의 결정 불가능성을 보여주는 단계에서 이미 전제하고 있는 명제이다. <본 논문 4.결정불능명제 1)의 (1)에서>

5) (Q->N)&(N->R) -> (Q->R)

6) <논증I>의 ⑤에서

7) ‘A는 증명 가능하다.’ -> ‘A는 증명 불가능하다.’

8) 사실 ‘A=A는 증명 불가능하다.'라는 명제 A의 정의가 잘못 되었다고 생각할 수도 있겠지만 ‘A는 증명 가능하다.’라는 두 번째 전제가 항상 참이어야 하는 명제가 아니므로 굳이 명제 A의 정의를 거짓이라고 부정하지 않고 두 번째 전제를 부정함으로써 귀류법을 만족시킬 수 있기 때문에 이러한 결론을 내릴 수 있었다. 또한 'A=A는 증명 불가능하다.'자체만으론 이 명제에 어떠한 모순점도 드러나지 않는다.

9) 이는 바로 다음에 전개된 논의에서도 동일한데 ‘A=A는 증명 불가능하다.’라는 명제 A의 정의와 ‘’A가 아니다.’가 증명 가능하다.’라는 두 가정에 의해서 ‘A는 증명 가능하다.’라는 모순된 결론이 도출되었을 때에도 우리는 ‘’A가 아니다.’가 증명 가능하다.’라는 전제가 거짓이라는 결론에 이르게 된 것이다. 그렇게 명제 A는 그 명제가 참임도 거짓임도 증명 불가능한 명제가 되었다.

10) A가 증명 가능하다면 명제 A가 참이라는 것은 자명하다. 사실 이 명제는 처음에 전개된 명제 A의 참, 거짓 증명 불가능성에 대한 설명에서 하나의 전제가 되는 명제였다.(주석 ‘28’ 참조)

11) 고로 앞에서 'A=A는 증명 불가능하다.’와 ‘A는 증명 가능하다.’라는 전제 사이에서 모순된 결론이 나왔을 때 사실 후자가 아니라 전자를 부정해야 했던 것이다.(참고로 전자가 거짓이면 명제 A 자체가 성립할 수 없으므로 후자 또한 당연히 부정되게 된다.)