2026. 4. 4.
어떤 수학적 명제를 증명하는 방법에는 크게 두 가지가 있는데, 구성적인 직접 증명법과 부정 명제의 모순됨을 유도하여 본 명제가 참임을 주장하는 간접 증명법이 있다. 이들이 서로 얽혀 있는 경우도 있다.
"명제를 증명한다"는 말은 "명제가 옳음을 증명한다"는 말과 같은 뜻이다.
명제의 증명이 복잡한 경우에는 대중들은 간혹 직접 증명인지 간접 증명인지 헷갈리고, 증명 전체를 잘 이해하기 어렵다.
대표적인 보기가 유클리드의 "소수들의 무한함"에 관한 증명이다. 유클리드는 흔히 우리가 말하는 것처럼 "소수가 무한히 많다"고 말하지 않고, "어떠한 수보다도 소수의 개수는 많다"고 말하였다. 유클리드의 증명은 매우 구성적인데도, 많은 이들이 귀류법으로 증명한 것, 즉 ``결론이 틀렸다면 모순이 생긴다"는 식의 증명이라고 말한다.
유클리드의 증명을 예를 들어 살펴 보자. 예를 들어 2와 3이 소수임은 분명하다. 이때 2*3 + 1, 즉 7을 얻는데, 이 또한 소수이다. 이제 우리가 아는 소수는 2, 3, 7 이다. 그러면 2*3*7 + 1, 즉 43 또한 소수이다. 계속하면 2*3*7*43 +1 = 42*43 +1 = 1807 인데, 1807 은 소수가 아니고 인수분해하면 1807 = 13 * 139 이다. 이때 새로운 소수 13과 139를 얻는다.
이와 같이 소수들이 무한함에 관한 유클리드의 증명은 새로운 소수를 찾는 매우 구체적인 구성법이다. "소수들이 유한개뿐이다"라고 주장하면 모순이 생긴다는 식의 귀류법이 아니다.
대각논법을 통하여 어떤 집합에도 그 보다 더 큰 집합이 있음을 밝힐 수 있는데, 이 논법은 "더 큰 집합이 존재하지 않는다면 모순이 생긴다"는 귀류법식의 단순한 존재 증명이 아니라 구체적으로 더 큰 집합이 어떤 것인지 밝히는 구성적인 논법이다.
예를 들어 자연수 전체의 집합 N과 자연수들의 동아리 모두로 이루어진 집합 P(N)을 생각해 보자. 여기에서 ``동아리"란 ``부분집합"이라는 뜻으로 사용하였다. 동아리 각각은 0과1로 이루어진 무한수열로 이해하여도 좋다.
이때 대각논법이란 함수 f: N → P(N) 이 어떤 것이던, 전사가 아님을 밝히는 법인데, 이는 동아리 중에 번호를 부여할 수 없는 동아리가 어떤 것인지 구체적으로 밝히는 법이다. ``번호를 부여할 수 없는 동아리가 존재한다''는 것을 밝히는 단순한 ``존재증명"이 아니라 구성적인 증명이다. 칸토어가 제시한 번호없는 동아리는 바로 D := { n | n ∉ f(n) } 이다.
동아리 f(n)을 0과 1로 이루어진 무한 수열이라 생각하고, 그 수열의 k번째 항을 f(n,k)라 하면, D라는 동아리, 즉 수열은 그 k번째 항이 D(k) = 1- f(k,k) 이다.
물론 D가 왜 번호를 가지지 않는지를 귀류법적으로 설명할 수도 있지만, 귀류법이 아니라도 D가 f(n)과 다르다는 것은 뻔하다.
이런 대각논법은 자연수 집합에만 적용되는 것이 아니고 모든 집합에 적용되어 결국 ``어떤 집합에도 더 큰 집합이 있음''을 알게 되고, 무한들이 무한함을 알 수 있다.
대각은 對角線을 뜻하지만, 大覺이라 할 수 있다.
𝛿(x,y) := 𝛿(x)(y) 의 값은 x와 y가 같을 때에만 1이고 다를 때에는 모두 0이다.
어떤 개체 x에 대하여 𝛿(x)는 다른 대상들을 0과 1로 판정하는 함수인데, 함수들은 더하거나 스케일을 조정할 수 있기 때문에 결국 𝛿(x)는 벡터가 된다. 이것을 고전적인 상태 x가 양자 상태 𝛿(x)로 변신하였다고 말 할수 있다. 벡터가 아닌 것들이 벡터로 변신하는 과정이다. 디랙은 𝛿(x) 대신에 |x⟩라는 기호를 사용하였다. 이제 슈레딩거의 고양이
대각논법은 물리학에서 양자 상태를 설명할 때에도 적용되고, 괴델이 불완전성 정리를 발견할 때에도 그대로 적용된다. 튜링은 대각논법을 이용하여 "알고리즘으로 모든 것을 알 수는 없음"을 증명하였다.
브라우어는 g라는 수를 골드바흐 가설이 참이면 g=1 이라 정의하고, 골드바흐 가설이 참이 아니면 g=0 이라 정의한다면, (1-g)g = 0 임은 분명하다고 하였다. 하지만 아직은 g=1 이라고 주장할 수도 없고, g=0 이라고 주장할 수도 없다. g=1 이라고 주장할 수 없다고 해서 g=0 이라고 주장하면 안된다는 말이다.
어린 괴델은 브라우어가 귀류법을 함부로 사용해서는 안된다는 말을 명심하고 있었다.