Gödel, Escher, Bach An Eternal Golden Braid by Douglas R. Hofstadter

FALSE? [N] = YES if N, seen as a TNT-string, IS a false statement of

number theory; otherwise NO.

(e.g., FALSE? [666111666] = NO,

FALSE? [223666111666] = YES,

FALSE? [7014] = NO)

The last seven examples are particularly relevant to our future

metamathematical explorations, so they highly merit your scrutiny.

Expressibility and Representability

Now before we go on to some interesting questions about BlooP and are led

to its relative, FlooP, let us return to the reason for introducing BlooP in

the first place, and connect it to TNT. Earlier, I stated that the critical mass

for Godel's method to be applicable to a formal system is attained when all

primitive recursive notions are representable in that system. Exactly what

does this mean? First of all, we must distinguish between the notions of

representability and expressibility. Expressing a predicate is a mere matter

of translation from English into a strict formalism. It has nothing to do with

theoremhood. For a predicate to be represented, on the other hand, is a

much stronger notion. It means that

(1) All true instances of the predicate are theorems;

(2) All false instances are nontheorems.

By "instance", I mean the string produced when you replace all free

variables by numerals. For example, the predicate m + n = k is represented

in the pq-system, because each true instance of the predicate is a theorem,

each false instance is a nontheorem. Thus any specific addition, whether

true or false, translates into a decidable string of the pq-system. However, the

pq-system is unable to express-let alone represent-any other properties

of natural numbers. Therefore it would be a weak candidate indeed in a

competition of systems which can do number theory.

Now TNT has the virtue of being able to express virtually any number-

theoretical predicate; for example, it is easy to write a TNT -string which

expresses the predicate "b has the Tortoise property". Thus, in terms of

expressive power, TNT is all we want.

However, the question "Which properties are represented in TNT?" is

precisely the question "How powerful an axiomatic system is TNT?" Are all

possible predicates represented in TNT? If so, then TNT can answer any

question of number theory; it is complete.

Primitive Recursive Predicates Are Represented in TNT

Now although completeness will turn out to be a chimera, TNT is at least

complete with respect to primitive recursive predicates. In other words, any

statement of number theory whose truth or falsity can be decided by a

BlooP and F100P and GlooP 417