◄ Index 
◄
Main essay
Do Gödel’s incompleteness theorems set absolute limits
on the ability of the brain to express and communicate mental
concepts verifiably?
A lay
perspective
Bhupinder
Singh Anand[1]
Classical interpretations of Gödel’s formal
reasoning, and of his conclusions, implicitly imply that mathematical languages
are essentially incomplete, in the sense that the truth of some arithmetical
propositions of any formal mathematical language, under any interpretation, is,
both, non-algorithmic, and essentially unverifiable. However, a language of
general, scientific, discourse, which intends to mathematically express, and
unambiguously communicate, intuitive concepts that correspond to scientific
investigations, cannot allow its mathematical propositions to be interpreted
ambiguously. Such a language must, therefore, define mathematical truth
verifiably. We consider a constructive interpretation of classical, Tarskian,
truth, and of Gödel’s reasoning, under which any formal system of Peano
Arithmetic - classically accepted as the foundation of all our mathematical
languages - is verifiably complete in the above sense. We show how some
paradoxical concepts of Quantum mechanics can, then, be expressed, and
interpreted, naturally under a constructive definition of mathematical truth.
Contents[2]
I Do
Gödel’s Theorems limit our ability to mathematically express, and communicate,
mental concepts?
I-2 When is a proposition true in a
constructive, and intuitionistically unobjectionable, way?
I-3 What exactly does this mean, and why is the
distinction important?
I-4 A
constructive definition of Tarskian satisfiability
I-5 Extending
Church’s Thesis and defining effective computability
I-6 Some consequences, and a definition of uniform
completeness
I-7 The Uniform Church Thesis and the classical
Church-Turing Theses
II Some significant
issues in interpreting classical theory constructively
II-1 Are Platonism and Formalism incompatible
doctrines?
II-2 Is
mathematical truth verifiable effectively?
II-3 What is the significance of Gödel's First
Incompleteness Theorem?
II-4 What
is the significance of Turing's Halting Theorem?
II-5 Can all mental concepts be expressed
mathematically?
2. Some of Gödel’s definitions
I Do Gödel’s Theorems limit our ability to mathematically
express, and communicate, mental concepts?
Classical[4] interpretations of Gödel’s formal reasoning and
conclusions - in his seminal 1931 paper, “On
formally undecidable propositions of Principia Mathematica and related systems
I” [Go31a], in which he introduces
his two, famous, “Incompleteness” Theorems - suggest that the classical,
Tarskian, truth[5] of some propositions[6] of a formal mathematical language[7], under an interpretation[8], is, both, non-algorithmic[9], and essentially unverifiable, constructively[10].
The
questions arise: Does this imply, first, that the determination of mathematical
truths, akin to that of scientific truths, is a process best described as
discovery; and, second, do Gödel’s Theorems set absolute limits on our ability
to mathematically express, and communicate, our mental concepts precisely, and
verifiably, in general, scientific, discourse[11]?
Since
it is not germane to the issue in these essays, we shall neither divert
ourselves with an exposition of the novel meta-mathematical, and logical,
features of these remarkable meta-theorems, nor with details of their
fascinating meta-proofs[12]. For the purist, Gödel’s original, 1931, paper (cf. [Go31a] and [Go31b]) remains unsurpassed as the
definitive source for a study of the Theorems, and of their immediate
consequences. For the interested, popular discussions of the Theorems, and of
their commonly perceived meanings and implications, are lucidly provided, and
extensively referenced, by Penrose in [Pe90],
and in [Pe94].
What
interests us here, rather, is the possibility that there may be a “loophole”, in
the classical interpretation of Gödel’s formal reasoning, which allows us to
define mathematical truth in an effectively verifiable way. We, thus, limit
ourselves to reviewing, essentially from a layperson’s perspective, the
argument that any formal system of
Specifically,
we consider whether the classical interpretation of Gödel’s argument - that
there is some undecidable[16] arithmetical proposition (which we may refer to as
GUS, and formally write as the well-formed formula[17] [(Ax)R(x)]) that is
unprovable[18] in PA, but true, under the standard interpretation[19] M of PA - is constructive, and intuitionistically
unobjectionable[20].
We then
consider whether, under a suitably constructive interpretation of classical, Tarskian, truth, and of Gödel’s reasoning,
any formal system of Peano Arithmetic
- classically accepted as the foundation of all our mathematical languages - is
verifiably complete, and indicate some consequences of such an interpretation.
We,
finally, address, and review, the questions[21]:
(1) Are Platonism and Formalism incompatible
doctrines?
(2) Is mathematical truth verifiable effectively?
(3) What is the significance of Gödel’s First Incompleteness
Theorem?
(4) What is the significance of Turing's Halting
Theorem?
(5) Can all mental concepts be expressed
mathematically?
(6) Can Peano Arithmetic model some of the more
paradoxical concepts of Quantum Mechanics?
I-2 When
is a proposition true in a constructive, and intuitionistically
unobjectionable, way?
Now, classically, Gödel’s
well-formed formula [(Ax)R(x)] does translate constructively as a true
sentence under the standard interpretation of PA. However, in general, there is
nothing intuitive or constructive - in the sense of being effectively
verifiable - about such “truths”.
Classically,
a formal proposition is “true” only if we accept:
Tarski’s
definition[22]: A well-formed formula [(Ax)F(x)] of a language L is true under an interpretation M of L if, and
only if, the interpreted relation[23], F(x), is satisfied by every x in M.
Although this appears
to be a fairly innocent formalisation of intuitive truth, we note, first,
that it is silent on the question of how, for any interpretation M, we can
effectively determine whether the relation F(x) is, indeed, satisfied by every x in M.
Second,
it does not distinguish between languages of expression, which are intended to
capture elements, of the mental gestalt of an individual, within a symbolic
language (reasonably, these would include our spoken and written languages, as
also sign languages, painting, sculpture, music, etc.), and languages of
communication, which are intended to distinguish, and effectively communicate,
those of such individual concepts that are accepted as lying within what may be
accepted, and termed, as a common collective of gestalts.
This
lack of distinction is reflected in the oft encountered - and, as we argue,
unnecessary[24] - controversy between those who believe that whatever
can be conceived must exist in a Platonic world, and those who believe that
only that which can be communicated effectively can be claimed to exist.
Moreover,
a significant consequence - of the failure to distinguish between Platonic
conception and effective communication - is that Tarski’s definition implicitly
commits us to admitting, in a formal language, such as, say, PA, implicit reference to Platonic
elements, in the domain of an interpretation M of PA, that are, clearly, non-intuitive, and
conceivable only subjectively in individual gestalts[25].
Thus,
the definition (implicitly) implies that we may (explicitly) assert the
closure of a formal relation under the universal quantifier as satisfied in M
if, and only if, the relation is individually, and collectively,
satisfied by all the elements in the ontology of M, even if some elements of
this ontology are not interpretations of any mathematical objects that
are representable[26] in PA!
Now, a
constructive view of Gödel’s reasoning, as suggested in these essays, is
that such a broad, and implicit (hence ambiguous), commitment is
unnecessary, even if it is not formally invalid. It should, then, follow that,
by the principle of Occams razor, we ought not to unrestrictedly assert
[R(x)] as collectively
satisfied by all x in the
standard interpretation M of PA,
although we may assert that [R(x)] is satisfied individually by any given x in M.
The
significance of this, last, distinction is that the totality of values for
which [R(x)] is
satisfied in M is not, then, constructively definable as a formal mathematical
object. In other words, the classical assumption that such values always define
a “set” in any Axiomatic Set Theory such as ZFC may, when interpreted
constructively, introduce an anomaly, if not an inconsistency. Thus, we may not
be able to make any constructively meaningful assertion about the totality of
values that satisfy [R(x)] in M.
More
precisely, we argue that every recursive[27] number-theoretic[28] relation need not be accepted as well-defining a
(recursively enumerable[29]) sub-set of the natural numbers in any Axiomatic Set
Theory that is a consistent[30] extension of PA[31], if we define a mathematical
object and a set constructively as follows:
Definition (i): A primitive mathematical object, of a formal
mathematical language, L, is any symbol for an individual constant, predicate
letter, or a function letter (cf. [Me64], p46;
also p1, p10), which is defined as a
primitive symbol of L.
Definition (ii): A formal mathematical object, of a formal
mathematical language, L, is any symbol for an individual constant, predicate
letter, or a function letter that is either a primitive mathematical object of
L, or one that can be introduced through definition (cf. [Me64], p82) into L without inviting
inconsistency.[32]
Definition (iii): A mathematical object, of a formal
mathematical language, L, is any symbol that is either a primitive, or a
formal, mathematical object of L.
Definition (iv): A set, in the domain of any interpretation,
M, of a formal mathematical language, L, is the range of any function in M that
is an interpretation of a function letter that is a mathematical object of L.
Constructively,
as a consequence of the arguments cited above, expressions such as “(Ax)F(x)”, and “(Ex)F(x)”, in an interpretation M of a formal theory P,
may be taken to mean[33] “F(x) is true for all x in M”, and “F(x) is true for some x in M”, respectively, if, and only if, the predicate letter “F”
is a formal mathematical object in P.
In the
absence of a meta-proof that “F” is, indeed, such a mathematical object,
the expressions “(Ax)F(x)” and “(Ex)F(x)” ought,
constructively, only be taken to mean that “F(x) is true for any given x in M”, and “It is not true that F(x) is false for any given x in M”, indicating that the predicate “F(x)” is well-defined, and decidable, for any given
value of x, but that there
may not be any uniformly effective
method for such decidability.
I-3 What
exactly does this mean, and why is the distinction important?
The
question arises: What exactly does this mean, and why is the distinction
important?
Taking the
latter part of the question first, the distinction is important because we
do not, then, need to accept absolute limits on our ability to adequately
formalise, and effectively communicate, mathematical concepts that are accepted
as being common to a collective of gestalts[34].
Now, a
central issue in the development of any significant Artificial Intelligence
is that of understanding[35], and finding, effective methods of duplicating the
cognitive and expressive processes of the human mind. This issue is being
increasingly brought into sharper focus by the rapid advances in the
experimental, behavioral, and computer sciences[36].
Penrose’s
“The Emperor’s New Mind” and “Shadows of the Mind” highlight what is striking
about the attempts, and struggles, of current work in these areas
to express their observations adequately - necessarily in a predictable
way[37] - within the standard interpretations of
formal propositions as offered by classical theory.
So, the
question arises: Are formal classical theories essentially unable to
adequately express the extent and range of human cognition, or does the problem
lie in the way formal theories are classically interpreted at the moment?
The
former addresses the question of whether there are absolute limits on our
capacity to express human cognition unambiguously; the latter, whether there
are only temporal limits - not necessarily absolute - to the capacity of
classical interpretations to communicate unambiguously that which we
intended to capture within our formal expression.
Now, a
thesis of these essays is that we may comfortably reject the first,
by recognising that we can, indeed, constructively extend Tarski’s definitions, of the
“satisfiability” and “truth” of formal relations and propositions,
respectively, under a given interpretation, verifiably.
I-4 A constructive definition of Tarskian
satisfiability
So, we
return to the first part of the earlier question: What exactly does this
mean?
Well,
it means that we can, for instance, replace the strong[38], classical, implicit interpretation of Tarski’s non-constructive definition,
which is essentially the assertion:
(i)
Classical satisfiability: The
well-formed formula [F(x)] of a formal system P is satisfied classically under an
interpretation M of P if, and only if, the interpreted predicate F(x) is satisfied collectively, and individually,
by the elements in the domain of M,
by
the weaker, explicit assertion:
The well-formed formula [F(x)] of a formal system P is satisfied constructively
under an interpretation M of P if, and only if, the
interpreted predicate F(x) is satisfied either collectively, or individually,
by the elements in the domain of M.
We can,
further, eliminate any implicit commitment to a Platonic ontology by making
this definition
constructive - in the sense of being effectively verifiable, as follows:
(ii) Individual satisfiability: The well-formed formula [F(x)] of a formal system P is individually
satisfied under an interpretation M of P if, and only if, given any
value k in M, there is an
individually effective method (which may depend on the value k) to determine that the interpreted proposition F(k) is satisfied in M.
(iii) Uniform satisfiability: The well-formed formula [F(x)] of a formal system P is uniformly[39] satisfied under an interpretation M of P if, and
only if, there is a uniformly
effective method (necessarily independent of x) such that, given any value k in M, it can determine that the interpreted
proposition F(k) is
satisfied in M.
(iv)
Constructive satisfiability:
The well-formed formula [F(x)] of a formal system P is constructively satisfied under an
interpretation M of P if, and only if, it is either uniformly satisfied in
M, or it is individually satisfied in M.
Clearly,
if [F(x)] is uniformly
satisfied in M, then it is, obviously, individually satisfied in M. However, does
the converse hold? More to the point, could Gödel’s undecidable
proposition, [(Ax)R(x)], be an instance of a formula [R(x)] that is individually satisfied in M
(since Gödel shows that [R(k)] is provable in P for any numeral [k]), but not uniformly satisfied in M?[40]
An interesting consequence of an affirmative answer to this question would be that the interpreted arithmetical predicate R(x) - which is instantiationally equivalent[41] to a primitive recursive relation - becomes Turing-undecidable[42]! Prima facie, this would appear to conflict with the classical postulation that a number-theoretic function is Turing-computable if, and only if, it is partial recursive[43]. However, the conflict may be illusory: the proof of equivalence seems to presume[44] that there is always a uniformly effective method for computing any given partial recursive function