超越整数 (transcendental integers) は、Harvey Friedman が定義した巨大数の分類である[1]。
整数\(n\)が次の条件を満たすときに限り、\(n\)は超越整数であるとする。 チューリングマシン M が停止するということを、ZFCで\(2^{1000}\)個以内の記号で証明できるのであれば、必ず M は\(n\) ステップ以内で停止する。すなわち、\(n\)はZFCによる停止性の証明が\(2^{1000}\)個以内の記号でできるようないかなるチューリングマシンの停止時間よりも大きいかまたは等しい。
性質[]
明らかに\(m>n\)かつ\(n\)が超越整数ならば、\(m\)も超越整数である。言い換えれば、超越整数は上に閉じており、したがって最小の超越整数が存在する。
Friedmanはこの種の数がブール関係理論に自然に生じると考えている。超越整数がFriedmanの有限約束ゲームに速やかに現れるのは非常にありそうなことである。なぜならば対応する関数はすべてのSMAHの可証再帰関数よりも急速に増加し、SMAHはZFCの強い拡張だからである。しかし、非自明な超越整数の特定の例は知られていない。
拡張[]
超越整数の定義から関数が自然に生じる。さらなる拡張が\(\textrm{TR}\)関数である。
well-defined性[]
\(\textrm{ZFC}\)集合論で作業していたとしても、最小の超越整数のwell-defined性は自明ではない。なぜならば、\(\textrm{ZFC}\)集合論の\(\Sigma_1\)健全性はゲーデルの不完全性定理により証明できないからである。
実際、\(\textrm{ZFC}\)集合論が自身の矛盾性、つまり\(\neg \textrm{Con}(\textrm{ZFC})\)が証明可能である可能性がある。その場合、\(\textrm{ZFC}\)集合論において「\(\textrm{ZFC}\)集合論は任意のチューリングマシンの停止性を証明可能である」ということを証明可能である。このことを踏まえると、最小の超越整数のwell-defined性がいかに非自明なものか理解できるだろう。結論から言うと最小の超越整数のwell-defined性が\(\textrm{ZFC}\)公理系で証明可能であることはメタに証明可能であるが、そのメタな証明に従って実際に\(\textrm{ZFC}\)公理系で証明を書き下そうものならその長さ自体が\(2^{1000}\)字を超えてしまうのである。
この問題については、TR関数の記事を参照のこと。