Before Physics — 논리, 불완전성, 그리고 과학의 기반

암호학은 수학 위에 서 있고, 양자 암호학은 물리학 위에 서 있다. 이 글은 양자역학과 상대성 이론으로 나아가기 전, 수학적 참은 공리와 논리적 추론으로, 물리적 참은 실험적 검증으로 판별된다는 차이에서 출발한다.

수학·논리 vs 물리학

수학과 논리의 세계에서는 두 가지만 요구된다:

1. 공리 집합(Axiom Set)이 무모순적이다. 즉 공리들 사이에 모순이 없다
2. 논리적 추론 과정이 올바르다. 즉 각 단계가 타당한 추론 규칙을 따른다

이 두 조건을 만족하면 도출된 정리(Theorem)는 증명된다. 여기서 「증명된다」와 「참이다」를 붙여 쓰지 않는 것이 중요하다. 증명은 공리에서 규칙을 따라 문장을 뽑아내는 절차이고, 참과 거짓은 그 문장을 어떤 해석 위에서 읽었을 때 비로소 정해진다. 둘을 잇는 다리가 건전성(soundness) 이다. 추론 규칙이 건전하면 증명된 문장은 그 공리를 만족하는 모든 해석에서 참이다.

이 구별은 뒤에서 다시 필요하다. 괴델의 정리가 말하는 「참이지만 증명할 수 없다」가 바로 두 개념이 어긋나는 자리를 가리키기 때문이다.

여기서 핵심은 수학적 참이 현실에 존재하지 않아도 된다는 점이다. 4차원 구면, 무한 차원 벡터 공간, 비유클리드 기하학은 물리적으로 관찰되지 않더라도 각자의 공리계 안에서 참을 말할 수 있다.

물리학은 여기에 한 가지를 더 요구한다: 실험적 검증.

수학적 모델이 아무리 아름답더라도, 반복된 실험에서 같은 결과가 나오지 않으면 물리적 참이 아니다. 물리학은 수학 위에 구축되지만, 실험이라는 필터를 통과해야만 비로소 “실재”를 기술한다고 인정된다.

논리 체계는 완전한가?

완전성(Completeness): 모든 참인 명제는 증명을 갖는가?

무모순성(Consistency): $S$와 $\neg S$ 둘 다 증명을 가질 수 없는가?

직관적으로 우리는 둘 다 “당연히 그래야 한다”고 기대한다. 무모순적이지 않으면 체계 안에서 아무 명제나 증명할 수 있어 의미가 없어지고, 완전하지 않으면 참인데 증명할 수 없는 명제가 존재하게 된다.

1931년, 쿠르트 괴델(Kurt Gödel)은 이 기대를 산산조각 냈다.

괴델의 불완전성 정리

제1 불완전성 정리

먼저 무엇을 말하는 정리인지 직관으로 잡고, 그다음에 그 직관이 왜 아직 증명이 아닌지를 본다.

문장 A (직관용): “이 정리는 증명을 갖지 않는다.”

A에 대해 두 가지 가능성만 존재한다:

경우 1. A의 증명이 존재한다면: A의 주장(“증명이 없다”)이 거짓이 된다. 거짓인 명제에 증명이 존재하는 셈이므로 무모순성이 깨진다. 우리의 논리 체계가 무모순적이라고 믿는 한, 이 경우는 배제된다.

경우 2. A의 증명이 존재하지 않는다면: A의 주장(“증명이 없다”)은 사실이다. A는 참이지만 증명이 없는 명제다. 완전성이 깨진다.

여기까지가 직관이다. 이 서술은 아직 증명이 아니다. 우리말 문장 「이 정리는 증명을 갖지 않는다」는 거짓말쟁이 역설과 같은 꼴이고, 자연어 문장은 형식 체계 안의 문장이 아니다. 체계가 그것을 증명한다거나 부정한다는 말 자체가 성립하지 않는다. 진짜 정리는 이 문장을 체계 안에서 만들어 내는 절차와, 체계에 거는 조건을 함께 요구한다.

제1 불완전성 정리. 산술을 충분히 표현할 수 있고, 공리를 기계적으로 나열할 수 있으며, 무모순인 형식 체계 $T$에는 $T$가 증명하지도 부정하지도 못하는 문장이 존재한다.

세 조건이 모두 필요하다. 산술을 표현하지 못하면 체계가 자기 자신에 관한 문장을 쓸 수 없고, 공리를 기계적으로 나열할 수 없으면 「증명 가능하다」를 체계 안에서 정의할 수 없으며, 무모순이 아니면 아무 문장이나 증명되어 결론이 뜻을 잃는다.

흔히 쓰는 「참이지만 증명할 수 없다」는 표현에는 조건이 하나 더 붙는다. 참이라고 말하려면 해석이 필요하기 때문이다. 만들어진 문장을 표준 자연수 위에서 읽고 체계가 그 해석에서 건전하다고 볼 때, 그 문장은 참이면서 증명되지 않는다. 앞 절에서 증명과 참을 갈라 둔 이유가 여기에 있다.

자기 참조 문제: 괴델 넘버링

“이 정리”라는 자기 참조가 형식 체계 안에서 정당한가? 괴델은 괴델 넘버링(Gödel Numbering) 으로 이를 해결했다.

알파벳으로 표현할 수 있는 모든 문자열에 고유 번호를 부여한다:

$$\lambda_1,\ a_2,\ b_3,\ aa_4,\ ab_5,\ \ldots$$

번호를 붙이면 「증명」이라는 말도 수 위의 계산으로 바뀐다. 어떤 수열이 $T$ 안의 올바른 증명인지 검사하는 일은 기계적 절차이고, 산술을 충분히 표현하는 체계는 그 절차를 자기 언어로 적을 수 있다. 이렇게 얻는 것이 증명 가능성 술어 $\mathrm{Prov}_T(x)$, 곧 「번호가 $x$인 문장은 $T$에서 증명된다」를 뜻하는 산술 문장이다.

자기 참조는 여기서 나온다. 문자열을 쭉 나열하다 보면 자기를 가리키는 것이 우연히 걸린다는 이야기가 아니다. 대각화 보조정리(diagonal lemma) 가 그런 문장의 존재를 보장한다. 어떤 성질 $\varphi(x)$를 적든, $G$의 번호를 $g$라 할 때 $G \leftrightarrow \varphi(g)$를 $T$가 증명하는 문장 $G$를 만들 수 있다는 정리다. $\varphi$ 자리에 $\neg\mathrm{Prov}_T$를 넣으면 「나는 증명되지 않는다」고 말하는 문장이 형식적으로 완성된다.

제2 불완전성 정리

제1 정리에서 “체계가 무모순적이라면”이라는 가정을 사용했다. 여기서 한 단계 더 나아간다:

제2 불완전성 정리. 제1 정리와 같은 조건을 갖춘 체계 $T$는 「$T$는 무모순이다」를 뜻하는 자기 언어의 문장 $\mathrm{Con}(T)$를 증명하지 못한다.

얼개는 제1 정리를 체계 안으로 옮겨 적는 것이다. 제1 정리의 증명은 「$T$가 무모순이면 $G$는 증명되지 않는다」를 보인다. 이 논증 자체를 $T$의 언어로 적어 $T$가 따라오게 만들면 $T$는 $\mathrm{Con}(T) \to G$를 증명한다. 만약 $T$가 $\mathrm{Con}(T)$까지 증명한다면 $T$는 $G$를 증명하게 되어 제1 정리에 어긋난다.

옮겨 적기가 성립하려면 증명 가능성 술어가 얌전히 굴어야 한다. 힐베르트·베르나이스 도출 조건이라 부르는 세 가지다. $T$가 $A$를 증명하면 $A$가 증명 가능하다는 사실도 $T$가 증명해야 하고, 증명 가능성이 함의를 보존해야 하며, 증명 가능하다는 사실 자체가 증명 가능함을 $T$가 알아야 한다. 이 조건을 벗어나도록 술어를 일부러 비틀면 결론도 성립하지 않는다. 제2 정리는 증명 가능성을 자연스럽게 적었을 때의 이야기다.

이것은 Halting Problem과 유사한 구조다. 프로그램이 멈추는지 안 멈추는지를 범용적으로 판별하는 알고리즘이 존재하지 않는 것처럼, 논리 체계가 깨지는지 안 깨지는지를 체계 내부에서 판별할 수 없다. 깨지는 순간을 관찰해야만 깨진다는 사실을 알 수 있다.

오컴의 면도날 (Occam’s Razor)

실험과 일치하는 이론이 여러 개 존재할 때, 어떤 것을 선택해야 하는가?

가장 간결한 이론을 선택하라. (윌리엄 오컴, 14세기)

공리 집합이 가장 작고, 가정이 가장 적은 이론이 우선한다. 이것은 미학적 선호가 아니다. 불필요한 가정은 틀릴 가능성을 높이고, 반증 가능성을 줄여 과학적 가치를 떨어뜨린다.

예를 들어, 뉴턴 역학과 아리스토텔레스 역학이 일상적 현상을 비슷하게 설명한다면, 더 적은 공리로 더 넓은 현상을 설명하는 뉴턴 역학을 선택한다. 그리고 뉴턴 역학이 설명하지 못하는 현상(수성의 세차 운동, 빛의 속도 불변 등)이 발견되면, 더 간결한 공리에서 이를 설명하는 상대성 이론으로 나아간다.

과학적 원리

물리학을 이야기할 때 아래 세 문장이 원리처럼 자주 인용된다.

존재의 기준: 실험으로 검증할 수 없는 것은 존재하지 않는다.

차이의 기준: 실험으로 차이를 검증할 수 없으면 그 차이는 존재하지 않는다.

동일성의 기준: 실험으로 구별할 수 없는 두 대상은 실제로 같은 것이다.

이 셋은 물리 법칙이 아니라 철학적 입장이다. 검증 가능성을 의미의 기준으로 삼는 검증주의, 개념을 측정 절차로 환원하는 조작주의가 그것이다. 물리학이 실제로 요구하는 것은 이보다 약하다. 관측으로 구별되지 않는 두 서술은 예측이 같고, 그래서 물리학은 둘을 갈라 세울 근거를 갖지 못한다. 거기서 「그러므로 같은 것이다」나 「그러므로 없는 것이다」로 넘어가는 마지막 한 걸음은 존재에 관한 별도의 선택이다.

이 선택은 실무에서 대체로 유용하다. 구별되지 않는 차이를 이론에 남겨 두면 오컴의 면도날에 걸리는 군더더기가 되기 때문이다. 다만 유용한 규범과 증명된 사실은 다르다.

문제는 양자역학에서 가장 날카로워진다. 이중 슬릿 실험에서 어느 슬릿을 지났는지 알아낼 수 있게 만들면 간섭무늬가 사라지고, 알 수 없게 두면 간섭무늬가 나타난다. 실험이 말해 주는 것은 여기까지다.

「관측하지 않은 전자는 경로를 갖지 않는다」로 나아가는 것은 한 해석의 주장이다. 코펜하겐 해석은 대체로 그렇게 말하지만, 드브로이·봄 해석은 전자가 언제나 확정된 경로를 가지되 우리가 그것을 알 수 없다고 말하고, 다세계 해석은 또 다르게 말한다. 세 해석은 실험 결과를 똑같이 예측한다. 실험은 어느 쪽이 옳은지 가려 주지 않는다.