굿스타인 정리: 폭발적으로 커지다가 결국 0으로 돌아오는 수열
아무 자연수나 하나 골라 보세요. 그런 다음 두 가지 규칙을 반복해서 적용하며 결과를 지켜보세요. 대부분의 시작값에서 이 수열은 구골을 훌쩍 지나, 관측 가능한 우주의 원자 수를 훨씬 뛰어넘는 숫자까지 치솟습니다. 그런데도 반드시 0으로 돌아옵니다.
이것이 굿스타인 정리입니다. 처음 들으면 마치 속임수 같습니다. 규칙은 복잡하지 않고, 숫자는 평범하며, 진술은 깔끔합니다. 하지만 수십 년간 그 이유가 일반적인 산술의 틀 안에서 자리를 찾지 못했습니다. 이 글은 논리 증명을 따라가도록 요구하지 않습니다. 대신, 그 아래에 놓인 그림을 보여 드립니다. 한번 보고 나면, 이 정리는 더 이상 신비롭지 않습니다.
규칙은 거의 어린아이처럼 단순하다
자연수 하나와 밑수 2에서 시작합니다. 각 단계에서 두 가지를 합니다. 첫째, 현재 수를 세습적 n진법 표기법으로 씁니다. 둘째, 밑수 n이 등장하는 모든 자리를 n+1로 바꾼 다음 1을 뺍니다. 그리고 다음 밑수로 넘어가 반복합니다.
밑수를 올리고 1을 빼는 것은 순해 보입니다. 밑수를 2에서 3으로 올리는 것은 작은 변화처럼 느껴지고, 1을 빼는 것은 수를 억제해 줄 것 같습니다. 세습적 표기법과 만나면 이 두 직관 모두 무너지는 이유를 곧 보게 될 것입니다.
폭발하는 과정을 지켜보자
4에서 시작합니다. 세습적 2진법으로 4는 2^2입니다. 모든 2를 3으로 바꾸고 1을 빼면 3^3 빼기 1, 즉 26이 됩니다. 이제 26을 세습적 3진법으로 쓰고 밑수를 4로 올린 뒤 1을 빼면 41이 나옵니다. 계속 이어 갑니다.
| Step | Base | Written in that base | Value |
|---|---|---|---|
| 1 | 2 | 2² | 4 |
| 2 | 3 | 2·3² + 2·3 + 2 | 26 |
| 3 | 4 | 2·4² + 2·4 + 1 | 41 |
| 4 | 5 | 2·5² + 2·5 | 60 |
| 5 | 6 | 2·6² + 6 + 5 | 83 |
| 6 | 7 | 2·7² + 7 + 4 | 109 |
4에서 시작하는 수열은 4, 26, 41, 60, 83, 109 순서로 진행되며 그 이후에도 계속 올라갑니다. 이 소박한 시작조차 꽤 오랫동안 계속 증가하다가 결국 하강합니다. 19에서 시작한다면, 그 수는 물리적으로 쓸 수 없는 높이까지 도달합니다. 수열이 꺾이기 시작하기 전까지 걸리는 단계 수가 관측 가능한 우주의 원자 수보다 큽니다. 빅뱅 때 가장 빠른 컴퓨터로 계산을 시작했더라도, 오늘날 정점을 보지 못했을 것입니다.
모든 직관이 말합니다: 이 수열은 발산한다. 이렇게 커진 숫자에서 되돌아오는 것은 불가능하다. 하지만 직관은 여기서 단순히 틀렸습니다. 눈에 보이는 숫자들이 보여 주지 않는 무언가가 보이지 않는 곳에서 일어나고 있습니다.
오직 내려가기만 하는 숨겨진 수
각 항을 그것의 순서수 그림자로 대체하기
핵심 이동은 이것입니다. 굿스타인 수열의 어느 항이든 그것의 세습적 n진법 표현을 읽습니다. 이제 밑수 n이 보이는 곳마다 그 자리에 오메가(ω, 첫 번째 무한 순서수)를 씁니다. 표현의 구조는 전혀 바뀌지 않습니다. 단지 기호를 교체했을 뿐입니다. 결과는 순서수, 즉 자연수를 넘어 무한으로 확장된 일종의 수입니다.
예를 들어, 세습적 2진법에서 4는 2^2입니다. 2를 오메가로 바꾸면 ω^ω가 됩니다. 세습적 3진법에서 26의 순서수 그림자는 2ω² + 2ω + 2로, 오메가의 오메가 제곱보다 훨씬 작은 유한 높이의 오메가 다항식입니다. 세습적 3진법 표현의 지수 2, 1, 0은 이미 3보다 작으므로 더 이상 쌓지 않습니다. 이 순서수들은 완벽하게 잘 정의된 수학적 대상입니다.
밑수를 올려도 그림자는 변하지 않는다
밑수를 n에서 n+1로 올리면 세습적 표현의 기호가 n에서 n+1로 바뀌지만, 표현의 구조는 동일하게 유지됩니다. 따라서 밑수를 올릴 때 순서수 그림자는 변하지 않습니다. 올리기 전 항의 그림자와 올린 후 항의 그림자는 같은 순서수입니다.
하지만 그 다음 자연수에서 1을 뺍니다. 세습적 표기법에서 1을 빼려면 표현의 가장 낮은 항을 벗겨 내야 합니다. 이것은 세습적 표현의 구조를 바꾸는데, 밑수를 오메가로 대체하면 엄격하게 더 작은 순서수를 줍니다. 미미한 차이가 아니며, 우연도 아닙니다. 자연수 수열에서 1을 빼는 것은 매번 순서수 그림자를 엄격하게 아래로 끌어당깁니다.
패턴은 이렇습니다: 밑수를 올리면 (그림자는 제자리), 1을 빼면 (그림자는 내려감). 한 단계당 순효과: 순서수 그림자가 매번 최소 한 단계씩 내려갑니다.
순서수는 영원히 감소할 수 없다
순서수의 엄격하게 감소하는 수열은 영원히 계속될 수 없습니다. 이것은 순서수에 관한 가장 근본적인 사실 중 하나입니다. 정수와 달리, 순서수는 무한히 내려갈 수 없습니다. 바닥이 있습니다. 순서수 그림자의 수열은 결국 0에 도달해야 하며, 순서수 그림자가 0일 때 세습적 표현이 영 순서수로 대응되는 유일한 자연수는 0 자체입니다. 따라서 굿스타인 수열도 반드시 0에 도달해야 합니다.
눈에 보이는 자연수는 상상할 수 없는 크기로 부풀어 오를 수 있습니다. 하지만 그 뒤에 있는 순서수들은 조용하고 필연적으로 매 단계마다 아래로 째깍째깍 움직이고 있습니다. 소음은 눈에 보이는 숫자 안에 있습니다. 진실은 그림자 안에 있습니다.
히드라도 같은 말을 한다
같은 이야기를 게임으로 풀 수 있습니다. 나뭇가지 끝에 머리가 달린 나무 모양의 괴물, 히드라를 상상해 보세요. 머리 하나를 자릅니다. 어느 머리를 언제 자르느냐에 따라 그루터기에서 새 머리들이 여럿 돋아나기도 하고, 때로는 훨씬 많이 돋아납니다. 계속 자릅니다. 히드라가 이기는 것처럼 보입니다.
1982년 수학자 제프 파리스와 로리 커비가 소개한 커비-파리스 히드라 게임은 바로 이 상황이며, 굿스타인 수열과 동일한 수학을 담고 있습니다. 머리가 돋아나는 규칙은 밑수 올리기 폭발에 대응하고, 나무 구조는 세습적 표기법에 대응하며, 나무 뒤에 숨은 순서수는 굿스타인 논증과 마찬가지로 매 번의 자름마다 엄격하게 감소합니다.
어떤 전략을 쓰든, 어떤 머리를 자르든 상관없이 당신은 항상 이깁니다. 히드라는 항상 죽습니다. 새 머리의 폭발은 실재하며 때로는 장관이지만, 불꽃놀이 아래에서 카운트다운이 돌아가고 있습니다. 히드라 게임은 굿스타인 정리가 분장을 한 것입니다.
수학자들이 주목하는 이유
이야기가 여기서 방향을 틉니다. 굿스타인 정리는 참입니다. 위의 순서수 논증이 보여 주듯 증명 가능하게 참입니다. 그런데 1982년, 커비와 파리스는 또 다른 사실을 증명했습니다: 이 정리는 페아노 공리계 안에서 증명될 수 없다는 것입니다.
페아노 공리계는 자연수에 대한 추론의 표준 형식 체계입니다. 덧셈, 곱셈, 자연수에 대한 귀납법 등 여러분이 일반적인 산술이라고 부르는 거의 모든 것을 포괄합니다. 대부분의 수학 수업 결과들이 살아가는 무대입니다. 그런데 굿스타인 수열이 종료된다는 사실을 증명하기에는 단순히 충분하지 않습니다.
이것이 정리가 모든 의미에서 증명 불가능하다는 뜻은 아닙니다. 순서수 논증은 작동하며 완전히 엄밀합니다. 다만 순서수 논증은 페아노 공리계가 접근할 수 없는 방식으로 무한에 대한 추론을 요구합니다. 이 체계는 굿스타인 수열을 정확히 기술할 수 있습니다. 항 하나하나를 실행할 수 있습니다. 각 항이 특정 자연수라는 것도 인식할 수 있습니다. 하지만 내리막을 보장하는 순서수 구조, 즉 그림자는 볼 수 없습니다.
굿스타인 정리는 평범한 자연수에 관한 자연스러운, 평범해 보이는 명제가 표준 산술의 손이 닿지 않는 곳에 있다고 밝혀진 최초의 사례 중 하나였습니다. 일부러 증명 불가능하게 만들어진 인위적인 논리 퍼즐이 아닙니다. 고등학생에게 설명할 수 있고 냅킨에 쓸 수 있는, 평범한 수열에 관한 명제인데, 표준 산술은 이 사건을 해결할 수 없습니다.
그 속의 선(禪)
여기서 잠시 머물러 볼 만한 것이 있습니다. 한계 없이 폭발하는 것처럼 보이는 수열이, 매 단계마다, 눈에 보이는 숫자들이 숨기고 있는 하강에 참여하고 있습니다. 두 가지 일이 동시에 일어나고 있습니다: 엄청난 성장, 그리고 조용하고 필연적인 귀환.
이것은 모순이 아닙니다. 숫자의 크기가 그것의 운명과 같지 않다는 것을 상기시켜 줍니다. 중요한 것은 그 아래의 구조이며, 여기서 구조는 항상 0을 향하고 있습니다.
수학은 이런 순간들로 가득합니다: 발산해야 할 것 같지만 그렇지 않은 양, 실패해야 할 것 같지만 유지되는 증명, 무한할 것 같지만 종료되는 수열. 기술은 항을 무식하게 계산하는 데 있지 않습니다. 실제로 무슨 일이 일어나고 있는지 알려 주는 올바른 그림자, 즉 추적할 그림자를 찾는 데 있습니다. 일단 불꽃놀이 뒤에서 순서수가 째깍이고 있는 것을 보고 나면, 이 정리는 단지 참인 것이 아닙니다. 필연적으로 느껴집니다.
크기는 소음입니다. 구조가 신호입니다. 수열은 처음부터 집으로 향하고 있었습니다.
자주 묻는 질문
- 굿스타인 정리는 무엇을 말하나요?
- 굿스타인 정리는 모든 굿스타인 수열이, 중간에 아무리 크게 자라더라도, 결국 반드시 0에 도달한다고 말합니다. 성장이 천문학적인 규모로 이루어질 수 있고 상상할 수 없을 만큼 많은 단계가 필요할 수 있지만, 모든 시작값에 대해 종료가 보장됩니다.
- 수열이 계속 커지는데 어떻게 다시 0으로 돌아오나요?
- 각 항에는 숨겨진 순서수 짝이 있으며, 이 순서수는 매 단계마다 엄격하게 감소합니다. 눈에 보이는 자연수는 풍선처럼 부풀어 오를 수 있지만, 그 뒤에 있는 순서수는 오직 내려갈 수만 있습니다. 순서수의 감소하는 수열은 영원히 계속될 수 없으므로, 과정은 반드시 0에서 끝납니다.
- 세습적 n진법 표기법이란 무엇인가요?
- 숫자를 n진법으로 표기하고, 그 지수들도 다시 n진법으로 표기하는 것을 끝까지 반복하는 방식입니다. 예를 들어 4를 세습적 2진법으로 쓰면 2의 2제곱으로, 지수인 2도 2진법으로 표현됩니다.
- 굿스타인 정리가 논리학에서 왜 유명한가요?
- 참이지만 페아노 공리계만으로는 증명할 수 없기 때문입니다. 페아노 공리계에서 증명 불가능한 자연수에 관한 자연스럽고 인위적이지 않은 최초의 명제 중 하나였으며, 바로 그 이유로 수학과 논리학의 경계에 자리합니다.
- 히드라 게임이 같은 아이디어인가요?
- 그렇습니다. 커비와 파리스의 히드라는 동일한 수학을 재구성한 것입니다. 머리를 자르면 더 많은 머리가 자랄 수 있지만, 히드라는 결국 항상 쓰러집니다. 굿스타인 수열이 항상 0에 도달하는 이유와 정확히 같습니다.
