**◄ ***Index***◄
***Main essay*

Three beliefs that lend illusory legitimacy to Cantor’s diagonal argument

Bhupinder
Singh Anand[1]

(*A .pdf file of this essay before the current update
is available at **http://arXiv.org/abs/math/0304310*)

1. Cantor’s
diagonal argument, Gödel’s proof, and Turing’s Halting problem

Whatever other beliefs there may remain for considering Cantor’s diagonal argument[2] as mathematically legitimate, there are three that, prima facie, lend it an illusory legitimacy; they need to be explicitly discounted appropriately.

The first - Cantor’s diagonal argument defines a non-countable Dedekind real number[3]; the second - Gödel uses the argument to define a formally undecidable, but interpretively true, proposition; and the third - Turing uses the argument to define an uncomputable Dedekind real number.

2. Cantor’s
diagonal argument

In the first case, we may, Platonically[4], define any natural number, expressed in binary notation, and followed by a period and a non-terminating sequence of the integers 0 and 1, as a Cantorian real number.

Cantor’s diagonal argument, then, considers any, given, 1-1 correspondence:

(*) *n* ↔ *C*_{n}

where *n* ranges over the natural numbers, and *C** _{n}* is a
Cantorian real number of the form 0.

It is not at all obvious, however, that the following conclusion can be drawn from the above argument:

Every Cantorian real number necessarily defines a classical[5] Dedekind cut[6] in the rational numbers (or its, classically equivalent, Cauchy sequence[7] of rationals).

For instance, we note, first, that the
classical definition of a Cauchy sequence, {*s _{n}*}, of rational numbers,
implicitly implies that, for each such sequence, there is some effective method
of proving that, given any rational number

Since there can only be denumerable
such effective methods, it follows that, classically, the real numbers, when
defined as Cauchy sequences, are denumerable. It, also, follows that the
Cantorian real number defined by the diagonal argument cannot be assumed,
without a constructive proof, to be a classical Dedekind real number.

Second,
consider the non-terminating series of the odd natural numbers 1, 3, 5, 7, ...
. We can express this as the non-terminating binary series:

1, 11, 101, 111, ... ,

and correspond
to it the non-terminating sequence of rational numbers:

0.1, 0.11, 0.101, 0.111, ... .

Clearly, this last series oscillates; it can, prima facie, be computed by a classical Turing machine; and it defines a Cantorian real number if we, not entirely unreasonably, Platonically interpret Turing’s various postulations[8], in his seminal paper [Tu36], to implicitly imply that the non-terminating sequence of instantaneous tape descriptions[9] of every, non-halting, “circle-free a-machine”, uniquely defines a mathematical object that consists of a non-terminating sequence of the integers 0 and 1, whose individual terms are not necessarily computable.

However, equally clearly, the above series does not yield a Cauchy sequence of rational numbers that can be taken to define[10] a Dedekind real number[11].

Cantor’s argument should, therefore,
be interpreted only as establishing that we cannot define a number-theoretic
function *f*(*n*)
= *C** _{n}*
in such a way that the range of

However, there may yet be some
definable number-theoretic function, *f*(*n*), such that:

(*a*) its range contains all the Dedekind real
numbers;

(*b*) it is undefined in the class R of Dedekind
real numbers for some values in its domain;

(*c*) it is defined for these values in the extended
class of Cantorian real numbers (which clearly contains all the Dedekind real
numbers).

Such a function, moreover, need not be
algorithmically computable. Thus there may be no Turing machine T such that,
given any natural number *k*, T halts if, and only if, it can be held to compute the
Cantorian real number *f*(*k*). This would be the case if there were, for instance, some
*k* such
that any effective method of computing *f*(*k*) were necessarily dependent on *k*, and, so, not
necessarily an effective method of computing *f*(*n*) for every *n*.[12]

The conclusion: We can neither conclude that Cantor’s diagonal argument determines an uncountable Dedekind real number, nor conclude from it that the cardinality of the Dedekind real numbers necessarily differs from that of the Dedekind (Peano) natural numbers[13].

3. Gödel’s proof

In the second case, Gödel’s use of the diagonal argument, in his seminal 1931 paper on formally undecidable propositions [Go31a], is purely illustrative. He uses it in his Introduction simply to sketch the main ideas of his Theorem VI heuristically, without claiming any formal rigour. The aim of his paper, as he then remarks, is to show that ([Go31a], p9):

... The method of proof which has just been explained can obviously be applied to every formal system which, first, possesses sufficient means of expression when interpreted according to its meaning to define the concepts (especially the concept ‘provable formula’) occurring in the above argument; and, secondly, in which every provable formula is true. In the precise execution of the above proof, which now follows, we shall have the task (among others) of replacing the second of the assumptions just mentioned by a purely formal and much weaker assumption.

The question arises: Is it valid to treat Gödel’s heuristic argument, based on a semantic concept of intuitive “soundness[14]”, as being equivalent to his Theorem VI? Such equivalence is, of course, intuitionistically objectionable; even classically, set-theoretic arguments[15] corresponding to Cantor’s diagonal argument are not considered constructive in any sense.

That Gödel did not consider the two as equivalent is suggested by his remarks at the end of his Theorem VI ([Go31a], p26):

One can easily convince oneself that the proof we have just given is constructive (for all the existential assertions occurring in the proof rest upon Theorem V which, as it is easy to see, is intuitionistically unobjectionable), ... .

Thus, Gödel’s conversion of the non-constructive, semantic, argument into a syntactic one that he considered constructive, and intuitionistically unobjectionable, is significant; although a strong Platonist, Gödel’s remarks indicate that he intended to ensure that his argument, in Theorem VI, does not admit possible inconsistencies that could be argued as being inherent in the classically accepted non-constructivity of Cantor's diagonal argument.

4.1 Turing real numbers

In the third case, the real numbers considered by Turing, in his original 1936 paper on computable numbers [Tu36], were explicitly defined as the computations of “circle-free a-machines”. Turing wrote:

(*i*) The
“computable” numbers may be described briefly as the real numbers whose
expressions as a decimal are calculable by finite means.

(*ii*)
According to my definition, a number is computable if its decimal can be
written down by a machine.

(*iii*) The computable numbers do not, however, include all
definable numbers, and an example is given of a definable number which is not
computable.

(*iv*)
If at each stage the motion of a
machine ... is *completely* determined by the configuration, we shall
call the machine an “automatic machine” (or *a*-machine).

(*v*) If an *a*-machine prints two kinds of symbols,
of which the first kind (called figures) consists entirely of 0 and 1 (the others
being called symbols of the second kind), then the machine will be called a
computing machine. If the machine is supplied with a blank tape and set in
motion, starting from the correct initial *m*-configuration, the
subsequence of the symbols printed by it which are of the first kind will be
called the *sequence computed by the machine*. The real number whose
expression as a binary decimal is obtained by prefacing this sequence by a
decimal point is called the *number computed by the machine*.

Thus, Turing implicitly implied here
that every *a*-machine could be said to “compute” a binary sequence,
which, in turn, could be suitably interpreted as defining a real number.

(*vi*) If a computing machine never writes down more than a
finite number of symbols of the first kind it will be called *circular*.
Otherwise it is said to be *circle-free*.

(*vii*) A sequence is said to be computable if it can be
computed by a circle-free machine. A number is computable if it differs by an
integer from the number computed by a circle-free machine.

Since a circle-free *a*-machine
may not halt, this clarification of Turing’s can, not unreasonably, be
interpreted as, again implicitly, defining the irrational numbers between 0 and
1 as the non-terminating sequence of instantaneous tape descriptions of a
non-halting, circle-free, *a*-machine. The rational numbers between 0 and
1 correspond, obviously, to the finite sequence of instantaneous tape
descriptions of a halting *a*-machine.

However, as in the case of Cantorian
real numbers, we cannot assume, in the absence of a formal, constructive and
intuitionistically unobjectionable[16],
proof, that a given Turing real number, as defined, implicitly, in (*v*) and (*vii*) above, is also a
Dedekind real number.

**4.2 **** Turing’s Halting argument**

Although Turing appears to argue in his paper [Tu36] that Cantor’s argument can be taken to establish the Platonic existence of an uncomputable Turing real number, he seems to have been ambivalent about using the argument unrestrictedly whilst introducing his Halting argument.

Perhaps, echoing Gödel’s earlier reservations to some extent, Turing too felt the need to express - albeit obliquely - awareness of a non-constructive element in the use of Cantor’s diagonal argument to define a Dedekind real number. Whatever the reason, he offered an alternative argument that was, essentially, based on defining an uncomputable number-theoretic function, rather than on non-constructively postulating that a period, followed by a non-terminating sequence of the digits 0 and 1, necessarily defines a Dedekind real number.

The ambivalence is reflected below, in Turing’s description of the Halting problem [Tu36]:

(*viii*) ... we might apply the diagonal process. “If the
computable sequences are enumerable, let I* _{n}* be the

The fallacy in this argument lies in the assumption that J is computable. It would be true if we could enumerate the computable sequences by finite means, but the problem of enumerating computable sequences is equivalent to the problem of finding out whether a given number is the D.N of a circle-free machine, and we have no general process for doing this in a finite number of steps. In fact, by applying the diagonal process argument correctly, we can show that there cannot be any such general process.

The simplest and most direct proof of this is by
showing that, if this general process exists, then there is a machine which
computes J. This proof, although perfectly sound, has the
disadvantage that it may leave the reader with a feeling that “there must be
something wrong”. The proof which I shall give has not this disadvantage, and
gives a certain insight into the significance of the idea “circle-free”. It
depends not on constructing J, but on constructing J*'*, whose *n**’*th figure is Y* _{n}*(

(*ix*) Let us suppose that there
is such a process; that is to say, that we can invent a machine D which, when supplied with the S.D of any
computing machine M will test this S.D and if M is circular will mark the S.D with the symbol “*u*” and if it is circle-free will mark it
with “*s*”. By combining the machines D
and I we could construct a
machine M to compute the
sequence J*'*. The machine D may require a tape. We may suppose that
it uses the *E*-squares beyond all
symbols on *F*-squares, and that
when it has reached its verdict all the rough work done by D is erased.

The
machine H has its motion divided
into sections. In the first *n*–1 sections, among other things, the
integers 1, 2, …, *n*–1 have been written down and tested by the
machine D. A certain number, say
*R*(*n*–1), of them
have been found to be the D.N’s of circle-free machines. In the *n**’*th section the machine D
tests the number *n*. If *n* is satisfactory, *i.e*., if it is the D.N of a
circle-free machine, then *R*(*n*)
= 1+*R*(*n*–1)
and the first. *R*(*n*)
figures of the sequence of which a D.N is *n* are calculated. The *R*(*n*)*’*th figure of this sequence is written down as one of the
figures of the sequence J' computed by H. If *n* is not satisfactory, then *R*(*n*) = *R*(*n*–1) and the machine
goes on to the (*n*+1)*’*th section of its
motion.

(*x*) From the construction
of H we can see that H is circle-free. Each section of the
motion of H comes to an end after
a finite number of steps. For, by our assumption about D, the decision as to whether *n*
is satisfactory is reached in a finite number of steps. If *n*
is not satisfactory, then the *n**’*th
section is finished. If *n* is satisfactory, this means that the
machine M(*n*)
whose D.N is *n* is circle-free, and therefore its *R*(*n*)*’*th figure can be calculated in a finite number of steps.
When this figure has been calculated and written down as the *R*(*n*)*’*th figure of J*'*, the *n**’*th section is finished. Hence H
is circle-free.

(*xi*) Now let *k*
be the D.N of H. What does H do in the *k**’*th section of its motion? It must test whether *k*
is satisfactory, giving a verdict “*s*”
or “*u*”. Since *k*
is the D.N of H, and since H is circle-free, the verdict cannot be “*u*”. On the other hand the verdict cannot
be “*s*”. For if it were, then in
the *k**’*th section of its motion H
would be bound to compute the first *R*(*k*–1)+1
= *R*(*k*) figures of
the sequence computed by the machine with *k* as its D.N and to
write down the *R*(*k*)’th
as a figure of the sequence computed by H.
The computation of the first *R*(*k*)–1
figures would be carried out all right, but the instructions for calculating
the *R*(*k*)’th
would amount to “calculate the first *R*(*k*)
figures computed by *H* and write
down the *R*(*k*)’th”.
This *R*(*k*)’th
figure wonld never be found. *I.e*., H is circular, contrary both to what we
have found in the last paragraph and to the verdict “*s*”. Thus both verdicts are impossible and
we conclude that there can be no machine D.

**4.3**** The Halting problem and CT**

Now,
Turing’s alternative argument is, essentially, the following form of the Halting problem[18]:

Suppose we have a Turing machine ** WillHalt**
which, given an input string

Moreover,
without appealing to Cantor’s diagonal argument, it is easily proven by
contradiction that Turing machine ** WillHalt**(

If “** WillHalt**(

Prima
facie, the definition appears similar to that of a “** Liar**”
proposition as “The ‘

So, if
we accept that ** WillHalt**(

4.4 CT and Turing’s “oracle”

We note
that, in his paper [Tu36], Turing did not
conclude from his Halting argument that a function such as ** WillHalt**(

Turing's 1938
Princeton Ph.D. thesis, work conducted in close cooperation with Church, was
entitled Systems of logic defined by ordinals, and published
as (Turing 1939). Predominantly the work consisted of highly technical
developments within mathematical logic. However the driving force lay in the
question: what is the consequence of supplementing a formal system with
uncomputable deductive steps? In pursuit of this question, Turing introduced the
definition of an “oracle” which can supply on demand the answer to the halting
problem for every Turing machine. ... Turing defined the “oracle” purely
mathematically as an uncomputable function, and said, “We shall not go any
further into the nature of this oracle apart from saying that it cannot be a
machine.” The essential point of the oracle is that it performs *non-mechanical*
steps.

Clearly,
if the Church-Turing Thesis is false, then ** WillHalt** can be a
machine; further, if

Now, prima facie, it is reasonable to
assume that we can, in principle, modify the definition of a Turing machine T
so that it will always recognise a “looping” situation; we simply specify that
T record every instantaneous tape description at the execution of each machine
instruction (in the manner of a classical - albeit virtual and infinite -
two-dimensional, teleprinter-type tape), and compare the current instantaneous
tape description with the record before proceeding to the next instruction. We
could, further, instruct the machine T to interrupt the computation, and to
assign arbitrary values and, or, further associated actions, to those instances
of ** WillHalt**(

Is such a machine a classical Turing machine? Is the resultant predicate well-defined? Does the above construction transform a Turing-undecidable predicate into an effectively decidable one? It is not obvious whether classical theory can provide unequivocal answers to these questions without recourse to CT, which would beg the question.

Clearly, if we can show, or accept,
that the extended ** WillHalt**(

5. The influence of Gödel’s reasoning

We can argue that the Platonist roots of Turing’s “oracle” are dimly visible in the classical acceptance of the non-constructivity that is implicit in Gödel’s reasoning. Prima facie, most classical interpretations uncritically draw sustenance, and strength, from the original reasoning and conclusions expressed by Gödel in his 1931 paper. Thus it would not be surprising if classically accepted heuristic, and formal, expositions are founded on implicit, non-constructive, Platonist assumptions that could be implicit in Gödel’s formal, and informal, reasoning. The non-constructive logical consequences of such arguments would also, then, be classically accepted - perhaps reluctantly - simply because their non-constructive roots are obscurely hidden in such implicit premises.

For instance, Gödel’s and Rosser's reasoning on the definability of “undecidable” sentences in any Peano Arithmetic, assuming its consistency, is classically viewed as being definitively formal. The numerous attempts to challenge the reasoning and its conclusions over the years (starting with Wittgenstein most notably, and apparently led by Yessenin-Volpin later) have invariably, and quite effectively, attracted the fatal criticism of being heuristic, and non-formal, by Gödel’s standard of constructiveness.

However, both Gödel’s and Rosser's arguments are based on critical interpretations of their formal arguments that appeal to semantic elements at some point in their reasonings. Anomalous consequences of such reasoning[22] could be obscured if, having accepted these results as definitively formal, classical expositions of the arguments appeal at some critical points to heuristic interpretations and reasoning for ease of exposition. Classical theory may, then, be focusing more on the implications of the accepted interpretations of Gödel’s reasoning, and less on seeking any possible non-formal components that may be implicit either in the reasoning, or in its interpretation.

[Go31a] Gödel,
Kurt. 1931. *On formally undecidable propositions of Principia Mathematica
and related systems I*. In M. Davis (ed.). 1965. The Undecidable. Raven
Press,

[Go31b] Gödel, Kurt.
1931. *On formally undecidable propositions of Principia Mathematica and
related *

<*Web page*: http://home.ddc.net/ygg/etext/godel/index.htm>

[Go51] Gödel, Kurt.
1951.* Some basic theorems on the foundations of mathematics and their
implications. *Gibbs lecture. In Kurt Gödel, Collected Works III, pp.
304-323. 1995. Unpublished Essays and Lectures. S. Feferman et al (ed.).

[Ho00] Hodges,
A. 2000. *Uncomputability in the work of Alan Turing and
Roger Penrose*. (

<*Web
page*: http://www.turing.org.uk/philosophy/lecture1.html>

[HW98] Hodges, W.
1998. *An editor recalls some hopeless papers. *The Bulletin of Symbolic
Logic, Volume 4, Issue 1, March 1998, pages 1-16.

<*Web
link*: http://www.math.ucla.edu/%7Easl/bsl/0401-toc.htm>

[Me64] Mendelson,
Elliott. 1964. Introduction to Mathematical Logic. Van Norstrand,

[Ru53] Rudin,
Walter. 1953. Principles of Mathematical Analysis.

[Tu36] Turing,
Alan. 1936. *On computable numbers, with an application to the
Entscheidungsproblem*.

<*Web
page*: http://www.abelard.org/turpap2/tp2-ie.asp>

(*Updated: Friday
17 ^{th} September 2:53:53 AM IST by re@alixcomsi.com*)

**◄ ***Index*** ▲ **Top
of page

[1] The author is an independent scholar. E-mail: re@alixcomsi.com; anandb@vsnl.com.

[4] By
Platonically we mean it is not necessary that, given any natural number *n*, we have access
to an effective method for calculating the *n*’th term of the sequence in the
definition that follows.

[5] For the purposes of this essay we take Rudin [Ru53], and Mendelson [Me64], as representative, in the areas that they cover, of standard expositions of classical real analysis, and, first order logic and effective computability, respectively.

[12] Of particular interest, are Turing’s following remarks:

“The expression ‘there is a
general process for determining …’ has been used throughout this section as
equivalent to ‘there is a machine which will determine …’ This usage can be
justified if and only if we can justify our definition of ‘computable’. For
each of these ‘general process’ problems can be expressed as a problem
concerning a general process for determining whether a given integer *n* has a property
*G*(*n*)
[*e.g.* *G*(*n*) might mean ‘*n* is satisfactory’ or ‘*n* is the Gödel
representation of a provable formula’], and this is equivalent to computing a
number whose *n*’th
figure is 1 if *G* (*n*) is true and 0 if it is false. ...

... The computable numbers
do not include all (in the ordinary sense) definable numbers. Let P be a sequence whose *n*’th figure is 1
or 0 according as *n*
is or is not satisfactory. It is an immediate consequence of the theorem of §8 that P is not computable. It is (so far as we
know at present) possible that any assigned number of figures of P can be calculated, but not by a uniform
process. When sufficiently many figures of P
have been calculated, an essentially new method is necessary in order to obtain
more figures.”

This point was echoed later by, in this case, Gödel - in his Gibbs lecture - where he, again implicitly, suggested that not every effective method need necessarily be algorithmic, although every algorithm is, necessarily, an effective method [Go51]:

“I wish to point out that
one may conjecture the truth of a universal proposition (for example, that I
shall be able to verify a certain property for any integer given to me) and at
the same time conjecture that no general proof for this fact exists. It is easy
to imagine situations in which both these conjectures would be very well
founded. For the first half of it, this would, for example, be the case if the
proposition in question were some equation *F*(*n*) = *G*(*n*) of two
number-theoretical functions which could be verified up to very great numbers *n*.”

[13] We note that the latter result can, however, be proved non-constructively in an axiomatic set theory such as, say, ZFC, (see [Ru53], p34, Theorem 2.40, Corollary).

[14] A formal theory is considered “sound” if its theorems are true under its standard interpretation.

[17] Turing’s Halting argument can, also, be interpreted as implying that, whereas every Turing real number (his computable sequence) is, obviously, a Cantorian real number, some Cantorian real numbers are not Turing real numbers (computable sequences).

[18] Cf. David Matuszek’s lecture notes at http://www.netaxs.com/people/nerp/automata/halting2.html.

[19] We note
that definitions such as those of the “** Liar**” proposition and of
the “

Clearly, if the raison d'etre of a language is to be a medium for communicating properties about content that lies outside the language, then the self-referential study of the internal structure of a language must also aim at effectively unambiguous communication - in this case, of the nature and structure of formal, finite, strings that are finitely constructible within the language.

Admitting non-finite, non-constructive elements into the language may compromise it to the point where we could permit non-communicable (or, more accurately, non-discernible) entities to be reflected in the language in such a way that they can be interpreted ambiguously by various interpretations - and yet give the illusion of unambiguous interpretation within each interpretation.

For instance, if we accept the argument that Cantorian real numbers are not necessarily Dedekind real numbers, then Cantor's diagonal construction may, indeed, be a notable example of such ambiguous interpretation.

[20] We note
that, in the *k*’th
section, machine H will input, and attempt to simulate, machine *k*, on input *k*, ad infinitum.

[21] That ** WillHalt**(

[22] For instance, although Gödel’s semantic reasoning is, indeed - as he remarks - constructive and intuitionistically unobjectionable, Rosser’s application of the Deduction Theorem, on the basis of a semantic hypothesis is, prima facie, non-constructive, intuitionistically objectionable, and arguably valid.

Briefly, Rosser’s informal
meta-argument seems to depend critically on the semantic argument that (cf. [Me64], p146), assuming [*H*] is a
provable formula in any Peano Arithmetic, PA, which is assumed simply
consistent, and assuming, further, that *j* is the Gödel-number of a proof of [*H*]
in PA, and given that:

(*i*) If PA proves: [*H*],
then PA proves: [*q*(*j*)],

where [*q*(*y*)] is also a PA-formula,
we may conclude, by the standard Deduction Theorem of first-order logic, that:

(*ii*) PA proves: [*H*
→ *q*(*j*)].

However, such a conclusion
is questionable, since (*ii*) may not be true.

To see this, note that,
given any natural number *h*, we could construct a Turing-machine T that would
decompose *h*
to check whether it is in fact the Gödel-number of some well-formed formula [*H*]
of PA. However, assuming the provability of [*H*], T would be unable to
conclude that the meta-assertion (*ii*) is valid, since the assertion does
not hold for every natural number *j*. Such validity would, of course, follow if (*ii*) is
valid.

In other words, the formal
meta-mathematical expression of (*i*) is, actually, the meta-statement:

(*iii*) If PA proves:
[*H*], then there is some *j* such that PA proves: [*q*(*j*)].

Now, from this, we cannot conclude (as Rosser does) that:

(*iv*) If PA proves: [*H*],
then PA proves: [(E*j*)*q*(*j*)].

Thus, from (*iii*), we
may only conclude that, under the standard interpretation, it is true there
must, then, be a number *j*. However, for *j* to be introduced as a primitive symbol into a formal
PA-proof, as in Rosser's arguments (*i*) and (*ii*), where he applies
the Deduction Theorem, we also need a formal PA-proof that, under Rosser’s
hypothesis, the number *j* is adequately defined in every interpretation. However,
[(E*j*)*q*(*j*)] may be
PA-unprovable.

Moreover, if *j* is Turing uncomputable, then *j* may not be
adequately definable by any PA-formula, and so the Deduction Theorem cannot be
applied to the meta-assertion (*i*), to conclude (*ii*), within a
formal proof sequence of PA, so as to yield Rosser’s undecidable proposition in
PA.

Of course, the deduction:

PA proves: [*q*(*j*)]

would follow from standard
logical axioms if it could, indeed, be shown that [(E!*j*)*q*(*j*)] is
PA-provable (where “!” signifies uniqueness) - which is not the case.

In other words, Rosser's
argument simply assumes, implicitly, that, if we are given an *h* as above, then
some *j*
is always Turing-computable (hence there is always a PA-formula that uniquely
represents such *j*),
and arrives at a contradiction. However, the contradiction only establishes
that *j*
may be Turing-uncomputable
for some *h*.
In the absence of a PA-proof of (*iv*), we cannot logically conclude from
this, as he seems to do, that there is no such *j*.

[23] MSC-class: 03B10

Key words: Algorithm, arithmetic, Cantor, Cauchy, Church, circle-free, classical, computable, consistent, constructive, Dedekind, diagonal construction, effective method, formal system, function, Gödel, interpretation, instantaneous, intuitive, loop, mapping, mathematical object, model, natural number, non-terminating, number-theoretic, Peano, Platonic, predicate, proposition, real number, satisfactory, sentence, set theory, sound, standard model, tape description, Turing, uncomputable, uncountable, undecidable, uniform method.