Goodstein의 정리와 증명불가능성

며칠 전에 Goodstein의 정리라는 걸 처음 봤다. 대충 위키피디아를 읽고 글을 써본다. ㅋㅋ 이 글에 나온 모든 지식은 위키피디아에 있음.

Goodstein의 정리가 뭔고 하면, 상속 n진법 표현(hereditary base-n notation)이라는 걸 생각해보자. 이건 또 뭔고 하면-_-

35는 이진법으로 2^5 + 2^1 +2^0 인데, 지수 5는 이진법으로 표현되지 않았으므로 다시 한 번 이진법으로 표현한다. 즉, 2^{2^2 +1} + 2^1 +2^0 이 hereditary base-2 notation이 된다.

임의의 어떤 수가 초항으로 주어질 때, hereditary base-2 notation부터 시작해서 hereditary base-n notation을 hereditary base-(n+1) notation으로 바꿔치기 한 후 1을 뺀 수를 다음 항으로 하는 수열을 생각하자.

예를 들어 위키피디아에 나온 예시를 그대로 옮겨보자.
초항이 19 = 2^{2^2}+2^1 + 2^0이면,
두 번째 항은 3^{3^3} + 3^1 + 3^0 -1 = 7625597484990이 된다. ㅋ
세 번째 항은 4^{4^4} + 3 \approx 1.3 \times 10^{154} 이 되고,
네 번째 항은 5^{5^5} + 2 \approx 1.8 \times 10^{2184}
다섯 번째 항은 6^{6^6} + 1 \approx 2.6 \times 10^{36305}
여섯 번째 항은 7^{7^7} \approx 3.8 \times 10^{695974}
일곱 번째 항은
\begin{gathered}8^{8^8} -1 = \hfill \\ \quad 7\cdot 8^{7\cdot 8^7 + 7\cdot 8^6 + 7\cdot 8^5 + 7\cdot 8^4 +7\cdot 8^3 +7\cdot 8^2 +7\cdot 8+7}+\hfill\\ \quad 7\cdot 8^{7\cdot 8^7 + 7\cdot 8^6 + 7\cdot 8^5 + 7\cdot 8^4 +7\cdot 8^3 +7\cdot 8^2 +7\cdot 8+6}+\\ \quad \cdots +7\cdot 8^2 + 7\cdot 8 +7 \hfill\\ \quad \approx 3 \times 10^{15151335}\hfill\end{gathered}
이 된다. 아놔-_-

이런 수열을 Goodstein 수열이라고 하는데, Goodstein의 정리는, 모든 Goodstein 수열은 궁극적으로 영에 수렴한다는 정리이다. 헐-_- 저게 영이 된다고??

근데 증명은 ordinal number를 가지고 하는 것 같다. 별로 수 같지 않은 존재지만-_- ordinal number의 addition, multiplication, exponentiation이 잘 정의돼 있다고 한다. 각 base를 ordinal number로 바꿔치기한 새로운 수열을 병렬적으로 생각하면 strictly하게 감소하기 때문에, 이 병렬적 수열이 영에 수렴하기 때문에 Goodstein 수열도 영으로 수렴한다고 하는 듯. 사실 잘 이해가 안 돼서 책을 좀 찾아봤는데, 수리논리학 책을 본 적이 없으니 아놔 봐도 잘 이해가 안 됨-_-

근데 뭔가 수 같지 않은 걸로 증명하는게 영 보기 좋지 않은데, 정수론 문제니까 정수 집합 안에서 깔삼하게 증명 안되나? 싶은 생각이 드는데, 여기서 대 반전-_-!!! 이 정리는 Peano arithmetic에서 증명이 불가능하다는 것이 증명되었다고 한다. 위키피디아를 보니 이 증명은 꽤 빡세다고 하네-_-

여하간, 참인 명제지만 공리계 안에서 증명 불가능한 사례인데, 일전에 이야기한 적[1]이 있다. 보통 이런 명제는 자기를 지칭하는 self-reference를 포함하는 어거지 같은 명제가 많지만 (나는 거짓말을 하고 있다!! 이런 거-_-) 몇 안 되는 self-reference가 아닌 명제들 이라나 뭐라나.

 


[1] 내 백과사전 참인 명제와 증명가능한 명제의 차이 2017년 3월 18일

4 thoughts on “Goodstein의 정리와 증명불가능성

    • 위키피디아 goodstein 정리 항목에서 히드라 어쩌구 하는게 이 내용이었군요. ㅎㅎ 저도 공부해 보고 싶은데 능력부족이라 … ㅎㅎ

  1. 증명의 핵심은 ordinal number들이 well-ordered 이기 때문에 strictly decreasing sequence 는 멈춰야 한다는 것이지요. 이 증명 자체는 정말 간단명료한데 PA 안에서는 증명이 안 된다니 팔짝 뛸 노릇입니다 ㅋㅋ Goodstein sequence 처럼 매우매우 빨리 증가하는 수열들에 (취미로) 관심있는 사람들도 있더군요. http://googology.wikia.com/wiki/Googology_Wiki -_-

댓글이 닫혀있습니다.