굿스타인의 정리
Goodstein's theorem수학적 논리학에서 굿스타인의 정리는 자연수에 관한 진술로, 1944년 르우벤 굿스타인(Ruben Goodstein)에 의해 증명된 것으로서, 모든 굿스타인의 수열은 결국 0으로 끝난다는 것을. 커비(Kirby)와 파리는[1] 페아노 산술에서는 증명할 수 없다는 것을 보여주었다(그러나 2차 산술과 같은 더 강력한 시스템에서는 증명할 수 있다).이는 괴델의 불완전성 정리와 게르하르트 겐첸의 1943년 페아노 산술에서 ε-유도성의0 비도덕성을 직접 입증한 사례에 이어 페아노 산술에서 증명할 수 없는 참된 진술의 세 번째 예였다.파리-해링턴 정리가 또 다른 예를 들었다.
로런스 커비와 제프 파리는 굿스타인 시퀀스와 유사한 행동을 가진 그래프 이데아틱 하이드라 게임을 도입했는데, '히드라'(신화학적 다두하이드라의 이름을 딴 레르나)는 뿌리가 있는 나무로, 그 '헤드'(나무의 가지) 중 하나를 잘라내는 것으로 동작이 이루어지며, 히드라는 한정된 숫자의 새로운 수를 키워 반응한다.일정한 규칙에 따르다커비와 파리는 헤라클레스가 머리를 자르는데 사용하는 전략과는 상관없이 히드라가 결국 살해될 것이라는 것을 증명했지만, 이것은 매우 오랜 시간이 걸릴지도 모른다.굿스타인 시퀀스처럼 커비와 파리는 페아노 산술만으로는 증명할 수 없다는 것을 보여주었다.[1]
유전기준-n 표기법
Goodstein 시퀀스는 "계속적 base-n 표기법"이라는 개념으로 정의된다.이 표기법은 통상적인 base-n 위치 표기법과 매우 유사하지만, 통상적인 표기법은 굿스타인의 정리 목적으로는 충분하지 않다.
n이 1보다 큰 자연수인 일반 base-n 표기법에서 임의의 자연수 m은 n:의 힘의 배수의 합으로 표기된다.
여기서 각 계수 a는i 0 ≤ ai < n을 만족하고, ≠ 0을k 만족한다.예를 들어, 베이스 2에서는
따라서 35의 base-2는 100011로 25 + 2 + 1을 의미한다. 마찬가지로 base-3로 표시된 100은 10201이다.
지수 자체는 base-n 표기법으로 작성되지 않는다는 점에 유의하십시오.예를 들어 위의 표현에는 2와5 3이4 있고, 5 > 2, 4 > 3이 있다.
base-n 표현을 세습 base-n 표기법으로 변환하려면 먼저 모든 지수를 base-n 표기법으로 다시 쓰십시오.그런 다음 지수 내부에 있는 모든 지수를 다시 쓰고, 표현식에 나타나는 모든 숫자(기준 자체를 제외)가 base-n 표기법으로 변환될 때까지 이러한 방식으로 계속한다.
예를 들어 일반 base-2 표기법에서 35는 25 + 2 + 1인 반면, 세습 base-2 표기법에서는 다음과 같이 표기한다.
5 = 22 + 1이라는 사실을 이용하여 유사하게 유전 베이스 3 표기법에서 100은
굿스타인 시퀀스
숫자 m의 Goodstein 시퀀스 G(m)는 자연수의 시퀀스다.시퀀스 G(m)의 첫 번째 원소는 m 그 자체다.두 번째 G(m)(2)를 얻으려면 m을 유전 베이스-2 표기법으로 쓰고, 2s를 모두 3s로 변경한 다음 결과에서 1을 뺀다.일반적으로 goodstein sequence of m의 (n + 1)-초기 용어 G(m)(n + 1)는 다음과 같다.
- G(m)(n)의 세습 베이스 n + 1 표현을 취한다.
- base-n + 1의 각 발생을 n + 2로 교체한다.
- 1을 빼라. (다음 항은 전기와 지수 n에 모두 의존한다.)
- 결과가 0이 될 때까지 계속하며, 이때 시퀀스가 종료된다.
초기 Goodstein 시퀀스는 빠르게 종료된다.예를 들어, G(3)는 6번째 단계에서 종료된다.
베이스 | 유전 표기법 | 가치 | 메모들 |
---|---|---|---|
2 | 3 | 3을 base-2 표기법으로 작성 | |
3 | 3 | 2를 3으로 바꾼 다음 1을 빼십시오. | |
4 | 3 | 3을 4로 바꾼 다음 1을 뺀다.이제 4초도 남지 않았다. | |
5 | 2 | 4초 남아서 5초.1만 빼면 돼. | |
6 | 1 | 5초 남아서 6초.1만 빼면 돼. | |
7 | 0 | 6초 남아서 7초.1만 빼면 돼. |
나중에 굿스타인 시퀀스는 매우 많은 수의 스텝에 대해 증가한다.예를 들어 G(4) OEIS: A056193은 다음과 같이 시작한다.
베이스 | 유전 표기법 | 가치 |
---|---|---|
2 | 4 | |
3 | 26 | |
4 | 41 | |
5 | 60 | |
6 | 83 | |
7 | 109 | |
11 | 253 | |
12 | 299 | |
24 | 1151 | |
Elements of G(4) continue to increase for a while, but at base , they reach the maximum of , stay there for the next steps, and그리고 나서 그들의 하강을 시작한다.
The value 0 is reached at base . (Curiously, this is a Woodall number: . This is also the case with all other fin4보다 큰 시작 값에 대한 기준)[citation needed]
그러나 G(4)조차 굿스타인 염기서열의 원소가 얼마나 빨리 증가할 수 있는지에 대한 좋은 생각을 주지 못한다.G(19)는 훨씬 더 빠르게 증가하며 다음과 같이 시작한다.
유전 표기법 | 가치 |
---|---|
19 | |
7625597484990 | |
| |
| |
이러한 급속한 성장에도 불구하고 굿스타인의 정리에는 모든 굿스타인의 순서는 결국 출발값이 어떻게 되든 0으로 종료된다고 명시되어 있다.
굿스타인의 정리 증명
굿스타인의 정리는 다음과 같이 증명할 수 있다(페아노 산술 외 기법을 사용, 이하 참조). 굿스타인의 수열 G(m)를 주어 엄격히 감소하고 종료되는 서수형 숫자의 평행 순서 P(m)를 구성한다.그러면 G(m)도 종료해야 하며, 0이 되어야 종료할 수 있다.이 증거에 대한 일반적인 오해는 G(m)가 P(m)에 의해 지배되기 때문에 0으로 간다고 믿는 것이다.사실 P(m)가 G(m)를 지배한다는 사실은 전혀 작용하지 않는다.중요한 점은: P(m)(k)가 존재하는 경우에만(병렬) G(m)(k)가 존재한다는 것이다.그 후 P(m)가 종료되면 G(m)도 종료된다.그리고 G(m)는 0에 해당하는 경우에만 종료할 수 있다.
u의 유전적 base k 표현을 계산한 다음 base k의 각 발생을 첫 번째 무한 서수 Ω으로 대체하는 = f ( , ) 함수를 정의한다.For example, .
그런 다음 시퀀스 P(m)의 각 용어 P(m)(n)는 f(G)(m)(n),n+1)로 정의된다.예를 들어 G(3)(1) = 31 = 2 + 2 및0 P(3)(1) = f(21 + 2,20) = Ω1 = Ω0 = Ω = Ω + Ω + 1. 순서형 숫자의 덧셈, 곱셈, 지수를 잘 정의한다.
는 f( ( )( n), + )> (n + ) + ) ,n+ ) () (