グッドスタインの定理
つまり指数でない全ての数字はnとなり、全ての指数(とその指数)はnまたは0になる( n 0 = 1 {\displaystyle n^{0}=1} である点に注意)。
例えば、35は2を底として普通に書くと 2 5 + 2 + 1 {\displaystyle 2^{5}+2+1} となるが、遺伝的記法で書くと
2 2 2 + 1 + 2 + 1 {\displaystyle 2^{2^{2}+1}+2+1}
となる。
数字mのグッドスタイン数列をG(m)と書き、次のように定義する。数列の初項はmとする。次項を得るには、mを2を底とした遺伝的記法で書いてから、現れる「2」を全て3に置換し、結果から1を引く。これがG(m)の第2項である。G(m)の第3項を得るには、一つ前の項(の3を底とした遺伝的記法)の「3」を全て4に置換し、結果からまた1を引く。以下、同様に繰り返し、結果が0になった時が数列の終わりである。
初めのほうのグッドスタイン数列はすぐに終結する。G(3)の様子を見てみよう。
この後の多くのグッドスタイン数列は非常に長い間に渡って増大し続ける。例えば、G(4)は次のように始まる。
G(4)の項はしばらく増大し続けるが、底が3 · 2となったところで最大値3 · 2 − 1に達し、そのまま3 · 2項の間同じ値を取り続けてから、最初で最後の下降を始める。
値が0となるのは底が3 · 2 − 1の時である。しかしながら、G(4)はグッドスタイン数列が「いかに」急速に増大し得るかについて、良い例とは言えない。G(19)ははるかに急速に増大する。立ち上がりを見てみよう。
これだけ急速に増大するにもかかわらず、グッドスタインの定理は、初項mが何であろうとグッドスタイン数列は必ず0で終わると主張する。