Not to be confused with Transcendental number.

The transcendental integers are a set of huge numbers, defined by Harvey Friedman.[1]

If \(n\) is an integer then we call it transcendental if the following holds: let M be a Turing machine, such that there is proof in ZFC of length at most \(2^{1,000}\) showing that M halts. Then M halts in at most \(n\) steps. In other words, \(n\) is greater than or equal to halting time of every Turing machine with ZFC proof of halting of length at most \(2^{1,000}\).

Properties

It is clear that if \(m>n\) and \(n\) is transcendental, then so is \(m\). Equivalently, transcendental integers are upwards closed, and consequently there is a smallest transcendental integer.

Friedman suspects that this kind of numbers should naturally arise in Boolean relation theory. It is very likely that transcendental integers quickly appear in Friedman's finite promise games, because corresponding functions outgrow all provably recursive functions of SMAH, which is strong extension of ZFC. However, no specific examples of nontrivial transcendental integers are known.

Extension

A function naturally arises from the definition of a transcendental integer. It is further extended to \(\textrm{TR}\) function.

Well-definedness

Even when we are working in \(\textrm{ZFC}\) set theory, the well-definedness of the least transcendental integer is non-trivial, as we do not have a proof of the \(\Sigma_1\)-soundness of \(\textrm{ZFC}\) set theory by Goedel's incompleteness theorem.

Indeed, the inconsistency of \(\textrm{ZFC}\) set theory itself, i.e. \(\neg \textrm{Con}(\textrm{ZFC})\), might be provable under \(\textrm{ZFC}\) set theory. In that case, the statement "The termination of any Turing Machine is provable under \(\textrm{ZFC}\) set theory" is provable under \(\textrm{ZFC}\) set theory. Now readers are supposed to understand how non-trivial the well-definedness of the least transcendental integer is. In fact, it is known that the least transcendental integer is well-defined in the sense that it is meta-theoretically provable that the existence of the least transcendental integer is provable under \(\textrm{ZFC}\) set theory. However, if we try to explicitly write down the proof of the well-definedness following the meta-theoretic proof, then the resulting proof is of length \(2^{1000}\).

For the issue, see the article of TR function.


Sources

See also

Community content is available under CC-BY-SA unless otherwise noted.